# Grasper: A Generalist Pursuer for Pursuit-Evasion Problems

arXiv: https://arxiv.org/abs/2404.12626 · HTML: https://mlsanity.com/paper/2404.12626/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 46 references that are in the map.
- First posted on arXiv 19 Apr 2024.

## Builds on (most cited first, 19 of 19)

- [Fast R-CNN](https://mlsanity.com/paper/1504.08083/) (2015)
- [Exploration by Random Network Distillation](https://mlsanity.com/paper/1810.12894/) (2018)
- [The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games](https://mlsanity.com/paper/2103.01955/) (2021)
- [A Survey on Multi-Task Learning](https://mlsanity.com/paper/1707.08114/) (2017)
- [An Overview of Multi-Task Learning in Deep Neural Networks](https://mlsanity.com/paper/1706.05098/) (2017)
- [Counterfactual Multi-Agent Policy Gradients](https://mlsanity.com/paper/1705.08926/) (2017)
- [Graph Contrastive Learning with Adaptive Augmentation](https://mlsanity.com/paper/2010.14945/) (2020)
- [GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training](https://mlsanity.com/paper/2006.09963/) (2020)
- [GraphMAE: Self-Supervised Masked Graph Autoencoders](https://mlsanity.com/paper/2205.10803/) (2022)
- [A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning](https://mlsanity.com/paper/1711.00832/) (2017)
- [From Canonical Correlation Analysis to Self-supervised Graph Neural Networks](https://mlsanity.com/paper/2106.12484/) (2021)
- [Human-Timescale Adaptation in an Open-Ended Task Space](https://mlsanity.com/paper/2301.07608/) (2023)
- [A Decentralized Policy Gradient Approach to Multi-task Reinforcement Learning](https://mlsanity.com/paper/2006.04338/) (2020)
- [Solving Large-Scale Extensive-Form Network Security Games via Neural Fictitious Self-Play](https://mlsanity.com/paper/2106.00897/) (2021)
- [Multi-Robot Adversarial Patrolling: Facing a Full-Knowledge Opponent](https://mlsanity.com/paper/1401.3903/) (2014)
- [A Dynamic Game Framework for Rational and Persistent Robot Deception With an Application to Deceptive Pursuit-Evasion](https://mlsanity.com/paper/1907.00459/) (2019)
- [Dynamic Programming for One-Sided Partially Observable Pursuit-Evasion Games](https://mlsanity.com/paper/1606.06271/) (2016)
- [CFR-MIX: Solving Imperfect Information Extensive-Form Games with Combinatorial Action Space](https://mlsanity.com/paper/2105.08440/) (2021)
- [A Survey of Decision Making in Adversarial Games](https://mlsanity.com/paper/2207.07971/) (2022)

## Built on by (most cited first, 6 of 6)

- [Reevaluating Policy Gradient Methods for Imperfect-Information Games](https://mlsanity.com/paper/2502.08938/) (2025)
- [Equilibrium Policy Generalization: A Reinforcement Learning Framework for Cross-Graph Zero-Shot Generalization in Pursuit-Evasion Games](https://mlsanity.com/paper/2511.00811/) (2025)
- [GraphChase: A Platform and Benchmark for Urban Network Security Games](https://mlsanity.com/paper/2501.17559/) (2025)
- [Fast and the Furious: Hot Starts in Pursuit-Evasion Games](https://mlsanity.com/paper/2510.10830/) (2025)
- [ARAC: Adaptive Regularized Multi-Agent Soft Actor-Critic in Graph-Structured Adversarial Games](https://mlsanity.com/paper/2511.08412/) (2025)
- [R2PS: Worst-Case Robust Real-Time Pursuit Strategies under Partial Observability](https://mlsanity.com/paper/2511.17367/) (2025)

## Abstract (arXiv)

Pursuit-evasion games (PEGs) model interactions between a team of pursuers and an evader in graph-based environments such as urban street networks. Recent advancements have demonstrated the effectiveness of the pre-training and fine-tuning paradigm in PSRO to improve scalability in solving large-scale PEGs. However, these methods primarily focus on specific PEGs with fixed initial conditions that may vary substantially in real-world scenarios, which significantly hinders the applicability of the traditional methods. To address this issue, we introduce Grasper, a GeneRAlist purSuer for Pursuit-Evasion pRoblems, capable of efficiently generating pursuer policies tailored to specific PEGs. Our contributions are threefold: First, we present a novel architecture that offers high-quality solutions for diverse PEGs, comprising critical components such as (i) a graph neural network (GNN) to encode PEGs into hidden vectors, and (ii) a hypernetwork to generate pursuer policies based on these hidden vectors. As a second contribution, we develop an efficient three-stage training method involving (i) a pre-pretraining stage for learning robust PEG representations through self-supervised graph learning techniques like GraphMAE, (ii) a pre-training stage utilizing heuristic-guided multi-task pre-training (HMP) where heuristic-derived reference policies (e.g., through Dijkstra's algorithm) regularize pursuer policies, and (iii) a fine-tuning stage that employs PSRO to generate pursuer policies on designated PEGs. Finally, we perform extensive experiments on synthetic and real-world maps, showcasing Grasper's significant superiority over baselines in terms of solution quality and generalizability. We demonstrate that Grasper provides a versatile approach for solving pursuit-evasion problems across a broad range of scenarios, enabling practical deployment in real-world situations.