Towards Optimally Decentralized Multi-Robot Collision Avoidance via Deep Reinforcement Learning

Pinxin Long; Tingxiang Fan; Xinyi Liao; Wenxi Liu; Hao Zhang; Jia Pan

Source-linked AI summary

Towards Optimally Decentralized Multi-Robot Collision Avoidance via Deep Reinforcement Learning

Pinxin Long, Tingxiang Fan, Xinyi Liao, Wenxi Liu, Hao Zhang, Jia Pan

arXiv:1709.10082v3Sep 28, 2017cs.ROcs.AIcs.LGcs.MA

TL;DR

Decentralized multi-robot collision avoidance is difficult when robots lack other agents’ states and intents, while existing methods can require costly sensing or underperform centralized approaches. The paper learns a shared sensor-level policy from raw measurements using multi-scenario, multi-stage policy-gradient reinforcement learning. In simulated evaluations, the policy produced time-efficient, collision-free navigation and generalized to heterogeneous robots and a 100-robot scenario.

Problem
Decentralized collision avoidance must be safe and efficient without each robot observing other robots’ states and intents, while existing distributed methods can require computationally costly agent-level feature extraction.
Method
The paper trains a shared decentralized sensor-level policy that maps raw sensor measurements to velocity commands using multi-scenario, multi-stage policy-gradient reinforcement learning.
Results
The learned policy found time-efficient, collision-free paths in large-scale simulated multi-robot systems and generalized to heterogeneous robots and 100-robot scenarios without fine-tuning.
Takeaways & Limitations
The results demonstrate a sensor-level decentralized policy with collision-avoidance performance and generalization capability evaluated against NH-ORCA.
Takeaways & Limitations
The local collision-avoidance policy cannot replace a global path planner for scheduling many robots through complex environments with dense obstacles.

Abstract

from arXiv · show

Developing a safe and efficient collision avoidance policy for multiple robots is challenging in the decentralized scenarios where each robot generate its paths without observing other robots' states and intents. While other distributed multi-robot collision avoidance systems exist, they often require extracting agent-level features to plan a local collision-free action, which can be computationally prohibitive and not robust. More importantly, in practice the performance of these methods are much lower than their centralized counterparts. We present a decentralized sensor-level collision avoidance policy for multi-robot systems, which directly maps raw sensor measurements to an agent's steering commands in terms of movement velocity. As a first step toward reducing the performance gap between decentralized and centralized methods, we present a multi-scenario multi-stage training framework to find an optimal policy which is trained over a large number of robots on rich, complex environments simultaneously using a policy gradient based reinforcement learning algorithm. We validate the learned sensor-level collision avoidance policy in a variety of simulated scenarios with thorough performance evaluations and show that the final learned policy is able to find time efficient, collision-free paths for a large-scale robot system. We also demonstrate that the learned policy can be well generalized to new scenarios that do not appear in the entire training period, including navigating a heterogeneous group of robots and a large-scale scenario with 100 robots. Videos are available at https://sites.google.com/view/drlmaca

I. INTRODUCTION

Multi-robot navigation requires safe, robust collision avoidance, but centralized and agent-level decentralized methods rely on information or processing pipelines that limit scalability, robustness, or applicability. The paper proposes a sensor-level decentralized policy trained with multi-scenario, multi-stage deep reinforcement learning for nonholonomic robots in complex environments.

Motivation: Centralized methods use comprehensive agent intents and workspace knowledge to plan collision-avoidance actions, but they are difficult to scale and depend on reliable communication.They are also inapplicable in unknown and unstructured environments.
Related limitations: Agent-level decentralized policies use observable states of neighboring agents, while related learning pipelines may require perfect sensing, segmentation, recognition, and tracking.These requirements can impose expensive online computation and reduce robustness to perception uncertainty.
Proposed direction: Sensor-level policies directly map raw sensor data to collision-free steering commands without requiring perfect neighboring-agent sensing or scenario-specific offline parameter tuning.The paper identifies supervised-learning difficulties including extensive interaction data, non-optimal expert trajectories, and hand-designed loss functions.
Proposed direction: The proposed multi-scenario, multi-stage framework learns the collision-avoidance policy with a policy-gradient reinforcement-learning method.The approach targets multiple nonholonomic mobile robots navigating to goals without collisions in rich and complex environments.

III. PROBLEM FORMULATION

