💻 computer science

Diffusion for Long-Horizon Multi-Robot Path Planning in Human-Shared Environments

This paper introduces Multi-Robot Rolling Diffusion (MRRD), a novel framework that enables real-time, long-horizon path planning for large robot teams in crowded human-shared environments by combining rolling-horizon schemes, parallelized diffusion inference, and conflict resolution to significantly outperform existing baselines in safety and mission success.

Original authors: Vaibhav Sanjay, Yorai Shaoul, Jiaoyang Li

Published 2026-07-14

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Vaibhav Sanjay, Yorai Shaoul, Jiaoyang Li

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 a bustling city square where a team of 15 robot friends needs to cross from one side to the other, but the square is packed with real people walking around. The robots need to move together without bumping into each other or the humans, and they need to look natural while doing it. This is the challenge the paper tackles with a new system called Multi-Robot Rolling Diffusion (MRRD).

Think of the old way robots planned their paths like a rigid marching band. They would decide the entire route from start to finish before taking a single step, and they were forced to march at a speed that fit a pre-set song length, no matter how far they had to go. If the goal was far away, they'd have to sprint dangerously fast; if it was close, they'd have to shuffle awkwardly slow. The paper argues that this "fixed-time" approach is a major flaw because it leads to erratic, unsafe movements and fails when the crowd gets too thick.

MRRD changes the game by acting more like a group of friends walking through a busy market. Instead of planning the whole day's route at once, they take short, rolling steps. They look ahead just a few seconds (about 3.2 seconds in the simulation), decide where to go next, take a few steps (about 1.6 seconds), and then immediately look ahead again to adjust. This "rolling" approach lets them speed up or slow down naturally based on how far the goal is and how crowded the path is right now.

To make sure the 15 robots don't trip over each other, MRRD uses a clever "traffic cop" system called Conflict-Based Search. Imagine the robots are playing a game where they all try to draw their paths at the same time. If two robots try to occupy the same spot at the same time, the system pauses, draws a temporary "do not enter" bubble around that spot, and asks the robots to redraw their paths to avoid it. The paper shows that this method allows the robots to solve these conflicts in real-time, even with 15 of them on the screen.

The robots also learn to move like humans by studying a massive dataset of 20,000 real human walking paths. They use a "diffusion" model, which is like a creative artist who starts with a blurry, noisy sketch and slowly cleans it up until it looks like a perfect, smooth walk. The paper suggests that by adding a special "urgency" signal to this artist, the robots can learn to walk briskly when they are far from their goal and slow down when they are close, solving the "fixed-time" problem.

In the paper's simulations, MRRD proved to be a standout performer. When tested with up to 15 robots in empty spaces, MRRD achieved a 0.00 robot-robot collision rate, meaning the robots never bumped into each other in those specific scenarios. In contrast, other methods struggled, with collision rates reaching as high as 0.98 (almost every trial failing) for some competitors in similar tests. MRRD also kept robot-human collisions extremely low, at 0.08 in the 15-robot empty map test, while other methods saw rates as high as 1.00 in specific scenarios like the 12-robot empty map.

The system was also incredibly fast. In the most crowded test with 15 robots in an empty map, MRRD's total planning time (the sum of all the rolling steps) was just 8.8 seconds. This is about 7 times faster than the next best diffusion-based method, which took 60.2 seconds. The robots also moved much more smoothly, with acceleration profiles that were 5 to 8 times lower than the jerky movements of the other methods.

The paper concludes that while this method works brilliantly in these simulated environments, it is a specific solution for this type of problem. It suggests that future work could involve making the system even more robust by integrating human prediction directly into the drawing process, but for now, MRRD stands as a highly effective way to get large teams of robots moving safely and socially through human crowds.

Technical Summary: Multi-Robot Rolling Diffusion (MRRD)

Problem Definition

The paper addresses the challenge of multi-robot path planning in human-shared environments. The core objective is to coordinate a team of robots ( $N$ ) to navigate through a 2D workspace containing static obstacles, other robots, and dynamic humans ( $M$ ). The system must achieve three simultaneous goals:

Collision Avoidance: Prevent robot-robot, robot-human, and robot-obstacle collisions.
Social Awareness: Generate paths that are predictable and socially acceptable, mimicking human movement patterns rather than purely geometric shortest paths.
Scalability and Real-Time Performance: Operate efficiently for large robot teams (up to 15) in real-time, adapting to varying distances and crowd densities.

The authors identify a critical limitation in existing generative planners (e.g., CoBL-Diffusion): the "fixed-time problem." Traditional diffusion models generate paths with a rigid, fixed duration regardless of the distance to the goal. This forces erratic velocities (dangerously high for distant goals or unnaturally slow for nearby ones) and hinders adaptability in dynamic, long-horizon scenarios.

Methodology: Multi-Robot Rolling Diffusion (MRRD)

The proposed framework, MRRD, is a three-level architecture that integrates a rolling-horizon scheme, Conflict-Based Search (CBS), and a diffusion-based single-robot planner.

1. Rolling-Horizon Planning (Top Level)

Instead of generating a single, global path from start to finish, MRRD employs a rolling-horizon approach (Algorithm 1).

