Decentralized Multi-Robot Navigation for Autonomous Surface Vehicles with Distributional Reinforcement Learning

Reliable collision avoidance is crucial to the deployment of Autonomous Surface Vehicles (ASV), which is still a challenging problem [1], especially in congested environments. The Convention on the International Regulations for Preventing Collisions at Sea (COLREGs) [2] defines rules for collision avoidance between vessels, which have been used to develop obstacle avoidance solutions in multi-ASV navigation scenarios [3, 4, 5, 6]. However, following COLREGs may cause conflicting actions when the roles of each ego vehicle with respect to different neighboring vehicles are in conflict, especially in congested waters [7]. In addition to the risk of collision with other vehicles, static obstacles that exist in the marine environment, such as buoys or rocks, may pose threats to navigation safety. To avoid collision with them, an ASV may need to maneuver in a way that does not comply with COLREGs, which primarily consider the relationship to nearby vehicles. Additionally, the motion of marine autonomous vehicles is affected by current flows [8], thus following COLREGs may not always be safe when navigating in strong current. The objective of this work is to develop a safe decentralized ASV collision avoidance policy for the multi-ASV navigation problem in congested marine environments where unknown static obstacles and currents exist.

Deep Reinforcement Learning (DRL) combines the ability of Reinforcement Learning to adapt to unknown environments through trial-and-error learning [9] with the strong representation capability of deep neural networks, and has been applied to various robotics control problems, including to ASVs [10, 11]. Different from DRL that aims to learn the expected return of actions, Distributional Reinforcement Learning (Distributional RL) learns return distributions [12], enabling the deployment of risk-sensitive policies by distorting return distributions with risk measures [13] for enhanced safety performance.

Building on our previous work on single ASV sensor-based navigation with Distributional RL [14], we propose a Distributional RL based policy for decentralized multi-ASV collision avoidance with the following contributions: (1) We design a policy network structure that encodes interaction relations among the ego vehicle, static obstacles and other vehicles, and develop a decentralized multi-agent training framework that induces a coordinated collision avoidance policy by parameter sharing among training agents. (2) The proposed policy based on Distributional RL is compared against a traditional DRL policy and classical methods, including Artificial Potential Fields (APF) and Reciprocal Velocity Obstacles (RVO), in simulation experiments. The results indicate that the proposed framework achieves the highest success rate over all levels of environmental complexity, with nearly the smallest amount of travel time and energy cost. When equipped with a proposed variant of our algorithm that automatically adapts risk sensitivity, the navigation safety of the proposed policy can be clearly improved in highly congested environments. (3) Our approach has been made freely available at https://github.com/RobustFieldAutonomyLab/Multi_Robot_Distributional_RL_Navigation.

Traditional non-RL-based methods are widely used to solve the problem of navigating multiple robots in a decentralized manner. Since the original proposal of using Artificial Potential Fields (APF) in mobile robot navigation [15], it has also been used in multi-robot scenarios, by considering other robots as moving obstacles and generating repulsive forces according to their positions and velocities [16, 17]. Fiorini et al. [18] applied the concept of Velocity Obstacles to the dynamic obstacle avoidance problem, which identifies the set of velocities leading to future collisions with moving obstacles. Reciprocal Velocity Obstacles (RVO) [19, 20] and Optimal Reciprocal Collision Avoidance (ORCA) [21, 22] improved the performance of velocity obstacle methods on the multi-robot navigation problem by selecting velocities that exhibit reciprocal obstacle avoidance behaviors. Kim et al. [23] proposed to predict the future motion of neighboring agents with past observations of them by Ensemble Kalman Filtering, showing the robustness of the method to noisy, low-resolution sensors, and missing data. To solve the freezing robot problem when navigating in cluttered environments, Trautman et al. [24, 25] modeled the interactions among agents with Gaussian processes to achieve cooperative navigation.

Decentralized multi-agent collision avoidance solutions based on Deep Reinforcement Learning (DRL) have been developed in recent years. Chen et al. [26, 27] proposed DRL based methods that aim at minimizing the expected time to goal while avoiding collisions, and can show socially aware behaviors in pedestrian-rich environments. Everett et al. [28] deal with varying numbers of observed agents by using long short-term memory (LSTM) structures, which improves the policy performance when the number of agents increases. Long et al. [29] employed a centralized learning and decentralized execution framework that trains agents capable of navigating in complex environments with a large number of robots. Chen et al. [30, 31] modeled the higher-order interactions among agents, which consider not only the direct interactions between the ego agent and other agents, but also the indirect effects of interactions among other agents on the ego agent. In addition to the observations of other agents, Liu et al. [32] included an additional occupancy grid map or an angular map to encode static obstacle information, improving navigation performance in environments cluttered with static obstacles. Han et al. [33] trained DRL agents that exhibit reciprocal collision avoidance behaviors by designing a reward function based on RVO.

Compared to DRL, Distributional RL methods capture return distributions instead of only the expected return [12], and these methods have been used to train risk-sensitive agents for a variety of navigation tasks [34, 35, 36, 37, 14] in recent years. These works focus on the single robot navigation problem in environments with static obstacles or dynamic obstacles moving along pre-defined trajectories. We explore the application of Distributional RL to the decentralized multi-robot navigation problem in this paper.

Multiple robots are required to navigate in a simulated marine environment with no prior information describing current flows and static obstacles. At each time step $t$, each robot receives an observation of its own state, and of the states of static obstacles and other robots within the detection range, which can be expressed as a combined state vector $\mathbf{s}_{t}=[\mathbf{s}_{ego}^{t},\mathbf{s}_{static}^{t}.\mathbf{s}_{dynamic}^{t}]$, where $\mathbf{s}_{ego}$ contains the goal position and ego velocity, $\mathbf{s}_{static}$ contains the position and radius of detected obstacles, and $\mathbf{s}_{dynamic}$ contains the position and velocity of other detected robots.

The pose of each robot can be represented as $(x,y,\theta)$, where $(x,y)$ are the global Cartesian coordinates of the robot, and $\theta$ is its orientation. As shown in Fig. 1, $\mathbf{s}_{t}$ is expressed in the robot frame. The objective is to obtain a policy $\pi(\mathbf{s})$ that minimizes the expected travel time to a specified goal, while avoiding collisions with static obstacles and other robots.

In the above formula, $\mathbf{p}_{s}=[p_{sx},p_{sy}]$, $\mathbf{p}_{d}=[p_{dx},p_{dy}]$,$r_{rob}$ is the collision radius of the robot, and the robot is considered to reach its goal if its Euclidean distance to the goal is within the threshold $d_{thres}$.

The simulation environment we use is similar to our prior work [14]. The Rankine vortex model [38] is utilized to simulate current flows, where the angular velocity of the vortex core $\Omega=\Gamma/(2\pi r_{0}^{2})$.

The kinematic model described in [39] is used to model the effect of current flow on robot motion.

$\mathbf{V}(t)$ is the total velocity of the robot, $\mathbf{V}_{C}(\mathbf{X}(t))$ is the current flow velocity at robot position $\mathbf{X}(t)$, and $\mathbf{V}_{S}(t)$ is the robot steering velocity. The robot action at time step $t$ is $\mathbf{a}_{t}=(a_{t},w_{t})$, where $a$ is the rate of change in the magnitude of $\mathbf{V}_{S}(t)$, and $w$ is the rate of change in the direction of $\mathbf{V}_{S}(t)$. Then the navigation policy can be expressed as $\pi:\mathbf{s}\rightarrow(a,w)$. Linear acceleration $a$ and angular velocity $w$ may be selected as follows: $a\in\{-0.4,0.0,0.4\}\text{ m}/\text{s}^{2}$, and $w\in\{-0.52,0.0.0.52\}\text{ rad}/\text{s}$. The forward speed is clipped to $[0,v_{max}]$.

We evaluate the performance of two randomly selected IQN and DQN models, as well as baseline approaches which will be introduced as follows, on two sets of simulation experiments. The first set of experiments purely focuses on dynamic obstacle avoidance and does not contain any static obstacles. 500 randomly generated environments of different levels of difficulty (100 per level) are used. The number of robots range from 3 to 7, and the number of vortices range from 4 to 8. The start and goal of each robot are randomly generated such that the distance is at least 40.0 meters. In the second set of experiments, static obstacles are also included when creating 500 evaluation environments, where the number of static obstacles ranges from 4 to 8. If not all robots successfully reach their goals within 3 minutes, the test episode is considered failed. The energy consumption of a robot in an experiment episode is computed by summing up the magnitude of all actions executed during the process.

In addition to the greedy policy, we also test the risk sensitive policy used in our prior work [14], which adapts the CVaR threshold $\phi$ according to the distance to obstacles.

$X$ is the position of the ego robot, and $X_{O}$ are the positions of all obstacles and other robots.

In addition to IQN and DQN, we also evaluate the performance of two classical methods. Fan et al. [17] designed an improved Artificial Potential Field (APF) method to deal with both static and dynamic obstacles. The attractive potential field $U_{\text{att}}$ creates a force that drives the ego robot to the goal.

The repulsive potential field $U_{\text{rep1}}$ creates a repulsive force to avoid colliding with static obstacles.

For dynamic obstacles, an additional repulsive field based on the relative velocity to the ego robot is used.

