Solvability of Approximate Reach-Avoid Games Mario Gleirscher Abstract Objective: In a companion paper, we propose a parametric hybrid automaton model and an algorithm for the online synthesis of robustly correct and near-optimal controllers for cyber-physical system with reach-avoid guarantees. A key part of this synthesis problem is based on a weighted discretised game and solved via scope-adaptive discrete dynamic programming. Approach: This work examines proofs of key properties of the discussed algorithm. Evaluation: The main proof is by induction over the stages of a discrete Hamilton-Jacobi-Bellman system of equations. Contribution: The results include a game solvability theorem and identify necessary and sufficient conditions for its applicability. 1 Introduction Motivation. Control of non-linear, disturbed dynamical systems can be solved by constructing provably robust (i.e., for safety) and near-optimal (i.e., for minimum-cost reachability) controllers. To accommodate parametric uncertainties, such controllers have to be synthesised online, that is, during operation. In a companion paper [ 4 ] , we formalise such a control problem as a parametric weighted hybrid game automaton (HGA) with reach-avoid winning conditions. The automaton enables a flexible three-tier separation of control concerns: supervisory (e.g., moving obstacle evasion), tactical (e.g., near-optimal trajectory tracking), and sub-tactical (e.g., local stability) control. We provide a bounded solution algorithm for the discretised modal games of the HGA. The algorithm uses step-shielded discrete dynamic programming (DDP) and supports non- and quasi-stationary policies, increasing robustness to disturbance at the cost of performance [ 6 ] . To prepare our algorithm for online use, we (slightly) reduce DDP’s curse-of-dimensionality problem by scope adaptation 1 1 1 The relevant fraction of the state space is selected according to the current system state and extended on-the-fly to increase game solvability. and fixpoint approximation for the winning region. The modal synthesis algorithm is part of a HGA player. Challenge and Research Question. Given a system described as a HGA, part of the system’s assurances can be based on the guarantees provided by the solutions of the parametric modal games. Based on our exhaustive numerical algorithm for near-optimal online synthesis, under which assumptions does the algorithm construct a correct solution providing a robust reach-avoid guarantee? Approach and Application. Our notion of approximation encompasses a bound on the number of stages, a control robustness margin, as well as state space discretisation and dynamic scoping. We first examine necessary and sufficient conditions for game solvability and then use these conditions to provide a solvability proof. The HGA, the algorithms (their C ++ implementation), and an experimental evaluation are discussed in more detail in [ 4 ] . Contributions. In addition to our model and experiments in [ 4 ] , this work • provides a solvability (i.e., controller existence) theorem using a numerical Hamilton-Jacobi-Isaacs (HJI) equation [ 7 ] as a generic inductive invariant of the incrementally computed winning region and • identifies several conditions under which the synthesised controllers guarantee \delta -robust bounded correctness, in particular, safety for at least N stages and liveness by reaching goals within N stages; both under rejection of delayed bounded disturbance. Under the identified assumptions, we obtain a decision procedure for approximate modal reach-avoid games using a DDP-based \operatorname{\mathcal{O}}(N|{\mathbb{X}}||\mathcal{U}||\mathcal{D}|) -algorithm. Outline. Section 2 elaborates on the framework used in [ 4 ] . In Section 3 , we discuss the solvability conditions for our reach-avoid synthesis with guarantees. Based on these conditions, Section 4 presents a solvability theorem and a control barrier certificate. The Sections 5 and 6 reflect on the approach and summarise key findings. Details on the proof are presented in Appendix A . 2 Preliminaries This section introduces terms and definitions and finishes with a specification of the synthesis problem building on the solvability of reach-avoid games. Notation. For a set of variables \mathit{Var}=X\uplus U\uplus D , let {\mathbb{X}}\subset\mathbb{Z}^{X} be an X -typed, finite, m -dimensional Euclidean state space , 2 2 2 For a 3D coordinate \mathbf{p} , we use the typical naming convention \mathbf{p}=(x,y,z)^{\intercal} . and let \mathcal{U} and \mathcal{D} be U - and D -typed control and disturbance ranges, each including \mathbf{0} . Moreover, let the classes of terms \mathcal{T}(\mathit{Var}) and constraints \mathcal{C}(\mathit{Var}) over \mathit{Var} . \lVert\cdot\rVert is the corresponding 2-norm, \langle\cdot\rangle the scalar product, A\oplus B=\{a+b\mid a\in A\land b\in B\} the Minkowski sum of A,B\subseteq{\mathbb{X}} , and A|_{\mathit{Var}^{\prime}} the projection of tuples in A to variables in \mathit{Var}^{\prime}\subseteq\mathit{Var} , 3 3 3 We omit set parentheses when referring to singleton sets in subscripts. and \dashrightarrow indicates a partial map. Point-wise operators are lifted as usual. 4 4 4 For example, \min,\max on vectors of sets are evaluated element-wise and return a vector of scalars. Negation of a set returns the set of negated elements. Moreover, \underline{I} and \bar{I} denote the lower and upper bounds of an interval I\subseteq\mathbb{R} and \underline{I}..\bar{I} signifies that I\subseteq\mathbb{Z} . [\![\varphi]\!]_{\mathfrak{M}} denotes \varphi ’s models in domain {\mathfrak{M}} , 5 5 5 For example, the class of states, state pairs, sequences, or transition systems. formally, [\![\varphi]\!]_{\mathfrak{M}}=\{M\in{\mathfrak{M}}\mid M\models\varphi\} . Trajectories. Given the finite sequences \mathbb{X}^{\star} over {\mathbb{X}} , the concatenation \bar{x}\bar{x}^{\prime} of \bar{x},\bar{x}^{\prime}\in\mathbb{X}^{\star} , the length |\bar{x}| of \bar{x} , and its value \bar{x}_{k} at position k\in 1..|\bar{x}| , we call \bar{x} a \Delta -trajectory if \forall k\in 1..|\bar{x}|-1\colon\bar{x}_{k+1}\in\bar{x}_{k}\oplus\Delta with convex \Delta\subseteq{\mathbb{X}} constraining changes per transition. 6 6 6 For example, \Delta=\{-2,1,0,1,2\}^{m}=[-2,2]^{m}=[\pm 2]^{m} restricts changes to the discrete centered hyper-cube of length 5. For convenience, \bar{x} is also used as the set of its states. \bar{x} is said to be {\mathbb{X}} -continuous if \Delta enforces the minimal observable change in all changed {\mathbb{X}} -components (e.g., \Delta=[\pm 1]^{m} for \mathbb{Z} ). 7 7 7 It can be shown that trajectory {\mathbb{X}} -continuity is preserved under projection. Let \bar{\mathbb{X}}(\Delta),\tilde{\mathbb{X}}\subset\mathbb{X}^{\star} be the classes of \Delta -trajectories and {\mathbb{X}} -continuous trajectories \tilde{\mathbb{X}}=\bar{\mathbb{X}}([\pm 1]^{m}) , respectively. We write \bar{\mathbb{X}} if \Delta is clear from the context. Given \bar{x}\in\bar{\mathbb{X}}(\Delta) , \mathop{\mathit{}}{ct}(\bar{x})=\arg\min_{\bar{x}^{\prime}\in\tilde{\mathbb{X}},\,\bar{x}\subseteq\bar{x}^{\prime}}\lVert\bar{x}^{\prime}\rVert provides a shortest continuous trajectory \bar{x}^{\prime}\supseteq\bar{x} . We obtain \bar{x}^{\prime}\in\bar{\mathbb{X}}(\Delta) by the triangle inequality. Weighted Hybrid Game Automata. Given a set of modes Q , an alphabet A , events E\subseteq Q\times A\times Q , and the hybrid state space {\mathcal{S}}=Q\times{\mathbb{X}} , a weighted HGA G=(\mathit{Gra},\mathit{Var},\mathit{Ini},\mathit{Inv},\mathit{f},\mathit{Jmp},F) comprises a • mode transition graph \mathit{Gra}=(Q,A, E) , • initial conditions \mathit{Ini}\colon Q\to\mathcal{C}(X) , • invariants \mathit{Inv}\colon Q\to\mathcal{C}(X) , • flow constraints \mathit{f}\colon{\mathcal{S}}\to\mathcal{C}(\mathit{Var}\cup\dot{X}) , • jump conditions \mathit{Jmp}\colon E\to\mathcal{C}(\mathit{Var}\cup X^{+}) comprised of guards and updates, and • weighted winning conditions F\colon{\mathcal{S}}\to 2^{\mathcal{T}(\mathit{Var})} , generalising final conditions \mathit{Fin}\colon Q\to\mathcal{C}(X) [ 5 ] . The copies \dot{X} and X^{+} refer to the time derivatives and discrete updates of X . \operatorname{grd}(e) and \operatorname{upd}(e) denote the guard and update conditions of \mathit{Jmp}(e) . In the remainder, we frequently use {\mathbf{s}}=(q,{\mathbf{x}})\in{\mathcal{S}} for a state of G . Integer Difference Games. Let \Pi_{\mathcal{Y}}={\mathbb{X}}\times\mathbb{N}_{+}\dashrightarrow\mathcal{Y} be a strategy space for a player with alphabet \mathcal{Y} . Given a scope \mathcal{X}\subseteq{\mathbb{X}} , a flow constraint \mathit{f} , and its discretised Taylor expansion \hat{\mathit{f}} , a state {\mathbf{s}} of G can be associated with a discretised two-player game G_{\mathbf{s}}=(\mathcal{X},\hat{\mathit{f}},F) . 8 8 8 Players share the state and time but do not know each others’ future actions. We use {\mathbf{u}}\colon\Pi_{\mathcal{U}} and {\mathbf{d}}\colon\Pi_{\mathcal{D}} to describe the memory-less strategy profile of the two players, controller and environment, based on the non-empty control and disturbance ranges \mathcal{U} and \mathcal{D} . For the weighted reach-avoid winning condition F=(L,\Phi) with stage and terminal costs L and \Phi , we employ \displaystyle L({\mathbf{u}},{\mathbf{d}};{\mathbf{s}},k)=\begin{cases}0,\;\text{if}\;\rho\land\neg\alpha\\ \top,\;\text{if $\alpha$ (shielded)}\\ \lambda({\mathbf{u}},{\mathbf{d}};{\mathbf{x}},k),\;\text{otherwise}\end{cases}\Phi({\mathbf{s}})=\begin{cases}0,\;\text{if}\;\rho\land\neg\alpha\\ \top,\;\text{otherwise}\end{cases} (1) where \rho,\alpha\colon\mathcal{C}(\mathit{Var}) specify the goal and unsafe regions to be reached and avoided, respectively. We assume that [\![\rho]\!]\subseteq\mathcal{X} and [\![\alpha]\!]\subseteq{\mathbb{X}} with [\![\rho]\!]\setminus[\![\alpha]\!]\neq\varnothing . This way, L penalises \alpha and rewards \rho , maximally. Furthermore, \lambda({\mathbf{u}},{\mathbf{d}};{\mathbf{x}},k)=\mathbf{x}^{\intercal}P{\mathbf{x}}+\mathbf{u}^{\intercal}Q{\mathbf{u}}+\mathbf{d}^{\intercal}R{\mathbf{d}} is a weight term with correspondingly dimensioned matrices P , Q , and R . 9 9 9 As we do not restrict ourselves to LQR solutions, \lambda can be non-convex. Let \mathcal{G} be the class of integer difference games. A winning strategy for G_{\mathbf{s}} is a finite-horizon, discrete optimal controller {\mathbf{u}}^{*}\colon\Pi_{\mathcal{U}} , which can be obtained by solving a constrained, discrete dynamic optimisation problem [ 2 ] for given a horizon N : \displaystyle{\mathbf{u}}^{*}(\bar{\mathbf{x}};k) \displaystyle=\arg\min_{{\mathbf{u}}\in\Pi_{\mathcal{U}}}\max_{{\mathbf{d}}\in\Pi_{\mathcal{D}}}J(\bar{\mathbf{x}},{\mathbf{u}},{\mathbf{d}},k) (2) and \displaystyle V(\bar{\mathbf{x}};k) \displaystyle=\min_{{\mathbf{u}}\in\Pi_{\mathcal{U}}}\max_{{\mathbf{d}}\in\Pi_{\mathcal{D}}}J(\bar{\mathbf{x}},{\mathbf{u}},{\mathbf{d}},k) subject to \displaystyle\bar{\mathbf{x}}_{k+1} \displaystyle=\bar{\mathbf{x}}_{k}+\hat{\mathit{f}}({\mathbf{u}},{\mathbf{d}};\bar{\mathbf{x}}_{k},k) where \displaystyle J(\bar{\mathbf{x}},{\mathbf{u}},{\mathbf{d}},k) \displaystyle\textstyle=\sum_{i=k}^{N-1}L({\mathbf{u}},{\mathbf{d}};\bar{\mathbf{x}}_{i},i)+\Phi(\bar{\mathbf{x}}_{N},N)\;. J(\bar{\mathbf{x}},{\mathbf{u}},{\mathbf{d}},k) is the finite-horizon, discrete cost-to-go comprised of the running and terminal costs of a play from state \bar{\mathbf{x}}_{k} at time k , using the strategy profile ({\mathbf{u}},{\mathbf{d}}) . V(\bar{\mathbf{x}};k)\in[0,\top] with \top<\infty is the finite-horizon value corresponding to the optimal cost-to-go, using the optimal profile ({\mathbf{u}}^{*},{\mathbf{d}}^{*}) . Then, we define W(\mathcal{X},k)=\{{\mathbf{x}}\in\mathcal{X}\mid V({\mathbf{x}},k)<\top\} to be an approximation of G_{\mathbf{s}} ’s winning region at stage k when playing no more than N-k steps. In particular, W(\mathcal{X},N)=\{{\mathbf{x}}\in\mathcal{X}\mid\Phi({\mathbf{x}})<\top\} . 10 10 10 We use J^{N} , V^{N} , and W^{N} , if the horizon N is not clear from the context. To solve ( 2 ), we employ a forward-Euler DDP ( Algorithm 1 ) for the period I=1..N . Algorithm 1 Discrete dynamic programming The single-step successor {\mathbf{x}}^{ud}={\mathbf{x}}+\hat{\mathit{f}}({\mathbf{x}},u,d,k) is lifted in Line 6, such that {\mathbf{x}}^{ud}\in{\mathbf{x}}^{\mathcal{U}\mathcal{D}}\subseteq{\mathbb{X}} . Moreover, let {\mathbf{x}}^{{\mathbf{u}}{\mathbf{d}}}\in\bar{\mathbb{X}} be the N -step successor (trajectory) of G emanating from {\mathbf{x}}\in{\mathbb{X}} under influence of ({\mathbf{u}},{\mathbf{d}}) , and {\mathbf{x}}^{{\mathbf{u}}\mathcal{D}}\subseteq\bar{\mathbb{X}} be the family of such trajectories under \mathcal{D} . For \bar{\mathbf{x}}={\mathbf{x}}^{{\mathbf{u}}{\mathbf{d}}}\in\bar{\mathbb{X}} and \mathcal{C}\subseteq{\mathbb{X}}\times\mathcal{U}\times\mathcal{D}\times\mathbb{N}_{+} , trajectory granularity \Delta is bounded below by the smallest Lipschitz constant K_{*} of \hat{\mathit{f}} on \mathcal{C} via the supremal norm \lVert\cdot\rVert_{\mathcal{C}} by \displaystyle\sup_{k\in\mathbb{N}_{+}}\lVert\bar{\mathbf{x}}_{k+1}-\bar{\mathbf{x}}_{k}\rVert\leq K_{*}=\lVert\hat{\mathit{f}}\rVert_{\mathcal{C}}:=\sup_{c\in\mathcal{C}}\lVert\hat{\mathit{f}}(c)\rVert\leq\delta\;. (3) \Delta\supseteq[\pm\delta]^{m} may deliver bounds on measurement uncertainties, for example, from feedback delay, that is, delayed observation of environmental effects on {\mathbf{x}} . In Line 9, we allow a check of \widehat{\mathit{fp}}_{\mathrm{dDP}} for whether some approximation of a fixpoint is achieved prior to reaching N . While meeting the actual fixpoint would allow us to obtain a stationary optimal strategy profile, the fixpoint approximation still guarantees bounded correct (quasi-stationary and near-optimal) strategies under reduced memory consumption and computational effort. In [ 4 ] , we approximate that fixpoint with \displaystyle\widehat{\mathit{fp}}_{\mathrm{dDP}}(k)\equiv|W(\mathcal{X}_{\mathbf{s}},k)|=|W(\mathcal{X}_{\mathbf{s}},k+1)|\lor\widehat{\mathit{fp}}_{\mathbf{U}}(k)\,, (4) where the termination shortcut \widehat{\mathit{fp}}_{\mathbf{U}}(k)\equiv\exists k^{\prime}\geq k\colon\top\not\in V({\mathbf{x}}\oplus\Delta_{\delta},k^{\prime}) specifies that, latest at stage k , {\mathbf{x}} is \delta -robustly located inside W(\mathcal{X}_{\mathbf{s}},k) . Hybrid Game Playing. G[\mathbf{U},T] is parameterised by a hyper-policy \mathbf{U} and a task T . Our model in [ 4 ] assumes that {\mathbf{x}}=({\mathbf{p}},{\mathbf{v}},i) contains a position, a velocity, and a waypoint index. \mathbf{U}_{\delta}\colon\mathcal{G}\times 2^{\mathbb{N}_{+}}\to\Pi_{\mathcal{U}} increases flexibility, in particular, it wraps Algorithm 1 into a loop for spatio-temporal extension of (\mathcal{X},I) . \delta is the robustness margin according to ( 3 ). The role of T=({\mathbb{X}},{\bar{r}},\mathcal{O}_{\mathsf{}}) , with route {\bar{r}}\subset{\mathbb{X}}|_{\mathbf{p}} and fixed obstacle cloud \mathcal{O}_{\mathsf{}}\subset{\mathbb{X}}|_{\mathbf{p}} , is to refine F . Importantly, T needs to satisfy a healthiness condition called \delta -perforation : \displaystyle\exists\bar{x}\in\tilde{\mathbb{X}}\colon{\bar{r}}\subseteq\underbrace{\bar{x}|_{{\mathbf{p}}}\oplus\Delta_{\delta}}_{\text{cont.\ $\delta$-tube}}\land\bar{x}|_{{\mathbf{p}}}\oplus\Delta_{\delta}\cap\mathcal{O}_{\mathsf{}}=\varnothing\,. (5) Given ( 5 ), ( 1 ) implies V(\mathbf{0},\cdot)=0 . We use Algorithm 2 as a simulator that terminates when an overall goal \Omega is reached or failures occur (Line 10). Algorithm 2 Hybrid game player (with restricted task updates) Definition 1 (Online Synthesis Problem) Given a hybrid game automaton G and a task T , continuously find tactical controllers {\mathbf{u}} steering the system along route {\bar{r}} while safely circumventing unsafe regions. For correctness, we need {\mathbf{u}} to be (i) \delta -robust (i.e., safe under bounded disturbance \mathcal{D} ), (ii) near-optimal (i.e., follow the minimum-cost path inside padded segment scopes, approximating all waypoints), and (iii) reaching the endpoint of {\bar{r}} . □ 3 Side-Conditions for Game Solvability From our setting in [ 4 ] , it may seem obvious that V({\mathbf{x}},1)<\top is a sufficient condition for a bounded safe and live controller {\mathbf{u}}^{*} to exist. However, it turns out to non-obvious how to establish this condition in general and, in particular, for our setting. Hence, we first identify several side-conditions for game solvability, investigate their necessity and sufficiency, and then extract a theorem and proof from these findings. Local Controllability. To ensure the existence of control inputs to reject disturbance, a dynamics \hat{\mathit{f}} with a balanced equivalent-order player superposition requires the player alphabets \mathcal{U} and \mathcal{D} to satisfy \displaystyle\forall{\mathbf{d}}\in\mathcal{D}\,\exists{\mathbf{u}}\in\mathcal{U}\colon\langle{\mathbf{d}}+\frac{\langle{\mathbf{d}},{\mathbf{u}}\rangle}{\lVert{\mathbf{d}}\rVert},{\mathbf{d}}\rangle\leq 0\,. (6) Adding {\mathbf{d}} to the {\mathbf{d}} -component \frac{\langle{\mathbf{d}},{\mathbf{u}}\rangle}{\lVert{\mathbf{d}}\rVert} of {\mathbf{u}} in the scalar product with {\mathbf{d}} stresses the relevance of {\mathbf{u}} ’s magnitude. Refining ( 6 ) from compensation ( \leq ) to overriding ( < ), {\mathbf{v}} and, hence, {\mathbf{p}} become locally controllable. 11 11 11 Comparing \mathcal{U},\mathcal{D} by diameter only works if \mathcal{U},\mathcal{D} are centered, spherical, and dense enough. Algorithm 1 may deviate from ( 6 ). However, if, from {\mathbf{x}} , a worst-case {\mathbf{d}} would lead to [\![\alpha]\!] then, by ( 6 ), Algorithm 1 can prevent that from happening by prematurely rejecting {\mathbf{d}} , no matter whether or not the environment actually chooses such a {\mathbf{d}} when in {\mathbf{x}} . Local controllability is neither necessary (simple tasks are still solvable, e.g., with a short enough path to [\![\rho]\!] ) nor sufficient (no guaranteed progress, e.g., if the obstacle cloud is not enough perforated) for game solvability. Lower Bound for Robustness against Disturbance. It is important to know how robust the system is against disturbance under delayed observation and (minimal) non-zero progress. Equivalently, for evaluating \delta -perforation ( 5 ), we have to know how much space the controller needs at least to react under delayed feedback. More generally, because of possible latencies in sensing, computation, and actuation, disturbance rejection while maintaining correctness (e.g., safety, no stalling) might be delayed by one or more time steps. While ( 3 ) enforces cooperation towards a maximum change of {\mathbf{x}} , players in G_{\mathbf{s}} act adversarially. The \delta in ( 5 ) can thus be smaller than in ( 3 ): \displaystyle 0 \displaystyle<\max_{d\in\mathcal{D}}\inf_{\begin{subarray}{c}{\mathbf{v}}+\dot{\mathbf{v}}\neq\mathbf{0}\\ {\mathbf{x}}\in{\mathbb{X}},\,k\in\mathbb{N}_{+}\end{subarray}}\lVert\hat{\mathit{f}}({\mathbf{x}},\mathbf{0},d,k)|_{\mathbf{p}}\rVert<\delta\;, (7) \displaystyle 0 \displaystyle<\max_{d\in\mathcal{D}}\sup_{\begin{subarray}{c}{\mathbf{x}}\models\rho\\ {\mathbf{x}}\in{\mathbb{X}},\,k\in\mathbb{N}_{+}\end{subarray}}\lVert\hat{\mathit{f}}({\mathbf{x}},\mathbf{0},d,k)|_{\mathbf{p}}\rVert<\delta_{\rho}\;. (8) Being in the center of a narrow cavity outside [\![\alpha]\!] (e.g., in a tube), the controller does not know about the environment’s current and next choices but may want to provide choices to make progress. Because of value minimisation in Algorithm 1 , the worst case of u and d being coincident improves to the controller idling ( u=\mathbf{0} , e.g., because of a temporary fault) and the environment gaining instants of exclusive control. In asymmetric cases (e.g., close to a wall), Algorithm 1 will choose to deviate from u=\mathbf{0} in either direction and perhaps reduce \delta locally even further. The infimum in ( 7 ) strives for a minimum non-zero speed v_{\min} under disturbance rejection delayed by one stage. To make progress safely for at least one stage, \delta then has to be greater than v_{\min} . However, ( 7 ) is neither necessary (e.g., the system may slip through narrower cavities) nor sufficient (e.g., it does not address global progress or safety) for game solvability. The lower bound in ( 8 ) indicates a safe region under a potential lack of control beyond N and before or after a jump (e.g., at highest speed). \delta -Robust Tracking. \mathcal{U} and \mathcal{D} according to ( 6 ) and \delta according to ( 7 ) together imply that, among the {\mathbb{X}} -continuous trajectories satisfying ( 5 ), at least one \bar{x}\in\tilde{\mathbb{X}} is robustly trackable , that is, \displaystyle\max_{d\in\mathcal{D}}\inf_{\begin{subarray}{c}{\mathbf{x}}\in\bar{x}\\ k\in 1..|\bar{x}|\end{subarray}}\lVert\hat{\mathit{f}}({\mathbf{x}},\mathbf{0},d,k)|_{\mathbf{p}}\rVert<\delta\;. (9) We observe that the nearest point on \bar{x} is within a \delta -ball around \bar{x}_{k}^{ud} . Equivalently, a (controlled) move from \bar{x}_{k} does not deviate from \bar{x} by more than \delta . In passages of width above \delta , there will be several trajectories \bar{x}\in\tilde{\mathbb{X}} for Algorithm 1 to construct a controller {\mathbf{u}}^{*} that can track a matching (discontinuous) \Delta -trajectory \bar{x}^{\prime}\subseteq\bar{x} (i.e., distance below \delta by definition of {\mathbb{X}} -continuity). In passages of width \delta , Algorithm 1 will construct a controller {\mathbf{u}}^{*} that satisfies ( 7 ) and, thus, ( 9 ) and, by ( 6 ), will be able to again approach the near-optimal trajectory \bar{x} from ( 5 ) latest in the subsequent stage. If the smallest perforation width \delta_{\mathcal{O}_{\mathsf{}}} found in \mathcal{O}_{\mathsf{}} is a multiple of \delta according to ( 7 ), we obtain an upper delay bound n defined as \displaystyle n=\max\{n^{\prime}\in\mathbb{N}\mid n^{\prime}\delta\leq\delta_{\mathcal{O}_{\mathsf{}}}\}\;. (10) Disturbance rejection and robust tracking then extend to n observational delays and actuator perturbations. We call a system delay-bounded , if it operates with a maximum of n delays and perturbations. Delay-boundedness, emerging from local controllability ( 6 ) and robust trackability ( 9 ), forms a necessary condition for the existence of a corresponding controller. Heuristics for an Initial Horizon. A lower bound for N —under-approximating K_{*} and rarely applicable—would be \inf_{{\mathbf{p}}^{\prime}\in[\![\rho]\!]|_{\mathbf{p}}}\lVert{\mathbf{p}}-{\mathbf{p}}^{\prime}\rVert/v_{\max}\leq N . If \lVert{\mathbf{v}}\rVert\geq v_{\min}>0 is enabled by \delta satisfying ( 7 ), an upper, albeit impractical, bound would be N\leq|{\mathbb{X}}|_{\mathbf{p}}|/v_{\min} . Being at {\mathbf{p}} , initialising \mathbf{U} with \displaystyle N\approx\inf_{{\mathbf{p}}^{\prime}\in[\![\rho]\!]|_{\mathbf{p}}}\left\lfloor\frac{2\sigma\lVert{\mathbf{p}}-{\mathbf{p}}^{\prime}\rVert}{v_{\min}+v_{\max}}\right\rfloor (11) can be a reasonable heuristic, with sparsity \sigma=1 for a sparse or highly perforated \mathcal{O}_{\mathsf{}} and \sigma\gg 1 for a densely populated \mathcal{O}_{\mathsf{}} . While the lower bound is a necessary condition (i.e., the goal region must be closer than what the system can reach in N stages at highest speed), none of the bounds are sufficient (e.g., a non-perforated \mathcal{O}_{\mathsf{}} with \sigma=\infty will obstruct reaching the goal). Upper Bound of Stage Cost. L can be both zero outside [\![\rho]\!]\setminus[\![\alpha]\!] and non-zero inside that area. However, L must be bounded by N\sup_{c\in\mathcal{C}}L(c)<\top , which is a necessary condition for the following discussion. 4 Solvability and Controlled Invariant Set For the discussion below, we fix G_{\mathbf{s}} for some {\mathbf{s}}\in{\mathcal{S}} and leave {\mathbf{s}} implicit. Let {\mathbf{x}}\in{\mathbb{X}} , (u,d)\in\mathcal{U}\times\mathcal{D} , k\in 2..N . For the inclined reader, it is easy to see that Line 8 of Algorithm 1 implement a discrete HJI equation [ 7 ] \displaystyle V({\mathbf{x}},k-1)-V({\mathbf{x}},k)=\min_{u\in\mathcal{U}}\max_{d\in\mathcal{D}}\mathcal{H}({\mathbf{x}},u,d,k) (12) with a corresponding Hamiltonian (i.e., directional difference of V along \hat{\mathit{f}} ) \displaystyle\mathcal{H}({\mathbf{x}},u,d,k) \displaystyle=L({\mathbf{x}},u,d,k)+V({\mathbf{x}}^{ud},k)-V({\mathbf{x}},k)\;. HJI equations connect value evolution with the minimax combination of stage cost and value descent. Below, we first establish a fundamental lemma and proceed with an inductive invariant. Lemma 1 (Monotonicity) V({\mathbf{x}},k-1)<\top\implies V({\mathbf{x}},k-1)\leq V({\mathbf{x}},k) □ Proof ( Lemma 1 ) By Bellman’s principle of optimality, V({\mathbf{x}},k-1) is the value of the optimal suffix of length N-(k-1) . Exhaustive search (Lines 4 to 6 in Algorithm 1 ) rules out shorter suffixes of length N-k , yet unseen but better with respect to J , such that V({\mathbf{x}},k-1)>V({\mathbf{x}},k) . ■ Lemma 2 (Reach-Avoid k -Winning Region) If V (obtained via \mathbf{U} ) satisfies ( 12 ) then W(\mathcal{X},k) contains exactly the states from where the system can reach [\![\rho]\!]\setminus[\![\alpha]\!] in at most N-k stages while remaining outside [\![\alpha]\!] . □ Proof (Sketch for Lemma 2 ) The proof is by reverse induction on k in ( 12 ) and provided in full detail in Appendix A . This proof provides that Lemma 2 specifies an inductive invariant. ■ Under well-formedness assumptions detailed below, Lemma 2 is a sufficient condition for k -bounded safe and live controllers to exist. Configurations and Pre-/Post-Conditions. Defined in Section 2 , the hybrid game automaton G , the hyper-policy \mathbf{U}_{\delta} with a robustness margin \delta , and the task specification T=({\mathbb{X}},{\bar{r}},\mathcal{O}_{\mathsf{}}) together form a configuration \mathsf{C}=(G,\mathbf{U}_{\delta},T) . We call \mathsf{C} well-formed , written \mathit{wf}(\mathsf{C}) , if (i) \mathcal{O}_{\mathsf{}} is \delta -perforated ( 5 ) with \delta according to ( 7 ), (ii) locally controllable ( 6 ), and (iii) delay-bounded ( 10 ). For G_{\mathbf{s}} and a specific initial horizon N according to ( 11 ), we obtain the modal configuration \mathsf{C}_{\mathbf{s}}=(G_{\mathbf{s}},\mathbf{U}_{\delta,N},T) with discrete dynamics \hat{\mathit{f}} . We have \mathit{wf}(\mathsf{C}_{\mathbf{s}}) if \mathit{wf}(\mathsf{C}) and G_{\mathbf{s}} is initialised with {{\mathbf{x}}_{0}}\not\in[\![\alpha]\!] . We call {\mathbf{u}}^{*}_{\mathbf{s}} correct , written \mathit{cr}({\mathbf{u}}^{*}_{\mathbf{s}}) , if it is (i) live (i.e., it reaches the next waypoint or finishes its task), (ii) safe (i.e., it avoids the unsafe region, e.g., it avoids collisions), (iii) \delta -robust (it rejects disturbances below \delta with a single-step delay without getting into an unsafe state), and (iv) near-optimal (it provides the steepest value-decreasing control input), when applied to {\mathbf{x}}\in W(\mathcal{X}_{\mathbf{s}},1) for a maximum of N stages. The key aspects of the proposed online synthesis are summarised in the following solvability theorem. Theorem 1 (Modal Game Solvability) Given a modal configuration \mathsf{C}_{\mathbf{s}} , if \mathsf{C}_{\mathbf{s}} is well-formed then \mathbf{U} constructs a correct controller {\mathbf{u}}^{*}_{\mathbf{s}} , \displaystyle\forall{\mathbf{s}}\in{\mathcal{S}}\colon\{\mathit{wf}(\mathsf{C}_{\mathbf{s}})\}\;{\mathbf{u}}^{*}_{\mathbf{s}}:=\mathbf{U}_{\delta,N}(G_{\mathbf{s}})\;\{\mathit{cr}({\mathbf{u}}^{*}_{\mathbf{s}})\}\;. □ Proof (Sketch for Theorem 1 ) The post-conditions (i) to (iv) are established separately based on ( 5 ), the side conditions in Section 3 , features of Algorithm 1 , and Lemma 2 . The complete proof is provided in Appendix A . ■ Lemma 3 (Preservation) \mathbf{U}_{\delta,N} preserves game solvability. □ Proof ( Lemma 3 ) Observe that {\mathbf{x}} and \rho are fixed during scope extension. By Lemma 1 , if there exists a correct solution within N stages, a corresponding solution exists within N+1 stages. That solution will just not allow the controller to wait for too long in order to remain on the safe side. Under local controllability ( 6 ), extending the prediction interval I (initially 1..N ) to I^{\prime}=\underline{I}..\bar{I}+{\delta_{I}} and \mathcal{X}_{\mathbf{s}} to some \mathcal{X}^{\prime}\supset\mathcal{X}_{\mathbf{s}} preserves (i) liveness by relaxing W^{\bar{I}^{\prime}}(\mathcal{X}^{\prime},1) (from {\mathbf{x}} , the controller has more space and time to steer the system into [\![\rho]\!]\setminus[\![\alpha]\!] ), (ii) safety by constraining W^{\bar{I}^{\prime}}(\mathcal{X}^{\prime},1) only as far as necessary (allowing at most n delays ( 10 ) with \delta^{\prime}=n\delta , the environment has only n stages to accumulate unsafe disturbances) and, thus, solvability. ■ Corollary 1 (Controlled Invariant Set) With W(\mathcal{X}_{\mathbf{s}},1)\subseteq{\mathbb{X}}\setminus([\![\alpha]\!]\oplus\Delta_{\delta}) , \mathbf{U}_{\delta,N} provides a maximum N -bounded, robust (i.e., under-approximated), non-linear controlled invariant set, independent of ( 6 ). □ Theorem 1 establishes sub-problems (i) and (ii) of Definition 1 . To finally address sub-problem (iii), we define \mathit{cr}(\bar{\mathbf{s}})\equiv\bar{\mathbf{s}}_{n}|_{\mathbf{p}}={\mathbf{p}}_{n} and provide a solvability theorem applicable for the considered range of modal games. Theorem 2 (Global Game Solvability) Given a configuration \mathsf{C} , if \mathsf{C} is well-formed then Algorithm 2 produces a correct play \bar{\mathbf{s}} with \bar{\mathbf{s}}_{0}={\mathbf{s}}_{0} , \displaystyle\{\mathit{wf}(\mathsf{C})\}\;\bar{\mathbf{s}}:=\textsc{hybridPlay}[\mathsf{C}](\bar{\mathbf{s}})\;\{\mathit{cr}(\bar{\mathbf{s}})\}\;. □ Proof (Sketch Theorem 2 ) The proof demonstrates the existence and correctness of a fixpoint \bar{\mathbf{s}} and is provided in full detail in Appendix A . ■ 5 Discussion From Non-Stationary to Quasi-Stationary Controllers. If we reach the actual value fixpoint V^{\infty} in stage k^{\infty}\in 1..N , we obtain a stationary, infinite-horizon {\mathbf{u}}^{\infty} , which provides the \mathcal{X} -optimal input independent of time, forming a winning strategy as long as it has at least N-k^{\infty} stages to solve the problem. Otherwise, we obtain a non-stationary, (\mathcal{X},k) -optimal, terminal-time controller. This is one, which, at each stage k , provides an (\mathcal{X},k) -optimal input, forming a winning strategy, given exactly N-k stages to solve the problem. However, applying a fixpoint approximation in Algorithm 1 , such as ( 4 ), and reaching the quasi-fixpoint V^{*} in stage k^{*} , we obtain a quasi-stationary {\mathbf{u}}^{*} . This is one, which provides a near- \mathcal{X} -optimal input, forming a winning strategy as long as it requires at most N-k^{*} stages to solve the problem. By Lemma 1 , we can use {\mathbf{u}}({\mathbf{x}},k) across all the stages in k..N 12 12 12 That is, it can be used for a maximum of N-k stages. while preserving correctness and benefitting from lowering the space complexity \operatorname{\mathcal{O}}(N\mathcal{X}) of the computation and storage of {\mathbf{u}} to \operatorname{\mathcal{O}}(\mathcal{X}) . Regarding optimality, for k