nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Games with Full, Longitudinal, and Transverse Observability

verfasst von : Orna Kupferman

Erschienen in: Reachability Problems

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Design and control of multi-agent systems correspond to the synthesis of winning strategies in games that model the interaction between the agents. In games with full observability, the strategies of players depend on the full history of the play. In games with partial observability, strategies depend only on observable components of the history. We survey two approaches to partial observability in two-player turn-based games with behavioral winning conditions. The first is the traditional longitudinal observability, where in all vertices, the players observe the assignment only to an observable subset of the atomic propositions. The second is the recently studied transverse observability, where players observe the assignment to all the atomic propositions, but only in vertices they own.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel On Decision Problems for Substitutions in Symbolic Dynamics

Nächstes Kapitel Reachability Set Generation Using Hybrid Relation Compatible Saturation

Note that memoryless strategies, which depend only on the current vertex of the game, are a special case of strategies with a transverse observability. Since, however, we consider here games with a behavioral winning condition, memoryless strategies are not sufficient. In contrast, in some games with a structural winning condition, say Büchi or parity, memoryless strategies are sufficient, and hence also ones with transverse observability.

It is important to note that the complexities studies here consider two-player games. For settings with more players, the problem is undecidable [3, 15, 17].

Agarwal, S., Kodialam, M.S., Lakshman, T.V.: Traffic engineering in software defined networks. In: Proceedings of the 32nd IEEE International Conference on Computer Communications, pp. 2211–2219 (2013)

Almagor, S., Avni, G., Kupferman, O.: Repairing multi-player games. In: Proceedings of the 26th International Conference on Concurrency Theory. LIPIcs, vol. 42, pp. 325–339 (2015)

Alur, R., Henzinger, T.A., Kupferman, O.: Alternating-time temporal logic. J. ACM 49(5), 672–713 (2002)MathSciNetCrossRef

Chatterjee, K., Doyen, L.: The complexity of partial-observation parity games. In: Fermüller, C.G., Voronkov, A. (eds.) LPAR 2010. LNCS, vol. 6397, pp. 1–14. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-16242-8_1CrossRef

Chatterjee, K., Doyen, L., Henzinger, T.A., Raskin, J.-F.: Algorithms for omega-regular games with imperfect information. In: Ésik, Z. (ed.) CSL 2006. LNCS, vol. 4207, pp. 287–302. Springer, Heidelberg (2006). https://doi.org/10.1007/11874683_19CrossRef

Fisman, D., Kupferman, O.: Reasoning about finite-state switched systems. In: Namjoshi, K., Zeller, A., Ziv, A. (eds.) HVC 2009. LNCS, vol. 6405, pp. 71–86. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19237-1_10CrossRef

Gutierrez, J., Perelli, G., Wooldridge, M.J.: Imperfect information in reactive modules games. Inf. Comput. 261, 650–675 (2018)MathSciNetCrossRef

Kupferman, O., Shenwald, N.: Perspective games with notifications. Submitted (2020)

Kupferman, O., Vardi, G.: Perspective games. In: Proceedings of the 34th IEEE Symposium on Logic in Computer Science, pp. 1–13 (2019)

10.

Kupferman, O., Vardi, M.Y.: Synthesis with incomplete information. In: Advances in Temporal Logic, pp. 109–127. Kluwer Academic Publishers (2000)

11.

Kupferman, O., Vardi, M.Y.: Safraless decision procedures. In: Proceedings of the 46th IEEE Symposium on Foundations of Computer Science, pp. 531–540 (2005)

12.

Liberzon, D.: Switching in Systems and Control. Birkhauser, Boston (2003). https://doi.org/10.1007/978-1-4612-0017-8CrossRefMATH

13.

Lustig, Y., Vardi, M.Y.: Synthesis from component libraries. Softw. Tools Technol. Transf. 15(5–6), 603–618 (2013)CrossRef

14.

Margaliot, M.: Stability analysis of switched systems using variational principles: an introduction. Automatica 42(12), 2059–2077 (2006)MathSciNetCrossRef

15.

Pnueli, A., Rosner, R.: On the synthesis of an asynchronous reactive module. In: Ausiello, G., Dezani-Ciancaglini, M., Della Rocca, S.R. (eds.) ICALP 1989. LNCS, vol. 372, pp. 652–671. Springer, Heidelberg (1989). https://doi.org/10.1007/BFb0035790CrossRef

16.

Puchala, B.: Asynchronous omega-regular games with partial information. In: Hliněný, P., Kučera, A. (eds.) MFCS 2010. LNCS, vol. 6281, pp. 592–603. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15155-2_52CrossRef

17.

Reif, J.H.: The complexity of two-player games of incomplete information. J. Comput. Syst. Sci. 29, 274–301 (1984)MathSciNetCrossRef

18.

Vardi, M.Y., Wolper, P.: Yet another process logic. In: Clarke, E., Kozen, D. (eds.) Logic of Programs 1983. LNCS, vol. 164, pp. 501–512. Springer, Heidelberg (1984). https://doi.org/10.1007/3-540-12896-4_383CrossRef

19.

Vardi, M.Y., Wolper, P.: Automata-theoretic techniques for modal logics of programs. J. Comput. Syst. Sci. 32(2), 182–221 (1986)MathSciNetCrossRef

Titel: Games with Full, Longitudinal, and Transverse Observability
verfasst von: Orna Kupferman
Verlag: Springer International Publishing
Buch: Reachability Problems
Print ISBN: 978-3-030-61738-7

Electronic ISBN: 978-3-030-61739-4

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-61739-4_2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner