Bounded Branching and Modalities in Non-Deterministic Planning.
Blai Bonet · 2006
We study the consequences on complexity that arise when bounds on the number of branch points on the solutions for non-deterministic planning problems are imposed as well as when modal formulae are introduced into the description lan-guage. New planning tasks, such as whether there exists a plan with at most k branch points for a fully (or partially) observable non-deterministic domain, and whether there ex-ists a no-branch (a.k.a. conformant) plan for partially observ-able domains, are introduced and their complexity analyzed. Among other things, we show that deciding the existence of a conformant plan for partially observable domains with modal formulae is 2EXPSPACE-complete, and that the prob-lem of deciding the existence of plans with bounded branch-ing, for fully or partially observable contingent domains, has the same complexity of the conformant task. These re-sults generalize previous results on the complexity of non-deterministic planning and fill a slot that has gone unnoticed in non-deterministic planning, that of conformant planning for partially observable domains.