GONDOR to the Rescue: Satisficing Planning with Low Memory

• URL: http://arxiv.org/abs/2605.28454v1
• Date: Wed, 27 May 2026 13:20:58 GMT
• Title: GONDOR to the Rescue: Satisficing Planning with Low Memory
• Abstract summary: GONDOR is a memory-efficient extension of Greedy Best-First Search (GBFS)<n>GONDOR periodically compresses 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.<n> Experiments show that GONDOR consistently improves coverage under low memory budgets compared to standard GBFS.
• Score: 80.8869960059932
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Fast and Efficient Approximate Nearest Neighbor Search for High-Dimensional LLM Embeddings [0.0]
  SISAP Indexing Challenge benchmarks Approximate Nearest Neighbor Search (ANNS) algorithms under rigorous constraints.<n>This paper presents our submissions for the 2026 edition, addressing both $k$-Nearest Neighbor Graph (kNNG) construction on 1024-dimensional BGE-M3 embeddings and Maximum Inner Product Search (MIPS) on unnormalized Llama-3.2-8B features.
  arXiv  Detail & Related papers  (2026-07-23T06:35:12Z)
• PRISM: Pareto-Efficient Retrieval over Intent-Aware Structured Memory for Long-Horizon Agents [9.504077408241544]
  Long-horizon language agents accumulate conversation history far faster than any fixed context window can hold.<n>We present PRISM, a training-free retrieval-side framework that treats long-horizon memory as a joint retrieval-and-compression problem.
  arXiv  Detail & Related papers  (2026-05-12T15:28:30Z)
• GP-Tree: An in-memory spatial index combining adaptive grid cells with a prefix tree for efficient spatial querying [5.732286906919534]
  GP-Tree is a fine-grained spatial index that organizes approximated grid cells of spatial objects into a prefix tree structure.<n>We introduce optimization strategies, including tree pruning and node optimization, to reduce search paths and memory consumption.<n>Experiments on real-world datasets demonstrate that GP-Tree significantly outperforms traditional spatial indexes.
  arXiv  Detail & Related papers  (2026-03-08T07:59:03Z)
• Adaptive Prefiltering for High-Dimensional Similarity Search: A Frequency-Aware Approach [0.0]
  We present an adaptive prefiltering framework that partitions the query space into frequency tiers following Zipfian distributions.<n>Experiments on ImageNet-1k using CLIP embeddings demonstrate that frequency-aware budget allocation achieves equivalent recall with 20.4% fewer distance computations.<n>The framework introduces minimal overhead through lightweight frequency tracking and provides graceful degradation for unseen queries through coherence-based fallback policies.
  arXiv  Detail & Related papers  (2025-12-03T10:11:35Z)
• SLOPE: Search with Learned Optimal Pruning-based Expansion [2.0618817976970103]
  We present the Search with Learned Optimal Pruning-based Expansion (SLOPE) It learns the distance of a node from a possible optimal path, which in turn reduces the size of the open list. This ensures that the search explores only the region close to optimal paths while lowering memory and computational costs.
  arXiv  Detail & Related papers  (2024-06-07T13:42:15Z)
• Exploring Complicated Search Spaces with Interleaving-Free Sampling [127.07551427957362]
  In this paper, we build the search algorithm upon a complicated search space with long-distance connections. We present a simple yet effective algorithm named textbfIF-NAS, where we perform a periodic sampling strategy to construct different sub-networks. In the proposed search space, IF-NAS outperform both random sampling and previous weight-sharing search algorithms by a significant margin.
  arXiv  Detail & Related papers  (2021-12-05T06:42:48Z)
• Stagnation Detection in Highly Multimodal Fitness Landscapes [0.0]
  Stagnation detection has been proposed as a mechanism for randomized searchs to escape from local optima. In this paper, we investigate a new mechanism called radius memory which can be added to stagnation detection to control the search radius more carefully. We implement this idea in an algorithm called SD-RLS$textm$ and show compared to previous variants of stagnation detection that it yields speed-ups.
  arXiv  Detail & Related papers  (2021-04-09T14:33:52Z)
• BR-NS: an Archive-less Approach to Novelty Search [70.13948372218849]
  We discuss an alternative approach to novelty estimation, dubbed Behavior Recognition based Novelty Search (BR-NS) BR-NS does not require an archive, makes no assumption on the metrics that can be defined in the behavior space and does not rely on nearest neighbours search. We conduct experiments to gain insight into its feasibility and dynamics as well as potential advantages over archive-based NS in terms of time complexity.
  arXiv  Detail & Related papers  (2021-04-08T17:31:34Z)
• ROME: Robustifying Memory-Efficient NAS via Topology Disentanglement and Gradient Accumulation [106.04777600352743]
  Differentiable architecture search (DARTS) is largely hindered by its substantial memory cost since the entire supernet resides in the memory. The single-path DARTS comes in, which only chooses a single-path submodel at each step. While being memory-friendly, it also comes with low computational costs. We propose a new algorithm called RObustifying Memory-Efficient NAS (ROME) to give a cure.
  arXiv  Detail & Related papers  (2020-11-23T06:34:07Z)
• Sub-linear Regret Bounds for Bayesian Optimisation in Unknown Search Spaces [63.22864716473051]
  We propose a novel BO algorithm which expands (and shifts) the search space over iterations. We show theoretically that for both our algorithms, the cumulative regret grows at sub-linear rates.
  arXiv  Detail & Related papers  (2020-09-05T14:24:40Z)
• Best-First Beam Search [78.71330480725668]
  We show that the standard implementation of beam search can be made up to 10x faster in practice. We propose a memory-reduced variant of Best-First Beam Search, which has a similar beneficial search bias in terms of downstream performance.
  arXiv  Detail & Related papers  (2020-07-08T05:56:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.