💻 computer science

Dual-Informed Vertical Expansion for Multi-Objective Node Selection in Anytime Conflict-Based Search

This paper introduces Dual-Informed Vertical Expansion (DIVE), a novel node-selection policy for Conflict-Based Search that dynamically balances best-bound and depth-oriented strategies to reduce memory usage, minimize search interruptions, and provide early feasible solutions without sacrificing optimality.

Original authors: Willem van Osselaer, Jiarui Li, Meshal Alharbi, Gioele Zardini

Published 2026-07-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Willem van Osselaer, Jiarui Li, Meshal Alharbi, Gioele Zardini

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the director of a massive, chaotic warehouse where hundreds of robots need to move from their starting spots to their destinations without bumping into each other. Your goal is to find the perfect plan that gets everyone there as fast as possible.

This is the problem of Multi-Agent Path Finding (MAPF). To solve it, the paper uses an algorithm called Conflict-Based Search (CBS). Think of CBS as a detective trying to solve a puzzle. The detective builds a giant "tree" of possibilities. Each branch of the tree represents a different scenario (e.g., "Robot A waits here," "Robot B moves there"). The detective's job is to explore these branches to find the one perfect path that solves the whole puzzle.

The paper argues that the biggest mistake detectives make isn't how they solve the puzzle, but which branch they look at next.

The Three Detective Styles

The paper compares three different ways a detective can choose which branch to explore next:

1. The "Best-Bound" Detective (Standard BFS)

The Strategy: This detective always looks at the branch that mathematically looks the most promising right now. They check the "score" of every open branch and pick the lowest one.
The Good: They are very efficient at finding the proof that a solution is perfect. They don't waste time looking at bad branches.
The Bad: They keep a huge list of every single branch they've ever considered. Their memory fills up fast. Also, they might spend hours checking the "best" branches before they ever find a working solution. If you ask them for a plan after 5 minutes, they might say, "I haven't found a single working plan yet, I'm still checking the math."

2. The "Deep-Dive" Detective (Iterative Deepening / ID)

The Strategy: This detective picks a branch and follows it all the way to the bottom, like diving deep into a cave. If they hit a dead end, they climb back up and try the next deep cave.
The Good: They are very memory-efficient. They only need to remember the path they are currently walking on, not the whole forest.
The Bad: They are repetitive. They often re-walk the same shallow paths over and over again as they try deeper and deeper caves. They also struggle to find a working solution quickly because they get stuck in deep, unproductive holes.

3. The New Hero: DIVE (Dual-Informed Vertical Expansion)

The Strategy: This is the new method proposed in the paper. It's a hybrid.
- The "Dive": When the detective finds a promising path, they commit to it. They follow that branch deep down, looking for a working solution. They exploit the fact that the next step is usually very similar to the current step (like a robot just taking one more step forward).
- The "Re-anchor": If the dive hits a dead end or gets stuck, the detective doesn't just wander aimlessly. They immediately jump back to the "Best-Bound" list (the main map of promising branches) to pick a new starting point.
The Magic: This gives you the best of both worlds. You get the memory efficiency of the deep dive, but you don't get stuck in bad holes forever because you keep checking the main map.

Why DIVE is a Game-Changer

The paper claims DIVE solves three specific headaches that the other detectives have:

The "Anytime" Problem: In the real world, robots can't wait forever for a perfect plan. They need a plan now.
- Standard BFS might run for 10 minutes and say, "I'm done, here is the perfect plan," but if you stopped it at minute 9, it would have nothing to show you.
- DIVE finds a working plan very early. Even if the plan isn't perfect yet, DIVE can tell you, "Here is a plan, and I know it's within 5% of being perfect." This is called an Anytime capability. It's like a chef who brings you a delicious appetizer while the main course is still cooking, rather than making you wait until the whole meal is done.
The Memory Problem:
- Standard BFS needs a massive notebook to track every possibility.
- DIVE keeps a much smaller notebook because it focuses on one path at a time, only writing down the "promising" alternatives when it has to.
The "Jumping" Problem:
- Standard BFS jumps around the tree wildly, switching from one totally different scenario to another. This is inefficient for computers because they have to reload their context every time.
- DIVE stays on the same "family tree" of scenarios for longer (this is called parent-child continuity). It's like reading a book chapter by chapter instead of reading page 1, then page 50, then page 3, then page 100.

The "Warm Start" Trick

The paper also mentions that if you give the detective a "warm start" (a rough, imperfect plan created by a faster, simpler robot), DIVE can use it to prune away bad branches immediately. It's like giving the detective a hint: "Don't look in the basement; the solution is on the second floor." This helps DIVE work even better in very crowded, difficult situations.

The Bottom Line

The paper doesn't claim DIVE is the "fastest" at finding the absolute perfect proof in every single case (Standard BFS still wins there). Instead, it claims DIVE is the most balanced choice for real-world robots.

It trades a tiny bit of extra math work to get:

Much less memory usage.
Fewer "jumps" between different scenarios.
A working plan available immediately, with a guarantee of how close it is to perfect.

In short, DIVE turns a rigid, all-or-nothing math solver into a flexible, practical tool that can handle the messy reality of robots moving in a warehouse.

Technical Summary: Dual-Informed Vertical Expansion for Multi-Objective Node Selection in Anytime Conflict-Based Search

Problem Statement
Conflict-Based Search (CBS) is a leading exact algorithm for Multi-Agent Path Finding (MAPF). Standard CBS employs a best-first search (BFS) strategy at the high level, selecting nodes with the minimum lower-bound key to expand. While this approach is efficient in minimizing the number of expanded nodes and rapidly advancing the dual bound (the optimality certificate), it suffers from three significant drawbacks in practical deployment:

