The Big Picture
A decentralized negotiation method lets each robot plan locally and jointly pick a near-optimal team plan in real time, reducing total travel time up to 37% versus strong baselines while tolerating message delays.
ON THIS PAGE
The Evidence
Robots can each grow a compact set of locally feasible trajectories and negotiate a single-team plan by trading lightweight prices (dual rents) over the shared constraints. That decentralized column-generation style negotiation—implemented as WarpWeaver—finds agreements near the joint optimum and works asynchronously on each robot with bounded message delays. In simulation WarpWeaver cut total travel time by up to 37% (and up to 22% vs centralized offline planners) and doubled success on a connectivity task; it also ran onboard six real robots with low message latency and tight tracking.
Data Highlights
1Up to 37% reduction in total travel time versus a decentralized real-time baseline (EGO-Swarm); up to 22% reduction versus centralized offline planners on Dynobench.
2Nearly 2× success rate on a graph connectivity task compared with a task-specific planner; WarpWeaver completed all tested trials where the baseline sometimes failed.
3Real-robot demo: six robots planning onboard; median message round-trip 13 ms, 99th percentile 106 ms, same agreement in 311 of 312 picks, and executed trajectories tracked plans to within 0.03–0.07 m on average.
What This Means
Robotics engineers who need teams of robots to coordinate in real time will get a practical method that runs onboard and is robust to typical Wi‑Fi delays. Technical leaders evaluating multi-robot systems can use it to reduce overall mission time and improve success rates without a centralized planner. Researchers can adopt the decentralized column-generation pattern to balance local computation and limited communication for near-optimal team decisions.
Not sure where to start?Get personalized recommendations
Key Figures
![Fig. 1: (a) Iterated Best Response, F = 7.5 + 10.0 = 17.5 F={\color[rgb]{0.168,0.4297,0.5508}7.5}\;{+}\;{\color[rgb]{0.707,0.3125,0.1719}10.0}=17.5 s, vs. (b) Dispersive Tree Agreement, F = 8.0 + 5.5 = 13.5 F={\color[rgb]{0.168,0.4297,0.5508}8.0}\;{+}\;{\color[rgb]{0.707,0.3125,0.1719}5.5}=13.5 s, where the total travel time F F sums the arrival times of the blue and red robots.](https://arxiv.org/html/2610.31540v1/2610.31540v1/teaser.png)
Fig 1: Fig. 1: (a) Iterated Best Response, F = 7.5 + 10.0 = 17.5 F={\color[rgb]{0.168,0.4297,0.5508}7.5}\;{+}\;{\color[rgb]{0.707,0.3125,0.1719}10.0}=17.5 s, vs. (b) Dispersive Tree Agreement, F = 8.0 + 5.5 = 13.5 F={\color[rgb]{0.168,0.4297,0.5508}8.0}\;{+}\;{\color[rgb]{0.707,0.3125,0.1719}5.5}=13.5 s, where the total travel time F F sums the arrival times of the blue and red robots.

Fig 4: Fig. 4: WarpWeaver in simulation. (a) Circle-10, unicycles. (b) Forest-10, 3D double integrators. (c) Ten triple integrators on a forest map of EGO-Swarm. (d) Connectivity maintenance in the forest world of Realm, with the live links at three instants. In (a) and (d), each robot has its own colour and is drawn at three instants, later ones more opaque. In (b) and (c), trajectories and bodies are coloured by time from start (circle) to goal (star).

Fig 5: Fig. 5: Six robots, one take per task. Left: executed trajectories from motion capture, each robot in its own colour, with the robots at the start, midway, and at the last arrival, later instants more opaque. Right: the camera frames overlaid, later ones more opaque. (a) Swap around four pillars. (b) Tethered swap, with the tied pairs joined by dashed lines. (c) Doorway swap.
Ready to evaluate your AI agents?
Learn how ReputAgent helps teams build trustworthy AI through systematic evaluation.
Learn MoreLimitations
The method’s guarantees are “near-optimal” up to the spatial/time resolution of each robot’s search and an online-computed gap; finer resolutions cost more compute. Tasks that tightly bind many robots (for example a rigid formation) can produce weak integer-program relaxations and may favor continuous differential methods. Performance depends on the command-set and tree pruning choices, so tuning is needed to trade compute, communication, and solution quality for a specific platform and task.
Methodology & More
Treat the team as a joint optimal control problem but avoid building a huge centralized search. Each robot grows a compact, pruned tree of feasible, dynamically valid trajectories (a dispersive forward tree) so its local search is tractable. Coupling constraints between robots (collisions, connectivity, etc.) are replaced by local constraints plus shared prices: the team’s joint plan selection is cast as an integer linear program over each robot’s candidate sequences, and that program is solved by column generation. Under a price vector, each robot searches its own tree for improving candidate sequences and proposes them, so the heavy lifting is distributed and communication stays light.
WarpWeaver implements this as an asynchronous, anytime protocol that runs onboard each robot over a receding horizon and tolerates bounded message delays. When the negotiation quiets, the chosen joint plan is certified near-optimal relative to the search resolution. In benchmarks the method outperformed centralized offline planners on multi-robot motion problems (up to 22% better on Dynobench) and outpaced a decentralized baseline by up to 37% on drone tasks, while scaling well (stable per-robot times up to 50 robots). Real-robot tests with six unicycle robots running onboard achieved safe, accurate execution with low latency message exchange, demonstrating practical deployability. The main trade-offs are compute vs search resolution and weaker relaxations for tasks that tightly constrain many robots together.
Avoid common pitfallsLearn what failures to watch for
Credibility Assessment:
Authors have low reported h-indices and no affiliations listed; arXiv preprint with no citations — limited established signals.