TY - GEN
T1 - Incremental ARA*
T2 - 22nd International Conference on Automated Planning and Scheduling, ICAPS 2012
AU - Sun, Xiaoxun
AU - Uras, Tansel
AU - Koenig, Sven
AU - Yeoh, William
PY - 2012
Y1 - 2012
N2 - 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*.
AB - 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*.
UR - https://www.scopus.com/pages/publications/84866458814
M3 - Conference contribution
AN - SCOPUS:84866458814
SN - 9781577355625
T3 - ICAPS 2012 - Proceedings of the 22nd International Conference on Automated Planning and Scheduling
SP - 243
EP - 251
BT - ICAPS 2012 - Proceedings of the 22nd International Conference on Automated Planning and Scheduling
Y2 - 25 June 2012 through 29 June 2012
ER -