Real-Time Search in Dynamic Worlds

Our approach is conceptually simple: we perform a the search algorithm. In video game pathfinding and robot standard dynamic search but interrupt it periodically to move motion planning, the search is often required to be real-time, the agent according to a real-time search. In this paper, we that is, return the next move for the agent within a strict time use D* Lite (Koenig and Likhachev 2002) or Anytime D* bound, so that the agent can continue acting in the world. To (Likhachev et al. 2005) as the dynamic search algorithm and accommodate this constraint, real-time search algorithms interleave LRTA* (Korf 1990) or LSS-LRTA* (Koenig and Sun 2009) planning and moving. Because the agent must make as the real-time search algorithm. D* Lite and Anytime D* a choice of which move to execute next before finding a perform a global search backwards from the goal, trying to complete path to a goal, real-time search algorithms achieve reach the agent's current location. LRTA* and LSS-LRTA* fast response times at the cost of sub-optimality of the resulting perform a local search forward from the agent's current location, trajectories. There has been much research on real-time trying to reach the goal. Therefore, RTD* is a form of search algorithms, starting with LRTA* (Korf 1990).