Decentralized Multi-Agent Pursuit using Deep Reinforcement Learning

Solutions to the pursuit-evasion problem either assume the ‘worst-case’ adversary with infinite speed and complete awareness of the pursuers, or average-case behaviors [11]. Although single-agent pursuit-evasion is studied extensively in the literature [11, 12], its extension to multi-agent systems still remains an open problem [13], of interest in biology [13], physics [3, 1], and engineering [14, 2].

Non-learning pursuit methods can be organized into deterministic and heuristic solutions. Deterministic methods attempt to solve the problem with traditional mathematics tools, such as pursuit curves analysis [12] and differential games [14, 2]. Pursuit curve analysis formulates the trajectory of the pursuer analytically using differential equations. The system can then be solved to find the conditions of capture. Although the problem can be stated simply, closed-form analytical solutions are hard to obtain even using simplistic assumptions such as constant velocities and linear trajectories. Differential games formulate pursuit as a game, where the players must optimize an objective function, often the episode duration. However, it is challenging to define an appropriate objective function with increasing problem complexity, such as with a larger number of agents or motion constraints.

Heuristic solutions [1, 3, 15] inspired by behavior-based decentralized approaches [16], use computational simulations that aim to find emergent group behavior based on local observation [16, 17]. Angelani [3] proposed modeling up to a hundred autonomous pursuers as particles based on [16]. Muro [15] proposed small-scale hunter strategies with up to 5 agents, arguing that the behavior observed in wolf-pack hunts can be simulated with simple rules. Janosov [1] re-examined the concepts of the Vicsek particle model [3] in a more realistic scenario considering delays, accelerations, prediction and a faster target. However, these works assume access to information about the evader’s position and velocity, which is not directly available from onboard sensors.

The real-world applicability of many of the above approaches is limited due to their assumptions in observation and actuation. [3] and [1] both consider an omnidirectional particle model, which is not directly transferable to many robotic platforms. In contrast, our observation model is expressed relative to each agent, which can be found directly using onboard sensors, such as LiDARs or depth cameras[18]. We also consider a non-holonomic kinematic model, suitable for car-like mobile robots or fixed-wing airplanes.

The pursuit-evasion game is a highly studied task in multi-agent RL [19, 20, 21]. However, most approaches apply only to omnidirectional agents, which cannot be easily transferred to real robotic applications without a loss in performance. Lowe [4] presented an approach for multi-agent RL using an adapted version of an actor-critic algorithm extended to multi-agents. Their approach on the pursuit-evasion game with omnidirectional agents outperformed Deep Deterministic Policy Gradient (DDPG) [22]. Xu [7] considered pursuit-evader games with non-holonomic agents, where new agents can join the game. They adapted Bi-directional Recurrent Neural Networks [23] and DDPG. However, they only consider a situation with $3$ and $5$ agents. Furthermore, the observation also assumes global information about other agents, limiting the applicability to real-world situations. A few pursuit-evasion works consider non-holonomic constraints [6, 24]. Hüttenrauch [6] studied multi-agent pursuit-evasion systems by considering the agents as interchangeable and the exact number irrelevant. They create a new state representation based on mean embedding of distributions. Their work focuses on scalability and shows that their system can operate with up to fifty agents.

[25, 26, 27] learn a policy directly from images in a pursuit-evasion scenario with one chaser and one evader. These policies are then successfully transferred to a real-world scenario and show good performance.

Curriculum learning [28] is a learning paradigm to help improve speed of convergence and reduce local minima by gradually increasing the complexity of training data. This learning paradigm has been been widely used for RL[29, 30] and deep learning [31], and shown to solve problems which were previously considered intractable [5].

Our work, while borrowing ideas from both classical and learning-based methods, focuses on using DRL to improve the pursuit performance and consider operational metrics such as capture success rate and the average time to capture. Furthermore, we propose a method that is suitable for sim-to-real policy transfer with realistic observation models and non-holonomic constraints. To our knowledge, we are the first to demonstrate a real-world pursuit-evasion implementation with multiple pursuers using a DRL policy.

As the Deep RL algorithm, we use Twin Delayed Deep Deterministic Policy Gradient approach (TD3)[8], which is an improvement over DDPG [22], designed to reduce the overestimation of the value function. We consider all agents to be homogeneous which allows us to use shared experience to train all agents. This allows the agents to train faster, as well as gathering more information from every step in the environment. All agents are governed with the same policy, however, at each time step the agents use their local observations to individually take actions, resulting in a decentralized system. For each number of agents we train a different policy, which results in a total of $n_{max}$ policies, where $n_{max}$ is the maximum number of pursuers we analyze in this paper. This was because the length of the state representation changes based on the number of pursuers in the game.

