New Results in Bounded-Suboptimal Search

Maximilian Fickert, Tianyi Gu, Wheeler RumlAAAI 2022 · DOI

Introduction

In the field of bounded-suboptimal search, recent research suggests that simplicity often triumphs over algorithmic sophistication. While state-of-the-art methods like Explicit Estimation Search (EES) and Dynamic Potential Search (DPS) employ complex meta-reasoning to guide node expansion, a straightforward round-robin queue-switching scheme has been shown to significantly outperform them across a wide range of planning and search benchmarks.

Bounded-suboptimal search is critical for real-world applications where finding the absolute shortest path is computationally prohibitive. These algorithms guarantee a solution cost within a factor $w$ of the optimal cost. The core difficulty lies in balancing two competing objectives:

  1. Exploitation: Expanding nodes that appear to lead to a goal quickly to minimize search time.
  2. Bound-Raising: Expanding nodes that increase the lower bound on the optimal cost ($f_{min}$), ensuring the solution stays within the required suboptimality bound.

Traditional high-performance algorithms rely on online heuristic estimates to manage this balance. However, these estimates are often noisy, leading to inconsistent performance when the "meta-reasoning" logic is misled by inaccurate data.

The Round-Robin (RR) Scheme

To address the fragility of complex meta-reasoning, researchers investigated a Round-Robin (RR) approach. Instead of attempting to identify a single "best" node, the RR scheme maintains three separate queues and alternates between them:

  • Focal List: Contains nodes guaranteed to be within the bound, prioritized by a "speedy" heuristic (distance-to-go, $d$).
  • Inadmissible List: Contains nodes within the bound, prioritized by a potentially more accurate but non-guaranteed heuristic ($\hat{f}$).
  • Cleanup List: Contains all nodes, prioritized by the standard $f$-value to raise the lower bound ($f_{min}$).

By allocating a fixed portion of effort (one-third of expansions) to each queue, the algorithm ensures consistent progress toward both finding a goal and proving the suboptimality bound.

Empirical Evaluation

The authors conducted an extensive empirical comparison using two primary datasets:

  1. Classical Planning: 1,652 instances from 48 domains in the International Planning Competitions (IPC), implemented via the Fast Downward system.
  2. Classic Search Benchmarks: Standard AI problems including the 15-puzzle (with various cost models), Vacuum World, the Pancake problem, and Racetrack maps.

Key Results

Planning Performance

In the IPC benchmarks with a suboptimality bound of $w=1.5$, the simple RR-d algorithm (using distance $d$ in the focal list) achieved a normalized coverage of 60.7%. This outperformed previous state-of-the-art methods such as EES (57.0%) and DPS (60.0%). The variant RR-DXES achieved even higher coverage at 62.5%, further validating the robustness of the round-robin framework.

Coverage and performance metrics across IPC planning domains.

Search Performance

In classic search domains, the RR schemes demonstrated substantial speedups. In the "Heavy Tile" puzzle, for instance, RR-d and RR-DXES were often faster by an order of magnitude compared to EES and DPS. The RR approach proved remarkably robust; because it does not rely on a single inference rule, it is less susceptible to being "tricked" by misleading heuristic values in specific domains.

Performance comparison across classic search benchmarks.

Discussion and Insights

The success of the RR scheme highlights that sophistication can be a weakness. Mathematically elegant algorithms like DXES often fail because they focus too much on goal-seeking and neglect bound-raising, eventually running out of qualified nodes. The study underscores the importance of $f_{min}$—allocating a fixed portion of effort to raising the lower bound is a highly effective strategy, despite its simplicity.

Conclusion and Future Work

While the Round-Robin scheme is highly effective, it has limitations. It does not naturally converge to pure "speedy search" as the bound $w$ becomes very large, a property that algorithms like EES possess. Future research may explore more principled ways to dynamically allocate effort between queues without introducing the fragility seen in previous meta-reasoning attempts. Nonetheless, the current results establish the Round-Robin scheme as a new state-of-the-art for bounded-suboptimal search.

Summary updated

BibTeX
@inproceedings{fickert2022new,
  author = {Maximilian Fickert and Tianyi Gu and Wheeler Ruml},
  title = {{New Results in Bounded-Suboptimal Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i9.21256},
}

Loading related content...

Figure