Paper deep dive
HECTOR: Human-centric Hierarchical Coordination and Supervision of Robotic Fleets under Continual Temporal Tasks
Shen Wang, Yinhang Luo, Jie Li, Meng Guo
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 95%
Last extracted: 4/14/2026, 1:38:36 AM
Summary
HECTOR is a hierarchical, human-centric framework for coordinating large-scale, heterogeneous robotic fleets under continual, uncertain temporal tasks. It features a three-layer architecture: a bidirectional human-fleet interaction protocol, a rolling-horizon task assignment layer, and a local team-level coordination layer. The framework supports online mission updates (additions, cancellations, priority shifts) and uses linear temporal logic (LTL) to specify collaborative missions, improving computational efficiency and reducing operator workload in dynamic environments.
Entities (4)
Relation Signals (3)
HECTOR → coordinates → Robotic Fleet
confidence 95% · HECTOR for large-scale robotic fleets under continual and uncertain temporal tasks
Human Operator → interactswith → HECTOR
confidence 95% · bidirectional and multimodal protocol of online human-fleet interaction
HECTOR → uses → Linear Temporal Logic
confidence 95% · Collaborative missions are expressed as linear temporal logic formulas
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Robotic fleets can be extremely efficient when working concurrently and collaboratively, e.g., for delivery, surveillance, search and rescue. However, it can be demanding or even impractical for an operator to directly control each robot. Thus, autonomy of the fleet and its online interaction with the operator are both essential, particularly in dynamic and partially unknown environments. The operator might need to add new tasks, cancel some tasks, change priorities and modify planning results. How to design the procedure for these interactions and efficient algorithms to fulfill these needs have been mostly neglected in the related literature. Thus, this work proposes a human-centric coordination and supervision scheme (HECTOR) for large-scale robotic fleets under continual and uncertain temporal tasks. It consists of three hierarchical layers: (I) the bidirectional and multimodal protocol of online human-fleet interaction, where the operator interacts with and supervises the whole fleet; (II) the rolling assignment of currently-known tasks to teams within a certain horizon, and (III) the dynamic coordination within a team given the detected subtasks during online execution. The overall mission can be as general as temporal logic formulas over collaborative actions. Such hierarchical structure allows human interaction and supervision at different granularities and triggering conditions, to both improve computational efficiency and reduce human effort. Extensive human-in-the-loop simulations are performed over heterogeneous fleets under various temporal tasks and environmental uncertainties.
Tags
Links
- Source: https://arxiv.org/abs/2604.10892v1
- Canonical: https://arxiv.org/abs/2604.10892v1
Trouble viewing inline? Open PDF directly →
Full Text
124,523 characters extracted from source content.
Expand or collapse full text
HECTOR: Human-centric Hierarchical Coordination and Supervision of Robotic Fleets under Continual Temporal Tasks Shen Wang1, Yinhang Luo1, Jie Li2 and Meng Guo1 The authors are with 1 the School of Advanced Manufacturing and Robotics, Peking University, Beijing 100871, China; and 2National University of Defense Technology, Hunan 410073, China. This work was supported by the National Natural Science Foundation of China (NSFC) under grants U2241214, T2121002. Corresponding author: Meng Guo, meng.guo@pku.edu.cn. Abstract Robotic fleets can be extremely efficient when working concurrently and collaboratively, e.g., for delivery, surveillance, search and rescue. However, it can be demanding or even impractical for an operator to directly control each robot. Thus, autonomy of the fleet and its online interaction with the operator are both essential, particularly in dynamic and partially unknown environments. The operator might need to add new tasks, cancel some tasks, change priorities and modify planning results. How to design the procedure for these interactions and efficient algorithms to fulfill these needs have been mostly neglected in the related literature. Thus, this work proposes a human-centric coordination and supervision scheme (HECTOR) for large-scale robotic fleets under continual and uncertain temporal tasks. It consists of three hierarchical layers: (I) the bidirectional and multimodal protocol of online human-fleet interaction, where the operator interacts with and supervises the whole fleet; (I) the rolling assignment of currently-known tasks to teams within a certain horizon, and (I) the dynamic coordination within a team given the detected subtasks during online execution. The overall mission can be as general as temporal logic formulas over collaborative actions. Such hierarchical structure allows human interaction and supervision at different granularities and triggering conditions, to both improve computational efficiency and reduce human effort. Extensive human-in-the-loop simulations are performed over heterogeneous fleets under various temporal tasks and environmental uncertainties. Note to Practitioners This work is motivated by the practical need for an operator to coordinate a large number of heterogeneous and autonomous robots such as unmanned aerial and ground vehicles, to accomplish complex collaborative tasks such as patrol, delivery, search and rescue. Existing approaches often assume that the fleet size is relatively small, and the tasks are known beforehand, while neglecting the human interaction during online execution. This paper proposes a human-centric and hierarchical framework for online coordination and supervision of potentially dozens of robots. It allows the operator to interact online with the fleet via lean communication, e.g., to specify complex temporal missions, approve the formation of teams with assigned tasks, monitor the progress of task execution, potentially add new tasks and remove old tasks, and adjust the priority of some tasks. The hierarchical planning scheme decouples the formation of teams, the task assignment among teams and the task coordination within each team. Human-in-the-loop simulations suggest that the framework can be applied to practical relief missions after disasters, where the operator can coordinate and supervise large-scale fleets efficiently. I Introduction Figure 1: The considered scenario where a human operator coordinates, interacts, and supervises a large robotic fleet via the proposed framework. Online requests are specified via the designed interface and protocol (bottom-left), such as adding or cancelling new temporal tasks, different priorities and deadlines, or direct assignment of certain robots. The fleet reacts autonomously to fulfill different tasks at different regions, both at the global fleet-level (top) and the local team-level (bottom-right). In the simulated case, 3030 tasks and 450450 subtasks are accomplished by 8080 robots. Heterogeneous robotic fleets, combining ground and aerial vehicles, are increasingly adopted for missions that exceed the capabilities of individual robots [10, 22]. Concurrent operation improves efficiency, while collaboration enables functions such as formation, cooperative transport, and coverage [46, 42]. Despite these advantages, coordination of large fleets remains a central challenge, especially for missions with distributed subtasks requiring temporal and spatial constraints [20]. The task allocation problem grows combinatorially with fleet size and mission length [6]. Many existing approaches compute assignments offline for static task sets [38], but such assumptions are impractical for deployments where objectives evolve or are canceled in real time. Dynamic environments demand continual replanning, yet conventional methods rapidly become intractable and unstable, often leading to oscillatory allocations and degraded team performance [17]. Figure 2: The proposed human-centric framework for hierarchical coordination and supervision of robotic fleets, consisting of three main components: (I) the interaction protocol and interface for four types of online requests (left); (I) the automata-guided task assignment and team formation (middle); (I) three types of local coordination strategy for different tasks (right). Human requests, environment state and execution status are all updated online, for which adaptations for tasks and motions are triggered at different granularities and conditions. Moreover, in practice, robotic fleets rarely operate in full autonomy. As shown in Fig. 1, human operators frequently supervise high-level decision-making, including mission specification, cancellation of outdated objectives, and adjustment of task priorities [10, 7]. During execution, the operator may need to monitor mission progress, inspect robot status, reassign subtasks, or intervene under uncertainty [40]. Efficient procedures for human–fleet interaction are therefore crucial to ensure responsiveness and safety during operation. However, most existing research either emphasizes fully autonomous coordination [4] or restricts human–robot interaction to very small teams [7]. Recent efforts highlight scalable approaches to interactive fleet learning [17], but protocols and interfaces for large heterogeneous fleets under dynamic and partially unknown conditions remain largely unexplored. To address these challenges, this work introduces HECTOR, a unified framework for human-centric supervision and coordination of large-scale fleets in partially unknown and dynamic environments. Team-wise collaborative missions are specified and released online in response to observations during execution, so the distribution and requirements of tasks are revealed only at runtime. As illustrated in Fig. 2, the framework employs a hierarchical hybrid architecture with three layers: (I) a human–fleet interaction layer that converts online observations into team-wise missions; (I) a task-assignment layer that decomposes missions into collaborative tasks and allocates them to composed teams using a receding-horizon strategy; and (I) a local coordination layer that manages intra-team execution through appropriate distributed strategies. The interaction protocol supports bidirectional and multimodal requests between the operator and the fleet, including real-time visualization and supervision. Collaborative missions are expressed as linear temporal logic formulas over parameterized utility functions, providing both generality and formality in specification. The framework is fully online and adapts continuously to operator inputs, external events, and runtime observations. Its efficiency and robustness are validated through practical human-in-the-loop simulations with large heterogeneous systems. The main contributions of this work are twofold: (I) a flexible and scalable framework enabling operators to interact with and coordinate large-scale robotic fleets in uncertain and dynamic settings; and (I) explicit treatment of practical aspects such as heterogeneous capabilities, parameterized collaboration utilities, temporal task constraints, and variability in the number and distribution of subtasks. I Related Work I-A Task Planning for Robotic Fleets Task planning in robotic fleets addresses the decomposition of missions into subtasks and their allocation across robots or teams. Surveys on multi-robot task allocation (MRTA) [12, 41] have established taxonomies of problem structures, including vehicle routing, scheduling, and coalition formation [8]. Centralized optimization methods such as MILP and heuristic search [18] generate globally near-optimal solutions and allow precise encoding of resource and time constraints, but the combinatorial complexity makes them unsuitable for large fleets or missions with dynamic updates. Decentralized approaches improve scalability and resilience by distributing decision-making, such as market-based auctions [48] that trade computational effort for speed, and distributed optimization frameworks [11] that enable concurrent negotiation among agents. Approximate methods, including evolutionary algorithms [28] and genetic search [34], reduce computational overhead and can adapt to heterogeneous capabilities, but they often sacrifice guarantees of feasibility or temporal optimality. Recent efforts emphasize hierarchical decomposition and reactive coordination to improve scalability under dynamic task streams, including decomposition-based hierarchical planning [32, 25] and real-time reactive allocation under temporal logic [5]. Despite these advances, most approaches assume static and fully known tasks at the planning stage. Efficient solutions that adapt to the continual online task generation, uncertainties in subtask number and distribution, and online operator interventions remain open. I-B Complex Tasks as Temporal Logic Formulas Temporal logic has emerged as a principled way to specify robotic missions that combine safety, temporal order, and collaboration requirements. Probabilistic temporal logics (PCTL) [24] enable reasoning about uncertainty in outcomes, while LTL provides a rich language for describing sequential objectives such as repeated patrolling, collaborative capture, or persistent surveillance [20, 25, 37, 33]. Counting LTL (cLTL) [36] extends this by capturing quantitative requirements, for instance requiring a minimum number of robots at specific subtasks. Capability LTL [26, 3] address the time-dependent capabilities of robots during execution. Hierarchical LTL is proposed in [32] to further introduce structured analyses and synthesis to improve efficiency. Centralized formulations ensure completeness and optimality through sampling-based search [20], automaton–system synchronization [37], and MILP encoding of task constraints [25, 33, 36, 23], but they face double-exponential growth with task and fleet size. Decentralized methods address scalability through local coordination [27], decision trees [5], partial-order analyses [29], reactive synthesis [19], and hierarchical decoupling [31]. More recent works emphasize dynamic reactivity by combining logic specifications with scalable heuristics [25, 5, 3]. As summarized in Table I, scalability in complex missions has been addressed through mechanisms such as sampling [20], capacity-based optimization [25], counting constraints [36], decision tree [5], and flow-based construction [14]. Nevertheless, most aforementioned work overlook the online interaction with human operators, and different types of local tasks contained within the temporal mission, which in itself requires coordination and adaptation. Such nested coordination raises key challenges in retaining tractable computational complexity while enabling coherent adaptation across multiple spatial, temporal and organizational scales. As the most relevant to this work, HULK [30] facilitates continual task planning by modeling missions constraints as posets. However, this approach necessitates reconstruction whenever missions are modified online, limiting its online responsiveness. Furthermore, it fails to account for the interplay between high-level coordination and low-level motion feasibility, as well as the integration of human supervision during execution. The proposed method addresses these shortcomings by incorporating a human interaction protocol and an online adaptation algorithm, further integrating dynamic constraints into motion feasibility. Additionally, it enhances computational efficiency by eliminating the need for poset reconstruction and employing an automata-guided search instead. TABLE I: Comparison with Related Work Method Task Specification Online Task Uncertain/ Unknown Subtasks Human Interaction Dynamic Constraints Local Coordination STyLuS* [20] LTL × × × √ × ScRATCHeS [25] CaTL × × × √ × DecTree [5] LTL √ √ × × × cLTL++ [36] cLTL × × × √ × HieraTL [31] hLTL √ √ × × × Flow-based [14] Ordered × √ × × × HULK [30] LTL √ √ × √ √ HECTOR (Ours) LTL √ √ √ √ √ I-C Human-fleet Interaction Beyond automated task planning, effective human-swarm collaboration under uncertainty remains a central bottleneck, especially in deciding when and how operators should validate and intervene online [10, 7]. In practice, no universal metric reliably predicts whether an autonomous plan will remain operationally sound once execution begins, so human expertise is essential for validating reasoning quality and mission viability. Human–swarm interaction emphasizes interface design, situational awareness, and scalable mechanisms for directing collectives [21]. Mixed-initiative approaches [13] dynamically shift decision authority between humans and autonomy, supporting conflict resolution and efficient replanning in uncertain missions. Similar approaches are proposed in [43, 44] to compute least violating plans. Scaled-autonomy frameworks [40] extend this by allowing robots to modulate the level of assistance provided to the operator based on task load. Interactive fleet learning [17] integrates demonstration, online supervision, and data aggregation to refine fleet policies over time. However, many existing paradigms provide limited support for online validation and intervention, often restricting operators to static displays or post-hoc plans. In dynamic settings, this can force a fallback to teleoperation, which scales poorly with the fleet size due to increasing workload and latency. Consequently, interaction protocols that enable sparse and high-level oversight while preserving scalable autonomy remain insufficiently addressed. I Preliminary I-A Linear Temporal Logic (LTL) Linear Temporal Logic (LTL) formulas are composed of a set of atomic propositions APAP together with Boolean and temporal operators. Atomic propositions are Boolean variables representing elementary facts in the system, which can be either true or false depending on the state. The syntax [2] is given as follows: φ≜⊤|p|φ1∧φ2|¬φ|○φ|φ1Uφ2, \;|\;p\;|\; _1 _2\;|\; \;|\; \;|\; _1\, U\, _2, where ⊤≜True True, p∈APp∈ AP, ○≜ next, U≜ U until, and ⊥≜¬⊤ . Other operators such as □≜always always, ◇≜eventually eventually, and ⇒≜implication implication can be derived as abbreviations. LTL is widely used in robotics for specifying high-level missions such as “eventually visit region A and then always avoid region B.” Formally, an infinite word w over the alphabet 2AP2^AP is defined as an infinite sequence W≜σ1σ2⋯W _1 _2·s, with σi∈2AP _i∈ 2^AP. The language of a formula φ is defined as the set of words that satisfy it, namely ℒ≜Words(φ)=W∣W⊧φL Words( )=\W W \, where ⊧ denotes the satisfaction relation. A particularly useful subclass is the co-safe formulas, which can be satisfied by a finite sequence of words. They involve only the operators ○ , U, and ◇ , and are expressed in positive normal form. This property is advantageous in planning problems, since many practical missions can be verified after a finite execution, avoiding the need for reasoning over infinite traces. I-B Nondeterministic Büchi Automaton Given an LTL formula φ , one can construct an equivalent automaton that accepts exactly the set of words satisfying φ . A common representation is the Nondeterministic Büchi Automaton (NBA), defined as follows. Definition 1 (NBA). A NBA ℬB is a 5-tuple ℬ≜(Q,Q0,Σ,δ,QF)B (Q,\,Q_0,\, ,\,δ,\,Q_F), where Q is the set of states; Q0⊆Q_0 Q is the set of initial states; Σ=AP =AP is the set of alphabets; δ:Q×Σ→2Qδ:Q× → 2^Q is the nondeterministic transition relation; and QF⊆Q_F Q is the set of accepting states. ■ Given an infinite word w≜σ1σ2⋯w _1 _2·s, the resulting run [2] within ℬB is an infinite sequence ρ≜q0q1q2⋯ρ q_0q_1q_2·s such that q0∈Q0q_0∈ Q_0, qi∈Qq_i∈ Q, and qi+1∈δ(qi,σi)q_i+1∈δ(q_i,\, _i) hold for all i≥0i≥ 0. A run is accepting if it visits accepting states infinitely often, i.e., inf(ρ)∩QF≠∅ inf(ρ)∩ Q_F≠ , where inf(ρ) inf(ρ) is the set of states that appear infinitely often in the sequence of ρ. Such accepting runs are commonly represented in a prefix–suffix form, where the prefix reaches an accepting state, and the suffix is a cycle that revisits this state infinitely. This construction is fundamental in temporal-logic planning, but the size of ℬB can grow double exponentially with the length of φ , which poses scalability challenges in complex missions. IV Problem Formulation IV-A Multi-robot Systems Consider a team of N robots denoted by ≜1,⋯,NN \1,·s,N\, operating in a shared workspace ⊂ℝ3W ^3. Each robot i∈i is characterized by its position xi∈x_i , a reference velocity vi∈ℝ3v_i ^3, and a set of primitive actions iA_i. A robot can navigate freely in W according to viv_i, and can execute one action from iA_i at a time. The local plan of robot i is expressed as a sequence of timed actions: τi≜(ti1,pi1,ai1)(ti2,pi2,ai2)⋯, _i (t^1_i,\,p^1_i,\,a^1_i)(t^2_i,\,p^2_i,\,a^2_i)·s, (1) where tiℓ≥0t_i ≥ 0 denotes the time instant; piℓ∈p_i the goal position; and aiℓ∈ia_i _i the action to be executed. Thus, robot i navigates to piℓp_i with velocity viv_i and initiates action aiℓa_i from time tiℓt_i , for all ℓ≥1 ≥ 1. This representation encodes both mobility and task execution, which allows the fleet to be described as a set of inter-dependent and timed action sequences that must be coordinated at scale. IV-B Online Requests from Human Operator During execution, the operator can adapt the behavior of the fleet through online requests, which may introduce new missions or modify existing ones. Unlike offline formulations that assume static task sets, here the requests are treated as dynamic events that evolve over time and directly affect planning decisions. Four different types of requests are defined with explicit parameters as follows. (I) A new mission can be released at time t>0t>0 defined as κ1(t)≜(φt,t) _1(t) ( _t,\,t), where φt≜sc-LTL(t), _t -LTL( ω_t), (2) is a syntactically co-safe LTL specification over the set of collaborative tasks t≜ω1,⋯,ωMt ω_t \ _1,·s, _M_t\. Each collaborative task ωm _m is defined as: ωm≜(Sm,ηm,(nj,aj,sj),j=1,⋯,Jm), _m (S_m,\, _m,\, \(n_j,\,a_j,\,s_j),j=1,·s,J_m \ ), (3) where Sm⊂S_m is the region of execution; (nj,aj,sj)(n_j,a_j,s_j) is a subtask requiring at least njn_j robots to perform action aja_j at location sjs_j; and JmJ_m is the number of subtasks. The function ηm:ℕ×2→ℝ+ _m:N×A× 2^N ^+ defines the estimated duration, i.e., ηm(nj,aj,j) _m(n_j,a_j,N_j) gives the completion time if subteam j⊆N_j executes action aja_j at sjs_j. The logical composition of tasks follows the syntax in Sec. I-A, and satisfaction is defined through the relation ⊧ . Thus, the missions accumulate as t≜φtℓ,∀tℓ≤t _t \ _t_ ,\ ∀ t_ ≤ t\. Note that uncertainty is inherent: both the number of subtasks JmJ_m and their locations sj\s_j\ may be unknown at release, requiring redundancy in team formation and adaptive coordination during execution. Remark 1. The task definition in (3) differs from cLTL-based formulations in [36] in two aspects: (I) both task locations and the number of subtasks may be uncertain, and (I) the subtask duration depends on the assigned robots, rather than being instantaneous [29]. These extensions better reflect real-world missions such as search and rescue, where the environment reveals subtasks progressively. ■ Remark 2. The duration function ηm(⋅) _m(·) typically saturates, where the marginal benefit of adding robots decreases with team size. This property is widely adopted in generic task models [10, 22, 1], yet it is often neglected in temporal-logic planning [20, 32, 25, 5, 33, 3]. Capturing this effect is crucial to avoid over-allocation and to ensure efficient use of heterogeneous resources. ■ (I) Previous missions can be cancelled by κ2(t)≜φtℓ _2(t) \ _t_ \, where φtℓ∈t _t_ ∈ _t is the mission that has not yet been completed and should be cancelled. This captures the practical need to revoke outdated or invalid goals without disrupting other ongoing tasks and plans. (I) Deadlines and priorities of existing missions can be modified by κ3(t)≜(φtℓ,dℓ⋆,wℓ⋆) _3(t) \( _t_ ,\,d_ ,\,w_ )\, where φtℓ∈t _t_ ∈ _t is the mission to be modified, dℓ⋆>0d_ >0 is the updated deadline, and wℓ⋆>0w_ >0 is the revised priority. This reflects the ability of the operator to shift focus between competing objectives depending on urgency and available resources. (IV) Robots may be reassigned across missions manually by κ4(t)≜(ℓ,φtℓ) _4(t) \(N_ ,\, _t_ )\, where the subset of robots ℓ⊆N_ should be assigned to mission φtℓ∈t _t_ ∈ _t. This allows explicit operator control over resource allocation in situations where autonomous assignment may not match human intent. Thus, the evolving set of operator requests up to time t≥0t≥ 0 is denoted by the set below: (t)≜κ1(t),κ2(t),κ3(t),κ4(t),K(t) \ _1(t), _2(t), _3(t), _4(t) \, (4) where fulfilled requests are removed upon completion. This formulation enables a closed-loop interaction in which operator input and autonomous planning mutually adapt over time. IV-C Problem Statement Given the mission specifications in (2) and additional operator requests in (4), the overall objective is to synthesize collective plans in (1) such that the average mission response time is minimized, i.e., τi∑φtℓ∈t(tℓf−tℓ)|t|, _\ _i\\, _ _t_ ∈ _t(t_ f-t_ )| _t|, (5) where tℓt_ and tℓft_ f denote the release and completion times of mission φtℓ _t_ . This objective explicitly measures the responsiveness of the fleet, which is critical in dynamic and safety-critical environments such as disaster relief or surveillance. All operator requests in (t)K(t) must be satisfied during planning and execution as described earlier, ensuring that human interventions are seamlessly integrated into the autonomous coordination framework. Figure 3: The proposed protocols for human-fleet interaction: the human command and intervention module (left); the task decomposition and planning modules (right); and the visualization module (middle). Remark 3. The problem combines temporal missions with online operator requests, via introducing cancellations, priority updates and uncertain subtasks. Centralized MILP [41, 18] and decentralized market-based methods [48, 11] typically assume static tasks, while temporal-logic approaches [20, 37, 36] focus on fixed specifications. Existing frameworks for human–fleet interaction [10, 40] also target simpler settings, leaving the proposed problem insufficiently addressed. The integration of temporal-logic missions, dynamic operator requests, and large-scale multi-robot coordination therefore represents a significant gap that this work aims to fill. ■ V Proposed Solution The proposed solution consists of three main components as shown in Fig. 2: (I) the protocol and interface of human-fleet interaction, along with the hierarchical coordination and communication in Sec. V-A; (I) the receding-horizon task planning algorithm that assigns tasks to subteams of robots given the global mission specification and constraints on the resources in Sec. V-B; (I) the local coordination algorithm that assigns subtasks to robots during online execution in Sec. V-C. The synergy and adaptation of these components are triggered by online observations, human requests and execution status. For clarity, a table of key variables in this work is provided in the Appendix. V-A Protocol and Interface of Human-fleet Interaction This section introduces the communication and coordination framework that enables online human–fleet interaction. It first presents the protocol that maps operator requests to system modules, then describes the graphical interface that supports multimodal inputs and visual supervision, and finally outlines the hierarchical communication structure between the operator, team leaders, and team members. V-A1 Protocol for Online Requests The communication protocol links the four operator request types in (4) to the interaction module. As shown in Fig. 3, when a new mission is issued through request κ1 _1, the input is provided via voice, text, or templates, processed by the “task command module” and forwarded to the “task decomposition module,” which generates a sc-LTL specification with spatial-temporal constraints for the planning pipeline. Requests for cancellation κ2 _2, task modification κ3 _3, and robot reassignment κ4 _4 are processed by the “human intervention module,” which updates active missions and resources, passing changes to the “task allocation and planning module.” Ongoing executions that cannot be interrupted are preserved. The protocol ensures closed-loop communication, where upward flows transmit operator directives to the planning logic and downward flows provide feedback on planning results, execution progress, and environmental changes. This feedback is visualized via the “visualization and supervision interface,” displaying allocation maps, task graphs, and execution timelines. This setup ensures that operator interventions are executed and monitored in real-time throughout the mission lifecycle. Figure 4: Integrated interface for human-fleet interaction, which includes scenario visualization (top-left), temporal ordering of subtasks (top-middle), panel to specify operator requests (top-right), local plans and execution progress for teams and robots are visualized online (bottom). V-A2 Design of Graphical Interface for Online Interactions The graphical interface in Fig. 4 integrates the online interaction protocol with real-time visualization, linking operator inputs to the corresponding modules. On the right panel, the operator can release new missions through text, templates or voice, which are processed by the task command module to fulfill request κ1 _1. The same panel allows cancellation and priority updates, routed to the human intervention module for requests κ2 _2 and κ3 _3. Robot reassignment for request κ4 _4 is also supported. Responses are reflected in multiple interactive panels: the scene map displays task distribution, robot positions and trajectories; the mission panel shows the decomposed task graph and LTL formulas; and Gantt charts summarize task allocations and execution progress both for teams and robots. This interface closes the loop between human input, intermediate results and fleet execution, enabling transparent supervision and efficient adaptation. V-A3 Hierarchical Coordination and Communication The communication architecture follows a hierarchical structure that mirrors the organization of the fleet. At the top level, the operator interacts with designated team leaders through the task command and intervention modules, issuing high-level missions, modifying specifications, and adjusting deadlines or resource allocations [47]. Each team leader translates these directives into concrete plans for its team, forming subgroups when necessary and allocating robots to subtasks according to capabilities and availability [21]. At the lower level, team members communicate directly with their leader to receive local assignments and report execution status, enabling rapid coordination without overwhelming the operator with low-level details. This structure improves scalability by limiting communication overhead and enhances robustness by isolating local replanning within teams, while maintaining consistency since operator requests are propagated downward and execution feedback is aggregated upward in a structured manner. V-B Task Assignment and Team Formation V-B1 Simultaneous Task Decomposition and Team Assignment Existing work on task coordination for multi-robot systems under temporal logic specifications often relies on the synchronized product between the task automaton ℬφtB_ _t and the global system model, which is constructed as the product of all local robot models [37, 33]. This approach guarantees correctness but suffers from double-exponential growth in computational complexity. To mitigate this challenge, several methods have been proposed, including local coordination [27], decision trees [5], distributed sampling [20], hierarchical decoupling [31], and partial-order analyses [29]. Although these methods improve scalability in static environments, they are not suitable for open-world scenarios where new tasks may be triggered online. In such settings, re-computation of the entire system model would be required after each update, which invalidates previously computed results and leads to inefficiency. Consider the Büchi automaton ℬφm≜(Qm,Q0m,Σm,δm,QFm)B_ _m (Q^m,\,Q^m_0,\, ^m,\,δ^m,\,Q^m_F) associated with the mission specification φm∈Φt _m∈ _t, where Φt≜φ1,⋯,φM _t \ _1,·s, _M\ is the set of missions known at time t>0t>0 and ℳ≜1,⋯,MM \1,·s,M\. Moreover, the fleet is divided into K teams denoted by k⊂C_k and ≜1,⋯,KK \1,·s,K\, of which the exact value of K is to be decided. Each team kC_k is defined not by a fixed set of robots but by its composition, i.e., the available number of each robot type with associated capabilities. Denote by Γk,k∈\ _k,\,k \ the local plans of teams k\C_k\ as the sequences of tasks to be accomplished. Problem 1. Given the mission specifications φm∈Φt _m∈ _t, determine the optimal number of teams K, the composition of each team k\C_k\, and the local plans Γk\ _k\ such that: (I) the tasks can be executed by the assigned team under the temporal-logic constraints and the robot capacity constraints; and (I) the execution time for missions is minimized as in (5). ■ The search structure is organized as a tree ≜(,→) T (V,→), where ≜νV \ν\ is the set of nodes, and →⊂×→ ×V defines the edges. Each node ν≜(Γk,k∈,Q^m,m∈ℳ)ν (\ _k,\,k \,\ Q_m,\,m \) contains two components: the partial local plans of all teams k\C_k\ and the sets of current reachable states in ℬφmB_ _m for all missions φm∈Φt _m∈ _t. The root node is ν0≜(∅,Q^m0,m∈ℳ) _0 ( ,\ Q^0_m,\,m \). As summarized in Algorithm 1 and illustrated in Fig. 5, the proposed procedure consists of the following four stages. Figure 5: Illustration of the automaton-guided search tree, where the node expands over not only the local plans of each team Γk,k∈\ _k,\,k \, but also the progress of each mission Q^m,m∈ℳ\ Q_m,\,m \. The leaf nodes of complete assignments may correspond to different number of teams. (I) Selection. A set of P>0P>0 candidate nodes is selected for parallel expansion, i.e., P≜ν1⋆,⋯,νP⋆V_P \ _1 ,·s, _P \, where νp⋆≜argmin-pν∈χ(ν) _p argmin-p_ν \χ(ν) \ for p=1,⋯,Pp=1,·s,P. The value function χ:→ℝ+χ:V ^+ is defined as: χ(ν)≜maxk∈Tk+η1∑k∈Ck+η2∑m∈ℳmminqm∈Q^mψ(qm,QFm), splitχ(ν) & k max\T_k\+ _1 _k C_k\\ &+ _2 _m w_m q_m∈ Q_mminψ(q_m,\,Q^m_F), split (6) where η1,η2>0 _1, _2>0 are weighting parameters; mw_m denotes the preference weight associated with mission φm _m, reflecting human-specified priorities; Tk>0T_k>0 is the ending time of the local plan Γk _k; Ck>0C_k>0 is the estimated cost of Γk _k; and ψ(qm,QFm)>0ψ(q_m,\,Q^m_F)>0 returns the length of the shortest path from state qmq_m to any final state in QFmQ^m_F. The first term measures the makespan of the current assignments, the second term estimates the overall cost, and the third term accounts for the overall progress of missions. Remark 4. Parameters η1,η2>0 _1, _2>0 above regularize the search process, i.e., η1 _1 penalizes nodes with equal makespan based on cost, while η2 _2 prioritizes nodes with greater mission progress via ψ. These weights ensure makespan minimization while improving the search efficiency, with their impact primarily on convergence rate rather than optimality. ■ Moreover, given a node ν∈Pν _P and the associated local plans Γk\ _k\, the capacity constraints of each team k∈k under the updated assignment are given by: k≜((βkj,aj),aj∈ωkj,∀ωkj∈Γk),C_k ( \(β^j_k,\,a^j),\,a^j∈ω^j_k \,\,∀ω^j_k∈ _k ), (7) which specifies the minimum number of robots βkj>0β^j_k>0 to perform action aj∈a^j for each assigned task ωkj∈Γkω^j_k∈ _k. This requirement provides actions and counts, without binding specific robots, and thereby decouples assignment from scheduling. Moreover, if the capacity constraints above exceed the overall fleet capacity, i.e., the following condition: ∑k∈βkj≤∑i∈(aj∈i),∀aj∈; _k β^j_k≤ _i 1(a^j _i),\;∀ a^j ; (8) is violated, where the left-hand side is the required capacity and the right-hand side is the available fleet capacity. Then this node is marked infeasible and excluded from the set PV_P. (I) Expansion. Each selected node νh⋆∈P _h _P is expanded by assigning an additional task to one team. The set of candidate tasks is defined as below: Ωνh⋆−≜⋃m∈ℳω∈Σm|∃qm∈Q^m:δm(qm,ω)∈Qm, ^-_ _h _m \ω∈ ^m\, |\,∃ q_m∈ Q_m:δ^m(q_m,ω)∈ Q^m \, (9) where ω is an atomic task symbol from the alphabet Σm ^m and δm:Qm×Σm→2Qmδ^m:Q^m× ^m→ 2^Q^m is the transition function of the Büchi automaton ℬφmB_ _m. Thus, a candidate task must enable a valid state transition for at least one automaton ℬφmB_ _m. For each ω∈Ωνh⋆−ω∈ ^-_ _h , a child node is created by augmenting the local plan Γk _k of team kC_k with ω, namely: ν+≜(Γ1,⋯,Γk+,⋯,ΓK,Q^m+m∈ℳ),ν^+ (\ _1,·s, ^+_k,·s, _K\,\;\ Q_m^+\_m ), (10) where Γk+ ^+_k appends ω to Γk _k; the task set Ωk _k within Γk _k is updated by adding ω; and Q^m+≜δm(qm,ω)|qm∈Q^m Q_m^+ \δ^m(q_m,ω)\,|\,q_m∈ Q_m\ is the updated set of reachable states for mission φm _m. Consequently, the edge (νh⋆,ν+)( _h ,\,ν^+) is inserted into the search tree T. If no valid and feasible transition exists, then Ωνh⋆−=∅ ^-_ _h = and the node cannot be expanded. In addition, a new team (K+1)(K+1) can be created first by specifying its composition; a candidate task ω∈Ωνh⋆−ω∈ ^-_ _h is then assigned to it, and its capacity constraints K+1C_K+1 are computed by (7). Hence, task assignment and team formation emerge naturally during the search. More importantly, after assigning task ω to team k∈k , denoted by ωkℓω _k, the associated capacity constraint kC_k for this team is updated as follows: βkj≜maxaj∈ωkℓ∈Γknj,∀aj∈; β^j_k a^j∈ω _k∈ _kmax\n_j\,\;∀ a^j ; (11) i.e., the maximum number of robots βkjβ^j_k required for each action aja^j across the sequence of tasks ωkLkω^L_k_k. The related ending time is updated by: te(ωkℓ)≜maxωj∈Pre(ωkℓ)te(ωj)+Tnav(Skℓ−1,Skℓ)+Texec(ωkℓ), splitt_ e( _k ) & _j∈ Pre( _k )max \t_ e( _j) \\\ &+T_ nav(S_k -1,S_k )+T_ exec( _k ),\\ split (12) where te(ωkℓ)t_ e(ω _k) is the estimated ending time of ωkℓ∈Γkω _k∈ _k; Pre(ωkℓ) Pre( _k ) is the set of assigned tasks; and Tnav(Skℓ−1,Skℓ)T_ nav(S_k -1,S_k ) is the estimated navigation duration between regions. Input: Φt=φ1,⋯,φM _t=\ _1,·s, _M\, automata ℬφm\B_ _m\, fleet N. Output: Teams K, capacities k\C_k\, plans Γk\ _k\. 1 2Initialize =(,→) T=(V,→), =ν0V=\ _0\; 3 4while not terminated do /* Selection */ 5 P←ν1⋆,⋯,νP⋆V_P←\ _1 ,·s, _P \ by χ(ν)χ(ν) in (6); 6 Initialize kC_k for all k∈k via (7); 7 /* Expansion */ 8 foreach νh⋆∈P _h _P do 9 Obtain Ωνh⋆− ^-_ _h by (9); 10 foreach ω∈Ωνh⋆−ω∈ ^-_ _h do 11 if add new team then 12 Create K+1C_K+1, set ΓK+1=∅ _K+1= ; 13 Update K; 14 foreach team k∈k do 15 Generate ν+ν^+ by adding ω to Γk _k as (10); 16 Update Q^m+ Q_m^+ for all m; 17 Add (νh⋆,ν+)( _h ,ν^+) to T; 18 Update kC_k via (11); 19 Update te(ωkℓ)t_ e( _k ) via (12); 20 if (8) violated then mark ν+ν^+ infeasible; 21 /* Bounding */ 22 foreach ν∈ν do 23 Compute ζ(ν)ζ(ν) by (13); 24 Prune dominated nodes by (14); 25 26 Update ¯ V by (15); 27 /* Termination */ 28 Compute ¯⋆ V by (16), select νK⋆ _K by (17); 29 return Optimal K, k\C_k\, Γk\ _k\; Algorithm 1 Simultaneous Task Decomposition and Team Assignment (I) Bounding. To reduce unnecessary exploration, each node is evaluated through a performance profile that retains detailed information about the plans of all teams and the progress of all missions, i.e., ζ(ν)≜[Tk,k,minqm∈Q^mψm(qm,QFm),m∈ℳ], splitζ(ν) [\,&\T_k\,\;\C_k\,\;\\ & \ q_m∈ Q_mmin _m(q_m,\,Q^m_F),m \\, ], split (13) where TkT_k is the ending time of Γk _k; CkC_k is the estimated cost of Ωk _k; and the last term ψm(⋅) _m(·) measures the minimum distance from the current automaton states Q^m Q_m to the accepting set QFmQ^m_F for each mission φm _m. The profile ζ(ν)ζ(ν) has dimension (2K+M)(2K+M) and is non-negative. Given two nodes ν1 _1 and ν2 _2, node ν1 _1 is said to dominate node ν2 _2 if the following holds: ζ(ν1)≤ζ(ν2),andζ(ν1)≠ζ(ν2),ζ( _1)≤ζ( _2), ζ( _1)≠ζ( _2), (14) where the inequality is understood element-wise across the vector in (13). Thus, node ν1 _1 has no larger makespan or cost for any team, and no less mission progress for any specification, with strict improvement in at least one entry. In this case, node ν2 _2 is marked as dominated and excluded from expansion. The set of all non-dominated nodes is the set of frontiers, defined as follows: ¯≜ν∈|∄ν′∈:ν′ dominates ν, V \ν \, |\, \,ν :ν dominates ν \, (15) which is updated whenever a new node is added. This bounding procedure maintains only ¯ V as candidates for expansion, ensuring that strictly inferior nodes are pruned and that the search focuses on promising branches of the tree T. (IV) Termination. The stages of selection, expansion, and bounding are repeated until the computation budget is exhausted or no new non-dominated nodes emerge. The current set of frontier is ¯ V from (15), and the subset of complete assignments is given by: ¯⋆≜ν∈¯|(Q^m∩QFm)≠∅,∀m∈ℳ, V \ν∈ V\, |\,( Q_m∩ Q^m_F)≠ ,\;∀ m \, (16) where the accepting set is reached for all missions. Thus, the optimal node is selected among these assignments, i.e., νK⋆≜argminν∈¯⋆χ(ν), _K argmin_ν∈ V \,\χ(ν)\, (17) with χ(ν)χ(ν) from (6). The associated capacity constraints k\C_k\ and the global assignment are specified by the resulting plans Γk\ _k\ together with execution times. Example 1. As illustrated in Fig. 5, given ω1,ω2,ω3,ω4,ω5 _1, _2, _3, _4, _5 in the mission automata ℬφm\B_ _m\, the node νK⋆ν _K assigns 55 tasks to 33 subteams and the optimal K⋆=3K =3. Thus the local plans are given by executing ω3 _3 after ω1 _1 for team one; ω4 _4 after ω2 _2 for team two; and task ω5 _5 for team three. ■ Last but not least, due to the dynamic nature of the environment, a receding-horizon strategy is adopted for the task assignment. Thus, the search is paused when the number of assigned tasks for the fleet reaches the horizon H>0H>0 as a user-defined hyper-parameter, and is resumed at the next planning cycle as described in the sequel. Note that the horizon H balances the batch-assignment efficiency and the online responsiveness. A small H results in fragmented task sequences and frequent replanning, which under-utilizes its capability to optimize large task sets. Conversely, an excessively large H increases computational redundancy and may induce oscillation in dynamic environments, as long-term commitments are often invalidated by online mission updates. This trade-off is evaluated empirically in Sec. VI. Remark 5. The framework presented above offers several advantages over existing approaches [20, 37, 33, 31, 29, 30]: (I) it circumvents the explicit construction of the synchronous product between the Büchi automaton, the robot models as transition systems, and the global product, which is prohibitively large in multi-robot settings; (I) the search is both anytime and complete, in contrast to mixed-integer linear programming methods that often require long solving times without intermediate feasible outputs; (I) it is well suited to partially known and dynamic environments where missions are triggered online, since a new specification can be incorporated by introducing its reachable state set Q^k Q_k without interfering with existing missions; (IV) the stages of node selection and expansion can be carried out in parallel, enabling efficient scaling to large teams and complex mission sets; (V) the node construction and expansion above differ from the poset-based methods in [29, 30]. Instead of using partial orders, each node ν above maintains the sets of reachable states Q^m Q_m for each mission automaton, allowing task decomposition and team assignment simultaneously. This approach eliminates the re-computation for global posets, enabling faster integration of online missions and reducing overhead pre-processing. More numerical comparisons are given in Sec. VI. ■ Correctness and completeness of the simultaneous task decomposition and team assignment algorithm above is provided below. Particularly, it is shown that the completeness and optimality hold in the static and known case with the full horizon. Moreover, in the online receding-horizon case, the algorithm can still ensure correctness and feasibility, while scalability and adaptability are evaluated empirically in Sec. VI. Proofs are provided in the Appendix. Theorem 1. Consider an instance of Problem 1 with fleet N and mission set Φt _t. Suppose all missions are known a priori and the planning horizon H is larger than the total number of admissible tasks. Then, the team plans Γk\ _k\ generated by Alg. 1 satisfy: (I) all temporal constraints encoded in the mission automata ℬφm\B_ _m\ hence all mission specifications; and (I) all capacity constraints in (7)–(8). Moreover, whenever feasible plans exist, Alg. 1 returns the feasible plan that minimizes the makespan objective in (6). Lemma 2. Under online mission release and the receding-horizon replanning with H<|Ω|H<| |, Alg. 1 guarantees that the computed partial plan ν is consistent with the active missions. Moreover, each time a new mission is added, the updated partial plan after adaptation can still preserve satisfaction under the event-triggered adaptation scheme. V-B2 Capacity-based and Redundancy-aware Team Formation Given the optimal team–task assignment νK⋆ _K , the composition of each team remains to be determined. In particular, the capacity constraints derived earlier specify only the aggregate requirements for each team, i.e., the minimum numbers of robots with specific capabilities. The actual formation of teams requires allocating individual robots to these abstract capacities while respecting disjoint membership and redundancy margins. This problem is formulated as follows. Problem 2. Given the assignment νK⋆ _K and the fleet N, determine the team formation ¯=1,⋯,K⋆ N=\N_1,·s,N_K \, where kN_k is the set of robots assigned to team kC_k. Each team must satisfy the required capacities, and membership must be disjoint, i.e., k1∩k2=∅N_k_1 _k_2= for k1≠k2k_1≠ k_2. The objective is to minimize the overall response time as defined in (5), thereby ensuring efficient execution of all assigned tasks. ■ The team formation problem is addressed using a redundancy-aware mixed-integer linear programming (MILP) formulation. This formulation explicitly enforces the capacity constraints of each team, while also incorporating redundancy margins that allow flexibility in resource allocation. The approach can be summarized in two key components. Figure 6: Illustration of the capacity-based and redundancy-aware team formation. Given the task assignment νK⋆ _K , the team formation 1,⋯,K⋆\N_1,·s,N_K \ are the determined optimally under the redundancy margin in (18). (I) Capacity constraints. Binary decision variables bik∈0,1b_ik∈\0,1\ are introduced to indicate whether robot i∈i is assigned to team kC_k. For each action aj∈a^j required by team kC_k, the number of assigned robots must satisfy a lower bound and an upper bound as follows: βkj≤∑i∈bik 1(ai=aj)≤βkjαj,β^j_k\;≤ _i b_ik\, 1(a_i=a^j)\;≤\;β^j_k _j, (18) where βkjβ^j_k is the minimum number of robots required to perform action aja^j, and αj≥1 _j≥ 1 is a redundancy margin introduced as in Remark 6. The inequality above ensures that team kC_k is always sufficiently staffed to satisfy the task requirements, while still allowing limited redundancy given available resources within the fleet. Together, these constraints provide a trade-off between feasibility, efficiency and robustness for the team formation. Remark 6. The margin αj\ _j\ above accounts for (i) uncertainty in the effective workload of tasks such as unknown subtasks revealed online, and (i) robot failure or unavailability during execution. In practice, they are selected as a small safety factor above 1 and increased when subtask-count uncertainty or failure rate is higher. Larger αj\ _j\ improves robustness but may reduce efficiency by reserving additional robots; smaller αj\ _j\ yields higher utilization but can be less resilient to uncertainty and failures. ■ (I) Min-max objective. The second component is to minimize the response time across all teams. For each robot i potentially assigned to team kC_k, the expected arrival time at the first task region Sk1S_k^1 is tik≜t^i+Tnav(x^i,Sk1)t_ik t_i+T_ nav( x_i,S_k^1), where t^i t_i is the time when robot i becomes available and x^i x_i is its position at that time. Once robots are assigned, the execution cost of team kN_k is given by J(k)≜maxi∈ktik+∑ω∈ΓkTexec(ω)J(k) _i _k\t_ik\+ _ω∈ _kT_ exec(ω), where the first term captures the synchronization delay of the slowest robot, and the second term aggregates execution times. The global objective is then minmaxk∈J(k)min\,\max_k J(k)\, which minimizes the worst-case response time across all teams. This reflects the fact that overall mission efficiency is determined by the slowest team to complete its tasks. The above formulation constitutes a MILP problem, which can be solved by off-the-shelf solvers such as GLOP [39]. The solution provides the optimal binary assignment bik\b_ik\, from which the team formation ¯ N is derived. Specifically, the team formation is given by k≜i∈∣bik=1N_k \i b_ik=1\, which defines the robots in team kC_k. In addition, the local plan of each robot i∈ki _k can be generated as a timed sequence of tasks, i.e., ξi≜(Sk1,ωk1)(Sk2,ωk2)⋯(SkLk,ωkLk),∀i∈k; _i (S^1_k,ω^1_k)(S^2_k,ω^2_k)·s(S^L_k_k,ω^L_k_k),\;∀ i _k; (19) where ωkℓω _k is the ℓ -th task in team kC_k; SkℓS _k is the associated region; and LkL_k is the number of tasks. This ensures that each robot has a concrete plan consistent with both the task assignment of its team and the global mission specification. The redundancy-aware team formation is formulated as a MILP with binary membership variables bik∈0,1b_ik∈\0,1\, where i∈i and k∈1,⋯,K⋆k∈\1,·s,K \. This formulation introduces (||K⋆)O(|N|K ) integer variables and (||K⋆)O(|A|K ) capacity constraints in (18). While NP-hard in the worst case, the value of K⋆K is small in this context, ensuring that the solve time remains manageable. The best incumbent feasible formation can be returned under a limited planning time. In case of no feasible solutions, a greedy capacity-filling heuristic is employed as a fallback. Note that this team-formation MILP is significantly smaller than the direct robot-to-subtask assignment method without the hierarchical structure [36, 23]. More numerical comparisons can be found in Sec. VI. Example 2. Fig. 6 shows the team formation induced by the optimal task assignment νK⋆ν _K , i.e., coalitions kk=1K⋆\C_k\_k=1^K . In particular, the team 1=2,4,6,7,9N_1=\2,4,6,7,9\ executes ω2ω3ω6ω8 _2 _3 _6 _8; the team 2=3,8,15,14,13N_2=\3,8,15,14,13\ executes ω1ω5 _1 _5; and the team K⋆=5,10,11,17,19,18N_K =\5,10,11,17,19,18\ executes ω9ω11ω10 _9 _11 _10. ■ V-C Local Task and Trajectory Coordination within Teams Given the optimal assignment νK⋆ _K , the local task plan i τ_i of each robot i∈ki _k is derived as in (19). Each robot i navigates to region SkℓS _k to start executing its ℓ -th task (Skℓ,ωkℓ)(S _k,\,ω _k). As denoted in (3), subtasks kℓ≜(nj,aj,sj),j=1,⋯,JkℓJ _k \(n_j,\,a_j,\,s_j),j=1,·s,J _k \ must be considered to perform the task ωkℓω _k. For task ωkℓω _k assigned to team kN_k, the local plan of each robot i∈ki _k is given by i≜(ti1,pi1,ai1)(ti2,pi2,ai2)⋯ τ_i (t^1_i,\,p^1_i,\,a^1_i)(t^2_i,\,p^2_i,\,a^2_i)·s, which is a sequence of timed goal positions and actions. The collective plan of the team is given by kℓ≜i∣i∈k τ _k \ τ_i i _k\. However, the assignment of subtasks is interdependent with the optimization of the associated trajectories, as the trajectory affects the time taken for each robot to reach subtask positions and execute subtasks. The optimization problem must consider the trajectory of each robot ix_i alongside subtask assignment, ensuring that both spatial and temporal coordination are optimized simultaneously. Thus, the objective is not only to assign subtasks to the robots but also to determine both the local plans i\ τ_i\ and trajectories i\x_i\ of all robots in team kN_k. This simultaneous coordination guarantees that the overall task completion is time-efficient, considering both the subtask execution and the robot motion. Optimizing trajectories is crucial to minimizing the makespan of task completion. Figure 7: Local coordination results for the static and known local tasks described in Sec. V-C1. In total 1414 delivery subtasks (filled circles) are assigned to 55 robots (filled pentagons), of which the trajectories are shown for fully-actuated (left) and non-holonomic (right) robots. Problem 3. Given task ωkℓω _k with area SkℓS_k , subtasks kℓJ _k as in (3) and the assigned team kN_k, the goal is to determine the optimal local plans i\ τ_i\ and robot trajectories i\x_i\ for each robot i∈ki _k. The objective is to minimize the makespan TkℓT _k as the collective execution time for task ωkℓω _k, while simultaneously optimizing trajectories and task assignments. ■ Uncertainty in the number of subtasks JkℓJ_k and their locations sj\s_j\ for task ωkℓ _k requires coordination strategies conditioned on task properties. Static and known tasks reduce to allocation and trajectory optimization for makespan minimization. Static but unknown tasks require exploration with online insertion of discovered subtasks. Dynamic but known tasks require continual online reassignment and trajectory updates. These cases defined by the static–dynamic and known–unknown axes motivate tailored coordination strategies below. V-C1 Static and Known Subtasks In the static and known case, both the number of subtasks JkℓJ _k and their locations sj\s_j\ are predetermined. This situation often arises in delivery or inspection tasks with fixed points of interest. While the setting is classical, the consideration of robot dynamics is essential: robots with free holonomic motion can move directly between subtasks, whereas robots with non-holonomic constraints must follow feasible trajectories that depend on both position and orientation. Therefore, planning in this case requires different treatments depending on the underlying motion model. For holonomic robots, the problem reduces to a variant of the multi-vehicle routing problem (MVRP) without return. Robots travel along straight-line segments between subtasks, and the sequence of visits is determined by solving a combinatorial optimization problem, via off-the-shelf solvers such as [39]. The outcome directly specifies the local plans i\ τ_i\, while the trajectories i\x_i\ are straight-line connections. However, for non-holonomic robots, the problem becomes a hybrid optimization in which task sequencing and feasible trajectories are optimized jointly. Each subtask location is augmented with an orientation, and also the robot state. The transition between subtasks is evaluated using motion primitives generated between states, such as Dubins curves [35, 45]. Each primitive is a dynamically feasible trajectory with the associated cost and duration. Thus, the overall objective is given by: Jkℓ≜mini,imaxi∈k∑(sj1,sj2)∈iminκ∈(xj1,xj2)Cost(κ),J _k \ τ_i,x_i\min\, \ i _kmax\; \ _(s_j_1,s_j_2)∈ τ_i κ∈ κ(x_j_1,x_j_2)min\, Cost(κ) \ \, (20) where (xj1,xj2) κ(x_j_1,x_j_2) denotes the predefined set of feasible motion primitives connecting the intermediate states xj1x_j_1 and xj2x_j_2. In practice, a hybrid-A⋆ like search method [9] can be adopted to jointly optimize the sequence of subtasks and motion primitives, producing the local plans i\ τ_i\ and trajectories i\x_i\ that minimize the makespan. Example 3. As shown in Fig. 7, in total 1414 delivery subtasks are assigned to 55 robots under different dynamic constraints. Note that the subtasks require different robot capabilities. The resulting assignments and trajectories are significantly different for holonomic and non-holonomic teams. ■ V-C2 Static and Unknown Subtasks In the static and unknown case, the subtasks kℓJ_k of ωkℓ _k are initially unknown but become fixed once discovered. This setting is common in search-and-rescue, where the number and locations of victims or targets in a region are revealed only during execution. Since subtasks appear online, the static assignment model in the first case is not directly applicable. To address this, we propose a simultaneous exploration and coordination (SEC) method with two components: (I) collaborative exploration of the task area and (I) dynamic assignment of newly discovered subtasks during exploration. During exploration, the team must survey the task region SkℓS_k to reveal subtasks. Two strategy classes are considered here: (I) Obstacle-free spaces: the goal is collaborative coverage, where standard coverage methods, e.g., polygon-based decomposition, apply while accounting for heterogeneous robot velocities, initial positions, and perception radii. (I) Cluttered or structured workspaces: robots must plan around obstacles; frontier-based exploration is commonly used [16], with trajectories respecting the robot dynamic constraints. In both cases, coordination avoids redundant search and ensures full coverage. The output is the exploration trajectories i\x_i\ for all i∈ki _k. Figure 8: Execution results for the case of static and unknown subtasks in Sec. V-C2, e.g., the “search and rescue” task. Left: The initial trajectories for coverage by 55 robots with unknown targets (in circles); Right: The actual trajectories after discovering, assigning and executing 88 rescue subtasks. Furthermore, once the region begins to be explored and new subtasks are discovered, the task of assigning and fulfilling these subtasks must be done simultaneously with exploration. A minimum-disruption planning method is proposed, where newly discovered subtasks are inserted into the local plans of each robot. The objective is to minimize the increase in makespan due to these insertions. Specifically, once a subtask j∈kℓj _k that meets the robot capabilities aj∈ia_j _i is discovered, the robot updates its local plan to include the subtask. The task sequence for each robot i∈ki _k is then re-optimized to minimize the makespan for the new tasks, i.e., min(i,i)∑j=1Lkℓ(Cost(i+−Cost(i))), \( τ_i,x_i)\min\; \ _j=1^L_k ( Cost( τ_i^+- Cost( τ_i)) ) \, (21) where i+ τ_i^+ denotes the updated local plan after inserting the newly discovered subtasks, and the objective quantifies the resulting increase in execution cost and makespan. Subtasks are assigned online by selecting the robot that yields the smallest incremental cost in (21). The assignments are recomputed either periodically or after substantial progress on the current set. The output is the updated local sequences i\ τ_i\ and corresponding trajectories i\x_i\. Finally, non-holonomic constraints are handled as in the static and known case by planning over motion primitives to ensure feasible trajectories. Example 4. As shown in Fig. 8, in total 55 robots are assigned to execute the task with 88 unknown targets. The initial trajectories of exploration minimizes the coverage time by the computed division points. More targets are discovered during exploration and assigned via the proposed scheme. The resulting trajectories not only explore the task region, but also fulfill all discovered subtasks. ■ V-C3 Dynamic and Known Subtasks For the third case, the set of subtasks JkℓJ_k within ωkℓ _k and their initial locations sjs_j are known, but the subtasks are dynamic moving during execution. Their real-time positions are assumed to be available through external sensing or tracking systems [49]. Typical examples include collaborative pursuit or capture tasks, where the robots must form coalitions to surround and intercept moving targets. In such settings, static plans quickly become suboptimal or infeasible as the subtasks evolve over time. Input: Subteam kN_k, subtasks kℓJ_k , cost χ(⋅)χ(·). Output: Updated i(t)\ τ_i(t)\ and i(t)\x_i(t)\. 21 repeat at each planning iteration for each robot i∈ki _k; 43 Collect neighbor memberships and χ(ℛj)\χ(R_j)\; 65 Set j′←argminjχ(ℛj)j ←argmin_j\;χ(R_j); 87 if (23) holds then; 109 Send switch intent to robot j′j ; 1211 if no higher-priority conflicts; 13 Set ji←j′j_i\!←\!j and synchronize; 1514 until no robots can switch; 16 Update i(t)\ τ_i(t)\ and i(t)\x_i(t)\ given ℛ¯t R_t; Algorithm 2 Distributed Local Update for Dynamic and Known Subtasks A distributed dynamic coalition formation (DCF) method is adopted, in which each robot i∈ki _k updates its coalition membership using local information and peer communication [8, 15]. At any time t, each subtask j∈kℓj _k is associated with a coalition ℛj(t)⊆kR_j(t) _k, and the collection of all coalitions forms a scheme ℛ¯t≜ℛj(t),j∈kℓ R_t \R_j(t),\,j _k \. The coalitions are disjoint and collectively exhaustive, i.e., ℛj1(t)∩ℛj2(t)=∅R_j_1(t) _j_2(t)= for j1≠j2j_1≠ j_2, and ⋃j∈kℓℛj(t)=k _j _k R_j(t)=N_k. The local plan i(t) τ_i(t) is determined by its current coalition, i.e., i(t)=(ti,pi,ai) τ_i(t)=(t_i,p_i,a_i) for the currently assigned subtask, and its trajectory i(t)x_i(t) follows the coalition decision. To guide updates, each robot maintains local estimates of the coalition costs χ(ℛj)χ(R_j), which depend on the robot–target distances and the velocities. The instantaneous team cost is defined as: χ(ℛ¯t)≜maxj∈kℓχ(ℛj)+1Jkℓ∑j∈kℓχ(ℛj),χ( R_t) j _k max\,χ(R_j)+ 1J_k _j _k χ(R_j), (22) where the first term reflects the current makespan across all subtasks, and the second term encourages a balanced workload. Based on (22), the local switch rule is stated from the perspective of each robot and is summarized in Alg. 2. At time t, robot i knows its assigned task jij_i and the associated coalition ℛjiR_j_i. More importantly, it can estimate χ(ℛj′)χ(R_j ) for nearby subtasks j′∈kℓj _k . Then, the robot i can evaluate the following condition locally: maxχ(ℛj′⋃i),χ(ℛji\i)<maxχ(ℛji),χ(ℛj′), split&max\! \χ(R_j \i\),\,χ(R_j_i \i\) \\\ & <max\! \χ(R_j_i),\,χ(R_j ) \, split (23) where ℛj′R_j is the candidate coalition and ℛjiR_j_i is the current coalition of robot i. If the inequality holds, an intent to switch is announced to neighbors in ℛj′R_j and ℛjiR_j_i, a priority rule resolves potential conflicts, and afterwards a synchronization finalizes the change. Robot i then updates its local plan i(t) τ_i(t) and trajectory i(t)x_i(t) to track the new subtask. This local rule uses only the neighborhood costs and memberships, preserves disjoint coalitions, and drives the scheme toward a locally optimal ℛ¯t⋆ R_t , yielding time-varying plans i(t)\ τ_i(t)\ and trajectories i(t)\x_i(t)\ that continuously adapt to the moving subtasks. Figure 9: Execution results of the dynamic and known subtasks in Sec. V-C3. Top: the trajectories of 55 robots (filled hexagons) and 55 targets (filled circles) at different snapshots; Bottom: the evolution of assigned coalitions for each target. Note that different colors reflect different capacity constraints. Example 5. As shown in Fig. 9, 55 robots are assigned to 55 moving targets by forming dynamic coalitions online in Alg. 2. Initially, each robot is assigned to one target. However, robots 22 and 33 exchange their targets at t1t_1. When target 33 is finished at t3t_3, robots 2,42,4 form into a coalition to execute target 22 while robot 33 executes target 44. ■ Remark 7. The local coordination policy in Sec. V-C relies on inter-robot information exchange over the communication graph induced by the communication radius. Connectivity is the key structural requirement: if the graph is disconnected, coordination messages cannot propagate and effective collaboration cannot be realized. Moreover, latency, packet loss, and bandwidth limitations primarily slow information flow, increasing the planning time and causing transient inconsistencies in i\ τ_i\. However, when the graph is connected sufficiently often over time windows, delayed or missed updates are corrected once communication resumes. More realistic models of intermittent communication with joint planning of task and communication events remain our ongoing work. ■ Remark 8. Note that the case of dynamic and unknown tasks is not considered here, due to two reasons: (I) without knowing the total number and locations of subtasks, it is difficult to determine whether the current task is completed, e.g., subtasks may move dynamically from unexplored areas to explored areas; (I) if such a task exists, the coordination strategy would be a combination of the second and third cases above, i.e., to assign the subtasks of exploration and collaboration via dynamic coalition formation. ■ The theorem below presents the correctness guarantee for the local coordination policies proposed above. Detailed proof is attached in the Appendix. Theorem 3. For each task ωkℓ _k and team kN_k, the strategies in Sec. V-C ensure that the plans i\ τ_i\ and trajectories i\x_i\ are feasible, and minimize the local task makespan. V-D Online Execution, Interaction and Adaptation V-D1 Online Execution and Receding-horizon Adaptation Figure 10: Illustration of the change of execution status between navigation, execution and synchronization (left), for a team kC_k given its local plan Γk _k (right) in (17) and (19). Note that the concurrency constraint between tasks ω2,ω5 _2, _5 are enforced by the synchronization state (red line). Given the initial workspace and mission descriptions, the missions are decomposed into tasks and the local teams ¯ N are formed. A finite set of H tasks is then assigned with redundancy by Alg. 1, yielding the local plan Ξk _k for each team k∈¯N_k∈ N. Then, each team executes (Skℓ,ωkℓ)∈ξk(S _k,ω _k)∈ _k by navigating to SkℓS _k and performing ωkℓω _k. Specifically for robots in teams, synchronization is required before execution. Not only the robots within the team should collaborate to perform tasks, but also there are temporal constraints between tasks including precedence or concurrency. This yield three distinctive states during online execution: navigation, execution and synchronization. When execution begins, the subtasks kℓJ _k are coordinated by three local strategies to derive the action plans i\ τ_i\. Execution is concurrent across teams and parallel within each team. This process continues until all local plans Ξk\ _k\ are completed, or a replanning is triggered. Example 6. As shown in Fig. 10, teams 1N_1 and 2N_2 are constructed from capacities 1C_1 and 2C_2 by team formation. After task ω2 _2, team 2N_2 should wait for team 1N_1 to perform task ω5 _5, due to the concurrency constraint for ω2,ω5 _2, _5. ■ Furthermore, a receding-horizon scheme handles replanning for online tasks and operator updates. As shown in Fig. 11, only H tasks are assigned per cycle, and the remaining tasks are considered in the next cycle. Replanning is triggered by: (I) execution progress, when more than half of the planned tasks are accomplished; (I) new mission specifications, when new missions or modifications arrive; and (I) feasibility, when any team reports infeasibility due to execution failures. Upon any of the triggering conditions, the task assignment and team formation are recomputed by Alg. 1 using the current system state. The candidate pool includes tasks that are assigned but not yet started, unassigned tasks and newly specified tasks, which enables consistent revision of priorities and team compositions. However, tasks currently in execution are not preempted, and the associated teams continue execution without interruption. This non-preemption policy preserves the safety and continuity, which is crucial when the tasks outnumber the required teams. Moreover, the robot states are maintained by rolling forward the execution status: for team kN_k with the current sequence (ωk0,⋯,ωkLk)(ω^0_k,·s,ω^L_k_k), where ωkLkω^L_k_k is ongoing, it holds that t^i≜te(ωkLk) t_i t_ e( _k^L_k) and x^i≜SkLk x_i S_k^L_k for each i∈ki _k. This enables consistent future formations under temporal ordering constraints. Figure 11: Illustration of the receding-horizon scheme for coordination and online adaptation in Sec. V-D. Note that the number of teams is increased from 33 (left) to 55 after the task assignment and team formation (right), and the tasks ω3,ω4 _3, _4 are not preempted after replanning. Figure 12: Simulated human-in-the-loop scenario of 8080 robots in dynamic environment. Top: in total 3232 tasks and 482482 subtasks are performed during the mission time of 180.4s180.4\,s, with the time elapsed from left to right. Clearly κ1 _1 to κ4 _4 are issued in the process; Bottom-left: the snapshots of execution of tasks at t=15st=15\,s, where different markers indicate different types of robots; Bottom-right: gantt charts of teams executing assigned tasks at t=0st=0\,s, t=15st=15\,s and t=130st=130\,s. Note that tasks ω1−ω9 _1- _9 are released at t=0st=0\,s, ω10−ω14 _10- _14 at t=30st=30\,s, ω15−ω19 _15- _19 at t=60st=60\,s, ω20−ω26 _20- _26 at t=100st=100\,s, ω27−ω30 _27- _30 at t=130st=130\,s, and ω31,ω32 _31, _32 are issued by operator at t=110st=110\,s. Remark 9. Note that the choice of the key parameters including the rolling horizon H, the redundancy margin α≥1α\!≥\!1, and the replanning trigger, such as the completion ratio of committed tasks or event-driven updates, typically depends on the expected mission volatility, e.g., the arrival and cancellation rate in Φt _t, the uncertainty in task and target estimation, e.g., location and service-time dispersion, and the anticipated robot failure and communication drop rate, which together balance look-ahead optimality, robustness, and responsiveness. Numerical analyses on how their values affect the overall performance are provided in Sec. VI. ■ V-D2 Fulfillment of Online Human Requests Online operator requests are routed from the graphic interface including text, voice and templates, following the protocol for online requests in Sec. V-A. These requests are processed by the task decomposition module and the proposed planning stack. Each request induces a bounded update of the search tree T and the frontiers ¯ V, followed by a re-optimization of teams K, capacities k\C_k\, and plans Γk\ _k\ by Alg. 1. The updated plans are forwarded to the team execution as in Sec. V-C, under the non-preemption and receding-horizon scheme in Sec. V-D1, while the visualization interface immediately reflects changes in the task allocation, temporal relations among tasks and Gantt timelines, as summarized in Sec. V-A2. More specifically, the four types of requests defined in Sec. IV-B are handled as follows. A new mission κ1 _1 is parsed and decomposed to sc-LTL, yielding ℬφmB_ _m and Q^m0 Q^0_m, with Φt←Φt∪φm _t\!←\! _t∪\ _m\; the planner continues the tree search by evaluating χ(ν)χ(ν) in (6), updating ¯ V via (15), and re-selecting the complete assignment by (16). A cancellation κ2 _2 removes φm _m from Φt _t, prunes nodes whose progress depends on Q^m Q_m, and recomputes ¯ V, while preserving tasks already in execution. A deadline or priority update κ3 _3 modifies the value function and costs by re-weighting the progress and adding deadline penalties within χ(ν)χ(ν) and CkC_k of (6) and (7), in addition to bounding functions in (13), thus biasing the selection toward urgent missions. Lastly, a direct robot reassignment κ4 _4 changes its fleet N and states (t^i,x^i)( t_i, x_i). Then, the capacity-based formation with bounds (18) is re-solved with the min–max objective J(k)J(k) in (17), producing the revised k\C_k\ and Γk\ _k\. All requests are issued through the same interface and acknowledged by synchronized feedback. Note that request κ4 _4 imposes linear admissibility constraints on bik\b_ik\ such as the locked and forbidden assignments, and optional limits on membership changes. These constraints are reflected in the receding-horizon assignment by restricting which capacity allocations are allowed within the tree search. Therefore, feasibility checks are performed across layers. Remark 10. In practice, an operator may issue contradictory requests, e.g., enforcing immediate completion of a task via κ3 _3 while restricting the only capable robot via κ4 _4. In case of conflicting operator requests, if the set of current requests tK_t renders the hard constraints inconsistent, e.g., capacity bounds (18), non-preemption in Sec. V-D1, or priority constraints in χ(ν)χ(ν) and CkC_k in (7), then Alg. 1 and the formation objective J(k)J(k) in (17) becomes infeasible. This infeasibility is detected at the module where it arises, thus an explicit warning is issued with the violated constraint class and implicated missions or robots, which prompts the operator to revise tK_t before replanning proceeds. ■ V-D3 Complexity and Scalability Analysis The computational complexity of the proposed method is analyzed as follows. In each iteration of Alg. 1, selecting a batch of P nodes and expanding up to B≜(K+1)|Ωνh⋆−|B (K+1)\,| ^-_ _h | children incurs (PBK)O(PBK) for the automaton-state updates Q^m+ Q^+_m, together with the capacity and timing updates in (11) and (12); maintaining the non-dominated frontier based on (13)-(15) requires (||(2K+M))O(|V|(2K+M)) to reach the completeness condition in (16). The capacity-based team-formation MILP introduces (NK⋆)O(NK ) binary variables bikb_ik, which is NP-hard in general but limited by the small number of teams. For the case of static and known tasks, the routing problem with subtour elimination is NP-hard, and its number of variables scales with |k|(Jkℓ)2|N_k|(J_k )^2. For static and unknown tasks, polygonal coverage generation and assignment are near-linear in the region representation, while rolling insertion of newly discovered subtasks is (|k|)O(|N_k|) per discovery. Lastly, for dynamic and known tasks, the distributed coalition updates are linear in team size and the number of active targets per iteration. Although the local MILPs and coalition updates are NP-hard in the worst case, the hierarchical decomposition confines them to small teams, enabling event-based replanning with standard solvers. Detailed empirical runtime evaluations of each component and scaling benchmarks are provided in Sec. VI. VI Numerical Experiments For numerical validation, the proposed method is implemented in Python 3 and tested on a laptop with an Intel Core Ultra 9 285K CPU. The solver GLOP [39] is used for integer optimization. Simulation videos can be found in the supplementary files. Figure 13: Final trajectories of local task executions for robots under the dynamic constraints of maximum curvature κ≤3κ≤ 3. Top: delivery task ω3 _3 at t=22st=22\,s for a team of 88 robots and 1818 subtasks; Middle: surveillance task ω7 _7 at t=25st=25\,s for a team of 2020 robots and 1616 subtasks; Bottom: dynamic capture task ω5 _5 at t=13st=13\,s for a team of 2222 robots and 1818 subtasks. VI-A System Description As shown in Fig. 12, the simulated fleet consists of N=80N=80 heterogeneous robots operating in an open environment of size 260m×42m260\,m× 42\,m. There are three robot types with complementary capabilities: 2020 Type-A robots that perform perception and delivery; 2020 Type-B robots that perform perception and grasping; and 4040 Type-C robots that perform delivery and grasping. Robots are initially distributed evenly over two bases. Unless otherwise specified, all robots follow a first-order dynamics model with a maximum speed of 2.5m/s2.5\,m/s in simulation. To assess the effect of motion feasibility, both robots with curvature constraints and robots without curvature constraints are considered. The curvature limit is set to 3m−13\,m^-1. There are |t|=5| _t|=5 missions released online at random time instants, with inter-arrival times drawn from a normal distribution with mean μ=32.5sμ=32.5\,s and standard deviation σ=5sσ=5\,s; samples are truncated to positive times. Upon release, mission locations are placed within the workspace according to a spatially uniform distribution. Each mission specified at time tit_i follows the sc-LTL template below: φi=◇(φdeli∧◇φsurvi)∧(¬φcapiφsurvi), _i\;=\; \! ( ^i_ del \, ^i_ surv )\; \; ( \, ^i_ cap\,U\, ^i_ surv ), where the three task types are as follows. A delivery task requires two distinct subtasks to be completed through delivery or grasping actions. A surveillance task requires perception. A dynamic capture task requires two distinct subtasks to be completed through delivery or grasping actions while targets move. Delivery tasks contain on average 1313 subtasks. Surveillance tasks contain on average 1515 subtasks, and each subtask is initially unknown with probability 0.50.5. Capture tasks include approximately 1717 moving targets with speed 0.5m/s0.5\,m/s within the designated region. The global planning horizon is H=6H=6, and replanning is triggered. Replanning occurs upon sufficient execution progress, upon the release or modification of missions, and upon detected infeasibility. Note that operator commands are issued in real-time throughout the simulation, via the proposed protocol. VI-B Results VI-B1 Mission Decomposition and Subteam Formation As shown in Fig. 12, the first mission contains 99 tasks. At release, tasks ω1 _1 through ω4 _4 are delivery, ω7 _7 and ω8 _8 are surveillance, and ω5 _5, ω6 _6, and ω9 _9 are capture. The associated NBA is computed in 0.20s0.20\,s with 77 states and 1818 transitions. Given these task automata, Algorithm 1 optimizes the number of subteams and predicts a makespan of 37.5s37.5\,s when K=5K=5. The computation takes 1.36s1.36\,s. During this process, human intervention request κ1 _1 for new mission release is integrated in real time, where a new task ω3 _3 is added to the set. This process confirms the system adaptability to the online inputs of the operator. This layer validates the top-down design: the global planner reasons on precedence to size coalitions before any motion planning. Then the subteams are instantiated with capabilities matched to the next admissible tasks. The resulting formations are: 0N_0 with 1616 Type-B robots for surveillance tasks ω7 _7 and ω8 _8, 1N_1 with 22 Type-B and 1414 Type-C robots for capture task ω9 _9, 2N_2 with 55 Type-C robots for delivery task ω4 _4, 3N_3 with 55 Type-C robots for delivery task ω2 _2, and 4N_4 with 22 Type-B and 1414 Type-C robots for capture task ω5 _5. This composition reflects the capability coupling in the specification: surveillance requests perception, capture requests grasping or delivery in addition to coordination, and delivery requests transport actions. Figure 14: Evolution of enrolled robots and tasks accomplished, as new missions are specified by φ0−φ10 _0- _10. Top: the number of enrolled robots with different status, including navigation, waiting, and task execution; Bottom: number of remaining tasks that are assigned and unassigned. Execution begins with 3N_3 on ω2 _2 and 4N_4 on ω5 _5. Teams 0N_0, 1N_1, and 2N_2 move to staging locations because the temporal ordering requires ω2 _2 before ω4 _4, ω5 _5 before ω7 _7, and ω4 _4 before ω8 _8. The ordering also allows ω8 _8 and ω9 _9 to proceed concurrently. These temporal constraints promote purposeful staging and prevent premature, infeasible starts. At t=15st=15\,s, teams 3N_3, 4N_4, and 2N_2 complete ω2 _2, ω5 _5, and ω4 _4, respectively, for a total of 4747 finished subtasks. Completion triggers replanning, which costs 0.41s0.41\,s. At this stage, request κ3 _3 for priority change is issued by the operator to execute ω8 _8 due to a deadline adjustment. Since 0N_0 is executing ω7 _7 at that time, the tasks ω8 _8 and ω9 _9 are revisited along with the remaining frontier tasks. Team 0N_0 continues ω7 _7 without interruption, and new teams 5N_5 through 9N_9 are formed to execute ω6 _6, ω3 _3, ω1 _1, ω8 _8, and ω9 _9, respectively. This confirms that the online loop preserves continuity for in-progress work while exploiting newly freed resources. At t=24st=24\,s, the operator issues request κ2 _2 for task cancellation, terminating task ω6 _6 to reflect the updated priorities. Thus, the respective robots in 5N_5 are freed up resources to other tasks in the next replanning. At t=30st=30\,s, a new mission with 55 tasks and 77 relations is released. The global layer replans in 0.44s0.44\,s, produces 55 subteams, and updates the predicted makespan to 51.3s51.3\,s. Note that at t=110st=110\,s, requests κ1 _1 are released to add task ω31 _31 and ω32 _32. Other missions are released at t=60s,100s,130st=60\,s,100\,s,130\,s increase the overall workload to 3232 tasks and 482482 subtasks. Specially, conflicting requests are issued by operator at t=140st=140\,s, where κ3 _3 requests to raise the priority of task ω30 _30 execute, and κ4 _4 requests to assign 1010 Type-C robots to execute ω27 _27. Namely, the available Type-C robots can not meet the capacity requirements of task ω30 _30. Thus, the system shows the conflict to operator and asks which command to execute. The operator chooses κ3 _3, raising the priority of task ω30 _30. In total, the full mission set finishes at 180.4s180.4\,s over 1212 replanning events. The mean task response time is 37.0s37.0\,s, and the mean and max replanning time for 1212 events are 0.36s0.36\,s, 0.87s0.87\,s. The requests continue to be processed, ensuring that dynamic adjustments are smoothly integrated into the execution timeline. Figure 15: Sankey diagram of all robots that participated in the overall mission, along with the number of teams and their compositions. Note that subteams are labeled N0−N49N_0-N_49 and robots are labeled A0−A79A_0-A_79. VI-B2 Local task execution Local execution follows the three strategy classes in Sec. V-C and respects the curvature feasibility shown in Fig. 13. All robot trajectories have curvature below 3m−13\,m^-1. At t=22st=22\,s, the delivery task ω3 _3 includes 1818 static and known subtasks. Team 6N_6 is assigned 88 robots using (20); each robot completes 22 or 33 subtasks under a fixed robot-to-subtask assignment, yielding short traversal and limited coalition changes. During this phase, the operator issues request κ4 _4 for robot reassignment, transferring robot 21 from ω5 _5 to support team 6N_6 in completing subtasks 5,9,165,9,16 of ω3 _3 under resource reallocation. This intention enables rapid cross-task resource redistribution under changing priorities. At t=25st=25\,s, the surveillance task ω7 _7 requires exploration with unknown subtasks. Team 0N_0 follows region-covering trajectories, and newly revealed subtasks are allocated using (21) to minimize route disruption. For example, robot 43 completes subtask 10 and robot 4 completes subtask 12 before resuming exploration. At this point, the operator issues request κ4 _4 for robot reassignment, assigning robot 42 to assist team 0N_0 in completing subtask 9 of ω7 _7. This timely intervention reallocates available capacity to the newly revealed workload, improving execution efficiency. In total, 1616 subtasks are discovered and completed, validating that exploration and execution should interleave to reduce idle time. At t=13st=13\,s, the capture task ω5 _5 comprises 1818 moving subtasks and is executed by team 4N_4 with 2222 robots. Alg. 2 updates local coalitions online as targets move; coalitions dissolve upon subtask completion and robots are reassigned. For instance, robots 60 and 21 complete subtask 0 jointly; robot 60 then completes subtask 10 alone, while robot 21 completes subtask 1 alone. Near completion, robots consolidate into two coalitions to finish subtasks 5 and 8, indicating that additional robots mitigate motion variability and accelerate completion. Across task families, mean response times are 29.39s29.39\,s for delivery, 46.37s46.37\,s for surveillance, and 35.65s35.65\,s for dynamic capture, with local planning times of 0.31s0.31\,s, 0.22s0.22\,s, and 0.50s0.50\,s. VI-B3 Overall Resources Utilization and Adaptation As can be seen in Fig. 14, the status of task execution takes the largest proportion of robot states for whole progress. The proportion of navigation states is acceptable since the whole scene is in shape of rectangular. Waiting states are kept low due to the scheduling strategies. The unassigned tasks in the lower panel spike to 55 after each release and fall to 0 within 15s15\,s, indicating fast adaptation to new tasks. Moreover, the proposed scheme continually reshapes the composition of each team as the mission evolves, as illustrated in Fig. 15. In total 4949 subteams are formed and robots are reused across teams such as robots in N43N_43 later are separated out to form new teams N46N_46 and N47N_47 together with other robots. VI-C Comparisons The proposed method is compared against eight baselines: (I) MILP, where a complete MILP is formulated for all robots N and tasks Ω¯t _t, similar to [41, 33], i.e., without the subteam formation; (I) SAMP-Task, where a sampling-based planner from [20] is adopted for all robots and tasks; (I) SAMP-Subtask, which applies the sampling-based planner directly to subtasks; (IV) ScRATCHeS, which formulates a complete MILP for all robots N and tasks Ω¯t _t, with capacity-based temporal logic formulation [25]; (V) Hulk, which follows poset abstraction of mission automata and task-graph constrained receding-horizon assignment [30]; (VI) Flow, which models precedence-aware coalition task allocation and solves it via network-flow approximations with online re-allocation [14]; (VII) Inf-H, which is the same as our method but with an infinite horizon H, i.e., all known tasks are assigned in Alg. 1; (VIII) Greedy, which assigns a maximum of one task to each subteam, i.e., without the horizon H. The first six baselines are established methods, while the last two are ablation studies. Note that the replanning conditions for all baselines are identical to the proposed method. The compared metrics include the maximum response time for missions, average response time of missions, the average and maximum planning time, the average number of robots performing navigation, waiting for collaboration, and executing tasks, and the success rate. TABLE I: Comparison with Baselines (N=80,M=30,J=450)(N=80,M=30,J=450) Method Resp. Time [s] Ave. Resp. [s] Ave/Max Plan [s] N/W/E Robots Succ. Rate [%] Ours 184.4 34.6 0.46/0.76 19/3/27 100 MILP 327.8 99.1 90.3/144.0 23/7/18 100 SAMP-Task 286.0 72.6 0.45/0.74 24/7/15 100 SAMP-Subtask 230.1 45.6 3.8/8.0 16/5/30 86 ScRATCHeS 257.4 64.9 1.25/7.60 13/3/19 100 Hulk(+poset) 194.4 40.5 4.66/7.59 24/8/24 100 Flow 183.5 41.8 1.79/5.98 31/1/34 96 Inf-H 182.1 77.1 53.4/415.8 23/3/24 100 Greedy 325.7 115.6 0.31/0.56 31/7/30 100 Figure 16: Snapshots of baselines Flow and ScRATCHeS. Left: the subtasks in the red circle are unfinished after t=32st=32s; Right: robots marked in red have long navigation distance due to inefficient assignments. As summarized in Table I, the proposed method outperforms all other methods across most metrics, including response time, planning time, and robot scheduling. Efficiency and Response: HECTOR achieves a total response time of 184.4s184.4\,s, which is significantly lower than most methods like MILP at 327.8s327.8\,s and SAMP-Task at 286.0s286.0\,s, largely owing to the establishment for subteam. While the Inf-H method exhibits a comparable total response time, its maximum planning time can be prohibitively long at 415.8s415.8\,s, demonstrating the inefficiency of an infinite horizon. The Flow based method has a execution success rate of 96%96\% though also exhibiting a comparable response time. Meanwhile, HECTOR maintains a highly stable and efficient planning, with the average and max planning time of 0.46/0.76s0.46/0.76\,s. While some methods exhibit comparable computational efficiency in terms of planning time with SAMP-Task at 0.45/0.74s0.45/0.74\,s and Greedy at 0.31/0.56s0.31/0.56\,s, they suffer from inefficient scheduling of robots or prolonged response times. Reliability and Success Rate: HECTOR and MILP both achieve a 100%100\% success rate, but HECTOR does so with significantly less computational overhead. As shown in Fig. 16, while ScRATCHeS exhibits excellent robot scheduling (13/3/1913/3/19), it falls short in terms of response and planning time. In contrast, SAMP-Subtask and Flow exhibit lower success rates at 86%86\% and 96%96\%, as they do not account for uncertainties in subtasks. Although Greedy remains fast, it results in inefficient robot scheduling (31/7/3031/7/30) and a long response time at 325.7s325.7s. Robustness in Complex Coordination: While SAMP-Subtask struggles with the increased search space of 450450 subtasks, our hierarchical structure effectively decouples the task assignment from intra-team coordination. Though Hulk shows a competitive response time at 194.4s194.4\,s, HECTOR avoids the mission poset establishment for complex temporal tasks, leading to a 1010 times reduction in planning time. TABLE I: Scalability and Robustness Analysis (,,)(N,M,J) Failure ρ Resp. Time [s] Ave/Max Plan [s] N/W/E Robots Succ. Rate [%] (120, 50, 750) 0.05 378.2 0.46/0.82 26/5/27 100 0.10 346.6 0.51/0.79 29/5/25 100 (150, 80, 1202) 0.05 699.1 0.53/0.88 29/3/31 100 0.10 788.3 0.55/0.90 26/7/36 100 (170, 100, 1509) 0.05 923.1 0.65/1.48 30/6/30 100 0.10 1120 0.87/1.65 31/3/29 100 Figure 17: Computational time analysis across the five core modules with varying numbers of robots N and tasks M. VI-D Generalization For further validation, the scalability and robustness of our method are evaluated by increasing the fleet size and introducing robot failures with a probability ρ. The scenarios are scaled from a fleet of 120120 robots with 5050 tasks (released within 240s240\,s), to 150150 robots and 8080 tasks (released within 400s400\,s), to 170170 robots and 100100 tasks (released within 480s480\,s). (I) Scalability. As summarized in Table I, regardless of the failure rate ρ being 0.050.05 or 0.10.1, the average and maximum planning time remain consistently below 2.0s2.0\,s, even as the problem scale grows to 170170 robots and 100100 tasks. This efficiency is primarily attributed to our receding-horizon planning with H=6H=6, which prevents computational explosion with increasing fleet size. When the fleet size and the number of tasks increase to 120120 and 5050, the response time increases by 40%40\% to 57%57\% relative to the total horizon of 240240 seconds. Similarly, with a fleet size of 150150 and 8080 tasks, the response time increases by 75%75\% to 97%97\% relative to the total horizon of 400400 seconds, while the response time increases by 92%92\% to 133%133\% relative to the horizon of 480480 seconds, clearly indicating that the response time scales with the fleet and task sizes, and demonstrating the long-range scheduling of robots in large-scale scenarios. Furthermore, the average number of deployed robots increases as the fleet size and task complexity grow. (I) Failure Recovery. Even with failure probabilities of ρ=0.05ρ=0.05 and 0.10.1, the success rate remains at 100%100\% for fleets of 170170 robots with 100100 tasks and 15091509 subtasks. To recover from these failures, more robots are recruited and the average response time is further increased. The average planing time is only increased slightly with higher failure rate. This shows that the fleet capacities are sufficient to meet the task requirements, even under more challenging conditions. (I) Runtime Decomposition. Fig. 17 reports the runtime of each main module in the proposed framework, including task assignment, team formation, and local coordination, under different fleet sizes |||N| and the numbers of tasks |act||T_act|. It can be seen that task assignment consistently requires more computational time than team formation, with times ranging from approximately 0.35s0.35s to a maximum of 0.55s0.55s as both N and M increase. In contrast, team formation remains relatively stable, typically between 0.05s0.05s and a maximum of 0.1s0.1s. The dynamic and known scenario exhibits the lowest computational times for local coordination strategies, while the static and known case takes longest time at around 0.4s0.4s. Figure 18: Parameter sensitivity and performance analysis of the HECTOR framework: parameter horizon H in assignment (top-left), redundancy margin α in team formation (top-right), the number of finished task in current horizon to trigger the replan (bottom-left), and the curvature κ of robots to plan the trajectories in task coordination (bottom-right). (IV) Sensitivity to Key Parameters. As shown in Fig.18, the sensitivity of the proposed scheme with respect to several key parameters are analyzed. In particular, the analysis of the rolling horizon H reveals that the average replanning time increases from 0.25s0.25s at H=4H=4 to 2.22s2.22s at H=8H=8. The average number of teams during each replan is around 3.93.9, which remains close across different horizons. Moreover, the replan count decreases to 1010 as the triggering condition is increased from 22 to 66. The total replanning time decreases from 9.3s9.3s to 3.5s3.5s, while the response time is increased from 34.0ms34.0ms and 47.8ms47.8ms. Regarding the redundancy margin α, the agents per coalition increase with α, reaching 3232 agents at α=2.0α=2.0, compared to 1717 agents at α=1.1α=1.1. However, the success rate remains 100%100\% across all choice of α. Lastly, as the curvature constraints κ are tightened, the execution costs of local tasks are increased due to tighter dynamic constraints, especially for static and unknown tasks from 25s25s to 180s180s. The success rate remains 100%100\% across all curvatures and tasks, demonstrating its versatility, even for non-holonomic teams. Figure 19: Illustration of the distributed dynamic coalition formation under different communication delays. Top: the ideal scenario without communication delay; Bottom: scenario with stochastic delays ranging from 10110^1 to 102ms10^2\,ms. (V) Communication Constraints. The performance of the distributed dynamic coalition formation under varying communication latencies is evaluated, as shown in Fig. 19. It can be seen that when the communication latency is increased to a stochastic delay ranging from 10110^1 to 102ms10^2\,ms, the proposed algorithm can still ensuring successful task completion. Notably, the resulting robot formation, local plans, and trajectories are drastically different. For instance, robots 2121 and 2020 are assigned to the subtask 0, while subtask 77 is finished by the coalition formed by robots 3434 and 2525 instead of robots 2323 and 6161. The overall task execution time is increased slightly from 31.0s31.0s to 41.2s41.2s. Figure 20: High-fidelity ROS simulation of the proposed framework under the scene for disaster relief. Top-left: 2 UAVs assigned to static known tasks (green), 4 robots to dynamic known tasks (purple), and 6 robots to static unknown tasks (yellow); Middle: the task execution trajectories for 10 tasks over different regions and 3636 subtasks. Bottom-right: the execution timeline of each robot completing assigned tasks in 34.6s\,s on average. VI-E High-fidelity ROS-Simulation VI-E1 Mission and Workspace Setup To validate the proposed framework under more realistic robot dynamics and environment interactions, a ROS-based simulation is conducted for 12 UAVs performing 10 tasks as part of the disaster relief mission, as shown in Fig. 20. The tasks are released in three stages across 3 different missions. Two UAVs are assigned to the static tasks, including the searching for the workshop and storage tank. Four UAVs are allocated to the dynamic tasks, such as transporting relief packages to moving workers. The static tasks include delivering goods and seeding messages to fixed delivery locations. The request κ1 _1 for new task release is issued to add an additional task, ω9 _9, for transporting medical supplies to a new location, prompting a reallocation of resources. When workers make empirical requests to the operator at unexpected locations, the request κ4 _4 for robot reassignment is utilized to reassign UAV 77 from ω7 _7 to assist team 3N_3 with ω6 _6. These interventions ensure the system remains flexible and responsive to dynamic missions. VI-E2 Simulation Results and System Performance As summarized in Fig. 20, the simulation results highlight the effectiveness of the hierarchical coordination framework, with all 1010 tasks and 5050 subtasks successfully completed. The system efficiently handles dynamic task reassignments, with 4 replanning events performed in less than 1s\,s each. The average response time for tasks is 34.6s\,s, and the mean replanning time for 10 events is 0.46s\,s. For static tasks, the average response time is 28.9s\,s, while dynamic capture tasks have a response time of 29s\,s. The multimodal human-fleet interaction protocol allows real-time operator inputs through the GUI, enabling dynamic task modifications. Leveraging external situational awareness, the operator identifies a critical conflict where a routine supply delivery obstructed urgent rescue operations, request κ2 _2 for task cancellation is triggered to cancel ω8 _8 due to a priority shift, freeing resources for higher-priority tasks. Additionally, the request κ3 _3 for deadline modification is used to extend deadlines for ω9 _9 as delays occur due to unforeseen human-induced circumstances. This flexibility ensures seamless task allocation and continuous adaptation to changing task conditions, maintaining smooth execution throughout the mission. VII Conclusion This work presents HECTOR, a hierarchical planning and coordination framework that couples global mission assignment with local subtask and trajectory coordination. It embeds practical human–fleet protocols and a graphic interface for multimodal and online interactions under complex temporal tasks. Future work includes conflicting requests, adversarial settings via game-theoretic reasoning, and tighter integration of communication constraints. References [1] K. R. Apt and A. Witzel (2009) A generic approach to coalition formation. International game theory review 11 (03), p. 347–367. Cited by: Remark 2. [2] C. Baier and J. Katoen (2008) Principles of model checking. MIT press. Cited by: §I-A, §I-B. [3] G. A. Cardona and C. Vasile (2024) Planning for heterogeneous teams of robots with temporal logic, capability, and resource constraints. The International Journal of Robotics Research 43 (13), p. 2089–2111. Cited by: §I-B, Remark 2. [4] Y. Chen, Y. Sun, and B. Englot (2021) Decentralized multi-robot task allocation with uncertain task rewards. Autonomous Robots 45 (5), p. 659–680. External Links: Document Cited by: §I. [5] Z. Chen and Z. Kan (2025) Real-time reactive task allocation and planning of large heterogeneous multi-robot systems with temporal logic specifications. The International Journal of Robotics Research 44 (4), p. 640–664. Cited by: §I-A, §I-B, §I-B, TABLE I, §V-B1, Remark 2. [6] S. Choudhury, S. Arora, A. Kapoor, and D. Dey (2017) Dynamics-aware multi-robot task allocation with deadlines. Robotics: Science and Systems (RSS). Cited by: §I. [7] A. Dahiya et al. (2023) A survey of multi-agent human–robot interaction systems. Robotics and Autonomous Systems 161, p. 104335. External Links: Document Cited by: §I, §I-C. [8] W. Dai, A. Bidwai, and G. Sartoretti (2024) Dynamic coalition formation and routing for multirobot task allocation via reinforcement learning. In IEEE International Conference on Robotics and Automation (ICRA), p. 16567–16573. Cited by: §I-A, §V-C3. [9] S. Erke, D. Bin, N. Yiming, Z. Qi, X. Liang, and Z. Dawei (2020) An improved a-star based path planning algorithm for autonomous land vehicles. International Journal of Advanced Robotic Systems 17 (5). Cited by: §V-C1. [10] J. Ferreira and P. Lima (2021) A survey of human–multi-robot interaction. Robotics and Autonomous Systems 144, p. 103837. External Links: Document Cited by: §I, §I, §I-C, Remark 2, Remark 3. [11] F. Fioretto, E. Pontelli, and W. Yeoh (2018) Distributed constraint optimization problems and applications: a survey. Journal of Artificial Intelligence Research 61, p. 623–698. External Links: Document Cited by: §I-A, Remark 3. [12] M. Gini (2017) Multi-robot allocation of tasks with temporal and ordering constraints. In AAAI Conference on Artificial Intelligence, Cited by: §I-A. [13] M. Gombolay, R. Wilcox, and J. A. Shah (2017) Computational design of mixed-initiative human–robot teaming. Journal of Artificial Intelligence Research 57, p. 389–452. External Links: Document Cited by: §I-C. [14] W. Gosrich, S. Agarwal, K. Garg, S. Mayya, M. Malencia, M. Yim, and V. Kumar (2025) Online multi-robot coordination and cooperation with task precedence relationships. IEEE Transactions on robotics. Cited by: §I-B, TABLE I, §VI-C. [15] J. Guerrero and G. Oliver (2012) Multi-robot coalition formation in real-time scenarios. Robotics and Autonomous Systems 60 (10), p. 1295–1307. Cited by: §V-C3. [16] D. Holz, N. Basilico, F. Amigoni, and S. Behnke (2010) Evaluating the efficiency of frontier-based exploration strategies. In International Symposium on Robotics, p. 1–8. Cited by: §V-C2. [17] R. Hoque, L. Y. Chen, S. Sharma, K. Dharmarajan, B. Thananjeyan, P. Abbeel, and K. Goldberg (2022) Fleet-dagger: interactive robot fleet learning with scalable human supervision. In Conference on Robot Learning (CoRL), Cited by: §I, §I, §I-C. [18] Y. Ji, X. Li, and X. Yang (2021) Multi-robot task allocation with time and resource constraints. Robotics and Autonomous Systems 136, p. 103711. External Links: Document Cited by: §I-A, Remark 3. [19] Y. Kantaros, S. Kalluraya, Q. Jin, and G. J. Pappas (2022) Perception-based temporal logic planning in uncertain semantic maps. IEEE Transactions on Robotics 38 (4), p. 2536–2556. Cited by: §I-B. [20] Y. Kantaros and M. M. Zavlanos (2020) Stylus*: a temporal logic optimal control synthesis algorithm for large-scale multi-robot systems. The International Journal of Robotics Research 39 (7), p. 812–836. Cited by: §I, §I-B, §I-B, TABLE I, §V-B1, §VI-C, Remark 2, Remark 3, Remark 5. [21] A. Kolling, P. Walker, N. Chakraborty, K. Sycara, and M. Lewis (2016) Human interaction with robot swarms: a survey. IEEE Transactions on Human-Machine Systems 46 (1), p. 9–26. External Links: Document Cited by: §I-C, §V-A3. [22] M. Križmančić, B. Arbanas, T. Petrović, F. Petrić, and S. Bogdan (2022) Cooperative aerial–ground multi-robot system for automated construction tasks. Automation in Construction 141, p. 104469. External Links: Document Cited by: §I, Remark 2. [23] V. Kurtz and H. Lin (2021) A more scalable mixed-integer encoding for metric temporal logic. IEEE Control Systems Letters 6, p. 1718–1723. Cited by: §I-B, §V-B2. [24] M. Lahijanian, S. B. Andersson, and C. Belta (2015) Temporal logic motion planning and control with probabilistic satisfaction guarantees. IEEE Transactions on Robotics 31 (3), p. 546–561. External Links: Document Cited by: §I-B. [25] K. Leahy, Z. Serlin, C. Vasile, A. Schoer, A. M. Jones, R. Tron, and C. Belta (2021) Scalable and robust algorithms for task-based coordination from high-level specifications (scratches). IEEE Transactions on Robotics 38 (4), p. 2516–2535. Cited by: §I-A, §I-B, §I-B, TABLE I, §VI-C, Remark 2. [26] L. Li, Z. Chen, H. Wang, and Z. Kan (2025) Task allocation of heterogeneous robots under temporal logic specifications with inter-task constraints and variable capabilities. IEEE Transactions on Automation Science and Engineering. Cited by: §I-B. [27] L. Lindemann, J. Nowak, L. Schönbächler, M. Guo, J. Tumova, and D. V. Dimarogonas (2019) Coupled multi-robot systems under linear temporal logic and signal temporal logic tasks. IEEE Transactions on Control Systems Technology 29 (2), p. 858–865. Cited by: §I-B, §V-B1. [28] H. Liu, M. Li, and X. Li (2019) Multi-robot task allocation with evolutionary algorithms: a comparative study. Applied Soft Computing 81, p. 105511. External Links: Document Cited by: §I-A. [29] Z. Liu, M. Guo, and Z. Li (2024) Time minimization and online synchronization for multi-agent systems under collaborative temporal logic tasks. Automatica 159, p. 111377. Cited by: §I-B, §V-B1, Remark 1, Remark 5, Remark 5. [30] Q. Luo, J. Li, and M. Guo (2025) HULK: large-scale hierarchical coordination under continual and uncertain temporal tasks. In IEEE International Conference on Robotics and Automation (ICRA), Cited by: §I-B, TABLE I, §VI-C, Remark 5, Remark 5. [31] X. Luo and C. Liu (2025) Simultaneous task allocation and planning for multi-robots under hierarchical temporal logic specifications. IEEE Transactions on Robotics. Cited by: §I-B, TABLE I, §V-B1, Remark 5. [32] X. Luo, S. Xu, R. Liu, and C. Liu (2024) Decomposition-based hierarchical task allocation and planning for multi-robots under hierarchical temporal logic specifications. IEEE Robotics and Automation Letters 9 (8), p. 7182–7189. Cited by: §I-A, §I-B, Remark 2. [33] X. Luo and M. M. Zavlanos (2022) Temporal logic task allocation in heterogeneous multirobot systems. IEEE Transactions on Robotics 38 (6), p. 3602–3621. Cited by: §I-B, §V-B1, §VI-C, Remark 2, Remark 5. [34] J. G. Martin, J. R. D. Frejo, R. A. García, and E. F. Camacho (2021) Multi-robot task allocation problem with multiple nonlinear criteria using branch and bound and genetic algorithms. Intelligent Service Robotics 14 (3), p. 707–727. External Links: Document Cited by: §I-A. [35] J. Ny, E. Feron, and E. Frazzoli (2011) On the dubins traveling salesman problem. IEEE Transactions on Automatic Control 57 (1), p. 265–270. Cited by: §V-C1. [36] Y. E. Sahin, P. Nilsson, and N. Ozay (2019) Multirobot coordination with counting temporal logics. IEEE Transactions on Robotics 36 (4), p. 1189–1206. Cited by: §I-B, §I-B, TABLE I, §V-B2, Remark 1, Remark 3. [37] P. Schillinger, M. Bürger, and D. V. Dimarogonas (2018) Simultaneous task allocation and planning for temporal logic goals in heterogeneous multi-robot systems. The International Journal of Robotics Research 37 (7), p. 818–838. Cited by: §I-B, §V-B1, Remark 3, Remark 5. [38] S. L. Smith and F. Bullo (2009) Dynamic task allocation in multi-robot systems. Proceedings of the IEEE 94 (7), p. 1272–1286. Cited by: §I. [39] G. L. O. Solver Note: https://developers.google.com/optimization/lp Cited by: §V-B2, §V-C1, §VI. [40] G. Swamy, S. Reddy, S. Levine, and A. Dragan (2020) Multi-robot allocation of assistance from a shared uncertain human supervisor. In IEEE International Conference on Robotics and Automation (ICRA), p. 6409–6415. Cited by: §I, §I-C, Remark 3. [41] A. Torreño, E. Onaindia, A. Komenda, and M. Štolba (2017) Cooperative multi-agent planning: a survey. ACM Computing Surveys (CSUR) 50 (6), p. 1–32. Cited by: §I-A, §VI-C, Remark 3. [42] E. Tuci et al. (2018) Cooperative object transport in multi-robot systems. Frontiers in Robotics and AI 5, p. 59. External Links: Document Cited by: §I. [43] J. Tumova, A. Marzinotto, D. V. Dimarogonas, and D. Kragic (2014) Maximally satisfying ltl action planning. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), p. 1503–1510. Cited by: §I-C. [44] A. Ulusoy, S. L. Smith, X. C. Ding, C. Belta, and D. Rus (2013) Optimality and robustness in multi-robot path planning with temporal logic constraints. The International Journal of Robotics Research 32 (8), p. 889–911. Cited by: §I-C. [45] P. Váňa and J. Faigl (2015) On the dubins traveling salesman problem with neighborhoods. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), p. 4029–4034. Cited by: §V-C1. [46] A. Varava, K. Hang, D. Kragic, and F. T. Pokorny (2017) Herding by caging: a topological approach towards guiding moving agents via mobile robots.. In Robotics: Science and Systems, p. 696–700. Cited by: §I. [47] Y. You et al. (2021) Human-multi-robot interaction: a survey. Foundations and Trends in Robotics 9 (2), p. 59–170. External Links: Document Cited by: §V-A3. [48] S. Zhao, Y. Shen, and Y. Ding (2021) Market-based task allocation for multi-robot systems with uncertain task rewards. IEEE Robotics and Automation Letters 6 (2), p. 3053–3060. External Links: Document Cited by: §I-A, Remark 3. [49] L. Zhou, V. Tzoumas, G. J. Pappas, and P. Tokekar (2018) Resilient active target tracking with multiple robots. IEEE Robotics and Automation Letters 4 (1), p. 129–136. Cited by: §V-C3. TABLE IV: Nomenclature of Key Variables and Definitions Term Definition Reference Φt _t Set of missions known at time t>0t>0. Sec. V-B τi _i Local plan of robot i∈i . Sec. IV-A =κ1,2,3,4K=\ _1,2,3,4\ Operator requests. Sec. IV-B ℬφmB_ _m Büchi automaton for mission φm _m. Sec. V-B Q^m Q_m Set of reachable states in automaton ℬφmB_ _m. Sec. V-B T Search tree structure defined as (,→)(V,→). Sec. V-B χ(ν)χ(ν) Value function for node selection. Eq. (6) kC_k Capacity constraints for team k. Sec. V-B βkjβ^j_k Min. robots required to perform action aja^j for team k. Eq. (7) αj _j Redundancy margin for workload uncertainty and failures. Sec. V-B ζ(ν)ζ(ν) Performance profile for node evaluation and pruning. Eq. (13) ¯ V Set of non-dominated frontier nodes in the search tree. Eq. (15) H Planning horizon for task assignment. Sec. V-B bikb_ik Robot i assigned to team kN_k. Sec. V-B J(k)J(k) Execution cost of team k. Sec. V-B NkN_k Robots in team k. Sec. V-B kℓJ _k Set of local tasks for the ℓ -th task of team k. Sec. V-C ix_i Trajectory of robot i∈i . Sec. V-C -A Proof of Lemmas and Theorems Proof. of Theorem 1. Temporal correctness follows from the update of the reachable state sets Q^m Q_m along enabled automaton transitions qmℓ+1∈δm(qmℓ,ωℓ+1)q_m +1∈δ^m(q_m ,ω +1) and from the completeness condition Q^m∩QFm≠∅ Q_m∩ Q_F^m≠ in (16). Any root to leaf path that ends at a node ν∈¯⋆ν∈ V therefore induces, for every m∈ℳm , an accepting run of ℬφmB_ _m, so the joint plans Γk\ _k\ satisfy all temporal constraints encoded by ℬφm\B_ _m\. Moreover, the capacity feasibility and finite time convergence follow from local pruning and finiteness of the search space. Each expansion step updates kC_k and enforces the fleet constraint ∑k∈βkj≤∑i∈(aj∈i) _k _k^j≤ _i 1(a^j _i), hence any node in ¯⋆ V respects all capacity bounds. The set Φt _t, the automaton state sets QmQ^m, the alphabets Σm ^m, the total number of tasks Ω , and the admissible team compositions are finite, so the set of feasible nodes is finite. Dominance pruning does not remove all representatives of any feasible solution class, and a fair selection rule eventually expands every feasible non-dominated node. For a feasible problem, at least one complete non-dominated node ν∈¯⋆ν∈ V is therefore generated in finite time, which yields plans that satisfy all missions and all capacities. Lastly, given the objective function (6) and enough planning time, the node with the minimum cost as in (5) would be returned, which also satisfies each mission requirement at the accepting states. This completes the proof. ∎ Proof. of Lemma 2. Similar to the previous case of known tasks, since each node ν explicitly tracks reachable states Q^m Q_m and transitions δmδ^m, and expansion strictly enforces the capacity bounds in (8), the partial plans are inherently consistent with the mission specification and capability constraints. Moreover, the receding-horizon handover during re-planning uses the final state of H as the next root ν0 _0, ensuring the execution sequence remains a valid prefix toward the accepting sets QFm\Q_F^m\. Thus, the accumulated trace of all robots satisfies the mission requirement φm _m once an accepting state qk∈QFmq_k∈ Q^m_F is reached. However, it is worth noting that global optimality is lost because the limited horizon H and online mission updates prevent the tree search from considering the complete set of all future tasks. ∎ Proof. of Theorem 3. In the static and known case, the task reduces to an MVRP, where the trajectory of each robot i∈ki _k is optimized to minimize the makespan JkℓJ_k . For non-holonomic robots, the problem is augmented with motion primitives κ(xj1,xj2)κ(x_j_1,x_j_2) to ensure feasible trajectories, with the overall objective to minimize JkℓJ_k under trajectory constraints. In the static and unknown case, exploration ensures all subtasks kℓJ_k are discovered, and the makespan maxi∈kTimax_i _kT_i is minimized as new subtasks are dynamically inserted. In the dynamic and known case, coalition updates are driven by the cost function χ(ℛj)χ(R_j) for each coalition ℛjR_j, and the switch condition ensures that robots only switch coalitions if it reduces the overall team cost χ(ℛ¯t)χ( R_t). The process converges to a locally optimal configuration, minimizing the makespan maxk∈J(k)max_k J(k). ∎