PaperlayerView exact revision on arXiv

Source-linked AI summary

Motion Planning Among Dynamic, Decision-Making Agents with Deep Reinforcement Learning

Michael Everett, Yu Fan Chen, Jonathan P. How

arXiv:1805.01956v1cs.ROcs.AIcs.LG

TL;DR

Robotic collision avoidance must handle dynamic agents whose behaviors and intents are not reliably captured by existing assumptions, while also accommodating varying numbers of neighbors. The paper introduces GA3C-CADRL, which learns without a prescribed behavior model and uses LSTM encoding for arbitrary agent counts. It reports stronger simulation performance as agent counts increase and demonstrates autonomous robotic navigation at human walking speed without 3D Lidar.

  • Problem

    Existing learning-based collision-avoidance methods assume properties such as homogeneous agents or specific motion models, while typical networks require fixed-size observations.

  • Method

    GA3C-CADRL uses deep reinforcement learning without assuming other agents’ dynamics and applies LSTM encoding to represent arbitrarily many nearby agents.

  • Results

    The proposed algorithm outperforms the previous approach in simulation as the number of agents increases and is demonstrated on a robot navigating among pedestrians without 3D Lidar.

  • Takeaways & Limitations

    The results support learning collision-avoidance structure without explicitly enforcing other agents’ behavior and using LSTM to encode many agent states into a fixed-length representation.

Abstract

from arXiv · show

Robots that navigate among pedestrians use collision avoidance algorithms to enable safe and efficient operation. Recent works present deep reinforcement learning as a framework to model the complex interactions and cooperation. However, they are implemented using key assumptions about other agents' behavior that deviate from reality as the number of agents in the environment increases. This work extends our previous approach to develop an algorithm that learns collision avoidance among a variety of types of dynamic agents without assuming they follow any particular behavior rules. This work also introduces a strategy using LSTM that enables the algorithm to use observations of an arbitrary number of other agents, instead of previous methods that have a fixed observation size. The proposed algorithm outperforms our previous approach in simulation as the number of agents increases, and the algorithm is demonstrated on a fully autonomous robotic vehicle traveling at human walking speed, without the use of a 3D Lidar.

I. INTRODUCTION

This work targets decentralized collision avoidance among dynamic, decision-making agents whose behaviors, intents, and policies are only partially observable. It removes assumptions about fixed behavior models and uses LSTM-based encoding to handle arbitrarily many nearby agents.

  • Motivation: Pedestrians are moving obstacles that continually make decisions a robot can only partially observe.Without communication, their belief states, policies, and intents are not directly measurable but may be inferred.
  • Limitations of prior work: Existing learning-based methods assume properties such as agent homogeneity or a specific short-timescale motion model.
  • Contributions: The proposed collision-avoidance policy does not assume that other agents follow any particular behavior model.
  • Contributions: LSTM cells encode a varying number of agent states into a fixed-length vector, enabling decisions based on an arbitrary number of nearby agents.This addresses the fixed-dimension input required by typical feedforward networks.
  • Contributions: The work evaluates the framework in simulation and demonstrates it on a robot navigating among pedestrians without a 3D Lidar.

B. Collision Avoidance with Deep RL (CADRL)

CADRL formulates multi-agent collision avoidance as a reinforcement-learning problem with partially observable neighbor states and unknown transition dynamics. Previous methods approximate an optimal value function while relying on propagated states and constant-velocity assumptions that create a timestep tradeoff.

  • Problem formulation: The agent state combines observable position, velocity, and radius with hidden goal position, preferred speed, and orientation; actions specify speed and heading angle.
  • Problem formulation: The policy minimizes expected time to goal while avoiding collisions, using rewards for reaching the goal and penalties for collisions.
  • CADRL approach: Previous approaches learn an approximation of the optimal value function for each joint configuration, then derive actions by evaluating propagated next states.
  • Problem formulation: Because other agents’ policies and intents are unknown, the state-transition dynamics are also unknown.
  • CADRL limitations: Previous approaches assume other agents continue at constant velocity during propagation, neglecting reactions and cooperation in multi-agent interactions.
  • CADRL limitations: The timestep ∆t must be large enough to avoid numerical noise but is experimentally set to 1 sec because smaller or larger values prevent training convergence.

C. Policy-Based Learning

