kNN LRTA*: Simple Subgoaling for Real-Time Search

Abstract

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