CS Paper Radar

Robust Game-theoretic Motion Planning over Extended Time Horizons

Bennet Outland, Vishala Arya

cs.MA eess.SY ·submitted 2026-09-26 00:07 UTC · v1

Abstract

This work presents a solution to nonconvex, game-theoretic motion planning problems subject to disturbances over long time horizons. The problem is posed as a partially-decoupled generalized Nash equilibrium problem, in which each agent's dynamics depend only on its own state and control, admitting fast solution methods for competitive multi-agent motion planning. An algorithm, WOLF, is developed that applies receding-horizon model predictive control to an open-loop differential games solver based on sequential convexification. In contrast to robust formulations that fix the uncertainty description offline, the robustness tube here is itself a dynamic state, co-optimized with the trajectory, and its thickness directly sets the tightening of the shared coupling constraints. A sufficient condition is derived under which a nominal trajectory satisfying constraints tightened against all agents' error bounds remains feasible for every admissible disturbance realization. The method is demonstrated on two adversarial on-orbit games with coupled translational-attitude dynamics: a stealthy co-orbital jamming game under an active detection-probability bound, and a sun-blocking game in which an adversary disables an evader by decreasing solar power

Closest papers

Nearest neighbours by meaning across the whole index.

Approximate Feedback Nash Equilibria in Constrained Differential Games via Model Predictive Control with Upper Bound Guarantees

eess.SY cs.GT ·2026-10-03 ·Balint Varga, Karl Handwerker, Imre Rudas, Peter Galambos
theory similarity 0.70
Abstract

Physical human--machine interaction and other multi-agent control settings require decision-making policies that adapt online. Differential games provide a principled framework where each agent optimizes an individual objective while anticipating the other's response. The relevant solution concept in many applications is the feedback Nash equilibrium (FNE), which yields time-consistent state-feedback strategies. However, computing the FNE is demanding and becomes intractable when state and input constraints must be enforced, motivating the need for approximate methods. This paper presents a Model Predictive Control (MPC) approach that approximates infinite-horizon FNE trajectories through repeated solution of finite-horizon open-loop games. An auxiliary-game formulation is introduced that selects prediction horizons and terminal costs to approximate the feedback-game optimality conditions. The approach is extended to incorporate hard constraints via a constrained open-loop game formulation. For the unconstrained setting, an analytic upper bound on the state-trajectory deviation between the MPC-induced and FNE trajectories is derived, enabling quantitative performance certification. Numerical examples illustrate the effectiveness of the proposed method compared with baseline approaches from the literature.

0.26

Where Planning Changes the Outcome of Orbital Games

cs.MA cs.AIcs.ROeess.SY ·2026-10-16 ·Duncan Eddy, Mahdi Al-Husseini, Mykel J. Kochenderfer
similarity 0.66
Abstract · IEEE Aerospace Conference 2027

This paper introduces OrbitalGym, a simulation environment for studying when planning algorithms or system design determine the outcome of adversarial orbital encounters. In an orbital game, two non-cooperative teams of satellites maneuver during rendezvous and proximity operations to win a differential-reward objective. Advances in terrestrial game playing have prompted many methods for orbital games, but studies typically evaluate one method in one scenario, often against a passive or random defender. It is unclear whether better planning matters once vehicle capability (maneuverability, sensing, communications) and adversarial responses are considered. OrbitalGym is a JAX-based environment supporting varying numbers of agents, state representations (position, velocity, attitude, fuel), explicit or implicit communication, and proximity or conical field-of-view sensors. It compiles games to batched GPU code, enabling large-scale parallel simulation of policies across many configurations. This identifies regimes where policy choice affects outcomes and regimes where system capability dominates. We study two close-range games: pursuit-evasion, where one spacecraft tries to capture another, and lady-bandit-guard, where a guard prevents an attacker from reaching a protected asset. We compare PD, LQR, model predictive path integral control, and Monte Carlo tree search over ratios of thrust and propellant, initial separation, game duration, sensor capability, and the definition of capture. In pursuit-evasion the propellant ratio decides most encounters: against five of six evader policies, pursuer policy changes capture probability by 10 percent or more in at most 15 of 90 capability configurations. In lady-bandit-guard, policy matters more: against bandits able to reach the asset, a better guard policy raises defense probability by at least 10 percent in 56 to 74 of 90 configurations.

