V. Bulitko, N. Sturtevant, J. Lu and T. Yau (2007) "Graph Abstraction in Real-time Heuristic Search", Volume 30, pages 51-100

PDF | PostScript | doi:10.1613/jair.2293

Real-time heuristic search methods are used by situated agents in applications that require the amount of planning per move to be independent of the problem size. Such agents plan only a few actions at a time in a local search space and avoid getting trapped in local minima by improving their heuristic function over time. We extend a wide class of real-time search algorithms with automatically-built state abstraction and prove completeness and convergence of the resulting family of algorithms. We then analyze the impact of abstraction in an extensive empirical study in real-time pathfinding. Abstraction is found to improve efficiency by providing better trading offs between planning time, learning speed and other negatively correlated performance measures.

Click here to return to Volume 30 contents list