PaperlayerView exact revision on arXiv

Source-linked AI summary

Collision Avoidance in Pedestrian-Rich Environments with Deep Reinforcement Learning

Michael Everett, Yu Fan Chen, Jonathan P. How

arXiv:1910.11689v4cs.ROcs.AI

TL;DR

The paper addresses collision avoidance among heterogeneous, non-communicating dynamic agents when intents, behavior models, and the number of neighbors are uncertain. It proposes a deep-RL policy with an LSTM input strategy for variable agent sets, and reports stronger scaling and real-robot demonstrations than prior approaches.

  • Problem

    Collision avoidance must handle unknown agent intents, heterogeneous behaviors, and a large or varying number of neighboring agents without relying on explicit communication.

  • Method

    The method trains a deep-RL collision-avoidance policy in simulation, using an LSTM to encode observations of many neighboring agents and learning interaction modeling offline for rapid online queries.

  • Results

    The algorithm outperformed classical and deep-RL baselines, scaled better as agent counts increased, and was demonstrated in formation control and on aerial and ground robots.

  • Takeaways & Limitations

    The results support using LSTMs to encode varying numbers of agent states and indicate that the learned policy can be deployed on real robots.

Abstract

from arXiv · show

Collision avoidance algorithms are essential for safe and efficient robot operation among pedestrians. This work proposes using deep reinforcement (RL) learning as a framework to model the complex interactions and cooperation with nearby, decision-making agents, such as pedestrians and other robots. Existing RL-based works assume homogeneity of agent properties, use specific motion models over short timescales, or lack a principled method to handle a large, possibly varying number of agents. Therefore, this work develops an algorithm that learns collision avoidance among a variety of heterogeneous, non-communicating, dynamic agents without assuming they follow any particular behavior rules. It extends our previous work by introducing a strategy using Long Short-Term Memory (LSTM) that enables the algorithm to use observations of an arbitrary number of other agents, instead of a small, fixed number of neighbors. The proposed algorithm is shown to outperform a classical collision avoidance algorithm, another deep RL-based algorithm, and scales with the number of agents better (fewer collisions, shorter time to goal) than our previously published learning-based approach. Analysis of the LSTM provides insights into how observations of nearby agents affect the hidden state and quantifies the performance impact of various agent ordering heuristics. The learned policy generalizes to several applications beyond the training scenarios: formation control (arrangement into letters), demonstrations on a fleet of four multirotors and on a fully autonomous robotic vehicle capable of traveling at human walking speed among pedestrians.

I. INTRODUCTION

The paper develops decentralized deep-RL collision avoidance for uncertain interactions with heterogeneous, non-communicating agents. Its LSTM-based representation handles a large, varying number of neighbors while learning cooperative behavior for efficient online action selection.

  • Unknown pedestrian and vehicle intents, plus impractical communication, make safe autonomous navigation difficult in dynamic environments.
  • Existing decentralized methods trade computational efficiency and reactive behavior against smooth motion, long-horizon planning, or susceptibility to the freezing robot problem.
  • CADRL uses reinforcement learning to move expensive interaction modeling offline while providing a computationally efficient policy that implicitly encodes cooperative behavior.
  • LSTM encodes spatial representations of a large, possibly varying number of neighboring agents, addressing fixed-dimension input limits of typical feedforward networks.
  • The proposed method avoids assumptions that other agents are homogeneous, follow particular behavior rules, or obey specific short-timescale motion models.
  • The algorithm is reported to outperform prior works as agent counts increase, with hardware demonstrations on aerial and ground robots.

B. RELATED WORK

Prior collision-avoidance approaches either react myopically using simplified interaction rules or plan smoother trajectories through computationally expensive prediction and inference. The paper positions learned policies as a way to retain fast online execution while modeling interactions offline.

  • MPC planners repeatedly optimize action sequences using predictions of future world states conditioned on world-state history.
  • Static-world models can produce time-inefficient paths because they do not anticipate changes caused by moving obstacles.
  • Reaction-based methods account for current obstacle motion efficiently but do not anticipate hidden intents and can generate unnatural trajectories.
  • Trajectory-based methods produce smoother, non-myopic paths but may be computationally expensive or require unobservable agent states.
  • Inference and planning must be performed online at each new observation, adding computational expense.

2) Learning-based approaches

