Not Logged In

Adding local exploration to greedy best-first search for satisficing planning

Full Text: 2014-AAAI-Local-Exploration.pdf PDF

Greedy Best-First Search (GBFS) is a powerful algorithm at the heart of many state of the art satisficing planners. One major weakness of GBFS is its behavior in so-called uninformative heuristic regions (UHRs) - parts of the search space in which no heuristic provides guidance towards states with improved heuristic values. This work analyzes the problem of UHRs in planning in detail, and proposes a two level search framework as a solution. In Greedy Best-First Search with Local Exploration (GBFSLE), a local exploration is started from within a global GBFS whenever the search seems stuck in UHRs. Two different local exploration strategies are developed and evaluated experimentally: Local GBFS (LS) and Local Random Walk Search (LRW). The two new planners LAMA-LS and LAMA-LRW integrate these strategies into the GBFS component of LAMA-2011. Both are shown to yield clear improvements in terms of both coverage and search time on standard International Planning Competition benchmarks, especially for domains that are proven to have large or unbounded UHRs.

Citation

F. Xie, M. Müller, R. Holte. "Adding local exploration to greedy best-first search for satisficing planning". National Conference on Artificial Intelligence (AAAI), (ed: Carla E. Brodley, Peter Stone), pp 2388-2394, July 2014.

Keywords:  
Category: In Conference
Web Links: AAAI

BibTeX

@incollection{Xie+al:AAAI14,
  author = {Fan Xie and Martin Müller and Robert Holte},
  title = {Adding local exploration to greedy best-first search for satisficing
    planning},
  Editor = {Carla E. Brodley, Peter Stone},
  Pages = {2388-2394},
  booktitle = {National Conference on Artificial Intelligence (AAAI)},
  year = 2014,
}

Last Updated: June 30, 2020
Submitted by Sabina P

University of Alberta Logo AICML Logo