Related Work

Much interest in conformant and conditional planning can be traced to CGP [30], a conformant version of GraphPlan [4], and SGP [31], the analogous conditional version of GraphPlan. Here the graph search is conducted on several planning graphs, each constructed from one of the possible initial states. More recent work on C-plan [10] and Frag-Plan [21] generalize the CGP approach by ordering the searches in the different worlds such that the plan for the hardest to satisfy world is found first, and is then extended to the other worlds. Although ${\cal C}{\sl AltAlt}$ and $POND$ utilize planning graphs similar to CGP and Frag-plan it only uses them to compute reachability estimates. The search itself is conducted in the space of belief states.

Another strand of work models conformant and conditional planning as a search in the space of belief states. This started with [15], who concentrated on formulating a set of admissible pruning conditions for controlling search. There were no heuristics for choosing among unpruned nodes. GPT [6] extended this idea to consider a simple form of reachability heuristic. Specifically, in computing the estimated cost of a belief state, GPT assumes that the initial state is fully observable. The cost estimate itself is done in terms of reachability (with dynamic programming rather than planning graphs). GPT's reachability heuristic is similar to our $h_{m-RP}^{MG}$ heuristic because they both estimate the cost of the farthest (maximum distance) state by looking at a deterministic relaxation of the problem. In comparison to GPT, ${\cal C}{\sl AltAlt}$ and $POND$ can be seen as using heuristics that do a better job of considering the cost of the belief state across the various possible worlds.

Another family of planners that search in belief states is the MBP-family of planners--MBP [3], and KACMBP [1]. In contrast to ${\cal C}{\sl AltAlt}$ but similar to $POND$ , the MBP-family of planners all represent belief states in terms of binary decision diagrams. Action application is modeled as modifications to the BDDs. MBP supports both progression and regression in the space of belief states, while KACMBP is a pure progression planner. Before computing heuristic estimates, KACMBP pro-actively reduces the uncertainty in the belief state by preferring uncertainty reducing actions. The motivation for this approach is that applying cardinality heuristics to belief states containing multiple states may not give accurate enough direction to the search. While reducing the uncertainty seems to be an effective idea, we note that (a) not all domains may contain actions that reduce belief state uncertainty and (b) the need for uncertainty reduction may be reduced when we have heuristics that effectively reason about the multiple worlds (viz., our multiple planning graph heuristics). Nevertheless, it could be very fruitful to integrate knowledge goal ideas of KACMBP and the reachability heuristics of ${\cal C}{\sl AltAlt}$ and $POND$ to handle domains that contain both high uncertainty and costly goals.

In contrast to these domain-independent approaches that only require models of the domain physics, PKSPlan [26] is a forward-chaining knowledge-based planner that requires richer domain knowledge. The planner makes use of several knowledge bases, as opposed to a single knowledge base taking the form of a belief state. The knowledge bases separate binary and multi-valued variables, and planning and execution time knowledge.

YKA [28] is a regression conditional planner using BDDs that uses a cardinality heuristic. Recently Rintanen has also developed related reachability heuristics that consider distances for groups of states, which do not rely on planning graphs [29].

More recently, there has been closely related work on heuristics for constructing conformant plans within the CFF planner [17]. The planner represents belief states implicitly through a set of known facts, the action history (leading to the belief state), and the initial belief state. CFF builds a planning graph forward from the set of known literals to the goal literals and backwards to the initial belief state. In the planning graph, conditional effects are restricted to single literals in their antecedent to enable tractable 2-cnf reasoning. From this planning graph, CFF extracts a relaxed plan that represents supporting the goal belief state from all states in the initial belief state. The biggest differences between the $LUG$ and the CFF technique are that the $LUG$ reasons only forward from the source belief state (assuming an explicit, albeit symbolic, belief state), and the $LUG$ does not restrict the number of literals in antecedents. As a result, the $LUG$ does not lose the causal information nor perform backward reasoning to the initial belief state.

Our handling of uncertainty through labels and label propagation is reminiscent of and related to de Kleer's assumption based truth maintenance system (ATMS) [14]. Where an ATMS uses labels to identify the assumptions (contexts) where a particular statement holds, a traditional truth maintenance system requires extensive backtracking and consistency enforcement to identify other contexts. Similarly, where we can reason about multiple possible worlds (contexts) with the LUG simultaneously, the MG approach requires, not backtracking, but reproduction of planning graphs for other possible worlds.

Finally, ${\cal C}{\sl AltAlt}$ and $POND$ are also related to, and an adaptation of the work on reachability heuristics for classical planning, including $AltAlt$ [23], FF [18] and HSP-r [5]. ${\cal C}{\sl AltAlt}$ is the conformant extension to $AltAlt$ that uses regression search (similar to HSP-r) guided by planning graph heuristics. $POND$ is similar to FF in that it uses progression search with planning graph heuristics.