---
title: "Attractor-based Closed List Search: Sparsifying the Closed List for Efficient Memory-Constrained Planning"
authors:
  - "Alvin Zou"
  - "Muhammad Suhail Saleem"
  - "Maxim Likhachev"
doi: "10.24963/ijcai.2025/1004"
url: "https://ijcai.org/proceedings/2025/1004"
pdf: "https://ijcai.org/proceedings/2025/1004.pdf"
venue: "Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence"
year: 2025
pages: "9031-9038"
track: "Main Track"
keywords:
  - "Search: S: Heuristic search"
---

# Attractor-based Closed List Search: Sparsifying the Closed List for Efficient Memory-Constrained Planning

Alvin Zou, Muhammad Suhail Saleem, Maxim Likhachev

*Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence*, pages 9031-9038. DOI: [10.24963/ijcai.2025/1004](https://doi.org/10.24963/ijcai.2025/1004)

## Abstract

Best-first search algorithms such as A* and Weighted A* are widely used tools. However, their high memory requirements often make them impractical for memory-constrained applications, such as on-board planning for interplanetary rovers, drones, and embedded systems. One popular strategy among memory-efficient approaches developed to address this challenge is to eliminate or sparsify the Closed list, a structure that tracks states explored by the search. However, such methods often incur substantial overhead in runtime, requiring recursive searches for solution reconstruction. In this work, we propose Attractor-based Closed List Search (ACLS), a novel framework that sparsely represents the Closed list using a small subset of states, termed attractors. ACLS intelligently identifies attractor states in a way that enables efficient solution reconstruction while preserving theoretical guarantees on the quality of the solution. Furthermore, we also introduce a lazy variant, Lazy-ACLS, which defers the computation of attractor states until necessary, substantially improving planning speed. We demonstrate the efficacy of ACLS used in conjunction with A*, Weighted A*, and Dijkstra’s searches across multiple domains including 2D and 3D navigation, Sliding Tiles, and Towers of Hanoi. Our experimental results demonstrate that ACLS significantly reduces memory usage, maintaining only 9% of the states typically stored in a Closed list, while achieving comparable planning times and outperforming state-of-the-art approaches. Source code can be found at github.com/alvin-ruihua-zou/ACLS.