A Novel Technique for Avoiding Plateaus of Greedy Best-First Search in Satisficing Planning
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.
Cite
Text
Imai and Kishimoto. "A Novel Technique for Avoiding Plateaus of Greedy Best-First Search in Satisficing Planning." AAAI Conference on Artificial Intelligence, 2011. doi:10.1609/AAAI.V25I1.8004Markdown
[Imai and Kishimoto. "A Novel Technique for Avoiding Plateaus of Greedy Best-First Search in Satisficing Planning." AAAI Conference on Artificial Intelligence, 2011.](https://mlanthology.org/aaai/2011/imai2011aaai-novel/) doi:10.1609/AAAI.V25I1.8004BibTeX
@inproceedings{imai2011aaai-novel,
title = {{A Novel Technique for Avoiding Plateaus of Greedy Best-First Search in Satisficing Planning}},
author = {Imai, Tatsuya and Kishimoto, Akihiro},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2011},
pages = {985-991},
doi = {10.1609/AAAI.V25I1.8004},
url = {https://mlanthology.org/aaai/2011/imai2011aaai-novel/}
}