Andrii Bidochko

• Updated: June 14, 2026
• 7 min read

GONDOR to the Rescue: Satisficing Planning with Low Memory

Direct Answer

GONDOR (Greedy Online Navigation with Dynamic Outpost‑based Re‑search) is a memory‑efficient extension of Greedy Best‑First Search (GBFS) that keeps planning feasible on devices with very tight RAM budgets. By periodically compressing the search tree into a sparse set of “outpost” states and later re‑searching between them, GONDOR dramatically expands coverage while staying within strict memory limits.

Background: Why This Problem Is Hard

Heuristic search algorithms such as GBFS dominate domains ranging from autonomous navigation to automated workflow orchestration because they can quickly home in on a goal using an admissible heuristic. The algorithm’s strength, however, is also its Achilles’ heel: it expands a frontier of nodes that must be stored in memory. On modern edge devices—smart sensors, drones, or on‑device AI assistants—available RAM can be as low as a few megabytes. When the open‑list (the priority queue) and closed‑list (duplicate detection) exceed this budget, the planner either crashes or is forced to prune aggressively, which often leads to incomplete or sub‑optimal plans.

Traditional mitigations include:

• Iterative deepening: repeatedly runs the search with increasing depth limits, but each iteration repeats work and can be too slow for real‑time constraints.
• Memory‑bounded A* (e.g., SMA*): discards least‑promising nodes, yet the discarding policy can discard critical waypoints, causing the planner to miss reachable goals.
• External storage: offloads nodes to disk or flash, which introduces latency unsuitable for latency‑sensitive agents.

These approaches either sacrifice completeness, increase latency, or demand hardware that many edge deployments cannot afford. Consequently, a method that can retain the rapid convergence of GBFS while staying within a strict memory envelope is highly desirable for today’s AI‑driven products.

What the Researchers Propose

The GONDOR framework reimagines the search process as a two‑phase cycle:

1. Online Navigation Phase: The planner runs a standard GBFS expansion, but after a configurable number of node generations it triggers a compression step.
2. Outpost Selection & Re‑search Phase: Instead of discarding the entire frontier, GONDOR selects a sparse set of “outpost” states that act as anchors. The rest of the tree is pruned, freeing memory. When the goal is finally reached, the algorithm stitches together a complete path by re‑searching locally between consecutive outposts.

Key components include:

• Outpost Selector: a policy that decides which nodes become anchors based on heuristic value, depth, or diversity.
• Compression Engine: responsible for deleting non‑anchor nodes and updating the open‑list.
• Re‑search Scheduler: orchestrates the short‑range searches that reconnect outposts after the goal is discovered.
• Duplicate Detector (optional Bloom‑filter variant): provides a compact, probabilistic closed‑list to further shrink memory usage.

How It Works in Practice

The practical workflow can be visualized as a loop that alternates between expansion and consolidation:

1. Initialize: Insert the start state into the open‑list.
2. Expand: Repeatedly pop the node with the lowest heuristic estimate (the GBFS “greedy” step) and generate successors.
3. Monitor Memory: After every k expansions (or when a memory threshold is crossed), invoke the compression routine.
4. Select Outposts: Apply the chosen outpost policy—e.g., keep the top‑N nodes with the best heuristic scores, or retain nodes that maximize spatial coverage.
5. Prune: Remove all non‑outpost nodes from both open‑ and closed‑lists, freeing RAM.
6. Continue Search: Resume GBFS from the remaining outposts, treating each as a new frontier.
7. Goal Detection: When a node satisfies the goal predicate, halt forward expansion.
8. Re‑search Stitching: Starting from the goal, run a bounded GBFS backward to the nearest outpost, then repeat until the start state is reached. Concatenate the resulting sub‑paths into a full solution.

What distinguishes GONDOR from earlier memory‑bounded planners is the explicit preservation of strategically chosen waypoints (outposts) that guarantee connectivity. The re‑search phase is lightweight because it operates on a dramatically reduced sub‑graph, and the overall memory footprint stays bounded regardless of the original problem size.

Evaluation & Results

