Seminar on Computational Learning and Adaptation

 State abstraction in Learning Real-time Heuristic Search

Vadim Bulitko
Department of Computing Science
University of Alberta

Abstract:

Learning real-time heuristic search methods, such as LRTA*, are used by situated agents in applications that require the amount of planning per move to be independent of the problem size. Such agents interleave planning, execution, and learning. They plan only a few actions at a time in a local search space and avoid getting trapped in local minima by learning their heuristic function. Efficiency of such learning has been a key research area in real-time heuristic search. Techniques that focus learning on relevant parts of the search space and use aggressive learning rules have been suggested and proved efficient. Orthogonal to these are techniques based on automated state abstraction.

In this talk we describe how learning performance of LRTA* can be substantially improved by running it in a smaller abstract search space. The resulting algorithm retains real-time performance and completeness/convergence properties. Empirically, the abstraction is found to improve efficiency by trading off planning time, learning speed and other antagonistic performance measures. The talk will be illustrated with applications to path-planning in computer video games.

Return to the seminar schedule