Case-Based Subgoaling in Real-Time Heuristic Search for Video Game
  Pathfinding
  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 re-visiting the same
problem states repeatedly. The situation changed recently with a new algorithm,
D LRTA*, which attempted 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 to applying
state-of-the-art real-time search methods in video games. The new algorithm
solves a number of randomly chosen problems off-line, compresses the solutions
into a series of subgoals and stores them in a database. When presented with a
novel problem on-line, it queries the database for the most similar previously
solved case and uses its subgoals to solve the problem. In the domain of
pathfinding on four large video game maps, the new algorithm delivers solutions
eight times better while using 57 times less memory and requiring 14% less
pre-computation time.
