OHCP: A Local Search Planner Based on Ordered Hill Climbing Algorithm and Local-Minimal Restart Strategy
This paper describes OHCP, a fast planner using local search based on Ordered Hill Climbing (OHC) search algorithm and local-minimal restart strategy. OHC is used as a basis of a heuristic planner in conjunction with relaxed planning graph heuristic. A novel approach is proposed in OHC framework to extract useful information from relaxed plans to preorder all promising neighborhoods, which can cut down the frequency of calling the heuristic evaluation procedure. In order to preserve completeness and improve search effort, a new restart strategy for complete search from local minimal is proposed when the local search guided by OHC fails. The ideas are implemented in our planner OHCP. Experimental results show strong performance of the proposed planner on recent international planning competition domains.
Helen Zhang, Gang Shen and David Jin
R. S. Liang et al., "OHCP: A Local Search Planner Based on Ordered Hill Climbing Algorithm and Local-Minimal Restart Strategy", Advanced Materials Research, Vols. 219-220, pp. 1683-1688, 2011