ViPER: Visibility-based Pursuit-Evasion via Reinforcement Learning
Authors: Yizhuo Wang
Yuhong Cao
Jimmy Chiun
Subhadeep Koley
Mandy Pham
Guillaume Adrien Sartoretti
Venue: CoRL 2024 (2024)
Keywords: MARL
pursuit-evasion
graph attention
path planning
TL;DR: We propose a neural framework for visibility-based pursuit-evasion to learn a coordinated yet distributed policy for multiple agents to effectively search for worst-case evaders, resulting in a significantly improved success rate across various maps.

Abstract: In visibility-based pursuit-evasion tasks, a team of mobile pursuer robots with limited sensing capabilities is tasked with detecting all evaders in a multiply-connected planar environment, whose map may or may not be known to pursuers beforehand. This requires tight coordination among multiple agents to ensure that the omniscient and potentially arbitrarily fast evaders are guaranteed to be detected by the pursuers. Whereas existing methods typically rely on a relatively large team of agents to clear the environment, we propose ViPER, a neural solution that leverages a graph attention network to learn a coordinated yet distributed policy via multi-agent reinforcement learning (MARL). We experimentally demonstrate that ViPER significantly outperforms other state-of-the-art non-learning planners, showcasing its emergent coordinated behaviors and adaptability to more challenging scenarios and various team sizes, and finally deploy its learned policies on hardware in an aerial search task.

ViPER: Visibility-based Pursuit-Evasion via Reinforcement Learning
Yizhuo Wang Yuhong Cao Mandy Pham
Jimmy Chiun'
Subhadeep Koley²
Guillaume Sartoretti'
National University of Singapore 2EET Shibpur 3UC Berkeley
Abstract: In visibility pursuit-evasion tasks, a team of mobile pursuer robots with limited sensing capabilities is tasked with detecting all evaders in multiply-connected planar environment, whose map may may not be known to pursuers beforehand. This requires tight coordination among multiple agents to ensure that the omniscient and potentially arbitrarily fast evaders are guaran- teed to be detected by the pursuers. Whereas existing methods typically rely on a relatively large team of agents to clear the environment, we propose ViPER, neural solution that leverages graph attention network learn a coordinated yet distributed policy via multi-agent reinforcement learning (MARL). We exper- imentally demonstrate that ViPER significantly outperforms other state-of-the-art non-learning planners, showcasing its emergent coordinated behaviors and adapt- ability to more challenging scenarios and various team sizes, and finally deploy its learned policies on hardware in an aerial search task.
Keywords: Pursuit-Eyasion, Graph Attention, Path Planning, MARL
Introduction
Pursuit-evasion broadly encompasses general problems that consider detecting/capturing mobile or even adversarial targets (i.e., evaders) by team of pursuer agents. has broad applicability in robotic deployments, including human localization after disasters, area patrols prevent unautho- rized activities, and environmental monitoring of wildlife habitats [1, 3, 4]. In this work, unlike many pursuit-evasion problems that assume full observability of the evader's position and motion dynamics [5, 6, alllownnng the focus to be merely on chasing the evader(s) without the need for searching-aa we address more general worst-case scenario: visibility-based pursuit-evasion, where agents have no information about the evaders. In this scenarios, agents with limited sensing range must coordinate to eventually detect all omniscient evaders, regardless of their movements.
In visibility- based pursuit- based the agents' sequential observations, the environment is classified into contaminated areas, where the presence of evaders is uncertain, and cleared areas, where it is guaranteed that no evaders can reside/enter without being detected by any agent [2, 8, 9]. Agents are tasked with expanding frontiers (i.e., the boundaries between cleared and contaminated arcas) to methodically explore the entire environment, turning all contaminated areas into cleared areas. During the task, agents need coordinate their actions to control recontamination, where evaders might re-enter cleared areas undetected, turning them back into contaminated areas (see Fig. lb). Therefore, this problem is also referred to adversarial search [5], or the clearing prob- lem [8. 10]. Due to the complexity of this problem, [8] deploys sile/constraint-baseee planners to reduce the complexity by prohibiting agents' actions that lead to recontamination, thereby signifi- cantly reducing the action space of agents. However, as shown in Fig. Ic, recontamination is un- avoidable to complete the task in some challenging scenarios. Following works [10, 11] utilize cen- tralized hhuea-heeristcc) sampling-base based methods to seek efficient search directly in unconstrained
"Equal contribution. Correspondence to wy980u. nu.iouu.uu.... eus
8th Conference Robot Learning (CoRL. 2024), Munich, Germany.

---

