PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep-Learned Collision Avoidance Policy for Distributed Multi-Agent Navigation

Pinxin Long, Wenxi Liu, Jia Pan

arXiv:1609.06838v2cs.AIcs.CVcs.RO

TL;DR

Multi-agent navigation needs fast collision avoidance despite noisy sensing and the tuning demands of geometric methods. This paper trains an end-to-end neural policy from simulated collision-avoidance frames and evaluates it against ORCA. The learned policy reports a 2% failure rate versus ORCA’s 15%, while also generalizing to several unseen settings.

  • Problem

    Multi-agent collision avoidance must support real-time goal-directed motion despite obstacles, moving agents, imperfect sensing, and difficult parameter tuning.

  • Method

    The method trains a deep collision avoidance network on approximately 310,000 simulator-generated examples with varied parameters and sensor noise.

  • Results

    ORCA has a 15% failure rate while the learned policy has a 2% failure rate in the reported comparison.

  • Takeaways & Limitations

    The learned policy generalizes to agents with different sizes and scenes with static obstacles, despite training without static obstacles.

  • Takeaways & Limitations

    The model achieves around 64% training-set classification accuracy, and static obstacles were absent from training data, limiting performance in some challenging obstacle scenarios.

Abstract

from arXiv · show

High-speed, low-latency obstacle avoidance that is insensitive to sensor noise is essential for enabling multiple decentralized robots to function reliably in cluttered and dynamic environments. While other distributed multi-agent collision avoidance systems exist, these systems require online geometric optimization where tedious parameter tuning and perfect sensing are necessary. We present a novel end-to-end framework to generate reactive collision avoidance policy for efficient distributed multi-agent navigation. Our method formulates an agent's navigation strategy as a deep neural network mapping from the observed noisy sensor measurements to the agent's steering commands in terms of movement velocity. We train the network on a large number of frames of collision avoidance data collected by repeatedly running a multi-agent simulator with different parameter settings. We validate the learned deep neural network policy in a set of simulated and real scenarios with noisy measurements and demonstrate that our method is able to generate a robust navigation strategy that is insensitive to imperfect sensing and works reliably in all situations. We also show that our method can be well generalized to scenarios that do not appear in our training data, including scenes with static obstacles and agents with different sizes. Videos are available at https://sites.google.com/view/deepmaca.

I. INTRODUCTION

Multi-agent collision avoidance requires decentralized, real-time decisions that prevent collisions while agents pursue goals. Existing approaches motivate an end-to-end learned policy because parameter tuning is tedious and sensing may be imperfect.

  • Multi-agent collision avoidance requires each agent to act in real time while avoiding static obstacles and moving agents and progressing toward its goal.
  • Prior decentralized velocity-based methods rely on local sensing and can provide collision-free motion in cluttered workspaces.
  • Existing methods require parameter choices without a systematic selection principle, making manual tuning tedious.
  • The paper proposes a deep neural network that maps noisy sensor measurements directly to locally collision-free steering velocities.

A. Collision Avoidance for Multi-Agent Navigation

The paper situates collision avoidance within distributed navigation and defines a reactive controller that uses local observations and preferred motion to produce collision-avoidance velocities without communication or perfect sensing.

  • ORCA is a distributed velocity-based framework that can provide collision-free navigation, but it requires careful parameter tuning and accurate observations.
  • Agents repeatedly sense their surroundings and independently compute local trajectories toward goals while avoiding agents and obstacles within a time horizon.
  • The proposed controller uses raw sensor measurements rather than explicitly estimated positions, velocities, and shapes of surrounding agents.
  • A deep network maps local observations and preferred velocity to a velocity increment used for safe collision avoidance and progress toward the goal.
  • The collision avoidance network is named CANet.

IV. LEARNING-BASED COLLISION AVOIDANCE

The learning-based approach generates training data with ORCA and uses those data to train a deep neural collision avoidance policy.

  • The method uses ORCA to generate a large training dataset, then describes the network architecture and training procedure for the learned policy.

A. A Recap of ORCA

ORCA selects a permitted collision-free velocity closest to an agent’s preferred velocity, but its behavior depends on carefully tuned parameters.

  • ORCA first computes a permitted velocity space in which an agent avoids collisions over a time horizon.
  • It then selects the permitted velocity closest to the agent’s preferred velocity.
  • ORCA can produce locally collision-free motion with appropriate parameters, but different scenarios require careful tuning and may cause agents to get stuck.
  • Changing PROTECTRADIUS requires selecting new values for the other parameters.

B. Dataset

The dataset pairs noisy local observations and preferred velocities with ORCA-generated collision-avoidance velocities. It is collected from randomized simulator configurations, transformed into local inputs, cleansed, augmented, normalized, and discretized into 61 velocity classes.

  • Data generation: One simulator step is retained per randomized scenario to reduce correlations between training examples.The authors favor independent data items over strongly correlated sequence frames for neural-network training.
  • Data generation: Each example records an agent’s sensor observation, preferred velocity, and ORCA-computed collision-avoidance velocity.The observation uses a simulated 360-degree 2D laser scanner with 1-degree resolution and a 4-meter maximum range.
  • Input representation: Neighbor velocities are estimated by non-rigid point-cloud matching between consecutive scans, then observations are converted into the agent’s local coordinate frame.The matching uses the coherent point drift algorithm with the fast Gauss Transform.
  • Data generation: About 310,000 examples are generated by running the RVO2 simulator with varied ORCA parameters, neighbor counts, and Gaussian sensor noise.PROTECTRADIUS and TIMEHORIZON vary across specified sets, while noise standard deviation ranges from 0.01 to 0.05.
  • Preprocessing: The data pipeline removes colliding or unreasonable examples, adds noise and symmetry-based augmentations, and standardizes inputs before training.Cleansing excludes cases where ORCA’s velocity still causes collision and filters velocities near the speed limit.
  • Velocity labels: Collision-avoidance velocities are formulated as a classification problem using a manually designed partition with 61 classes informed by k-means clustering.Classification is preferred over regression to reduce sensitivity to outliers and represent uncertainty through class probabilities.

