Abstract
S. Koenig, M. Likhachev and X. Sun. Speeding up Moving-Target Search. In International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2007.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. Errata: This version of the paper correct one omission and one mistake. For Lazy MT-Adaptive A*, the user-supplied initial h-values do not only need to be consistent but also satisfy the additional triangle inequality H(s,s'') ≤ H(s,s') + H(s',s'') for all states s, s' and s'', that is also required by D* Lite. Also, Lines 46-47 in the pseudocode of Lazy MT-Adaptive A* were indented too much.
The proofs that Eager and Lazy MT-Adaptive A* use the same h-values can be found in a technical report.
Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.
This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.