ITSA*: Iterative Tunneling Search with A*

David Furcy

ITSA*: Iterative Tunneling Search with A* This paper describes a new approach to anytime heuristic search based on local search in the space of solution paths. This work makes two contributions. First, we introduce a new local optimization algorithm called Iterative Tunneling Search with A* (ITSA*) that explores the neighborhood of a given solution path in order to find shortcuts and thus a shorter overall path. Second, we introduce a new anytime heuristic search algorithm called ABULB that performs a full-fledged local (or neighborhood) search with restarts. ABULB uses a variant of beam search called BULB to generate an initial path and ITSA* to locally optimize this path. When a minimum is reached, ABULB restarts BULB to obtain the next path to optimize, etc. The successive paths output by BULB and ABULB have smaller and smaller costs. We present empirical results with this new anytime algorithm in two standard benchmark domains.

Subjects: 15.7 Search

Submitted: May 30, 2006

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.