niels.widger, ruml at cs.unh.edu

xiaoxuns at usc.edu 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 (accom-modate 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 algo-rithms, such as D * Lite, are not real-time. We show how these two families of algorithms can be combined using bidi-rectional search, producing Real-Time D * (RTD*), the first real-time search algorithm designed for dynamic worlds. Our empirical evaluation shows that, for dynamic grid pathfind-ing, RTD * results in significantly shorter trajectories than ei-ther LSS-LRTA * or naive real-time adaptations of D * Lite because of its ability to opportunistically exploit shortcuts