PaperlayerView exact revision on arXiv

Source-linked AI summary

Dispersive Tree Agreements for Multi-Robot Coordination

Shashank A. Deshpande, Blake T. Edwards, Jonathan P. How

arXiv:2610.31540v1cs.ROcs.MAmath.OC

TL;DR

Existing decentralized real-time planners often do not pursue the joint optimum, while joint-optimal approaches are largely centralized and offline. WarpWeaver coordinates dispersive tree searches through decentralized column generation, and its evaluations report travel-time and connectivity gains alongside onboard operation on six robots.

  • Problem

    Existing decentralized real-time coordination can settle in local optima without pursuing the joint optimum, while approaches that pursue it are largely centralized and offline.

    Source: §I · p. 1

  • Method

    WarpWeaver uses decentralized column generation to guide locally grown dispersive trees toward a near-optimal agreement, with a quiescence certificate.

    Source: §I · p. 2

  • Results

    Travel time falls by up to 22% against centralized offline planners on Dynobench and by up to 37% against a decentralized real-time baseline; graph-connectivity success nearly doubles against a task-specific planner.

    Source: §I · p. 2

  • Takeaways & Limitations

    WarpWeaver runs asynchronously over a receding horizon onboard each robot, and deadline-limited agreements come close in cost to quiesced agreements.

    Source: §I · p. 2

    Tasks with tightly coupled constraints, such as rigid formation maintenance, may yield few joint solutions among individual trees and weak relaxations.

    Source: §VIII · p. 14

Abstract

from arXiv · show

Multi-robot coordination of nonlinear systems is naturally formulated as joint-space optimal control subject to constraints over groups of robots. Existing methods that approach joint optimality remain largely centralized, offline, and confined to collision-free motion planning, while decentralized, real-time counterparts target safe navigation without pursuing the joint optimum. This paper develops a decentralized, real-time planner that approaches the joint optimum as an anytime process. We extend a recent single-robot framework that searches dispersive trees of forward-propagated commands for differentially flat systems to coordinate a multi-robot team near-optimally. We first show that the inter-robot coupling can be effectively replaced by some local constraints, under which locally grown dispersive trees contain a near-optimal agreement. It is this structure that the robots pursue by decentralized column generation, negotiating rents on the shared space that guide the search of each robot's tree. The negotiation settles on an agreement whose near-optimality is certified at quiescence. Our protocol, WarpWeaver, implements this negotiation as an asynchronous real-time loop over a receding horizon, and demonstrates effective closure to quiesced agreements even when real-time deadlines cut the negotiation short. In simulation, WarpWeaver reduces total travel time by up to 22% against centralized offline planners on the Dynobench suite and by up to 37% against a decentralized real-time baseline, and nearly doubles the success rate of a task-specific planner on graph connectivity. Hardware experiments on six robots planning onboard demonstrate real-world implementability.

I. INTRODUCTION

The paper targets real-time decentralized coordination of differentially flat robots without giving up the joint optimum. It combines dispersive forward search with column generation, against a background of centralized offline and decentralized real-time approaches with different limitations.

A. Sampling and Search for Multi-Robot Motion Planning

  • Centralized methods use high-level conflict handling, composite-space sampling, or motion-primitive search, with completeness or optimality guarantees, but focus on pairwise separation.The approaches described include multi-agent path finding and composite configuration-space sampling.Source: §I · p. 1

B. Trajectory Optimization for Multi-Robot Motion Planning

  • Decentralized trajectory optimization replans safe trajectories around peers’ incumbents, while consensus methods penalize disagreement; both can settle in local optima without pursuing the joint optimum.These approaches are described in and, respectively.Source: §I · p. 1

I. INTRODUCTION

  • Dispersive forward trees [17] provide locally grown candidate trajectories; decentralized column generation uses shared-space rents to guide their search toward a near-optimal agreement certified at quiescence.WarpWeaver runs this negotiation asynchronously over a receding horizon, and deadline-limited agreements come close in cost to quiesced ones.Source: §I · p. 2
  • Up to 22% lower total travel time against centralized offline planners on Dynobench and up to 37% against a decentralized real-time baseline; graph-connectivity success nearly doubles against a task-specific planner.The planner was also deployed onboard six robots in real time.Source: §I · p. 2

C. Coordination Beyond Inter-Robot Separation

  • Coordination tasks such as network connectivity and tethering go beyond pairwise separation, and the paper represents them as hard constraints on joint-space dynamics.The paper demonstrates connectivity maintenance in simulation and tethering in hardware experiments.Source: C. Coordination Beyond Inter-Robot… · p. 3

D. Column Generation and Decentralized Pricing

  • Column generation creates linear-program variables on demand, with dual prices guiding new-column searches; prior multi-agent applications include routing and task assignment.The paper applies decentralized pricing to search locally grown dispersive trees under limited communication.Source: D. Column Generation and Decentralized… · p. 3

III. PROBLEM FORMULATION

  • The problem is joint optimal control over robot trajectories, with a joint cost and both individual and group-wise trajectory constraints.The cost is a monotone, convex, piecewise-linear aggregate of private agent-wise costs, and costs and predicates are structured over time windows.Source: §III · p. 3

A. Examples

The examples cast kinodynamic motion planning and connectivity maintenance as joint optimal control problems. Differential flatness then reformulates the systems in output-jet space while retaining the costs and constraints.

A. Examples

  • Kinodynamic planning includes free-space and terminal-rest constraints for each robot, pairwise body separation, and a summed travel cost.The separation margin subtracts the robots’ radii from the distance between their position components.Source: A. Examples · p. 4
  • Connectivity maintenance requires a connected communication graph without prescribing which links remain active; a spanning-tree margin captures that condition for the whole team.The connectivity predicate couples the team, allowing one link to break when the remaining links preserve connectivity.Source: A. Examples · p. 4

B. Flat Reformulation

  • Under differential flatness, state trajectories, costs, and predicates can be represented through output jets, and admissible output curves correspond to realizable state trajectories and controls.The flatness assumptions exclude the singular locus of the flatness maps; the output-space problem retains the structural assumptions on costs and predicates.Source: B. Flat Reformulation · pp. 4–5

IV. DISPERSIVE FORWARD TREES AND NEAR-OPTIMAL CONTROL

Dispersive forward tree search reduces the growth of command-sequence search while retaining a near-optimality guarantee. Its locally grown trees support a decentralized anytime approach to the joint solution.

IV. DISPERSIVE FORWARD TREES AND NEAR-OPTIMAL CONTROL

  • A dispersive tree retains one best-running-cost representative per occupied spatiotemporal cell, pruning duplicate search states.The tree is generated by depthwise de-duplication from the root.Source: §IV · p. 5
  • Tree growth takes O(|A| T d+1(M/s)|R|) forward computation rather than O(|A|T ) for the complete tree, and is polynomial in horizon T.The cited guarantee concerns the single-agent dispersive-tree framework [17].Source: §IV · p. 5
  • With sufficiently small dispersion and pruning radius, a feasible control sequence has a corresponding retained tree sequence within a bounded near-optimality loss.The theorem conditions the bound on δA + s ≤ cB ε and a margin condition for the feasible solution.Source: §IV · p. 6
  • The joint-space product of robot command sets yields a near-optimal joint solution, while local trees grown against peer information support an anytime decentralized approach.The paper pursues this structure under limited communication over multiple rounds.Source: §IV · p. 6

V. DISPERSIVE TREE AGREEMENTS FOR NEAR-OPTIMAL COORDINATION

The section establishes that agent-local dispersive trees can contain a near-optimal agreement, then develops a decentralized negotiation to find one. The negotiation formulates agreement selection as an ILP and uses column generation, with a near-optimality guarantee at quiescence.

A. Overview

  • Agreement selection is restricted to an ILP over agents’ command-sequence sets at a chosen space-time resolution.The section presents this formulation as the basis for the subsequent column-generation scheme.Source: A. Overview · p. 6
  • At quiescence, column generation yields an agreement near-optimal relative to JOCP solutions robust at the search resolution, up to an online-computed gap.The search alternates between solving a restricted linear relaxation and decentralized generation of improving columns.Source: A. Overview · p. 6

B. Existence of Near-Optimal Agreements

  • A feasible joint solution can be represented by an agreement in the product of agent-local dispersive trees after enlarging predicates to solution-dependent corridors.These individual predicates replace joint predicates and allow agents to search independently; the existence result bounds the loss by LΦρ.Source: B. Existence of Near-Optimal Agreements · p. 6

C. Discretized Restriction of the Agreement Problem

The agreement problem is discretized into a finite ILP, then handled through decentralized column generation whose locally priced searches can certify pool sufficiency at quiescence.

C. Discretized Restriction of the Agreement Problem

  • The discretized ILP represents each agent’s command sequence and excludes joint selections that occupy forbidden cell tuples.It partitions jet space into cells and the horizon into substeps; joint predicates are enforced through occupancy constraints.Source: C. Discretized Restriction of the… · p. 7
  • The discretization tightens joint predicates by at most γS := LG (S + 2Mh).The stated bound depends on cell size S and substep length h.Source: C. Discretized Restriction of the… · p. 7

D. Decentralized Column Generation

  • The full ILP has too many command-sequence variables to enumerate, so column generation solves a restricted pool and adds improving sequences under dual prices.The restricted master’s dual prices guide agents’ searches for new columns.Source: D. Decentralized Column Generation · p. 7
  • The ILP’s separable structure lets agents price and search their own sequences locally, interacting through the aggregator and joint predicates.Each agent solves a local problem on its onboard computer.Source: D. Decentralized Column Generation · p. 7
  • If every agent’s best priced sequence has nonnegative reduced cost, the pool is certified within LΦ ρ of the robust JOCP solutions at search resolution ρ.A negative reduced-cost sequence instead enlarges the pool.Source: D. Decentralized Column Generation · p. 9

E. Protocol and Real-Time Implementation

WarpWeaver runs decentralized column generation as an asynchronous, receding-horizon negotiation, with agents committing to a common endorsed solution at each pick time.

E. Protocol and Real-Time Implementation

  • Each agent runs the same onboard loop, broadcasting generated columns and endorsing joint solutions from the shared pool.The best globally endorsed solution is the one with least cost, with ties broken by a common rule.Source: E. Protocol and Real-Time Implementation · p. 9
  • At pick time, agents commit to the best globally endorsed solution, even if the negotiation has not reached quiescence.Agents stop sending messages δcomm before the pick time to allow commitment before the next committed windows begin.Source: E. Protocol and Real-Time Implementation · p. 9
  • A quiescent iteration requires a shared pool, nonnegative best reduced costs under the common optimal dual, and endorsement of a common solution.Under the stated assumptions, all agents commit to the same solution; its cost receives the near-optimality certificate only if the iteration is quiescent.Source: E. Protocol and Real-Time Implementation · pp. 9–10

Therefore, the cost of the solution committed at quiescence

At quiescence, the committed solution’s cost is bounded relative to the ρ-robust optimum by its excess over the restricted master, plus the resolution loss.

Therefore, the cost of the solution committed at quiescence

  • The committed solution exceeds the ρ-robust optimum by no more than its restricted-master excess Γn, plus the resolution loss LΦ ρ.This certificate applies when the iteration is quiescent and its pool is shared before the communication cutoff.Source: Therefore, the cost of the solution… · p. 10
  • Recursive-feasibility enforcement is specific to the JOCP; if recursive feasibility is lost, computational speed becomes essential for completeness.A globally endorsed solution must be found before the commit is due.Source: Therefore, the cost of the solution… · p. 10
  • Γn ≤ 0 in all 1,502 quiescent simulation iterations, leaving only the resolution-loss term in the certificate.The reported iterations are those in Tables II to IV and VI.Source: Therefore, the cost of the solution… · p. 10

VI. SIMULATION EXPERIMENTS AND BENCHMARKS

WarpWeaver is evaluated on multi-robot kinodynamic planning benchmarks and scaling tests, with comparisons to offline and decentralized real-time planners. The results report lower travel time on Dynobench, EGO-Swarm, and scaled unicycle tests.

A. Multi-Robot Kinodynamic Motion Planning

  • The benchmarks measure median total travel time summed over agents, comparing WarpWeaver with centralized offline planners on the unicycle and 3D double-integrator platforms and with EGO-Swarm on ten-drone forest maps.The comparisons use five trials per instance; the EGO-Swarm evaluation includes triple-integrator and X500 platforms.Source: A. Multi-Robot Kinodynamic Motion… · p. 12, Table II · p. 12, Table III · p. 12
  • On Dynobench, WarpWeaver completes every trial and has the lowest total travel time on 10 of 11 instances, improving on the best baseline by 8% at the median and up to 22%.Against EGO-Swarm, it succeeds in all 15 trials on both platforms, versus 12 for EGO-Swarm, and reduces travel time by 36–37% with triple integrators and 31–33% with X500s.Source: A. Multi-Robot Kinodynamic Motion… · p. 12, Table II · p. 12, Table III · p. 12
  • The study also emulates asynchronous real-time scaling tests in a 20 × 20 m arena, increasing the number of randomly initialized unicycles from 10 to 50.Each robot uses a virtual clock based on its measured computation time and its own share of GPU and CPU resources.Source: A. Multi-Robot Kinodynamic Motion… · pp. 12–13, Table IV · p. 13
  • Across N = 10–50 unicycles, WarpWeaver completes all 25 trials without collision and has 17–35% lower total travel time than db-LaCAM at every team size.Travel time per robot rises from 16.8 s at N = 10 to about 22 s at N = 20, then stays flat through N = 50.Source: A. Multi-Robot Kinodynamic Motion… · p. 13, Table IV · p. 13

B. Connectivity Maintenance

The experiments evaluate team-wide connectivity maintenance, the effect of real-time cutoffs, and onboard planning with six physical robots. WarpWeaver completes more connectivity tasks than Realm, stays close to quiesced solutions under deadlines, and succeeds in the reported robot trials.

B. Connectivity Maintenance

  • WarpWeaver completes all 15 connectivity tasks against eight for Realm, which solves none in the forest, and brings the last robot to its target 59% sooner in the clutter world and 29% sooner in the garage at the median.Both planners keep the team connected throughout; robots that reach their targets relay for the others without a dedicated mechanism.Source: B. Connectivity Maintenance · p. 13, Table V · p. 13

C. The Cost of a Real-Time Cutoff

  • Under real-time cutoffs, WarpWeaver’s median total travel time matches the quiesced result on seven of 11 Dynobench instances and exceeds it by at most 1.2% on all but swap4.In scaling tests, it is within 0.3% of εq-quiesced agreements through N = 30 and within 1.3% and 6% at N = 40 and 50, respectively, compared with agreements after five seconds of negotiation.Source: C. The Cost of a Real-Time Cutoff · p. 13, Table VI · p. 14

VII. REAL-ROBOT EXPERIMENTS

  • The six-robot deployment uses onboard Jetson Orin computers, Wi-Fi messaging through ROS 2, Vicon positions, and a hand-entered obstacle map across swap, tethered-swap, and doorway-swap tasks.The real-time protocol commits the same agreement at 311 of 312 picks; the exception follows a robot restart after a battery swap.Source: §VII · p. 14, Figure 5 · p. 15
  • In real-robot trials, every robot reaches its goal without contact with robots or obstacles, tied pairs remain within range and line of sight, and trajectories track committed plans within 0.03–0.07 m on average.The tether distance reaches at most 2.37 m against a 2.4 m limit.Source: §VII · p. 14, Table VII · p. 14

VIII. CONCLUSION

  • A coordination task is only as tractable as its integer linear restriction; tightly coupled constraints such as rigid formation can leave few joint solutions in the individual trees and yield weak relaxations.The paper identifies incorporating differential information about constraint geometry into dispersive search as future work.Source: §VIII · p. 14

