OHCP: A Local Search Planner Based on Ordered Hill Climbing Algorithm and Local-Minimal Restart Strategy

Rui Shi Liang; Hui Ma; Min Huang

doi:10.4028/www.scientific.net/AMR.219-220.1683

Paper Titles

Research on Confidentiality about Provenance Based on Logical Key Hierarchy
p.1664

The Application of Fuzzy Clustering Method in the Division of Reservoir Flow Unit
p.1670

The Hardware in the Loop Simulation System of Speed Ratio Control on EMCVT
p.1675

Theoretical Analysis of Resource Swap for Reuse Based Hardware Task Scheduling in Reconfigurable System
p.1679

OHCP: A Local Search Planner Based on Ordered Hill Climbing Algorithm and Local-Minimal Restart Strategy
p.1683

Partial Friction Fault Diagnosis of Electrical Submersible Pump Based on Support Vector Machines
p.1689

Study on Economic Evaluation Index System of Oil–Gas Exploration Project
p.1693

The Implementation of MSK Based on DSP and Complex Bandpass Processing
p.1697

Algorithm of Disambiguation and Matching of Chinese Word Segmentation in Connected Strategies Research
p.1702

HomeAdvanced Materials ResearchAdvanced Materials Research Vols. 219-220OHCP: A Local Search Planner Based on Ordered Hill...

OHCP: A Local Search Planner Based on Ordered Hill Climbing Algorithm and Local-Minimal Restart Strategy

Abstract:

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.

You might also be interested in these eBooks

View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 219-220)

Pages:

1683-1688

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.219-220.1683

Citation:

Cite this paper

Online since:

March 2011

Authors:

Rui Shi Liang, Hui Ma, Min Huang

Keywords:

AI Planning, Local Search, Local-Minimal Restart Strategy, Ordered Hill Climbing Algorithm

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] Helmert M. 2003. Complexity results for standard benchmark domains in planning. Artificial Intelligence 143(2):219~262.

DOI: 10.1016/s0004-3702(02)00364-8

Google Scholar

[2] Fikes, R. Nilsson, N. 1971. STRIPS: A new approach to the application of theorem proving to problem solving. Artificial Intelligence 2: 189-208.

DOI: 10.1016/0004-3702(71)90010-5

Google Scholar

[3] International Planning Competition Archives official website: http://ipc.icaps-conference.org.

Google Scholar

[4] Bonet, B., Geffner, H. Planning as Heuristic Search. 2001. Artificial Intelligence 129:5-33.

DOI: 10.1016/s0004-3702(01)00108-4

Google Scholar

[5] Hoffmann, J. and Nebel, B. 2001. The FF planning system: Fast plan generation through heuristic search. Journal of Artificial Intelligence Research 14: 253-302.

DOI: 10.1613/jair.855

Google Scholar

[6] Gerevini, A. and Saetti, A. and Serina, I. 2003. Planning Through Stochastic Local Search and Temporal Action Graphs in LPG. Journal of Artificial Intelligence Research 20: 239-290.

DOI: 10.1613/jair.1183

Google Scholar

[7] Helmert, M. 2006. The fast downward planning system. Journal of Artificial Intelligence Research, 26: 191--246.

DOI: 10.1613/jair.1705

Google Scholar

[8] Blum A., Furst M. 1997. Fast Planning Through Planning Graph Analysis. Artificial Intelligence 90:281--300.

DOI: 10.1016/s0004-3702(96)00047-1

Google Scholar

[9] Hoffmann, J. 2005. Where Ignoring Delete Lists, Works: Local Search Topology in Planning Benchmarks. Journal of Artificial Intelligence Research 24: 685-758.

DOI: 10.1613/jair.1747

Google Scholar

[10] Koehler, J. and Nebel, B. and Hoffmann, J. and Dimopoulos, Y. 1997. Extending planning graphs to an ADL subset. In Proc. 4th European Conf. on Planning, 275-287.

DOI: 10.1007/3-540-63912-8_92

Google Scholar