Decentralized and Communication-Free Multi-Robot
Navigation through Distributed Games

Many multi-robot navigation methods require explicit communication among robots, either to avoid collisions with obstacles by generating a consensus behavior among robots [21] or to calculate a global gradient that controls the overall shape of the multi-robot formation [9]. Several methods have used leader and follower models to navigate a multi-robot system. By controlling the movements of a number of robots, the overall behavior of the system was influenced [22]. A single leader was utilized in [23], basing its movements on influencing nearby naive agents to follow it to goal positions. A single leader was also utilized in [24] and multiple leaders were used in [10], but both required guaranteed connectivity with the leader. A consistent drawback of these models is a required communication, either for centralized control or for knowledge of follower positions in the environment.

Recently, several decentralized methods have been implemented. Graph neural networks have enabled decentralized behavior policies [13, 25], but relied on local communication that allowed information to propagate globally. Graph temporal logic was applied to swarm guidance in order to create policies that scale to large numbers of agents [26], but relies on knowledge of the overall agent distribution. Deep reinforcement learning was used to learn navigation policies around complex obstacles, allowing decentralized policies but requiring full knowledge of the state of the multi-robot system for training [27, 12].

Game theory seeks to explain and analyze the interaction of rational agents accommodating their own preferences and expectations. Modelling systems as games enables agents to analyze actions based on how they impact other agents. Many methods have been designed to find solutions to games, including optimization and reinforcement learning [28, 29, 30]. Game theory has been applied in several multi-robot system applications [31], due to its ability to consider the interaction of multiple agents and their competing motivations.

In autonomous driving, game theory has been applied to the problem of lane changing and merging [18]. Deep reinforcement learning was used to solve two player merging games in [17], which relied on defining drivers as proactive or passive. Roles for two players were also used in [32], which modelled lane changing as a Stackleberg game that has implicit leaders and followers. Multiple drivers were modelled in [33], which solved games through optimization by converting constraints such as collision avoidance to Lagrangian multiplier terms. In addition to lane changing, game theory was also used to generate racing trajectories which would avoid collisions while still competing with other agents [19, 34].

Despite the exploration of game theory in autonomous driving, previous research has mostly been limited to only two player systems (i.e., two cars). Recently, game theory has been applied to several multi-robot scenarios. Many approaches have considered task allocation, both with the requirement of communication [35] and enabling this without communication being necessary [36, 37, 38]. Collision avoidance has been considered, but has required the agents to be capable of communicating with each other [mylvaganam2017differential]. Multi-robot sensing and patrolling has been the other main scenario explored with game theoretic models, but approaches have required prior mappings of the environment [39, 20] or still require communication between agents [40].

Game theoretic models have been used due to their useful ability to model other agents in a system, but have not been theoretically well studied in generating navigational behaviors for a large multi-robot system without the ability to communicate between robots in complex environments.

We consider a multi-robot system consisting of $N$ robots. Each robot has a position $\mathbf{p}\in\mathbb{R}^{d}$, where $\mathbf{p}_{i}$ is the position of the $i$-th robot. At each time step $t$, each robot makes a decision to take an action $\mathbf{a}_{i}^{t}$ and update its position. We define a goal $\mathbf{g}\in\mathbb{R}^{d}$ that is the position that the multi-robot system is attempting to navigate to, which is known to each robot. This goal can be stationary (e.g., a fixed location in the environment) or dynamic (e.g., a moving human whom the multi-robot system must follow). We define the multi-robot system to have reached the goal state when $\|\mathbf{p}_{+}-\mathbf{g}\|_{2}<T$, where $\mathbf{p}_{+}$ is the geometric center of the robot system and $T$ is a distance threshold.

We define an ideal interaction distance $R$ between robots, where if $\|\mathbf{p}_{i}-\mathbf{p}_{j}\|_{2}\ll R$ then the $i$-th and $j$-th robots are at risk of collision (with the collision risk rising as $\mathbf{p}_{i}$ approaches $\mathbf{p}_{j}$) and if $\|\mathbf{p}_{i}-\mathbf{p}_{j}\|_{2}\gg R$ then there is a risk of losing cohesion between robots $i$ and $j$ (with this risk rising as $\mathbf{p}_{i}$ moves further away from $\mathbf{p}_{j}$). Successful cohesion in the multi-robot system results from maintaining $\|\mathbf{p}_{i}-\mathbf{p}_{j}\|_{2}=R\;\forall\>i,j\in\{1,\dots,N\},i\neq j$. Finally, we consider a set of $O$ obstacles in the environment. Robots should take actions such that $\|\mathbf{p}_{i}-\mathbf{o}_{j}\|_{2}>0$, so as to avoid collisions with obstacles. We assume each robot is able to locally perceive neighboring robots and obstacles.

