The CAltAlt and POND Planners

CAltAlt - Conformant AltAlt is a regression planner that searches in belief space with conditional actions to find conformant plans. The innovation of CAltAlt is its heuristic guidance approach based on planning graphs. It relies on a Labelled Uncertainty Graph (LUG), a condensed version of the multiple graphs used in CGP, for extracting heuristics to guiding search. The LUG can make use of a wide variety of mutex relations; the most expressive are similar to CGP. [Contact us for Linux Binary]

POND - Partially Observable Non-Deterministic planner is a progression search belief space planner that uses LAO* search over belief states represented with BDDs. POND's search is guided by heuristics from the LUG to find conformant and contingent plans. It can find plans that take the form of directed acyclic graphs. Although POND allows observations and it uses the LUG for heuristics, it does not incorporate observations or knowledge into the heuristics, yet! Unlike CAltAlt, POND does not use mutexes in its construction of the LUG. [Linux Binary available]

Papers

Daniel Bryce and Subbarao Kambhampati, "Heuristic Guidance Measures for Conformant Planning", ICAPS 2004.[pdf] [slides]
Daniel Bryce, Subbarao Kambhampati, and David E. Smith, "Planning in Blief Space with a Labelled Uncertainty Graph", AAAI 2004 Workshop on Learning and Planning in Markov Processes -- Advances and Challenges.[pdf]
Daniel Bryce, Subbarao Kambhampati, and David E. Smith, "Planning Graph Heuristics for Belief Space Search", ASU TR0605, 2005.[pdf] [domains] [Linux Binary availabe]
William Cushing and Daniel Bryce, "State Agnostic Planning Graphs: and their application to belief space planning", AAAI 2005. [pdf] [domains] [Linux Binary available ] [slides] [supporting materials] [audio from talk]
Daniel Bryce, and Subbarao Kambhampati, "Cost Sensitive Reachability Heuristics for Handling State Uncertainty", UAI, 2005.[pdf] [Linux Binary available] [domains]

Background: Lynx Lake, Prescott, AZ 9/6/03 (a "pond" in Dan's hometown, still looking for a picture of a CAltAlt...)