Paper deep dive
Model Predictive Supervisory Control for Hierarchical and Distributed UAS Traffic Management
Matheus P. Loures, Guilherme V. Raffo, Patrícia N. Pena
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 8/20/2026, 3:44:18 AM
Summary
This paper proposes a hierarchical Model Predictive Supervisory Control (MPSC) framework for Urban Unmanned Aircraft System Traffic Management (UTM). The framework integrates Supervisory Control Theory (SCT) for safety enforcement with Model Predictive Control (MPC) for cost-optimal decision-making. It utilizes scalable supervisor templates and automata-based prediction models to enable distributed execution for multi-agent systems, ensuring conflict-free routing and resource exclusivity in dense urban airspace.
Entities (7)
Relation Signals (6)
MPSC → appliedto → UTM
confidence 95% · Using this framework, this work develops an urban Unmanned aircraft system Traffic Management (UTM) model.
MPSC → integrates → SCT
confidence 95% · MPSC integrates receding-horizon cost-optimal control with Supervisory control theory (SCT) based supervision
MPSC → uses → MILP
confidence 92% · This work integrates DES-based supervisory restrictions, receding-horizon decision-making, and MILP-based MPSC
SCT → enforces → Safety
confidence 90% · SCT based supervision that enforces safety, nonblockingness, and resource exclusivity.
DES → representedby → Automaton
confidence 90% · Deterministic finite automata (DFA) represent DES as G=(Q,Σ,δ,q0,Qm)
MPSC → enables → distributed execution
confidence 88% · Scalability arises from hierarchical and scalable supervisor and automaton templates, enabling distributed execution without monolithic synthesis.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:This work proposes a hierarchical Model Predictive Supervisory Control (MPSC) framework for multi-agent systems with shared resources. MPSC integrates receding-horizon cost-optimal control with Supervisory control theory (SCT) based supervision that enforces safety, nonblockingness, and resource exclusivity. Scalability arises from hierarchical and scalable supervisor and automaton templates, enabling distributed execution without monolithic synthesis. Using this framework, this work develops an urban Unmanned aircraft system Traffic Management (UTM) model. The model supports pickup-and-delivery missions under time-varying demand efficiently.
Tags
Links
- Source: https://arxiv.org/abs/2608.18353v1
- Canonical: https://arxiv.org/abs/2608.18353v1
Trouble viewing inline? Open PDF directly →
Full Text
37,469 characters extracted from source content.
Expand or collapse full text
Model Predictive Supervisory Control for Hierarchical and Distributed UAS Traffic Management footnoteinfoThis study was supported in part by the Brazilian agencies CAPES through the Academic Excellence Program (PROEX) – Finance Code 001, CNPq under grants 317058/2023-1 and 422143/2023-5, FAPEMIG under fellowship APQ-06580-24, and in part by Petrobras/ANP under Grants 2023/00494-5 and 2023/00643-0. Matheus P. Loures Guilherme V. Raffo Patrícia N. Pena Address: Graduate Program in Electrical Engineering, Universidade Federal de Minas Gerais, Belo Horizonte, MG, Brazil mploures,raffo,ppena@ufmg.br Address: Department of Electronics Engineering, Universidade Federal de Minas Gerais, Belo Horizonte, MG, Brazil Abstract This work proposes a hierarchical Model Predictive Supervisory Control (MPSC) framework for multi-agent systems with shared resources. MPSC integrates receding-horizon cost-optimal control with Supervisory control theory (SCT) based supervision that enforces safety, nonblockingness, and resource exclusivity. Scalability arises from hierarchical and scalable supervisor and automaton templates, enabling distributed execution without monolithic synthesis. Using this framework, this work develops an urban Unmanned aircraft system Traffic Management (UTM) model. The model supports pickup-and-delivery missions under time-varying demand efficiently. keywords Model Predictive Supervisory Control, Multi-Agent Systems, Localized Supervisor, UTM 1 Introduction The popularization of unmanned aerial vehicles (UAVs) has expanded beyond military and academic niches into everyday services, such as logistics, critical infrastructure inspection, environmental monitoring, and urban public services. The shared low-altitude airspace, however, constitutes a physical bottleneck. Consequently, Unmanned Aircraft Systems Traffic Management (UTM) requires conflict-free routing, time-constrained scheduling, ad hoc communication, distributed decision-making, and autonomous fault response. Several global UTM initiatives emphasize dynamic authorization, robust communication, and real-time fleet monitoring. Examples include NASA’s U.S. trials (2), Europe’s U-space framework for very-low-level (VLL) operations (22), China’s low-altitude route networks (24), and India’s Digital Sky (25). In Brazil, VLL airspace (60–150 m) is under full state sovereignty, with geofences representing no-fly zones and safe routes (18). However, advanced UTM development remains crucial for safely carrying out complex operations within this space. Dense urban UTM operations require formal coordination methods capable of representing multi-agent interactions, shared resources, and operational constraints. Supervisory control theory (SCT) provides a formal basis for synthesizing minimally restrictive supervisors that regulate discrete-event systems (DES). It achieves this by disabling a subset of events to satisfy formal specifications, thereby ensuring critical properties like nonblocking behavior and controllability (20). Prior SCT-based studies have addressed multi-agent coordination through distributed motion control (21), scalable swarm robotics (15), and hierarchical safe navigation (7; 23). Recent work has also combined SCT with model-predictive and multi-objective scheduling mechanisms for real-time UAV coordination (16). Building on this foundation, this paper proposes a hierarchical UTM framework structured around a model predictive supervisory control (MPSC) process, in which UTM-level supervisory restrictions define admissible airspace behaviors and UAV-level predictive optimization selects feasible local actions. This work integrates DES-based supervisory restrictions, receding-horizon decision-making, and MILP-based MPSC within a hierarchical UTM architecture for multi-UAV coordination, so that optimization is performed only over behaviors admitted by the supervisory control layer. 2 Preliminaries This section introduces the fundamental concepts of DES and SCT that underpin our methodology, along with the automata-based prediction model representation used in the MPSC. 2.1 Discrete Event Systems and Supervisory Control Discrete Event Systems (DES) are dynamic systems where state changes through instantaneous event-driven transitions, suitable for sequencing and synchronization (6). An alphabet Σ is a finite set of symbols. A string is a finite sequence of events, and the set of all possible sequences forms the Kleene closure Σ∗ ^*. A language is any subset of Σ∗ ^*. Deterministic finite automata (DFA) represent DES as G=(Q,Σ,δ,q0,Qm)G=(Q, ,δ,q_0,Q_m): Q is the set of states, δ:Q×Σ→Qδ:Q× → Q is the transition function, q0q_0 is the initial state, and QmQ_m is the set of marked states. The extended transition function δ:Q×Σ∗→Qδ:Q× → Q satisfies δ(q,σs)=q′δ(q,σ s)=q given δ(q,σ)=q1δ(q,σ)=q_1 and δ(q1,s)=q′δ(q_1,s)=q . Generated language ℒ(G)=s∈Σ∗∣δ(q0,s)∈QL(G)=\s∈ δ(q_0,s)∈ Q\ and marked language ℒm(G)=s∈Σ∗∣δ(q,s)∈QmL_m(G)=\s∈ δ(q,s)∈ Q_m\ describe the system’s behavior.The parallel composition of two automata G1||G2G_1||G_2 produces a third DFA that synchronizes the behaviors of G1G_1 and G2G_2 in the common events. To incorporate performance criteria, a DFA is extended to a multi-weighted automaton based on (8). Definition 1 (16) A multi-weighted automaton G=(Q,Σ,δ,q0,Qm,W)G=(Q, ,δ,q_0,Q_m,W) is a DFA with W:Q→ℝkW:Q ^k that assigns a k-dimensional cost vector to each state. 2.2 Supervisory Control and Scalability Supervisory control theory (SCT) guarantees safe DES operation by modeling the plant G with event set Σ=Σc∪Σuc = _c∪ _uc (controllable and uncontrollable events). The plant is composed with a specification E to obtain the desired behavior K=ℒm(G∥E)K=L_m(G E). If enforcing K would disable uncontrollable events, the supervisor instead implements the supremal controllable and nonblocking sublanguage Sup(K,G)Sup\,C(K,G). For large multi-agent systems, monolithic supervisor synthesis becomes computationally prohibitive because the state space grows combinatorially with the number of agents. This work adopts the scalable approach of 14, which exploits structural symmetry among groups of identical agents. A relabeling map R:Σ→TR: → T abstracts each group iG_i of nin_i identical agents into a single template generator iH_i. Supervisory synthesis is performed on these template generators rather than on the full synchronous product. Under standard assumptions (disjoint agent event sets, relabeling-invariant specification, etc.), the resulting supervisor is nonblocking, and its state size and synthesis cost are independent of the agent population sizes nin_i. 2.3 Automata-Based Prediction Model Model predictive control is founded on the integration of optimization techniques with control theory, wherein a finite-horizon optimal control problem is solved at each time step to enforce system constraints and minimize a defined cost functional (5). In this work, we propose a model predictive supervisory control which extends this concept to DES by using the supervisor’s behavior as the predictive model in the receding-horizon scheme. To support this formulation, a matrix encoding for graphs and automata is adopted, inspired by exact representations such as MILP-based DES scheduling (12), state-equation modeling (11), and classical determinant-based graph theory (10). A DFA with n states and m events is then represented by three binary matrices capturing its transition structure: • Adjacency matrix A∈0,1n×nA∈\0,1\^n× n: Ai,j=1A_i,j=1 if state qjq_j is reachable from qiq_i by any event; • Event reachability matrix B∈0,1m×nB∈\0,1\^m× n: Be,j=1B_e,j=1 if state qjq_j can be reached by event σe _e from any state; • Event availability matrix C∈0,1n×mC∈\0,1\^n× m: Ci,e=1C_i,e=1 if event σe _e is enabled at state qiq_i. States and events are represented using one-hot encoding: x∈0,1nx∈\0,1\^n for states and u∈0,1mu∈\0,1\^m for events, where exactly one component is active (⊤x=11 x=1 and ⊤u=11 u=1). Given the current state xt∈0,1nx_t∈\0,1\^n and the applied event ut∈0,1mu_t∈\0,1\^m at time t, the DFA dynamics are captured algebraically by the state transition model xt+1=(Axt)⊙(But),x_t+1= (A\,x_t ) (B\,u_t ), (1) where ⊙ denotes Hadamard (element-wise) multiplication (17). The resulting vector xt+1x_t+1 is the unique state satisfying both reachability constraints simultaneously. The correctness of this algebraic transition relies on a property formalized as follows. The matrices A,B,CA,B,C represent a deterministic automaton G if each state-event pair (xt,ut)(x_t,u_t) yields at most one successor state. Algebraically, this condition is expressed as (A⋅B⊤)⊙C=C. (A· B ) C=C. 0011αβ A=(0110),B=(0110),C=(1001) A= pmatrix0&1\\ 1&0 pmatrix,\;B= pmatrix0&1\\ 1&0 pmatrix,\;C= pmatrix1&0\\ 0&1 pmatrix Figure 1: Example 1: automaton G and the matrices A, B, and C. Example 1 Consider the automaton in Fig. 1. Its algebraic representation follows (1) with matrices A, B, C given in (). Applying (1) with xt=(10)Tx_t=(1 0)^T and ut=(10)Tu_t=(1 0)^Tyields xt+1=(0110)(10)⊙(0110)(10)=(01)⊙(01)=(01).x_t+1= pmatrix0&1\\ 1&0 pmatrix\, pmatrix1\\ 0 pmatrix pmatrix0&1\\ 1&0 pmatrix\, pmatrix1\\ 0 pmatrix= pmatrix0\\ 1 pmatrix pmatrix0\\ 1 pmatrix= pmatrix0\\ 1 pmatrix. (2) 3 Problem Statement This section formalizes the UTM problem as a hierarchical multi-agent coordination challenge in a constrained urban airspace. The objective is to efficiently coordinate a fleet of UAVs to successfully execute assigned delivery tasks while simultaneously respecting safety, capacity, and regulatory constraints. The resulting formulation is designed to prioritize scalability, adaptability, and operational compliance in dense environments. The urban airspace setting is characterized by three entities: • UAV Fleet U: A set of UAVs, where i∈i , are tasked with performing missions. Each UAV is modeled as a weighted automaton (Def. 1) Gi=(Qi,Σi,δi,q0i,Qmi,Wi),G_i=(Q_i, _i, _i,q_0_i,Q_m_i,W_i), (3) where WiW_i assigns energy, time, and penalty weights used later by the MPSC optimization process; • Multilayer Airspace: the environment is represented as a directed multigraph. Vertices comprise special nodes (vertiports, suppliers, clients, charging stations) and logical nodes (intermediate routing points). Logical nodes carry a physical position (x,y,z)(x,y,z) and may share (x,y)(x,y) while differing in altitude, representing different layers. Each airway is modeled as a non-directed edge whose operational direction is assigned at runtime (13). • UTM: A global discrete-event controller responsible for enforcing shared-resource and regulatory constraints. It actively prevents edge/vertex conflicts, maintains online geofences, and regulates fleet-level access to the airspace through a set of supervisory automata. The multi-agent coordination problem requires event sequences that complete all missions subject to battery, workflow, communication, and global airspace safety constraints. A hierarchical solution separates the UAV layer, where agents execute controllable events (edge acquisition, task execution, charging) based on their weighted automata, from the UTM layer, which tracks the fleet configuration, computes prohibited transitions, and enforces geofencing and mutex constraints on shared vertices and edges. A bidirectional interface enables UAVs to send edge requests and state updates while the UTM returns disabled-event sets, yielding scalable, safe, regulation-compliant multi-UAV operation. 4 Model Predictive Supervisory Control Focusing on large multi-agent systems, this section presents a hierarchical and scalable model predictive supervisory control design for coordination. The framework achieves a comprehensive mathematical formulation by integrating receding-horizon optimal control problem with scalable solution methods. 4.1 Multilayer Airspace Modeling The urban low-altitude airspace is modeled as a multilayer multigraph ℳ=(,)M=(V,A) whose layers ℓ∈ℒ represent altitude bands (13). Nodes are either special SV_S (mission locations) or logical LV_L (navigation waypoints, each with horizontal coordinates and a layer; distinct logical nodes may share horizontal coordinates across layers). Undirected corridors connect nodes within or between layers; special nodes are linked only through logical nodes. The admissible corridor set =SL∪LL∪VA=A_SL _L _V consists of special-to-logical corridors, logical-to-logical corridors that replicate a base-layer pattern, and vertical corridors connecting logical nodes with the same horizontal coordinates in different layers. No two corridors intersect except at shared endpoints. Figure 2: Hierarchical and scalable supervisory architecture. Example 2 A minimal delivery scenario is used to illustrate the framework. The environment contains the special nodes S=V,S,C,EV_S=\V,S,C,E\, which represent a vertiport (V), a supplier (S), a client (C), and a charging station (E), respectively. These are connected through a single logical node L=LV_L=\L\, considering only a single layer (L=1L=1). This setting is shown in Fig. 3. Figure 3: Single layer representation of the delivery scenario. 4.2 Hierarchical & Scalable Supervisory Control Architecture The proposed hierarchical MPSC framework couples SCT-based admissibility with MILP-based receding-horizon optimization, addressing the state-space explosion of multi-agent supervisory control. The UTM supervisory layer enforces global admissibility by modeling shared airspace as a DES resource-allocation problem. A class-level supervisor template, a DFA over a generic alphabet encoding the admissible behavior shared by all UAVs of the same class, is synthesized once for a representative UAV model and instantiated for each vehicle via event relabeling (14; 4; 7), yielding indexed instances with vehicle-specific event labels. Using relabeled events, the UTM maintains a global view of vertex occupancy, corridor availability, directional flow, vertical access, and dynamic geofences, and computes a prohibited-event set P that disables movements violating mutual exclusion, geofencing, direction rules, or shared-resource constraints. The UAV decision layer receives P and solves a finite-horizon MPSC problem within its relabeled supervisor’s reachable sub-automaton, selecting a cost-minimizing sequence over mission progress, travel, energy, waiting, charging, and return-to-base behavior. Only the first event is executed, after which the optimization is repeated from the updated state in a receding-horizon manner. This separation defines the hierarchy: each UAV makes autonomous, locally cost-optimal decisions strictly within the admissible set enforced by the UTM. SCT guarantees language-level safety and nonblockingness, while MPSC supplies online cost optimization. Under synchronized state updates, every executed event satisfies both the supervised language and current global restrictions. Assuming that the supervisors are controllable and nonblocking, P is synchronized across UAVs, and each UAV executes only events permitted by its supervisor and not in P, every executed sequence remains in the admissible supervised language and respects the UTM’s mutual-exclusion and geofencing constraints. This property follows from the fact that the MPSC optimization is restricted to the event set admitted by the SCT supervisor after applying the prohibitions imposed by the UTM coordination layer. Therefore, optimization affects only the selection among admissible behaviors and does not alter the supervisory safety constraints. 4.3 UAV DES Models and Formal Specifications The UAV decision-making framework derives its alphabet directly from the multilayer airspace graph: each directed edge yields acquisition and release symbols for movement rights, while additional symbols capture task actions (pickup, delivery, charging), as well as global functions such as task acceptance, mission completion, and battery reporting. From this alphabet, plant automata are built to reflect operational capabilities: a movement automaton models stationary/transit alternation, edge-resource plants regulate traversal direction, an operational-mode plant encodes mission activities (servicing, delivery, charging), and auxiliary automata handle communication, liveness, and battery monitoring. Because the DES structure originates from the airspace graph, the number of events and automata grows with the vertices, corridors, layers, and resources; each corridor adds acquisition and release events, and each additional layer expands admissible movement and edge constraints. Example 3 For the system model in Example 2, the UAV automata (Fig. 4) operate over alphabet ΣUAV _UAV containing corridor acquisition and release events tuvt_uv, ruvr_uv; service events swS,ewS,swC,ewCsw_S,ew_S,sw_C,ew_C; charging events scE,ecEsc_E,ec_E; and auxiliary events ac,ft,hb,lbac,ft,hb,lb for task acceptance, heartbeat, and battery monitoring. qidleq_idleqmovq_movtVL,tLV,tSL,tLS,tCL,tLC,tEL,tLEt_VL,t_LV,t_SL,t_LS,t_CL,t_LC,t_EL,t_LErVL,rLV,rSL,rLS,rCL,rLC,rEL,rLEr_VL,r_LV,r_SL,r_LS,r_CL,r_LC,r_EL,r_LE (a) qfreeq_freeqocc+q_occ^+qocc−q_occ^-tuvt_uvruvr_uvtvut_vurvur_vu (b) qbaseq_baseqplaceq_placeqpickq_pickqloadq_loadswSsw_SewSew_SswCsw_CewCew_CscEsc_EecEec_E (c) qcomq_comac,ftac,ft (d) qliveq_livehbhb (e) qpwrq_pwrlblb (f) Figure 4: UAV subplants Formal specifications restrict UAV behavior to ensure safety, task correctness, and airspace compliance. The map-navigation specification (Fig. 5(a)) encodes multilayer topology by allowing only transitions along reachable corridors. Workflow specifications (Fig. 5(b)) enforce the high-level mission sequence and prevent unsafe or premature transitions. Battery specifications (Fig. 5(c)) impose energy-aware operation by restricting motion under low-energy conditions. Location–task specifications (Fig. 5(d), 5(e), 5(f)) guarantee that service and charging actions occur exclusively when the UAV is at the corresponding functional node. Together, these components yield a complete DES formulation of the scenario. qVq_VqSq_SqLq_LqCq_CqEq_EtVLt_VLtLVt_LVtLCt_LCtCLt_CLtLSt_LStSLt_SLtLEt_LEtELt_EL (a) qpickq_pickqplaceq_placeqbaseq_baseswSsw_StLVt_LVswCsw_C (b) qOKq_OKqLOWq_LOWlblbscEsc_E (c) qoutSq_out_SqinSq_in_StLSt_LStSLt_SLswSsw_S (d) qoutCq_out_CqinCq_in_CtLCt_LCtSLt_SLswCsw_C (e) qoutEq_out_EqinEq_in_EtLEt_LEtELt_ELscEsc_E (f) Figure 5: UAV specifications Building upon these generic models, a monolithic supervisor genericS_generic was synthesized for a single agent. This supervisor encodes the safe behavior of a UAV operating within the modeled logical network. To address the scalability challenges inherent in multi-agent discrete-event systems, this generic supervisor serves as a template that can be specialized for each UAV, i∈i by duplicating the automata and adding indices to the agent’s events. 4.4 UTM Models The UTM layer is modeled as a scalable supervisor whose plants reuse the UAV’s map and motion automata together with a vertex-blocking plant, while specifications enforce vertex blocking and edge mutual exclusion. The synthesized supervisor provides dynamic geofencing, corridor directionality enforcement, and shared-resource arbitration across the fleet. Its state-space size grows with the airspace graph (vertices, corridors, layers) but, due to relabeling and template instantiation, remains independent of the number of UAVs. New tasks are assigned to the first available, charged UAV. Example 4 For the scenario of Example 2, the UTM alphabet is ΣUTM _UTM, containing all corridor events tuvt_uv and vertex-blocking events bu,ubub_u,ub_u. Its plants are the map automaton (Fig. 5(a)), the directional edge-usage automaton (Fig. ), and a geofence plant (Fig. ) that generates blocking events. For each vertex, a specification Eblock,iE_block,i (e.g., Fig. ) disables incoming corridor events after the corresponding blocking event; a mutex specification Emutex,iE_mutex,i (e.g., Fig. ) ensures a vertex, once entered, remains occupied until a departure event occurs. qblkq_blkbS,ubS,bC,ubC,bE,ubE,bL,ubL,bV,ubV matrixb_S,ub_S,b_C,ub_C,b_E,\\ ub_E,b_L,ub_L,b_V,ub_V matrix (a) qubLq_ub_LqbLq_b_LbLb_LubLub_LtVL,tSL,tCL,tELt_VL,t_SL,t_CL,t_EL (b) qLfreeq_L_freeqLoccq_L_occtVL,tSL,tCL,tELt_VL,t_SL,t_CL,t_ELtLV,tLS,tLC,tLEt_LV,t_LS,t_LC,t_LE (c) Figure 6: Example 4: (a) Plant with vertex blocking related events; (b) Block vertex; (c) Mutual exclusion. The UTM tracks each UAV’s state within UTMS_UTM individually, avoiding an explicit synchronous product. Agent-specific events update only that UAV’s state, while geofencing events bub_u, ubuub_u are applied to all states simultaneously. From the combined disabled transitions, the UTM computes the prohibited-event set P of all tuvt_uv that would violate mutex, geofencing, or shared-resource constraints, and broadcasts it so that each MPSC controller restricts its optimization to P, ensuring decentralized, conflict-free coordination. 4.5 MILP Formulation for MPSC When a new task is issued, it is assigned to a single UAV, which generates its corresponding desired event set ℐI. This set is composed of events related to the accomplishment of tasks. The UAV must solve an MPSC optimization problem to determine how to execute the task. Prior to optimization, each state of each plant and specification automaton of the UAV has a cost vector assigned; these atomic cost components are then algebraically lifted to the supervisor level (16). A state-dependent sub-automaton is extracted around the UAV’s current supervisor state using a receding horizon of length H. On this structure, a Mixed-Integer Linear Program is formulated. The MILP selects the next event by minimizing operational cost while maximizing incentives associated with the desired event set ℐI. The proposed MILP is posed as follows: min αS∑t=0H−1⊤xt−βI∑i∈ℐ∑t=0H−1(H−t)ut,i _S\, _t=0^H-1w x_t\;-\; _I _i _t=0^H-1(H-t)\,u_t,i (4) s.t. x0=q0 x_0=q_0 (5) xt+1=(Axt)⊙(But) x_t+1=(Ax_t) (Bu_t) ∀t ∀ t (6) |Q|⊤xt=1 1_|Q| x_t=1 ∀t ∀ t (7) |Σ|⊤ut=1 1_| | u_t=1 ∀t ∀ t (8) |Σ|⊤(Cxt⊙ut)=1 1_| | (Cx_t u_t )=1 ∀t ∀ t (9) ut,i=0 u_t,i=0 i∈,∀t i ,\;∀ t (10) xt∈0,1|Q|,ut∈0,1|Σ| x_t∈\0,1\^|Q|, u_t∈\0,1\^| | ∀t ∀ t (11) with H being the prediction horizon, xt∈0,1|Q|x_t∈\0,1\^|Q| the state vector, ut∈0,1|Σ|u_t∈\0,1\^| | the event vector, q0q_0 the initial state at time t=0t=0, ℐI the desired event set, P the set of prohibited events, w the aggregated operational cost in state xtx_t, and αS _S and βI _I the optimization weights for operational cost and incentive term, respectively. The MILP minimizes a multi-objective cost function (4), which balances operational costs against an incentive for desirable events. The solution is constrained by the DES algebraic framework, incorporating: initial state fixation (5), automaton dynamics (6), state and event one-hot encoding (7)–(8), event feasibility via matrix C (9), and supervisory prohibitions (10). This receding-horizon formulation operates cyclically: it first generates a depth-H sub-automaton via Breadth-First Search (BFS) (3). It then applies a structural correction step to ensure the resulting sub-automaton satisfies the determinism requirement of Definition 2.3. Subsequently, the MILP problem is solved using the matrices A, B, and C from the sub-automaton, executing only the first optimal event u0⋆u_0 , updating the state to xt+1x_t+1, and repeating the entire procedure at the next iteration. 5 Case Study: Structured Urban Airspace To validate the proposed Hierarchical MPSC architecture, two experiments were executed within a ROS 2/Gazebo framework (19).11 1 For access to the complete and functional code, please visit the project’s GitHub repository: https://github.com/lacsed/MPSC-Hierarchical-UTM.git The implementation employed a multi-process simulation architecture that leveraged the Python.NET bridge to execute the UltraDES .NET library (1) for supervisory control design, while the optimization layer utilized the Gurobi solver (9). The case studies feature structured urban airspaces represented by planar H/V graphs with logical corridors and specialized service nodes. Scenario R1 contains 9 graph nodes, 15 air corridors, 1 vertiport, 1 charging station, 1 supplier, and 2 clients, executed with N=2N=2 UAVs. Scenario R2 contains 19 graph nodes, 34 air corridors, 1 vertiport, 1 charging station, 2 suppliers, and 3 clients, executed with N=4N=4 UAVs across two movement layers, and extends the running example (Examples 1, 2, 3, and 4) by augmenting the topology and fleet size. For each scenario, the UAV model instantiates GmoveG_move, directional edge‑usage plants, GmodesG_modes, and the auxiliary plants GcomG_com, GliveG_live, and GbatG_bat. Specifications comprise EmapE_map, EWFE_WF, EbatE_bat, and location–task specifications Eloc,iE_loc,i for the specialized nodes in SV_S. (a) R1 (b) R2 Color Meaning Gray Logical node Red Vertiport Blue Charging station Green Supplier Orange Client Figure 7: Urban airspace topology for scenarios R1 and R2. A monolithic supervisor is synthesized for the generic UAV model and is replicated through event relabeling. State‑cost vectors are computed offline after synthesis, each state receiving an atomic cost triple (E,Tf,D)(E,T_f,D) for energy, traversal time, and task incentives. The UTM model contains the global map, resource constraints, geofencing vertex‑blocking specifications, and vertex‑mutex specifications, as detailed in Section 4.4. Disabled UTM events are communicated to the fleet through the prohibited‑event set P, whereas geofencing events bub_u and ubuub_u are applied synchronously as they modify global admissibility. Table 1: DES metrics for R1. Metric Hierarchical Centralized exact Supervisor states 570 444,816 Supervisor transitions 1,676 3,828,328 Centralized synthesis time (s) – 117.70 Table 1 quantifies the reduction in supervisor size achieved by the hierarchical DES formulation for R1. The hierarchical supervisor reduces the number of states by ∼780× 780× and the number of transitions by a ∼2300 2300 compared to the centralized supervisor. This reduction directly lowers memory requirements and simplifies depth‑first search traversal during online optimization. The centralized synthesis time of 117.70 seconds, even for the smaller R1 scenario, indicates that the monolithic approach becomes infeasible as the map size and the number of UAVs increase. The proposed solution avoids this limitation, bypassing the combinatorial explosion in monolithic DES coordination through a hierarchical approach. Table 2: Experimental metrics. Metric R1 R2 UAVs / nodes / corridors 2 / 9 / 30 4 / 19 / 68 Completed / assigned missions 4 / 4 5 / 6 Mean mission time (s) 69.11 44.42 Maximum mission time (s) 84.42 53.25 Throughput (missions/min) 1.29 2.46 Accepted UTM grants 32 205 Prohibited events: mean / max 7.03 / 12 19.28 / 27 The metrics in Table 2 demonstrate that the hierarchical architecture maintains efficient operation despite the increased complexity. Mean mission time decreases from 69.11 seconds in R1 to 44.42 seconds in R2, while throughput rises from 1.29 to 2.46 missions per minute. Accepted UTM grants increase from 32 to 205, confirming higher service capacity. Although the mean number of prohibited events grows from 7.03 to 19.28, indicating more active constraint enforcement, mission execution times remain bounded and conflict-free coordination is preserved. This behavior stems from the separation between local predictive decision-making and global supervisory restriction: each UAV solves its own MPSC problem, and the UTM layer communicates only the prohibited-event set required to maintain global admissibility. From the ROS implementation perspective, dedicated nodes were implemented for UTM supervision, UAV execution, mission publication, and task allocation. The UTM node receives discrete events from the fleet, updates the global supervisory state, and broadcasts the prohibited‑event set P. Each UAV node executes a local MPSC loop, interprets admissible events according to the current task and battery condition, and publishes the selected controllable event. Mission management nodes publish delivery requests and coordinate distributed task claiming, avoiding a centralized motion planner. Communication among these nodes was realized through the following ROS topics: • /event: System-wide discrete event communication • /task_todo: Administrative task publication • /task: Fleet-wide task allocation • /prohibited_events: UTM global constraint broadcast • /task_claims: Distributed task claiming This node‑topic organization separates continuous vehicle execution, discrete‑event supervision, and mission allocation. Consequently, each UAV solves its local MPSC problem independently, while the UTM layer preserves global admissibility by broadcasting only the prohibitions required to prevent conflicts, enforce geofencing, and maintain mutual exclusion over shared airspace resources. 6 Conclusion This paper introduced a novel Hierarchical MPSC framework that integrates SCT guarantees with MPC optimization, ensuring collision-free operation and computational tractability for large UAV fleets. The system demonstrated dynamic task allocation and real-time constraint enforcement, confirming suitability for urban air mobility. Future work will extend cost adaptation to the central UTM coordinator, investigate distributed multi-agent coordination, develop map-agnostic decision abstraction, create a federated UTM architecture for metropolitan-scale traffic, and design a UTM task-assignment policy that accounts for UAV characteristics such as battery state and position. Moreover, future work will address the systematic assignment of cost vectors to states and specifications, the treatment of critical low-battery scenarios, and the prioritization of battery constraints over non-critical tasks. References Alves and Pena (2023) L. V. Alves and P. N. Pena Ultrades project-a multiplatform discrete event systems tool. IFAC-PapersOnLine 56 (2), p. 6081–6086. Cited by: §5. Aweiss et al. (2018) A. S. Aweiss, B. D. Owens, J. Rios, J. R. Homola, and C. P. Mohlenbrink Unmanned aircraft systems (uas) traffic management (utm) national campaign i. In 2018 AIAA Information Systems-AIAA Infotech@ Aerospace, p. 1727. Cited by: §1. Bundy and Wallen (1984) A. Bundy and L. Wallen Breadth-first search. In Catalogue of artificial intelligence tools, p. 13–13. Cited by: §4.5. Cai and Wonham (2010) K. Cai and W. M. Wonham Supervisor localization: a top-down approach to distributed control of discrete-event systems. IEEE Transactions on Automatic Control 55 (3), p. 605–618. Cited by: §4.2. Camacho and Bordons (2007) E. Camacho and C. Bordons Model predictive control. Springer. Cited by: §2.3. Cassandras and Lafortune (2008) C. G. Cassandras and S. Lafortune Introduction to discrete event systems. Springer. Cited by: §2.1. Dulce-Galindo et al. (2022) J. Dulce-Galindo, M. A. Santos, G. V. Raffo, and P. N. Pena Distributed supervisory control for multiple robot autonomous navigation performing single-robot tasks. Mechatronics 86, p. 102848. Cited by: §1, §4.2. Fahrenberg et al. (2011) U. Fahrenberg, L. Juhl, K. G. Larsen, and J. Srba Energy games in multiweighted automata. In Theoretical Aspects of Computing – ICTAC 2011, p. 95–115. External Links: ISBN 978-3-642-23283-1 Cited by: §2.1. Gurobi Optimization (2023) L. Gurobi Optimization Gurobi optimizer reference manual, 2023. Cited by: §5. Harary (1962) F. Harary The determinant of the adjacency matrix of a graph. Siam Review 4 (3), p. 202–210. Cited by: §2.3. Kobayashi and Imura (2012) K. Kobayashi and J. Imura Deterministic finite automata representation for model predictive control of hybrid systems. Journal of Process Control 22 (9), p. 1670–1680. Cited by: §2.3. Kobetski and Fabian (2006) A. Kobetski and M. Fabian Scheduling of discrete event systems using mixed integer linear programming. In 2006 8th International Workshop on Discrete Event Systems, p. 76–81. Cited by: §2.3. Labib et al. (2019) N. S. Labib, G. Danoy, J. Musial, M. R. Brust, and P. Bouvry A multilayer low-altitude airspace model for uav traffic management. In Proceedings of the 9th ACM Symposium on Design and Analysis of Intelligent Vehicular Networks and Applications, p. 57–63. Cited by: 2nd item, §4.1. Liu et al. (2019) Y. Liu, K. Cai, and Z. Li On scalable supervisory control of multi-agent discrete-event systems. Automatica 108, p. 108460. Cited by: §2.2, §4.2. Lopes et al. (2016) Y. K. Lopes, S. M. Trenkwalder, A. B. Leal, T. J. Dodd, and R. Groß Supervisory control theory applied to swarm robotics. Swarm Intelligence 10 (1), p. 65–97. Cited by: §1. Loures et al. (2025) M.P. Loures, M.A. Santos, L.C.A. Pimenta, P.N. Pena, and G.V. Raffo An adaptive approach to multi-agent coordination: leveraging supervisory control theory and mpc for real-time scheduling. IFAC-PapersOnLine 59 (20), p. 2435–2440. Note: 23th IFAC Symposium on Automatic Control in Aerospace 2025 External Links: ISSN 2405-8963 Cited by: §1, §4.5, Definition 1. Million (2007) E. Million The hadamard product. Course Notes 3 (6), p. 1–7. Cited by: §2.3. Ministério da Defesa - Comando da Aeronáutica (2020) Ministério da Defesa - Comando da Aeronáutica Aeronaves não tripuladas e o acesso ao espaço aéreo brasileiro. ICA 100-40 Departamento de Controle do Espaço Aéreo (DECEA), Brasília, Brazil. Cited by: §1. Quigley et al. (2009) M. Quigley, B. Gerkey, K. Conley, J. Faust, T. Foote, J. Leibs, R. Wheeler, A. Y. Ng, et al. ROS: an open-source robot operating system. In ICRA workshop on open source software, Vol. 3, p. 5. Cited by: §5. Ramadge and Wonham (1987) P. J. Ramadge and W. M. Wonham Supervisory control of a class of discrete event processes. SIAM journal on control and optimization 25 (1), p. 206–230. Cited by: §1. Roszkowska and Reveliotis (2013) E. Roszkowska and S. Reveliotis A distributed protocol for motion coordination in free-range vehicular systems. Automatica 49 (6), p. 1639–1653. Cited by: §1. SESAR Joint Undertaking (2016) SESAR Joint Undertaking European drones outlook study: unlocking the value for europe. Study European Union, SESAR Joint Undertaking, Brussels, Belgium. External Links: Link Cited by: §1. Vilela and Hill (2022) J. Vilela and R. Hill Hierarchical planning in a supervisory control context with compositional abstraction. Discrete Event Dynamic Systems 32 (1), p. 89–113. Cited by: §1. Xu et al. (2020) C. Xu, X. Liao, J. Tan, H. Ye, and H. Lu Recent research progress of unmanned aerial vehicle regulation policies and technologies in urban low altitude. Ieee Access 8, p. 74175–74194. Cited by: §1. Yadav et al. (2021) A. Yadav, S. Goel, B. Lohani, and S. Singh A uav traffic management system for india: requirement and preliminary analysis. Journal of the Indian Society of Remote Sensing 49 (3), p. 515–525. Cited by: §1.