Implementation

Figure 9: The implementations of CAltAlt and $POND$ rely on many existing technologies. The search engine is guided by heuristics extracted from planning graphs.

The implementation of CAltAlt uses several off-the-shelf planning software packages. Figure 9 shows a diagram of the system architecture for CAltAlt and $POND$ . While CAltAlt extends the name of $AltAlt$ , it relies on a limited subset of the implementation. The components of CAltAlt are the IPC parser for PDDL 2.1 (slightly extended to allow uncertain initial conditions), the HSP-r search engine [5], the IPP planning graph [20], and the CUDD BDD package [7] to implement the $LUG$ labels. The custom parts of the implementation include the action representation, belief state representation, regression operator, and the heuristic calculation.

The implementation of $POND$ is very similar to CAltAlt aside from the search engine, and state and action representation. $POND$ also uses the IPP source code for planning graphs. $POND$ uses modified LAO* [16] source code from Eric Hansen to perform AO* search, and CUDD [7] to represent belief states and actions. Even with deterministic actions it is possible to obtain cycles from actions with observations because we are planning in belief space. $POND$ constructs the search graph as a directed acyclic graph by employing a cycle-checking algorithm. If adding a hyper-edge to the search graph creates a cycle, then the hyper-edge cannot represent an action in a strong plan and is hence not added to the graph.