# Error Analysis and Correction for Weighted A*'s Suboptimality (Extended Version)

arXiv: https://arxiv.org/abs/1905.11346 · HTML: https://mlsanity.com/paper/1905.11346/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 May 2019.

## Built on by (most cited first, 1 of 1)

- [Effective Integration of Weighted Cost-to-go and Conflict Heuristic within Suboptimal CBS](https://mlsanity.com/paper/2205.11624/) (2022)

## Abstract (arXiv)

Weighted A* (wA*) is a widely used algorithm for rapidly, but suboptimally, solving planning and search problems. The cost of the solution it produces is guaranteed to be at most W times the optimal solution cost, where W is the weight wA* uses in prioritizing open nodes. W is therefore a suboptimality bound for the solution produced by wA*. There is broad consensus that this bound is not very accurate, that the actual suboptimality of wA*'s solution is often much less than W times optimal. However, there is very little published evidence supporting that view, and no existing explanation of why W is a poor bound. This paper fills in these gaps in the literature. We begin with a large-scale experiment demonstrating that, across a wide variety of domains and heuristics for those domains, W is indeed very often far from the true suboptimality of wA*'s solution. We then analytically identify the potential sources of error. Finally, we present a practical method for correcting for two of these sources of error and experimentally show that the correction frequently eliminates much of the error.