Bounded-cost Search Using Estimates of Uncertainty

Maximilian Fickert, Tianyi Gu, Wheeler RumlIJCAI 2021 · DOI

TL;DR

This paper introduces Expected Effort Search (XES), a novel bounded-cost search algorithm that leverages uncertainty estimates in heuristic functions to find solutions within a given cost bound more efficiently. XES consistently outperforms existing methods like Potential Search (PTS) and Bounded-cost Explicit Estimation Search (BEES) on standard planning and search benchmarks, demonstrating the value of incorporating uncertainty in deterministic search.

What Problem Does This Paper Address?

Many real-world problems require finding a solution quickly, but not necessarily the absolute optimal one. Bounded-cost search addresses this by aiming to find a plan that costs no more than a user-specified absolute bound, as fast as possible. Traditional approaches like A* can be too slow when optimal solutions are hard to find. Existing bounded-cost search algorithms like Potential Search (PTS) and Bounded-cost Explicit Estimation Search (BEES) try to guide the search towards promising nodes. However, PTS focuses solely on the probability of finding a solution within the bound, neglecting the search effort required. BEES improves on this by considering distance-to-go estimates but still doesn't fully account for the uncertainty in its estimations. This paper tackles the challenge of efficiently guiding a search algorithm when faced with a cost bound, by better leveraging heuristic information and its inherent uncertainty.

Methods

The core contribution is the Expected Effort Search (XES) algorithm. XES is a best-first search that prioritizes nodes based on an "expected effort" metric, calculated as $T(n)/p(n)$. Here:

  • $T(n)$ is an estimate of the search effort (time) required to find a solution under node $n$.
  • $p(n)$ is the estimated probability that a solution within the cost bound $C$ can be found under node $n$.

This metric is derived from a simplified formal model where search proceeds in subtrees, and the probability of finding a solution and the effort involved are estimated. XES instantiates $T(n)$ using a debiased distance estimate and $p(n)$ using belief distributions (specifically, truncated Gaussian distributions) derived from heuristic estimates, similar to the Nancy algorithm. The paper also proposes improved variants of BEES (BEES95 and BEEPS95) that incorporate these belief distributions.

Datasets

The paper evaluates its algorithms on:

  • IPC'18 bounded-cost track benchmarks: 180 instances from 9 domains.
  • Satisficing tracks of previous IPCs: 2147 instances from 48 domains, using upper bounds from Planning.Domains as cost bounds.
  • Four classic heuristic search benchmarks:
    • Sliding-Tile Puzzle (uniform, heavy, inverse, and square-root costs)
    • Vacuum World (uniform and heavy costs)
    • Pancake Problem (standard and heavy costs)
    • Racetrack Domain (using Dijkstra and Euclidean distance heuristics)

No new benchmarks were introduced; existing ones were used to compare against prior work.

Key Insights and Ideas

  • Uncertainty is Key: The paper strongly advocates for using uncertainty estimates in heuristic functions for deterministic search, a trend traditionally seen in planning under uncertainty. This is a significant shift from relying solely on point estimates.
  • Expected Effort as a Guiding Principle: The $T(n)/p(n)$ metric elegantly balances the probability of success with the cost of exploration, providing a more robust guidance signal than previous approaches.
  • Formal Justification for Heuristics: The paper provides a simplified formal model to theoretically justify the expected effort heuristic, strengthening its credibility.
  • Robustness to Heuristic Quality: XES is shown to be less sensitive to the accuracy of probability estimates compared to BEES variants, making it more robust in practice.

Key Results

  • Superior Performance: XES consistently outperforms existing bounded-cost search algorithms (PTS, BEES, BEEPS) across planning and heuristic search benchmarks.
  • Higher Coverage: On IPC'18 bounded-cost instances, XES achieved the highest coverage (66%), significantly outperforming others.
  • Fewer Expansions and Less Time: On commonly solved instances, XES generally required fewer expansions and less search time compared to its competitors.
  • Improved BEES Variants: BEES95 and BEEPS95 showed modest but consistent improvements over their base algorithms, demonstrating the benefit of incorporating belief distributions.
  • Robustness Across Domains: XES demonstrated strong performance across a wide variety of domains, including those with different heuristic types and problem complexities.

Limitations and Future Work

  • Simplified Formal Model: The formal model used to derive the expected effort heuristic relies on several simplifying assumptions (A1-A3), such as search proceeding exclusively in one subtree at a time and independence of subtrees. While the paper shows XES performs well empirically, the direct applicability of the formal proof to complex real-world scenarios might be limited.
  • Heuristic Instantiation: The paper instantiates $T(n)$ with a debiased distance estimate and $p(n)$ from Nancy-style distributions. Future work could explore other ways to obtain these estimates or integrate them with different types of heuristics.
  • Further Exploration of BEES Variants: While BEES95 and BEEPS95 showed improvements, further research could explore other ways to leverage belief distributions within the BEES framework.
  • Domain-Specific Optimizations: The paper focuses on general-purpose algorithms. Future work might investigate domain-specific adaptations or combinations of XES with other techniques.

Summary updated

BibTeX
@inproceedings{fickert2021bounded,
  author = {Maximilian Fickert and Tianyi Gu and Wheeler Ruml},
  title = {{Bounded-cost Search Using Estimates of Uncertainty}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/231},
}
Figure