The authors benchmarked GONDOR across several numeric planning domains (e.g., logistics, robot motion, and resource allocation) using a variety of heuristic configurations (admissible, inadmissible, and learned heuristics). Experiments compared three setups:

• Standard GBFS with unlimited memory (baseline).
• GBFS constrained to a low memory budget (e.g., 2 MB).
• GONDOR under the same low‑memory budget, with different outpost policies and with/without the Bloom‑filter duplicate detector.

Key findings include:

• Coverage Improvement: GONDOR solved 30‑45 % more problem instances than memory‑constrained GBFS across all domains.
• Solution Quality: The length of the returned plans was within 5‑10 % of the unlimited‑memory baseline, demonstrating that the compression does not dramatically degrade optimality.
• Memory Consistency: Peak RAM usage never exceeded the preset limit, confirming the algorithm’s predictability for edge deployment.
• Bloom‑filter Variant: Adding a Bloom filter reduced closed‑list memory by up to 60 % with only a negligible increase in false‑positive duplicate checks, further extending coverage under the tightest budgets.

These results collectively show that GONDOR can retain the speed and heuristic guidance of GBFS while delivering robust performance on devices where traditional planners would fail.

Why This Matters for AI Systems and Agents

For practitioners building autonomous agents, robotics pipelines, or on‑device AI assistants, planning under memory constraints is a daily reality. GONDOR’s outpost‑centric design offers a practical pathway to embed sophisticated heuristic search directly on edge hardware without offloading to the cloud.

Specific implications include:

• Real‑time Decision Making: Agents can generate feasible routes or action sequences within milliseconds, even when operating on micro‑controllers with limited RAM.
• Scalable Multi‑Agent Coordination: Because each agent can run its own GONDOR instance independently, large fleets (e.g., delivery drones) can plan locally without a central server.
• Reduced Cloud Dependency: By keeping planning on‑device, data privacy is preserved and network latency is eliminated—critical for compliance‑heavy industries.
• Integration with Existing Toolchains: GONDOR’s modular outpost selector can be swapped for domain‑specific heuristics, making it compatible with platforms such as the UBOS platform overview that already support custom planning modules.
• Enhanced Automation Workflows: When combined with the Workflow automation studio, GONDOR can serve as the backbone for dynamic task scheduling in low‑resource environments.

Overall, GONDOR bridges the gap between high‑performance heuristic search and the practical memory limits of modern edge deployments, unlocking new use‑cases for AI agents that were previously out of reach.

What Comes Next

While GONDOR marks a significant step forward, several avenues remain open for exploration:

• Adaptive Outpost Policies: Learning‑based selectors that adjust outpost density based on observed search difficulty could further improve coverage.
• Hybrid Memory Models: Combining GONDOR with external‑memory techniques (e.g., SSD‑backed caches) may enable planning on devices with ultra‑tight RAM but ample flash storage.
• Domain‑Specific Extensions: Tailoring the re‑search phase to exploit problem structure (e.g., hierarchical abstractions in robotics) could reduce the stitching overhead.
• Robustness to False Positives: Investigating alternative probabilistic data structures beyond Bloom filters (e.g., Cuckoo filters) may lower duplicate detection error rates.
• Enterprise‑Scale Deployment: Integrating GONDOR into the Enterprise AI platform by UBOS would allow large organizations to provision memory‑efficient planners across heterogeneous hardware fleets.
• Community Adoption: The authors have released an open‑source implementation; contributing extensions, benchmarks, or wrappers for popular robotics middleware (ROS, MoveIt) can accelerate real‑world uptake.

Developers interested in experimenting with GONDOR can start by cloning the repository, reviewing the provided outpost selection modules, and plugging the planner into existing UBOS solutions for SMBs that require on‑device decision making.

References

For a complete technical description, see the original pre‑print: GONDOR paper on arXiv.

Andrii Bidochko

CTO UBOS

Andrii Bidochko is an AI entrepreneur and researcher focused on AI agents, reinforcement learning, and autonomous systems. He writes about the technologies shaping the future of machine intelligence, from frontier models and agent architectures to real-world AI applications.