PaperlayerView exact revision on arXiv

Source-linked AI summary

Reinforcement Learned Distributed Multi-Robot Navigation with Reciprocal Velocity Obstacle Shaped Rewards

Ruihua Han, Shengduo Chen, Shuaijun Wang, Zeqing Zhang, Rui Gao, Qi Hao, Jia Pan

arXiv:2203.10229v1cs.RO

TL;DR

Multi-robot navigation must choose safe, efficient velocities with limited information about interactive obstacles. The paper combines VO/RVO state representations, a BiGRU policy, and risk-aware rewards trained with DRL, and reports better success rate, travel time, and average speed than compared methods.

  • Problem

    Reliable collision avoidance and optimal velocity selection remain challenging for distributed robots with limited sensing and varying numbers of surrounding robots.

  • Method

    The approach uses sequential VO/RVO vectors, a BiGRU network for continuous velocity actions, and an RVO-area and expected-collision-time reward trained with PPO.

  • Results

    The policy outperforms state-of-the-art and learning-based comparisons in success rate, travel time, and average speed across complex multi-robot scenarios.

  • Takeaways & Limitations

    RVO-based representations, BiGRUs, and risk-aware rewards support reciprocal collision-avoidance behavior and a trade-off between collision risk and travel time.

Abstract

from arXiv · show

The challenges to solving the collision avoidance problem lie in adaptively choosing optimal robot velocities in complex scenarios full of interactive obstacles. In this paper, we propose a distributed approach for multi-robot navigation which combines the concept of reciprocal velocity obstacle (RVO) and the scheme of deep reinforcement learning (DRL) to solve the reciprocal collision avoidance problem under limited information. The novelty of this work is threefold: (1) using a set of sequential VO and RVO vectors to represent the interactive environmental states of static and dynamic obstacles, respectively; (2) developing a bidirectional recurrent module based neural network, which maps the states of a varying number of surrounding obstacles to the actions directly; (3) developing a RVO area and expected collision time based reward function to encourage reciprocal collision avoidance behaviors and trade off between collision risk and travel time. The proposed policy is trained through simulated scenarios and updated by the actor-critic based DRL algorithm. We validate the policy in complex environments with various numbers of differential drive robots and obstacles. The experiment results demonstrate that our approach outperforms the state-of-art methods and other learning based approaches in terms of the success rate, travel time, and average speed. Source code of this approach is available at https://github.com/hanruihua/rl_rvo_nav.

I. INTRODUCTION

Distributed multi-robot navigation lets robots decide independently with limited information, but reliable collision avoidance and optimal velocity selection remain challenging. The paper combines VO representations, BiGRUs, and RVO-based rewards within DRL to address these challenges.

  • Motivation: Distributed systems let robots decide independently from onboard sensing, supporting deployment of many robots with relatively low computational cost.Their central challenge is reliable collision avoidance with limited sensing and efficient velocity selection.
  • Related approaches: Existing trajectory-planning methods can require substantial computation as time discretization becomes finer, while direct velocity methods seek lower-cost collision-free navigation.Potential-field approaches use attraction and repulsion concepts to identify collision-free, time-efficient velocities.
  • Related approaches: VO methods predict collision regions, whereas DRL methods learn actions from structured environment states using manually designed rewards.DRL can incorporate multiple steps of experience into navigation decisions.
  • Open challenges: DRL multi-robot navigation still requires interaction-aware state representations, efficient sequential-state-to-action mappings, and suitable reward designs.The paper identifies these as three central development challenges for fully functional systems.
  • Proposed approach: The proposed approach represents robots and obstacles with RVO and VO vectors, uses a BiGRU network for continuous actions, and designs rewards from collision geometry and expected collision time.These components target reciprocal collision avoidance under limited surrounding information.

A. Reciprocal Velocity Obstacle

