Fast Detection of Unsolvable Planning Instances Using Local Consistency
By Christer Bäckström, Peter Jonsson, Simon Ståhlberg. 2013
41 citations recorded by the source corpus.
There has been a tremendous advance in domain-independent planning over the past decades, and planners have become increasingly efficient at finding plans. However, this has not been paired by any corresponding improvement in detecting unsolvable instances. Such instances are obviously important but largely neglected in planning. In other areas, such as constraint solving and model checking, much effort has been spent on devising methods for detecting unsolvability. We introduce a method for detecting unsolvable planning instances that is loosely based on consistency checking in constraint programming. Our method balances completeness against efficiency through a parameter k: the algorithm identifies more unsolvable instances but takes more time for increasing values of k. We present empirical data for our algorithm and some standard planners on a number of unsolvable instances, demonstrating that our method can be very efficient where the planners fail to detect unsolvability within reasonable resource bounds. We observe that planners based on the h^m heuristic or pattern databases are better than other planners for detecting unsolvability. This is not a coincidence since there are similarities (but also significant differences) between our algorithm and these two heuristic methods.
Subfields: Artificial Intelligence, Computer Networks and Communications
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Marcel Steinmetz
- Jörg Hoffmann
- Peter Kissmann
- Á. Torralba
- Malte Helmert
- Paolo Traverso
- Malik Ghallab
- Dana S. Nau
In Computer Networks and Communications
Citations in the corpus
- "Distance"? Who Cares? Tailoring Merge-and-Shrink Heuristics to Detect Unsolvability (2014, background): “Our work is partly inspired by recent work [1] on unsolvable planning problems, testing whether projections onto a subset of variables (a special case of M&S) are unsolvable, where the tested variable subsets are systematically enumerated (starting with small ones).”
- Towards Clause-Learning State Space Search: Learning to Recognize Dead-Ends (2016, background): “Recent work (B¨ackstr¨om, Jonsson, and St˚ahlberg 2013; Hoffmann, Kissmann, and Torralba 2014) has started to break with this tradition, introducing the concept of unsolvability heuristics , dedicated to dead-end detection.”