The state of a pursuer $i$, assuming a total of $n$ pursuers, is given by $s_{i}=[\psi_{i},\dot{\psi}_{i},s_{i,T},s_{i,1},s_{i,2},..,s_{i,{n-1}}]$, where $\psi$ is the heading with respect to a fixed world frame, $s_{i,T}$ is the state of the target relative to pursuer $i$ and $s_{i,j}$ is the state of pursuer $j$ relative to pursuer $i$. (Time indices are dropped for the sake of clarity). The relative state of the target with respect to pursuer $i$ is $s_{i,T}=[d_{i,j},\dot{d}_{i,T},\alpha_{i,T},\dot{\alpha}_{i,T}]$ and the relative state of pursuer $j$ with respect to pursuer $i$ ($i\neq j$) is $s_{i,j}=[d_{i,j},\alpha_{i,j}]$, where $d_{i,j}$ is the Euclidean distance between pursuers $i$ and $j$ and $\alpha_{i,j}$ is the heading error defined as the angle between the heading of pursuer $i$, and the vector between $i$ and $j$, as shown in in Fig 1. The state representation consists of a total of $2n+4$ variables, which scales linearly with the number of pursuers $n$.

An important consideration is how the $s_{i,j}$ are ordered in the state representation $s_{i}$. A straightforward way would be to assign a unique identifier to each pursuer and always represent them in the same order. However, this leads to inefficiencies in learning as neural networks typically are not permutation-invariant when operating on sets [32]. To illustrate this, consider swapping the poses of two pursuers with everything else being the same. With unique identification ordering, the resulting state would be different than the original, whereas since we have homogeneous agents, the state should not change. To tackle this problem we assign $j$ values for each observation by sorting each other pursuer with respect to their relative angle $\alpha$.

The observation of the pursuers was designed to be easily applicable on real platforms and is used commonly in conventional single-agent pursuit [12]. The agent observations do not require localization with respect to a global frame, as local observations $d$ and $\alpha$ are not referenced in global coordinates and can be extracted using onboard sensors such as laser scanners or cameras. Recent work[18] demonstrates the feasibility of acquiring measurements such as range and the relative angle between the pursuers, using only embedded sensors in drones. For the heading $\psi$, a directional sensor would be needed, such as a magnetometer.

At each time step, each agent individually receives a reward designed to incentivize the capture of the evader and encourage a good formation of pursuers. The reward function is:

At each step that the target is not captured, each and every agent receives a negative reward that is a weighted linear combination of an individual reward (its distance to the target $d_{i,target}$) and a group reward (q-score [13], which we call the formation score in our work). The formation score is a scalar number in the range $[0,2]$, which provides a metric for evaluating the fitness of a formation of the pursuers (lower is better). The formation score ($q$) is defined as:

where $\boldsymbol{\hat{\textbf{$d$}}}_{\textbf{iT}}$ denotes a unit vector pointing in the direction from agent $i$ and the target, and $n$ is the number of agents. In this equation, the closest agent to the target is defined as agent $0$. The formation score encourages agents to spread around the target (i.e., approach the target from different directions) and penalizes the angular proximity between agents. We introduce the formation score when there are at least two agents, as the formation score for one agent is not defined. Early experiments with the formation score showed that when the formation is the only component of the reward, pursuers would only form a good formation but would not make an attempt to capture the evader. To avoid this situation, we penalize the distance to the target, which helps encourage the agents to get close to the evader while being in a good formation. The weights $w_{q}$ and $w_{d}$ were chosen such that when the agents are close to the target, the reward is dominated by the formation score, encouraging good formation. However, when the agents are far from the target, the reward is dominated by the distance to the target, encouraging the agents to move closer to the evader. We analyze the effect of the formation score on pursuit performance in Sec. VI-G.

If the target is captured at a time step, then the pursuer who captures the evader receives the reward $r_{captor}$, while the rest of the agents receive $r_{helper}$, such that $r_{captor}>r_{helper}$. This encourages each pursuer to go for the final capture while encouraging collaboration.

