The Trailblazer Search: A New Method for Searching and Capturing Moving Targets

Proceedings of the AAAI Conference on Artificial Intelligence, 12

Volume

Search and Genetic Algorithms

Search

This paper proposes a new search algorithm for targets that move. Ishida and Korf presented an algorithm, called the moving target search, that captures a target while deciding each search step in constant time (Ishida and Korf 1991). However, this algorithm requires many search steps to solve problems, if it uses a heuristic function that initially returns inaccurate values. The trailblazer search stores path information of the region it has searched and exploits this information when making decisions. The algorithm maintains a map of the searched region, and chases the target once it falls on a path found on the map. We empirically show that the algorithm’s map function can significantly reduce the number of search steps, compared with the moving target search. We also discuss the efficiency of the trailblazer search, taking the maintenance cost of the map into consideration.