ViPER: Visibility-Based Pursuit-Evasion via Reinforcement Learning
Multi-Agent RLGraph AttentionPursuit-EvasionGuaranteed Search
86%
of maps cleared with only three pursuers
the distributed baseline clears 24%
51%
shorter trajectories at four pursuers
281.9 m against 577.1 m, at a 100% success rate
< 0.01 s
forward inference per agent on hardware
under 1 s for a full map update and replan
4,000
randomly generated training maps
plus 100 unseen maps held out for testing
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.
How It Works
The evader is omniscient and arbitrarily fast, so the team cannot chase it — it has to sweep the environment so that no region the evader could still be hiding in is ever left behind.
-
01
A worst-case guarantee, not a lucky sighting
The task is only successful if detection is guaranteed against an evader that knows where every pursuer is and can move arbitrarily fast. That rules out probabilistic search: the cleared region must grow monotonically, and any gap the team leaves open counts as recontamination.
-
02
Exploration as a side effect
Agents observe the number of visible frontiers between cleared and contaminated regions — not the frontiers between known and unknown space. Mapping the environment becomes an auxiliary task, which is why the same policy works whether the map is given in advance or not.
-
03
Graph attention with a privileged critic
A graph attention network turns the partial map into a policy each agent runs independently, while a centralized critic sees the full state during training only. Agents act on their own at execution time, with no shared planner in the loop.
-
04
Trained small, deployed wide
Soft actor-critic on 4,000 randomly generated maps, always with three agents, a bounded evader speed and 100 m × 100 m worlds. Team size, evader speed and map scale all change at test time without retraining.
-
05
Coordination nobody scripted
Agents learn to trade a little controlled recontamination for a much shorter route, and to converge on rooms that need two bodies to clear — one agent starts moving toward another the moment it sees help coming.
Results
Every planner was run on the same maps, 30 times per map from random starting positions.
A full run: the cleared region on the left, the attention graph driving it on the right.
Hardware Validation
Three Crazyflie 2.1 drones searched a 4 m × 4 m mockup arena at a 0.2 m waypoint resolution, with a human-driven TurtleBot3 playing an omniscient evader confined to contaminated areas.
Paper Video
BibTeX
@inproceedings{wang2024viper,
title={ViPER: Visibility-Base Pursuit-Evasion via Reinforcement Learning},
author={Wang, Yizhuo and Cao, Yuhong and Chiun, Jimmy and Koley, Sourav and Pham, Minh and Sartoretti, Guillaume},
booktitle={Conference on Robot Learning (CoRL)},
year={2024}
}