Optimal controller synthesis for timed systems
From MaRDI portal
(Redirected from Publication:6135744)
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.
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; zbMATH DE number 4212851
- 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
- scientific article; zbMATH DE number 1303059 (Why is no real title available?)
- scientific article; zbMATH DE number 1337733 (Why is no real title available?)
- scientific article; zbMATH DE number 1749054 (Why is no real title available?)
- scientific article; zbMATH DE number 1796156 (Why is no real title available?)
- scientific article; zbMATH DE number 1794367 (Why is no real title available?)
- A faster algorithm for solving one-clock priced timed games
- A theory of timed automata
- Adding negative prices to priced timed games
- Automata, Languages and Programming
- Dynamical properties of timed automata
- Efficient on-the-fly emptiness check for timed Büchi automata
- Energy and mean-payoff timed games
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- Formal Modeling and Analysis of Timed Systems
- Improved undecidability results on weighted timed automata
- Nondeterministic Space is Closed under Complementation
- Number of quantifiers is better than number of tape cells
- On short paths interdiction problems: Total and node-wise limited interdiction
- On the Value Problem in Weighted Timed Games.
- On the optimal reachability problem of weighted timed automata
- Optimal infinite scheduling for multi-priced timed automata
- Optimal paths in weighted timed automata
- Optimal reachability in divergent weighted timed games
- Pseudopolynomial iterative algorithm to solve total-payoff games and min-cost reachability games
- Reachability-Time Games on Timed Automata
- Relationships between nondeterministic and deterministic tape complexities
- Simple priced timed games are not that simple
- Solving Sequential Conditions by Finite-State Strategies
- Symbolic Approximation of Weighted Timed Games
- The method of forced enumeration for nondeterministic automata
- Two-player reachability-price games on single-clock timed automata
- Uppaal in a nutshell
Cited in
(12)- Time-optimal control for discrete-time hybrid automata
- Robust Controller Synthesis in Timed Automata
- Time-scale synthesis of a closed-loop discrete optimal control system
- Control and synthesis of non-interferent timed systems
- Decidability of one-clock weighted timed games with arbitrary weights
- scientific article; zbMATH DE number 3899631 (Why is no real title available?)
- Synthesis of robust optimal real-time systems
- scientific article; zbMATH DE number 1751940 (Why is no real title available?)
- Inaproximability in weighted timed games
- scientific article; zbMATH DE number 5994811 (Why is no real title available?)
- The Complexity of Bounded Synthesis for Timed Control with Partial Observability
- 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)