Then, we formulate the problem of multi-robot navigation with multiple distributed and differentiable simultaneous strategic games $\mathcal{G}=\{\mathcal{N},\mathcal{X},\mathcal{J}\}$, where each robot is the main player of a game based on its local environment. Each game is simultaneous as the robot plays its game at each time step without knowledge of how other robots will move. Each game is also strategic, where players are unable to coordinate through explicit communication. $\mathcal{N}$ represents the set of players, where the cardinality of $\mathcal{N}$ is denoted as $N^{\prime}$. This set of players is defined as the main player robot and the neighboring robots within sensing distance. $\mathcal{X}=\{X_{1},\dots,X_{N^{\prime}}\}$ represents the strategy set for game $\mathcal{G}$, where $X_{i}$ represents the set of available strategies of the $i$-th player. We define a strategy $\mathbf{x}_{i}\in X_{i}$ to be a movement update available to the $i$-th robot given $\mathbf{p}_{i}$ and actions $\mathbf{a}_{i}$

where $\mathbf{a}_{i}$ satisfies $\|\mathbf{a}_{i}\|_{2}=1$ and $\alpha$ is a hyperparameter controlling the importance of the action. Values of $\alpha$ are discussed later in the paper when consider the theoretical aspects of the games.

We define $\mathcal{J}=\{J_{1}(\mathbf{x}_{1},\mathbf{x}_{-1}),\dots,J_{N^{\prime}}(\mathbf{x}_{N^{\prime}},\mathbf{x}_{-N^{\prime}})\}$ as the set of differentiable cost functions that govern the action of each player, where $\mathbf{x}_{i}$ is the strategy of the $i$-th player and $\mathbf{x}_{-i}$ is the strategy set of all other players, i.e. $\mathbf{x}_{-i}=(\mathbf{x}_{1},\dots,\mathbf{x}_{i-1},\mathbf{x}_{i+1},\dots,\mathbf{x}_{N^{\prime}})$. Each player is assumed to be rational, i.e., each player will select a strategy $\mathbf{x}_{i}$ that minimizes its cost function $J_{i}(\mathbf{x}_{i},\mathbf{x}_{-i})$, while expecting that every other player is selecting strategies in $\mathbf{x}_{-i}$ that minimize their own cost functions. We denote the optimal strategy for player $i$ as $\mathbf{x}_{i}^{*}$ and the optimal strategies for the other players as $\mathbf{x}_{-i}^{*}$. The formulated cost function common to each player is defined as:

where $C_{i}(\mathbf{x}_{i},\mathbf{x}_{-i})$ represents a cost related to cohesion with other players within sensing distance, which can be defined as $C_{i}(\mathbf{x}_{i},\mathbf{x}_{-i})=\sum_{n=1,n\neq i}^{N^{\prime}}\|(\mathbf{x}_{i}-\mathbf{z}_{n})\|_{2}^{2}$, where $\mathbf{z}_{n}$ defines a point that is on the axis between a sensed robot $n$ and robot $i$ and is distance $R$ from robot $n$ (e.g., if the distance between robots is less than $R$, this cost will encourage robot $i$ to move away from robot $n$). This is calculated from the position of robot $i$ using the estimated strategy $\mathbf{x}_{n}$ of the neighboring robot $n$, such that $\mathbf{z}_{n}=R(\mathbf{p}_{i}-\mathbf{x}_{n})/(\|\mathbf{p}_{i}-\mathbf{x}_{n}\|_{2})$.

Hyperparameters $\beta_{1},\beta_{2},\beta_{3}$ balance the different influences and are valued such that $\beta_{1}\geq O\beta_{3}-N^{\prime}\beta_{2}$. $\beta_{1}$ controls the weighting of progress towards the goal. This part of the cost function decreases as the $i$-th robot makes progress towards the goal. $\beta_{2}$ controls the weighting of cohesion with neighboring robots. This cohesion cost is minimized when the $i$-th robot is at a distance $R$ from every neighbor. $\beta_{3}$ controls the weighting of navigating to avoid obstacles. As robots move away from obstacles, this term minimizes the overall cost function.

In order to identify optimal behaviors for each robot, our approach constructs the described game $\mathcal{G}_{i}$ for each robot $i\in\{1,\dots,N\}$ at each time step. Algorithm 1 solves the game required to enable decentralized and communication-free multi-robot navigation. The algorithm identifies the players involved in each game $\mathcal{G}_{i}$, consisting of only the local neighbors of robot $i$, and initializes a null strategy for the main player. Then, it minimizes each neighboring player’s cost function to identify optimal strategies $\mathbf{x}_{-i}^{*}$. From this, it updates the main player’s cost function and identifies the optimal strategy $\mathbf{x}_{i}^{*}$ that minimizes it. When Algorithm 1 converges after iteration, $\mathbf{x}_{i}^{*}$ is adopted as the strategy for robot $i$. In empirical evaluation, Algorithm 1 converges quickly, typically in less than $N^{\prime}$ iterations.

For each game, we have two objectives for the main player (denoted as robot $i$). First, our approach should minimize the cost function $J_{i}(\mathbf{x}_{i},\mathbf{x}_{-i})$ described in Eq. (2), in order to identify the best strategy for this main player. Second, our approach should generate strategies that move in the direction of a Nash equilibrium for the game, or a state where no player can improve their strategy without other players changing their strategies. If every player acts rationally, as we are assuming, then a Nash equilibrium means that robot $i$ has identified a strategy $\mathbf{x}_{i}$ that cannot be improved upon, assuming its expectations of its neighbors’ optimal strategies $\mathbf{x}_{-i}^{*}$ are accurate.

