Freiburg, Germany
June 11-16, 2011
21st International Conference on Automated Planning and Scheduling

Heuristics for Domain-independent Planning

The aim of this workshop series is to further advance the understanding of the ideas underlying current heuristics, their limitations, and the ways for overcoming them. We seek crisp and meaningful ideas and understanding, rather than incremental improvements ('beating the competition'). Also, rather than merely being interested in the 'largest' problems that current heuristic search planners can solve, we are equally interested in the simplest problems that they can't actually solve well.


The full HDIP proceedings are available as pdf. The single papers are also linked in the schedule.


This schedule as a PDF file.

The workshop will be held on June 12, 2011 in hall 101–00–026 on the computer science campus.

Heuristics I
09:00-09:30 Emil Keyder, Miquel Ramirez and Hector Geffner
Heuristics with Choice Variables: Bridging the Gap between Planning and Graphical Models
09:30-10:00 Mohamed Elkawkagy, Pascal Bercher, Bernd Schattenberg, and Susanne Biundo
Landmark-Aware Strategies for Hierarchical Planning
10:00-10:30 Raz Nissim, Jörg Hoffmann and Malte Helmert
Computing Perfect Heuristics in Polynomial Time: On Bisimulation and Merge-and-Shrink Abstractions in Optimal Planning
Coffee Break
Heuristics II
11:00-11:30 Patrik Haslum, John Slaney and Sylvie Thiebaux
Incremental Lower Bounds for Additive Cost Planning Problems
11:30-12:30 Alan Fern
Learning Search Heuristics
(invited talk)
Lunch Break
Search I
14:00-14:30 Erez Karpas and Carmel Domshlak
Living on the Edge: Safe Search with Unsafe Heuristics
14:30-15:00 J. Benton, Patrick Eyerich and Subbarao Kambhampati
Enhancing Search for Satisficing Temporal Planning with Objective-driven Decisions
15:00-15:30 William Cushing, J. Benton and Subbarao Kambhampati
Cost Based Satisficing Search Considered Harmful
Coffee Break
Search II
16:00-16:30 Jussi Rintanen
Planning with SAT, Admissible Heuristics and A*
16:30-17:00 Nir Pochter, Aviv Zohar and Jeffrey Rosenschein
Exploiting Problem Symmetries in State-Based Planners
17:00-17:30 Roei Bahumi, Carmel Domshlak and Michael Katz
On Satisficing Planning with Admissible Heuristics

Call for papers

Motivation and Goals

The automatic derivation of heuristic estimators to guide the search has become one of the main approaches in domain-independent planning. The approach works: very large problems, with many state variables and operators can be solved in this way, that could not be solved before, and the approach appears to scale up better than others.

The workshop on heuristics for domain-independent planning so far took place in conjunction with ICAPS 2007 and ICAPS 2009, and was very successful both times. Many ideas presented at these workshops have led to contributions at major conferences and pushed the frontier of research on heuristic planning in several directions, both theoretically and practically. The workshops, as well as work on heuristic search that has been published since then, have also shown that there are many exciting open research opportunities in this area. Given the considerable success of the past workshops, we would like to continue holding it biennially.

We look for contributions that would help us understand better the ideas underlying current heuristics, their limitations, and the ways for overcoming them. Contributions do not have to show that a new heuristic or new varia- tion of a known heuristic ’beats the competition’. Above all we seek crisp and meaningful ideas and understanding. Also, rather than merely being interested in the ’largest’ problems that current heuristic search planners can solve, we are equally interested in the simplest problems that they can’t actually solve well.

The workshop series, while having originated mainly in classical planning, is very much open to new ideas on heuristic schemes for more general settings, such as temporal planning, planning under uncertainty and adversarial planning. We also explicitly wish to encourage submission of works, such as machine learn- ing of heuristic functions, that diverge from the wide-spread approach deriving heuristic values by solving relaxations/abstractions of the problem at hand.

Paper Formats Solicited

We welcome technical papers as well as position statements. Papers mixing these two aspects are welcome, too. We particularly welcome descriptions of open problems, approaches that didn’t turn out to perform as expected, or problems that existing techniques do not handle well – provided in each case that there is something the heuristic search planning community can learn from the presented observation. The papers should be formatted in AAAI style, and range between 2 and 6 pages. See for formatting instructions. Submission will be handled via our EasyChair site at

As the workshop is not an archival conference, multiple submissions are permitted. Work that is a strict subset of that recently previously published in an archival journal should be presented as a short position statement.

Papers that are currently under review in other conferences or journals must be formatted for blind review with no author or affiliation information listed.

Workshop Format

The workshop is planned to be a full 1-day format, but the precise format is to be decided as a function of the contributions received. We strive to have two types of presentations: long and short (15-20 and 5-10 minutes), and if appropriate a discussion session where the audience members are encouraged to participate.

Important Dates

  • Final date for camera-ready copy: May 20th, 2011
  • Workshop date: June 12th, 2011


Program Committee

  • J. Benton, Arizona State University, Tempe, AZ, USA
  • Hector Geffner, Universitat Pompeu Fabra, Barcelona, Spain
  • Adele Howe, Colorado State University, Fort Collins, CO, USA
  • Derek Long, University of Strathclyde, Glasgow, UK
  • Wheeler Ruml, University of New Hampshire, Durham, NH, USA
  • Vincent Vidal, ONERA, France
  • Sungwook Yoon, PARC, Palo Alto, CA, USA
  • Erez Karpas, Technion, Israel