Abstract

Abstract: Incremental search algorithms, such as Generalized Fringe-Retrieving A* and D* Lite, reuse search trees from previous searches to speed up the current search and thus often find cost-minimal paths for series of similar search problems faster than by solving each search problem from scratch. However, existing incremental search algorithms have limitations. For example, D* Lite is slow on moving target search problems, where both the start and goal states can change over time. In this paper, we therefore introduce Moving Target D* Lite, an extension of D* Lite that uses the principle behind Generalized Fringe-Retrieving A* to repeatedly calculate a cost-minimal path from the hunter to the target in environments whose blockages can change over time. We demonstrate experimentally that Moving Target D* Lite can be three to seven times faster than Generalized Adaptive A*, which so far was believed to be the fastest incremental search algorithm for solving moving target search problems in dynamic environments. Errata: This version of the paper corrects one omission and one mistake. The h-values do not only need to be consistent but also satisfy the additional triangle inequality for D* Lite given in the earlier D* Lite publication, namely that h(s,s'') ≤ h(s,s') + h(s',s'') for all states s, s' and s'', and Line 60 in Figure 2 needs to be 'k_m := k_m + h(s_oldgoal, s_goal).' Also, we updated the experimental results after we noticed a problem in the implementation of our experiments: We performed the experiments in gridworlds of size 1000 x 1000. After each move of the agent from its current cell to a neighbor, we intended to block a certain number of randomly chosen unblocked cells and unblock the same number of randomly chosen blocked cells. We had ported code to a different operating system and, in the process, changed the random number generator. The new random number generator used to determine these cells generated random numbers in the range from 0 to 32,767 only, which is too small to choose among all cells. Fortunately, the correction of this programming mistake did not change the experimental results dramatically, and the qualitative relationship of the runtimes of Moving Target D* Lite and Generalized Adaptive A* remained unchanged. Two papers were affected by this programming mistake.

Download the paper in pdf.

Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.

This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.