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

摘要

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 videogame 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.