Controlled search over compact state representations, in nondeterministic planning domains and beyond

Two of the most efficient planners for planning in nondeter- ministic domains are MBP and ND-SHOP2. MBP achieves its efficiency by using Binary Decision Diagrams (BDDs) to represent sets of states that share some common properties, so it can plan for all of these states simultaneously. ND-SHOP2 achieves its efficiency by using HTN task decomposition to focus the search. In some environments, ND-SHOP2 runs exponentially faster than MBP, and in others the reverse is true. In this paper, we discuss the following:• We describe how to combine ND-SHOP2’s HTNs with MBP’s BDDs. Our new planning algorithm, YoYo, per- forms task decompositions over classes of states that are represented as BDDs. In our experiments, YoYo easily outperformed both MBP and ND-SHOP2, often by sev- eral orders of magnitude.
• HTNsarejustoneofseveraltechniquesthatareoriginally developed for classical planning domains and that can be adapted to work in nondeterministic domains. By combin- ing those techniques with a BDD representation, it should be possible to get great speedups just as we did here.
• We discuss how these same ideas can be generalized for use in several other research areas, such as planning with Markov Decision Processes, synthesizing controllers for hybrid systems, and composing Semantic Web Services.