Abstract
This paper introduces PEA+IDA, a hybrid search algorithm designed to optimize the trade-off between time and memory in state-space search. By integrating Partial Expansion A (PEA) with Iterative Deepening A (IDA), the algorithm selectively manages memory during its initial phase, allowing it to reach deeper search thresholds before transitioning to the memory-restricted IDA phase. Experimental results on the STRIPS optimal benchmark demonstrate that PEA+IDA significantly reduces node expansions and increases task coverage compared to the previous state-of-the-art hybrid, A+IDA*.
Introduction
In pathfinding and automated planning, researchers face a fundamental trade-off between time and memory. A is the gold standard for speed because it stores every visited node, but it frequently fails when it exceeds available RAM. Conversely, IDA** solves the memory problem using a depth-first approach with minimal memory requirements, but it suffers from high time costs due to constant node re-expansions.
Recent hybrid approaches, such as A+IDA, attempt to bridge this gap by running A until memory is nearly full and then switching to IDA using the stored nodes as starting points. However, standard A often fills memory with "junk" nodes—children with high heuristic values that are not immediately useful—forcing the algorithm into the slower IDA phase prematurely. This paper proposes PEA+IDA to address this inefficiency.
Methods
The core innovation of PEA+IDA lies in its two-phase approach, utilizing a more selective memory management strategy during the initial search.
- Phase 1 (Restricted PEA): Instead of standard A*, the algorithm uses Partial Expansion A. When expanding a node, it only stores children whose estimated cost ($f$-value) is equal to the parent's. Other children are discarded, and the parent is re-inserted into the "Open" list with an updated cost. This keeps the memory footprint significantly smaller.
- Transition: The algorithm runs PEA* until a pre-defined memory limit is reached.
- Phase 2 (IDA*): Once memory is full, the algorithm switches to IDA, picking nodes from the PEA Open list as starting points for depth-first iterations.
Because PEA is more selective about which nodes it stores, it can reach a higher F-limit (a deeper search threshold) within the same memory footprint compared to standard A. This ensures that when Phase 2 begins, the search is already much closer to the goal.
Experimental Setup
The researchers evaluated PEA+IDA using the STRIPS optimal benchmark from the International Planning Competition (IPC), encompassing 1,877 tasks across various classical planning domains such as Blocks, Logistics, and Sokoban. They utilized the state-of-the-art $h^{LMCut}$ heuristic and tested the algorithms at three memory stress levels: 10%, 50%, and 90% of the peak memory required by a full A* search.
Key Results
PEA+IDA consistently outperformed the previous state-of-the-art hybrid, A+IDA, across multiple metrics:
- Higher Coverage: At a 90% memory limit, PEA+IDA solved 318 tasks, compared to 275 for A+IDA.
- Reduced Expansions: The algorithm often reduced total node expansions by orders of magnitude. In the "Logistics" domain at 50% memory, PEA+IDA required only 373 expansions, whereas A+IDA expanded approximately 22 million nodes.
- Efficiency Gains: The authors observed speed-ups ranging from 2x to 8x over A+IDA across different memory limits.
Discussion and Future Work
The success of PEA+IDA highlights that the "quality" of stored nodes matters more than the quantity. By maintaining a more homogeneous Open list, PEA prevents IDA from getting stuck in unproductive branches early in the second phase.
Future work includes moving beyond the "black-box" constraint by using Enhanced PEA (EPEA), which leverages domain knowledge to avoid generating discarded children entirely. Additionally, the authors suggest integrating Transposition Tables into the IDA* phase to improve duplicate detection and further optimize search performance.
Summary updated