Type-Based Exploration with Multiple Search Queues for Satisficing Planning

Fan Xie, Martin Müller, Robert Holte, Tatsuya ImaiAAAI 2014 · OpenReview

Abstract

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.

Introduction

In automated planning, "satisficing" search aims to find any valid plan efficiently. Greedy Best-First Search (GBFS) is the standard approach, relying on a heuristic function ($h$) to estimate the distance to the goal. However, GBFS is prone to the "early mistake" problem: if the heuristic is misleading early on, the search can become trapped in massive, unproductive subtrees. Standard exploration techniques like $\epsilon$-GBFS often fail because the "bad" regions of the search space are exponentially larger than the "good" ones, making random node sampling ineffective.

The Challenge of Misleading Heuristics

The core issue is that heuristics often concentrate the search in regions that do not contain the solution. As shown in Figure 4, in domains like "Nomystery," the vast majority of nodes in the open list are clustered around heuristic values far from the actual solution node. This concentration makes it nearly impossible for a standard greedy search to stumble upon the correct path if it starts in the wrong direction.

Distribution of nodes in the open list for Nomystery problems. The solution node (blue star) is often located in the extreme tail of the heuristic distribution, far from the peak where the search is concentrated.

Methodology: Type-Based Exploration

To address this, the authors introduce Type-GBFS, which leverages a Type System to ensure diverse exploration. A type system partitions search nodes into disjoint "buckets" based on features like the $(h(s), g(s))$ pair, where $g(s)$ is the path cost.

The Type-GBFS algorithm alternates between two steps:

  1. Greedy Step: Expands the best node from a standard priority queue to maintain search efficiency.
  2. Exploration Step: Selects a non-empty type bucket uniformly at random, then selects a node within that bucket uniformly at random.

By sampling types uniformly rather than nodes, the algorithm gives equal weight to rare, potentially promising states (e.g., those with high $g$-values that have bypassed a bottleneck) and common, misleading states. This logic was also integrated into the state-of-the-art LAMA-2011 planner, resulting in Type-LAMA.

Experimental Results

The approach was evaluated on 2,112 problems from International Planning Competitions (IPC).

  • Coverage: Type-GBFS solved nearly 200 more problems than standard GBFS. Type-LAMA improved upon LAMA-2011 by 36.8 problems.
  • Efficiency: In difficult instances, Type-GBFS achieved speedups of 10x to 50x.
  • Robustness: In the resource-constrained "Nomystery" domain, Type-GBFS solved 17/20 instances compared to 9/20 for standard GBFS.

Conclusion

Type-based exploration provides a robust "safety net" for heuristic search. While standard GBFS relies entirely on heuristic accuracy, Type-GBFS systematically explores different regions of the state space, allowing it to recover from early heuristic errors. Future work includes refining type granularity and investigating adaptive sampling strategies for different types.

Summary updated

Abstract

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.
BibTeX
@inproceedings{xie2014type,
  author = {Fan Xie and Martin Müller and Robert Holte and Tatsuya Imai},
  title = {{Type-Based Exploration with Multiple Search Queues for Satisficing Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  url = {https://openreview.net/forum?id=B1VbclZdWB},
}
Figure