PEA*+IDA*: An Improved Hybrid Memory-Restricted Algorithm

Frederico Messa, André Grahl Pereira

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.

  1. 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.
  2. Transition: The algorithm runs PEA* until a pre-defined memory limit is reached.
  3. 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.
Illustration of the Open list management in PEA*+IDA* vs A*+IDA*.

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.
Comparison of node expansions between A*+IDA* (x-axis) and PEA*+IDA* (y-axis) across different memory limits and phases.

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

Abstract

It is well-known that the search algorithms A* and Iterative Deepening A* (IDA*) can fail to solve state-space tasks optimally due to time and memory limits. The former typically fails in memory-restricted scenarios and the latter in time-restricted scenarios. Therefore, several algorithms were proposed to solve state-space tasks optimally using less memory than A* and less time than IDA*, such as A*+IDA*, a hybrid memory-restricted algorithm that combines A* and IDA*. In this paper, we present a hybrid memory-restricted algorithm that combines Partial Expansion A* (PEA*) and IDA*. This new algorithm has two phases, the same structure as the A*+IDA* algorithm. The first phase of PEA*+IDA* runs PEA* until it reaches a memory limit, and the second phase runs IDA* without duplicate detection on each node of PEA*'s Open. First, we present a model that shows how PEA*+IDA* can perform better than A*+IDA* although pure PEA* usually makes more expansions than pure A*. Later, we perform an experimental evaluation using three memory limits and show that, compared to A*+IDA* on classical planning domains, PEA*+IDA* has higher coverage and expands fewer nodes. Finally, we experimentally analyze both algorithms and show that having higher F-limits and better priority-queue composition given by PEA* have a considerable impact on the performance of the algorithms.
BibTeX
@inproceedings{messa2022pea,
  author = {Frederico Messa and André Grahl Pereira},
  title = {{PEA*+IDA*: An Improved Hybrid Memory-Restricted Algorithm}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i9.21270},
}
Figure