Speeding up Moving-Target Search - Robotics Institute Carnegie Mellon University

Speeding up Moving-Target Search

Sven Koenig, Maxim Likhachev, and Xiaoxun Sun
Conference Paper, Proceedings of 6th International Joint Conference on Autonomous Agents and MultiAgent Systems (AAMAS '07), May, 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.

BibTeX

@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},
}