C. Collision Avoidance Network

CANet maps local observations and preferred velocities to a probability distribution over discretized collision-avoidance velocities. Its two-branch MLP is trained with stratified cross-validation, and runtime sampling selects a velocity using safety margins.

  • Architecture: CANet is a two-branch multilayer perceptron that combines local observation and preferred-velocity inputs.The network outputs a probability distribution over velocity classes that is converted into a collision-avoidance velocity.
  • Architecture: The main branch uses four fully connected ReLU layers, while the auxiliary preferred-velocity branch uses one fully connected ReLU layer.The main layers have 1024, 1024, 512, and 256 units with dropout probability 0.2; the auxiliary layer has 256 units.
  • Training: The network is trained with 10-fold stratified cross-validation using SGD with momentum, early stopping, and a maximum of 300 epochs.Training takes about 5 hours on a single Nvidia Titan X GPU with batch size 64.
  • Velocity selection: At runtime, CANet chooses the highest-probability class, samples candidate velocities around its centroid, and selects the candidate with the maximum safety margin.A velocity is slowed if its minimum safety margin is negative, indicating collision with obstacles.

V. EXPERIMENTS AND RESULTS

The experiments evaluate the learned framework in simulated scenarios against ORCA and on a real multi-robot system.

  • Evaluation: The framework is evaluated in multiple simulated scenarios, compared with ORCA, and tested on a real multi-robot system.The reported experiments cover both simulation and physical-robot evaluation.

A. Experiment Setup

The evaluation compares the learned policy with ORCA across six scenarios using navigation trajectories, travel time, distance, safety margin, and completion.

  • Scenarios: The learned policy is evaluated through trajectories and averaged over 20 simulations because its collision-avoidance velocity is random.
  • Baselines: ORCA is tuned for comparison, including TIMEHORIZONOBS = 10.0s for static-obstacle scenarios and scenario-specific TIMEHORIZON values.
  • Scenarios: Six scenarios vary agent counts and include Crossing, Circle, Swap, Random, 3 Obstacles, and 1 Obstacle.
  • Metrics: Performance is measured by total travel time, total distance traveled, safety margin, and completion.

B. Quantitative Comparisons

The learned policy matches or improves ORCA under a larger safety margin, adapts clearance to scene clutter, and achieves a lower failure rate in a challenging obstacle scenario.

  • Travel Performance: The learned policy provides better or comparable navigation duration and trajectory length than ORCA with PROTECTRADIUS = 0.5.ORCA with PROTECTRADIUS = 0.2 is faster and shorter in most scenarios but uses a smaller safety margin.
  • Safety Margin: The learned policy adapts its safety margin to clutter, using smaller clearance in the 3 Obstacles scenario than in the 1 Obstacle scene.
  • Completion: ORCA fails in 15% of randomly generated L-shaped-obstacle trials, compared with 2% for the learned policy.Failures include agents not reaching goals or severely colliding during runtime.
  • Evaluation: The learned policy generates trajectories for the evaluated scenarios, including scenes with static obstacles.

C. Generalization

The learned policy exhibits cooperative behavior and generalizes beyond its training conditions to static obstacles, different agent sizes, and real-robot navigation.

  • Cooperative Behavior: In the symmetrical Circle scenario, agents using the learned policy exhibit cooperative rotation, unlike ORCA’s individual and sometimes jerky motions.
  • Unseen Obstacles: The learned policy generalizes to static-obstacle scenarios that were absent from training data.
  • Different Agent Sizes: With different-sized agents, a larger agent deviates farther from its original path and causes other agents to adjust their navigation.ORCA’s corresponding behavior does not demonstrate generalization because it receives all agents’ radii before computing velocities.
  • Real-Robot Demonstration: Four real robots navigate toward antipodal positions while avoiding collisions in a fully distributed setup using 2D lidar.

VI. CONCLUSION AND LIMITATIONS

The paper presents a learned reactive collision-avoidance policy that improves ease of use, success rate, and navigation performance while generalizing to several unseen situations. Its current limitations include incomplete training fit, absent static obstacles in training, and limited real-world scope.

  • Conclusion: The learned policy offers a distributed collision-avoidance approach with advantages over ORCA in ease of use, success rate, and navigation performance.
  • Conclusion: The policy generalizes from training on identical moving agents to agents with different sizes and scenarios with static obstacles.
  • Limitations: The multilayer perceptron fits the training data incompletely, with training accuracy around 64%.
  • Limitations: Because static obstacles were excluded from training-data generation, performance may be limited in narrow hallways and doorways.
  • Future Work: Future work includes complex vehicle dynamics, 2D/3D camera sensing, reinforcement learning, and reliable deployment with many agents.
Loading 1609.06838v2…