We first evaluated the Obstacle Field scenario seen in Figure 2(a), with quantitative results seen in Figure 3. We see that our full approach completes simulations with the closest to the ideal interaction distance in Figure 3(a), while maintaining it well as time progresses. The $\beta_{3}=0$ approach performs similarly well, as this still considers system cohesion. The greedy approach and $\beta_{2}=0$ approach, which do not value cohesion, result in robots grouped much too close together. Figure 3(b) displays the connectivity status achieved by different methods over the course of the simulation. Both our full approach and our $\beta_{3}=0$ approach maintain connectivity well, as does the greedy approach, which indirect causes robots to move towards one another at the goal. Our $\beta_{2}=0$ approach is less able to maintain a connected system as it moves through obstacles due to it not valuing spacing between robots, but increases connectivity as the system reaches the goal position.

Figure 3(c) shows the average nearest obstacle to any robot. Here, we see that our $\beta_{3}=0$ approach performs poorly for the first time, with it and the greedy approach moving very near to obstacles. Our full approach and our $\beta_{2}=0$ approach perform well, as they value distance from obstacles. Finally, Figure 3(d) shows the distance to the goal over time for each approach. Only the random approach fails to make progress towards the goal. Overall, we see that our full approach performs the best, making progress towards the goal while staying close to the ideal system cohesion, maintaining connectivity, and avoiding obstacles. Each baseline version performs poorly somewhere, with $\beta_{2}=0$ maintaining a poor interaction distance and connectivity and $\beta_{3}=0$ navigating much closer to obstacles.

We next evaluated the Area Obstacles scenario seen in Figure 2(b), in which large square obstacles lie between the multi-robot system and the goal position. These larger obstacles interfere with robot movement much more than point obstacles, and so cause larger variation in evaluation. First, in Figure 4(a) we see that our approach is the only one capable of ending a simulation with robots distributed at the ideal cohesion distance. The alternate versions of our approach result in robots grouped much too closely together, while the greedy approach ends with robots spaced too far apart, as robots become stuck navigating through the large obstacles. Figure 4(b) shows a similar result when considering the connectivity status. All approaches struggle to maintain a fully connected system as the robots move through the large obstacles. Our approach and its variations perform the best, ensuring the multi-robot system stays together instead of separating around obstacles and resulting in the highest connectivity scores. The greedy approach, which attains high connectivity through simple point obstacles, has much more trouble maintaining connectivity as robots become stuck without an algorithm to plan navigational behaviors around the large obstacles.

In Figure 4(c) we see the distance to the nearest obstacle as robots progress through the environment. As with the Obstacle Field scenario, our full approach and the $\beta_{2}=0$ approach are able to maintain significant distance from the large obstacles, showing the importance of the obstacle avoidance term in the cost function. Again we see the $\beta_{3}=0$ and greedy approaches result in the lowest average distance to an obstacle, indicating a high risk of being stuck behind an obstacle or nearing a collision. Finally, in Figure 4(d) we see that our approach and its variations are the only approaches able to consistently reach a goal position through the Area Obstacles. These approaches, because of their ability to plan actions in the context of their environments and their neighbors, allow the multi-robot system to effectively navigate the large obstacles. The greedy approach, as can be expected by its poor maintenance of system cohesion and its nearness to obstacles, regularly fails to navigate the entire system to the goal position.

Finally, we evaluate the scenario seen in Figure 2(c) in which there is a Dynamic Goal, as if the multi-robot system was tasked with following waypoints or a human through an environment. We see similar results to earlier scenarios. The naive greedy approach causes robots to bunch together, maintaining cohesion but making the system at risk for collisions. Our baseline approaches again each struggle in the cost areas that their hyperparameters omit. When $\beta_{2}=0$, we see that the system maintains connectivity at the expense of allowing robots to become dangerously close together. When $\beta_{3}=0$, we see that the system maintains a safe distance between robots but risks collisions with obstacles.

However, our full approach again balances the evaluated metrics. It is able to maintain an ideal interaction distance among robots, keeping them at a safe distance to avoid collisions but still achieving full connectivity. This full approach is also able to maintain a safe distance from obstacles in the environment, while still making progress towards the waypoints.

In order to understand how our approach would perform with the noise inherent in physical robot operations (i.e., uncertainty about the positions of detected neighbors and obstacles), we conduct evaluations with locations in the environment modified with $10\%$ sensor noise. Results with this added noise can be seen in blue in Figures 3-5. We can see that our approach does lose performance when noise is added, but is still able to outperform both of our baseline methods and the greedy method. Due to robots being able to play their games before each action, errors in observation do not build up or persist and cause long term issues. Additionally, as our approach is decentralized, errors from the added noise do not propagate through the system, and are restricted to individual robots. Accordingly, our approach is very robust to the sensor and movement noise encountered in physical multi-robot systems.