HAA
Cleared Area
Recontamination
Obstacle
a) Good Coordination
b) Poor Coordination
c) Difficult Initial Position
Figure 1: Visibility-basel pursuit-evasion in a simple environment with two agents. The agents' trajectories are shown red/blue, while that of an imaginary, worst-case evader is shown in gray.
action spaces, However, these methods are still limited to relatively small-scale scenarios or require extensive optimization.
Motivated by the advanced performance recently achieved by deep reinforcement learning (DRL) over compling-based methods in various single-robot informative path planning tasks [12, 13, 14), we propose ViPER, MARL-based solution for pursuit-evasion, allowing agents to learn to ac- tively collaborate a decentralized manner, to achieve significantly improved performance over conventional methods in relatively large-scale pursuit-evasion tasks. To develop such a desired learning-base based planner, we make efforts address the following key challenges: (1) Informatively yet concisely encode the observed/commmuicatted information through the agents' neural network to enable efficient policy learning. Complex observations (including clcared/contaminatee areas, obstacles, other agents, etc.) need to be represented in an efficient format so that the neural net- work can learn smoothly and efficiently.
(2) Accurately model the long-term influence of agents' decisions on recontamination. Due to the changeability of the task (i.e., environments are partially known), model-free RL may struggle at accurately estimating the underlying transition model, mak- ing the training process less stable. (3) Efficiently enable agents to learn cooperative maneuvers. In scenarios, the optimal actions of the team might depend sensible decisions of specific agents, making efficient credit assignment critical for cooperation learning. ViPER addresses the challenges above by:
incorporating the cleared area dynamics and the other agents' information into graph attention network to allow context-aware policy learning;
leveraging privileged ground-truth information during training to address the inaccuracy and stability inherent to model-free RL's state value estimation;
employing an attentive critic for credit assignment that integrates agent action features to enable agents learning more efficient, decentralized cooperation.
To the best of our knowledge, ViPER is the first neural solution for the visibility- pursuit- evasion problem that considers worst-case adversaries. Our approach improves team coordination, significantly outperforming state-of-the-an art non-learning planners unknown environments. We further empirically show that ViPER, once trained, can adapt to varying team sizes and (significantly more challenging) map structures. We also highlight its robustness in the face of agent failure, and finally experimentally validate learned policies on hardware in an aerial search task.
2
Prior Works
The initial formulation of the guaranteed worst-case pussuit-evasion problem introduced by Parsons [15], followed by Suzuki and Yamashita [16] who proposed visibility- variant, tran- sitioning the setting from discrete graphs to continuous polygonal environments. In such scenarios, agents aim to find an evader who can move at unpredictable and potentially unbounded speeds.
Known environments: There is a rich literature on visibility-based pursuit-evasion problems, with the majority of works considering fully known environments in which agents precalculate their routes offline before execution. Many of these studies focus completeness and optimal- ity of single-agent pursuit-evasion algorithms, considering an omnidirectional sensor with infinite

---