Learning-based collision avoidance replaces costly online interaction modeling with policies learned offline, but prior value-based methods depend on motion assumptions and propagation choices. This work motivates direct policy learning to avoid those issues.

  • Prior learning-based approach: CADRL uses an offline-learned value function to enable fast online action selection, combining computational efficiency with interaction-aware motion.The value function estimates expected time to the goal, and prior methods extract actions through one-step lookahead under a simplified kinematic model.
  • RL formulation: RL formulates collision avoidance as sequential decision-making with unknown state-transition dynamics caused by other agents’ policies and hidden intents.The MDP includes state, action, transition, reward, and discount components; the transition model is unknown because other agents’ actions depend on hidden goals and policies.
  • Limitations: Large propagation intervals reduce numerical noise but assume other agents maintain constant velocity, neglecting reactions and becoming less valid as agent count increases.The prior framework also requires tuning Δt for training convergence; Δt = 1 sec was selected experimentally without much theoretical rationale.
  • Prior learning-based approach: CADRL’s separate collision checking can select inefficient actions because its constant-velocity prediction conflicts with the value function’s preferred action.In the illustrated case, combining collision cost with state value makes the agent go straight to avoid collision, despite a cooperative agent potentially adjusting its velocity.
  • Proposed direction: The proposed framework learns a policy directly, eliminating forward projection during policy evaluation and removing the need to tune the Δt hyperparameter.It uses an actor-critic design in which a single network approximates both policy and value functions, trained with separate loss terms.

D. RELATED WORKS USING LEARNING

Learning-based collision avoidance methods trade modeling and data requirements against scalability and safety guarantees. Agent-level methods increasingly address variable numbers of neighbors with recurrent representations, while guarantees remain difficult in pedestrian-rich settings.

  • Learning paradigms: Imitation learning requires expert demonstrations, whereas inverse reinforcement learning estimates pedestrian cost functions to inform robot planning.Reinforcement learning offers self-play as an alternative source of experience, using low-fidelity simulation to reduce expensive real-world data collection.
  • State representations: Sensor-level RL selects actions from raw laser or image observations, creating very large state spaces that make training challenging.For example, a 480 × 360 × 3 camera input contains 5,184,000 values before feature extraction.
  • State representations: Agent-level RL must represent a variable number of nearby agents, while fixed-input feedforward networks require padding or a predetermined maximum.Increasing that maximum adds network parameters and training time.
  • State representations: A recurrent network converts a timestep’s sequence of agent states into a fixed-size world-state representation before feedforward policy processing.The approach addresses variable neighbor counts; attention mechanisms are identified as another possible embedding strategy.
  • Reward design: Dense rewards ease learning but make reward shaping difficult, whereas sparse rewards are easier to specify but require careful exploration and initialization.Balancing goals and proximity to others can create undesired local minima in dense reward functions.
  • Safety: Learning-based methods typically lack safety guarantees such as deadlock avoidance and zero collisions, especially when assumptions about other agents are difficult to make realistic.Overly conservative assumptions can also degrade performance in pedestrian-rich environments.

III. APPROACH

GA3C-CADRL formulates collision avoidance as a multiagent reinforcement-learning problem using local, rotation-invariant observations of the robot and nearby agents. The policy maps these observations to actions while training incorporates experiences from multiple agents.

  • The agent state separates fixed-size self-information from one observable state vector for each nearby agent.The local coordinate frame makes the representation rotation-invariant.
  • The action space contains 11 discrete combinations of speed and heading change designed to mimic robotic-vehicle turning constraints.Preferred speed has six headings, while half-preferred and zero speed have three heading choices each.
  • GA3C-CADRL solves the multiagent problem with asynchronous actor-critic reinforcement learning.The policy and value function are trained from state, action, and reward experiences.

B. HANDLING A VARIABLE NUMBER OF AGENTS