We apply a curriculum for learning by starting from an easier version of the task and gradually increasing the difficulty until the actual difficulty is achieved. There are two main factors in determining the difficulty of a pursuit-evasion game: the relative speed of the target with respect to the pursuers and the capture radius $d_{cap}$. We vary the capture radius by starting from a large radius (so it is easier to capture the target), then gradually making it smaller. This encourages agents to not adopt a straightforward chasing tactic at the beginning of learning but to form more sophisticated behaviors, which could be transferred to smaller capture radii. We also experimented with reducing the pursuer speed to reduce the difficulty of the task, however, we found that pursuers mostly learned to follow the evader directly, and it was harder to explore more sophisticated behaviors afterward.

Curriculum learning helps exploration, especially during the early stages of learning, because early, on it helps the pursuers to capture the target, which would take a longer time in the actual, and more difficult scenario. This helps alleviate the sparse reward problem, which is a well-known challenge in DRL [33]. We analyze the effect of curriculum learning on the pursuit performance in Sec. VI-F.

We implemented two behavior modes for the evader: Fixed Paths and Repulsive. For both, we vary the relative speed of the evader from $0.8$ to $2$ times the pursuer speed, with a step size of $0.2$. We conduct 100 trials for every speed level.

Fixed Paths: We propose a benchmark where the evader follows three predefined paths, as shown in Fig. 2.

Repulsive: We use a potential field method with repulsive forces only to find a motion vector. Each pursuer exerts a repulsive force in the direction of the vector between the pursuer and the evader. The arena boundary also exerts a force so that the evader can avoid the wall. These forces decrease proportionally to the distance squared. The resultant vector is calculated by:

where $\vec{e}$ is the current position of the evader, $\vec{a}_{j}$ is the position of agent $j$ and $d_{j}$ is the distance to $\textit{a}_{j}$. $\gamma$ is the direction of the agent to the closest point on the wall, $\boldsymbol{\hat{\textbf{$\gamma$}}}$ is the unit vector rotated by an angle of $\gamma$ and $d_{w}$ represents the distance of the agent to the wall.

We implemented three baseline methods: Two classical (Janosov [1] and Angelani [3]) and a DRL (Hüttenrauch [6]) method. The approach by Hüttenrauch [6] was trained on our simulation environment using their communication set. This observation vector included relative angle, the distance towards the target, and the heading of each of the pursuers. It should be noted that this observation set included more information than our model. Furthermore, this information (orientation of neighbors) would likely require explicit communication in a real-world application since it can not be easily estimated from current embedded sensors. We trained the policy for 4 million timesteps (same as our approach, around 4 times as long as their original paper) without curriculum learning (no curriculum learning was used in their original work) and presented the best simulation results.

We adapted the classical methods to use a non-holonomic model. As these methods are designed for omnidirectional agents, they are not directly comparable to our solution. Therefore, we convert the outputs of these models into the unicycle model using the following equations:

The omnidirectional models have two outputs, $dx$ and $dy$, which are the velocity in the $x$ and $y$ direction respectively. From this, we find the desired heading $\psi_{desired}$ of the omnidirectional controller. We use a P controller on the error between the desired heading $\psi_{desired}$ and current heading $\psi$. We tune gain $K$ such that the number of captures is maximized in simulation trials.

In these experiments, the evader followed fixed paths, as explained in Sec.V-A. The pursuers were trained on the repulsive evader only but were tested on the fixed paths benchmark. The capture rate and the average number of steps with respect to the number of pursuers are shown in Fig. 3. While Janosov [1] get above $95\%$ on the fixed paths benchmark for $N>2$, Angelani [3] does not perform well on this benchmark. Both our approach and Hüttenrauch [6] complete the task successfully for $n\geq 3$. The average timesteps to capture for both DRL approaches is significantly lower than the other approaches for the fixed paths benchmark, likely because the classical algorithms attempt to corral the target. In contrast, the DRL based approaches tended to be more aggressive and intercept the evader quickly along the fixed paths.

The success rate and average timesteps to capture the repulsive evader with respect to the number of pursuers are shown in Fig. 4. Our approach outperforms the competing approaches in cases with a lower number of agents in terms of the success rate. Hüttenrauch [6] performs well with a larger number of agents, however, struggles with fewer agents. Janosov [1] completes the task with a success rate above $94\%$ for $n\geq 4$. However, it does not perform well with fewer than four agents. Angelani [3] does not perform well in this benchmark. Furthermore, with one or two agents, all methods showed poor performance, as it is difficult to chase a faster evader with few agents. Our approach takes more time on average to complete the capture compared to [1].

