Dynamic Control in Path-Planning with Real-Time Heuristic Search

All Papers

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 towards 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 outperforms 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 computation, but produce four times better quality solutions. These extensions make real-time heuristic search a practical choice for path-planning in computer video-games.