We present a new algorithm called A*+BFHS for solving problems with unit-cost operators where A* and IDA* fail due to memory limitations and/or the existence of many distinct paths between the same pair of nodes. A*+BFHS is based on A* and breadth-first heuristic search (BFHS). A*+BFHS combines advantages from both algorithms, namely A*'s node ordering, BFHS's memory savings, and both algorithms' duplicate detection. On easy problems, A*+BFHS behaves the same as A*. On hard problems, it is slower than A* but saves a large amount of memory. Compared to BFIDA*, A*+BFHS reduces the search time and/or memory requirement by several times on a variety of planning domains.

Breadth-first heuristic search (BFHS) is a classic algorithm for optimally solving heuristic search and planning problems. BFHS is slower than A* but requires less memory. However, BFHS only works on unit-cost domains. We propose a new algorithm that extends BFHS to domains with different edge costs, which we call uniform-cost heuristic search (UCHS). Experimental results show that the iterative-deepening version of UCHS, IDUCHS, is slower than A* but requires less memory on a variety of planning domains.

We present a simple combination of A* and IDA*, which we call A*+IDA*. It runs A* until memory is almost exhausted, then runs IDA* below each frontier node without duplicate checking. It is widely believed that this algorithm is called MREC, but MREC is just IDA* with a transposition table. A*+IDA* is the first algorithm to run significantly faster than IDA* on the 24-Puzzle, by a factor of almost 5. A complex algorithm called dual search was reported to significantly outperform IDA* on the 24-Puzzle, but the original version does not. We made improvements to dual search and our version combined with A*+IDA* outperforms IDA* by a factor of 6.7 on the 24-Puzzle. Our disk-based A*+IDA* shows further improvement on several hard 24-Puzzle instances. We also found optimal solutions to a subset of random 27 and 29-Puzzle problems. A*+IDA* does not outperform IDA* on Rubik’s Cube, for reasons we explain.

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.