Lookahead Pathology in Real-Time Path-Finding

Large real-time search problems such as path-finding in com-puter games and robotics limit the applicability of complete search methods such as A*. As a result, real-time heuris-tic methods are becoming more wide-spread in practice. These algorithms typically conduct a limited-depth looka-head search and evaluate the states at the frontier using a heuristic. Actions selected by such methods can be subop-timal due to the incompleteness of their search and inaccu-racies 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 syn-thetic examples in single-agent search. As real-time search methods gain ground in applications, the importance of un-derstanding and remedying lookahead pathologies increases. This paper, for the first time, conducts a large scale inves-tigation 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 addi-tional 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 substan-tially improves on-line performance and, as an added benefit, spares the user from having to tune a control parameter