AWA - a window constrained anytime heuristic search algorithm

Aine, Sandip ; Chakrabarti, P. P. ; Kumar, Rajeev (2007) AWA - a window constrained anytime heuristic search algorithm International Joint Conference on Artificial Intelligence . pp. 2250-2255. ISSN 1045-0823

[img]
Preview
PDF - Publisher Version
156kB

Official URL: http://ijcai.org/Past%20Proceedings/IJCAI-2007/PDF...

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.

Item Type:Article
Source:Copyright of this article belongs to Morgan Kaufmann Publishers Inc..
ID Code:5946
Deposited On:19 Oct 2010 10:07
Last Modified:16 May 2016 16:23

Repository Staff Only: item control page