A Novel Technique for Avoiding Plateaus of Greedy Best-First Search in Satisficing Planning

Authors

  • Tatsuya Imai Tokyo Institute of Technology
  • Akihiro Kishimoto Tokyo Institute of Technology

DOI:

https://doi.org/10.1609/aaai.v25i1.8004

Abstract

Greedy best-first search (GBFS) is a popular and effective algorithm in satisficing planning and is incorporated into high-performance planners. GBFS in planning decides its search direction with automatically generated heuristic functions. However, if the heuristic functions evaluate nodes inaccurately, GBFS may be misled into a valueless search direction, thus resulting in performance degradation. This paper presents a simple but effective algorithm considering a diversity of search directions to avoid the errors of heuristic information. Experimental results in solving a variety of planning problems show that our approach is successful.

Downloads

Published

2011-08-04

How to Cite

Imai, T., & Kishimoto, A. (2011). A Novel Technique for Avoiding Plateaus of Greedy Best-First Search in Satisficing Planning. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1), 985-991. https://doi.org/10.1609/aaai.v25i1.8004

Issue

Section

Reasoning about Plans, Processes and Actions