{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T08:03:06Z","timestamp":1784793786452,"version":"3.55.0"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032325181","type":"print"},{"value":"9783032325198","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,7,24]],"date-time":"2026-07-24T00:00:00Z","timestamp":1784851200000},"content-version":"vor","delay-in-days":204,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We study the problem of generating paths on a graph that satisfy a collection of\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\omega $$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>\u03c9<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -regular objectives. We propose a decoupled framework in which each objective is assigned to an independent agent that selects a\n                    <jats:italic>local<\/jats:italic>\n                    policy, while a scheduler\u2014oblivious to the graph and objective\u2014dynamically composes these policies into a single path. We ask when such a composition satisfies all objectives, assuming their conjunction is realizable. The framework enables modular policy design but raises fundamental compositional challenges. We show that even extremely fair deterministic schedulers do not ensure correctness, and that\n                    <jats:italic>stochastic<\/jats:italic>\n                    schedulers, while necessary, are insufficient without coordination. For safety objectives, we demonstrate that fully decentralized implementations are impossible, and we introduce a protocol for synchronizing on maximal safe actions. For non-safety objectives, we introduce\n                    <jats:italic>conventions<\/jats:italic>\n                    \u2014simple, a priori restrictions agreed upon before the graph or objectives are revealed\u2014that guarantee satisfaction of all objectives when followed by all agents. We characterize minimally restrictive conventions for major subclasses of\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\omega $$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>\u03c9<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -regular objectives. In particular, B\u00fcchi objectives admit universal composition of finite-memory policies without scheduler communication; co-B\u00fcchi objectives require only knowledge of whether the agent was scheduled; and parity objectives additionally require knowledge of which agent was scheduled.\n                  <\/jats:p>","DOI":"10.1007\/978-3-032-32519-8_13","type":"book-chapter","created":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T07:17:49Z","timestamp":1784791069000},"page":"237-257","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Decoupled Planning for\u00a0Multiple Omega-Regular Objectives"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5588-8287","authenticated-orcid":false,"given":"Guy","family":"Avni","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas A.","family":"Henzinger","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9864-7475","authenticated-orcid":false,"given":"Kaushik","family":"Mallik","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4802-6803","authenticated-orcid":false,"given":"Suman","family":"Sadhukhan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6077-7514","authenticated-orcid":false,"given":"K. S.","family":"Thejaswini","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,7,24]]},"reference":[{"issue":"3","key":"13_CR1","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/BF01782772","volume":"2","author":"B Alpern","year":"1987","unstructured":"Alpern, B., Schneider, F.B.: Recognizing safety and liveness. Distrib. Comput. 2(3), 117\u2013126 (1987). https:\/\/doi.org\/10.1007\/BF01782772","journal-title":"Distrib. Comput."},{"key":"13_CR2","doi-asserted-by":"publisher","unstructured":"Anand, A., Nayak, S.P., Schmuck, A.K.: Synthesizing permissive winning strategy templates for parity games. In: Enea, C., Lal, A. (eds.) CAV 2023. LNCS, vol. 13964, pp. 436\u2013458. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-37706-8_22","DOI":"10.1007\/978-3-031-37706-8_22"},{"key":"13_CR3","doi-asserted-by":"publisher","unstructured":"Avni, G., Henzinger, T.A., Chonev, V.: Infinite-duration bidding games. J. ACM 66(4), 31:1\u201331:29 (2019). https:\/\/doi.org\/10.1145\/3340295","DOI":"10.1145\/3340295"},{"key":"13_CR4","doi-asserted-by":"publisher","unstructured":"Avni, G., Henzinger, T.A., Mallik, K., Sadhukhan, S., Thejaswini, K.S.: Decoupled planning for multiple omega-regular objectives. CoRR arXiv:2605.13185 (2026). https:\/\/doi.org\/10.48550\/arXiv.2605.13185","DOI":"10.48550\/arXiv.2605.13185"},{"key":"13_CR5","doi-asserted-by":"publisher","unstructured":"Avni, G., Mallik, K., Sadhukhan, S.: Auction-based scheduling. In: Finkbeiner, B., Kov\u00e1cs, L. (eds.) TACAS 2024. LNCS, vol. 14572, pp. 153\u2013172. Springer, Cham (2024). https:\/\/doi.org\/10.1007\/978-3-031-57256-2_8","DOI":"10.1007\/978-3-031-57256-2_8"},{"key":"13_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/978-3-662-46681-0_22","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"N Basset","year":"2015","unstructured":"Basset, N., Kwiatkowska, M., Topcu, U., Wiltsche, C.: Strategy synthesis for stochastic games with multiple long-run objectives. In: Baier, C., Tinelli, C. (eds.) TACAS 2015. LNCS, vol. 9035, pp. 256\u2013271. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46681-0_22"},{"key":"13_CR7","doi-asserted-by":"publisher","first-page":"536","DOI":"10.1016\/j.ic.2017.09.010","volume":"261","author":"N Basset","year":"2018","unstructured":"Basset, N., Kwiatkowska, M., Wiltsche, C.: Compositional strategy synthesis for stochastic games with multiple objectives. Inf. Comput. 261, 536\u2013587 (2018). https:\/\/doi.org\/10.1016\/j.ic.2017.09.010","journal-title":"Inf. Comput."},{"key":"13_CR8","doi-asserted-by":"publisher","unstructured":"Billingsley, P.: Probability and Measure, 3rd edn. Wiley, New York (1995). https:\/\/doi.org\/10.1017\/S0013091500004521","DOI":"10.1017\/S0013091500004521"},{"key":"13_CR9","doi-asserted-by":"publisher","unstructured":"Chatterjee, K., De\u00a0Alfaro, L., Henzinger, T.A.: Trading memory for randomness. In: 2004 Proceedings of the First International Conference on the Quantitative Evaluation of Systems, QEST 2004, pp. 206\u2013217. IEEE (2004). https:\/\/doi.org\/10.1109\/QEST.2004.1348035","DOI":"10.1109\/QEST.2004.1348035"},{"key":"13_CR10","doi-asserted-by":"publisher","unstructured":"Chatterjee, K., Piterman, N.: Combinations of qualitative winning for stochastic parity games. In: 30th International Conference on Concurrency Theory, CONCUR, pp. 6:1\u20136:17. LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPICS.CONCUR.2019.6","DOI":"10.4230\/LIPICS.CONCUR.2019.6"},{"key":"13_CR11","unstructured":"De\u00a0Alfaro, L.: Formal verification of probabilistic systems. Stanford university (1998)"},{"key":"13_CR12","doi-asserted-by":"publisher","unstructured":"De\u00a0Alfaro, L., Henzinger, T.A.: Concurrent omega-regular games. In: Proceedings Fifteenth Annual IEEE Symposium on Logic in Computer Science (Cat. No. 99CB36332), pp. 141\u2013154. IEEE (2000). https:\/\/doi.org\/10.1109\/LICS.2000.855763","DOI":"10.1109\/LICS.2000.855763"},{"key":"13_CR13","doi-asserted-by":"publisher","unstructured":"Finkbeiner, B., Schewe, S.: Uniform distributed synthesis. In: 20th Annual IEEE Symposium on Logic in Computer Science (LICS 2005), pp. 321\u2013330. IEEE (2005). https:\/\/doi.org\/10.1109\/LICS.2005.53","DOI":"10.1109\/LICS.2005.53"},{"key":"13_CR14","doi-asserted-by":"publisher","unstructured":"Guenov, M., Barker, S.: Application of axiomatic design and design structure matrix to the decomposition of engineering systems. Syst. Eng. 8, 29\u201340 (2005). https:\/\/doi.org\/10.1002\/sys.20015","DOI":"10.1002\/sys.20015"},{"key":"13_CR15","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1016\/J.PROTCY.2016.03.010","volume":"23","author":"AK Guruji","year":"2016","unstructured":"Guruji, A.K., Agarwal, H., Parsediya, D.: Time-efficient A* algorithm for robot path planning. Procedia Technol. 23, 144\u2013149 (2016). https:\/\/doi.org\/10.1016\/J.PROTCY.2016.03.010","journal-title":"Procedia Technol."},{"issue":"7","key":"13_CR16","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1145\/2209249.2209270","volume":"55","author":"D Harel","year":"2012","unstructured":"Harel, D., Marron, A., Weiss, G.: Behavioral programming. Commun. ACM 55(7), 90\u2013100 (2012). https:\/\/doi.org\/10.1145\/2209249.2209270","journal-title":"Commun. ACM"},{"issue":"5","key":"13_CR17","doi-asserted-by":"publisher","first-page":"1830","DOI":"10.1257\/000282803322655581","volume":"93","author":"S Hart","year":"2003","unstructured":"Hart, S., Mas-Colell, A.: Uncoupled dynamics do not lead to Nash equilibrium. Am. Econ. Rev. 93(5), 1830\u20131836 (2003). https:\/\/doi.org\/10.1257\/000282803322655581","journal-title":"Am. Econ. Rev."},{"issue":"2","key":"13_CR18","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1080\/0740817X.2013.803639","volume":"46","author":"E Kagan","year":"2014","unstructured":"Kagan, E., Ben-Gal, I.: A group testing algorithm with online informational learning. IIE Trans. 46(2), 164\u2013184 (2014). https:\/\/doi.org\/10.1080\/0740817X.2013.803639","journal-title":"IIE Trans."},{"key":"13_CR19","doi-asserted-by":"publisher","unstructured":"Klein, D., Manning, C.D.: A* parsing: fast exact viterbi parse selection. In: Proceedings of the 2003 Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics, pp. 119\u2013126 (2003). https:\/\/doi.org\/10.3115\/1073445.1073461","DOI":"10.3115\/1073445.1073461"},{"key":"13_CR20","doi-asserted-by":"publisher","unstructured":"Kupermann, O., Varfi, M.: Synthesizing distributed systems. In: Proceedings 16th Annual IEEE Symposium on Logic in Computer Science, pp. 389\u2013398. IEEE (2001). https:\/\/doi.org\/10.1109\/LICS.2001.932514","DOI":"10.1109\/LICS.2001.932514"},{"issue":"2","key":"13_CR21","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1006\/game.1998.0676","volume":"27","author":"AJ Lazarus","year":"1999","unstructured":"Lazarus, A.J., Loeb, D.E., Propp, J.G., Stromquist, W.R., Ullman, D.H.: Combinatorial games under auction play. Games Econom. Behav. 27(2), 229\u2013264 (1999). https:\/\/doi.org\/10.1006\/game.1998.0676","journal-title":"Games Econom. Behav."},{"key":"13_CR22","doi-asserted-by":"publisher","unstructured":"Lewis, D.: Convention: A Philosophical Study. Wiley (2008). https:\/\/doi.org\/10.1002\/9780470693711","DOI":"10.1002\/9780470693711"},{"key":"13_CR23","doi-asserted-by":"publisher","unstructured":"Pneuli, A., Rosner, R.: Distributed reactive systems are hard to synthesize. In: Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science, pp. 746\u2013757. IEEE (1990). https:\/\/doi.org\/10.1109\/FSCS.1990.89597","DOI":"10.1109\/FSCS.1990.89597"},{"key":"13_CR24","doi-asserted-by":"publisher","unstructured":"Pnueli, A.: On the extremely fair treatment of probabilistic algorithms. In: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, pp. 278\u2013290 (1983). https:\/\/doi.org\/10.1145\/800061.808757","DOI":"10.1145\/800061.808757"},{"issue":"1","key":"13_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1993.1012","volume":"103","author":"A Pnueli","year":"1993","unstructured":"Pnueli, A., Zuck, L.D.: Probabilistic verification. Inf. Comput. 103(1), 1\u201329 (1993). https:\/\/doi.org\/10.1006\/inco.1993.1012","journal-title":"Inf. Comput."},{"key":"13_CR26","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1613\/jair.3987","volume":"48","author":"DM Roijers","year":"2013","unstructured":"Roijers, D.M., Vamplew, P., Whiteson, S., Dazeley, R.: A survey of multi-objective sequential decision-making. J. Artif. Intell. Res. 48, 67\u2013113 (2013). https:\/\/doi.org\/10.1613\/jair.3987","journal-title":"J. Artif. Intell. Res."},{"key":"13_CR27","doi-asserted-by":"publisher","unstructured":"Sch\u00e4fer, L., Christianos, F., Hanna, J.P., Albrecht, S.V.: Decoupled reinforcement learning to stabilise intrinsically-motivated exploration. In: Proceedings of the 21st AAMAS, pp. 1146\u20131154. IFAAMAS (2022). https:\/\/doi.org\/10.65109\/EYJJ1710","DOI":"10.65109\/EYJJ1710"}],"container-title":["Lecture Notes in Computer Science","Computer Aided Verification"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-32519-8_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T07:17:51Z","timestamp":1784791071000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-32519-8_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032325181","9783032325198"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-32519-8_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"24 July 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","label":"Disclosure of Interests","group":{"name":"EthicsHeading","label":"Ethics"}},{"value":"CAV","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Computer Aided Verification","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Lisbon","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Portugal","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 July 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 July 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"38","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cav2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.floc26.org\/program","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}