Optimal Planners: The optimal approaches (CGP and GPT) tend not to scale as well, despite their good solutions. CGP has trouble constructing its planning graphs as the parallel conformant plan depth increases. CGP spends quite a bit of time computing mutexes, which increases the planning cost as plan lengths increase. CGP does much better on shallow and parallel domains like BT, where it can find one step plans that dunk every package in parallel.

GPT performs progression search that is guided by a heuristic that measures the cost of fully observable plans in state space. GPT finds optimal serial plans but is not as effective when the size of the search space increases. GPT fails to scale with the search space because it becomes difficult to even compute its heuristic (due to a larger state space as well).

YKA: YKA, like CAltAlt is a regression planner, but the search engine is very different and YKA
uses a cardinality heuristic. YKA performs well on all the domains because of its search engine based on BDDs. We notice a difference in progression and regression by comparing **P OND** to YKA, similar to trends found in the comparison between **P OND** and CAltAlt. Additionally, it seems YKA has a stronger regression search engine than CAltAlt. **P OND** is able to do better than YKA in the Rovers and Logistics domains, but it is unclear whether that it is because of the search direction or heuristics.

CFF: Conformant FF, a progression planner using a relaxed plan similar to the LUG relaxed plan, does very well in the Rovers and Logistics domains because it uses the highly optimized FF search engine as well as a cheap to compute relaxed plan heuristic. However, CFF does not do as well in the BT, BTC, Cube Center, and Ring problems because there are not as many literals that will be entailed by a belief state. CFF relies on implicitly representing belief states in terms of the literals that are entailed by the belief state, the initial belief state, and the action history. When there are very few literals that can be entailed by the belief state, reasoning about the belief state requires inference about the action history. Another possible reason CFF suffers is our encodings. The Cube Center and Ring domains are naturally expressed with multi-valued state features, and in our transformation to binary state features we describe the values that must hold but also the values that must not hold. This is difficult for CFF because the conditional effect antecedents contain several literals and its heuristic is restricted to considering only one such literal. It may be that CFF is choosing the wrong literal or simply not enough literals to get effective heuristics. However in BT and BTC where we used only one literal in effect antecedents CFF still performs poorly.

## 7.2 Conditional Planning

Table 9 shows the results for testing the conditional versions of the domains on **P OND**, MBP, GPT,
SGP, and YKA.

MBP: The **P OND** planner is very similar to MBP in that it uses progression search. **P OND** uses an AO* search, whereas the MBP binary we used uses a depth first And-Or search. The depth first search used by MBP contributes to highly sub-optimal maximum length branches (as much as an order of magnitude longer than **P OND**). For instance, the plans generated by MBP for the Rovers domain have the rover navigating back and forth between locations several times before doing anything useful; this is not a situation beneficial for actual mission use. MBP tends to not scale as well as **P OND** in all of the domains we tested. A possible reason for the performance of MBP
is that the Logistics and Rovers domains have sensory actions with execution preconditions, which prevent branching early and finding deterministic plan segments for each branch. We experimented