The trailblazer search with a hierarchical abstract map
Takahiro Sasaki, Fumihiko Chimura, Mario Tokoro · 1995
Map Takahiro Sasaki 3 and Fumihiko Chimura y and Mario Tokoro z Department of Computer Science, Faculty of Science and Technology, Keio University 3-14-1 Hiyoshi, Kohoku-ku, Yokohama 223, Japan 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...