Multi-target adaptive A*
Kengo Matsuta, Hayato Kobayashi, Ayumi Shinohara · 2010
Agents often have to solve series of similar path planning problems. Adaptive A * is a recent incremental heuristic search algorithm that solves such problems fasterthanA*, updating a heuristic function (also known as h-values) using information from previous searches. In this paper, we address path planning with multiple targets on Adaptive A* framework. Although we can solve such problems bycalculating the optimal path to each target, it would be inefficient, especially when the number of targets is large. We consider two cases whose objectives are (1) an agent reaches one of the targets, and (2) an agent has to reach all of the targets. We propose several methods to solve such problems keeping consistency of a heuristic function. Our experiments show that the proposed methods properly work on an application, i.e., maze problems.