Lookahead Pathologies for Single Agent Search

Abstract

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.