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

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

Prajwal Vijay · N/A · 2026

reinforcement-learning benchmark
PDF arXiv Code (GitHub)

Framework

N/A

License

N/A

Stars

N/A

Summary

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 \emph{Geometric Sprawl}.

Abstract Summary

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 \emph{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 \href{https://github.com/Prajwal-Vijay/geometric-coherence-weighted-matching}{github.com/Prajwal-Vijay/geometric-coherence-weighted-matching} to support reproducible evaluation of assignment strategies for 3D reach-avoid games.

Key Points

  • 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 \emph{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.

Problem Formulation

Consider a reach-avoid game with $N_{p}$ pursuers $\mathcal{P}=\{P_{1},\ldots,P_{N_{p}}\}$ and $N_{e}$ evaders $\mathbb{E}=\{E_{1},\ldots,E_{N_{e}}\}$ in $\mathbb{R}^{3}$. The goal region is $\Omega_{\text{goal}}=\{x\in\mathbb{R}^{3}\mid z\leq 0\}$ and the play region is $\Omega_{\text{play}}=\{x\in\mathbb{R}^{3}\mid z>0\}$.

All players are holonomic mass points with first-order kinematics [ 1 ] : where $u_{P_{i}}(t),u_{E_{j}}(t)\in\mathbb{S}^{2}$ are heading unit vectors and $v_{P_{i}},v_{E_{j}}\in\mathbb{R}^{+}$ are speeds.

Problem Formulation — Geometric Coherence via Weighted Matching for 3D Heterogeneous Multi-Agent Reach-Avoid Games
Fig. 1 : Architecture Diagram

Weighted Matching: Resolving Geometric Sprawl

The SOTA formulation [ 1 ] maximizes only the number of captured evaders. A coalition intercepting an evader at $z=0.01$ above the goal plane is treated identically to one catching an evader at $z=7.0$—both count as one capture. This indifference to capture quality is acceptable when the assignment has a unique maximum-cardinality matching. It is catastrophic when many such matchings exist.

Weighted Matching: Resolving Geometric Sprawl — Geometric Coherence via Weighted Matching for 3D Heterogeneous Multi-Agent Reach-Avoid Games
(a) Braided Corridors weighted The Pursuers sequentially capture the evaders without going back and forth between the corridors and maintain clear responsibility for the rougly ’parallel’ corridors.

Simulation Framework and Benchmark Suite

The simulation is implemented in Python, utilizing SciPy for sequential least squares programming (SLSQP) and Matplotlib for 3D visualization. To support reproducible ablation studies, the architecture is structured into three interacting tiers as depicted in figure 1 : Scenario & Evaluation Tier : Generates the 35-scenario deterministic benchmark suite.

It initializes heterogeneous agent configurations (speeds, capture radii) and logs fleet-wide telemetry, including path tortuosity and angular control effort ($J_{\theta}$).

Simulation Framework and Benchmark Suite — Geometric Coherence via Weighted Matching for 3D Heterogeneous Multi-Agent Reach-Avoid Games
(b) Braided Corridors Unweighted Matching blindness leads to geometric sprawl. This unweighted approach leads to chaotic criss-crossing of assignments, where a pursuer on the left(orange) is winding sharply right to address the rightmost evader.

Results

Performance metrics . We report steps to resolution and termination reason ( all_resolved vs. max_steps ), captured/escaped evader counts, mean interception height and two trajectory-quality metrics: path tortuosity $\tau=L_{\mathrm{path}}/L_{\mathrm{chord}}$ and angular-effort proxy In our first-order holonomic simulator, lower $\tau$ and $J_{\theta}$ indicate smoother and less aggressively turning trajectories.

Results — Geometric Coherence via Weighted Matching for 3D Heterogeneous Multi-Agent Reach-Avoid Games
(c) Switchback Gate weighted Shows orderly and spatially coherent clearing in the switchback scenario. Assignments are local and efficient, pursuers sweep their respective evaders in mostly monotone, local trajectories.

Sources and Demonstrations

Figures are reproduced from Vijay See the full paper for experimental details and the project page, when the paper links one, for demonstrations and videos.

Share

Related Papers

4D Radar Perception Algorithms for Autonomous Driving: A Review
arXiv preprint

4D Radar Perception Algorithms for Autonomous Driving: A Review

Xumin Wu, Jun Zhou, Jilin Mei et al.

Research on 4D millimeter-wave radar perception algorithms has flourished in recent years, extending from signal processing and object detection to semantic segmentation, motion estimation, occupancy prediction, and dynamic scene reconstruction.

vision reinforcement-learning benchmark
PDF Beginner
A Review Of Robotic World Models For Dynamic Environments Based On Factor And Scene Graphs
arXiv preprint

A Review Of Robotic World Models For Dynamic Environments Based On Factor And Scene Graphs

Marco Giberna, Miguel Fernandez-Cortizas, Jose Luis Sanchez Lopez et al.

Models based on graphs have emerged in robotics as a powerful foundation for internal world representations, where factor and scene graphs are among the most prominent model types found in the related literature and in successful robotic solutions.

vision reinforcement-learning benchmark
PDF Beginner