Moving target D* Lite

Xiaoxun Sun, William Yeoh, Sven KoenigAAMAS 2010 · OpenReview

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 is four to five 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.
BibTeX
@inproceedings{sun2010moving,
  author = {Xiaoxun Sun and William Yeoh and Sven Koenig},
  title = {{Moving target D* Lite}},
  booktitle = {AAMAS},
  year = {2010},
  url = {https://openreview.net/forum?id=65jXLLkkrc},
}

Loading related content...

Figure