Abstract
This paper challenges a fundamental assumption in artificial intelligence: that looking further ahead always leads to better decisions. In the context of real-time path-finding, the authors demonstrate that deeper search can actually lead to worse performance—a phenomenon known as "lookahead pathology." Through empirical analysis on commercial game maps, the study identifies heuristic learning as the primary driver of this pathology and proposes state abstraction as a method to dynamically select optimal search depths.
Introduction
In path-finding for applications like video games, agents often cannot calculate a complete path to a goal due to real-time constraints. Instead, they utilize Real-Time Search, which involves exploring a limited lookahead depth ($d$), estimating the remaining distance using a heuristic, and executing a move.
Common intuition suggests that a larger $d$ (searching deeper) should yield better moves. However, this paper investigates whether "lookahead pathology"—a phenomenon where deeper search leads to suboptimal decisions—exists in single-agent path-finding on realistic maps and seeks to explain its underlying causes.
Methodology
The authors evaluate the Learning Real-Time Search (LRTS) algorithm, a variant of LRTA* that updates its heuristic estimates of the map as it explores. To isolate the cause of pathology, they conducted two types of experiments:
- On-policy: The agent moves from start to goal, updating its map knowledge (learning) as it goes.
- Off-policy: The agent is teleported to random states and asked for the best move based on static knowledge, without updating its heuristic.
The study used 1,000 path-finding problems set on maps from commercial computer games, including a benchmark "office-and-garden" map consisting of 8,743 states.
The Nature of Lookahead Pathology
The researchers found that pathology is a practical reality, appearing in over 50% of the single-agent path-finding problems tested. A critical insight is that the maps themselves are not the issue; rather, the interaction between search and learning causes the performance drop.
As shown in Table 1, pathology is almost non-existent in off-policy scenarios (4.3%), whereas it is prevalent in on-policy learning (57.7%). This suggests the "Update Density Paradox": smaller lookahead depths ($d=1$) update the heuristic of the current state more frequently relative to the total number of states they visit. Because they update more often, their heuristic estimates become accurate faster than those of agents using deeper lookahead.
Key Results
- Pathology Prevalence: In basic on-policy experiments, 57.7% of problems exhibited some degree of pathology.
- Search Frequency: In standard LRTS, deeper searches happen less frequently (every $d$ moves). When the authors forced the agent to search every single move regardless of $d$, the pathology significantly decreased.
- Path Length Performance:
- The best fixed lookahead depth was $d=1$, resulting in an average path length of 175.4.
- If the agent could choose the optimal depth for each specific problem, the average path length dropped to 107.9.
- Efficiency via Abstraction: Using "clique abstraction" to group states into regions allowed the authors to pre-compute optimal depths for regions. This reduced the average path length to 169.3 while only requiring pre-computation for 0.004% of all state pairs.
Conclusion
Lookahead pathology is a significant factor in real-time path-finding. The study demonstrates that deeper search can be counterproductive when it reduces the density of heuristic updates. While finding the optimal search depth for every state is computationally prohibitive, state abstraction offers a tractable way to mitigate pathology and improve agent efficiency in complex environments. Future work will focus on automated methods for selecting lookahead depth on-the-fly without exhaustive pre-calculation.
Summary updated