Dynamic control in path-planning with real-time heuristic search
Vadim Bulitko, Yngvi Björnsson, Mitja Luštrek, Jonathan Schaeffer, Sverrir Sigmundarson · 2007
Real-time heuristic search methods, such as LRTA*, are used by situated agents in applications that require the amount of planning per action to be constant-bounded regardless of the problem size. LRTA * interleaves planning and execution, with a fixed search depth being used to achieve progress to-wards a fixed goal. Here we generalize the algorithm to allow for a dynamically changing search depth and a dynamically changing (sub-)goal. Evaluation in path-planning on video-game maps shows that the new algorithm significantly outper-forms fixed-depth, fixed-goal LRTA*. The new algorithm can achieve the same quality solutions as LRTA*, but with nine times less computation, or use the same amount of computa-tion, but produce four times better quality solutions. These extensions make real-time heuristic search a practical choice for path-planning in computer video-games.