Iterative Process: The system plans short path segments of length $H$ (planning horizon) and executes only $K$ steps (execution horizon, where $K < H$ ).
Adaptability: After executing $K$ steps, the robot's new position becomes the start for the next iteration. This allows the planner to react to changing human predictions and robot positions continuously.
Human Prediction: The system utilizes a perfect prediction function for human paths over the horizon $H$ , avoiding the need for long-term human trajectory forecasting.

2. Multi-Robot Coordination (Middle Level)

To resolve robot-robot collisions within the rolling horizon, MRRD adapts Conflict-Based Search (CBS) (Algorithm 2).

Parallel Generation: Unlike sequential planners, MRRD generates initial path segments for all $N$ robots in parallel using the diffusion model.
Constraint Tree: If collisions are detected between robots, the algorithm splits the problem into child nodes. It imposes spherical constraints on specific robots at specific times and replans their paths to avoid these constrained regions.
Separation of Concerns: Robot-human interactions are handled by the diffusion model's learned priors, while robot-robot interactions are explicitly resolved via the CBS constraint tree.

3. Single-Robot Diffusion Planner (Bottom Level)

The core innovation lies in the diffusion model architecture and its conditioning mechanism (Fig. 1).

Urgency-Based Temporal Conditioning: To solve the "fixed-time problem," the model is conditioned on an urgency term ( $u_i$ $u_{i}$ ) representing the number of waypoints to the goal, rather than a fixed time duration.
- The model is trained on human walking data where the goal position and urgency are sampled to teach the model to adjust speed based on distance.
- During inference, the model generates a batch of paths with varying urgency values. The system selects the path that is feasible (no collisions) and has the highest speed (lowest $u_i$ ) appropriate for the current context.
Guidance Terms: The denoising process is guided by gradients of three cost functions:
1. Constraint Costs: Penalizing violations of CBS-imposed spherical constraints.
2. Human Distance Costs: Penalizing proximity to humans using a personal space model (core and close radii) with rank-weighted penalties for dense crowds.
3. Obstacle Costs: Penalizing penetration into static obstacles using Signed Distance Fields (SDF).
Architecture: A temporal U-Net processes the noisy path, goal embedding, and urgency embedding to iteratively denoise the path.

Key Contributions

MRRD Framework: A novel 3-level planner combining rolling-horizon execution, CBS-based collision resolution, and diffusion-based path generation.
Urgency Conditioning: A mechanism to condition diffusion models on "time-to-goal" (urgency) rather than fixed duration, enabling adaptive velocity profiles and resolving the fixed-time problem.
Scalable Parallel Inference: Implementation of parallelized diffusion inference within a CBS framework, allowing the system to scale to large robot teams (15 robots) in real-time.
Differentiated Guidance: A guidance strategy that separates social awareness (handled by the diffusion prior and human cost) from inter-robot coordination (handled by CBS constraints).

Experimental Results

The authors evaluated MRRD in simulated environments with varying robot counts (6–15), human crowds, and static obstacles, comparing it against CoBL-Diffusion (diffusion-based) and Navi-STAR (RL-based).

Safety and Success Rates:
- MRRD achieved 0% robot-robot collision rates across all scenarios, whereas baselines suffered rates up to 0.98 (Navi-STAR) and 0.28 (CoBL-Diffusion) in 15-robot scenarios.
- MRRD maintained a 92% success rate with 15 robots, while CoBL-Diffusion dropped to 32% and Navi-STAR to 0%.
- Robot-human collision rates were significantly lower for MRRD (0.08) compared to baselines (0.22–1.00).
Efficiency:
- MRRD demonstrated superior planning speed. For 15 robots, MRRD took 8.8 seconds to plan, compared to 60.2 seconds for CoBL-Diffusion and 17.3 seconds for Navi-STAR.
- The parallelized approach was 4x faster than a non-parallelized version of MRRD.
Trajectory Quality:
- MRRD produced smoother trajectories with mean acceleration profiles 5–8 times lower than CoBL-Diffusion, indicating more human-like, fluid movement.
- Goal-reaching accuracy was significantly better (0.37m error vs. 1.46m for CoBL-Diffusion).
Obstacle Navigation:
- In complex maps with static obstacles, MRRD maintained a 0.00 robot-robot collision rate and a 56% success rate in the densest scenario, while CoBL-Diffusion failed completely (0% success).

Significance and Claims

The paper claims that MRRD successfully bridges the gap between socially aware navigation and scalable multi-robot coordination. By moving away from rigid, fixed-duration path generation, the method allows robots to adapt their speed to the environment dynamically, a crucial factor for safety in human-shared spaces.

The authors emphasize that their approach:

Scales effectively to large teams (up to 15 robots) in real-time, a capability lacking in previous learning-based benchmarks.
Decouples interaction types, using diffusion for social norms and CBS for hard collision constraints, resulting in robust performance without sacrificing safety.
Outperforms existing baselines in both safety metrics (collision rates) and mission success, while generating trajectories that are qualitatively smoother and more human-like.

The work concludes that while future improvements could include invariance in the denoising process and integrated human prediction modules, MRRD currently represents a significant step forward in deploying large robot teams in dynamic, human-populated environments.