Lookahead Pathology in Real-Time Path-Finding

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 21

AAAI Member Abstracts

Path-finding tasks commonly require real-time response, which on large problems precludes the use of complete search methods such as A*. Incomplete single-agent search methods work similarly to minimax-based algorithms used in two-player games. They conduct a limited-depth lookahead search, i.e., expand a part of the space centered on the agent, and heuristically evaluate the distances from the frontier of the expanded space to the goal. Actions selected based on heuristic lookahead search are not necessarily optimal, but both in minimax search and in single-agent search it is generally believed that deeper lookahead increases the quality of decisions. Theoretical analyses of minimax have shown that the opposite is sometimes the case. This phenomenon has been termed the minimax pathology. Recently pathological behavior was observed in single-agent search as well. In this poster we investigate lookahead pathology in real-time path-finding on maps from commercial computer games. Pathology was experimentally observed in more than half of the 1,000 problems considered. This indicates that in single-agent search, pathological behavior is a practical issue - unlike in minimax search, where it seems to be mostly an artifact of the theoretical analyses.