conference paper published yes Guy Avni author 463C8BC2-F248-11E8-B48F-1D18A9856A870000-0001-5588-8287 Thomas A Henzinger author 40876CD8-F248-11E8-B48F-1D18A9856A870000-0002-2985-7724 Kaushik Mallik author 0834ff3c-6d72-11ec-94e0-b5b0a4fb85980000-0001-9864-7475 Suman Sadhukhan author K. S. Thejaswini author ToHe department CAV: Computer Aided Verification Vigilant Algorithmic Monitoring of Software project We study the problem of generating paths on a graph that satisfy a collection of w-regular objectives. We propose a decoupled framework in which each objective is assigned to an independent agent that selects a local policy, while a scheduler—oblivious to the graph and objective—dynamically 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 stochastic 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 conventions—simple, a priori restrictions agreed upon before the graph or objectives are revealed—that guarantee satisfaction of all objectives when followed by all agents. We characterize minimally restrictive conventions for major subclasses of w-regular objectives. In particular, Büchi objectives admit universal composition of finite-memory policies without scheduler communication; co-Büchi objectives require only knowledge of whether the agent was scheduled; and parity objectives additionally require knowledge of which agent was scheduled. https://research-explorer.ista.ac.at/download/22719/22730/2026_LNCS_Avni.pdf application/pdfno Springer Nature2026Lisbon, Portugal eng 0302-9743 1611-3349 9783032325181 2605.1318510.1007/978-3-032-32519-8_13 16682237-257 G. Avni, T.A. Henzinger, K. Mallik, S. Sadhukhan, K.S. Thejaswini, in:, 38th International Conference on Computer Aided Verification, Springer Nature, 2026, pp. 237–257. Avni, Guy, et al. “Decoupled Planning for Multiple Omega-Regular Objectives.” <i>38th International Conference on Computer Aided Verification</i>, vol. 16682, Springer Nature, 2026, pp. 237–57, doi:<a href="https://doi.org/10.1007/978-3-032-32519-8_13">10.1007/978-3-032-32519-8_13</a>. Avni, Guy, Thomas A Henzinger, Kaushik Mallik, Suman Sadhukhan, and K. S. Thejaswini. “Decoupled Planning for Multiple Omega-Regular Objectives.” In <i>38th International Conference on Computer Aided Verification</i>, 16682:237–57. Springer Nature, 2026. <a href="https://doi.org/10.1007/978-3-032-32519-8_13">https://doi.org/10.1007/978-3-032-32519-8_13</a>. G. Avni, T. A. Henzinger, K. Mallik, S. Sadhukhan, and K. S. Thejaswini, “Decoupled planning for multiple omega-regular objectives,” in <i>38th International Conference on Computer Aided Verification</i>, Lisbon, Portugal, 2026, vol. 16682, pp. 237–257. Avni G, Henzinger TA, Mallik K, Sadhukhan S, Thejaswini KS. 2026. Decoupled planning for multiple omega-regular objectives. 38th International Conference on Computer Aided Verification. CAV: Computer Aided Verification, LNCS, vol. 16682, 237–257. Avni, G., Henzinger, T. A., Mallik, K., Sadhukhan, S., &#38; Thejaswini, K. S. (2026). Decoupled planning for multiple omega-regular objectives. In <i>38th International Conference on Computer Aided Verification</i> (Vol. 16682, pp. 237–257). Lisbon, Portugal: Springer Nature. <a href="https://doi.org/10.1007/978-3-032-32519-8_13">https://doi.org/10.1007/978-3-032-32519-8_13</a> Avni G, Henzinger TA, Mallik K, Sadhukhan S, Thejaswini KS. Decoupled planning for multiple omega-regular objectives. In: <i>38th International Conference on Computer Aided Verification</i>. Vol 16682. Springer Nature; 2026:237-257. doi:<a href="https://doi.org/10.1007/978-3-032-32519-8_13">10.1007/978-3-032-32519-8_13</a> 227192026-08-16T22:01:44Z2026-08-18T08:41:44Z