Optimal reachability in divergent weighted timed games

DOI10.1007/978-3-662-54458-7_10zbMATH Open1486.68092arXiv1701.03716OpenAlexW2575538450MaRDI QIDQ2988366FDOQ2988366

Pierre-Alain Reynier, Damien Busatto-Gaston, Benjamin Monmege

Publication date: 19 May 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: Weighted timed games are played by two players on a timed automaton equipped with weights: one player wants to minimise the accumulated weight while reaching a target, while the other has an opposite objective. Used in a reactive synthesis perspective, this quantitative extension of timed games allows one to measure the quality of controllers. Weighted timed games are notoriously difficult and quickly undecidable, even when restricted to non-negative weights. Decidability results exist for subclasses of one-clock games, and for a subclass with non-negative weights defined by a semantical restriction on the weights of cycles. In this work, we introduce the class of divergent weighted timed games as a generalisation of this semantical restriction to arbitrary weights. We show how to compute their optimal value, yielding the first decidable class of weighted timed games with negative weights and an arbitrary number of clocks. In addition, we prove that divergence can be decided in polynomial space. Last, we prove that for untimed games, this restriction yields a class of games for which the value can be computed in polynomial time.

Full work available at URL: https://arxiv.org/abs/1701.03716

Recommendations

• Automata, Languages and Programming
• On the Value Problem in Weighted Timed Games.
• Robust weighted timed automata and games
• Formal Modeling and Analysis of Timed Systems
• On the optimal reachability problem of weighted timed automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Applications of game theory (91A80) 2-person games (91A05)

Cites Work

• A theory of timed automata
• 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
• 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
• Dynamical properties of timed automata
• Optimal infinite scheduling for multi-priced timed automata
• Adding Negative Prices to Priced Timed Games
• Pseudopolynomial iterative algorithm to solve total-payoff games and min-cost reachability games
• Title not available (Why is that?)
• 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.

Cited In (9)

• Symbolic Approximation of Weighted Timed Games
• Title not available (Why is that?)
• Expected reachability-time games
• On the Value Problem in Weighted Timed Games.
• Title not available (Why is that?)
• Optimal controller synthesis for timed systems
• Optimal Reachability in Divergent Weighted Timed Games
• Automata, Languages and Programming
• Alternating Reachability Games with Behavioral and Revenue Objectives

This page was built for publication: Optimal reachability in divergent weighted timed games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2988366)