kNN LRTA*: simple subgoaling for real-time search

摘要: Real-time heuristic search algorithms satisfy a constant bound on the amount of planning per action, independent problem size. As result, they scale up well as problems become larger. This property would make them suited for video games where Artificial Intelligence controlled agents must react quickly to user commands and other agents' actions. On downside, real-time employ learning methods that frequently lead poor solution quality cause agent appear irrational by revisiting same states repeatedly. The situation changed recently with new algorithm, D LRTA*, which attempts eliminate automatically selecting subgoals. LRTA* is poised except it has complex memory-demanding pre-computation phase during builds database In this paper, we propose simpler more memory-efficient way pre-computing subgoals thereby eliminating main obstacle applying state-of-the-art in games. domain pathfinding eight game maps, algorithm used approximately nine times less memory than while finding solutions 9% worse.