The paper formulates multi-robot collision avoidance as partially observed sequential decision-making for homogeneous differential-drive robots. Each robot independently samples velocity actions from a shared policy, while trajectories satisfy collision, obstacle, and kinematic constraints and the objective minimizes mean arrival time.

Problem setting: During training, all N robots are homogeneous discs with the same radius R and move as nonholonomic differential-drive robots among obstacles and other decision-making robots.The problem is defined on the Euclidean plane.
Decentralized decisions: Each robot uses partial observations and independently computes a collision-free steering command that approaches its relative goal.The robot has no explicit knowledge of other robots’ states and intents.
Decentralized decisions: A shared stochastic policy maps each robot’s observation to a velocity action that guides goal approach while avoiding robots and obstacles within the next observation interval.The action is sampled from policy π shared by all robots and produces velocity v_t.
Trajectory constraints: The resulting observation-action sequences define robot trajectories subject to nonholonomic kinematic constraints and collision-clearance conditions.The trajectory set includes separation from other robots and obstacles, together with a maximum-velocity constraint.
Optimization objective: The shared policy is optimized by minimizing the expected mean arrival time of all robots, using policy-gradient reinforcement learning with trust-region-bounded updates for stability.Average arrival time is also used as an evaluation metric.

IV. APPROACH

The approach section organizes the reinforcement-learning framework, neural-network collision-avoidance policy, and training protocols used to optimize the policy.

Approach: The approach introduces the reinforcement-learning framework before describing the policy’s deep-neural-network architecture and training protocols.These components are presented as the key ingredients for optimizing the collision-avoidance policy.
Approach: The policy architecture is described in terms of a deep neural network for collision avoidance.The passage identifies architecture as a distinct part of the approach description.
Approach: The training protocols are elaborated as the procedures used to optimize the collision-avoidance policy.The section follows the framework and architecture descriptions with training details.

A. Reinforcement Learning Setup

The reinforcement-learning setup casts the problem as a POMDP in which decentralized robots act from local observations. Observations combine laser scans, relative goal position, and current velocity, with normalized sensor histories.

POMDP formulation: The multi-robot problem is formulated as a POMDP solved with reinforcement learning, using observation, action, transition, reward, and state spaces.Each robot observes samples from underlying system states, and a centralized multi-robot transition model is unnecessary for fully decentralized planning.
Observation space: Each observation combines 2D laser range measurements, the relative goal position, and the robot’s current velocity.The relative goal is represented in polar coordinates, while velocity includes translational and rotational components.
Observation space: The laser input contains three consecutive frames from a 180-degree scanner with a 4-meter maximum range and 512 distance values per scan.The scanner is mounted on the robot’s forepart to obtain a large unoccluded view.
Observation space: Observations are normalized by subtracting the mean and dividing by the standard deviation computed from statistics collected during training.This normalization is applied to the observation inputs.

2) Action space:

The continuous action space represents each robot’s translational and rotational velocities, while rewards combine goal progress, collision avoidance, and smooth motion.

Action space:: Translational velocity v ranges from 0.0 to 1.0, while rotational velocity w ranges from −1.0 to 1.0.Backward motion is disallowed because the laser range finder cannot cover the robot’s back area.
Reward design:: The objective is to avoid collisions during navigation and minimize the mean arrival time across robots.
Reward design:: Each robot’s reward combines goal-reaching, collision, and rotational-velocity terms.The training constants are rarrival = 15, rcollision = −15, and ωw = −0.1, with ωg = 2.5.

B. Network architecture

The policy network processes laser scans alongside goal and velocity information, then produces a stochastic continuous-velocity action.

Network architecture: A four-hidden-layer neural network approximates the policy πθ, mapping observation ot to action outputs.
Network architecture: The network outputs velocity means and a separate log-standard-deviation vector for stochastic action sampling.The final action is sampled from a Gaussian distribution whose mean is the predicted velocity mean; logstd is updated only during training.
Network architecture: Laser features are concatenated with the relative goal position and current velocity before entering the final hidden layer.
Network architecture: The first three hidden layers process laser measurements using one-dimensional convolutions followed by a fully connected layer.The first two layers use 32 filters with kernel sizes 5 and 3, both with stride 2 and ReLU activations; the third layer has 256 rectifier units.
Network architecture: Sigmoid and tanh activations constrain the predicted translational and rotational velocity means to their permissible ranges.

C. Multi-scenario multi-stage training