The method uses A3C to jointly learn value and policy functions for collision avoidance, with asynchronous parallel experience generation and GPU-efficient batching.

  • C. Policy-Based Learning: A3C uses a single deep neural network to approximate both the value function and policy function.Training uses separate loss terms for the value and policy outputs.
  • C. Policy-Based Learning: The value loss trains the network’s value output to match the future discounted reward estimate.
  • C. Policy-Based Learning: The policy loss penalizes high-probability actions with lower-than-predicted returns and encourages exploration through entropy regularization.The entropy term is controlled by tunable constant β.
  • C. Policy-Based Learning: A3C simulates many environment-interaction threads in parallel and fuses their experiences to train the policy.
  • C. Policy-Based Learning: GA3C accelerates A3C through GPU batching and queues for training experiences and action predictions.The implementation modifies learning to account for lag introduced by queuing.

A. GA3C-CADRL

GA3C-CADRL maps an agent’s observation to an action distribution using its own state and an LSTM encoding of nearby agents, then outputs value and policy estimates.

  • A. GA3C-CADRL: GA3C-CADRL maps an agent’s environmental observation to a probability distribution over actions in a local coordinate frame.The observation separates the agent’s own information from information about other world objects.
  • A. GA3C-CADRL: The agent’s distance to its goal is defined as dg = ||pg − p||2.
  • A. GA3C-CADRL: The action space contains 11 discretized combinations of speed and heading change designed to mimic robotic-vehicle turning constraints.At preferred speed, six headings span ±π/6; lower speeds use three heading choices.
  • A. GA3C-CADRL: The sparse reward assigns positive reward at the goal, collision penalties, distance-based near-collision rewards, and zero reward otherwise.Discounting with γ < 1 encourages efficiency instead of using a step penalty.
  • A. GA3C-CADRL: GA3C-CADRL trains on mixed experiences from multiple agents, while excluding experiences from agents using other policies.The network outputs a scalar value function and a discrete action policy after encoding other agents with the LSTM.

B. Handling a Variable Number of Agents

The framework handles variable numbers of nearby agents by processing their observable states as an LSTM sequence and converting them into a fixed-length world representation.

  • B. Handling a Variable Number of Agents: Recurrent neural networks accept arbitrary-length input sequences and produce fixed-size outputs, unlike typical fixed-input feedforward networks.
  • B. Handling a Variable Number of Agents: The method treats the variable number of other-agent observable-state vectors as a non-time-dependent LSTM input sequence.This applies LSTM sequence encoding to the state of the world rather than to temporal motion data.
  • B. Handling a Variable Number of Agents: In practice, TensorFlow’s LSTM implementation requires a known maximum sequence length, which can exceed the expected number of agents.An example maximum sequence length is 20 agents.
  • B. Handling a Variable Number of Agents: The LSTM processes each nearby agent state sequentially, updating hidden states until the final state encodes the world into a fixed-length vector.
  • B. Handling a Variable Number of Agents: Agent states are fed in reverse distance order so that the closest agents, processed last, have the greatest effect on the final hidden state.
  • B. Handling a Variable Number of Agents: The final hidden state is concatenated with the agent’s own state before two fully connected layers produce value and discrete policy outputs.Backpropagation updates the LSTM weights to learn the representation of variable numbers of agents.

C. Training the Policy

Training initializes GA3C-CADRL through supervised learning, then improves collision avoidance with reinforcement learning in increasingly crowded simulated scenarios.

  • C. Training the Policy: The previous CADRL and SA-CADRL methods relied on forward propagation of other agents’ states, which required tuning but did not represent their true behaviors.The new GA3C-CADRL formulation removes forward propagation and learns both policy and value functions.
  • C. Training the Policy: Supervised initialization converges in less than 5 minutes using CADRL-generated state-action-value pairs and combined value and policy losses.The initialization dataset is publicly released.
  • C. Training the Policy: After supervised initialization, the policy reaches goals reliably without interactions but still performs poorly in collision avoidance.
  • C. Training the Policy: The reduced structure and joint policy-value learning distinguish GA3C-CADRL from CADRL, whose initialization was sufficient to learn a policy comparable to reaction-based methods.The policy output has an order of magnitude higher dimensionality than the scalar value function.
  • C. Training the Policy: Reinforcement-learning experiences come from random multi-agent scenarios containing non-cooperative, zero-velocity, and learned-policy agents.Only experiences from agents using the learned GA3C-CADRL policy are returned to training.
  • C. Training the Policy: The policy is trained first with 2–4 agents and then with 2–10 agents after convergence, rather than fixing the maximum agent count beforehand.

