Incremental ARA*: An Incremental Anytime Search Algorithm for Moving-Target Search

Authors

  • Xiaoxun Sun University of Southern California
  • William Yeoh Singapore Management University
  • Tansel Uras University of Southern California
  • Sven Koenig University of Southern California

DOI:

https://doi.org/10.1609/icaps.v22i1.13525

Keywords:

Moving-target search, Incremental search, Anytime search

Abstract

Moving-target search, where a hunter has to catch a moving target, is an important problem for video game developers. In our case, the hunter repeatedly moves towards the target and thus has to solve similar search problems repeatedly. We develop Incremental ARA* (I-ARA*) for this purpose, the first incremental anytime search algorithm for moving-target search in known terrain. We provide an error bound on the lengths of the paths found by I-ARA* and show experimentally in known four-neighbor gridworlds that I-ARA* can be used with smaller time limits between moves of the hunter than competing state-of-the-art moving-target search algorithms, namely repeated A*, G-FRA*, FRA*, and sometimes repeated ARA*. The hunter tends to make more moves with I-ARA* than repeated A*, G-FRA* or FRA*, which find shortest paths for the hunter, but fewer moves with I-ARA* than repeated ARA*, which finds suboptimal paths for the hunter like I-ARA*. Also, the error bounds on the lengths of the paths of the hunter tend to be smaller with I-ARA* than repeated ARA*.

Downloads

Published

2012-05-14

How to Cite

Sun, X., Yeoh, W., Uras, T., & Koenig, S. (2012). Incremental ARA*: An Incremental Anytime Search Algorithm for Moving-Target Search. Proceedings of the International Conference on Automated Planning and Scheduling, 22(1), 243-251. https://doi.org/10.1609/icaps.v22i1.13525