AWA*-a window constrained anytime heuristic search algorithm
Sandip Aine, P.P. Chakrabarti, Rajeev Kumar · 2007
This work presents an iterative anytime heuristic search algorithm called Anytime Window A* (AWA*) where node expansion is localized within a sliding window comprising of levels of the search tree/graph. The search starts in depth-first mode and gradually proceeds towards A * by incrementing the window size. An analysis on a uniform tree model provides some very useful properties of this algorithm. A modification of AWA * is presented to guarantee bounded optimal solutions at each iteration. Experimental results on the 0/1 Knapsack problem and TSP demonstrate the efficacy of the proposed techniques over some existing anytime search methods. 1