A Novel Technique for Avoiding Plateaus of Greedy Best-First Search in Satisficing Planning

Let h be a heuristic function selected for expansions when GBFS with the FF heuristic that estimates the distance to a goal from a node n. GBFS (Hoffmann and Nebel 2001) solves a planning problem. The selects the best node n with the smallest h(n) in the open list horizontal axis indicates each expansion of the best node that maintains nodes that have been generated but have not n in the open list and the vertical axis represents n's corresponding been expanded yet. It then expands n to generate n's successors, heuristic value for that expansion. Circles, the and saves these successors in the open list, unless triangle, and diamond represent expanding nodes that are they have been previously added to the open list.