The policy is trained with parallel multi-robot reinforcement learning, using shared-policy experience collection and PPO updates to support complex, large-scale scenarios.

Multi-scenario multi-stage training: Each robot independently receives its observation and executes an action generated by the shared policy πθ.
Multi-scenario multi-stage training: Training alternates between parallel trajectory sampling and policy updates using the sampled data.
Multi-scenario multi-stage training: The PPO policy loss is optimized with Adam under a KL-divergence constraint, while a separate value network estimates advantages.The policy and value networks do not share parameters because separate networks produced better results in practice.
Multi-scenario multi-stage training: Parallel PPO scales to teams with hundreds of robots because each robot independently collects training data.Decentralized execution reduces sample-collection time and supports training across many scenarios.

2) Training scenarios:

Training uses simulated environments and a staged curriculum: robots first learn in simpler settings, then train with more robots in richer scenarios.

Training scenarios:: The simulator generates diverse obstacle environments while robots move concurrently through sampled starts and goals.
Training stages:: The curriculum begins with 20 robots in a random scenario and later increases the team to 58 robots in richer, more complex scenarios.
Training stages:: Curriculum training accelerates convergence and achieves higher rewards than training from scratch for the same number of epochs.
Training scenarios:: The training process collects trajectories from multiple robots in parallel before updating the policy and value function.
Training stages:: The algorithm adapts its KL penalty coefficient when the measured policy divergence is above or below target thresholds.

V. EXPERIMENTS AND RESULTS

The experiments evaluate training, computational cost, and performance across diverse simulated scenarios. The framework uses multiple training environments and reports its implementation and execution setup.

The evaluation covers quantitative comparisons across simulated scenarios and tests generalization in challenging environments.The experiments compare policies and assess generalization capability.
The implementation uses TensorFlow and simulates large robot groups with laser scanners in Stage.Training ran on an i7-7700 CPU with an Nvidia GTX 1080 GPU.
Training uses diverse obstacle scenarios with all robots moved concurrently in the Stage simulator.The scenarios vary obstacle layouts and robot start and goal positions.
Online decentralized control computes actions for ten robots in 3ms on the CPU and about 1.3ms on the GPU.

B. Quantitative comparison on various scenarios

The study compares the learned policies with NH-ORCA and supervised learning using repeated performance measurements. Across circle and random scenarios, the learned policies achieve stronger success and speed-related outcomes, with stage-specific generalization differences.

1) Performance metrics: Performance is measured using success rate, extra time, and extra distance, with each test case evaluated for 50 repeats.Extra time and extra distance compare travel outcomes against straight-line maximum-speed lower bounds.
2) Circle scenarios: The learned policy significantly improves success rate, average extra time, and travel speed over NH-ORCA on circle scenarios.For more than 15 robots, it travels slightly farther but reaches goals faster because higher speed requires more deceleration space.
2) Circle scenarios: Table II reports mean and standard deviation for performance metrics across methods and robot counts in circle scenarios.
3) Random scenarios: Both reinforcement-learning policies achieve higher success and faster target arrival than NH-ORCA in random scenarios.Their longer trajectories accompany higher average speed and success rate; Stage 1 performance is partly attributed to overfitting, whereas Stage 2 uses multiple scenarios.

4) Group scenarios:

The learned Stage-2 policy handles group coordination and generalizes beyond its training distribution. It completes a narrow-corridor exchange, navigates heterogeneous and non-cooperative robots, and scales to 100 robots without fine-tuning.

4) Group scenarios: Only the Stage-2 policy completes the narrow corridor exchange between two robot groups with two obstacles.Stage 1 fails, while NH-ORCA fails because it relies on global planners in the complex environment.
4) Group scenarios: The sensor-level policy infers static obstacles from raw sensor readings without the additional processing required by agent-level methods.
C. Generalization: The learned policy avoids non-cooperative rectangular robots traveling straight at fixed speed, despite training only with cooperative disc-shaped robots.
C. Generalization: The policy navigates heterogeneous robots with different sizes and shapes to their goals without collisions.
C. Generalization: The policy generalizes to 100 robots moving toward antipodal positions in a large circle without fine-tuning.
VI. CONCLUSION: The paper presents multi-scenario, multi-stage training for a fully decentralized sensor-level collision-avoidance policy using policy-gradient reinforcement learning.The conclusion frames this as a step toward reducing the performance gap between centralized and decentralized methods.