db-ECBS Plans Motion for Dense Robot Swarms

Why moving a crowd of robots is hard

Coordinating many robots in a shared space sounds like a solved problem until you look at what the popular solutions actually assume. The dominant family, Multi Agent Path Finding, treats the world as a grid graph. A robot hops from cell to neighboring cell, and the planner’s job is to schedule those hops so nobody collides. It is fast and it has clean guarantees, but it throws away something important. Real robots have momentum. A quadrotor cannot stop on a dime or turn a right angle in place. A car with a trailer cannot slide sideways. The grid plan may be lovely on paper and physically impossible to execute.

The fix is kinodynamic planning, which respects the robot’s dynamics and actuation limits so the plan is actually flyable or drivable. The trouble is that kinodynamic planning for one robot is already hard, and doing it for a whole team in a shared space multiplies the difficulty. Most methods respond by making a compromise. Either they simplify the dynamics until the problem is tractable, or they accept trajectories that are far from optimal, wasting time and energy. Neither is satisfying when you want a warehouse full of robots to move quickly and smoothly.

There is a second problem that almost every planner ignores entirely. When two drones fly close together, the air matters. The rotors of one push a downward jet, the downwash, onto anything below, and that force can knock the lower drone off its planned path. Measure it in a lab and it is not a rounding error, it is a real disturbance that can break a tight formation. Akmaral Moldagalieva, Joaquim Ortiz-Haro, and Wolfgang Hönig argue that a planner for close proximity flight has to reason about these forces up front rather than hope a controller cleans them up later.

The pieces db-ECBS is built from

The name db-ECBS stands for discontinuity bounded Enhanced Conflict Based Search, and it is a marriage of three existing ideas. Understanding the parents makes the child easy to read.

The first parent is Conflict Based Search, a well known solver for the grid version of the problem. Its trick is a two level structure. At the low level, each robot plans its own path as if the others did not exist. At the high level, the planner looks for conflicts, two robots wanting the same cell at the same time, and resolves them one at a time by adding a constraint that forbids one robot from being there then. Enhanced Conflict Based Search is a faster variant that accepts solutions within a controllable factor of optimal, trading a little quality for a lot of speed. That factor is written \(\omega\), and it is the knob that lets the planner run fast when a perfect answer is not worth the wait.

The second parent is db-A*, a single robot kinodynamic planner. Rather than search a grid, it stitches together short precomputed motion snippets called motion primitives, each one a little trajectory that already obeys the robot’s dynamics. The clever part is that it allows small gaps, or discontinuities, between primitives during the search, bounded by a value \(\delta\). Allowing gaps makes the search far easier, and the gaps get cleaned up later.

The third parent is nonlinear trajectory optimization, the step that takes the rough, slightly discontinuous plan and polishes it into a smooth, dynamically feasible trajectory that respects every limit. The authors solve this in the joint space of all robots at once so the interactions between them are handled properly.

How the three layers work together

Put those parents together and db-ECBS runs a search in three layers, all offline before the robots move.

At the low level, every robot plans its own trajectory independently using db-A*, gaps and all. These plans are cheap because each robot ignores the others. At the middle level, the planner checks whether any two robots collide or whether any drone pushes too much downwash onto another, and it resolves the earliest such conflict by handing both robots a new constraint and replanning just them. At the top level, once the trajectories are collision free and within the force limits, they become the starting guess for the joint optimization that removes the remaining gaps and produces the final plan.

Then comes the part that makes it an anytime planner. The whole procedure repeats with a smaller discontinuity bound \(\delta\), which means more motion primitives and a finer, more accurate search. Each pass can improve on the last, so the planner returns a usable answer quickly and keeps making it better if you give it more time. The authors prove the method is probabilistically complete, meaning it will find a solution if one exists given enough search effort, and asymptotically bounded suboptimal, meaning the cost of its answer stays within the factor \(\omega\) of the best possible.

Teaching the search to feel the air

The interaction awareness is the feature that sets this planner apart, so it is worth seeing how it enters the math. Each robot’s dynamics get an extra term, a disturbance force \(\psi\) that depends on where its neighbors are.

Here \(\mathbf{x}\) is the robot state, \(\mathbf{u}\) is its control input, and \({\psi}\) is the interaction force set by the relative states of nearby robots \(\mathbf{r}\). A simple physical version of that force, for a pair of robots, is a repulsion that grows sharply as they close in.

