Guaranteeing Completeness in FF

FF first attempts to search for a solution plan by performing Enforced Hill-Climbing (EHC) search from the initial state towards the goal state. As discussed earlier, EHC uses hill-climbing local search guided by the RPG heuristic while a strictly-better successor can be found. As soon as no strictly better successor can be found, FF has entered a plateau, and breadth-first search is used until an improving state is found. In directed search spaces, EHC can lead the search process in the wrong direction and to dead-ends; i.e. the open list is empty, but no goal state has been found. In these cases FF resorts to best-first search from the initial state, thereby preserving completeness.



Andrew Coles and Amanda Smith 2007-01-09