range [17, 18]. Furthermore, Gerkey et al. [2] provided a complete algorithm for agents with a limited angle of view and proved that computing the minimum numher of such agents required to search an area is NP-hard. Since there is no known foosed-form solution for the multi-agent pursuit- evasion game, Quattrini Li al. [19] decomposed the environment into convex hulls and introduced heuristic search approach, whereas Olsen et al. [1 proposed solving it with graph sampling- based method, aiming to mitigate the inherent complexity of the complete algorithms [20].
Unknown environments: Sachs and Rajko [21] presented the first single-agent algorithm that does not require a complete map of the environment, while Kolling and Carpin [9] utilized coordinated sweep lines by the team to simultancously clear and explore unknown environments. Based on this, Durham et al. [8] developed an algorithm that guarantees capture if the number of pursuers is suf- ficient. They introduced method to update the global frontiers between cleared and contaminated areas using solely local information. All these methods assume relatively simple polygonal topol- ogy of the unknown environments and require more than sufficient agents to carry out the tasks [10].
3 Problem Formulation
Environments: We consider a bounded, multiply-connected environment represented by an occu- pancy map M c R² that is initially known (M = .M₂) or unknown (M- = =M,)) to the agents. In the case of an unknown environment, the map is gradually explored and revealed by the agents such that M2 U.M. = M. Based on their omnidirectional sensor measurements, agents will classify the known areas into either traversable free areas M or occupied areas M, within their line-of-sighr visibility range (i.e., M, U.. = M&).. The free space is further categorized into either cleared areas Me contaminated areas M, \ Me. Note that assume perfect communication among agents, allowing them to exchange information and share the same map throughout the task.
Agents and evaders: We task n agents to coordinate their trajectories V = (Vi,... th., with the objective of capturing evaders capable of moving at potentially unbounded speeds Ve. Here, d/: (,,,,, ... + M represents the trajectory of agent i over time, with (t) indicating the agent's location at timestep t. Agents scan their surrounding environment within their sensor foot- print (()) S M which has range of Tfvv (with visibility also limited by obstacles), commu- nicate with other agents to exchange their measurements, and consequently update their map M. We hypothesize a worst-case scenario where the evaders are positioned right outside the frontiers between the cleared and contaminated areas, denoted by F a.Me \ M.. poised to intrude once there are any frontiers not within the visibility of any agent. Such frontiers are termed the uncovered frontiers Fu., where evaders in contaminated areas can penetrate and cause recontamination, con- fined to their speed Ug- Since the locations of an agent in two consecutive timesteps are within each other's visibility (explained in Section 4), the intersection of two consecutive sensor footprints will also be visible during the agent's ss movement. This applies to any agent in the team and we denote this intersected area as
1+1
n Ü S(er(1)) v=1 Li=1
S(V =
Recontamination will spread through the free areas My at speed ve, encroaching upon the cleared areas M.. In particular, when evaders are arbitrarily fast (i.e., = 20), the contaminated areas will expand through each connected M, until reaching the boundary of ((I..+1).
The objective of the visibility- pursuit-evasion problem is determine the optimal agent trajectories U such that the cleared areas can expand to encompass the entire free space while minimizing the length of the trajectory for all agents:
Objective:
V
arg min Σ max ( + 1) - (t)ll, s.t. M. = My,
(2)
with Mj the ground-truth free areas. Note that we optimize the sum of the maximum length per step, assuming synchronous decision decision-making and execution, whereby all agents must reach their viewpoints to proceed to the next step.
3

---

4 Multi-Agent Coordination Method
This section casts saibilliy-basse' pursuit-evasion an RL problem, outlines proposed policy and critic networks based on graph attention, and details its training procedure. We provide insights into the design of our observation, reward, and network architecture to foster advanced coordination.
4.1 Cursuit-Evasion as an RL Problem
Sequential decision-making: While agents can pre-plan their trajectories offline in a known en- vironment, navigating an unknown environment relies on an adaptive online planner to continu- ally update the map. This casts the task as a sequential decision decision-making problem, specifically a Markov decision process (MDP). We first uniformly distribute candidate viewpoints (also referred to nodes hereafter) Vi {vD, UI,... Yuy (5) M across the free areas, and ap- pend additional nodes into the newly identified free areas (if any) with each decision timestep. We then connect each node with its collision-free neighboring nodes within a specified range (usually S rfwv) forming the graph G, = (V,, F.z) with its corresponding traversable edge set F4,- Upon all agents reaching their previously selected viewpoints, each agent will simultaneously choose the next viewpoint to visit, sequentially constructing the agent's 's trajectory v)x(t) Vi.
Observation space: Inspired by recent single-agent DRL-based informative path planning plan- ners [12, 13], the observation
(G', v)) includes the augmented graph G", (V/, Ee)) and the current locations of the agent team v, The augmented graph Gj shares the same edge topology E, as Gr, but also incorporates map information to assist agents in making informed and coordinated de- cisions. For each v' E V", the property of the node v/ = (Ami.;: Ayi. Pi. Uy Mu.j. 8j: Sc.j. 95): (I) Relative position (Axt,j, Als,)): the node's position relative agent j. i.e., (Aviyy Alky) "y (l) For simplicity, we omit the agent enumerator in graph and observation. (2) Occupancy of other agents py: binary value indicating whether any other agent is positioned U.. (3) Utility My: represents the number of visible frontiers at node fy [22]. i.e., Uj Kf E F If u,ll < Vfov, M., = 0)). where / C M is a straight line connecting the node to the frontier. The node utility in contaminated areas is set to -1. (4) Uncovered utility uny similar to utility, but counts only the uncovered frontiers not within any agents' visibility, i.e. replace F above with Fa. (5) Cleared signal sy: binary value indicating whether Uy is within cleared areas. (6) Coun- terfactual cleared signal Sc.j hallucinates scenario without the presence of agents, considering how cleared areas would change, to help improve understanding of the evader's speed. Specifically, when 00, 8x, = 0. (7) Guidepost gj: binary value indicating whether by is on the agent's 's A* trajectory to its nearest frontier, which significantly aids in agent navigation to frontiers, especially when they are distant. The node coordinates and utility values the observation are normalized before being fed into the neural network.
Action space: Each time all agents reach their designated viewpoints Vr, the graph attention- based networks, parameterized by 0 and shared among all agents, output stochastic policies To (at,s or.e). i = 1,..., n (s.t. (t + = Uj (ej, (t)) E.). Agents select the next neigh- boring node based on these policies, then navigate to their selected viewpoints along straight paths, updating their maps with the information collected en route. If multiple agents select the same viewpoint, the others will alternatively choose the closest node to that viewpoint.
Reward structure: Our reward is designed to incentivize agents to optimize the task objective as outlined in Eq. (2). That is, we assign rewards/penalties for expanding/shrinking cleared areas, impose penalties for the largest distance traveled between viewpoints among all agents, and assign a substantial reward ry upon the successful task completion (0 otherwise):
ri = c . (Maal) - C2 max [| + 1) - (b(( + L(M.=M)) Ty:
(3)
where C1 C2 are two constants for scaling. This reward re is equally shared among all agents, as it is challenging design a reward structure that aligns with the actual objective while accurately assigning individual rewards to each agent.

---

Encoder
Policy Decoder
Masked Self- Attention Layers
Node Featurea Neighboring Features
Policy
Action
Partiel Map Shors Augmented Graph
Actions of Agents d,
Current/Other Agent's Features
Agent's Selected Node (Features)
Critic Decoder
Erhanced Gument Noce Feature
Masked Attantion Subjected E,
State- Action Values
Filtar Agent/ Neighboring Node
Ground- truth Map Augmented Graph
Masked Self- Attention Layers
Features
Figure 2: ViPER's policy and critic networks based on graph attention. It illustrates the scenario with unknown prior knowledge of the environment. In the constructed maps, black, white, and gray colors denote the occupied, free, and unknown areas, respectively. The collision-free graph is extracted from the map, with nodes colored represent their utility and connected by pink edges. Note that the ground-truth map is only used by the critic during training.
4.2 Network Architecture
Inspired by recent advances in graph attention networks [23, 24], we design network learn policy Te that orchestrates coordinated behaviors among multiple agents. Our graph attention-based policy network consists of an encoder and a decoder: the encoder extracts information from nodes across the entire known map, while the decoder yields which neighboring node to visit next, based on the aggregated global information.
We train critic network to approximate the state-action values. These values represent the expected cumulative future rewards (i.e., return) and guide our policy network by evaluating the quality of the chosen actions. The environment is fully observable if it is known a priori: 8 O₁- However, in unknown environments, the policy network can only access partial information about the environ- ment as agents explore. In our work, unlike the policy network, the critic network is provided with complete ground -tuth information (e.g., entire map/graph, see Fig. 2) during training phase. This privileged learning approach, leveraging the critic's access to the full state, contributes to a more stable training process [13]. To harness the full potential of the well-established centralized training with decentralized execution (CTDE) paradigm [25], further provide the critic with the actions of other agents within the team d₃ That is, during the training phase, the integration of the state (G²", W,) along with enables the critic to estimate state-action values with greater accuracy, thus in turn implicitly assisting agents in predicting the structure of the environment as well as the behaviors of other agents.
Encoder: Our encoder is essentially a sequence of masked self-attention layers (introduced in Appendix A) that enhances the features of each node by incorporating information from other nodes within the graph structure. We first apply a feed-forwart layer to embed the node properties in V into d-dimensional node features h". These node features are then processed through N stacked self-attention layers (i.e., 11 k. = h", and with N = 6 in our practice), where each layer uses the output the previous one as its input. We calculate the mask M, of the graph using the adjacency matrix derived from E,. This mask is applied to ensure each node has access only to features of its neighboring nodes (i.e., attention weight w,, = O, v(u,, viy) & E,). Although atten- tion is constrained to neighboring nodes at each layer, nodes can still acquire non-neighboring node features by repeatedly aggregating features through this stacked self-attention structure. We find that, in contrast to unmasked attennttenninn, our method of masked self-attention, which propagates neighboring features layer by layer, leads to a more effective learning of pathfinding solution [26]. The encoder thus enhances the node features ht" to J.",, as each updated set of node features contains dependencies on other nodes the graph, depending on M, and N.
Policy decoder: The decoder is used to determine the final policy based on the enhanced node features h. From these node features, select the one at the robot's current position query:
5

---

ha = h va(t)' The current node features h", along with its neighboring node features (presented as key-value pairs) from h", are fed into an attention layer, thereby enhancing the output he with information from its neighboring nodes. Subsequently, we adopt a single-head attention mechanism with he and its neighboring node features, and directly use its attention scores as the final output policy Th = (as,1 O1,1) = Wi.j. from which the agent selects the next viewpoint to move to. This design relaxes the need for predefined policy size, instead allowing the policy's dimensions to adapt dynamically the number of neighboring nodes, thus naturally accommodating graphs with arbitrary connectivity.
The critic network Qs. parameterized by Ø, shares the same encoding structure with the policy network Tg. but employs a different decoder that incorporates other agent's actions. We mirror the idea in MAAC [27] that introduced an attentive critic to select relevant information for each agent. From the enhanced node features h² output by the encoder, we filter the node features of other agents f (t) and their corresponding selected features h* (=++1) at the next timestep based on their current actions a₁- These features are then concatenated as key-value pairs to enhance the current node feature h.. Subsequently, informed by the actions of other agents, the current node features are further enhanced by incorporating neighboring features, identical to the process in the policy decoder. The enhanced current node features he are then concatenated with neighboring features and are finally mapped to state-action values (s az) by a feed-forward layer.
Critic decoder:
4.3 Network Training Procedure
We train our RL agents using the soft actor-critic (SAC) algorithm 4, 000 randomly created maps for training dataset, and an additional set of 100 unseen maps the test dataset. The training details (algorithm, dataset, graph and sensing configurations) can be found in Appendix B. ViPER's code and trained model are available at https: //github/ com htmm//ammtta//iP.....
5 Experiments
In this section, compare method with state-of-the-ar (SOTA) baseline planners designed for unknown environments, showcasing its superiority in terms of performance, generalization, and robustness. We also discuss the emergent coordinated behavior of our trained policy and present the results of a real-life aerial search task involving three drones and one ground robot.
5.1 Comparison Analysis
We compare ViPER with two planners from Durham et al. [8] and Gregorin et al. [10]. Durham et al. proposed a distributed planner that makes decisions based solely on local frontiers and communi- cation, thus it does require prior mapping of the environment. Suggested by the settings in their original paper, we tuned their planner to output high-quality solutions for fair comparison. While many studies evaluate their algorithms in simply structured environments, structurally complex, requiring agents to implicitly predict the map and actively respond to updates. Our evaluation map dataset comprises 100 maps that were unseen during model training. We also use
map dataset is more
and conjugated maps from Gregorin et al. and compare our performance against the results reported in their paper, using the same Toov- Following [10], we test each map 30 times with random start positions. Note that throughout all evaluations, we use our model trained with 3 agents and bounded evader speed (v, I 20m//imeesee with map size 100 x 100m²) to facilitate faster environment simulation during training.
We report the success rate and the maximum trajectory length E max [1 - (t)ll in Table 1, averaged across 100 maps with unbounded evader speed, i.c., Ve = co. We mark failure of the task if the trajectory length of any agent exceeds 1, 000m. Our results show that ViPER outper- forms the other two baselines in both metries. Upon closer inspection, the performance gap is more pronounced when the team size is smaller. We believe that this likely comes from the restriction in Durham's 's algorithm of not allowing recontamination, potentially requiring larger team size than

---

Table 1: Comparison against SOTA planners in differrnt map sets and team sizes n. We report the success rate and averaged trajectory length (in parentheses).
Our maps
Multiply-conneeted maps [10]
Conjugated maps [10]
a
Durham
ViPER
n
Gregorin
Durham
ViPER
n
Gregorin
Durham
ViPER
24.0% (842.7)
86.0% (411.5)
38.5%
20.0%
50.0%
29.5%
84.2%
92.5%
4
66.0% (577.1)
100% (281.9)
5
73.5%
60.0%
80.0%
15
48.5%
88.3%
100 %
5
89.0% (394,4)
100% (230.0)
6
74.0%
76.7%
98.3%
1.0
Cleared Rate
0.6
0.4
VIPER (n=4)
0.2
VIPER (n-8)
Durham (n=4)
Durna in-8)
0.0
100
200
300
400
500
Figure 3: Paths in complex unknown/known (left/right) large-scale environments (n = 10).
Length
Figure Evolution of the cleared rate versus trajectory length on our map set.
necessary. This is evident in Fig. 4, which plots the evolution of the cleared rate |Mal/|M5 com- pared to trajectory length. When n - 4, the performance disparity is significant, while at n 8, both approaches achieve a 100% success rate, resulting in averagely monotonic increases in the cleared rate. Gregorin's is approach, on the other hand, centralized and allows a certain level of recontamination. Their method combines random walking with an evolutionary approach address rarely explored states. However, in conjugated maps, its success rate still significantly drops the environment size and the number of agents increase, limiting its scalability to larger team sizes.
5.2 Generalization and Adaptability Analysis
Known environments: We evaluate our model in known environments and present our results Table Despite being trained in unknown environments, our model is capable adapting to known environments (and vice versa) without much performance change/degradation, and it scales effectively various team sizes. This is largely due to the fact that the agent observations only include the number of observable frontiers between cleared and contaminated areas (i.e., utility) by design, while excluding information on the exploration frontiers between known and unknown areas. That is, we regard the exploration of the environment as an auxiliary task of the pursuit-evasion.
Complex environments: We adopt an additional map dataset of 100 maps with significantly more complex topologies than those used during training and times larger the area to evaluate the al- gorithm's generalizability with 10 agents. There, the task is deemed unsuccessful once any agent's trajectory length exceeds 3, 000m. The results are presented in the last row of Table 2 and example solutions can be seen in Fig. 3. In unknown environments, the agents may initially misjudge the lay- out, leading to inaccurate agents distribution. Consequently, certain agents need to wait at junctions for a long period, awaiting the arrival of other agents before continuing to collaboratively explore environment and minimize recontamination, thereby increasing the difficulty of the task. We believe these results suggest that ViPER can generalize to vastly different/challengingg environments with minimal impact map size the number of agents involved, without the need for retraining.
Agent failure: In Appendix C, we exhibit ViPER's 's robustness to mid-task agent failures, showing its ability to adapt and prevent further recontamination from failed agent(s).
5.3 Emergent Coordination
Our agents exhibit interesting emergent coordinated behaviors during training, thanks to our graph- attention-bast based network and centralized privileged critic (an ablation study of these modules can be found in Appendix D). One of map set is shown in Fig. 5, where display the solution
7

---

Table 2: Adaptability to various environmentssettings
(a) t = 10 (98.9)
(b) t 15 (139.8)
(c) == 21 (192.1)
Our maps
Unknown
Known
86.0% (411.5)
82.0 52.0% (401.3) 100% (267.6)
100% (281.9)
5
100% (230.0)
100 % (230.7)
Our maps (complex)
Figure 5: 3 agents clearing an unknown environment. Dotted green/red lines show covered/uncovered frontiers.
69.0% (1795) 98.0% (1005)
snapshots various timesteps and trajectory lengths (in parentheses). We observe that, once the green agent clears the top-right room and begins moving towards the blue agent for assistance, the blue agent starts to move downward in advance upon observing the green agent's approach, allowing for some areas of controllable recontamination to reduce trajectory length. Then, after clearing the room, the blue agent joins forces with the green agent to clear the upper room, which has an obstacle situated the middle requiring at least two agents to clear. Our additional examples in Appendix further confirm that, although agents make synchronous decisions in MARL framework, they can intelligently allocate themselves on-demand and dynamically redistribute as the task progresses.
5.4 Experimental Validation
Agant
Agent 3
We carried out experiments to validate ViPER in an aerial search task using three Crazyfile 2.1 drones as searching agents and one TurtleBot3 robot as an imaginary evader (see Fig. 6). The experiment was conducted in a x 4m mockup arena with way- point node resolution 0.2m. We opted to use the optical flow sensors the drones for position track- ing, with the origins set their take-off positions, and transformed the updated positions into global frame. Waypoints were iteratively published to drones by a remote computer, while the TurtleBot3, controlled by a human as an omniscient evader, only navigated contaminated areas. This exper- iment confirms that ViPER can be deployed on robots with relatively low computational costs, and exhibit high performance. For each agent, forward inference takes less than 0.01s, and the combined environment update and planning take less than 1s of wall clock time.
Agent
Imnsginary Evader
Figure 6: Experimental validation on three Crazyfile drones.
6 Conclusion
Summary: We introduce the first neural framework based on multi muuttiagentteeinooron reinforcement learning for visibility-based pursuit-evasion tasks that addresses worst-case scenarios. Our approach relies graph attention network to allow agents to individually process their shared information and achieve the necessary level of tight coordination that can ensure the detection of omniscient and potentially arbitrarily fast evaders. In our evaluation, our learned policies exhibit emergent coordinated team- work behaviors that outperform state-of-thed -he-th--rt planners by a large margin. We also demonstrate ViPER can adapt to different team sizes, handle diverse scenarios, and remain effective in the face of agent failures.
Limitations and future work: Although ViPER can efficiently handle exploration and recontam- ination compared to other methods, the initial positions of the agents still greatly affects their per- formance and can sometimes result in task failure. When all agents are in a position that necessi- tates additional support from other agents, they are unlikely sacrifice their own, usually extensive, cleared areas to assist others. This reluctance can lead to deadlocks in actions, despite the theoretical existence of solution. Future work will explore multi-level graph representations and hierarchical decision-min meckiinn-mmkingaaee for improved graph structure reasoning and state exploration.

---

Acknowledgments
This work was supported by Temasek Laboratories (TL@NUS) under grant TL/FS/2022011.
References
[1] P. Tokekar, E. Branson, J. Vander Hook, and V. Isler. Tracking aquatic invaders: Autonomous robots for monitoring invasive fish. IEEE Robotics & Automation Magazine, 20(3):33-41, 2013.
[2] B. Gerkey, Thrun, and Gordon. Visibility- pursuit-evasion with limited field of view. The International Journal of Robotics Research, 25(4):299-315, 2006.
[3] Y. Wang, Y. Wang, Y. Cao, and G. Sartoretti. Spatio-temporal attention network for persis- tent monitoring of multiple mobile targets. In 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 3903-3910, IEEE, 2023.
[4] M. Popović, Vidal-Calleja, G. Hitz, Chung, Sa, R. Siegwart, and J. Nieto. An infor- mative path planning framework for uav-based terrain monitoring. Autonomous Robots, 44(6): 889-911, 2020.
[5] T. H. Chung, G. A. Hollinger, and V. Isler. Search and pursuit-evasion in mobile roboties: A survey, Aulonomous robots, 31:299-316, 2011.
[6] W. Li. A dynamics perspective of pursuit-evasion Capturing and escaping when the pursuer runs faster than the agile evader. IEEE Transactions on Automatic Control, 62(1):451-457, 2016.
[7] C. De Souza, Newbury, A. Cosgun, Castillo, B. Vidolov, and D. Kulić. Decentralized multi-agent pursuit using deep reinforcement learning. IEEE Robotics and Automation Letters, 6(3):4552-4555 4559, 2021.
[8] J. W. Durham, A. Franchi, and F. Bullo. Distributed pursuit-evasion without mapping or global localization via local frontiers. Autonomous Robots, 32:81-95. 2012.
[9] A. Kolling and S. Carpin. Multi-robot pursuit-evasion without maps. In 2010 IEEE Interna- tional Conference on Robotics and Automation, pages 3045-3051. IEEE, 2010.
[10] L. Gregorin, S. N. Givigi, F. Freire, E. Carvalho, and L.. Molina. Heuristics for the multi-robot worst-case pursuit-evasion problem. IEEE Access, 1-11552-177666 2017.
[11] T. Olsen, A. M. Tumlin, N. M. Stiffler, and J. M. O' Kane. A visibility roadmap sampling ap- proach for a multi-robot visibility -based pursuit-evasion problem. In 2021 IEEE International Conference on Robotics and Automation (ICRA), pages 7957-7964. IEEE, 2021.
[12] Rückin, I.. Jin, and M. Popovié. Adaptive informative path planning using deep reinforce- ment learning for uav-based active sensing. In 2022 International Conference on Robotics and Automation (ICRA), pages 4473 4479. IEEE, 2022.
[13] Y. Cao, R. Zhao, Y. Wang, B. Xiang, and G. Sartoretti. Deep reinforcement learning-based large-scale robot exploration. IEEE Robotics and Automation Letters, 2024.
[14] Liang, Z. Wang, Y. Cao, Chiun, M. Zhang, and G. A. Sartoretti. Context-aware deep reinforcement learning for autonomous robotic navigation in unknown area. Conference on Robot Learning, pages 1425-1433 PMLR, 2023.
[15] T. Parsons.
Pursuit-evasion in graph. Theory and Applications Graphs, pages 426 441,
1978.

---

[16] I. Suzuki and M. Yamashita. Searching for mobile intruder in a polygonal region. SIAM Journal on computing, 21(5):863-888 1992.
[17] J. Guibas, J.-C. Latombe, S. M. La Valle, D. Lin, and R. Motwani. Visibility- pursuit- evasion in polygonal environment. In Algorithms and Data Structures: 5th International Workshop, WADS 97 Halifax, Nova Scotia, Canada August 6-8, 1997 Proceedings 5, pages 17-30. Springer, 1997.
[18] N. M. Stiffler and J. M. O'Kane. Complete and optimal visibility- based pursuit-evasion. The International Journal of Robotics Research, (6(8):9239946, 2017.
[19] A. Quattrini Li, R. Fioratto, Amigoni, and V. Isler. A search-based approach to solve pursuit- evasion games with limited visibility in polygonal environments. In Proceedings of the 17th International Conference Autonomous Agents and MultiAgent Systems, pages 1693-1701, 2018.
[20] N. M. Stiffler and J. M. O'Kane A complete algorithm for visibility-based pursuit-evasion with multiple pursuers. In 2014 IEEE International Conference on Robotics and Automation (ICRA), pages 1660-1667. IEEE, 2014.
[21] S. Sachs, S. M. LaValle, and Rajko. Visibility- pursuit-evasion an unknown planar environment. The International Journal of Robotics Research, 23(1):3-26, 2004.
[22] C. Cao, H. Zhu, H. Choset, and J. Zhang. Tare: A hierarchical framework for efficiently exploring complex 3d environments. In Robotics: Science and Systems, volume 5, 2021.
[23] Velickovie, G. Cucurull, A. Casanova, A. Romero, P. Lio, Y. Bengio, et al. Graph attention networks. The Sixth International Conference Learning Representations, 1050(20):10- 48550, 2017.
[24] V. Dwivedi and X. Bresson. generalization of transformer networks to graphs. arXiv preprint 2Xiv:2012200699, 2020.
[25] R. Lowe, Y. I. Wu, A. Tamar, J. Harb, O. Pieter Abheel, and I. Mordatch. Multi-agent actor- critic for mixed cooperativecoompttiii environments. Advances in neural information pro- cessing systems, 30, 2017.
[26] Y. Cao, T. Hou, Y. Wang, X. Yi, and G. Sartoretti. Ariadne: A reinforcement learning approach using attention- deep networks for exploration. In 2023 IEEE International Conference on Robotics and Automation (ICRA), pages 10219-10225, 2023. doi:10.1 109/CCA488891 2023.1011 1016065..
[27] S. Iqbal and F. Sha. Actor-atiention-critic for multi-agent reinforcement learning. In Interna- tional conference on machine learning, pages 2961-2970. PMLR, 2019.
[28] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, E. Kaiser, and I. Polo- sukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[29] E. Parisotto, F. Song, J. Rae, R. Pascanu, C. Gulcehre, Jayakumar, M. Jaderberg, R. L. Kaufman, A. Clark, S. Noury, et al. Stabilizing transformers for reinforcement learning. In International conference machine learning, pages 7487-7498. PMLR, 2020.
[30] Haarnoja, A. Zhou, K. Hartikainen, G. Tucker, Ha. J. Tan, V. Kumar, H. Zhu, A. Gupta, Abbeel, al. Soft actor-critic algorithms and applications. arXiv preprint arXiv: 2018.
[31] Chad. Random dungeon generator.
http:://perplexintteccccck
random- pondom-dungeon-ee html.
10

---

A
Attention Layers
Our network relies on attention layers in the Transformer [28], where each layer transforms query vector 14 and a collection of key-value pair vectors & into an output vector hg by computing weighted sum of values. The attention scores are derived by measuring the similarities between queries and keys within each attention head:
9: -
Wij Softmax
1/
(4)
where ki v are derived by three separate learnable matrices in RRddd as 9i = W k = W h4"", = w..... Following [29], we adopt Identity Map Reordering (IMR) between at- tention layers, placing layer normalization before attention layer to improve network stability in RI. tasks.
B Network Training Procedure
We train our DRL agents with the soft actor-critic (SAC) algorithm. SAC learns a soft value function by modifying the policy gradient to include an entropy term, H- oc)), which encourages the exploration of more diverse actions and helps prevent premature convergence [30]:
Algorithm:
VeJ, (0) Eo~D.e>x Ve (og(TT((a,, o1,))) (-a (og( (o,x)) (o(ss,ae)))
(5)
where is the number timesteps and y E [0, 1] the discount rate, the replay buffer, and a serves temperature parameter that scales the importance of the entropy term against the reward. The temperature parameter is automatically adjusted to match the target entropy H..
We use a dungeon map generator [31] to randomly create a set of 4 x 1, 000 multiply- connected maps for our training dataset, with each map oriented four times for map set augmenta- tion, and an extra set of 100 different maps that are unseen during training for performance evalua- tion. Each map have size of 100m 100m.
Map dataset:
The onboard omnidirectional sensor with radius of Tíov 20m will monitor/identify potential evaders (and map the environment). Here, assuming circular field of view (FoV) aligns with most related works [9, 10] and helps incorporate ViPER with both downward-facee cameras and LiDAR. Each agent scans its surrounding environment and communicates with other agents to update shared belief.
Sensing:
Graph: The candidate viewpoints Vi are uniformly distributed throughout the entire known free areas My. The spacing between two adjacent nodes (i.e., resolution) is set at 4m. Note that these parameters are tunable to meet specific practical requirements. Each node is connected with its 25 nearest neighboring nodes (including itself) to establish the edge set E,, provided the paths between them are collision-free. We consider a successful task completion to be the closure of the cleared areas Mc (i.e., no frontiers between cleared and contaminated areas).
Training: During training, the episode is terminated once its length exceeds 128 timesteps, with replay buffer size of DJ 10, 000, a discount rate of y = 1, and the target entropy set to 0.01 -log k. Our model is trained on a workstation with an AMD 7950X3D CPU where 12 environments run in parallel, and an NVIDIA GeForce RTX 3090 GPU to train the network once an episode terminates, after accumulating 5, 000 steps of data in the replay buffer. The model converges after 40 hours of training, and adopt the model at 40, 000 episodes for experiments in Section 5.
C Robustness to Agent Failure
We evaluate the robustness of ViPER to agent failures occurring in the middle of the task. Specifi- cally, we simulate agent failure by deactivating random agent, including its movement and sensor, once agents have explored half of the environment. The result is plotted in Fig. 7, averaged over 100
11

---

maps. Our results indicate that the performance remains similar to (or slightly superior to) that of the fully functional agent group (comparing n - n 1 to n 1). This demonstrates that the re- maining functional agents are able to reactively adapt and prevent further recontamination from the failed agent, thereby avoiding the need to almost entirely restart the task should the recontamination
spread uncontrolled.
D Ablation Results
1.0
We perform comprehensive ablation study eval- uate the effectiveness of our graph attention architec- ture, attentive critic, and privileged learning module.
0.8
Cleared Rate
0.6
Graph attention encoding: To evaluate the effec- tiveness of our graph attention architecture, we addi- tionally train two ablation baselines. In comparison to ViPER with 6-layer graph encoder, one baseline was trained with 3-layer graph encoder, while the other was trained without any encoder. As shown in Fig. 8, the performance significantly degrades with a shallower encoder during training, as agents' limited graph perception results in more myopic decision- making. Without graph encoder, the agents struggle to learn any effective long-term policies necessary to successfully complete the task, leading frequent task failures.
n=4>3
n=$24
0.2
n=3
n=4
n=5
0.0
100
200
300
400
500
Length
Figure 7:
Performance amidst agent fail- ure during the task.
We train three additional ablation baselines: ViPER without the MAAC (attentive critic module). ViPER without GT (ground truth information during training), and ViPER without both MAAC and GT. We present the reward and length curves during training in Fig. dent that ViPER consistently outperforms its baselines throughout the training process. We further observe a significant performance decline without privileged learning, indicating the importance of access to ground truth information for the critic achieve training. Our ablation study demonstrates that both the attentive critic and privileged learning (indi- vidually and combined) enhance ViPER's ability to learn a better policy for multi-agent coordination in visibility-based pursuit-evasion tasks.
Critic module:
is evi-
accurate value estimate during
E Emergent Multi-Agent Coordination: Some Examples
We handcraft several specific scenarios to showcase team coordination and provide insights into ViPER's policy. As illustrated in Fig. 9a, when there is an isolated obstacle/chamber the center of a closed environment, can continuously hide behind the obstacle to elude detection. In this case, two agents must simul- taneously extend their frontiers from both sides of the obstacle ensure the evaders are detected. Similarly, shown in Fig. 9b, each passage must be monitored by agent prevent recontam- ination. In Fig. 9c, four agents are initially paired off to direct toward rightward and downward. However, upon discovering more frontiers below, the green agent reactively reverses and adjusts its trajectory to head downward instead. Fig. 9d depicts scenarios where, if an agent inspects each room along a corridor, an evader could potentially slip past and conceal itself an already cleared room. One solution to use two agents, with one consistently monitoring the corridor. Our two agents alternatively choose take turns clearing rooms and monitoring the corridor, resulting in an even shorter trajectory length.
impossible for a single agent to clear the entire areas, as the evaders
12

---

900
VIPER
1.50
ViPER 3-layer encoder
Averaged Reward
1.25
Averaged Length
800
ViPER w/o encoder
700
1.00
VIPER
VIPER 3-layer encoder
600
0.75
ViPER w/o encoder
500
0.50
400
0.25
300
0.00
10k
20k
30k
40k
10k
20k
30k
40k
Training Episode
Training Episode
1.6
ViPER VIPER MAAC
Averaged Reward
1.4
Averaged Length
500
VIPER w/o GT
ViPER w/o MAAC GT
450
1.2
400
1.0
350
ViPER
VIPER w/o MAAC ViPER w/o GT ViPER w/o MAAC &
0.8
300
250
10k
20k
30k
40k
0
10k
20k
30k
40k
Training Episode
Training Episode
Figure 8: Training curves of ViPER and its ablation baselines, all trained with a team size of 4. All curves are averaged over window of 200 data points, with the shaded area representing
+00.2 times the standard deviation.
(a) 2 passages
(b) 3 passages
(c) 4 passages
(d) Corridor
Figure 9: Coordinated behaviors among agents to clear the environment. (a-c) unknown, (d) known.
13


Reviews:
[{"review_id": "fdcDQ30uTA", "reviewer": "Reviewer_fEXc", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": 3, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "This paper introduces ViPER, a new approach using a graph attention network and multi-agent reinforcement learning to improve coordination in visibility-based pursuit-evasion tasks where robots detect evaders in complex environments. ViPER outperforms traditional methods by adapting to various scenarios and team sizes, and has been successfully deployed on aerial search hardware.", "summary_of_recommendation": "The research is presented mainly from a theoretical perspective, and the real-world experiments appear to be limited. Therefore, from the viewpoint of robotics, including applications, the research could still be improved.", "technical_quality": 3, "clarity_of_presentation": 3, "potential_impact": 2, "robotics_focus": 2, "quality_of_limitations": 2, "questions_for_rebuttal": "The paper appears well-written and could potentially be enhanced by addressing the following points:\n\n* The motivation for targeting the pursuit-evasion problem and the proposed approach should be clarified to improve readability, particularly for those primarily familiar with robotics.\n* In the experimental evaluation, it should be specified whether the observed camera images are from the aerial robot or if they capture the entire field.\n* The method for tracking the position of the drones should be detailed. Specifically, if coordinate transformations are used, what is the origin of these coordinates?\n* The actions outputted by the model should be defined. Are they the desired velocity of the drone or the path of the drone?\n* The definition of visibility during the experiments should be clarified. Is the drone equipped with a camera that scans the environment?\n\nThese clarifications will enhance the understanding and applicability of the research findings.", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "z17Oq3ypSa", "reviewer": "Reviewer_Z6Zd", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": 3, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "The paper proposes a method for finding a plan for multiple robots with limited sensor range to clear an environment so that all potential evaders are found. The problem is solved formulating it as a multi agent reinforcement learning problem, with the method that is based on a graph attention network to learn the distributed policy. Experiments in simulation and one demonstration with real robots are performed.", "summary_of_recommendation": "While there can be an additional ablation study, overall the paper proposed an interesting learning-based method to solve a pursuit evasion problem, with convincing results, including experiments in unseen environments.", "technical_quality": 3, "clarity_of_presentation": 4, "potential_impact": 3, "robotics_focus": 4, "quality_of_limitations": 3, "questions_for_rebuttal": "1. It would be useful to include an ablation study on the proposed architecture to see the impact of each component.", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "c9y8O2XumO", "reviewer": "Reviewer_ycfG", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": 3, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "This paper introduces a method that utilizes graph attention networks to learn centralized planning decentralized control policies for the pursuit-evasion task.", "summary_of_recommendation": "The authors put forward a strong learning-based method that is trained on a dataset of thousands of maps, leading to generalization and adaptability to unseen environments. The method was validated with real robot experiments. However, the robot experiments were relatively small in scale and the baseline comparisons seem weak.", "technical_quality": 3, "clarity_of_presentation": 4, "potential_impact": 3, "robotics_focus": 3, "quality_of_limitations": 3, "questions_for_rebuttal": "1. How does your method scale / perform with multiple evaders? \n\n2. Since the graph attention network incorporates other environment information alongside the graph, is it possible for this method to work with heterogenous robot teams? If not, what changes would be needed to enable this?", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Strengths:

• Novel approach using graph attention networks and multi-agent reinforcement learning for pursuit-evasion tasks
• Outperforms state-of-the-art non-learning planners by a significant margin
• Demonstrates adaptability to unknown environments and various team sizes 
• Successfully deployed on real aerial robots, validating practical applicability

Weaknesses:

• Insufficient graphical explanations of system architecture and integration
• Limited real-world experiments (only 3 drones and 1 evader tested)
• Comparison only to older baselines (2012, 2017), missing more recent learning-based approaches
Decision: Accept