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.