APPENDIX A PROOFS

The proofs establish that local dispersive trees can represent a near-optimal joint agreement and that the integer linear restriction encodes agreements soundly, up to discretization margins.

A. Proof of Proposition 1

  • Individual predicates keep each agent’s rollout within ρ of its reference, allowing the proof to transfer the reference’s joint-predicate margins to the locally grown tree sequences and establish an agreement.The cost loss is bounded by LΦρ relative to the solutions with the specified margins.Source: A. Proof of Proposition 1 · pp. 15–16

B. Proof of Proposition 2

  • The integer-program constraints make each feasible binary solution select exactly one locally feasible sequence per agent, while occupancy rows exclude forbidden tuples and ensure the selected rollouts satisfy joint predicates.Conversely, sufficiently smooth rollouts satisfying joint predicates with a discretization margin produce a feasible integer-program solution.Source: B. Proof of Proposition 2 · p. 16

C. Proof of Proposition 3

The proofs relate the restricted master problem to the full column set and extend dispersive-tree tracking guarantees to priced costs that include rents on shared space.

C. Proof of Proposition 3

  • For the restricted column pool, the linear-program value is bounded by the full-column relaxation, while dual optimality and zero pricing gaps make the bounds coincide.The argument uses feasibility and the rent constraints to bound the total rents and weighted costs.Source: C. Proof of Proposition 3 · pp. 16–17

D. Proof of Proposition 4

  • The pricing-tree proof extends single-agent dispersive tracking to rents that are not Lipschitz in the window trajectory by bounding each window’s rent through its reference occupancy.Dispersion and a margin-correcting control retain a feasible sequence that tracks the reference, while the occupancy bound controls its rent.Source: D. Proof of Proposition 4 · p. 17

E. Proof of Theorem 2

The proof bounds the summed per-agent quantity using the joint objective, an inflation term, and dual variables. It establishes that forbidden tuples cannot lie in the reference trajectories’ inflated occupancies.

E. Proof of Theorem 2

  • The summed per-agent bound is at most Φ(jet z1, . . . , jet zN) + LΦ ρ + b⊤µ − 1⊤π.The proof obtains this by summing (46) and applying (48) and (49).Source: E. Proof of Theorem 2 · p. 18
  • No forbidden tuple lies in the ρ-inflated occupancies of the reference trajectories, because joint margins and smoothness contradict the forbidden-tuple condition.The proof uses the Lipschitz property of ht in the maximum metric to complete the contradiction.Source: E. Proof of Theorem 2 · p. 18
  • When the dual solution is optimal, strong duality gives 1⊤π − b⊤µ = DP(Q) = LP(Q), supporting the claims in part (ii).The remaining implication in part (ii) uses ˆJi ≥ 0 for every agent.Source: E. Proof of Theorem 2 · p. 18

F. Proof of Proposition 5

The proof follows iteration n of Algorithm 1 to establish agreement consistency and the quiescence certificate. At quiescence, agents share a pool whose joint solutions provide the cost comparison used for the certificate.

F. Proof of Proposition 5

  • The proof applies iteration n of Algorithm 1 line by line, then uses DP(Q) = LP(Q) and Theorem 2(ii) to derive the certificate by subtracting from Φ(cn).The argument assumes DP(Q) has an optimal solution.Source: F. Proof of Proposition 5 · p. 18
  • All agents hold the same nonempty set of globally endorsed solutions at time tn and pick the same best solution, which is an agreement.Initialization supplies the initial agreement; published solutions satisfy all predicates, and ties use a common rule.Source: F. Proof of Proposition 5 · p. 18
  • At quiescence, no agent broadcasts a column, and every globally endorsed solution uses columns in Q and costs at least JCP(Q).Each agent publishes a JCP(Q) solution before the communication cutoff, and all agents endorse it.Source: F. Proof of Proposition 5 · p. 18

Related papers

Loading 2610.31540v1…