Zooming Cautiously: Linear-Memory Heuristic Search With Node Expansion Guarantees
This work addresses memory efficiency in search algorithms for AI and optimization, offering improved worst-case guarantees over existing methods like IDA*, though it is incremental in nature.
The paper tackled the problem of linear-memory heuristic search by introducing two parameter-free algorithms that guarantee only a logarithmic factor more node expansions than A* in tree search spaces, with empirical results showing practicality and robustness.
We introduce and analyze two parameter-free linear-memory tree search algorithms. Under mild assumptions we prove our algorithms are guaranteed to perform only a logarithmic factor more node expansions than A* when the search space is a tree. Previously, the best guarantee for a linear-memory algorithm under similar assumptions was achieved by IDA*, which in the worst case expands quadratically more nodes than in its last iteration. Empirical results support the theory and demonstrate the practicality and robustness of our algorithms. Furthermore, they are fast and easy to implement.