Speeding up moving-target search

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.

REFERENCES

• 1: M. Goldenberg, A. Kovarksy, X. Wu, and J. Schaeffer. Multiple agents moving target search. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 1538--1538, 2003.
• 2: P. Hart, N. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 2:100--107, 1968.
• 3: R. C. Holte , T. Mkadmi , R. M. Zimmer , A. J. MacDonald, Speeding up problem solving by abstraction: a graph oriented approach, Artificial Intelligence, v.85 n.1-2, p.321-361, Aug. 1996 [doi>10.1016/0004-3702(95)00111-5]
• 4: T. Ishida and R. Korf. Moving target search. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 204--210, 1991.
• 5: Sven Koenig , Maxim Likhachev, D*lite, Eighteenth national conference on Artificial intelligence, p.476-483, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 6: S. Koenig and M. Likhachev. Incremental A*. In T. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems 14, pages 1539--1546, Cambridge, MA, 2002. MIT Press.
• 7: Sven Koenig , Maxim Likhachev, Adaptive A, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082748]
• 8: S. Koenig and M. Likhachev. A new principle for incremental heuristic search: Theoretical results. In Proceedings of the International Conference on Automated Planning and Scheduling, pages 410--413, 2006.
• 9: Sven Koenig , Maxim Likhachev, Real-time adaptive A*, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160682]
• 10: Sven Koenig , Maxim Likhachev , David Furcy, Lifelong planning A*, Artificial Intelligence, v.155 n.1-2, p.93-146, May 2004 [doi>10.1016/j.artint.2003.12.001]
• 11: S. Koenig and R. Simmons. Real-time search in non-deterministic domains. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 1660--1667, 1995.
• 12: M. Likhachev and S. Koenig. Speeding up the Parti-Game algorithm. In S. Becker, S. Thrun, and K. Obermayer, editors, Advances in Neural Information Processing Systems 15, pages 1563--1570, Cambridge, MA, 2002. MIT Press.
• 13: Judea Pearl, Heuristics: intelligent search strategies for computer problem solving, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• 14: A. Stentz. The focussed D* algorithm for real-time replanning. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 1652--1659, 1995.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.0 General

General Terms:
Algorithms, Experimentation, Performance, Theory

Keywords:
D* lite, MT-adaptive A*, hunter, incremental heuristic search, moving-target search, planning with the freespace assumption, target, unknown terrain, video games