Researchers introduce GONDOR, a memory-efficient extension of Greedy Best-First Search that enables planning algorithms to operate under strict memory constraints by compressing search trees while retaining sparse anchor states. The algorithm reconstructs paths through re-searching between these states, with experiments showing consistent improvements in coverage on low-memory devices compared to standard approaches.
GONDOR addresses a critical bottleneck in computational efficiency for edge devices and resource-constrained environments. Traditional Greedy Best-First Search dominates heuristic search applications but requires substantial memory for maintaining open and closed lists. This research tackles a practical problem: enabling sophisticated planning algorithms to function on devices with severe memory budgets, from embedded systems to mobile platforms.
The innovation centers on dynamic compression through anchor state selection and path reconstruction. Rather than storing the entire search tree, GONDOR periodically purges intermediate states while maintaining strategic waypoints (outposts), then re-searches locally between these anchors when a solution is found. This trade-off sacrifices some computational elegance for dramatic memory savings. The incorporation of Bloom filters for duplicate detection adds another efficiency layer by reducing memory overhead in closed-list management without sacrificing correctness.
For the edge computing and embedded AI sectors, this work carries significant implications. As AI deployment increasingly targets resource-constrained devices—autonomous robots, IoT systems, and field robotics—memory-efficient planning becomes essential. The research demonstrates consistent experimental validation across multiple planning domains and heuristic configurations, suggesting robust real-world applicability. The authors' commitment to releasing implementations accelerates adoption and enables community validation.
The broader impact extends to any domain requiring real-time planning under hardware constraints. This includes autonomous navigation, robotics pathfinding, and distributed decision-making systems. The technique's generalizability across different outpost selection policies provides flexibility for domain-specific optimization, making it a potential standard tool for practitioners building memory-conscious systems.
- →GONDOR enables heuristic search planning on memory-constrained devices by compressing search trees while retaining sparse anchor states
- →The algorithm reconstructs complete paths through re-searching between anchor points, trading modest computation for significant memory savings
- →Bloom filters enhance efficiency by providing compact duplicate detection without traditional closed-list overhead
- →Experimental validation across multiple planning domains shows consistent coverage improvements compared to standard GBFS under strict memory budgets
- →Open-source release facilitates adoption in edge computing, robotics, and embedded AI applications