Controller Synthesis for Parametric Timed Games
Mikael Bisgaard Dahlsen-Jensen, Baptiste Fievet, Laure Petrucci ✉, Jaco van de Pol · 2025
Read Controller Synthesis for Parametric Timed Games by Mikael Bisgaard Dahlsen-Jensen, Baptiste Fievet, Laure Petrucci ✉, Jaco van de Pol (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-2506-15532.txt.
Introduction
Mikael Bisgaard Dahlsen-Jensen, Baptiste Fievet, Laure Petrucci, and Jaco van de Pol present a method for winning timed games in this 2025 paper. Timed games model contests where moves depend on clocks, such as controllers that must react within deadlines. In the parametric form, some clock limits are left open as variables.
Earlier methods only found which settings of those variables allow a win. The new approach also builds the winning strategy itself, under a fresh definition of what such a strategy is. The strategy can then be turned into a timed controller that enforces it. A working implementation and tests on a production cell case show the method is practical.
Catalog record
| CREATOR | Mikael Bisgaard Dahlsen-Jensen, Baptiste Fievet, Laure Petrucci ✉, Jaco van de Pol |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 90 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-15532
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Controller Synthesis for Parametric Timed Games Thanks: This work was partially supported by CNRS international PhD programme, the CNRS International Research Network CLoVe and Innovationsfonden Danmark’s DIREC project SIoT (Secure Internet of Things). Thanks: This is the full version of the paper under the same title accepted to QEST+FORMATS 2025. Mikael Bisgaard Dahlsen-Jensen, Baptiste Fievet, Laure Petrucci ✉, Jaco van de Pol Abstract We present a (semi)-algorithm to compute winning strategies for parametric timed games. Previous algorithms only synthesized constraints on the clock parameters for which the game is winning. A new definition of (winning) strategies is proposed, and ways to compute them. A transformation of these strategies to (parametric) timed automata allows for building a controller enforcing them. The feasibility of the method is demonstrated by an implementation and experiments for the Production Cell case study. 1 Introduction Timed Games (TG) [ 16 ] extend Timed Automata (TA) [ 1 ] by distinguishing controllable and uncontrollable transitions and introducing a reachability goal. The game is won by the controller, if he can play controllable actions, such that no matter which uncontrollable actions are taken by the environment, the goal is reached. An on-the-fly algorithm was introduced in [ 7 ] , to decide whether a timed game is won by the controller. This algorithm forms the basis of Uppaal Tiga [ 5 ] . Parametric Timed Automata (PTA) [ 2 ] enable the study of an infinite family of TA by replacing concrete constraints by parameters. Given a desired property, the problem is to find all parameter valuations that satisfies it. Unlike TA, most problems are undecidable for PTA [ 3 ] , although several fragments are known to be decidable, e.g., L/U PTA [ 12 ] and PTA with only one clock [ 6 ] . Parametric Timed Games (PTG) combine the ideas of PTA and TG and were introduced along with a semi-algorithm for parameter synthesis for reachability objectives [ 13 , 14 ] , extended and implemented in [ 10 ] . The semi-algorithm in that work enumerates all constraints on clock parameters, for which the game is won. We extend the previous work in several directions. Our main goal is to generate a concrete strategy , that tells the controller how to win the game. Thus, we automatically synthesize a controller that is correct by construction. This strategy is represented itself by a parametric timed automaton, which can be put in parallel to the original system. In the synchronous product of the controller and the system, every run will eventually reach the goal location. Uppaal Tiga [ 5 ] allows generating winning strategies for TG and [ 11 ] proposes a translation from these to controller timed automata. However, these strategies have the “implicit semantics” that their instructions must be taken as soon as possible , causing ill-defined behavior in some cases. We improve the situation by a new type of strategies, whose instructions explicitly define the interval in which a transition must be taken, and extend this to PTG. This new notion of strategy allows for expressing the controller as a Parametric Timed Automaton. We also reconciled the algorithm from [ 7 ] with the actual implementation in [ 5 ] . In [ 7 ] (and also in its extension [ 10 ] ), a strategy can only rely on controllable actions, while Uppaal Tiga takes the more realistic approach, in which the strategy can also consider uncontrollable actions, as long as they cannot be postponed forever. In this paper, we develop the theory of these forced uncontrollable transitions , and adapt the algorithms accordingly. 1.1 Motivating Example Let us first recall how [ 7 ] , its parametric extension [ 13 , 14 ] as well as the tool Uppaal Tiga itself defines strategies: they are memoryless, i.e. provide the next action based solely on the current state. This action can be either a discrete transition or a Wait instruction. In case of a Wait , the controller must wait until a state is reached where the strategy provides a discrete transition, which should then be taken as soon as possible . However, the “first” future state where the strategy outputs a discrete transition may not exist. Example 1 Consider the example in fig. 1(a) . It is a Timed Game with a clock {\color[rgb]{0.4,0.4,1}\mathrm{x}} and a reachability objective with {\color[rgb]{0.4,0.4,0.65}\mathrm{Win}} as the only target location. Controllable (resp. uncontrollable) transitions are drawn by solid (resp. dashed) arrows, have action labels, optional guards and clock resets. {\color[rgb]{0.4,0.4,0.65}\mathrm{L_{0}}} {\color[rgb]{0.4,0.4,0.65}\mathrm{L_{1}}} {\color[rgb]{0.4,0.4,0.65}\mathrm{L_{2}}} {\color[rgb]{0.4,0.4,0.65}\mathrm{Win}} \begin{subarray}{c}{\color[rgb]{0.5,0.7,0.3}\mathrm{u_{1}}}\end{subarray} \begin{subarray}{c}{\color[rgb]{0.4,0.4,1}\mathrm{x}}=2\\ {\color[rgb]{0.5,0.7,0.3}\mathrm{u_{2}}}\\ {\color[rgb]{0.4,0.4,1}\mathrm{x}}:=0\end{subarray} \begin{subarray}{c}{\color[rgb]{0.4,0.4,1}\mathrm{x}}\geq 2\\ {\color[rgb]{0.5,0.7,0.3}\mathrm{c_{1}}}\end{subarray} \begin{subarray}{c}1<{\color[rgb]{0.4,0.4,1}\mathrm{x}}\leq 2\\ {\color[rgb]{0.5,0.7,0.3}\mathrm{c_{2}}}\end{subarray} \begin{subarray}{c}{\color[rgb]{0.5,0.7,0.3}\mathrm{c_{3}}}\end{subarray} (a) Example of a Timed Game. Uppaal Tiga: 1. In {\color[rgb]{0.4,0.4,0.65}\mathrm{L_{2}}} when True , do {\color[rgb]{0.5,0.7,0.3}\mathrm{c_{3}}} . 2. In {\color[rgb]{0.4,0.4,0.65}\mathrm{L_{1}}} when 1<{\color[rgb]{0.4,0.4,1}\mathrm{x}}\leq 2 , do {\color[rgb]{0.5,0.7,0.3}\mathrm{c_{2}}} 3. In {\color[rgb]{0.4,0.4,0.65}\mathrm{L_{1}}} when {\color[rgb]{0.4,0.4,1}\mathrm{x}}\leq 1 , {\color[rgb]{0.5,0.7,0.3}\mathrm{Wait}} . 4. In {\color[rgb]{0.4,0.4,0.65}\mathrm{L_{0}}} when {\color[rgb]{0.4,0.4,1}\mathrm{x}}=2 , do {\color[rgb]{0.5,0.7,0.3}\mathrm{c_{1}}} . 5. In {\color[rgb]{0.4,0.4,0.65}\mathrm{L_{0}}} when {\color[rgb]{0.4,0.4,1}\mathrm{x}}<2 , {\color[rgb]{0.5,0.7,0.3}\mathrm{Wait}} . Our modification: 2a. In {\color[rgb]{0.4,0.4,0.65}\mathrm{L_{1}}} when {\color[rgb]{0.4,0.4,1}\mathrm{x}}<2 wait until 1<{\color[rgb]{0.4,0.4,1}\mathrm{x}}<2 and do {\color[rgb]{0.5,0.7,0.3}\mathrm{c_{2}}} . 2b. In {\color[rgb]{0.4,0.4,0.65}\mathrm{L_{1}}} when {\color[rgb]{0.4,0.4,1}\mathrm{x}}=2 wait until {\color[rgb]{0.4,0.4,1}\mathrm{x}}=2 and do {\color[rgb]{0.5,0.7,0.3}\mathrm{c_{2}}} . (b) Specification of winning strategy. Figure 1 : Timed Game, strategy from Uppaal Tiga, and a modified fix. The environment can force a transition from {\color[rgb]{0.4,0.4,0.65}\mathrm{L_{0}}} to {\color[rgb]{0.4,0.4,0.65}\mathrm{L_{1}}} for any value 0\leq{\color[rgb]{0.4,0.4,1}\mathrm{x}}\leq 2 . When in {\color[rgb]{0.4,0.4,0.65}\mathrm{L_{1}}} there are three cases: If 1<{\color[rgb]{0.4,0.4,1}\mathrm{x}}<2 , we can immediately reach {\color[rgb]{0.4,0.4,0.65}\mathrm{Win}} by taking {\color[rgb]{0.5,0.7,0.3}\mathrm{c_{2}}} and {\color[rgb]{0.5,0.7,0.3}\mathrm{c_{3}}} . If {\color[rgb]{0.4,0.4,0.65}\mathrm{x}}\leq 1 , we can safely wait to reach the interval 1<{\color[rgb]{0.4,0.4,1}\mathrm{x}}<2 , and apply the previous case. If {\color[rgb]{0.4,0.4,1}\mathrm{x}}=2 , we should still take {\color[rgb]{0.5,0.7,0.3}\mathrm{c_{2}}} immediately, else we would be stuck in {\color[rgb]{0.4,0.4,0.65}\mathrm{L_{1}}} forever. However, we might not be able to take {\color[rgb]{0.5,0.7,0.3}\mathrm{c_{3}}} from {\color[rgb]{0.4,0.4,0.65}\mathrm{L_{2}}} before the environment sends us back to {\color[rgb]{0.4,0.4,0.65}\mathrm{L_{1}}} with {\color[rgb]{0.4,0.4,1}\mathrm{x}}=0 , where the previous case applies. Since we have a winning strategy from {\color[rgb]{0.4,0.4,0.65}\mathrm{L_{0}}} when the environment moves with {\color[rgb]{0.4,0.4,1}\mathrm{x}}\leq 2 , we can just wait if it happens, or else win with action {\color[rgb]{0.5,0.7,0.3}\mathrm{c_{1}}} when {\color[rgb]{0.4,0.4,1}\mathrm{x}} reaches value 2. The strategy synthesized by Uppaal is illustrated in fig. 1(b) . Notice that {\color[rgb]{0.5,0.7,0.3}\mathrm{c_{2}}} winning in {\color[rgb]{0.4,0.4,0.65}\mathrm{L_{1}}} when {\color[rgb]{0.4,0.4,1}\mathrm{x}}=2 is merged with applying {\color[rgb]{0.5,0.7,0.3}\mathrm{c_{2}}} in {\color[rgb]{0.4,0.4,0.65}\mathrm{L_{1}}} when 1<{\color[rgb]{0.4,0.4,1}\mathrm{x}}<2 . Let us focus on how to win from state ({\color[rgb]{0.4,0.4,0.65}\mathrm{L_{1}}},x=0) . From (3), we wait until {\color[rgb]{0.4,0.4,1}\mathrm{x}}>1 where (2) can be applied, taking action {\color[rgb]{0.5,0.7,0.3}\mathrm{c_{2}}} as soon as possible. But such a moment does not exist: when {\color[rgb]{0.4,0.4,1}\mathrm{x}}=1 , it is too early to take {\color[rgb]{0.5,0.7,0.3}\mathrm{c_{2}}} ; when {\color[rgb]{0.4,0.4,1}\mathrm{x}}=t>1 , it is too late as we could have taken {\color[rgb]{0.5,0.7,0.3}\mathrm{c_{2}}} earlier at a time t^{\prime} such that 1<t^{\prime}<t . Therefore, no run going through ({\color[rgb]{0.4,0.4,0.65}\mathrm{L_{1}}},{\color[rgb]{0.4,0.4,1}\mathrm{x}}=0) complies with the strategy provided by Uppaal . Yet, we need to be able to react if the environment moves from {\color[rgb]{0.4,0.4,1}\mathrm{L_{0}}} to {\color[rgb]{0.4,0.4,1}\mathrm{L_{1}}} when {\color[rgb]{0.4,0.4,1}\mathrm{x}}=0 . The way we handle this in our strategy is by adding additional information on how long to wait before acting. In fig. 1(b) (bottom), we show how we modify (2). This new specification requires the player to commit to an action in advance and wait until the specified time interval before executing it. In {\color[rgb]{0.4,0.4,0.65}\mathrm{L_{1}}} when applying (2a), the action {\color[rgb]{0.5,0.7,0.3}\mathrm{c_{2}}} can be taken at any point in time within 1<{\color[rgb]{0.4,0.4,1}\mathrm{x}}<2