In the above equations, $X$, $X_{g}$, $X_{o}$, and $X_{r}$ are positions of the robot, goal, static and dynamic obstacles respectively, and $v_{ao}$ is the relative velocity component in the direction from the ego robot to the dynamic obstacle. We use $k_{\text{att}}=50.0$, $k_{\text{rep}}=500.0$, $k_{\text{v}}=1.0$, and $n=2$. The total force $F=-\nabla U_{\text{att}}(X)-\nabla U_{\text{rep1}}(X)-\nabla U_{\text{rep2}}(X,V)$. As in our implementation of APFs in previous work [14], we choose the angular velocity that results in the closest alignment with vector $F$ in a single control step, and we choose the linear acceleration closest to the scaled component of $F$ in the direction of robot velocity, as the control action.

Van den Berg et al. [19] proposed Reciprocal Velocity Obstacles (RVO). For disc-shaped robots $A$ and $B$, the velocity obstacle $VO^{A}_{B}(\mathbf{v}_{B})$ is the set of velocities of $A$, $\mathbf{v}_{A}$, that will lead to collision with $B$ moving at velocity $\mathbf{v}_{B}$. Denote a ray starting at $\mathbf{p}$ and pointing in the direction of $\mathbf{v}$ as $\lambda(\mathbf{p},\mathbf{v})=\{\mathbf{p}+t\mathbf{v}|t\geq 0\}$, then $VO^{A}_{B}(\mathbf{v}_{B})$ can be expressed in Equation (23), where $\oplus$ is the Minkowski sum, and -$A$ refers to $A$ reflected about its reference point.

To solve the problem of oscillatory motions when choosing the velocity that avoids the $VO$s created by other robots, $RVO$ is introduced, which translates the apex of $VO^{A}_{B}(\mathbf{v}_{B})$ to $({\mathbf{v}}_{A}+{\mathbf{v}}_{B})/2$. Since no passively moving obstacles exist in our problem, the combined reciprocal velocity obstacle for each robot is the union of all the $RVO$s generated by other robots and the $VO$s generated by static obstacles.

The velocity $\mathbf{v}^{\prime}_{i}$ that minimizes the penalty function (25) is chosen to be the next velocity of robot $i$.

We use $w_{i}=0.2$ for all robots, and set $\mathbf{v}_{i}^{\text{pref}}$ as the velocity of maximum robot speed, with heading directed towards its goal. $tc_{i}(\mathbf{v}^{\prime}_{i})$ is the expected time to collision with the robot’s combined reciprocal velocity obstacle, and $AV^{i}$ is the set of admissible velocities. Similar to our application of APFs, we choose the angular velocity that results in the closest alignment with vector $\mathbf{v}^{\prime}_{i}$ in a single control step, and we choose the linear acceleration leading to the speed closest to that of $\mathbf{v}^{\prime}_{i}$ in a single control step, as the control action. The RVO agent of our work is based on the implementation in [41], which can be conveniently integrated into our simulation environment used in this study.

Our experimental results are summarized in Fig. 5. Adaptive IQN achieves the highest success rates across different levels of environment complexity, while consuming nearly the minimum amount of travel time and energy needed to reach goals. Fig. 6 and Fig. 7 visualize an experiment episode where seven robots, eight vortices and eight static obstacles exist. In the left plot of Fig. 6, robot 2 faces several static obstacles on the left and three robots coming from the right, while its goal is basically in the direction of its current speed. With a higher risk sensitivity, the adaptive IQN agent chooses to turn left to avoid getting into a more congested state with higher collision risk, while the greedy IQN agent would keep moving in the current direction towards the goal. Subsequently, after robot 2 turns left, robot 3 faces head-on collision risk with robot 2, and the adaptive IQN agent directs robot 3 to turn left in this instance to get away from the head-on situation. In comparison, Fig. 7 shows that greedy IQN failed in this episode due to the collision between robot 0 and robot 2. Thus, adaptive IQN can effectively enhance the safety in congested environments, which is shown as the increase in the difference of success rate between adaptive IQN and greedy IQN, while keeping the travel time and energy consumption small. It can be seen from Fig. 5 that DQN requires the minimum travel time and energy cost in its successful episodes, and its planned trajectories are straight compared to that of other methods. This evidence indicates the greedy nature of DQN, the success rate of which drops significantly as the environment becomes more complex. APF and RVO are vulnerable to current disturbances of robot motions, which cause the ASVs to struggle near vortices, and to fall victim to collisions with static obstacles in Fig. 7.

We propose a Distributional RL based decentralized multi-ASV collision avoidance policy, which is deployed in simulated congested marine environments filled with unknown static obstacles and vortical current flows (inspired by the challenges of whitewater rafting). The interactions among decentralized decision making agents as well as with static obstacles are considered in the policy network, which is shared by all agents during training to induce the coordinated avoidance of collisions, and robustness to current disturbances. Compared to traditional DRL, APF and RVO, the Distributional RL policy dominates in navigation safety, which can be further enhanced by adapting the risk sensitivity, while also achieving nearly the minimum amount of travel time and energy consumption.

This research was supported by the Office of Naval Research, grants N00014-20-1-2570 and N00014-21-1-2161.