Linux 32 executable with scripts (gzipped tar)

IPC-5 Booklet Abstract

Workshop paper

Slides

Model Checking Integrated Planning in
MIPS-XXL

The MIPS-XXL planner, as applied in the 2006 competition invokes two different search algorithms: in the first 5 of 30 minutes it does internal cost-optimized heuristic search. If this fails to find a solution, for the rest of the 25 minutes run time the planner is exectued using disk space to bypass main memory limits.

The planner is capable of parsing full PDDL3 and the results obtained with the planner are remarkably good (for complex domains often by far better than the ones generated winner of the satisficing track of the 2006 competition). In the limit, our planner guarantees cost-optimality, even though - by the space and time constraints - for many domains this limit is not to be achieved.

Both search algorithms perform explicit forward search, and are, therefore, very different to the symbolic approach taken in MIPS-BDD.

The first search algorithms is an anytime-wrapper on a heuristic best-first search with numerical state variables. The heuristic is very much the same as the one for Metric-FF developled by J. Hoffmann. Every time a new plan of quality Q is found, an additional constraint to the goal, forcing the next plan to be better. Temporal plans are generated by posterior PERT scheduling of the sequential plans generated.

The second search algorithms for the planner executes strategies for external memory based optimal planning. An external breadth-first search exploration algorithm is devised maintaining the currently best solution, such that the approach is guaranteed to find the cost-optimal solution in the limit.

The full breadth-first cost-optimizing search has been accelerated by including beam-search. From a given level only the k-best states are expanded. We observed that this allows to find very good solutions in very large depth.

The planner does not apply any heurisitic guidance, even though a variant for enforced hill-climbing has been devised.


MIPS-XXL

Stefan Edelkamp (stefan.edelkamp@cs.uni-dortmund.de)