The vector \(\mathbf{p}^{(12)}\) is the position of one robot relative to the other and \(\lambda\) scales the strength. For real drones the true downwash is messier than this clean formula, so the authors model it with a learned network, a deep sets model borrowed from the Neural-Swarm2 line of work, that predicts the aggregate force from all neighbors. The planner then treats this force as a hard limit. A trajectory is only allowed if the interaction force on every robot stays under a maximum \(\psi_{\max}\), and the conflict resolver treats a force that exceeds the limit exactly like a collision, adding a constraint to push the robots apart.

They also offer a simpler, more conservative option, wrapping each robot in an ellipsoid large enough that the downwash between any two robots outside their ellipsoids stays safe. The paper calls the conservative version db-ECBS-C and the interaction aware version db-ECBS-R, and the comparison between them is one of the more instructive results.

When two robots fly in close proximity, there is a nonnegligible force between them caused by airflow. This force can cause the lower robot to deviate from its planned trajectory. Ignoring these aerodynamic interactions can compromise trajectory accuracy and stability, potentially leading to unsafe formations. Moldagalieva, Ortiz-Haro, and Hönig, on why the air cannot be ignored

What the benchmark shows

The evaluation is broad, which is what gives the results weight. The authors test on 65 problems spanning six robot dynamics, a first order unicycle, a second order unicycle, a two dimensional double integrator, a three dimensional double integrator, and a car with a trailer among them. They compare against a spread of strong baselines, the sampling planner SST*, the mixed integer method S2M2, the conflict based planner K-CBS, their own earlier db-CBS, and the model predictive method MAPF/C+POST.

Two headline findings stand out. First, on problems without interaction forces, db-ECBS keeps finding solutions as the number of robots climbs, while the earlier db-CBS sees its success rate collapse. On a set of random heterogeneous problems with eight robots, db-CBS solved only a fraction while db-ECBS consistently returned an answer. Second, the solutions are cheap. Across the random instances db-ECBS produced trajectories at less than half the cost of the alternatives, a large margin in a field where a few percent is often the story.

The window and wall scenarios are where interaction awareness earns its keep. In the window problem, eight drones squeeze through a single opening half a meter across, flying close enough that downwash is unavoidable. The interaction aware db-ECBS-R keeps a 100 percent success rate with lower cost than the conservative ellipsoid version, because the conservative version keeps robots so far apart that it cannot fit them all through the gap. Reasoning about the actual force, rather than assuming a worst case bubble, is what lets the crowd thread the needle.

There is an honest counterpoint the authors do not hide. In large, open environments where robots are not forced together, the conservative ellipsoid model is often the smarter choice. It is simpler and faster, and when there is room to spread out, the interaction force never approaches its limit, so the extra machinery of the learned model earns nothing. The interaction aware version pays off specifically in dense, tight spaces, which is exactly where it is designed to help.

Does it run on real robots

Simulation results invite the obvious question, and the authors answer it. They fly the plans on hardware in a room about 7 meters by 4 meters, tracked by twelve motion capture cameras. The aerial robots are Bitcraze Crazyflie 2.1 drones controlled through Crazyswarm2, and the ground robots are Pololu 3pi+ 2040 differential drive units. One demonstration runs the eight drone window swap. Another mixes four ground robots and four flying robots and asks them to swap positions, with a 60 centimeter bamboo stick mounted on each ground robot to make the geometry genuinely awkward.

The plans track safely on the real robots, which matters because a plan that respects dynamics on paper can still fail if the model is wrong. The gap between the simulated trajectory and the flown one stays small, evidence that the dynamics and interaction models are close enough to reality to be trusted. The authors are candid that the controllers assume no sensing noise, so the motion primitives use slightly conservative limits to leave the controller room to correct small disturbances online.

Where it strains, honestly

The paper is refreshingly clear about the limits, and they mostly trace back to one place, the joint optimization at the top layer. Its cost grows only linearly with the number of time steps, which is fine, but it grows cubically with the dynamics dimension, and it has to optimize all robots together. That gets expensive fast. On a wall scenario with 16 drones the discrete search finishes in under a minute, about 54 seconds, while the joint optimization takes more than 1000 seconds. The search scales gracefully. The optimization is the bottleneck that caps how large a team the method can handle.

A second limit is that the motion primitives are tied to the environment. Long primitives are efficient in big open spaces but clumsy in tight ones, and short primitives are the reverse, so the right library depends on the scene. The authors suggest generating environment conditioned primitives with generative models as a way out, and point to a diffusion based follow up of their own. There is also the assumption of no sensing or actuation noise in the model, reasonable in a motion capture room but a real gap for outdoor or onboard sensing.

Finally, the interaction model is only as good as the data behind it. The learned downwash comes from a network trained on specific drones in a lab, and extending it to new robots or wildly different formations is not free. The physical repulsion formula is a clean illustration, but the real forces are captured by a model with its own training distribution and its own blind spots.

