Moving Target D* Lite

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 oftenfind cost-minimal paths for series of similar search problemsfaster than by solving each search problem from scratch. However, existing incremental search algorithms have limitations. For example, D* Lite is slow on moving targetsearch problems, where both the start and goal states canchange over time. In this paper, we therefore introduceMoving Target D* Lite, an extension of D* Lite that usesthe principle behind Generalized Fringe-Retrieving A* to repeatedly calculate a cost-minimal path from the hunter tothe target in environments whose blockages can change overtime. We demonstrate experimentally that Moving TargetD* Lite is four to five times faster than Generalized AdaptiveA*, which so far was believed to be the fastest incrementalsearch algorithm for solving moving target search problemsin dynamic environments.

Authors

• Xiaoxun Sun
• William Yeoh Washington University in St. Louis
• Sven Koenig University of California, Irvine

Keywords

No keywords are indexed for this paper.