Speeding up Moving-Target Search

May 2007

Speeding up Moving-Target Search

Authors:

Sven Koenig, Maxim Likhachev, and Xiaoxun Sun

Abstract:

In this paper, we study moving-target search, where an agent (= hunter) has to catch a moving target (= prey). The agent does not necessarily know the terrain initially but can observe it within a certain sensor range around itself. It uses the strategy to always move on a shortest presumed unblocked path toward the target, which is a reasonable strategy for computer-controlled characters in video games. We study how the agent can find such paths faster by exploiting the fact that it performs A* searches repeatedly. To this end, we extend Adaptive A*, an incremental heuristic search method, to moving-target search and demonstrate experimentally that the resulting MT-Adaptive A* is faster than isolated A* searches and, in many situations, also D* Lite, a state-of-the-art incremental heuristic search method. In particular, it is faster than D* Lite by about one order of magnitude for moving-target search in known and initially unknown mazes if both search methods use the same informed heuristics.
@conference{Koenig-2007-109731,
author = {Sven Koenig And Maxim Likhachev And Xiaoxun Sun},
title = {Speeding up Moving-Target Search},
booktitle = {Proceedings of 6th International Joint Conference on Autonomous Agents and MultiAgent Systems (AAMAS '07)},
year = {2007},
month = {May},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.