VO and RVO provide geometric foundations for collision avoidance, while DRL supplies learned decision-making for complex environments. The paper combines these ideas with an RVO-area and expected-collision-time reward to encourage reciprocal behavior.

  • Geometric foundations: VO methods define velocity regions associated with potential collisions, while RVO extends this framework to reciprocal avoidance among robots.RVO assumes robots use similar policies and share the avoidance effort.
  • Geometric foundations: ORCA and NH-ORCA impose velocity-space constraints, but their perfect-sensing assumption limits real-world performance.NH-ORCA additionally incorporates non-holonomic kinematic constraints.
  • Learning-based methods: DRL collision-avoidance methods use training experience to address complex scenarios with high efficiency and robustness.Agent-level methods use environment models rather than raw sensor data, improving computational efficiency and flexibility.
  • Learning-based methods: Variable numbers of surrounding robots challenge fixed-dimensional networks, while recurrent methods may emphasize later sequence elements in dense environments.SARL uses attention to infer obstacle importance but does not emphasize reciprocal collision-avoidance interactions.
  • Reward design: The reward uses RVO or VO areas and expected collision time to represent collision risk and encourage reciprocal collision-avoidance behavior.This design also targets a trade-off between collision risk and travel time.
  • System framework: The system represents surrounding robots with RVO vectors and static obstacles with VO vectors, then trains the policy with PPO.The policy outputs velocity increments for differential-drive robots navigating without inter-robot communication.

B. Reciprocal Velocity Obstacle

VO defines collision-inducing velocity sets for dynamic agents and static obstacles, while RVO shifts this construction to model reciprocal avoidance. Both are encoded as compact vectors for cooperative velocity selection.

  • VO construction: For disc-shaped robots, VO is constructed from relative positions, velocities, and radii to represent velocities that may cause collision within a period.The formulation uses a ray and Minkowski sum to construct the collision region.
  • VO construction: A robot avoids collision by selecting a velocity outside the relevant VO area.The same geometric definition represents static line obstacles, although blocked goal paths require global navigation.
  • RVO construction: RVO extends VO for active reciprocal avoidance among robots by translating the VO area so its apex reflects both agents’ velocities.This geometric shift distributes avoidance effort between the interacting robots.
  • Unified representation: VO and RVO areas are encoded as six-dimensional vectors containing an apex and the directions of left and right boundary rays.Each robot selects a velocity outside the joint VO and RVO areas to avoid collisions cooperatively.

C. Problem Statement

The problem is to select velocity sequences that minimize travel time while maintaining collision separation for differential-drive robots with limited sensing. The policy maps proprioceptive and obstacle-related observations to velocity increments independently for each robot.

  • Optimization objective: Multi-robot collision avoidance is formulated as minimizing travel time subject to collision-avoidance constraints.The setting contains n differential-drive robots navigating a shared workspace.
  • Observations: Each robot senses a limited number of neighboring robots, and its observation combines ego-state measurements with surrounding-environment measurements.The ego state includes velocity, orientation, desired velocity, and collision-avoidance radius.
  • Observations: The surrounding observation contains RVO vectors, relative distances, and reciprocal expected collision times for neighboring robots or obstacles.The reciprocal collision-time value avoids an infinite representation when collision is impossible.
  • Policy and constraints: The policy outputs velocity increments that update each robot’s velocity and position while enforcing separation from neighboring collision radii.The desired result is a collision-free velocity close to the robot’s desired velocity.
  • Policy and constraints: All robots share one navigation policy but independently compute their optimal velocities.This preserves the distributed nature of the control problem.

IV. REINFORCEMENT LEARNING FRAMEWORK

The framework maps observations of self and surrounding agents into velocity-based actions using an actor-critic architecture. A bidirectional GRU handles variable-length obstacle sequences, while the action is converted into feasible translational and rotational control.

  • The actor maps observed information to robot actions, while the critic evaluates those actions using the reward function.
  • The observation combines proprioceptive measurements with exteroceptive measurements from surrounding agents.
  • The action is a planar velocity increment, and the next velocity is clipped between minimum and maximum bounds.
  • Non-holonomic robots use translational and rotational velocities, obtained by converting the orthogonal velocity command.
  • The bidirectional GRU processes variable-length inputs in forward and backward directions to form a fixed-size representation.
  • The actor outputs a two-dimensional velocity mean and samples actions from a Gaussian distribution, while the critic estimates Vψ(o).

