Automated Planning with Adapted Enforced Hill Climbing

Planning systems based on heuristic search methods are a new class of planners that aim to solve planning problems more efficiently. Enforced Hill Climbing (EHC) is a technique often used in many AI Planning Systems, which was originally introduced by FF planner. It is a method guided by heuristics that combines the algorithm Hill Climbing (HC) with breadth-first search in order to escape from local maxima, which is a problem faced by local search algorithms. Although this method presents an enhanced performance when compared to alternative methods used in many of the other planning domains, it shows some weaknesses. For some planning problems EHC cannot escape from local maximum and might get stuck at dead ends, which leads to a failure. In this paper we present an extension of EHC to avoid the problems mentioned before. It has some optimizations such as a heap to store the states to be evaluated. This data structure helps the search process to escape from local maxima. Another modification is the use of backtracking when the search goes into dead ends. Experiments show significant improvements of our approach compared to the standard form of EHC when solving planning problems.