IV. RESULTS

The multi-agent LSTM network converges through staged reinforcement learning, reaching high average reward while requiring substantially more episodes than the previous approach. Its single-state query is also much faster than the earlier networks.

  • Computational efficiency: 0.4-0.5ms per query is approximately 20x faster than the previous networks.The query uses only the current state vector, and a GPU is not required for fast execution.
  • Training convergence: About 2 · 10^6 episodes and 12 hours were required for the multi-agent LSTM network to converge.Training used an NVIDIA GTX1060 graphics card and a low learning rate for stable training.
  • Training performance: Average reward increased from 0.15 after initialization to 0.90 after RL phase 1, then converged at 0.93 after RL phase 2.When phase 2 began, average reward initially dropped to 0.85 as the domain expanded from 4 to 10 agents.
  • Reward interpretation: Average reward below 1 indicates that some collisions or other penalized behavior remain after convergence.Reward measures success or failure but excludes the discount factor, so it does not indicate time efficiency.
  • Training configuration: The reported training configuration used Lr = 2 · 10−5, β = 1 · 10−4, γ = 0.97, bs = 100, and Adam.These are the key parameter values listed for the deep neural networks.

B. Simulation Results

GA3C-CADRL performs comparably to SA-CADRL with few agents and increasingly outperforms it as agent count grows, while accepting arbitrary numbers of agent observations through its LSTM-based representation.

  • 1) n ≤4 agents:: For n ≤4, GA3C-CADRL policies perform comparably to, though slightly worse than, SA-CADRL, whose agents have the lowest average extra time to goal.The difference between GA3C-CADRL-4 and GA3C-CADRL-10 is small in these scenarios.
  • 2) n > 4 agents:: GA3C-CADRL-10 can process all other agents through its LSTM representation, whereas SA-CADRL accepts only the nearest 3 agents’ states.GA3C-CADRL-4 remains implementable when n > 4, while SA-CADRL’s input remains limited.
  • 2) n > 4 agents:: 10- and 20-agent circles are successfully navigated by GA3C-CADRL, while several SA-CADRL agents get stuck or collide.These scenarios illustrate behavior that requires considering many agents simultaneously.
  • 2) n > 4 agents:: At n = 6, GA3C-CADRL achieves a 5x reduction in failed cases and a shorter average extra time to goal than SA-CADRL.The performance gain becomes stronger as the number of agents increases; GA3C-CADRL-10 also outperforms the alternatives at n = 8 and n = 10.
  • 2) n > 4 agents:: GA3C-CADRL-10’s success rate remains above 95% for n < 10, whereas SA-CADRL drops below 80%.The n = 10 environment is larger, so it is not necessarily more densely populated than the n = 8 environment.
  • 2) n > 4 agents:: The second RL training phase substantially decreases failed cases and slightly decreases average extra time to goal across n ≤10 environments.The framework retrains after convergence in simpler scenarios using more complex multi-agent scenarios.

C. Hardware Experiment

A GA3C-CADRL policy was deployed on a ground robot that navigated among pedestrians using a compact sensing suite without 3D Lidar, despite increased sensing uncertainty.

  • Perception: The 2D Lidar supports localization and obstacle detection, while cameras support pedestrian classification and obstacle detection.Pedestrian positions and velocities are estimated by clustering 2D Lidar scans and applying a camera-based classifier.
  • Hardware trade-off: Removing 3D Lidar reduces the sensing suite’s price by an order of magnitude but increases uncertainty in the robot’s environmental knowledge.The reduction includes lower perception range and accuracy.
  • Results and scope: The robot safely navigates many challenging pedestrian scenarios, while further work will quantify performance in more complicated environments.The paper does not provide that future performance analysis here.

V. CONCLUSION

The paper presents GA3C-CADRL as a more general collision-avoidance framework that handles unknown agent dynamics and variable agent counts, and demonstrates it in simulation and on a robot.

  • Conclusion: GA3C-CADRL learns collision avoidance with deep reinforcement learning without requiring knowledge of other agents’ dynamics.The framework is trained in simulation.
  • Conclusion: An LSTM at the network input encodes observations of an arbitrary number of nearby agents into a fixed-length world representation.This supports action selection when the number of observed agents varies.
  • Conclusion: The approach outperforms the existing method as the number of agents grows and navigates among pedestrians on a small ground robot without 3D Lidar.The robot is shown traveling at human walking speed.
Loading 1805.01956v1…