Lookahead Pathology in Real-Time Path-Finding

Contents

Large real-time search problems such as path-finding in computer games and robotics limit the applicability of complete search methods such as A*. As a result, real-time heuristic methods are becoming more wide-spread in practice. These algorithms typically conduct a limited-depth lookahead search and evaluate the states at the frontier using a heuristic. Actions selected by such methods can be suboptimal due to the incompleteness of their search and inaccuracies in the heuristic. Lookahead pathologies occur when a deeper search decreases the chances of selecting a better action. Over the last two decades research on lookahead pathologies has focused on minimax search and small synthetic examples in single-agent search. As real-time search methods gain ground in applications, the importance of understanding and remedying lookahead pathologies increases. This paper, for the first time, conducts a large scale investigation of lookahead pathologies in the domain of real-time path-finding. We use maps from commercial computer games to show that deeper search often not only consumes additional in-game CPU cycles but also decreases path quality. As a second contribution, we suggest three explanations for such pathologies and support them empirically. Finally, we propose a remedy to lookahead pathologies via a method for dynamic lookahead depth selection. This method substantially improves on-line performance and, as an added benefit, spares the user from having to tune a control parameter.