{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T19:00:59Z","timestamp":1743102059759,"version":"3.40.3"},"publisher-location":"Cham","reference-count":42,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031711619"},{"type":"electronic","value":"9783031711626"}],"license":[{"start":{"date-parts":[[2024,9,11]],"date-time":"2024-09-11T00:00:00Z","timestamp":1726012800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,9,11]],"date-time":"2024-09-11T00:00:00Z","timestamp":1726012800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Stochastic games are a well established model for multi-agent sequential decision making under uncertainty. In practical applications, though, agents often have only partial observability of their environment. Furthermore, agents increasingly perceive their environment using data-driven approaches such as neural networks trained on continuous data. We propose the model of neuro-symbolic partially-observable stochastic games (NS-POSGs), a variant of continuous-space concurrent stochastic games that explicitly incorporates neural perception mechanisms. We focus on a one-sided setting with a partially-informed agent using discrete, data-driven observations and another, fully-informed agent. We present a new method, called one-sided NS-HSVI, for approximate solution of one-sided NS-POSGs, which exploits the piecewise constant structure of the model. Using neural network pre-image analysis to construct finite polyhedral representations and particle-based representations for beliefs, we implement our approach and illustrate its practical applicability\u00a0to the analysis of pedestrian-vehicle and pursuit-evasion scenarios.<\/jats:p>","DOI":"10.1007\/978-3-031-71162-6_19","type":"book-chapter","created":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T02:02:27Z","timestamp":1725933747000},"page":"363-380","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Partially Observable Stochastic Games with\u00a0Neural Perception Mechanisms"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8685-5055","authenticated-orcid":false,"given":"Rui","family":"Yan","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6570-9737","authenticated-orcid":false,"given":"Gabriel","family":"Santos","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9326-4344","authenticated-orcid":false,"given":"Gethin","family":"Norman","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4137-8862","authenticated-orcid":false,"given":"David","family":"Parker","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9022-7599","authenticated-orcid":false,"given":"Marta","family":"Kwiatkowska","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,9,11]]},"reference":[{"key":"19_CR1","doi-asserted-by":"crossref","unstructured":"Bagnara, R., Hill, P.M., Zaffanella, E.: The Parma Polyhedra Library: toward a complete set of numerical abstractions for the analysis and verification of hardware and software systems. Sci. Comput. Programm. 72(1), 3\u201321 (2008). https:\/\/www.bugseng.com\/ppl","DOI":"10.1016\/j.scico.2007.08.001"},{"key":"19_CR2","unstructured":"Bhabak, A., Saha, S.: Partially observable discrete-time discounted Markov games with general utility. arXiv:2211.07888 (2022)"},{"key":"19_CR3","doi-asserted-by":"publisher","first-page":"829","DOI":"10.1613\/jair.4477","volume":"51","author":"B Bosansky","year":"2014","unstructured":"Bosansky, B., Kiekintveld, C., Lisy, V., Pechoucek, M.: An exact double-oracle algorithm for zero-sum extensive-form games with imperfect information. J. Artif. Intell. Res. 51, 829\u2013866 (2014)","journal-title":"J. Artif. Intell. Res."},{"key":"19_CR4","unstructured":"Brechtel, S., Gindele, T., Dillmann, R.: Solving Continuous POMDPs: value iteration with incremental learning of an efficient space representation. In: Proceedings of ICML\u201913, pp. 370\u2013378. PMLR (2013)"},{"key":"19_CR5","unstructured":"Brown, N., Bakhtin, A., Lerer, A., Gong, Q.: Combining deep reinforcement learning and search for imperfect-information games. In: Proceedings of NeurIPS\u201920, pp. 17057\u201317069. Curran Associates, Inc. (2020)"},{"issue":"6","key":"19_CR6","doi-asserted-by":"publisher","first-page":"1488","DOI":"10.1109\/TRO.2019.2933720","volume":"35","author":"L Burks","year":"2019","unstructured":"Burks, L., Loefgren, I., Ahmed, N.R.: Optimal continuous state POMDP planning with semantic observations: a variational approach. IEEE Trans. Rob. 35(6), 1488\u20131507 (2019)","journal-title":"IEEE Trans. Rob."},{"key":"19_CR7","doi-asserted-by":"crossref","unstructured":"Carr, S., Jansen, N., Bharadwaj, S., Spaan, M.T., Topcu, U.: Safe policies for factored partially observable stochastic games. In: Robotics: Science and System XVII (2021)","DOI":"10.15607\/RSS.2021.XVII.079"},{"issue":"4","key":"19_CR8","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/s10514-011-9241-4","volume":"31","author":"TH Chung","year":"2011","unstructured":"Chung, T.H., Hollinger, G.A., Isler, V.: Search and pursuit-evasion in mobile robotics. Auton. Robot. 31(4), 299\u2013316 (2011)","journal-title":"Auton. Robot."},{"key":"19_CR9","doi-asserted-by":"crossref","unstructured":"Delage, A., Buffet, O., Dibangoye, J.S., Saffidine, A.: HSVI can solve zero-sum partially observable stochastic games. Dyn. Games Appl., 1\u201355 (2023)","DOI":"10.1007\/s13235-023-00519-6"},{"key":"19_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3437-9","volume-title":"Sequential Monte Carlo Methods in Practice","year":"2001","unstructured":"Doucet, A., Freitas, N., Gordon, N. (eds.): Sequential Monte Carlo Methods in Practice. Springer, New York, NY (2001). https:\/\/doi.org\/10.1007\/978-1-4757-3437-9"},{"key":"19_CR11","unstructured":"Emery-Montemerlo, R., Gordon, G., Schneider, J., Thrun, S.: Approximate solutions for partially observable stochastic games with common payoffs. In: Proceedings of AAMAS\u201904, pp. 136\u2013143. IEEE (2004)"},{"key":"19_CR12","unstructured":"Feng, Z., Dearden, R., Meuleau, N., Washington, R.: Dynamic programming for structured continuous Markov decision problems. In: Proceedings of UAI\u201904, pp. 154\u2013161 (2004)"},{"key":"19_CR13","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.aap.2017.11.015","volume":"111","author":"T Fu","year":"2018","unstructured":"Fu, T., Miranda-Moreno, L., Saunier, N.: A novel framework to evaluate pedestrian safety at non-signalized locations. Accid. Anal. Prev. 111, 23\u201333 (2018)","journal-title":"Accid. Anal. Prev."},{"key":"19_CR14","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1023\/B:JOTA.0000026133.56615.cf","volume":"121","author":"MK Ghosh","year":"2004","unstructured":"Ghosh, M.K., McDonald, D., Sinha, S.: Zero-sum stochastic games with partial information. J. Optim. Theory Appl. 121, 99\u2013118 (2004)","journal-title":"J. Optim. Theory Appl."},{"key":"19_CR15","unstructured":"Guestrin, C., Hauskrecht, M., Kveton, B.: Solving factored MDPs with continuous and discrete variables. In: Proceedings of UAI\u201904, pp. 235\u2013242 (2004)"},{"key":"19_CR16","unstructured":"Gurobi Optimization, LLC: Gurobi Optimizer Reference Manual (2021). https:\/\/www.gurobi.com"},{"key":"19_CR17","unstructured":"Hansen, E.A., Bernstein, D.S., Zilberstein, S.: Dynamic programming for partially observable stochastic games. In: Proceedings of AAAI\u201904, vol.\u00a04, pp. 709\u2013715 (2004)"},{"key":"19_CR18","doi-asserted-by":"crossref","unstructured":"Hor\u00e1k, K., Bo\u0161ansk\u1ef3, B.: Solving partially observable stochastic games with public observations. In: Proceedings of AAAI\u201919, vol.\u00a033, pp. 2029\u20132036 (2019)","DOI":"10.1609\/aaai.v33i01.33012029"},{"key":"19_CR19","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2022.103838","volume":"316","author":"K Hor\u00e1k","year":"2023","unstructured":"Hor\u00e1k, K., Bo\u0161ansk\u1ef3, B., Kova\u0159\u00edk, V., Kiekintveld, C.: Solving zero-sum one-sided partially observable stochastic games. Artif. Intell. 316, 103838 (2023)","journal-title":"Artif. Intell."},{"issue":"3","key":"19_CR20","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/j.tcs.2008.02.041","volume":"399","author":"V Isler","year":"2008","unstructured":"Isler, V., Nikhil, K.: The role of information in the cop-robber game. Theoret. Comput. Sci. 399(3), 179\u2013190 (2008)","journal-title":"Theoret. Comput. Sci."},{"key":"19_CR21","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2021.103645","volume":"303","author":"V Kova\u0159\u00edk","year":"2022","unstructured":"Kova\u0159\u00edk, V., Schmid, M., Burch, N., Bowling, M., Lis\u1ef3, V.: Rethinking formal models of partially observable multiagent decision making. Artif. Intell. 303, 103645 (2022)","journal-title":"Artif. Intell."},{"key":"19_CR22","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2022.103805","volume":"314","author":"V Kova\u0159\u00edk","year":"2023","unstructured":"Kova\u0159\u00edk, V., Seitz, D., Lis\u1ef3, V., Rudolf, J., Sun, S., Ha, K.: Value functions for depth-limited solving in zero-sum imperfect-information games. Artif. Intell. 314, 103805 (2023)","journal-title":"Artif. Intell."},{"key":"19_CR23","unstructured":"Kumar, A., Zilberstein, S.: Dynamic programming approximations for partially observable stochastic games. In: Proceedings of FLAIRS\u201909, pp. 547\u2013552 (2009)"},{"issue":"1\u20132","key":"19_CR24","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/S0004-3702(02)00378-8","volume":"147","author":"O Madani","year":"2003","unstructured":"Madani, O., Hanks, S., Condon, A.: On the undecidability of probabilistic planning and related stochastic optimization problems. Artif. Intell. 147(1\u20132), 5\u201334 (2003)","journal-title":"Artif. Intell."},{"key":"19_CR25","unstructured":"Matoba, K., Fleuret, F.: Computing preimages of deep neural networks with applications to safety (2020). https:\/\/openreview.net\/forum?id=FN7_BUOG78e"},{"issue":"6337","key":"19_CR26","doi-asserted-by":"publisher","first-page":"508","DOI":"10.1126\/science.aam6960","volume":"356","author":"M Morav\u010d\u00edk","year":"2017","unstructured":"Morav\u010d\u00edk, M., et al.: DeepStack: expert-level artificial intelligence in heads-up no-limit poker. Science 356(6337), 508\u2013513 (2017)","journal-title":"Science"},{"key":"19_CR27","first-page":"2329","volume":"7","author":"JM Porta","year":"2006","unstructured":"Porta, J.M., Vlassis, N., Spaan, M.T., Poupart, P.: Point-based value iteration for continuous POMDPs. J. Mach. Learn. Res. 7, 2329\u20132367 (2006)","journal-title":"J. Mach. Learn. Res."},{"key":"19_CR28","doi-asserted-by":"crossref","unstructured":"Rasouli, A., Kotseruba, I., Kunic, T., Tsotsos, J.K.: PIE: a large-scale dataset and models for pedestrian intention estimation and trajectory prediction. In: Proceedings of ICCV\u201919, pp. 6262\u20136271 (2019)","DOI":"10.1109\/ICCV.2019.00636"},{"key":"19_CR29","doi-asserted-by":"crossref","unstructured":"Rasouli, A., Kotseruba, I., Tsotsos, J.K.: Are they going to cross? A benchmark dataset and baseline for pedestrian crosswalk behavior. In: Proceedings of ICCV\u201917, pp. 206\u2013213 (2017)","DOI":"10.1109\/ICCVW.2017.33"},{"issue":"1","key":"19_CR30","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1007\/s10957-013-0359-8","volume":"160","author":"S Saha","year":"2014","unstructured":"Saha, S.: Zero-sum stochastic games with partial information and average payoff. J. Optim. Theory Appl. 160(1), 344\u2013354 (2014)","journal-title":"J. Optim. Theory Appl."},{"key":"19_CR31","unstructured":"Smith, T., Simmons, R.: Heuristic search value iteration for POMDPs. In: Proceedings of UAI\u201904, pp. 520\u2013527. AUAI (2004)"},{"key":"19_CR32","first-page":"1628","volume":"285","author":"AJ Wiggers","year":"2016","unstructured":"Wiggers, A.J., Oliehoek, F.A., Roijers, D.M.: Structure in the value function of two-player zero-sum games of incomplete information. Front. Artif. Intell. Appl. 285, 1628\u20131629 (2016)","journal-title":"Front. Artif. Intell. Appl."},{"key":"19_CR33","unstructured":"Yan, R., Santos, G., Norman, G., Parker, D., Kwiatkowska, M.: Strategy synthesis for zero-sum neuro-symbolic concurrent stochastic games. arXiv 2202.06255 (2022)"},{"key":"19_CR34","unstructured":"Yan, R., Santos, G., Duan, X., Parker, D., Kwiatkowska, M.: Finite-horizon equilibria for neuro-symbolic concurrent stochastic games. In: Proceedings of UAI\u201922, pp. 2170\u20132180. AUAI Press (2022)"},{"key":"19_CR35","doi-asserted-by":"crossref","unstructured":"Yan, R., Santos, G., Norman, G., Parker, D., Kwiatkowska, M.: Partially observable stochastic games with neural perception mechanisms. arXiv:2310.11566 (2023)","DOI":"10.1007\/978-3-031-71162-6_19"},{"key":"19_CR36","unstructured":"Yan, R., Santos, G., Norman, G., Parker, D., Kwiatkowska, M.: Point-based value iteration for POMDPs with neural perception mechanisms. arXiv 2306.17639 (2023)"},{"key":"19_CR37","doi-asserted-by":"crossref","unstructured":"Yan, R., Santos, G., Norman, G., Parker, D., Kwiatkowska, M.: HSVI-based online minimax strategies for partially observable stochastic games with neural perception mechanisms. In: Proceedings of L4DC\u201924 (2024)","DOI":"10.1007\/978-3-031-71162-6_19"},{"key":"19_CR38","unstructured":"Zamani, Z., Sanner, S., Poupart, P., Kersting, K.: Symbolic dynamic programming for continuous state and observation POMDPs. In: Advances in Neural Information Processing Systems, vol. 25 (2012)"},{"key":"19_CR39","unstructured":"Zettlemoyer, L., Milch, B., Kaelbling, L.: Multi-agent filtering with infinitely nested beliefs. In: Advances in Neural Information Processing Systems, vol. 21 (2008)"},{"key":"19_CR40","doi-asserted-by":"publisher","DOI":"10.1016\/j.automatica.2022.110231","volume":"140","author":"W Zheng","year":"2022","unstructured":"Zheng, W., Jung, T., Lin, H.: The Stackelberg equilibrium for one-sided zero-sum partially observable stochastic games. Automatica 140, 110231 (2022)","journal-title":"Automatica"},{"key":"19_CR41","doi-asserted-by":"crossref","unstructured":"Zheng, W., Jung, T., Lin, H.: Continuous-observation one-sided two-player zero-sum partially observable stochastic game with public actions. IEEE Trans. Autom. Control, 1\u201315 (2023)","DOI":"10.1109\/TAC.2023.3276749"},{"key":"19_CR42","unstructured":"Zinkevich, M., Johanson, M., Bowling, M., Piccione, C.: Regret minimization in games with incomplete information. In: Advances in Neural Information Processing Systems, vol. 20 (2007)"}],"container-title":["Lecture Notes in Computer Science","Formal Methods"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-71162-6_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,27]],"date-time":"2024-11-27T23:02:09Z","timestamp":1732748529000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-71162-6_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,11]]},"ISBN":["9783031711619","9783031711626"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-71162-6_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024,9,11]]},"assertion":[{"value":"11 September 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Formal Methods","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Milan","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 September 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 September 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fm2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.fm24.polimi.it\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}