AAAI Publications, Twenty-First International Joint Conference on Artificial Intelligence

Font Size: 
Efficient Incremental Search for Moving Target Search
Xiaoxun Sun, William Yeoh, Sven Koenig

Last modified: 2009-06-25


Incremental search algorithms reuse information from previous searches to speed up the current search and are thus often able to find shortest paths for series of similar search problems faster than by solving each search problem independently from scratch. However, they do poorly on moving target search problems, where both the start and goal cells change over time. In this paper, we thus develop Fringe-Retrieving A* (FRA*), an incremental version of A* that repeatedly finds shortest paths for moving target search in known gridworlds. We demonstrate experimentally that it runs up to one order of magnitude faster than a variety of state-of-the-art incremental search algorithms applied to moving target search in known gridworlds.


Search; Heuristic Search; Moving Target Search; Incremental Search

Full Text: PDF