在内存极有限时,用稀疏锚点重搜路径,让贪心搜索不中断。
GONDOR to the Rescue: Satisficing Planning with Low Memory
- 用动态锚点压缩搜索树,仅保留关键状态节点
- 在低内存下覆盖范围比传统贪心搜索提升显著
- 适合边缘设备等内存受限的规划场景
贪心最佳优先搜索(GBFS)是解决可估价目标搜索问题的主流方法,尤其适用于内存受限场景,如边缘设备上的规划任务。为缓解内存压力,本文提出GONDOR(Greedy Online Navigation with Dynamic Outpost-based Re-search),一种内存高效的GBFS扩展:通过周期性压缩搜索树并保留稀疏锚点状态,在达到目标后通过重搜锚点间路径恢复解。我们分析了算法并探讨不同锚点选择策略的变体。此外,探索使用布隆过滤器实现闭列表中紧凑的重复检测。在多个数值规划领域和启发式配置下的实验表明,相比标准GBFS,GONDOR在低内存预算下始终表现出更优的覆盖能力。我们开源了GONDOR及其布隆过滤器变体,以促进内存高效启发式搜索研究。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。