D. Chris Rayner, Katherine Davison, Vadim Bulitko, Jieshan Lu
Modern computer games demand real-time simultaneous control of multiple agents. Learning real-time search, which interleaves planning and acting, allows agents to both learn from experience and respond quickly. Such algorithms require no prior knowledge of the environment and can be deployed without pre-processing. We introduce Prioritized-LRTA*, an algorithm based on Prioritized Sweeping. P-LRTA* focuses learning on important areas of the search space, where 'importance' is determined by the magnitude of the updates made to neighboring states. Empirical tests on path-finding in commercial game maps show a substantial learning speed-up over state of the art learning real-time heuristic search algorithms.
Subjects: 15.7 Search
Submitted: May 17, 2006