Optimal controller synthesis for timed systems
From MaRDI portal
Publication:6135744
DOI10.46298/LMCS-19(1:20)2023arXiv2104.12577MaRDI QIDQ6135744FDOQ6135744
Pierre-Alain Reynier, Benjamin Monmege, Damien Busatto-Gaston
Publication date: 26 August 2023
Published in: Logical Methods in Computer Science (Search for Journal in Brave)
Abstract: Weighted timed games are zero-sum games played by two players on a timed automaton equipped with weights, where one player wants to minimise the cumulative weight while reaching a target. Used in a reactive synthesis perspective, this quantitative extension of timed games allows one to measure the quality of controllers in real-time systems. Weighted timed games are notoriously difficult and quickly undecidable, even when restricted to non-negative weights. For non-negative weights, the largest class that can be analysed has been introduced by Bouyer, Jaziri and Markey in 2015. Though the value problem is undecidable, the authors show how to approximate the value by considering regions with a refined granularity. In this work, we extend this class to incorporate negative weights, allowing one to model energy for instance, and prove that the value can still be approximated, with the same complexity. A small restriction also allows us to obtain a class of decidable weighted timed games with negative weights and an arbitrary number of clocks. In addition, we show that a symbolic algorithm, relying on the paradigm of value iteration, can be used as an approximation/computation schema over these classes. We also consider the special case of untimed weighted games, where the same fragments are solvable in polynomial time: this contrasts with the pseudo-polynomial complexity, known so far, for weighted games without restrictions.
Full work available at URL: https://arxiv.org/abs/2104.12577
Recommendations
- scientific article; zbMATH DE number 1247464
- Synthesis of time optimal control for a class of linear systems
- scientific article; zbMATH DE number 1751940
- scientific article
- Sequential synthesis of time-optimal control
- On the synthesis of discrete controllers for timed systems
- Sequential synthesis of the time-optimal control in real time
- Control and synthesis of non-interferent timed systems
- Time-scale synthesis of a closed-loop discrete optimal control system
- Synthesis of suboptimal control in the time-optimal problem
Cites Work
- Uppaal in a nutshell
- A theory of timed automata
- Relationships between nondeterministic and deterministic tape complexities
- Title not available (Why is that?)
- Title not available (Why is that?)
- Nondeterministic Space is Closed under Complementation
- Optimal Reachability in Divergent Weighted Timed Games
- Title not available (Why is that?)
- Reachability-Time Games on Timed Automata
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- Automata, Languages and Programming
- Formal Modeling and Analysis of Timed Systems
- Improved undecidability results on weighted timed automata
- The method of forced enumeration for nondeterministic automata
- On short paths interdiction problems: Total and node-wise limited interdiction
- Efficient On-the-Fly Emptiness Check for Timed Büchi Automata
- Optimal paths in weighted timed automata
- On the optimal reachability problem of weighted timed automata
- Title not available (Why is that?)
- Number of quantifiers is better than number of tape cells
- Solving Sequential Conditions by Finite-State Strategies
- Dynamical properties of timed automata
- Optimal infinite scheduling for multi-priced timed automata
- Adding Negative Prices to Priced Timed Games
- Title not available (Why is that?)
- Pseudopolynomial iterative algorithm to solve total-payoff games and min-cost reachability games
- Title not available (Why is that?)
- A Faster Algorithm for Solving One-Clock Priced Timed Games
- Energy and mean-payoff timed games
- On the Value Problem in Weighted Timed Games.
- Title not available (Why is that?)
- Symbolic Approximation of Weighted Timed Games
Cited In (9)
- Time-optimal control for discrete-time hybrid automata
- Robust Controller Synthesis in Timed Automata
- Control and synthesis of non-interferent timed systems
- Time-scale synthesis of a closed-loop discrete optimal control system
- Title not available (Why is that?)
- Title not available (Why is that?)
- The Complexity of Bounded Synthesis for Timed Control with Partial Observability
- Title not available (Why is that?)
- Controller synthesis for dynamic hierarchical real-time plants using timed automata
This page was built for publication: Optimal controller synthesis for timed systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6135744)