Reproducing the joint optimization

The discrete search that makes db-ECBS scale is not naturally a machine learning object, but the top layer, the joint trajectory optimization with interaction forces, is a differentiable optimization that maps cleanly onto modern tooling. The implementation below writes that layer as a differentiable module. It models a small team of double integrator drones, adds a downwash style interaction force between them, and optimizes the joint trajectory from a straight line guess by gradient descent, penalizing collisions, actuation over limits, and excess interaction force. A runnable smoke test sends two drones on a head on swap and watches the optimizer bow their paths apart so both the separation and the force stay within their limits.

# Joint trajectory optimization with interaction forces.
# Educational reimplementation of the top layer of db-ECBS from
# Moldagalieva, Ortiz-Haro, and Honig, "db-ECBS: Interaction-Aware
# Multirobot Kinodynamic Motion Planning" (IEEE T-RO 2026). The discrete
# search (db-A* and ECBS) is not reproduced here. This is the joint
# space optimization that repairs a rough plan into a feasible one.
# Written with torch autograd so the whole trajectory is differentiable.

import torch


def downwash_force(pos, lam=2e-3, eps=0.05):
    """Pairwise interaction force on each robot from its neighbors.

    pos has shape [N, 3]. A simple physical stand in for the learned
    deep sets model in the paper. The force grows as robots close in and
    pushes the lower robot down, mimicking rotor downwash.
    """
    N = pos.shape[0]
    force = torch.zeros_like(pos)
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            d = pos[i] - pos[j]
            dist = torch.linalg.norm(d) + eps
            # Repulsion along the separation, stronger when close.
            force[i] = force[i] + lam * d / dist ** 3
            # Extra downward shove if robot i sits below robot j.
            if pos[i][2] < pos[j][2]:
                horiz = torch.linalg.norm(d[:2]) + eps
                force[i][2] = force[i][2] - lam / horiz ** 2
    return force


class JointTrajectoryOptimizer:
    """Optimize joint trajectories for N double integrator drones.

    Decision variables are the accelerations for every robot at every
    step. Positions and velocities follow from double integrator rollout.
    """

    def __init__(self, starts, goals, steps=60, dt=0.1,
                 a_max=2.0, safe_dist=0.35, psi_max=0.15):
        self.starts = starts            # [N, 3] start positions
        self.goals = goals              # [N, 3] goal positions
        self.N = starts.shape[0]
        self.steps = steps
        self.dt = dt
        self.a_max = a_max              # actuation limit
        self.safe_dist = safe_dist      # min robot separation
        self.psi_max = psi_max          # interaction force limit
        # Straight line acceleration guess, the role db-A* plays upstream.
        self.acc = torch.zeros(self.N, steps, 3, requires_grad=True)

    def rollout(self):
        """Integrate double integrator dynamics from the accelerations."""
        pos = self.starts.clone()
        vel = torch.zeros_like(self.starts)
        traj = []
        for k in range(self.steps):
            vel = vel + self.dt * self.acc[:, k]
            pos = pos + self.dt * vel
            traj.append(pos)
        return torch.stack(traj, dim=1)      # [N, steps, 3]

    def cost(self, traj):
        """Weighted sum of goal, effort, collision, and force penalties."""
        goal_err = ((traj[:, -1] - self.goals) ** 2).sum()
        effort = (self.acc ** 2).sum() * self.dt
        act_pen = torch.clamp(self.acc.abs() - self.a_max, min=0.0).pow(2).sum()

        collide = torch.zeros(1)
        force_pen = torch.zeros(1)
        for k in range(self.steps):
            p = traj[:, k]
            f = downwash_force(p)
            # Force violation, the interaction aware constraint.
            force_pen = force_pen + torch.clamp(
                torch.linalg.norm(f, dim=1) - self.psi_max, min=0.0).pow(2).sum()
            for i in range(self.N):
                for j in range(i + 1, self.N):
                    gap = torch.linalg.norm(p[i] - p[j])
                    collide = collide + torch.clamp(self.safe_dist - gap, min=0.0).pow(2)

        return (30.0 * goal_err + 0.05 * effort
                + 120.0 * collide + 60.0 * force_pen + 5.0 * act_pen)

    def solve(self, iters=800, lr=0.03):
        """Gradient descent on the joint trajectory, the anytime refinement."""
        opt = torch.optim.Adam([self.acc], lr=lr)
        for it in range(iters):
            opt.zero_grad()
            loss = self.cost(self.rollout())
            loss.backward()
            opt.step()
        return loss.item()


