Speeding up Moving-Target Search

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.

Authors

• Sven Koenig University of California & Örebro University
• Maxim Likhachev Carnegie Mellon University
• Xiaoxun Sun

Keywords

• D* Lite
• Hunter
• Incremental Heuristic Search
• Moving-Target Search
• MT-Adaptive A*
• Planning with the Freespace Assumption
• Target
• Unknown Terrain
• Video Games