Geometric Coherence via Weighted Matching for 3D Heterogeneous Multi-Agent Reach-Avoid Games

Prajwal Vijay

cs.ROSep 19, 2026

Geometric Coherence via Weighted Matching for 3D Heterogeneous Multi-Agent Reach-Avoid Games

Authors: Prajwal Vijay

Organizations: Dept. of Electrical Engineering, IIT Madras, Chennai, India

Abstract

We study assignment quality in 3D heterogeneous multi-agent reach-avoid games and identify a recurring failure mode of cardinality-only matching in geometrically structured scenarios, which we term Geometric Sprawl. In these cases, multiple maximum-cardinality assignments are available, but some induce spatially incoherent pairings and inefficient pursuit trajectories. Building on the evasion-space framework of Yan et al.~\cite{yan2022}, we introduce a cardinality-first weighted sequential matching method in which the Hamilton--Jacobi--Isaacs interception value $z_I(s,j)$ is used as a secondary assignment weight. Each sequential stage is solved with a min-cost max-flow backend, while the unweighted baseline uses the same solver with the weight term removed. We evaluate both methods on a deterministic 35-scenario benchmark (7 families & 5 initialization variants) under two regimes: a diagnostic stationary-unmatched setting and a hybrid saddle-point setting with goal-directed unmatched evaders. On this benchmark, the weighted method resolves 13 of 15 geometric stress-test instances that cause repeated timeouts for the unweighted baseline in the diagnostic regime, and under the hybrid regime improves mean captures from $3.20$ to $3.91$ (22% increase) and mean interception height from $3.87$ to $5.36$ (40% increase). We also report lower path tortuosity and lower angular-effort proxy values, suggesting smoother pursuit trajectories in this first-order simulation model. We release the simulator and benchmark suite at github.com/Prajwal-Vijay/geometric-coherence-weighted-matching to support reproducible evaluation of assignment strategies for 3D reach-avoid games.

Figures & tables

Panel of Figure 2 — Fig. 2 : Trajectory comparison between weighted (left, (a)(c)) and unweighted (right, (b)(d)) sequential matching under the diagnostic stationary-evader regime. Braided Corridors (top, (a)(b)) and Switchback Gate (bottom, (c)(d)) families shown.

Family	Strategy	Steps	Capt.	Esc.	$\bar{z}_{\mathcal{I}}$	$\bar{\tau}$	$J_{\theta}$
spread-mild	Weighted (ours)	2000	8.2	0.0	7.21	1.78	108
	Unweighted [ 1 ]	2000	8.2	0.0	3.55	3.64	259
	Random	2000	7.2	0.0	4.69	3.14	221
	Nearest-single	305	10.0	0.0	6.09	3.03	252
clustered	Weighted (ours)	2000	8.2	0.0	8.58	2.73	259
	Unweighted [ 1 ]	1381	9.4	0.0	5.18	2.84	383

TABLE I : Diagnostic study (stationary-unmatched evader policy): per-family averages over 5 variants, 3 pursuers vs. 10 evaders, max_steps

=2000

\bar{z}_{\mathcal{I}}

: avg. interception height (higher is better);

\bar{\tau}

: avg. path tortuosity (lower is better);

J_{\theta}

: avg. angular control effort (rad); For sequential strategies, Esc.

=0

at max_steps means remaining evaders became mathematically unresolvable (empty assignments) and timed out.

Family	Strategy	Steps	Capt.	$\bar{z}_{\mathcal{I}}$	$\bar{\tau}$	$J_{\theta}$
spread-mild	Weighted (ours)	131	3.0	5.41	1.09	14.7
	Unweighted [ 1 ]	131	2.0	5.69	1.00	0.0
	Nearest-single	148	2.0	6.98	1.29	66.6
clustered	Weighted (ours)	137	1.8	1.80	1.00	0.0
	Unweighted [ 1 ]	137	1.8	1.75	1.00	0.0
	Nearest-single	139	1.6	2.23	1.09	69.8

TABLE II : Adversarial Stress Test (Hybrid Saddle-Point Regime): Per-Family Averages, 3 Pursuers VS. 10 Evaders. Unmatched evaders charge toward

z=0

, matched evaders maneuver to interception. All Episodes terminate ALL_RESOLVED (Evaders either captured OR escaped).

Multi-Agent Systems

Multi-Agent Systems studies how autonomous agents coordinate, compete, communicate, and learn in shared or interdependent tasks.

See all 677 papers

Reach-Avoid Differential game with Reachability Analysis for UAVs: A decomposition approach
Dec 28, 2025Minh Bui, Simon Monckton, Mo ChenGame Theory Reachability Analysis
Simon Fraser University, Burnaby, BC V5A 1S6, Canada · Defense Research & Development Canada (DRDC), Medicine Hat, Alberta T1A 8K6, Canada
ITA-LaCAM: A Complete and Scalable TAPF Solver via Assignment-Aware Configuration-Space Search
Sep 13, 2026Yimin Tang, Han Zhang, Shao-Hung Chan +4Multi-Agent Path Finding Multi-Robot Task Allocation
Thomas Lord Department of Computer Science, University of Southern California · Symbotic · Department of Computer Science, University of California Irvine
Less is More: Robust Zero-Communication 3D Pursuit-Evasion via Representational Parsimony
Mar 9, 2026Jialin Ying, Zhihao Li, Zicheng Dong +2Multi-Agent Systems Multi-Agent Coordination
Department of Automation, Central South University, Changsha, China

Dec 28, 2025J/K move · Enter open · S save

Reach-Avoid Differential game with Reachability Analysis for UAVs: A decomposition approach

Minh Bui, Simon Monckton, Mo Chen

Simon Fraser University, Burnaby, BC V5A 1S6, Canada · Defense Research & Development Canada (DRDC), Medicine Hat, Alberta T1A 8K6, Canada

Game Theory Reachability Analysis Aerial Robotics

Open paper AskPDF arXiv

Reach-avoid (RA) games have significant applications in security and defense, particularly for unmanned aerial vehicles (UAVs). These problems are inherently challenging due to the need to consider obstacles, consider the adversarial nature of opponents, ensure optimality, and account for nonlinear dynamics. Hamilton-Jacobi (HJ) reachability analysis has emerged as a powerful tool for tackling these challenges; however, while it has been applied to games involving two spatial dimensions, directly extending this approach to three spatial dimensions is impossible due to high dimensionality. On the other hand, alternative approaches for solving RA games lack the generality to consider games with three spatial dimensions involving agents with non-trivial system dynamics. In this work, we propose a novel framework for dimensionality reduction by decomposing the problem into a horizontal RA sub-game and a vertical RA sub-game. We then solve each sub-game using HJ reachability analysis and consider second-order dynamics that account for the defender's acceleration. To reconstruct the solution to the original RA game from the sub-games, we introduce a HJ-based tracking control algorithm in each sub-game that not only guarantees capture of the attacker but also tracking of the attacker thereafter. We prove the conditions under which the capture guarantees are maintained. The effectiveness of our approach is demonstrated via numerical simulations, showing that the decomposition maintains optimality and guarantees in the original problem. Our methods are also validated in a Gazebo physics simulator, achieving successful capture of quadrotors in three spatial dimensions space for the first time to the best of our knowledge.

Abstract

Multi-Agent Systems

Explore similar work

Reach-Avoid Differential game with Reachability Analysis for UAVs: A decomposition approach

ITA-LaCAM: A Complete and Scalable TAPF Solver via Assignment-Aware Configuration-Space Search

Less is More: Robust Zero-Communication 3D Pursuit-Evasion via Representational Parsimony