The Trailblazer Search with a Hierarchical Abstract Map

Abstract

We deal with the moving target search problem where the location of the goal may change during the search process. The Trailblazer. Search ( TBS)[Chimura and Tokoro, 1994] achieves a systematic and effective search by maintaining a map. The map stores path information about the region where the algorithm has already searched through. However, because of the growth of the map, there is a problem that the time to make decisions of search steps increases rapidly. We propose an algorithm, the Trailblazer Search with an Abstract map(TBSA), that reduces the cost of map maintenance, and hence improves the reactiveness of the problem solver. We partition the information about the problem space into local maps, and build an abstract map that controls maintenance of the local maps. In this way, the problem solver can systematically manage information about the problem space, and it can utilize the map with less cost. We evaluate the efficiency of our method, and show how significant cost reduction in map maintenance can be achieved by using a two-layered map.