Updating Shortest Paths.
Stefan Edelkamp · 1998
. Moving target search is a state space approach for finding non-stationary goals. The plot is given by a realtime situation in which the target has to be captured by a so-called problem solver. The model chosen in the trailblazer search allows the problem solver to maintain a map of the explored graph and to move faster than the target. Within this map the shortest paths to a current position are calculated after every move that a competitor commits. The trailblazer search does not use information about former maps. Thus, the main problem tackled in this paper is the incremental calculation of the shortest path tree. We proof the correctness of our approach, reason about its efficiency and show that it is empirically good in the average case. 1 Introduction Chasing a moving target is a natural concept, e.g. for an animal to survive. The strategies of the hunter and its prey in the chase reflect the abilities of the animals, such as speed, coordination and senses. In most cases the hu...