Decentralized Non-communicating Multiagent Collision Avoidance with Deep Reinforcement Learning

Yu Fan Chen; Miao Liu; Michael Everett; Jonathan P. How

Source-linked AI summary

Decentralized Non-communicating Multiagent Collision Avoidance with Deep Reinforcement Learning

Yu Fan Chen, Miao Liu, Michael Everett, Jonathan P. How

arXiv:1609.07845v2Sep 26, 2016cs.MA

TL;DR

Non-communicating multiagent collision avoidance requires time-efficient, collision-free decisions despite unobservable agent intents and computationally costly interaction anticipation. The paper uses decentralized deep reinforcement learning to learn a value network for joint configurations and offload computation offline. Simulations report more than 26% improvement in paths quality compared with ORCA.

Problem
Non-communicating agents must find collision-free, time-efficient paths without observing others’ intents, while anticipating interactions can be computationally prohibitive.
Method
The method learns a deep value network encoding expected time to goal from joint agent states, then generalizes the two-agent solution to decentralized multiagent collision avoidance.
Results
More than 26% improvement in paths quality was reported compared with ORCA, with the method shown real-time implementable for a decentralized ten-agent system.
Takeaways & Limitations
The learned value function enables computationally efficient, real-time collision avoidance while implicitly encoding cooperative behavior.

Abstract

from arXiv · show

Finding feasible, collision-free paths for multiagent systems can be challenging, particularly in non-communicating scenarios where each agent's intent (e.g. goal) is unobservable to the others. In particular, finding time efficient paths often requires anticipating interaction with neighboring agents, the process of which can be computationally prohibitive. This work presents a decentralized multiagent collision avoidance algorithm based on a novel application of deep reinforcement learning, which effectively offloads the online computation (for predicting interaction patterns) to an offline learning procedure. Specifically, the proposed approach develops a value network that encodes the estimated time to the goal given an agent's joint configuration (positions and velocities) with its neighbors. Use of the value network not only admits efficient (i.e., real-time implementable) queries for finding a collision-free velocity vector, but also considers the uncertainty in the other agents' motion. Simulation results show more than 26 percent improvement in paths quality (i.e., time to reach the goal) when compared with optimal reciprocal collision avoidance (ORCA), a state-of-the-art collision avoidance strategy.

I. INTRODUCTION

Non-communicating collision avoidance must balance anticipating neighboring agents’ future motion with real-time computational limits. The work addresses this trade-off using decentralized deep reinforcement learning and extends the approach from two agents to larger teams.

Collision-free, time-efficient navigation is challenging because anticipating other agents’ motion and interactions must remain computationally tractable in real time.
Without reliable communication, agents must cooperate without knowing neighboring agents’ intents, such as goals or planned paths.
Reaction-based methods update one-step interaction rules but can be short-sighted, producing oscillatory or unnatural behavior because they ignore neighbors’ future states.
Trajectory-based methods anticipate future states but require online inference and planning, while uncertainty can make predicted paths inaccurate beyond a few seconds.
The proposed approach offloads expensive online computation to offline reinforcement learning by learning a value function that implicitly encodes cooperative behavior.
The paper contributes a two-agent deep-RL collision avoidance algorithm, a principled extension to n > 2 agents, kinematic constraints, and improved solution quality over reaction-based methods.

B. Reinforcement Learning

The reinforcement-learning formulation represents collision avoidance as sequential decision making over continuous permissible velocities. A deep value network evaluates joint agent states so one-step action selection can account for future interaction outcomes.

Reinforcement learning models sequential decisions with unknown state-transition dynamics using state, action, transition, reward, and discount components.
The system state concatenates both agents’ individual states, while actions are permissible velocity vectors constrained by the agent’s preferred speed.
The reward awards reaching the goal and penalizes getting too close to or colliding with the other agent.
The state-transition model is unknown because the other agent’s actions depend on its policy and hidden intents; the formulation assumes reciprocal policies.
The method optimizes a value function rather than Q because the action space is continuous and permissible velocities depend on preferred speed.

III. APPROACH

The approach uses a fully connected deep neural network with ReLU nonlinearities to parameterize a value function for the continuous joint state.

A fully connected deep neural network with ReLU nonlinearities parameterizes the value function V(·; w).The network is applied to a continuous 14-dimensional joint state, with weights represented by w.

A. Parametrization

The joint state is represented in an agent-centric coordinate frame to remove redundancy from rotation and translation invariance.

The agent-centric frame places the origin at the agent and points its x-axis toward the goal.This removes coordinate-transformation ambiguity from the joint-state parameterization.
The parameterization includes distance to the goal, d_g, and distance to the other agent, d_a.d_g = ||p_g − p||_2 and d_a = ||p − p̃||_2.

B. Generating Paths Using a Value Network

Paths are generated by repeatedly selecting the permissible velocity whose one-step projected joint state has the highest value, while approximating the neighbor’s short-term motion.

The agent repeatedly maximizes a one-step lookahead value to select actions that lead on average to high-value joint states.The value network guides online path generation toward the goal.
The other agent’s next state is approximated using a filtered velocity over a short duration.This approximation addresses the unknown distribution caused by the neighbor’s unobservable intent.
The CADRL procedure outputs a trajectory while iteratively updating time and receiving measurements from both agents.Algorithm 1 continues this loop until the goal is reached.
The filtered-velocity propagation uses a short-term linear model, while the projected value captures uncertainty in longer-term motion.The best action is selected from permissible velocity vectors.

C. Training a Value Network

Training first initializes the value network from baseline-policy trajectories, then refines it with reinforcement learning using simulated two-agent interactions.

