Controlled Search over Compact State Representations, in Nondeterministic Planning Domains and Beyond

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 21

New Scientific and Technical Advances in Research (Nectar) Papers

Two of the most efficient planners for planning in nondeterministic 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: (1) We describe how to combine ND-SHOP2's HTNs with MBP's BDDs. Our new planning algorithm, YoYo, performs task decompositions over classes of states that are represented as BDDs. In our experiments, YoYo easily outperformed both MBP and ND-SHOP2, often by several orders of magnitude. (2) HTNs are just one of several techniques that are originally developed for classical planning domains and that can be adapted to work in nondeterministic domains. By combining those techniques with a BDD representation, it should be possible to get great speedups just as we did here. (3) 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.