Least-Bad-First Search on Plateaux

A plateau is encountered when all of the successor nodes of a given current node have a heuristic value that is the same as, or worse than, that of the current node. The notion of best in this context relates to the successor with the heuristic value closest to that of the parent state. This is called least-bad-first search because no chosen successor can make heuristic progress, but some choices are less negative than others. The successor chosen in least-bad-first search will have least negative impact on the current state and therefore is more likely to be on the best path to the goal. When breadth-first search is used, the exit state that is reached might be further from the goal than the exit state reached when the state with the least negative impact is always expanded next.

Figure 2: Least-bad-first search versus breadth-first search on a plateau. Black nodes are those expanded by breadth-first search. Dotted blue/grey nodes are those expanded by both breadth-first and least-bad-first search. Solid blue/grey nodes are those expanded by only least-bad-first search. It can be seen that least-bad-first search leads to a better exit node than does breadth-first search.

In Figure 2 we show the order in which states are explored using least-bad-first search relative to breadth-first search. It can be observed that, using least-bad-first search, the exit state reached has a better heuristic value than that reached using the breadth-first search in FF. It can be expected that this sometimes leads to better quality plans being found. Our results in Section 6.3 show that, indeed, using least-bad-first search we sometimes find shorter plans than FF finds using its standard breadth-first strategy on plateaux.