Decoupled Planning for Multiple Omega-Regular Objectives
Guy Avni, Thomas A. Henzinger, Kaushik Mallik, Suman Sadhukhan, K. S. Thejaswini · 2026
Read Decoupled Planning for Multiple Omega-Regular Objectives by Guy Avni, Thomas A. Henzinger, Kaushik Mallik, Suman Sadhukhan, K. S. Thejaswini (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-13185.txt.
Introduction
Avni, Henzinger, Mallik, Sadhukhan and Thejaswini study graph paths meeting omega-regular goals. Each goal goes to its own agent with a local policy, while a blind scheduler weaves policies into one path. They ask when the weave meets all goals, assuming their form is realisable. Even very fair fixed schedulers fail, and random schedulers, while needed, fall short without coordination. For safety goals, decentralised code proves impossible, and a protocol syncs on maximal safe actions. For other goals, rules agreed beforehand guarantee success, with least-restrictive rules mapped.
Catalog record
| CREATOR | Guy Avni, Thomas A. Henzinger, Kaushik Mallik, Suman Sadhukhan, K. S. Thejaswini |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 100333 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.13185
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Decoupled Planning for Multiple Omega-Regular Objectives Thanks: This work is funded by the following grants: European Research Council under Grant No.: ERC-2020-AdG 101020093, ISF grant no. 1679/21, grant RYC2024-049116, MICIU/AEI/10.13039/501100011033, the ESF+, and Volkswagen Foundation within its Momentum framework under project no. 9C283. The last author was employed at Institute of Science and Technology Austria for part of this work. Guy Avni, Thomas A. Henzinger, Kaushik Mallik, Suman Sadhukhan, K. S. Thejaswini Abstract We study the problem of generating paths on a graph that satisfy a collection of ω \omega -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 ω \omega -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. 1 Introduction The graph traversal problem takes as input a finite directed graph and a temporal specification over sequences of vertices, and the goal is to compute a traversal policy for selecting the next vertex based on the history of the past vertices, such that the resulting infinite path fulfills the given specification. A primary application of graph traversal is robotic path planning [ 16 ] , and other applications include parsing natural languages using stochastic grammars [ 20 ] , and informational search with online learning [ 19 ] . Often, the specification requires simultaneous fulfillment of multiple, competing objectives; for example, a robot may need to simultaneously patrol a given location and visit the charging station intermittently. The traditional approach to solve such problems is to compute a single, monolithic policy for the conjunction of all objectives. In this paper, we introduce a decoupled framework for graph traversals. Consider a collection of objectives \varphi_{1},\ldots,\varphi_{N} that a path needs to satisfy. We describe the framework as an interaction among N agents. For 1\leq i\leq N , Agent i is only responsible for satisfying objective \varphi_{i} and does so by selecting a policy that achieves \varphi_{i} . At runtime, a fixed scheduler composes the policies by scheduling one of the agents to choose the next vertex at each step. Our goal is to ensure that the path generated by the composition satisfies all objectives (either deterministically or almost surely ) while achieving maximal decoupling by keeping the agents’ choices and scheduler as independent as possible. Before we make these goals more concrete and discuss the features that they lead to, we first illustrate the framework and its challenges. \ell t_{1} t_{2} start r b_{2} b_{1} Fig. 1(a) Reachability objectives given by T_{1}=\left\{\ell\right\} and T_{2}=\left\{r\right\} , and policies \pi_{1} dashed red and \pi_{2} dotted blue . v start a_{1} b_{1} a_{2} b_{2} Fig. 1(b) A graph with two Büchi objectives given by accepting vertices T_{1}=\left\{b_{1}\right\} and T_{2}=\left\{b_{2}\right\} . Example 1 Consider a coffee-serving robot in an office modeled as in Fig. 1(a) . The objective \varphi_{1} requires “reach and serve coffee at \ell ” and the objective \varphi_{2} requires “reach r .” Suppose Agent 1 and Agent 2 choose policies \pi_{1} and \pi_{2} that always take the shortest paths towards their respective goal states. Clearly, if the robot follows only \pi_{1} or only \pi_{2} , respectively, \varphi_{1} and \varphi_{2} are satisfied. We describe two schedulers for composing the policies at runtime. First, consider a deterministic scheduler \sigma_{\mathsf{d}} that alternates between \pi_{1} and \pi_{2} : at odd time steps, the robot follows \pi_{1} , and at even time steps, it follows \pi_{2} . The composition does not satisfy either objective. For example, the path starting from t_{2} forever alternates between t_{1} and t_{2} . Notably, \sigma_{\mathsf{d}} fulfills the extreme fairness property [ 25 ] , because each agent is given control infinitely often. The example shows that in order to guarantee that all objectives are satisfied, our framework requires schedulers with an even stronger form of fairness. Now consider a stochastic scheduler \sigma_{\mathsf{s}} that, at each point in time, chooses which policy to follow uniformly at random. This scheduler fulfills a stronger notion of fairness, called probabilistic fairness [ 12 ] (also related to \alpha -fairness [ 26 ] ). The composition of \pi_{1} and \pi_{2} using \sigma_{\mathsf{s}} now generates a random path that almost surely visits each of \ell,t_{1},t_{2} , and r infinitely often, thus both objectives are satisfied almost surely. ∎ We postpone the justification of our design choices of schedulers and policies until the end of the introduction. The advantages of our new framework stem from its modularity; it enables a separation of concerns in designing policies and allows changing, deleting, or adding any number of policies without any extra computational overhead, offering a lightweight, plug-and-play composition operation. We point out specific advantages over the monolithic approach: (i) parallel design : each policy is designed independently, which enables, for example, designed on separate CPUs to increase scalability, or by different vendors increasing flexible design; (ii) robustness : when an objective changes, only the relevant module needs to change and the other modules can stay fixed; (iii) iterative design : a realistic design procedure often requires addition of objectives to the original objectives, which can be simply added as a new module; (iv) dynamic changes : our framework allows deleting or adding objectives to a system that has already been deployed (a “patch”). The first step of our decoupled synthesis addresses the safety components of the individual objectives. Given a graph G and an objective \varphi , we can use standard procedure to decompose \varphi into safety and liveness components, writing \varphi=\varphi^{\mathsf{safe}}\cap\varphi^{\mathsf{live}} , where \varphi^{\mathsf{safe}} requires some unsafe vertices to be avoided at all time, and \varphi^{\mathsf{live}} requires some good event to eventually occur. We show that \varphi^{\mathsf{safe}} cannot, in general, be guaranteed under stochastic scheduling without additional communication. To this end, we propose a protocol in which agents communicate their sets of safe actions at each step, and the scheduled agent is required to select an action from the intersection of these sets. Under mild assumptions, we prove that this protocol suffices to ensure satisfaction of each safety objective at all times. Once safety is enforced, we remove all unsafe edges from the graph and exclusively focus on the liveness objectives in the resulting subgraph. For clarity of exposition, we assume this graph is strongly connected, although this assumption is not essential and will be relaxed later. We first study the existence of a stochastic scheduler