0.15

Convex Pursuit-Evasion Games for Spacecraft Proximity Operations on Circular and Elliptical Orbits

eess.SY math.OCastro-ph.IMmath.DS ·2026-09-13 ·Omer Burak Iskender
published similarity 0.66
Abstract · 38 pages, 10 figures, 19 tables (9 in appendices); accepted at Aerospace Science and Technology, 11 September 2026; ID: AESCTE-D-26-03480R1

Inspecting or servicing a non-cooperative spacecraft is a two-player game: the target can thrust to defeat the inspector's plan. Hamilton-Jacobi-Isaacs reachability answers such games exactly but its cost grows exponentially with state dimension, while learning-based controllers scale yet certify nothing. Convex formulations are the usual escape, typically cast as convex-concave saddle-point problems. That framing fails in the terminal-distance orbital game: with effort regularization, the payoff is convex in both controls, so no pure open-loop saddle point need exist. In its place we derive two exact one-sided guarantees read from the players' terminal reachable sets via support functions: an escape certificate proving the target can hold a guaranteed standoff, and a security strategy bounding the miss distance the inspector can force. Together they bracket the engagement without assuming player rationality, and over two hundred perturbed trials the escape certificate separated capture from escape without error. A projected extragradient method supplies a strategy pair in about 25 ms, certified in place by best-response gaps. The construction carries unchanged to elliptical reference orbits via Yamanaka-Ankersen dynamics, where the orbital phase moves miss distance by nearly a factor of two, reproduced by nonlinear Keplerian propagation. Under receding-horizon play the inspector captures in half of ten representative engagements. Angles-only navigation error, keep-out zones, multiple pursuers, and closed-loop play are treated as extensions.

0.68

Strategically Robust Game-Theoretic Multi-Agent Trajectory Optimization

eess.SY cs.GTcs.MA ·2026-09-28 ·Victor L. Qin, Nicolas Lanzetti, Saverio Bolognani, Hamsa Balakrishnan
published similarity 0.65
Abstract · 7 pages, 5 figures, accepted to CDC 2026

Aviation authorities worldwide expect Advanced Air Mobility (AAM) traffic management to be decentralized among service providers, requiring AAM flights to autonomously plan trajectories by predicting other flights' control inputs rather than relying on centralized coordination. Game-theoretic approaches that formulate multi-agent collision avoidance as an exact dynamic potential game can efficiently find open-loop equilibria, but they assume that agents exactly follow their equilibrium trajectories---an unrealistic assumption given uncertainties in actuation, perception, and computation. We propose a strategically robust formulation where each agent protects against a fictitious adversary that, for each timestep, perturbs other agents' control inputs within a bounded budget to minimize distance at that timestep. We show that, under reasonable assumptions on agents' distance cost and robustness levels, the strategically robust game remains an exact dynamic potential game and admits a quasi-closed-form solution to the inner adversarial problem for linear dynamics, which limits computational overhead. Experiments with up to eight agents using logarithmic distance costs show that strategic robustness selects more robust trajectories in high-collision-risk configurations while leaving low-risk trajectories nearly unchanged, with only a modest increase in runtime.

0.28

Certificate-Carrying Distributed Model Predictive Control on Product Manifolds with $\mathrm{SO}(3)$

eess.SY math.OC ·2026-09-25 ·Shengjun Zhang, Tingyi Liu, Lei Xu, Tao Yang
theory similarity 0.64
Abstract · 12 pages, 3 figures. Submitted to Automatica

This paper studies constraint certification in synchronous distributed model predictive control (DMPC) when neighboring predictions change between sampling instants. Before the parallel local solves, each agent communicates a shifted prediction and an announced update budget. A hard trajectory trust region makes that budget enforceable, while an edge-wise feasibility cap computed from the shifted packets keeps the fallback feasible without using any current optimizer output. Distance and relative-attitude constraints are tightened with explicit Lipschitz constants and two budget layers: one accounts for the simultaneous neighbor update and the other retains a checkable shift reserve. We prove hard pairwise constraint satisfaction and recursive feasibility under stated nominal-execution and terminal assumptions, give the additional residual caused by execution error, and derive a local practical value-decrease bound. A spacecraft formation example uses hard terminal and pairwise constraints, a geodesic relative- attitude constraint on $\SO$, and reproducible terminal-set checks. Comparisons with fixed, trajectory-only, and windowed online margins show that the proposed budget reduces conservatism while preserving a positive shifted-feasibility margin.

