$POND$

We show the total time and the number of expanded nodes for $POND$ solving the conformant problems (including Ring and Cube Center) in Table 5, and for $POND$ solving the conditional problems in Table 6. As with CAltAlt we show the total time and number of expanded nodes for each test. We also add the $h_{s-RP}^{MG}$ heuristic, not implemented in CAltAlt, that takes the summation of the values of relaxed plans extracted from multiple planning graphs. We do not compute mutexes on any of the planning graphs used for heuristics in $POND$ mainly because we build planning graphs for each search node. We proceed by first commenting on the performance of $POND$ , with the different heuristics, in the conformant domains, then discuss the conditional domains.

Table 5: Results for $POND$ for conformant Rovers, Logistics, BT, BTC, Cube Center, and Ring. The data is Total Time (ms)/# Expanded Nodes, ``TO'' indicates a time out and ``-'' indicates no attempt.

Table 6: Results for $POND$ for conditional Rovers, Logistics, BTS, BTCS. The data is Total Time (ms)/# Expanded Nodes, ``TO'' indicates a time out (20 minutes) and ``-'' indicates no attempt.

In the conformant domains, $POND$ generally does better than CAltAlt. This may be attributed in part to implementation-level details. $POND$ makes use of an existing (highly optimized) BDD package for belief state generation in progression, but as previously mentioned, CAltAlt relies on a less optimized implementation for belief state generation in regression. As we will see in the next section, regression planners that employ a more sophisticated implementation perform much better, but could still benefit from our heuristics. Aside from a few differences that we will mention, we see similar trends in the performance of the various heuristics in both CAltAlt and $POND$ . Namely, the $NG$ and $SG$ heuristics have limited ability to help the planner scale, the $MG$ heuristics help the planner scale better but are costly, and the $LUG$ provides the best scalability. The difference between the $MG$ and the $LUG$ are especially pronounced in Cube Center and Ring, where the size of the initial belief state is quite large as the instances scale. Interestingly in Ring, breadth first search and the single graph relaxed plan are able to scale due to reduced heuristic computation time and the low branching factor in search. The $LUG$ is able to provide good search guidance, but tends to take a long time computing heuristics in Ring.

We are also now able to compare the choices for aggregating the distance measures from relaxed plans for multiple graphs. We see that taking the maximum of the relaxed plans, $h_{m-RP}^{MG}$ , in assuming positive interaction among worlds is useful in Logistics and Rovers, but loses the independence of worlds in the BT and BTC domains. However, taking the summation of the relaxed plan values for different worlds, $h_{s-RP}^{MG}$ is able to capture the independence in the BT domain. We notice that the summation does not help $POND$ in the BTC domain; this is because we overestimate the heuristic value for some nodes by counting the Flush action once for each world when it in fact only needs to be done once (i.e. we miss positive interaction). Finally, using the $h_{RPU}^{MG}$ heuristic we do well in every domain, aside from the cost of computing multiple graph heuristics, because we account for both positive interaction and independence by taking the overlap of relaxed plans. Again, with the $LUG$ relaxed plan, analogous to the multiple graph unioned relaxed plan, $POND$ scales well because we measure overlap and lower the cost of computing the heuristic significantly.

The main change we see in using $POND$ versus CAltAlt is that the direction of search is different, so the $h_{card}$ heuristic performs unlike before. In the BT and BTC domains cardinality does not work well in progression because the size of belief states does not change as we get closer to the goal (it is impossible to ever know which package contains the bomb). However, in regression we start with a belief state containing all states consistent with the goal and regressing actions limits our belief state to only those states that can reach the goal through those actions. Thus in regression the size of belief states decreases, but in progression remains constant.

The performance of $POND$ in the conditional domains exhibits similar trends to the conformant domains, with a few exceptions. Like the conformant domains, the $MG$ relaxed plans tend to outperform the $SG$ relaxed plan, but the $LUG$ relaxed plan does best overall. Unlike the conformant domains, The $h_{m-RP}^{MG}$ performs much better in BTS and BTCS over BT and BTC partly because the conditional plans have a lower average cost. The $h_{card}$ heuristic does better in BTS and BTCS over BT and BTC because the belief states actually decrease in size when they are partitioned by sensory actions.