As we showed in Sec. VI.B, with an increasing number of agents, the task decreases in difficulty for a fixed arena size. Therefore, with a larger number of agents, most approaches can perform the task successfully. The pursuit-evasion game is played in an obstacle-free arena, but the agents can use the arena boundaries to constrain the evader movements. In this section, we investigate the effect of larger arena sizes using $n=3$ agents. We do not retrain our agents on the new arena size but use the model trained on the original radius size $r_{area}$. As shown in Fig. 5, our approach comfortably outperforms the other approaches in terms of success rate as the arena size increases. This shows that the learned policy can generalize to larger arenas. However, the average number of timesteps to capture for our approach is consistently higher than other approaches. We attribute this result to using only the successful captures to obtain the average number of timesteps: our approach can likely find solutions to more difficult problems at the expense of increased average duration to secure the capture.

In this section, we examine at the effect of relative evader speed on capture success, for $n=3$ pursuers. As shown in Fig. 6, while our approach had 100% success rate at all speed levels, all other methods had a drop-off at faster evader speeds. As expected, our approach was the fastest in capturing the target (only considering successful episodes).

In this section, we examine the scalability of our approach to an environment with more agents than the network was trained on. For the 4 agent policy in Fig. 7, the agents are trained in the 4 agent setting. At test time, the number of agents increases (as indicated on the horizontal axis), but each agent can only observe their 4 closest neighbors. In contrast, both the $N$ agent policy and Hüttenrauch [6] were given information about all pursuers. The success of our approach decreases with a larger number of agents, by around 5% when there are more agents, as the agents cannot coordinate fully. The other approaches reach 100% for a larger number of agents. The four agent policy requires a larger average number of timesteps to capture the target compared to a more specialized policy, and this performance penalty increases as more agents appear in the environment compared to the number of agents during training. However, the 4-agent policy tends to perform similarly to [6], which was designed for scalability.

Fig. 8 compares the effect of using our curriculum learning strategy described in Sec IV-D, for $n=3$ agents. The network was trained 3 times. At regular intervals, we stop training and evaluate the policy on the repulsive evader benchmark. The results show that curriculum learning is beneficial for capture performance: it converges to about 100% success rate after 1.5 million training steps, whereas without curriculum learning, the average success rate was below 80% even at 4 million training steps. Furthermore, the performance with curriculum learning was much more consistent, as evidenced by the low variance among the three runs.

As described in Sec. IV-C, we provide a partial reward at every timestep in order to encourage good formations. We analyze the effect of supplying this dense reward component to each agent. Fig. 9 compares the evolution of the capture performance with and without the formation score with respect to the number of training steps. These experiments were conducted with $n=3$ agents. As shown in the Fig. 9, benchmark scores were slightly higher when the formation score is used as part of the reward. Furthermore, when the formation score is used, the average capture time for successful episodes is decreased.

We observe two interesting learned emergent behaviors that often lead to successful captures: ambushing and splitting up.

Fig.10 shows the splitting up behavior with $n=3$ agents. This behavior was more common with a smaller number of agents. The agents tend to split up into two groups, trying to push the evader into a wall before attempting to block the two opposite directions. This tactic works well as the evader is backed against the wall and has limited room to escape.

Fig. 11 shows the ambushing behavior with $n=8$ agents. This behavior was more common with a larger number of agents. The agents tend to form a circle, attempting to move such that they can surround the evader and then approach from all directions. This seems to be a distinct behavior from the ’Split Up’ behavior, as the agents do not use the walls as much, preferring to surround the evader as a pack, similar to pack behaviors observed in Muro’s work [15]. When the agents execute this strategy to trap the evader, it is often very difficult for the evader to escape.

Previous sections considered constant linear speed and variable angular speed for pursuers, primarily because this is an assumption for classical algorithms. We now consider the more general case, where agents can also vary their linear velocity between 0 and $v_{p}$. Therefore, we train the network with two outputs: linear and angular velocity. We consider the $3$ agent scenario, in which the agents achieve 100% capture rate with and without velocity control, in both the fixed and reactive benchmarks.

The agents often displayed a “Stalking” strategy as illustrated in Fig. 12. With this strategy, the agents move towards the target before slowing down and waiting until the opportunity presents itself to capture the evader. This behavior may have analogs in nature, where pursuers will stalk their prey and position themselves such to maximize the likelihood of attack[34].