Satisfiability planning with constraints on the number of actions
Markus Büttner
We investigate satisfiability planning with restrictions
on the number of actions in a plan.
Earlier work has considered encodings of sequential plans
for which a plan with the minimal number of time steps
also has the minimum number of actions, and parallel
(partially ordered) plans in which the number of actions
may be much higher than the number of time steps.
For a given problem instance finding a parallel plan
may be much faster than finding a corresponding sequential plan
but there is also the possibility that the parallel plan
contains unnecessary actions.
Our work attempts to combine the advantages of parallel
and sequential plans by efficiently finding parallel plans
with as few actions as possible.
We propose techniques for encoding parallel plans with
constraints on the number of actions. Then we give algorithms
for finding a plan that is optimal with respect to a given number
of steps and an anytime algorithm for successively finding better
and better plans.
We show that as long as guaranteed optimality is not required,
our encodings for parallel plans are often much more efficient
in finding plans of good quality than a sequential encoding.