Least-Bad-First Search versus Breadth-First Search

To assess the effect of using least-bad-first search rather than breadth-first search to escape plateaux in EHC search, we ran tests across a range of planning domains using each of the two search algorithms. The results of these tests are shown in Figures 10 and 11, illustrating the time taken to find a solution plan, and the makespan of the plan found.

Figure 10: CPU time showing a comparison between using breadth-first and least-bad-first search on plateau search on a range of domains (from left to right: Airport, Philosophers, Depots, Driverlog, Pipestankage-nontemporal, Satellite, FreeCell, Pipesnotankage-nontemporal). These results were generated without using macro-actions.

$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/BestFSPlateauxvsBreadthFSPlateaux/airport}$	$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/BestFSPlateauxvsBreadthFSPlateaux/philosophers}$
$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/BestFSPlateauxvsBreadthFSPlateaux/depots}$	$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/BestFSPlateauxvsBreadthFSPlateaux/driverlog}$
$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/BestFSPlateauxvsBreadthFSPlateaux/pipestankage-nontemporal}$	$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/BestFSPlateauxvsBreadthFSPlateaux/satellite}$
$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/BestFSPlateauxvsBreadthFSPlateaux/FreeCell}$	$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/BestFSPlateauxvsBreadthFSPlateaux/pipesnotankage-nontemporal}$

Figure 11: Makespan of plans produced using breadth-first and least-bad-first search during plateau search on a range of domains (from left to right: Airport, Philosophers, Depots, Driverlog, Pipestankage-nontemporal, Satellite, FreeCell, Pipesnotankage-nontemporal). These results were generated without using macro-actions.

$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/BestFSPlateauxvsBreadthFSPlateauxMakespan/airport}$	$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/BestFSPlateauxvsBreadthFSPlateauxMakespan/philosophers}$
$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/BestFSPlateauxvsBreadthFSPlateauxMakespan/depots}$	$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/BestFSPlateauxvsBreadthFSPlateauxMakespan/driverlog}$
$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/BestFSPlateauxvsBreadthFSPlateauxMakespan/pipestankage-nontemporal}$	$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/BestFSPlateauxvsBreadthFSPlateauxMakespan/satellite}$
$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/BestFSPlateauxvsBreadthFSPlateauxMakespan/FreeCell}$	$\includegraphics[angle=0,width=0.47\textwidth]{JAIRresults/BestFSPlateauxvsBreadthFSPlateauxMakespan/pipesnotankage-nontemporal}$

As can be seen from the planning time and makespan graphs, using least-bad-first search rather than breadth-first search has no impact on planning time or solution plan quality in the Airport domain: the time spent searching plateaux is negligible, and the escape paths found are identical under the two plateau-search approaches.

In the Philosophers domain, search time is dramatically reduced by using least-bad-first search rather than breadth-first search on plateaux. Using least-bad-first search, all 48 problems are solved; using breadth-first search, only the first 14 are solved. The plans found in the first 14 have identical makespans, although the actions occur in differing orders in the two plans.

The search landscape provides some insights into why least-bad-first search is suited to this problem domain. At the start of the largest plateaux encountered, each action leads to a state with a strictly worse heuristic value; each of these corresponds to applying the action `queue-write' to a philosopher. From each of these, a state with a less-bad heuristic is visible. When using least-bad-first search, this less-bad state is considered before the others in the queue, avoiding the redundant search that would otherwise be performed by breadth-first search. Adding more philosophers to the problem causes a dramatic increase in the amount of redundant search performed when breadth-first search is used, leading to the observed performance improvement when a least-bad-first approach is taken.

In the Depots domain, we can observe the effect of differing exit points to plateaux when using least-bad-first and breadth-first search. When solving problem 18, least-bad-first search is able to solve the problem in substantially less time: EHC search is able to escape all the plateau encountered, and find a solution plan. Breadth-first search, however, leads to the termination of EHC, and exhaustive best-first search being used. On problem 15, however, breadth-first search is able to find a solution plan where least-bad-first search cannot; also, problem 5 is solved in much less time. In these two cases, it is not the success of breadth-first search on plateaux which leads to the improved performance, but its failure; EHC search terminates and resorts to best-first search in less time when breadth-first search is used than when least-bad-first search is used.

In the Driverlog domain, one additional problem, number 18, can be solved when least-bad-first search is used instead of breadth-first search. EHC using breadth-first search leads to a plateau which cannot be escaped, and EHC aborts without a solution plan; the resulting exhaustive best-first search cannot be completed within the allowed 30 minutes. The makespans of the plans found by the two approaches do not differ significantly.

In the Pipestankage-nontemporal domain, it can be seen that the use of least-bad-first search generally reduces the time taken to find solution plans. 34 problems are solved when using least-bad-first search compared to 30 when using breadth-first search and, in the majority of cases, the time taken to find a solution plan is reduced. The makespans of the resulting solution plans are generally increased when least-bad-first search is used, though, as the suboptimal exit paths found in this domain are often longer than the (optimal-length) paths found when breadth-first search is used.

In the Satellite domain using least-bad-first search leads to a reduction in planning time and, in many cases, a reduction of the makespan. In particular, the performance on problems 19 and 20 is substantially improved. The makespans on problems from 28 to 30 inclusive are also improved.

On the twenty standard benchmark FreeCell problems using least-bad-first search allows one additional problem to be solved within the 30 minute time limit. As with the results obtained when assessing the impact of macro-actions on planner performance, we obtained a more interesting and useful set of data. Figure 12 shows the results of these experiments: it can be seen that although least-bad-first search often improves the time taken to solve problems, the coverage overall is reduced, and no additional problems are solved where they previously were not.

In the Pipesnotankage-nontemporal domain, one additional problem can be solved using breadth-first search rather than least-bad-first search. Also, in many cases, the use of least-bad-first search increases the makespan of the solution plan found. Overall, although time reductions can occur when solving some problems when using least-bad-first search, the use of breadth-first search provides better overall performance both in terms of planning time and makespan.

Overall, it can be seen across the evaluation domains that the performance of the planner when using least-bad- or breadth-first search varies, in terms of planner execution time and plan quality: