W2. Heuristics for Domain-independent Planning: Progress, Ideas, Limitations, Challenges

List of Papers

Chairs

Preface

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 boolean 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.

Yet,

• we do not yet fully understand why and when these various heuristics work well, and
• nor we do understand their limitations and the ways to overcome them.

As an illustration:

1. Consider the problem of building an ordered tower b1, ..., bn, with b1 on top, from an initial state where all blocks are on the table, except bn that is on b1. This is a trivial problem yet the extremely powerful FF planner would not solve it. Similar trivial unsolved examples can be constructed for other heuristic search planners.
2. Or the problem of finding plans that avoid certain states; eg. states that contain certain subsets of atoms (bad states): none of the standard heuristics seems to be able to take such additional information into account.
3. Or the more theoretical problem that in instances with quadratic length solutions, delete-relaxation heuristics are unlikely to work as delete-relaxed problems always have linear size plans.

For dealing with this and many other relevant problems, new ideas are needed. We hope that this workshop will establish a good tradition of having a regular venue for discussing and better understanding the ideas underlying current heuristics, their limitations, and the ways for overcoming them.

Committee

List of Papers