Prioritized-LRTA*: Speeding Up Learning Via Prioritized Updates

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

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.