A* with Lookahead Re-Evaluated

Authors

  • Zhaoxing Bu University of Alberta
  • Roni Stern Ben Gurion University
  • Ariel Felner Ben Gurion University
  • Robert Holte University of Alberta

Keywords:

Heuristic Search, Proofs of Correctness, A* with Immediate Expansion, A* with Lookahead, Move Pruning

Abstract

A* with lookahead (AL*) is a variant of A* that performs a cost-bounded DFS lookahead from a node when it is generated. We show that the original version of AL* (AL*0) can, in some circumstances, fail to return an optimal solution because of the move pruning it does. We present two new versions, AL*1 and ELH, that we prove to always be correct and give conditions in which AL*0 is guaranteed to be correct. In our experiments with unit costs, AL*0 was usually the fastest AL* version, but its advantage was usually small. In our experiments with non-unit costs, AL*0 substantially outperforms both A* and IDA*. We also evaluate the idea of immediately expanding a generated node if it has the same f-value as its parent. We find that doing so causes AL* to require more memory and sometimes slows AL* down.

Downloads

Published

2021-09-01