Multi-weighted Reachability Games

Brihaye, Thomas; Goeminne, Aline

doi:10.1007/978-3-031-45286-4_7

Request a copy

Paper published in a book (Scientific congresses and symposiums)

Multi-weighted Reachability Games

Brihaye, Thomas; Goeminne, Aline

2023 • In Bournez, Olivier (Ed.) Reachability Problems - 17th International Conference, RP 2023, Proceedings

Peer reviewed

Permalink
https://hdl.handle.net/20.500.12907/47728

DOI
10.1007/978-3-031-45286-4_7

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

multiWeightedReach.pdf

Author preprint (447.63 kB)

Long version of the paper with proofs.

Request a copy

All documents in ORBi UMONS are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

lexico-optimal strategies; Pareto-optimal strategies; two-player games on graphs; Reachability; multi-weighted reachability games

Abstract :

[en] We study two-player multi-weighted reachability games played on a finite directed graph, where an agent, called P1, has several quantitative reachability objectives that he wants to optimize against an antagonistic environment, called P2. In this setting, we ask what cost profiles P1 can ensure regardless of the opponent’s behavior. Cost profiles are compared thanks to: (i) a lexicographic order that ensures the unicity of an upper value and (ii) a componentwise order for which we consider the Pareto frontier. We synthesize (i) lexico-optimal strategies and (ii) Pareto-optimal strategies. The strategies are obtained thanks to a fixpoint algorithm which also computes the upper value in polynomial time and the Pareto frontier in exponential time. Finally, the constrained existence problem is proved in PTIME for the lexicographic order and PSPACE -complete for the componentwise order.

Disciplines :

Computer science

Author, co-author :

Brihaye, Thomas ; Université de Mons - UMONS > Faculté des Science > Service de Mathématiques effectives

Goeminne, Aline ; Université de Mons - UMONS > Faculté des Science > Service de Mathématiques effectives

Language :

English

Title :

Multi-weighted Reachability Games

Publication date :

2023

Event name :

17th International Conference on Reachability Problems

Event place :

Nice, France

Event date :

11-10-2023 => 13-10-2023

Main work title :

Reachability Problems - 17th International Conference, RP 2023, Proceedings

Editor :

Bournez, Olivier

Publisher :

Springer Science and Business Media Deutschland GmbH

ISBN/EAN :

978-3-03-145285-7

Peer reviewed :

Peer reviewed

Additional URL :

https://link.springer.com/content/pdf/10.1007/978-3-031-45286-4_7

Research unit :

S820 - Mathématiques effectives

Research institute :

R150 - Institut de Recherche sur les Systèmes Complexes

Name of the research project :

5581 - CR-Brihaye - RobSynthMulTiGa - Fédération Wallonie Bruxelles
5330 - PDR-Brihaye - RatBeCoSi - Fédération Wallonie Bruxelles

Funders :

F.R.S.-FNRS - Fonds de la Recherche Scientifique [BE]

Funding text :

T. Brihaye—Partly supported by the F.R.S.-FNRS under grant n◦T.0027.21. A. Goeminne— Postdoctoral Researcher of the Fonds de la Recherche Scientifique - FNRS.

Available on ORBi UMONS :

since 10 January 2024

Statistics

Number of views

4 (3 by UMONS)

Number of downloads

2 (2 by UMONS)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

Bibliography

Brenguier, R., Raskin, J.-F.: Pareto curves of multidimensional mean-payoff games. In: Kroening, D., Păsăreanu, C.S. (eds.) CAV 2015. LNCS, vol. 9207, pp. 251–267. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21668-3 15
Brihaye, T., Goeminne, A.: Multi-weighted reachability games (2023). https://arxiv.org/abs/2308.09625
Chatterjee, K., Doyen, L., Henzinger, T.A., Raskin, J.: Generalized mean-payoff and energy games. In: Lodaya, K., Mahajan, M. (eds.) IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010, Chennai, India, 15–18 December 2010, LIPIcs, vol. 8, pp. 505– 516. Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2010). https://doi.org/10.4230/LIPIcs.FSTTCS.2010.505
Chatterjee, K., Katoen, J.-P., Weininger, M., Winkler, T.: Stochastic games with lexicographic reachability-safety objectives. In: Lahiri, S.K., Wang, C. (eds.) CAV 2020. LNCS, vol. 12225, pp. 398–420. Springer, Cham (2020). https://doi.org/10. 1007/978-3-030-53291-8 21
Chatterjee, K., Randour, M., Raskin, J.-F.: Strategy synthesis for multidimensional quantitative objectives. In: Koutny, M., Ulidowski, I. (eds.) CONCUR 2012. LNCS, vol. 7454, pp. 115–131. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32940-1 10
Delzanno, G., Raskin, J.-F.: Symbolic representation of upward-closed sets. In: Graf, S., Schwartzbach, M. (eds.) TACAS 2000. LNCS, vol. 1785, pp. 426–441. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-46419-0 29
Fijalkow, N., Horn, F.: Les jeux d’accessibilité généralisée. Tech. Sci. Informatiques 32(9-10), 931–949 (2013). https://doi.org/10.3166/tsi.32.931-949
Juhl, L., Guldstrand Larsen, K., Raskin, J.-F.: Optimal bounds for multiweighted and parametrised energy games. In: Liu, Z., Woodcock, J., Zhu, H. (eds.) Theories of Programming and Formal Methods. LNCS, vol. 8051, pp. 244–255. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39698-4 15
Laroussinie, F., Markey, N., Oreiby, G.: Model-checking timed ATL for durational concurrent game structures. In: Asarin, E., Bouyer, P. (eds.) FORMATS 2006. LNCS, vol. 4202, pp. 245–259. Springer, Heidelberg (2006). https://doi.org/10. 1007/11867340 18
Larsen, K.G., Rasmussen, J.I.: Optimal conditional reachability for multi-priced timed automata. In: Sassone, V. (ed.) FoSSaCS 2005. LNCS, vol. 3441, pp. 234– 249. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-31982-5 15
Puri, A., Tripakis, S.: Algorithms for the multi-constrained routing problem. In: Penttonen, M., Schmidt, E.M. (eds.) SWAT 2002. LNCS, vol. 2368, pp. 338–347. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45471-3 35
Travers, S.D.: The complexity of membership problems for circuits over sets of integers. Theor. Comput. Sci. 369(1-3), 211–229 (2006). https://doi.org/10.1016/j.tcs.2006.08.017