ITSA*: Iterative Tunneling Search with A*

Contents

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.