A* with Lookahead Re-Evaluated Conference Paper uri icon

abstract

  • 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.

publication date

  • January 1, 2014