C. Reward Function

The reward evaluates selected velocities using their relation to the joint RVO area, desired velocity, and expected collision time. Its tunable terms balance motion efficiency with collision risk.

  • The RVO reward is designed because distance-based rewards are improper when observations omit positions and velocities directly.
  • Expected collision time ξ captures collision risk using distance-to-obstacle and relative velocity under the current velocity.
  • The reward represents the quality of selected velocity vt according to the joint RVO area.
  • Velocities outside the RVO area are rewarded according to their distance from the desired velocity, while velocities inside it receive risk-dependent terms.
  • Membership in the RVO area is judged from the selected velocity and the boundary vectors using cross-product inequalities.
  • The constants a, b, c, d, e, and f are tunable; b weights desired-velocity deviation, while d and e weight inverse expected collision time.

V. POLICY TRAINING

The policy is trained with PPO in a distributed actor-critic loop. Robots collect observations, rewards, and actions, store them in buffers, and update actor and critic objectives iteratively.

  • PPO trains and successively updates the multi-robot collision-avoidance policy for continuous action spaces.
  • Each robot runs the policy for T timesteps while collecting observations, rewards, and actions for training.
  • Buffered data are used to estimate advantages, construct the clipped surrogate and value losses, and optimize them with Adam.
  • The policy actor and critic parameters are initialized before repeated data collection and policy-update cycles.

A. Simulation Setup

The policy is trained in simulated multi-robot scenarios and evaluated across circle, random, and corridor configurations. The setup limits each robot’s sensing range and neighbor inputs in the training scenario.

  • The simulations are developed with OpenAI Gym, and the RL-RVO policy is implemented in PyTorch.
  • Training uses disc-shaped robots in the circle scenario, with robots uniformly arranged around a circle and goals placed on the opposite side.
  • In training, each robot’s sensing range is 4m and its maximum number of input neighbors is 5.
  • The circle, random, and corridor scenarios provide distinct simulated configurations for multi-robot navigation.

1) Metrics:

The evaluation compares four policies across success rate, travel time, average speed, and computational cost in circle and random scenarios with varying robot counts. The proposed policy remains more effective in crowded settings and uses less computational cost than the learning-based comparators.

  • The evaluation measures success rate, travel time, and average speed, while Fig. 5 compares the average computational cost required for one control action.
  • Success rate and average speed decrease while travel time increases as the number of robots grows.
  • In circle scenarios, the proposed policy achieves the highest success rate and average speed and the lowest travel time, especially when robots are crowded.
  • In random scenarios, the proposed policy performs better in various dense situations and remains more robust and efficient under limited information.
  • The ablation study compares RL-RVO with RL-NRVO, RL-LSTM, and RL-Reward across circle, random, and corridor scenarios.

4) Real-world experiments:

Real-world experiments deploy the policy on up to eight differential-drive Turtlebots arranged on a circle with random orientations. Across 50 cases, the policy is compared with NH-ORCA and achieves higher success with less travel time despite real-world uncertainties.

  • The real-world experiments use up to 8 differential-drive Turtlebots arranged along a circle with random orientations.
  • Each Turtlebot computes velocity locally, receives exteroceptive measurements through ROS, and operates with a maximum velocity of 1m/s.
  • Because GA3C-CADRL and SARL have high computational cost, the real-world comparison uses NH-ORCA with 4, 6, and 8 Turtlebots.
  • Across 50 cases, the proposed policy has a better success rate and takes less travel time than NH-ORCA for the same navigation tasks.
  • The paper evaluates the policy through simulated and real-world experiments, including component ablations and comparisons of success rate, travel time, and average speed.
Loading 2203.10229v1…