Real-Time Search in Dynamic Worlds

Authors

  • David Bond University of New Hampshire
  • Niels Widger University of New Hampshire
  • Wheeler Ruml University of New Hampshire
  • Xiaoxun Sun University of Southern California

DOI:

https://doi.org/10.1609/socs.v1i1.18174

Keywords:

heuristic search, real-time search, dynamic worlds

Abstract

For problems such as pathfinding in video games and robotics, a search algorithm must be real-time (return the next move within a fixed time bound) and dynamic (accommodate edge costs that can increase and decrease before the goal is reached). Existing real-time search algorithms, such as LSS-LRTA*, can handle edge cost increases but do not handle edge cost decreases. Existing dynamic search algorithms, such as D* Lite, are not real-time. We show how these two families of algorithms can be combined using bidirectional search, producing Real-Time D* (RTD*), the first real-time search algorithm designed for dynamic worlds. Our empirical evaluation shows that, for dynamic grid pathfinding, RTD* results in significantly shorter trajectories than either LSS-LRTA* or naive real-time adaptations of D* Lite because of its ability to opportunistically exploit shortcuts.

Downloads

Published

2010-08-25