The approach uses an LSTM to convert a variable-length sequence of nearby-agent observations into a fixed-length world representation. That representation is combined with the robot’s own state and passed to actor and critic networks.

  • Recurrent neural networks accept arbitrary-length input sequences and produce fixed-size outputs, addressing feedforward networks’ fixed-input limitation.This allows the representation to accommodate varying numbers of other agents.
  • The LSTM is used to encode a sequence of agent observations rather than time-dependent data.Its weights are trained end-to-end to represent a variable number of agents in a fixed-length vector.
  • Each nearby agent’s observable state is fed sequentially into an LSTM, whose final hidden state encodes the other agents in a fixed-length vector.The LSTM uses hidden and cell states to retain pertinent information while processing the sequence.
  • Agent observations are ordered by decreasing distance, giving the closest agent the most recent effect on the final hidden state.This ordering is intended to reduce the impact of forgetting early inputs when many agent states are processed.
  • The final hidden state is concatenated with the agent’s own state to form an encoded joint-world state for downstream prediction.Two fully connected layers then produce a scalar value and a discrete action-probability distribution.

C. TRAINING THE POLICY

Training combines supervised initialization with asynchronous reinforcement learning in parallel multiagent simulations. The resulting framework supports scenarios with varying agent counts, while experiments identify a convergence boundary for larger groups.

  • Supervised initialization uses existing CADRL state-action-value tuples before reinforcement-learning refinement.The initialization converges in less than five minutes and enables later generation of useful experiences.
  • Parallel environments train on episodes containing 2-10 agents with randomized starts, goals, policies, radii, and preferred speeds.Agent radii range from 0.2 to 0.8 m and preferred speeds from 0.5 to 2.0 m/s.
  • The framework mixes experiences from multiple agents into training batches to improve joint expected reward.Experiences from agents running other policies are ignored during policy updates.
  • During inference, the policy selects the highest-probability action after onboard sensing and state transformation, followed by low-level control.Execution uses fixed neural-network parameters and requires a controller to track desired speed and heading.
  • Experiments suggest the number of agents should remain below about 6 for convergence.

A. COMPUTATIONAL DETAILS

GA3C-CADRL-10-LSTM achieves real-time inference and comparable small-agent performance while improving collision-avoidance outcomes as agent counts increase. It also generalizes beyond training scenarios to 20- and 40-agent settings.

  • A. COMPUTATIONAL DETAILS: 0.4–0.5ms average query time enables real-time CPU-only inference without a GPU.The network query uses only the current state vector and is approximately 20 times faster than the earlier implementation.
  • A. COMPUTATIONAL DETAILS: 24 hours and 2 · 10^6 episodes were required for multiagent LSTM training to converge.Training used an i7-6700K CPU with 32 parallel environment threads and no prior structure about other agents’ behaviors.
  • Baselines: For n ≤4 agents, GA3C-CADRL-10-LSTM performs comparably to, though slightly worse than, SA-CADRL.The plotted trajectories are generally similar, with SA-CADRL reaching goals slightly sooner.
  • Baselines: For n = 6, 8, 10, GA3C-CADRL-10-LSTM shows a 3-4x reduction in failed cases with similar ¯teg compared to SA-CADRL.Its success remains above 95% for n ≤10, while SA-CADRL drops below 80%; GA3C-CADRL variants also outperform ORCA for large n.

5) n > 4 agents: Ablation Study

The ablation study shows that policy-based learning and staged training improve performance for large agent populations, while LSTM preserves flexibility without requiring a fixed maximum. Increasing predefined capacity alone does not solve the core challenge.

  • 5) n > 4 agents: Ablation Study: GA3C-CADRL-WS-4 strongly outperforms SA-CADRL for large n despite matching its architecture and training-agent count.This isolates a benefit of policy-based learning over the SA-CADRL framework under the tested large-agent conditions.
  • 5) n > 4 agents: Ablation Study: The second training phase, expanding exposure to up to 10 agents, produces another large performance improvement.The framework can retrain in complex scenarios after converging in simpler ones.
  • 5) n > 4 agents: Ablation Study: LSTM accepts observations of any number of agents and performs similarly to GA3C-CADRL-10-WS-4 while offering a more flexible architecture.It also provides better performance for small n than the corresponding fixed-capacity approach.
  • 5) n > 4 agents: Ablation Study: Adding predefined agent capacity can have small or negative performance effects, so merely increasing the maximum input count does not address multiagent collision avoidance.The additional-capacity WS variants GA3C-CADRL-WS-4,6,8 sometimes degrade performance.

6) Comparison to Other RL Approach

