Best-First Utility-Guided Search

Wheeler Ruml, Minh Binh DoIJCAI 2007

Introduction

In many real-world pathfinding and planning scenarios, the goal is not just to find a solution, but to find a high-quality solution within a reasonable timeframe. Traditional algorithms like A* provide optimal solutions but can be prohibitively slow. Conversely, greedy searches find solutions quickly but often at the expense of quality.

The standard approach to this trade-off has been the use of anytime algorithms (e.g., ARA or Anytime A), which find an initial suboptimal solution and iteratively improve it. However, these algorithms suffer from a significant "meta-reasoning" challenge: determining exactly when to stop. Effective termination typically requires extensive "performance profiling" — prior domain-specific testing to predict if further search will yield worthwhile improvements. The authors of "Best-First Utility-Guided Search" argue that this approach is inherently suboptimal because the search process remains "ignorant" of the user's specific utility preferences until the very end.

The BUGSY Algorithm

To address these limitations, the authors introduce BUGSY (Best-first Utility-Guided Search—Yes!). BUGSY moves the utility trade-off from a post-hoc termination policy directly into the search guidance mechanism itself.

Utility-Driven Guidance

BUGSY operates by maximizing a user-defined linear utility function:

$$U(n) = U_{default} - (w_f \cdot f(s) + w_t \cdot t(s))$$

where $f(s)$ is the solution cost and $t(s)$ is the search time. The weights $w_f$ and $w_t$ allow the user to specify exactly how much search time they are willing to trade for a unit of solution cost.

Conceptual trade-off between solution cost and search time, showing the 'nearest' and 'cheapest' hypothesized outcomes used for guidance.

Dual Estimation and Online Correction

For every node $n$ in the search space, BUGSY estimates two potential outcomes:

  1. The cheapest solution reachable from $n$ (likely requiring more search time).
  2. The nearest solution reachable from $n$ (likely having a higher cost).

The algorithm expands the node with the highest estimated utility based on the better of these two hypothesized outcomes. Crucially, BUGSY incorporates online correction. By tracking "one-step errors" — the difference between expected and actual heuristic values during expansion — the algorithm adjusts its estimates on the fly. This allows BUGSY to adapt to the specific characteristics of a problem instance without requiring expensive prior training or pilot experiments.

Experimental Evaluation

The performance of BUGSY was evaluated across three distinct domains:

  • Gridworld Planning: Large-scale grids (2000x1200) with varying obstacle densities and "life" costs.
  • Multiple Sequence Alignment: A bioinformatics task aligning protein sequences using a sum-of-pairs cost function.
  • Temporal Planning: 31 problems from the International Planning Competition (IPC), including domains like Satellite, Rovers, and Logistics, where the objective is to minimize total makespan.

Key Results and Insights

BUGSY demonstrated significant advantages over state-of-the-art anytime algorithms. In sequence alignment tests, BUGSY achieved higher utility than anytime algorithms even when the latter were granted "clairvoyant" termination policies (an ideal scenario where the algorithm knows the perfect moment to stop).

Performance comparison of BUGSY against ARA*, AA*, and A* across various IPC planning domains. Bold values indicate the highest utility achieved.

In temporal planning domains, BUGSY often outperformed ARA and Anytime A by one to two orders of magnitude in terms of raw utility. A key insight from the study is the distinction between cost ($h(n)$) and distance ($d(n)$). To estimate search time accurately, an algorithm must estimate the number of future node expansions, making distance-to-goal a critical metric for utility-guided search.

Conclusion

BUGSY offers a robust, rational approach to search by treating the algorithm as an agent that understands its own effort. By integrating utility directly into guidance, it eliminates the need for complex meta-reasoning and domain-specific parameter tuning. While future work may address hard deadlines and memory constraints in extremely large search spaces, BUGSY represents a significant step forward in making search algorithms responsive to real-world user preferences.

Summary updated

BibTeX
@inproceedings{ruml2007best,
  author = {Wheeler Ruml and Minh Binh Do},
  title = {{Best-First Utility-Guided Search}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2007},
}
Figure