Improving Plan Quality through Heuristics for Guiding and Pruning the Search: A Study Using LAMA

Francesco Percassi, Alfonso Emilio Gerevini, Hector Geffner

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)

Abstract

Admissible heuristics are essential for optimal planning in the context of search algorithms like A*, and they can also be used in the context of suboptimal planning in order to find quality-bounded solutions. In satisfacing planning, on the other hand, admissible heuristics are not exploited by the best-first search algorithms of existing planners even when a time window is available for improving the first solution found. For example, in the well-know planner LAMA, better solutions within such a time window are sought by restarting a Weighted-A* search guided by inadmissible heuristics, each time a better solution is found. In this paper, we investigate the use of admissible heuristics in the context of LAMA for pruning nodes that cannot lead to better solutions. The revised search of LAMA is experimentally evaluated using two alternative admissible heuristics for pruning and three types of problems: planning with soft goals, planning with action costs, and planning with both action costs and soft goals. Soft goals are compiled into hard goals following the approach of Keyder and Geffner. The empirical results show that the use of admissible heuristics in LAMA can be of great help to improve the planner performance.
Original languageEnglish
Title of host publicationProceedings of the 10th International Symposium on Combinatorial Search
Subtitle of host publication(SoCS 2017)
EditorsAlex Fukunaga, Akihiro Kishimoto
PublisherAAAI press
Pages144-148
Number of pages5
ISBN (Print)9781577357902
Publication statusPublished - 5 Jun 2017
Externally publishedYes
Event10th Annual Symposium on Combinatorial Search - Pittsburgh, United States
Duration: 16 Jun 201717 Jun 2017
Conference number: 10
http://socs17.dreamhosters.com/ (Link to Symposium Website )

Conference

Conference10th Annual Symposium on Combinatorial Search
Abbreviated titleSoCS 2017
CountryUnited States
CityPittsburgh
Period16/06/1717/06/17
Internet address

Fingerprint Dive into the research topics of 'Improving Plan Quality through Heuristics for Guiding and Pruning the Search: A Study Using LAMA'. Together they form a unique fingerprint.

  • Cite this

    Percassi, F., Gerevini, A. E., & Geffner, H. (2017). Improving Plan Quality through Heuristics for Guiding and Pruning the Search: A Study Using LAMA. In A. Fukunaga, & A. Kishimoto (Eds.), Proceedings of the 10th International Symposium on Combinatorial Search: (SoCS 2017) (pp. 144-148). AAAI press.