Error Analysis and Correction for Weighted A*'s Suboptimality

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*

Authors

• Robert C. Holte
• Rubén Majadas
• Alberto Pozanco
• Daniel Borrajo

Keywords

No keywords are indexed for this paper.