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.
|Title of host publication||Proceedings of the 10th International Symposium on Combinatorial Search|
|Subtitle of host publication||(SoCS 2017)|
|Editors||Alex Fukunaga, Akihiro Kishimoto|
|Number of pages||5|
|Publication status||Published - 5 Jun 2017|
|Event||10th Annual Symposium on Combinatorial Search - Pittsburgh, United States|
Duration: 16 Jun 2017 → 17 Jun 2017
Conference number: 10
http://socs17.dreamhosters.com/ (Link to Symposium Website )
|Conference||10th Annual Symposium on Combinatorial Search|
|Abbreviated title||SoCS 2017|
|Period||16/06/17 → 17/06/17|
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.