Supervised training initializes the value network from trajectories generated by a baseline policy.Each trajectory is converted into state-value training examples.
Training trajectories are processed into state-value pairs {(s_jn, y)_k}^N_{k=1}.The target is y = γ t_g · v_pref, where t_g is the time to reach the goal.
The target value uses the discount factor, goal-reaching time, and preferred velocity: y = γ t_g · v_pref.This target is used for back-propagation with a quadratic objective.
The implementation averages velocity over the past 0.5 seconds and sets the propagation interval Δt to 1.0 second.
The action set contains 25 pre-computed actions and 10 randomly sampled actions.Pre-computed actions include directions toward the goal or current heading.
Deep V-learning is the training procedure used to train the value network.

1 Input: trajectory training set D

The value network is initialized from ORCA-generated trajectories and then refined through reinforcement learning. Evaluation indicates convergence after approximately 800 episodes, while learned trajectories can improve on ORCA.

ORCA generates 500 training trajectories containing approximately 20,000 state-value pairs for initializing the value network.
The initialization step learns a time-to-goal value function rather than simply imitating the ORCA policy.The learned value function can generate shorter trajectories than ORCA, although it may remain suboptimal.
Reinforcement learning refines the policy by simulating two agents with an ϵ-greedy policy and generating additional state-value pairs.
The training process converges in approximately 800 episodes, while evaluation paths become tighter as minimum separation decreases from 0.4m to 0.2m.

D. Incorporating Kinematic Constraints

The reinforcement-learning framework incorporates rotational kinematic constraints while preserving the collision-avoidance objective. These constraints restrict permissible motion and can produce slower, turn-aware behavior.

Rotational constraints are incorporated in the RL framework to model physical robots without the substantial computational increase associated with some existing approaches.
Under the direction constraint |φ − θ| < π/6, the agent may choose to slow down and can spin in place while turning toward its goal.
Constraint (9) limits travel direction, while constraint (10) specifies a maximum turning rate corresponding to a minimum turning radius of 1.0m.

E. Multiagent Collision Avoidance

CADRL extends a two-agent value network to multiagent collision avoidance by propagating each neighbor’s state and selecting actions based on projected neighbor states. Simulations produce smooth interaction patterns, but the extension remains an approximation to a true n-agent value function.

The multiagent extension uses each neighbor’s observable state to form joint states, while training thresholds are set to el = 1.0 and eu = 2.0.
With rotational constraints, the red agent may turn on the spot before moving while continuing to turn toward its goal.
CADRL generalizes to n > 2 agents by propagating every neighbor’s state one step forward and selecting the action with the highest value for any projected neighbor state.
In six-agent circle crossing, agents veer more than in the two-agent case to create room for smooth passage through the center.
In three horizontal swapping pairs, the central pair slows near the origin so the outer agents can pass first.
The multiagent value approximation can generate complex, smooth trajectories, but a true n-agent value network is left for future work.

IV. RESULTS

CADRL produces cooperative, increasingly tight trajectories and outperforms ORCA in the tested crossing scenarios while remaining suitable for real-time decentralized operation. Its computation scales with the number of neighbors, and repeated training trials produced similar performance.

Training and Trajectories: CADRL learns cooperative trajectories in which one agent slows and cuts behind another, while trajectories become tighter as minimum separation decreases from 0.4m to 0.2m.
Training and Trajectories: CADRL generates complex multiagent interaction patterns despite using a two-agent value network, including wider veering and strategic slowing in six-agent scenarios.
Computational Complexity: 5.7ms per iteration is the average CADRL runtime for two-agent collision avoidance problems.
Computational Complexity: 62ms per iteration is observed for decentralized CADRL controlling ten agents, with computation scaling linearly in neighboring agents.A centralized implementation scales quadratically, while independent value-network queries make decentralized CADRL parallelizable.
Computational Complexity: Less than three hours of offline training produced value networks that converged across three ORCA-generated trajectory sets.The initialization step took 9.6 minutes for 10,000 back-propagation iterations, and the reinforcement-learning step took approximately 2.5 hours for 1,000 episodes.
Computational Complexity: Less than 5% difference in time to reach goal across all evaluation test cases indicates similar paths from the three training trials.
Performance Comparison: CADRL performs significantly better than ORCA across crossing angles α ∈[90, 150] deg, although it can be slightly slower near α = 0.Unconstrained CADRL is better on average in randomized test cases, while constrained CADRL can perform better on particular crossing cases.

C. Performance Comparison on Random Test Cases

Randomized evaluations compare CADRL with ORCA across agent configurations and difficulty levels, showing faster goal-reaching paths, especially when interactions are more demanding. CADRL also handles static obstacles and a non-cooperative agent, though dense obstacle fields can cause it to get stuck.

Multiagent cases: In a four-agent test case, ORCA agents followed long arcs, whereas CADRL agents reached their goals much faster.The ORCA behavior reflects a similar two-agent interaction pattern.
Random test cases: On easier random test cases, CADRL performs similarly to, or slightly better than, ORCA at the median.The comparison uses extra time to goal over one hundred random test cases per configuration.
Random test cases: Above the 75th percentile, CADRL performs significantly better than ORCA on more difficult random test cases.This comparison concerns the upper tail of extra time to goal.
Non-cooperative agents: CADRL can navigate around stationary obstacles and a non-cooperative agent traveling in a straight line.Around the non-cooperative agent, CADRL veers farther left than in the cooperative case.
Non-cooperative agents: Dense obstacle fields can cause CADRL to get stuck because traps or dead ends may form between multiple obstacles.The paper scopes CADRL as a collision avoidance algorithm rather than a path planning algorithm for such scenarios.
Random test cases: CADRL finds paths that reach goals much faster than ORCA on average, with the clearest improvement on hard and multiagent cases.The table attributes the larger advantage to cases requiring more interactions.