Weighted A* search - unifying view and application
The A* algorithm is a well-known heuristic best-first search method. Several performance-accelerated extensions of the exact A* approach are known. Interesting examples are approximate algorithms where the heuristic function used is inflated by a weight (often referred to as weighted A*). These methods guarantee a bounded suboptimality. As a technical contribution, this paper presents the previous results related to weighted A* from authors like Pohl, Pearl, Kim, Likhachev and others in a more condensed and unifying form. With this unified view, a novel general bound on suboptimality of the result is derived. In the case of avoiding any reopening of expanded states, for epsilon > 0. this bound is (1 + epsilon) (left perpendicularN/2right perpendicular) where N is an upper bound on an optimal solution length.
Keywords: Planning ; Search ; Heuristic search ; A* ; Weighted A* ; Bdd ; Strips ; Binary Decision Diagrams ; Exact Bdd Minimization ; Heuristic-Search ; Best-1St Search ; Algorithm ; Obdds ; Graphs ; DLR
Record created on 2010-11-24, modified on 2016-08-08