《Real-Time Search in Dynamic Worlds》.pdf

Real-Time Search in Dynamic Worlds David M. Bond, Niels A. Widger, Wheeler Ruml Xiaoxun Sun Department of Computer Science Computer Science Department University of New Hampshire University of Southern California Durham, NH 03824 USA Los Angeles, CA 90089 USA david.bond at xiaoxuns at niels.widger, ruml at Abstract information between planning episodes so that re-planning can be faster. For problems such as pathfinding in video games and Existing real-time search algorithms are designed for robotics, a search algorithm must be real-time (return the known static graphs. However, most real-time search al- next move within a fixed time bound) and dynamic (accom- gorithms only explore the part of the state space near the modate edge costs that can increase and decrease before the goal is reached). Existing real-time search algorithms, such agent. When used in conjunction with the freespace assump- as LSS-LRTA*, can handle edge cost increases but do not tion, they can be made to work in situations where the world handle edge cost decreases. Existing dynamic search algo- is initially unknown and is discovered by the agent during rithms, such as D* Lite, are not real-time. We show how its travel. They will typically tolerate d