ANU Computer Science Technical Reports
TR-CS-12-03
Jussi Rintanen.
Generation of Hard Solvable Planning Problems.
March 2012.
[POSTSCRIPT (352316 bytes)] [PDF (344766 bytes)]
Abstract: Existing models for sampling the space of
all planning problems produce both solvable and unsolvable instances. In
particular, when attempting to identify very hard ones, one encounters both,
as the hardness in the standard models is accompanied by the possibility of
an instance being solvable or unsolvable. This is a disadvantage of the
standard models, because of the strong asymmetry of planning algorithms in
handling solvable and unsolvable instances, and the preference to have
solvable instances for the performance evaluation of planners. We look at the
generation of hard problem instances that are guaranteed to have a plan. The
basic method generates a state sequence which induces a valid plan. The main
issue to be solved in this setting is the choice of the effects and the
preconditions of the actions in the plan so that finding the plan becomes
difficult. We provide solutions to this problem, and demonstrate its strength
in terms of an experimental study with different types of planners. We argue
that our methods are better suited to planner performance evaluation than the
ones proposed by Bylander and Rintanen.
Technical Reports <Technical-DOT-Reports-AT-cs-DOT-anu.edu.au>
Last modified: Mon Apr 16 09:56:27 EST 2012