Real-time heuristic search with a priority queue
David C. Rayner, Katherine Davison, Vadim Bulitko, Kenneth O. Anderson, Jieshan Lu · 2007
Learning real-time search, which interleaves plan-ning and acting, allows agents to learn from mul-tiple trials and respond quickly. Such algorithms require no prior knowledge of the environment and can be deployed without pre-processing. We introduce Prioritized-LRTA * (P-LRTA*), a learn-ing real-time search algorithm based on Prioritized Sweeping. P-LRTA * focuses learning on important areas of the search space, where the importance of a state is determined by the magnitude of the up-dates made to neighboring states. Empirical tests on path-planning in commercial game maps show a substantial learning speed-up over state-of-the-art real-time search algorithms. 1