Source-linked AI summary
GAMBIT: Learning to Plan Continuous Multi-Robot Trajectories
Rishabh Jain, Akmaral Moldagalieva, Lorenzo Magnino, Michael Amir, Keisuke Okumura, Ajay Shankar, Wolfgang Hönig, Amanda Prorok
TL;DR
Continuous multi-robot planning requires coordination-aware heuristics, since dense interactions can make locally attractive motions ineffective. GAMBIT learns motion-primitive selection through imitation pretraining and RL fine-tuning, using safeguarded rollouts with backup trajectories. It reports strong performance across tested scenarios and collision-free execution, including at scale.
Problem
In dense continuous multi-robot settings, interaction-aware heuristics are difficult to design manually, while expert data, multi-modal solutions, and effective safeguards complicate learning.
Source: §I · p. 1Method
GAMBIT uses a GNN policy pretrained by imitation learning and fine-tuned by multi-agent reinforcement learning, with a safeguarded rollout that switches to backup trajectories when needed.
Source: §I · p. 1, 1) Safe Execution with Static Obstacles · p. 4Results
GAMBIT achieves the strongest overall performance among evaluated methods across tested scenarios, with the safeguarded rollout preventing collision-caused failures.
Source: B. Main Results · pp. 7–8Takeaways & Limitations
The authors present GAMBIT as a toolkit for building more capable multi-robot planners, with learned motion-primitive heuristics as a modular component.
Source: §I · p. 2, §V · p. 8The framework is presented for double-integrator dynamics, with extension to more general dynamics identified as future work.
Source: §V · p. 8
Abstract
from arXiv · showhide
GAMBIT is an opening chess move in which a player sacrifices a piece, typically a pawn, to gain a positional advantage later in the game. Analogously, in multi-robot coordination, individual robots may need to forgo locally reward-maximising behaviours to improve overall team performance. Such self-sacrificial behaviours are difficult to capture with manually designed heuristics, particularly in dense, interaction-rich environments. Focusing on double-integrator continuous dynamics, this work studies how to learn such coordinated heuristics over motion primitives for multi-robot trajectory execution. Our framework, GAMBIT, first learns coordinated motion-primitive selection through imitation learning and subsequently fine-tunes the policy through reinforcement learning. We further introduce a safeguarded rollout mechanism with backup trajectories that guarantees collision-free execution at all times. Experiments demonstrate that GAMBIT substantially outperforms a range of baselines, including centralised motion planners and decentralised reactive planners, while exhibiting strong scalability. In particular, it coordinates over a thousand robots with planning latency below a few hundred milliseconds in continuous domains.
I. INTRODUCTION
Continuous multi-robot planning needs heuristics that account for coordination, because interaction-heavy settings may require robots to move non-greedily. GAMBIT learns motion-primitive preferences and combines them with safeguarded rollouts for scalable, collision-free execution.
I. INTRODUCTION
- In interaction-rich settings, interaction-agnostic heuristics can misjudge motion primitives, while effective coordination may require temporarily moving away from the goal.Manually capturing such coordination takes substantial engineering effort that scales poorly with interaction complexity.Source: §I · p. 1
- GAMBIT uses a GNN policy pretrained by imitation learning on small instances and then fine-tuned with multi-agent reinforcement learning.The framework learns primitive selection from demonstrations as a classification task and uses a safeguarded rollout during RL.Source: §I · pp. 1–2
- GAMBIT produces better-coordinated trajectories in dense environments than reactive, centralised, and learning-based alternatives, with sub-hundredmillisecond latency for hundreds of robots.The backup mechanism guarantees safe and feasible execution across simulated and real-robot deployments.Source: §I · p. 2
- Because rollout relies on local robot interactions, GAMBIT is amenable to decentralised deployment and is presented as a modular building block for future planners.The authors also report physical deployment with closed-loop control on eight multirotors.Source: §I · p. 2
II. PRELIMINARIES AND RELATED WORK
The paper formulates point-to-point navigation for homogeneous spherical robots under double-integrator dynamics. It seeks collision-free trajectories from each robot’s start to goal and assesses solution quality by total travel time.
A. Problem Formulation
- Robots are modelled by position and velocity states, with acceleration controls and exact discrete-time double-integrator dynamics under constant acceleration per timestep.The workspace may be two- or three-dimensional and contain obstacles.Source: A. Problem Formulation · p. 2
- Each robot must follow a kinodynamically consistent trajectory from its start to its goal without colliding with obstacles or other robots.The terminal state must lie within the goal radius and satisfy a small velocity threshold.Source: A. Problem Formulation · p. 2
- Solution quality is measured by sum-of-costs: the total travel time across robots until each reaches its goal and remains there indefinitely.Source: A. Problem Formulation · p. 2
B. Planning with Motion Primitives
The paper learns to rank a finite set of motion primitives rather than directly outputting continuous controls, making the heuristic compatible with global search-based planning. It draws on neural MAPF policies while addressing the challenges of continuous multi-robot settings.
B. Planning with Motion Primitives
- Motion primitives restrict infinitely many possible controls to a finite set, and GAMBIT learns to rank these choices as a heuristic compatible with global search-based planners.The safeguarded rollout scheme is tailored to double-integrator dynamics.Source: B. Planning with Motion Primitives · p. 3
- In the experiments’ simple setting, each primitive is a single acceleration command, while the framework can extend to primitives containing longer control sequences.The ranking depends on the current multi-robot configuration.Source: B. Planning with Motion Primitives · p. 3
- The multi-robot setting adds interaction challenges to motion-primitive learning beyond those in single-robot settings.Source: B. Planning with Motion Primitives · p. 3
C. Neural MAPF Policies
- Neural MAPF policies provide a precedent for learning action distributions from local observations with imitation or reinforcement learning, but their grid-world actions use simplified discrete dynamics.GAMBIT aims to adapt these insights to continuous dynamics.Source: C. Neural MAPF Policies · p. 3
III. GAMBIT PIPELINE
GAMBIT combines a GNN-based policy, imitation pretraining, reinforcement-learning fine-tuning, and a safety-preserving rollout. Its architecture encodes robot observations, exchanges information between nearby robots, and outputs a distribution over motion primitives.
III. GAMBIT PIPELINE
- GAMBIT’s pipeline combines a GNN policy with imitation pretraining, RL fine-tuning, and a safety-preserving rollout scheme.Source: §III · p. 3
A. Policy Architecture
- Geometric locality lets the GNN policy learn interactions from small-robot instances and deploy to substantially larger teams at test time.The policy comprises an encoder, interaction-processing GNN layers, and a decoder over motion primitives.Source: A. Policy Architecture · p. 3
2) Interaction Modelling and Decoding:
- Each robot’s observation combines velocity, relative goal, a field-of-view representation, and an embedding of available motion-primitive outcomes.The field of view encodes obstacle and agent occupancy plus goal location; nearby robots are linked in a communication graph for GNN message passing, and the decoder outputs a primitive distribution.Source: 1) Observation Encoding · p. 3, 2) Interaction Modelling and Decoding · p. 3
B. Pretraining by Imitation Learning
GAMBIT pretrains motion-primitive selection on small expert-planned instances, then fine-tunes with reinforcement learning to address suboptimal demonstrations and improve solution quality. Its reward encourages team completion and lower sum-of-costs while leaving collision handling to the safeguarded rollout.
B. Pretraining by Imitation Learning
- Imitation learning uses small instances with four agents, since collecting large-team demonstrations is computationally expensive; GNN locality supports generalisation to larger teams.The expert data comes from an adapted db-LaCAM planner.Source: B. Pretraining by Imitation Learning · p. 3
- Motion-primitive selection is trained as classification: the closest primitive to each continuous expert action is the target, with cross-entropy loss.This formulation was observed to learn more stably than continuous-action regression followed by quantisation, and supplies a categorical distribution for safeguarded rollout.Source: B. Pretraining by Imitation Learning · p. 4
C. Fine-tuning by Reinforcement Learning
- RL fine-tuning addresses suboptimal behaviours inherited from computationally constrained expert demonstrations; training from scratch is unstable, whereas IL–RL training is stable.The policy can directly optimise solution quality during fine-tuning.Source: C. Fine-tuning by Reinforcement Learning · p. 4
- MAPPO fine-tuning uses the IL instance distribution and a reward focused on sum-of-costs, with an additional reward for all robots reaching their goals.The reward gives a team-level completion bonus and penalises each robot that has not reached its goal at each timestep.Source: C. Fine-tuning by Reinforcement Learning · p. 4
- The reward omits collision penalties because they can dilute goal-directed learning; collision prevention is handled algorithmically by a specialised rollout scheme.The rollout is designed for double-integrator dynamics.Source: C. Fine-tuning by Reinforcement Learning · p. 4
D. Safeguarded Rollout with Backup Trajectories
The rollout uses stopping trajectories to filter motion primitives against static obstacles. If no safe primitive is available at a later step, the robot follows its retained backup trajectory, preserving collision-free motion.
1) Safe Execution with Static Obstacles:
- For a state and motion primitive, the stopping trajectory applies the primitive, then maximum acceleration opposite the velocity until the robot stops.Primitives whose stopping trajectories collide with obstacles are filtered out.Source: 1) Safe Execution with Static Obstacles · p. 4
- Any selected primitive from the safe set has an available collision-free trajectory that brings the robot to a complete stop.The safe set contains only primitives whose associated stopping trajectories avoid obstacles.Source: 1) Safe Execution with Static Obstacles · p. 4
- If the safe set becomes empty, the robot continues the remaining portion of its previous stopping trajectory as a backup, avoiding dead-end states.The backup is guaranteed to bring the robot to a stop without collision; the resulting scheme guarantees collision-free motion with respect to obstacles.Source: 1) Safe Execution with Static Obstacles · p. 4
2) Safe Execution with Other Robots:
For multi-robot execution, the rollout combines backup trajectories with PIBT collision shielding. It checks stopping trajectories, falls back to backups when needed, and guarantees collision-free trajectories over time when the algorithm is invoked repeatedly.
2) Safe Execution with Other Robots:
- Backups play the role of a safe fallback analogous to a grid-world stay action, which may be unavailable in kinodynamic settings with non-zero velocity.The paper states that backups provide both collision-free safety and a feasible action assignment in finite time.Source: 2) Safe Execution with Other Robots · p. 5
- The algorithm finds a safe action assignment in finite time with collision-free subsequent stopping trajectories, provided input backups are jointly collision-free.Repeated invocation with those retained backups keeps multi-robot trajectories collision-free for all time.Source: 2) Safe Execution with Other Robots · p. 5
- PIBT assigns each robot an action only when its stopping trajectory avoids already assigned robots; conflicts with unassigned robots’ backups trigger recursive replanning.If recursion cannot assign a safe primitive, the involved robots use their input backup trajectories, which are assumed collision-free.Source: 2) Safe Execution with Other Robots · p. 5
3) Auxiliary Reward for RL:
An auxiliary RL reward penalises PIBT overrides so the policy is encouraged to produce coordinated actions itself. The implementation specifies motion-primitive and training settings, while Fig. 2 describes the metrics used to compare planners.
3) Auxiliary Reward for RL:
- The auxiliary reward penalises policy actions overridden by PIBT collision shielding, encouraging consistency between policy choices and shielded actions.The paper motivates this term by noting that shielding interventions can weaken the learning signal for the policy to synthesise coordinated actions.Source: 3) Auxiliary Reward for RL · p. 5
E. Implementation Details
- The 2D setup uses 9 motion primitives and the 3D setup uses 27, each combining directional accelerations with zero acceleration.Maximum acceleration is 2 m s−2 in 2D and 5 m s−2 in 3D; robot radius is 0.25 m, communication radius 3 m, and timestep 0.1 s.Source: E. Implementation Details · p. 5
- Imitation learning uses 60K four-agent demonstrations, and training requires approximately 40 GPU hours for IL plus 25 GPU hours for RL.Data collection takes approximately 22 wall-clock hours with 24 parallel runs; the policy has approximately 1.4M trainable parameters.Source: E. Implementation Details · pp. 5–6
- Fig. 2 plots complete success rate, normalised sum-of-costs, and computation time for each scenario; sum-of-costs and time are reported only when success exceeds 50%.Those two metrics are averaged over successful instances, with shaded regions indicating one standard deviation.Source: Figure 2 · p. 6
IV. EXPERIMENTS
The experiments test GAMBIT on held-out instances spanning multiple scenarios and compare it with planners and ablations representing different planning paradigms and technical components.
1) Instances:
- 32 test instances vary from 4 to 32 robots and include in-distribution scenarios plus out-of-distribution Conveyor cases.The test instances are distinct from those used during training.Source: 1) Instances · p. 6
2) Baselines:
- Baselines include reactive collision avoidance, centralised full-horizon planners, and learning-based planning, with evaluation constrained by method-specific scenario support.RVO is evaluated only in 2D obstacle-free scenarios, EGO-Swarm only in 3D, and MMD-XECBS only on Empty and Conveyor; all planners receive a one-minute limit.Source: 2) Baselines · p. 6
- Ablations remove imitation learning, reinforcement-learning fine-tuning, safeguarding, or all learning to assess their respective contributions.The no-learning variant uses a manually designed greedy heuristic, while the no-safeguard variant directly samples and executes a motion primitive with a collision-penalising reward.Source: 2) Baselines · pp. 6–7
- Figure 3 assesses scalability in Forest with up to 1,024 robots, showing workspace and local trajectories, ISR over time, and team inference-time distributions.ISR curves represent 32 instances; the inference-time panel reports the median and corresponding loop frequency.Source: Figure 3 · p. 7
3) Metrics:
GAMBIT achieves strong success rates across tested scenarios while maintaining competitive solution quality and moderate computation time. Its safeguarding, learned components, and offline coordination address limitations of alternatives, though livelocks remain a source of failures.
3) Metrics:
- CSR measures the fraction of instances where all agents reach goals, SOC assesses trajectory quality, and Time measures wall-clock time for complete trajectories.ISR measures the fraction of agents reaching their goals within each instance.Source: 3) Metrics · p. 7
B. Main Results
- GAMBIT delivers the strongest overall performance among evaluated methods, with high success rates across in- and out-of-distribution scenarios and competitive solution quality.With 32 robots, it requires about 1 s to derive feasible trajectories.Source: B. Main Results · p. 7
- Both imitation learning and reinforcement learning substantially improve success rates, while the safeguarded rollout is critical to strong performance.The authors conjecture safeguarding simplifies learning by relieving the policy of collision avoidance, allowing focus on goal-directed coordination.Source: B. Main Results · p. 7
- Reactive collision-avoidance planners struggle in dense, interaction-heavy settings, while MMD-XECBS achieves superior planning performance at high computational cost.GAMBIT remains reactive at execution while incorporating long-horizon reasoning through offline learning.Source: B. Main Results · p. 7
- Some failures are livelocks near obstacles, but none of the observed failures are caused by collisions.Livelocks include repeated actions without progress, such as difficulty passing narrow gaps or navigating around obstacles.Source: B. Main Results · pp. 7–8
- Figure 4 depicts an eight-multirotor deployment planned at 10 Hz, with a speed profile and a top-down view of the arena and trajectories.Source: Figure 4 · p. 8
C. Scalability Assessment
GAMBIT scales to teams of up to 1,024 robots and retains real-time responsiveness at scale. The paper also reports collision-free closed-loop multirotor deployment and identifies extension beyond double-integrator dynamics as a promising direction.
C. Scalability Assessment
- At 1,024 robots, GAMBIT maintains high individual success rates in dense Forest settings; at 512 robots, it synthesises safe coordinated actions in under 100 ms per step.No baseline successfully solves the enlarged-workspace instances; the greedy non-learning variant leaves some robots unsuccessful.Source: C. Scalability Assessment · p. 8
D. Multirotor Deployment
- Eight multirotors swapped start–goal locations among obstacles with collision-free closed-loop execution at 10 Hz and peak speed 2.2 m/s.Source: D. Multirotor Deployment · p. 8
V. CONCLUSION
- The authors present GAMBIT as a toolkit for capable multi-robot planners and identify dynamics beyond the double-integrator model as a promising extension.Source: §V · p. 8