def smoke_test():
    """Two drones swap positions head on and route around each other.

    A tiny lateral offset in the starts breaks the symmetry so the
    optimizer knows which way to bow the trajectories apart.
    """
    starts = torch.tensor([[0.0, 0.01, 1.2], [2.0, -0.01, 1.2]])
    goals = torch.tensor([[2.0, 0.0, 1.2], [0.0, 0.0, 1.2]])
    opt = JointTrajectoryOptimizer(starts, goals)

    final_loss = opt.solve()
    traj = opt.rollout().detach()

    # Report the closest approach and the largest interaction force.
    min_gap = 1e9
    max_force = 0.0
    for k in range(opt.steps):
        p = traj[:, k]
        min_gap = min(min_gap, torch.linalg.norm(p[0] - p[1]).item())
        max_force = max(max_force, torch.linalg.norm(
            downwash_force(p), dim=1).max().item())

    reached = torch.linalg.norm(traj[:, -1] - goals, dim=1).max().item()
    assert torch.isfinite(traj).all(), "non finite trajectory"
    print("final loss        {:.3f}".format(final_loss))
    print("closest approach  {:.3f} m  (safe distance 0.35 m)".format(min_gap))
    print("largest force     {:.3f}   (limit 0.15)".format(max_force))
    print("worst goal miss   {:.3f} m".format(reached))
    print("smoke test passed")


if __name__ == "__main__":
    smoke_test()

The honest caveat is the same one the paper carries. This reproduces the smoothing layer, not the search. The discrete db-A* and Enhanced Conflict Based Search that let the real system scale to sixteen robots live above this optimizer and feed it a good initial guess, which is what keeps the nonconvex optimization from wandering into a bad local minimum. The downwash function here is a readable physical stand in for the learned model the authors actually use. Swap it for a trained network and the structure does not change.

What this changes for robot teams

The practical promise is fleets that move like they mean it. A warehouse where some robots scan shelves while others haul boxes is a heterogeneous team sharing tight aisles, and a planner that respects each robot’s dynamics and keeps them from fouling each other’s airflow is what makes dense operation safe rather than merely possible. Delivery drones staging at a depot, inspection swarms threading through structure, search teams covering a collapsed building, all live in the regime this planner targets.

The interaction awareness is the piece that feels forward looking. As robots get cheaper and teams get denser, the assumption that each robot is an isolated point stops holding, and the forces they exert on each other become part of the planning problem rather than a nuisance for the controller. For anyone building the autonomy stack around a robot team, this sits next to the navigation and coordination problems the field is already chewing on, from how robot path planning has evolved to the security questions raised by coordinating an internet of drones. You can browse the wider set of work through the robotics and autonomous systems pillar.

Conclusion

The core achievement of this work is a single motion planner that holds three hard requirements together, respecting the real dynamics of a heterogeneous robot team, scaling to crowds of up to sixteen aerial robots, and reasoning directly about the aerodynamic forces the robots exert on each other. By generalizing a proven grid solver to the continuous, dynamics aware setting and layering fast search, conflict resolution, and joint optimization, db-ECBS finds trajectories at less than half the cost of its competitors and keeps working in dense scenarios where they fail outright.

The conceptual shift underneath it is treating interaction forces as a first class part of the plan. The easy path is to plan as if robots were points and hope a controller absorbs the downwash, and that path breaks precisely when robots get close, which is when coordination matters most. By folding the force into the search as a hard constraint, and by showing that a learned force model beats a conservative bubble exactly in the tight spaces where you cannot afford to spread robots out, the authors make a case that interaction awareness is not a luxury but a requirement for close proximity flight.

The ideas carry beyond drones. The same three layer recipe, discontinuity bounded search feeding a joint optimizer, applies to any team of robots with mixed dynamics, ground vehicles with trailers, manipulators sharing a workspace, or mixed air and ground fleets like the ones the authors fly in their own experiments. Because the framework is agnostic to the specific dynamics and collision shapes, adding a new robot type is a matter of supplying its motion primitives rather than rewriting the planner.

The limitations mark the frontier rather than undercut the result. The joint optimization scales cubically in the dynamics dimension and dominates the runtime for large teams, the motion primitives depend on the environment, and the learned interaction model inherits the blind spots of its training data. The authors point toward generative, environment conditioned primitives and a meta optimization that groups robots over short intervals as the routes past these walls.

What lingers is a shift in what counts as the plan. For a long time the plan was a set of paths and the physics was someone else’s problem. This work insists that the momentum of each robot and the air between them belong in the plan itself. Fold them in and a crowd of robots can thread a single window without a collision. Leave them out and the plan was never really flyable to begin with.

Frequently asked questions