Type-based exploration for satisficing planning with multiple search queues
Utilizing multiple queues in Greedy Best-First Search (GBFS) has been proven to be a very effective approach to satisficing planning. Successful techniques include extra queues based on Helpful Actions (or Preferred Operators), as well as using Multiple Heuristics. One weakness of all standard GBFS algorithms is their lack of exploration. All queues used in these methods work as priority queues sorted by heuristic values. Therefore, misleading heuristics, especially early in the search process, can cause the search to become ineffective. Type systems, as introduced for heuristic search by Lelis et al, are a development of ideas for exploration related to the classic stratified sampling approach. The current work introduces a search algorithm that utilizes type systems in a new way – for exploration within a GBFS multiqueue framework in satisficing planning. A careful case study shows the benefits of such exploration for overcoming deficiencies of the heuristic. The proposed new baseline algorithm Type-GBFS solves almost 200 more problems than baseline GBFS over all International Planning Competition problems. Type-LAMA, a new planner which integrates Type-GBFS into LAMA-2011, solves 36.8 more problems than LAMA-2011.
Citation
F. Xie,
M. Müller,
R. Holte,
T. Imai.
"Type-based exploration for satisficing planning with multiple search queues".
National Conference on Artificial Intelligence (AAAI), (ed: Carla E. Brodley, Peter Stone), pp 2395-2402, June 2014.
| Keywords: |
Planning, Heuristic Search, Exploration |
| Category: |
In Conference |
| Web Links: |
AAAI |
BibTeX
@incollection{Xie+al:AAAI14,
author = {Fan Xie and Martin Müller and Robert Holte and Tatsuya Imai},
title = {Type-based exploration for satisficing planning with multiple search
queues},
Editor = {Carla E. Brodley, Peter Stone},
Pages = {2395-2402},
booktitle = {National Conference on Artificial Intelligence (AAAI)},
year = 2014,
}Last Updated: June 30, 2020
Submitted by Sabina P 
