Lookahead Pathologies for Single Agent Search
- Vadim Bulitko
- Lihong Li
- Russ Greiner, Dept of Computing Science; PI of AICML
- Ilya Levner
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 limita-tions. In particular, a path-planning agent in a real-time strategy game may need to take an action be-fore 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 incom-pleteness of search and inaccuracies in the heuris-tic. It is usually believed that deeper lookahead in-creases the chances of taking the optimal action. In this paper, we demonstrate that this is not necessar-ily the case, even when admissible and consistent heuristic functions are used.
Citation
V. Bulitko, L. Li, R. Greiner, I. Levner. "Lookahead Pathologies for Single Agent Search". International Joint Conference on Artificial Intelligence (IJCAI), Acapulco, Mexico, August 2003.| Keywords: | pathologies, search |
| Category: | In Conference |
BibTeX
@incollection{Bulitko+al:IJCAI03,
author = {Vadim Bulitko and Lihong Li and Russ Greiner and Ilya Levner},
title = {Lookahead Pathologies for Single Agent Search},
booktitle = {International Joint Conference on Artificial Intelligence
(IJCAI)},
year = 2003,
}Last Updated: June 05, 2007Submitted by Staurt H. Johnson