The paper compares GA3C-CADRL with another deep RL policy and demonstrates deployment across formation control, multirotors, and pedestrian navigation. The learned policy remains effective with heterogeneous agents and realistic sensing, while DRLMACA is sensitive to agent radius.

  • 6) Comparison to Other RL Approach: GA3C-CADRL outperforms DRLMACA for both r = 0.2m and r = 0.5m in 100 random test cases.DRLMACA’s performance drops heavily at r = 0.5m, with 69% collisions in random 4-agent scenarios.
  • Multirotor Experiments: Four multirotors retain roundabout behavior during center-crossing swaps despite small differences in vehicle states and actions.The policy was transferred from simulation to multirotors with more complicated dynamics than the training model.
  • Formation Control: Six agents use GA3C-CADRL-10-LSTM to choose decentralized, collision-free actions while spelling “CADRL”.Each agent uses other agents’ current positions, velocities, and radii; goal coordinates are randomly assigned within a 6 × 6m region.
  • Pedestrian Navigation: A ground robot avoids collisions among pedestrians using only onboard sensing despite lacking perfect state knowledge.The sensing suite combines a 2D Lidar with three Intel Realsense R200 cameras.
  • Pedestrian Navigation: The robot successfully reaches a goal about 6m away while navigating near six heterogeneous pedestrians with varying, stochastic cooperativeness.The pedestrian roles were not assigned and changed stochastically throughout the scenario.

D. LSTM ANALYSIS

The LSTM encodes observations of varying numbers of neighboring agents into a fixed-length representation used for collision-avoidance decisions. Its input-gate behavior shows how current observations and accumulated hidden state influence which agents affect downstream decisions.

  • LSTM Gate Dynamics: The LSTM accepts each neighboring agent state sequentially, together with previous hidden and cell states, to process variable-size observations.The hidden state has size nh = 64.
  • Hardware Demonstrations: The learned policy was demonstrated on four multirotors and a ground robot among pedestrians traveling nominally at 1.2m/s.The multirotor demonstrations included parallel and orthogonal pair scenarios, with the orthogonal agents forming a symmetric roundabout pattern.
  • LSTM Gate Dynamics: An input-gate value near 1 passes most of a candidate cell state into the cell state, while a value near 0 gives the agent little downstream influence.The gate therefore indicates the contextual importance of the current agent observation.
  • LSTM Gate Dynamics: The normalized gate contribution separates effects from the current agent state, previous hidden state, and bias.The normalization scales the three components by the average magnitude of the input-gate vector.
  • LSTM Gate Dynamics: For the first agent, the current observation dominates input-gate activation because the initial hidden and cell states are blank.For later agents, the LSTM combines the current observation with the previous hidden state when deciding how much information to retain.
  • LSTM Gate Dynamics: When the closest agent heads toward the ego agent, the input-gate activation is larger than when that agent heads away.The increase appears in the current-observation contribution and was observed in most randomly generated scenarios.

2) Agent Ordering Strategies

The study compares heuristics for ordering agent observations before they enter the LSTM. Although the strategies reach similar final rewards, “closest last” provides the most stable training transition and the best final performance among the tested alternatives.

  • Ordering Definitions: “Closest last” orders agents by decreasing distance from the ego agent, while “closest first” uses the reverse order.Time-to-collision ordering uses minimum collision time at current velocities, with distance and ego-frame position as tie-breakers.
  • Training Protocol: Training used 1.5M episodes with 24 agents followed by 0.5M episodes with 2-10 agents.The comparison kept the network architecture fixed and changed only the LSTM agent ordering.
  • Training Results: All three ordering strategies achieved similar performance during the first 1M training episodes.By the end of Phase 1, “closest first” was slightly worse than the other two strategies.
  • Training Results: At the phase transition, “closest first” dropped substantially, whereas “closest last” showed no noticeable dip.The time-to-collision curve also exhibited a small dip, but all strategies converged to similar final performance.
  • Conclusion: The authors conclude that ordering has a second-order effect on reward curves, with “closest last” better than the tested alternatives.The ordering analysis is presented as evidence supporting the intuition about how the LSTM combines agent summaries.
  • Overall Findings: Across increasing agent counts, GA3C-CADRL outperformed a classical method and another deep RL method and scaled better than the authors’ previous learning-based method.The conclusion also reports hardware demonstrations on four autonomous multirotors and a ground robot among pedestrians.
Loading 1910.11689v4…