AWA* - A Window Constrained Anytime Heuristic Search Algorithm
Abstract
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.
Cite
Text
Aine et al. "AWA* - A Window Constrained Anytime Heuristic Search Algorithm." International Joint Conference on Artificial Intelligence, 2007.Markdown
[Aine et al. "AWA* - A Window Constrained Anytime Heuristic Search Algorithm." International Joint Conference on Artificial Intelligence, 2007.](https://mlanthology.org/ijcai/2007/aine2007ijcai-awa/)BibTeX
@inproceedings{aine2007ijcai-awa,
title = {{AWA* - A Window Constrained Anytime Heuristic Search Algorithm}},
author = {Aine, Sandip and Chakrabarti, P. P. and Kumar, Rajeev},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2007},
pages = {2250-2255},
url = {https://mlanthology.org/ijcai/2007/aine2007ijcai-awa/}
}