0.22

Certifiable Explicit Model Predictive Control for Spacecraft Rendezvous under Bounded Disturbances

eess.SY ·2026-08-23 ·Diogo Silva, Daniel Silvestre
similarity 0.63
Abstract · 12 pages, 5 figures, 2 tables. Submitted to IEEE Transactions on Control Systems Technology

Two properties of optimization-based controllers such as model predictive control (MPC) limit their use in space flight. The online computing time varies and can exceed the sampling period, and the closed-loop behavior carries no formal guarantee. Explicit MPC, where a parametric solution of the optimization problem is computed, replaces the on-board optimization with a lookup table of piecewise-affine functions with a fixed execution time. However, it has been regarded as only applicable to small horizons, since the number of regions bounds the memory the table occupies and admits only an exponential bound in the horizon. This paper builds on recent developments in parametric solutions of quadratic programs and nonconvex reachability analysis to provide an entire pipeline for spacecraft rendezvous controllers under the Clohessy-Wiltshire dynamics. For this application, efficient data structures can be constructed to encode the control law, both from a computing time and a memory standpoint. In addition, the controller can be verified offline with a guaranteed closed-loop stability certificate by resorting to reachability analysis with hybrid zonotopes. At a 51-step horizon the rendezvous law occupies 10.5 MB and is evaluated in under 300 ns. The occupied memory would fit for instance the CubeSat flight computer ARM9-class AT91RM9200 meaning that the horizon limitation does not hold when the partition is built with the parametric solvers and data structures shown in this paper.

0.16

Conflict-Predictive Variable Horizons in Multi-Drone Distributed Model Predictive Control

cs.RO cs.AIeess.SY ·2026-09-07 ·Linda Mümken, Michael Schwung, Stefan Lier, Andreas Schwung
theoryhot direction similarity 0.62
Abstract · 14 pages, 6 figures, 2 tables, is already submitted to IEEE Transactions on Systems, Man, and Cybernetics as journal-paper (current status "…

In distributed model predictive control for multi-drone collision avoidance, a fixed prediction horizon forces a compromise: a short horizon is inexpensive but reacts late to approaching neighbors, whereas a long one anticipates conflicts at a per-step cost that grows superlinearly with its length. We propose a conflict-predictive variable horizon that each drone sets locally, leaving the distributed model predictive control itself unchanged. From a short history of observed positions, a drone extrapolates the flight lines of its neighbors, tests each against its own using confidence funnels that narrow with prediction range, and obtains each time to conflict in closed form. The horizon is then the smallest admissible value whose planning window covers the farthest predicted conflict. It collapses to its minimum in clear airspace and grows only when a conflict lies ahead. Provided this minimum meets a single computable feasibility bound, we prove that recursive feasibility and asymptotic stability are preserved for every horizon the policy can select. These guarantees hold for a linear model, and a cascaded inner loop reduces each quadrotor's translational dynamics to a perturbed double integrator, so they carry over to the linearized quadrotor model and, as practical stability, to the full nonlinear one. In simulation on dense antipodal-swap benchmarks, the variable horizon reduces both per-step solver cost and total computation well below those of a long fixed horizon, and it maintains separation in every run, which a short fixed horizon of comparable per-step cost does not.

0.32

Game-Theoretic Control with Constrained Potential Surgery

cs.RO ·2026-09-25 ·Zhiyuan Zhang, Panagiotis Tsiotras
similarity 0.62
Abstract

Constrained general-sum dynamic games are a popular formulation for highly interactive multi-agent planning problems. In recent years, Generalized Nash Equilibrium (GNE) solvers have achieved real-time performance for small dynamic games. However, solution speed still remains a bottleneck, and controlling even a small number of agents (e.g., more than four) in a dynamic task remains elusive. In addition, Newton solvers that focus on the first-order conditions are vulnerable to non-Nash saddle points, limiting the usefulness of the provided solution. In this work, we propose a fast and versatile interior point solver for constrained dynamic games, along with a computationally efficient second-order correction that increases the probability of converging to a local GNE solution in constrained dynamic games. The performance of the proposed method is evaluated on numerical benchmarks and a physical experiment involving scaled race cars.

0.24