Lookahead pathologies for single agent search

Admissible and consistent heuristic functions are usually preferred in single-agent heuristic search as they guarantee optimal solutions with complete search methods such as A * and IDA*. Larger problems, however, frequently make a complete search intractable due to space and/or time limitations. In particular, a path-planning agent in a realtime strategy game may need to take an action before its complete search has the time to finish. In such cases, incomplete search techniques (such as RTA*, SRTA*, RTDP, DTA*) can be used. Such algorithms conduct a limited ply lookahead and then evaluate the states envisioned using a heuristic function. The action selected on the basis of such evaluations can be suboptimal due to the incompleteness of search and inaccuracies in the heuristic. It is usually believed that deeper lookahead increases the chances of taking the optimal action. In this paper, we demonstrate that this is not necessarily the case, even when admissible and consistent heuristic functions are used. 1 Lookahead Pathologies in Real-time Single-agent Search Complete search methods such as A * [Hart et al., 1968] and IDA * [Korf, 1985] produce optimal solutions when based on an admissible and monotonic heuristic function. The primary drawbacks are the exponential running time and the necessity to wait until the search completes before the first action can be taken [Korf, 1990]. This limits the applicability of complete search in practice as the deliberation time per action can be severely limited [Higgins, 2002], the domain model can be expensive [Bulitko and Wilkins, 2002], the goal states can be difficult to recognize [Levner et al., 2002]. Consequently, despite numerous advances in improving heuristic functions [Korf and Taylor, 1996; Culberson and Schaeffer, 1994; Reinefeld, 1993; Korf, 1997], incomplete real-time/on-line search methods remain the practical choice for complex reallife problems. Various incomplete search methods have been propose