Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
The paper introduces GONDOR, a memory-efficient extension of Greedy Best-First Search (GBFS) for heuristic search problems, designed for resource-constrained environments. GONDOR periodically compresses the search tree, retaining a sparse set of anchor states ("outposts") and reconstructs the path by re-searching between these outposts upon reaching the goal. Experiments on numeric planning domains demonstrate that GONDOR achieves higher coverage than standard GBFS under low memory budgets, especially when combined with Bloom filters for duplicate detection.
Planning on edge devices just got easier: GONDOR lets you do more with less memory by intelligently compressing search trees and re-searching between key "outpost" states.
Greedy Best-First Search (GBFS) is the dominant approach for solving search problems where the goal can be estimated with a heuristic, such as planning, route finding, navigation, and pathfinding. This is especially true when the memory is tightly constrained, such as planning on edge devices. To alleviate that, we present GONDOR (Greedy Online Navigation with Dynamic Outpost-based Re-search), a memory-efficient extension of GBFS that allows search to continue under strict memory limits by periodically compressing the search tree while retaining a sparse set of anchor states, then upon reaching the goal reconstructs the path by re-searching between the sparse states. We analyze the algorithm and discuss several variants defined by different outpost selection policies. In addition, we explore using Bloom filters for compact duplicate detection in the closed list. Experiments across numeric planning domains and heuristic configurations show that GONDOR consistently improves coverage under low memory budgets compared to standard GBFS. We release the implementation of GONDOR and the Bloom-filter variant to facilitate further research on memory-efficient heuristic search.