Upper and Lower Bounds for a Class of Constrained Linear Time-Varying Games
Vincent Liu, Chris ManziePeter M. Dower · 2025
Read Upper and Lower Bounds for a Class of Constrained Linear Time-Varying Games by Vincent Liu, Chris ManziePeter M. Dower (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-08310.txt.
Introduction
Two players fighting over the end state of a moving system pose a hard control problem when the system changes over time. Vincent Liu, Chris Manzie, and Peter Dower build an algorithm that brackets the true value of such a game. One side seeks to lower a final cost, the other to raise it. Runs of a simpler single-player system give an upper bound. A set of flat surfaces gives a lower bound.
Both bounds rest on solid math linked to a classic equation for game values. The cost of the method grows with the number of runs and surfaces used, not directly with system size. That keeps it workable for fairly large systems. Guaranteed brackets matter for control tasks where safety is at stake.
Catalog record
| CREATOR | Vincent Liu, Chris ManziePeter M. Dower |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 83 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-08310
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Upper and Lower Bounds for a Class of Constrained Linear Time-Varying Games Thanks: This research was supported by the Australian Commonwealth Government and the Faculty of Engineering and Information Technology (University of Melbourne) through the Ingenium Scholarship and the Air Force Office of Scientific Research (Grant number: FA2386‐22-1-4074). Vincent Liu, Chris ManziePeter M. Dower Abstract This paper develops an algorithm for upper- and lower-bounding the value function for a class of linear time-varying games subject to convex control sets. In particular, a two-player zero-sum differential game is considered where the respective players aim to minimise and maximise a convex terminal state cost. A collection of solutions of a single-player dynamical system subject to a trimmed control set is used to characterise a viscosity supersolution of a Hamilton-Jacobi (HJ) equation, which in turn yields an upper bound for the value function. Analogously, a collection of hyperplanes is used to characterise a viscosity subsolution of the HJ equation, which yields a lower bound. The computational complexity and memory requirement of the proposed algorithm scales with the number of solutions and hyperplanes that characterise the bounds, which is not explicitly tied to the number of system states. Thus, the algorithm is tractable for systems of moderately high dimension whilst preserving rigorous guarantees for optimal control and differential game applications. Keywords: Hamilton-Jacobi equations, viscosity solutions, differential games, linear time-varying systems, reachability analysis 1 Introduction The concept of a value function arises in various control and estimation problems including the synthesis of optimal feedback control laws and filters [ 1 , 2 ] , the modelling of differential games [ 3 ] , the design of optimal trajectories [ 4 ] , and the characterisation of reachable sets [ 5 ] . Though versatile in its applications, with the exception of specific problems such as linear quadratic regulators, easy-to-compute characterisations of the value function are not readily available. Under mild assumptions, the value function admits an equivalent characterisation as the solution of a Hamilton-Jacobi (HJ) equation and conventional grid-based approaches such as level set methods [ 6 ] , Markov chain approximations [ 7 ] , and semi-Lagrangian schemes [ 8 ] provide a general purpose means of numerically solving these HJ equations. However, these approaches suffer from the curse-of-dimensionality, which typically limits their use to system with no more than four states [ 9 ] . Modern literature on numerical methods for solving HJ equations largely focus on mitigating this well-known curse-of-dimensionality. In the special case where the Hamiltonian is state-independent, a generalised Hopf formula may be used to characterise solutions of HJ equations via a finite-dimensional nonlinear program [ 10 ] , which yields a highly parallelisable means of computing the value function. Otherwise, for systems where the control input is of lower dimension than the state, optimistic planning algorithms [ 9 ] and tree-structure approaches [ 11 ] can yield efficient approximations of the value function as discretisation is performed in the control space as opposed to the state space. In a more general setting, parametrisation of the value function via a finite collection of basis functions, such as in max plus methods [ 12 ] , neural networks [ 13 ] , and polynomial approximations [ 14 ] , may also yield computationally tractable approximation schemes for systems of moderate dimension. Provable properties for approximations of the value function are often desirable for a range of applications, yet such properties can be difficult to obtain for the aforementioned numerical schemes. For instance, in reachability analysis, upper and lower bounds for the value function may be used to produce inner- and outer-approximations of reachable sets [ 15 ] . To this end, classic comparison results for viscosity solutions of HJ equations (see, e.g., [ 16 , Thm 5.2.7, p.109] ) can facilitate the construction of verifiable bounds for the value function. In the case of time-invariant polynomial systems, polynomial supersolutions and subsolution of HJ equations can be generated via a sum-of-squares program, which yields upper and lower bounds for the value function [ 17 , 18 ] . Similar ideas are utilised in [ 19 ] wherein super- and subsolutions are characterised for bilinear systems in which the state matrix lies within a matrix ellipsoid. In this paper, an algorithm is developed for upper- and lower-bounding the value function for a class of linear time-varying (LTV) games subject to convex control sets. In particular, a two-player zero-sum differential game is considered where the respective players aim to minimise and maximise a terminal state cost, which is assumed to be convex. The proposed upper and lower bounds are, respectively, a viscosity supersolution and subsolution of an HJ equation associated with the differential game. The notion of viscosity solution is explicitly utilised in this work to construct bounds that are not continuously differentiable. The proposed upper bound in this work is a generalisation of [ 20 , Section III.b] to a differential game setting. Compared to [ 20 ] , one additional assumption is imposed, which roughly requires that the minimising player has greater control authority than the maximising player. The proposed upper bound is characterised by a collection of solutions of an auxiliary single-player system whose controls belong to a ‘trimmed’ control set. If these solutions are optimal with respect to minimising the terminal state cost, the upper bound coincides with the value function along these solutions, yielding a tight upper bound. When required, the values of the upper bound can be accessed by solving a quadratic program. The proposed lower bound is characterised by the maximum of a collection of hyperplanes, which can be made to coincide with the value function along the same set of solutions that characterise the upper bound. Thus, the upper and lower bounds provide an interval in which the value function must lie and this interval collapses along a characteristic set of solutions. Both the computational complexity and memory requirement of the proposed bounds are tied to the sparsity of the collection of solutions and hyperplanes, which is independent of the number of system states. Note that hyperplanes have been previously used to construct outer-approximations of reachable sets for LTV games in [ 21 ] , although a characterisation as a lower bound for the value function is not provided. This work extends on [ 21 ] by generalising the control sets, characterising the maximum of the hyperplanes as a viscosity subsolution, and demonstrating tightness of the lower bound. In [ 22 ] , a collection of hyperplanes have also been used to lower bound the value function, albeit for discrete-time nonlinear systems in a single-player setting. The remainder of this paper is organised as follows. Section 2 presents the problem setting and reviews the necessary preliminaries for the two-player differential game considered in this work. Section 3 demonstrates the upper and lower bound guarantees of the proposed approximating functions. The application of these results to reachability analysis is discussed in Section 4 . Section 5 then describes an algorithmic procedure for computing the proposed upper and lower bounds. Finally, an illustrative example is presented in Section 6 . Notation Let {\mathbb{N}}\doteq\{1,2,\ldots\},{\mathbb{R}} , and {\mathbb{R}}_{\geq 0} denote the set of natural, real, and non-negative real numbers, respectively.