Time Complexity of Iterative-Deepening A*: The Informativeness Pathology (Abstract)


  • Levi Lelis University of Alberta
  • Sandra Zilles University of Regina
  • Robert Holte University of Alberta




Korf, Reid, and Edelkamp launched a line of research aimed at predicting how many nodes IDA* will expand with a given depth bound. This paper advances this line of research in three ways. First, we identify a source of prediction error that has hitherto been overlooked. We call it the "discretization effect." Second, we disprove the intuitively appealing idea that a "more informed" prediction system cannot make worse predictions than a ``less informed'' one. More informed systems are more susceptible to the discretization effect, and in our experiments the more informed system makes poorer predictions. Our third contribution is a method, called "Epsilon-truncation," which makes a prediction system less informed, in a carefully chosen way, so as to improve its predictions by reducing the discretization effect. In our experiments Epsilon-truncation improved predictions substantially.




How to Cite

Lelis, L., Zilles, S., & Holte, R. (2011). Time Complexity of Iterative-Deepening A*: The Informativeness Pathology (Abstract). Proceedings of the AAAI Conference on Artificial Intelligence, 25(1), 1800-1801. https://doi.org/10.1609/aaai.v25i1.8053