---
title: "AWA* - A Window Constrained Anytime Heuristic Search Algorithm"
authors:
  - "Sandip Aine"
  - "P. P. Chakrabarti"
  - "Rajeev Kumar"
doi: ""
url: "https://ijcai.org/proceedings/2007/362"
pdf: "https://ijcai.org/proceedings/2007/0362.pdf"
venue: "Proceedings of the Twentieth International Joint Conference on Artificial Intelligence"
year: 2007
pages: "2250-2254"
track: ""
keywords:
---

# AWA* - A Window Constrained Anytime Heuristic Search Algorithm

Sandip Aine, P. P. Chakrabarti, Rajeev Kumar

*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.