Enforced Hill Climbing Search

Along with a heuristic based on relaxed planning graphs, FF introduced the Enforced Hill Climbing (EHC) algorithm, illustrated in Figure 1. EHC is based on the commonly used hill-climbing algorithm for local search, but differs in that breadth-first search forwards from the global optimum is used to find a sequence of actions leading to a heuristically better successor if none is present in the immediate neighbourhood.

Figure 1: Enforced Hill-Climbing Search

The key bottleneck in using EHC is where the search heuristic cannot provide sufficient guidance to escape a plateau¹ in a single action step, and breadth-first search is used until a suitable action sequence is found. Characteristically, EHC search consists of prolonged periods of exhaustive search, bridged by relatively quick periods of heuristic descent.

In practice, EHC guided by the RPG heuristic is an effective search strategy in a number of domains. Work has been done [Hoffmann 2005] on analysing the topology of the local-search landscape to investigate why it is an effective heuristic, as well as identifying situations in which it is weak.