AWA* - A Window Constrained Anytime Heuristic Search Algorithm
Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 2250-2254.
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.
@inproceedings{ijcai2007p362,
title = {AWA* - A Window Constrained Anytime Heuristic Search Algorithm},
author = {Aine, Sandip and Chakrabarti, P. P. and Kumar, Rajeev},
booktitle = {Proceedings of the Twentieth International Joint Conference on
Artificial Intelligence, {IJCAI-07}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ramon López de Mántaras},
pages = {2250--2254},
year = {2007},
url = {https://ijcai.org/proceedings/2007/362},
}
TY - CPAPER TI - AWA* - A Window Constrained Anytime Heuristic Search Algorithm AU - Aine, Sandip AU - Chakrabarti, P. P. AU - Kumar, Rajeev T2 - Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07 PB - International Joint Conferences on Artificial Intelligence PY - 2007 SP - 2250 EP - 2254 UR - https://ijcai.org/proceedings/2007/362 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