Memory Intensity: It maintains a large open frontier, which can exceed onboard memory limits.
Poor Parent-Child Continuity: It frequently jumps between unrelated branches of the constraint tree, failing to exploit the efficiency gains of processing a child node immediately after its parent (where only one constraint changes).
Lack of Anytime Behavior: It typically provides no feasible solution (incumbent) until the algorithm terminates and optimality is certified, making it unsuitable for systems requiring intermediate feasible plans under time or resource constraints.

Existing alternatives, such as Iterative Deepening CBS (IDCBS), address memory by using depth-first passes but introduce repeated work and still fail to provide intermediate incumbents. This paper argues that node selection should be treated as a modular design choice rather than a fixed implementation detail, allowing for a multi-objective trade-off between expanded nodes, memory usage, parent-child continuity, and incumbent discovery.

Methodology
The authors formalize high-level node selection in CBS as a modular policy $\pi$ that determines the order of node expansion without altering the low-level search, branching rules, or admissible heuristics. They prove that changing this policy preserves the exactness of CBS, provided standard branch-and-bound pruning conditions are maintained.

The paper introduces Dual-Informed Vertical Expansion (DIVE), a new node-selection policy designed to occupy a "missing middle ground" in the design space. DIVE operates through two distinct mechanisms:

Dive Phase (Depth-Oriented): When a node is expanded, DIVE attempts to continue a "dive" by immediately expanding its best child (lowest lower-bound) if that child's bound is strictly less than the current incumbent's cost ( $z_P$ ). This exploits parent-child locality and seeks feasible solutions early.
Reanchoring Phase (Best-Bound): If a dive terminates (because the best child cannot improve the incumbent or no children exist), the policy reverts to the global best-bound frontier to select the root of the next dive. This ensures regular progress toward the optimality certificate.

DIVE also incorporates incumbent pruning: any node with a lower bound greater than or equal to the current best feasible solution is pruned. This allows DIVE to safely explore the "primal zone" (nodes with costs higher than the optimum) to find good feasible solutions without compromising the final optimality proof.

The paper further proposes Memory-Constrained DIVE (MC-DIVE), a responsive variant that switches to pure depth-first search if the open queue exceeds a specific memory threshold, demonstrating how node selection can adapt to runtime constraints.

Key Contributions

Formal Separation of Policy and Correctness: The paper proves that node selection is independent of the exactness of CBS. Under standard branch-and-bound conditions, any policy that selects nodes from the open set preserves optimality, allowing for the design of policies that optimize for metrics other than just node count.
The DIVE Policy: The introduction of DIVE, which combines best-bound reanchoring with depth-oriented diving. It is shown to be a distinct Pareto point in the multi-objective space, minimizing dive breaks (transitions between parent-child chains) while retaining best-bound progress.
Multi-Objective Framework: The authors define a framework to evaluate policies based on five competing objectives: expanded nodes, dive breaks, maximum queue size, primal-bound progress (incumbent quality), and dual-bound progress (certificate speed).
Theoretical Analysis: The paper provides theoretical bounds on the performance of BFS, Depth-First Search (DFS), Iterative Deepening (ID), and DIVE on perfect search trees, predicting that BFS minimizes nodes, ID minimizes queue size, and DIVE minimizes dive breaks.

Experimental Results
Experiments on standard MAPF benchmarks (empty, random, room, and warehouse maps) with varying robot densities support the theoretical trade-off map:

Expanded Nodes: BFS remains the most efficient in terms of the number of nodes expanded. DIVE expands slightly more nodes (18–57% more on some benchmarks) due to controlled exploration of the primal zone, but significantly fewer than ID (which can expand 13–134% more due to repeated restarts).
Dive Breaks: DIVE consistently reduces the number of dive breaks by 6% to 51% compared to BFS, significantly improving parent-child continuity.
Memory Usage: DIVE reduces the maximum queue size by 44% to 86% compared to BFS, though ID remains the most memory-efficient (reducing queue size by 89–97%).
Anytime Behavior: DIVE is the only policy that consistently provides early feasible incumbents with certified primal-dual gaps before the search completes. In many cases, DIVE finds an optimal solution before the dual bound catches up to the optimum, whereas BFS and ID provide no solution until termination.
Warm Starts: In dense regimes where finding an initial incumbent is difficult, DIVE benefits significantly from warm starts (e.g., from PIBT), allowing it to solve instances that otherwise time out.
Ablation: Removing the "diversified search" component (best-bound restarts) from DIVE results in a policy that behaves like a pruned DFS, requiring substantially more nodes and dive breaks, confirming that the reanchoring mechanism is critical to DIVE's efficiency.

Significance and Claims
The paper claims that DIVE does not universally dominate existing policies but rather offers a distinct operating point in the design space of exact CBS. Its significance lies in transforming exact CBS into an anytime algorithm that can:

Provide feasible, high-quality solutions with certified gaps under time or memory constraints.
Reduce memory pressure and improve implementation runtime through better parent-child continuity.
Adapt to deployment contexts (e.g., memory-limited robots) through responsive variants like MC-DIVE.

The authors emphasize that while BFS is optimal for minimizing node count and ID is optimal for minimizing explicit memory, DIVE is the preferred choice when the system requires a balance of these factors, specifically when early feasible solutions and reduced dive breaks are critical for real-world robotic applications. The work motivates a shift from viewing node selection as a fixed heuristic to treating it as a tunable, multi-objective design parameter.

The Three Detective Styles

Why DIVE is a Game-Changer

The "Warm Start" Trick

The Bottom Line

Technical Summary: Dual-Informed Vertical Expansion for Multi-Objective Node Selection in Anytime Conflict-Based Search

More like this