Paper deep dive
HULK: Large-scale Hierarchical Coordination under Continual and Uncertain Temporal Tasks
Qingyuan Luo, Jie Li, Meng Guo
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 7/8/2026, 12:16:25 PM
Summary
The paper introduces HULK, a hierarchical coordination framework designed for large-scale multi-agent systems operating under continual, online-released tasks with uncertain subtasks. Unlike static offline methods, HULK employs a two-layer approach: a receding-horizon task assignment algorithm that allocates tasks to subteams based on sc-LTL constraints, and a local coordination algorithm that dynamically manages subtasks during execution. The framework utilizes posets for task ordering and MILP for subteam formation, demonstrating improved computational efficiency and robustness in heterogeneous, uncertain environments.
Entities (9)
Relation Signals (10)
Qingyuan Luo → affiliatedwith → Peking University
confidence 96% · Qingyuan Luo1... The authors are with 1the Department of Mechanics and Engineering Science, College of Engineering, Peking University
Jie Li → affiliatedwith → National University of Defense Technology
confidence 96% · Jie Li2... and 2National University of Defense Technology, Hunan 410073, China.
Meng Guo → affiliatedwith → Peking University
confidence 96% · Meng Guo1... Contact: meng.guo@pku.edu.cn
Paper → fundedby → NSFC
confidence 95% · This work was supported by the National Natural Science Foundation of China (NSFC) under grants 62203017, T2121002, U2241214
HULK → solves → Multi-agent Systems coordination problem
confidence 95% · Thus, this work tackles the large-scale coordination problem under continual and uncertain temporal tasks... The proposed hierarchical framework, HULK, consists of two interleaved layers
HULK → consistsof → Receding-horizon Task Assignment
confidence 94% · the proposed method is based on the hierarchical coordination framework (HULK) that combines the global task assignment and the local subtask coordination.
HULK → consistsof → Local Coordination Algorithm
confidence 93% · Afterwards, each subteam follows different local strategies, where subtasks are detected and assigned dynamically during execution.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Multi-agent systems can be extremely efficient when working concurrently and collaboratively, e.g., for delivery, surveillance, search and rescue. Coordination of such teams often involves two aspects: selecting appropriate subteams for different tasks in various areas, and coordinating agents in the subteams to execute the associated subtasks. Existing work often assumes that the tasks are static and known beforehand, where an integer program can be formulated and solved offline. However, in many applications, the team-wise tasks are generated online continually by external requests, and the amount of subtasks within each task is uncertain, e.g., the number of packages to deliver or victims to rescue. The aforementioned offline solution becomes inadequate as it would require constant re-computation for the whole team and global communication to broadcast the results. Thus, this work tackles the large-scale coordination problem under continual and uncertain temporal tasks, specified as temporal logic formulas over collaborative actions. The proposed hierarchical framework, HULK, consists of two interleaved layers: the rolling assignment of currently known tasks to subteams within a certain horizon, and the dynamic coordination within a subteam given the detected subtasks during online execution. Thus, coordination is performed hierarchically at different granularities and triggering conditions, improving computational efficiency and robustness. The method is validated rigorously over large-scale heterogeneous systems under various temporal tasks and environment uncertainties.
Tags
Links
- Source: https://arxiv.org/abs/2605.08722v1
- Canonical: https://arxiv.org/abs/2605.08722v1
Trouble viewing inline? Open PDF directly →
Full Text
45,241 characters extracted from source content.
Expand or collapse full text
HULK: Large-scale Hierarchical Coordination under Continual and Uncertain Temporal Tasks Qingyuan Luo1, Jie Li2 and Meng Guo1 The authors are with 1the Department of Mechanics and Engineering Science, College of Engineering, 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 62203017, T2121002, U2241214; 2030-Key Project under Grant 2020A0108200; and by the Fundamental Research Funds for the central universities. Contact: meng.guo@pku.edu.cn. Abstract Multi-agent systems can be extremely efficient when working concurrently and collaboratively, e.g., for delivery, surveillance, search and rescue. Coordination of such teams often involves two aspects: (i) selecting appropriate subteams for different tasks in various areas; (i) coordinating agents in the subteams to execute the associated subtasks. Existing work often assumes that the tasks are static and known beforehand, where an integer program can be formulated and solved offline. However, in many applications, the team-wise tasks are generated online continually by external requests; and the amount of subtasks within each task is uncertain (e.g., the number of packages to deliver, and victims to rescue). The aforementioned offline solution becomes inadequate as it would require constant re-computation for the whole team and global communication to broadcast the results. Thus, this work tackles the large-scale coordination problem under continual and uncertain temporal tasks, specified as temporal logic formulas over collaborative actions. The proposed hierarchical framework (HULK) consists of two interleaved layers: the rolling assignment of currently-known tasks to sub-teams within a certain horizon, and the dynamic coordination within a sub-team given the detected subtasks during online execution. Thus, the coordination is performed hierarchically at different granularities and triggering conditions, to improve the computational efficiency and robustness. It is validated rigorously over large-scale heterogeneous systems under various temporal tasks and environment uncertainties. I Introduction Fleets of heterogeneous robots, such as ground vehicles and aerial vehicles, are deployed to accomplish tasks that are otherwise too inefficient or even infeasible for a single robot [2]. Not only the overall efficiency of the team can be significantly improved by allowing the robots to move and act concurrently [33, 7]; but also the capabilities of the team can be greatly extended by enabling multiple robots to directly collaborate on a task [9, 35]. However, the optimal coordination of a large-scale multi-agent system to accomplish the desired task is well-known to be hard, especially to fulfill the spatially distributed subtasks in the right order at the right time. The set of possible task assignments are often combinatorial with respect to the number of robots and the length of tasks [2, 33, 18]. Commonly such a team-wise task is specified beforehand and remains unchanged, of which the solutions are derived offline and thus static. A particularly challenging scenario is when the system operates indefinitely, i.e., new tasks are released or canceled dynamically and continually by external demand, thus requiring the agents to change their task plans frequently. The aforementioned methods become inadequate as the sequence of tasks is infinite and their specifications are unknown beforehand. Recursive application of the static methods in a naive way leads to not only intractable computation complexity, but also inconsistent or even oscillatory assignments. I-A Related Work Figure 1: Overall framework, including: snapshots of online execution of three types of tasks, which contains numerous subtasks (top); the posets associated with missions that are released online (middle); and the receding-horizon assignment of tasks to optimized formation of teams (bottom). Task planning refers to the process of first decomposing this task into sub-tasks and then assigning them to the team, see [32, 11, 19] for comprehensive surveys. Different optimization criteria can be chosen, such as MinSUM [11]; and MinMAX [27]. The tasks can be specified in various forms, such as in the multi-vehicle routing problem [19], the job-shop problem [5]; and the coalition formation problem [25]. Existing methods can be categorized into centralized methods such as mixed integer linear programming (MILP) [32] and search-based methods [10]; and decentralized methods such as market-based methods [23] and distributed constraint optimization (DCOP) [4]. However, since many task planning problems are in general NP-hard or even NP-complete [11], meta-heuristic approaches are used to gain computational efficiency, e.g., local search [15] and genetic algorithms [19]. However, most of the aforementioned methods can not be applied directly in this work due to the general task specification as temporal logic formulas over collaborative actions. Additionally, the aforementioned methods often focus on solving a static problem, rather than the continual and dynamic scenario addressed in this work. Temporal logic formulas can be used to specify complex robotic tasks, such as Probabilistic Computation Tree Logic (PCTL) in [20], Linear Temporal Logics (LTL) in [18, 29, 24, 16, 12, 34], and counting LTL (cLTL) in [28]. Considerable results are developed in the recent years regarding the task assignment problem of team-wise tasks specified as temporal logic formulas. Analogously, they can be categorized into centralized methods and decentralized methods. Centralized methods often put emphases on optimality and completeness, such as the sampling-based search algorithm [18], the simultaneous decomposition and assignment method [29], the MILP formulation [24, 28, 16]. Decentralized methods are more applicable to large-scale multi-agent systems, including the local coordination of local tasks [12, 34, 13], the local assignment under partial workspace [26], the distributed sampling method [17], and the online auction algorithm [30]. However, the scenario where new tasks are released online with uncertain subtasks is rarely addressed in the aforementioned work, as it would require online adaptation for both the global task assignment and the local subtask execution. I-B Our Method To tackle these issues, this work put strong emphases on the online coordination algorithm that are essential when the collaborative tasks are released continually, and the amount of subtasks within each task is uncertain. In other words, both the distribution and requirements of the tasks can only be known during online execution. As shown in Fig. 1, the proposed method is based on the hierarchical coordination framework (HULK) that combines the global task assignment and the local subtask coordination. Namely, the global mission specification is first decomposed into collaborative tasks with the associated temporal constraints. Then, a receding-horizon assignment algorithm is applied to assign these collaborative tasks to subteams of the agents, subject to resources requirements, navigation cost and ordering constraints. Afterwards, each subteam follows different local strategies, where subtasks are detected and assigned dynamically during execution. Online adaptation at both levels is triggered by external events and execution status. Efficiency and robustness of the proposed framework is validated rigorously over large-scale heterogeneous systems and three different temporal tasks. Main contribution of this work is threefold: (I) The proposed hierarchical coordination algorithm is applicable to a wide range of formulations, such as heterogeneous agents, temporal tasks and collaborative actions; (I) It is robust to varying distribution of continual tasks, contingent agent failures and uncertain subtasks; and (I) It is computationally efficient and scalable to large-scale systems. I Problem Description I-A Multi-agent Systems Consider a team of N agents that share the common workspace ⊂ℝ3W ^3. Each agent i∈≜1,⋯,Ni \1,·s,N\ is described by its position xi∈ix_i _i and its action ai∈ia_i _i, where i⊆W_i is the allowed workspace; and iA_i is the set of primitive actions such as surveillance, delivery, capture and defense. Each agent can navigate freely in the workspace via a reference velocity vi∈ℝ3v_i ^3. Thus, the local plan of an agent is given by a sequence of timed goal positions and performed actions, i.e., τi≜(ti1,gi1,ai1)(ti2,gi2,ai2)⋯ _i (t^1_i,\,g^1_i,\,a^1_i)(t^2_i,\,g^2_i,\,a^2_i)·s with tiℓ≥0t _i≥ 0, giℓ∈ig _i _i, aiℓ∈ia_i _i being the time instant, goal position and action, ∀ℓ≥1∀ ≥ 1. In other words, under this local plan, agent i∈i should navigate to giℓg_i with velocity viv_i and start performing aiℓa_i from time tiℓt_i , for all ℓ≥1 ≥ 1. I-B Mission Specifications At time t≥0t≥ 0, a temporal mission is released (e.g., by a human operator or triggered by an event) to the fleet, denoted by φt≜sc-LTL(t) _t -LTL ( ω_t ), where: (I) t≜ω1,⋯,ωMt ω_t \ _1,·s, _M_t\ is the set of collaborative tasks within the mission. Each collaborative task ωm∈t _m∈ ω_t is denoted by: ωm≜(Sm,ηm,(nj,aj,sj),j=1,⋯,Jm), _m (S_m,\, _m,\, \ (n_j,\,a_j,\,s_j ),j=1,·s,J_m \ ), (1) where Sm⊂S_m is the area that the task should be accomplished; (nj,aj,sj)(n_j,a_j,s_j) is a subtask that requires at least njn_j agents performing action aja_j collaboratively at location sj∈Sms_j∈ S_m; Jm>0J_m>0 is the total number of subtasks within the task ωm _m; and the estimated duration of each subtask is given by function ηm:ℕ×2→ℝ+ _m:N×A× 2^N ^+, i.e., ηm(nj,aj,j) _m(n_j,\,a_j,\,N_j) returns the duration if the subteam of agents j⊂N_j is assigned to provide the required action aja_j at location sjs_j. Thus, task ωm _m is accomplished after each subtask is completed; (I) The tasks ωm _m are nested following the syntax of Linear Temporal Logic (LTL) [3], e.g., via φ≜⊤|p|φ1∧φ2|¬φ|○φ|φ1Uφ2, \;|\;p\;|\; _1 _2\;|\; \;|\; \;|\; _1\, U\, _2, where ⊤≜True True, p∈APp∈ AP, ○ (next), U (until) and ⊥≜¬⊤ . or other derived operators like □ (always), ◇ (eventually), ⇒ (implication). The full semantics and syntax of syntactic co-safe LTL (sc-LTL) are omitted here for brevity, see e.g., [3]. Consequently, the temporal mission φt _t is satisfied if all collaborative tasks are accomplished, while the resulting trace of their temporal ordering satisfies the sc-LTL formula φt _t via the satisfaction relation ⊧ from [3]. Lastly, the accumulated missions up to time t≥0t≥ 0 are denoted by t≜φtℓ,∀tℓ≤t _t \ _t_ ,\,∀ t_ ≤ t\. It is worth mentioning that the tasks ωm\ _m\ in (1) can be uncertain, i.e., the exact number of subtasks JmJ_m and their locations sj\s_j\ are unknown at the time of release. This might be due to the partial observability or dynamic nature of the environment. Remark 1. The definition of collaborative task in (1) differs from the notion of cLTL [28] in two aspects: (I) Both the location and number of subtasks are uncertain; (I) The duration of all subtasks can vary depending on the assigned agents, i.e., instead of being instantaneous [22]. ■ Remark 2. The duration function ηm(⋅) _m(·) typically saturates as the number of participants increases, i.e., the marginal benefits diminishes as also adopted in [1, 6]. ■ I-C Problem Statement Given the above model, the overall objective is to synthesize the collective plans τi\ _i\ such that the average response of each mission is minimized, i.e., τi∑φtℓ∈t(tℓf−tℓ)|t|,min_\ _i\\, _ _t_ ∈ _t(t_ f-t_ )| _t|, (2) where 0≤tℓ≤tℓf0≤ t_ ≤ t f_ are the time instants when the mission φtℓ∈t _t_ ∈ _t is released and accomplished, respectively. I Proposed Solution The proposed solution consists of two main components: (I) The receding-horizon task planning algorithm that assigns tasks to subteams of agents given the global mission specification and constraints on the resources; (I) The local coordination algorithm that assigns subtasks to agents during online execution. The synergy and adaptation of both components are triggered by external events and execution status. I-A Receding-horizon Task Assignment I-A1 Decomposition of Temporal Tasks Given the mission specification φ , the NBA associated with φ is denoted by ℬ=(Q,Q0,Σ,δ,QF)B=(Q,\,Q_0,\, ,\,δ,\,Q_F), of which the notation follows [3]. Based on ℬB, the associated tasks and their partial temporal constraints can be computed based on our earlier work [22, 21], as posets over tasks, i.e., Ωφ≜(Ω,⪯,≃), _ \( ,\, ,\, ) \, (3) where Ω≜ω1,⋯,ωM⊂Σ \ _1,·s, _M\⊂ is a set of tasks; the partial ordering constraints ⪯,≃⊂Ω×Ω ,\, ⊂ × such that: (I) ωm1⪯ωm2 _m_1 _m_2 if task ωm1 _m_1 should be accomplished before task ωm2 _m_2 is started; (I) ωm1≃ωm2 _m_1 _m_2 if tasks ωm1 _m_1 and ωm2 _m_2 should start at the same time. Simply speaking, the posets are abstracted from the mission automaton as the set of possible ways to satisfy the mission, as the set of tasks involved and their temporal relations. This allows more parallel execution during assignment thus improving efficiency. Detailed algorithms and completeness analyses can be found in [22]. As the missions can be specified online, the set of missions by time t>0t>0 is given by t _t, each of which can be decomposed into the partially-ordered tasks. Consequently, the set of all known and unfinished tasks by time t is given by: Ω¯t≜⋃φi∈tΩφi _t _ _i∈ _t\, _ _i, where Ωφi _ _i is the partially-ordered tasks associated with mission φi∈t _i∈ _t as defined in (3). Note that the tasks from different missions are assumed to be independent. Moreover, given Ω¯t _t, a directed acyclic task graph tG_t can be constructed for these tasks based on their partial ordering, i.e., each node in the graph represents a task in Ω¯t _t, and the edges represent the precedence and concurrence constraints. I-A2 Capacity-based Task Assignment for Subteams Given the temporal constraints on simultaneous execution and the objective to minimize response time, the agents need to be divided into subteams for parallel execution. However, due to limitations in the number and capacity of the agents, it is not feasible to create a subteam for each individual task, rather a subteam is assigned a sequence of tasks based on agent capacity and the requirements of the tasks. Denote by ν≜k,k=1,⋯,Kν \C_k,\,k=1,·s,K\ the set of partial assignments along with the capacity constraints for each subteam, where each local assignment is given by: k≜((ωk0,⋯,ωkLk),(mkj,akj),akj∈),C_k ( ( _k^0,·s, _k^L_k ), \(m^j_k,\,a^j_k),\,a^j_k \ ), (4) of which the first part is the sequence of tasks assigned to the k-th subteam, LkL_k is the total number of tasks in the sequence, while the second is the minimum number of agents mkjm^j_k to perform action akja^j_k. Note that the number of subteams K is not pre-defined and to be optimized. Input: Robots N, tasks t _t, horizon H. Output: Assignment νK⋆\ _K \, subteams k\N_k\, and local plans ξi\ _i\. /* Task Assignment */ 1 Compute posets Ω¯t _t for t _t by (3); 2 Build task graph tG_t given Ω¯t _t; 3 Initialize ⋆=∅V = ; 4 for K∈ℋK do 5 Compute optimal assignment νK⋆ν _K via (7); 6 Add νK⋆ν _K to ⋆V ; 7 8Choose best νK⋆ν _K among ⋆V by (7); /* Subteam Formation */ 9 Compute cost matrix tik\t_ik\ by (8); 10 Formulate and solve MILP problem to find bik\b_ik\; 11 Compute local plans ξi\ _i\ by (9); Algorithm 1 Task Assign. and Subteam Format. Consider that H>0H>0 tasks should be assigned within the task graph tG_t. A search-based algorithm is proposed to determine the optimal subteam assignment ν⋆ν . As summarized in Alg. 1, starting from the root node as the empty assignment ν0 _0, the selected node is expanded by adding the next feasible task to any of the subteam. In particular, the assignment for the set of tasks that are currently being executed remains unchanged, while the rest of the tasks within tG_t can be added if their preceding tasks are fulfilled or being executed. More importantly, after adding ωkLkω^L_k_k to the subteam k, the capacity constraint is updated as follows: mkj≜maxakj∈ωkℓ∈knj,∀akj∈;m^j_k a^j_k∈ω _k _kmax\n_j\,\;∀ a^j_k ; (5) i.e., the maximum number of agents mkjm^j_k required for each action akja^j_k across the sequence of task ωkℓω _k. The search is terminated when the number of assigned tasks for the fleet reaches the horizon H, or the capacity constraints are violated, i.e., ∑k∈mkj≤∑i∈(akj∈i),∀akj∈; _k m^j_k≤ _i 1(a^j_k _i),\;∀ a^j_k ; (6) where the left-side is the resources required by the assignment, and the right-side is the complete capacity of the fleet. Lastly, the optimal assignment is selected from the complete tree by evaluating the overall quality of each node, i.e., ξ(ν)≜ηLk(ν,Ω¯t)+maxk∈te(ωkLk);te(ωkℓ)≜(maxωj∈Pre(ωkℓ)te(ωj))+Tnav(Skℓ−1,Skℓ), splitξ(ν)& _L_k(ν,\, _t)+ k max\, \t_ e( _k^L_k) \;\\ t_ e( _k )& ( _j∈ Pre( _k )max \t_ e( _j) \ )+T_ nav(S_k -1,S_k ), split (7) where te(ωkℓ)t_ e(ω _k) is the estimated ending time of ωkℓ∈kω _k _k; Pre(ωkℓ) Pre( _k ) is set of preceding tasks in the task graph tG_t; Tnav(Skℓ−1,Skℓ)T_ nav(S_k -1,S_k ) is the estimated navigation time from the previous task region Skℓ−1S_k -1 to the current task region SkℓS_k ; and η(ν,Ωt)η(ν,\, _t) is the estimated progress achieved by the assignment ν w.r.t. the unfinished tasks. Denote by νK⋆ν _K the optimal assignment for K subteams. The same search procedure is repeated for different choices of K∈ℋ≜1,⋯,HK \1,·s,H\, for which the set of optimal assignments is given by ⋆≜νK⋆,K∈ℋV \ν _K,\,K \. Within this set, the same measure as in (7) is adopted to select the best choice of K as K⋆K and the associated assignment νK⋆ν _K . It is worth noting that the subteams k∈νK⋆\C_k\∈ν _K only specify the constraints on capacity, rather than specific agents. Remark 3. Note that various heuristics can be applied to prune the search space, e.g., elimination of symmetric nodes; removing branches if its root node is worse than the current best node. More numeric details are given in the Sec. IV. ■ I-A3 Redundancy-aware Subteam Formation Given the optimal task assignment for subteams νK⋆ _K , the actual formation of each subteam should be determined, i.e., to find the set of subteams ¯≜1,⋯,K⋆ N \N_1,·s,N_K \, where k1⋂k2=∅N_k_1 _k_2= , ∀k1≠k2∀ k_1≠ k_2 and k1,k2⊂N_k_1,N_k_2 . In other words, the robots in kN_k are assigned to the subteam kC_k within νK⋆ _K . This can be done in two steps: (I) The lower and upper bound for each task is determined by the capacity constraints; (I) A constrained min-max assignment problem is formulated for the N robots and the first task of K subteams, i.e., the estimated starting time if robot i∈i participates in the first task of subteam kC_k is given by: tik≜t^i+Tnav(x^i,Sk1),t_ik t_i+T_ nav( x_i,\,S_k^1), (8) where t^i t_i and x^i x_i are the expected time and position when robot i becomes available after executing its current task (if any); TnavT_ nav is the estimated duration to navigate to the task region Sk1S_k^1. It can be formulated as a mixed-integer linear programming (MILP) problem over the possible robot-task pairings with boolean variables bik\b_ik\, which can be solved efficiently by existing solvers such as GLOP [31]. Thus, the local task plan of each robot i∈ki _k is given by: ξ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; (9) as a timed sequence of tasks, where ωkℓ∈Ωω _k∈ is the assigned ℓ -th task of subteam k∈¯N_k∈ N; Skℓ⊂S _k is the associated region; and Lk>0L_k>0 is the total length. Note that the total number of tasks Ω¯t _t is much larger than the number of subteams, and continually expanded online. I-B Local Task Coordination Once the local task plans are derived, each robot i∈i starts executing its ℓ -th task (Skℓ,ωkℓ)(S _k,\,ω _k), i.e., to navigate to region SkℓS _k and perform the task ωkℓω _k. The required subtasks from (1) are denoted by kℓ≜(nj,aj,sj),j=1,⋯,JkℓJ _k \(n_j,\,a_j,\,s_j),\,j=1,·s,J _k \. Consequently, all agents in kN_k should collaboratively fulfill these subtasks to minimize the overall duration. More specifically, the local action plan of each agent i∈ki _k for task ωkℓω _k is given by τi=(ti1,gi1,ai1)(ti2,gi2,ai2)⋯ _i=(t^1_i,\,g^1_i,\,a^1_i)(t^2_i,\,g^2_i,\,a^2_i)·s, as the sequence of timed goal, positions and actions. The overall objective of the local coordination is to optimize the collective plans kℓ≜τi,i∈k τ _k \ _i,\,i _k\ such that the makespan of ωkℓω _k, denoted by TkℓT _k, is minimized, i.e., minkℓTkℓmin_ τ _k\,\T _k\. However, as specified earlier, there are uncertainties regarding the total number of subtasks JkℓJ _k and their locations sj\s_j\ within the task ωkℓω _k. Thus, depending on the characteristics of the tasks and workspace, three different local coordination strategies are adopted, as shown in Fig. 2. Figure 2: Illustration of three types of local tasks described in Sec. I-B, and the associated coordination strategy. I-B1 Static and Known Tasks As the first case, consider that the locations and the number of subtasks are all known and static. For instance, the task of “delivery” often consists of several locations to visit in a region and collaboratively deliver some objects, which are often known beforehand according to orders. In this case, variants of the multi-vehicle routing problem can be formulated as a MILP by enforcing the collaborative actions at each location. The key is that the constraints are formulated according to the navigation model of each agent and the duration function ηkℓη _k from (1) given the assignment variables. The exact formulation is omitted here due to limited space. Denote by kℓ,⋆ τ , _k the resulting local plans, which can be then sent to all agents. I-B2 Static and Unknown Tasks For the second case, the number and location of the subtasks are unknown or uncertain, but the subtasks remain static and immobile during execution. For instance, for the task of “search and rescue”, the exact number of victims within the region is unknown and can only be determined during online execution. Thus, a simultaneous exploration and coordination (SEC) method is proposed. To begin with, a collaborative exploration strategy is adopted for the subteam kℓN _k to explore the region SkℓS _k for potential subtasks, e.g., frontiers-based [14] and sampling-based [8]. Without loss of generality, the set of exploration subtasks at time t>0t>0 is associated with the points to visit in the region, denoted by teJ e_t. Moreover, numerous collaborative subtasks in kℓJ _k are detected at time t along with its location and the required number of agents, denoted by tcJ c_t. Consequently, the set of known subtasks that has not been fulfilled is denoted by t≜te∪tcJ_t e_t c_t. Since the subtasks in tJ_t are constantly changing, a rolling assignment algorithm similar to Alg. 1 is adopted, i.e., to assign subtasks within tJ_t in small batches via the optimal algorithm described in the first case. This procedure continues until the region is fully explored and all detected subtasks are completed. I-B3 Dynamic and Known Tasks For the third case, the total number of the subtasks and their locations are known, but the subtasks are dynamic and mobile during execution. For instance, the task of “collaborative capture” often requires the agents to form subteams in order to surround and capture numerous moving targets. In this case, the previous two strategies are not suitable as the motion of subtasks would quickly render the current plans highly suboptimal or even infeasible. Thus, a dynamic coalition formation (DCF) method is adopted for this case, as proposed in our earlier work [6]. Particularly, each agent i∈kℓi _k only decides the next subtask to perform, along with other agents as a coalition, i.e., i∈j∈^ti _j∈ N_t, where ^t≜j,j∈kℓ N_t \N_j,\,j _k\ is the coalition scheme with all coalitions at time t>0t>0; it holds that j1∩j2=∅N_j_1 _j_2= and ∪j∈kℓj⊆kℓ _j _kN_j _k. It has been proven in [6] that the DCF method converges to a K-serial stable (KSS) coalition scheme after a finite number of distributed coordination. The detailed algorithm is omitted here due to limited space. Afterwards, the agents would complete the assigned subtask as coalitions and the coalition scheme is updated each time a subtask is completed. Remark 4. The case of dynamic and unknown tasks is not considered since: (I) Without knowing the total number and locations of subtasks, it is difficult to determine whether the current task is completed; (I) A combination of the strategy for the second and third cases above would suffice. ■ I-C Overall Framework I-C1 Online Execution and Adaptation Initially at t=0t=0, given the initially-known workspace and mission descriptions, the missions are decomposed into tasks, based on which the set of local teams are formed as ¯ N. These tasks are assigned to the teams with a given horizon H and a redundancy ρ via Alg. 1, yielding the local plan ξk _k for each team k∈¯N_k∈ N. Afterwards, the teams start executing the task (Skℓ,ωkℓ)∈ξk(S _k,ω _k)∈ _k by navigating to the desired region SkℓS _k and performing the task ωkℓω _k. Depending on the exact type of task ωkℓω _k, the set of subtasks kℓJ _k contained within ωkℓω _k is executed by team kN_k following one of the three local coordination strategies to derive local action plans τi\ _i\. Note that all teams are executed concurrently, and all agents within the same team are also acting in parallel. The conditions for replanning are designed as follows: (I) If more than half of the assigned H tasks are accomplished; (I) If new missions are specified; or (I) If the local coordination of certain subteams returns infeasible. During replanning, the task assignment and subteam formation are updated by calling Alg. 1 given the current system state. However, the tasks that are currently being executed can not be preempted, which is essential when there are significantly more tasks than the number of subteams. I-C2 Complexity Analysis In each iteration of Alg. 1, since H tasks are assigned, the complexity reaches (H2H)O(H2^H). During subteam formation, H⋅NH· N Boolean variables are introduced to indicate the membership of agents in subteams. Regarding different types of tasks, |k|(Jkℓ)2|N_k|(J _k)^2 integer variables are introduced to solve the MILP for the static and known tasks; the planning complexity for the static and unknown tasks is ((Jkℓ)3)O((J _k)^3), similar to Alg. 1; and the complexity for the dynamic and unknown tasks is ((NωkJkℓ)(2Jkℓ+Nωk)|k|)O((N_ _kJ _k)(2J _k+N_ _k)|N_k|), where NωkN_ _k is the upper bound of agent number for each coalition [6]. Figure 3: Snapshots of simulation at t=23st=23s (Left) and t=62st=62s (Right) when new missions are released and replanning occurs. IV Numerical Experiments To numerical validations, the proposed method is implemented in Python3 and tested on a laptop with an Intel Core i5-12500H CPU. The solver GLOP [31] is adopted for integer optimization. Simulation videos can be found in the supplementary files. IV-A System Description As shown in Fig. 3, the simulated fleet consists of N=80N=80 heterogeneous agents in an open environment with map size 30m×25m30m× 25m. The agents fall into 33 kinds with varying capabilities: 20 Type-A agents capable of perception and delivery, 30 Type-B agents capable of perception and grasping, and 30 Type-C agents capable of delivery and grasping. Initially, the agents are distributed evenly at two bases. All agents adhere to first-order dynamics and have a maximum speed of 1.5m/s1.5m/s in simulation. Moreover, there are |t|=4| _t|=4 missions released at random time instants, with an average interval μ=30sμ=30s with a standard deviation of σ=10sσ=10s. The sc-LTL missions follow a template of φi=◇(φdel∧◇φsurv)∧(¬φcapφsurv) _i= ( _ del _ surv) ( _ capU _ surv), where the 33 types of tasks are: “delivery” task, requiring delivery or grasping for 22 different subtasks; “surveillance” task, requiring perception; and “dynamic capture” task, requiring delivery or grasping for 22 different subtasks. Delivery tasks have in average 1313 subtasks, and 1515 subtasks for surveillance tasks with a probability of 0.50.5 to be unknown. The capture tasks have around 1717 dynamic targets with speed 0.5m/s0.5m/s inside the region. The planning horizon is set to H=6H=6 and replanning conditions follow the I-C. Figure 4: Top: the number of subteams and their composition; Bottom: the status of agents in different modes and the number of tasks. IV-B Results As shown in Fig. 1 and 3, the first mission is known initially, it takes 0.2s0.2s for the method from [22] to compute its posets, yielding 8 tasks in total. Among these tasks, 88 pairs follow the “⪯ ” relation and 11 for the “≃ ” relation. Moreover, it takes 1.1s1.1s for Alg. 1 to determine that subteams are required with a predicted makespan of 41s41s. The subteams consist of maximum 2525 agents and minimum 44 agents. For the first task of each subteam, the completion time is in average 15.9s15.9s and in total 5151 subtasks are detected. The average planning time for 33 types of tasks is 0.3s0.3s, 0.2s0.2s and 0.5s0.5s, respectively. After 33 tasks are completed at t=23.6st=23.6s, replanning is triggered, yielding 33 new and 11 old subteams for the remaining tasks. At t=26st=26s, another mission is released, which contains 99 tasks with 1010 relations. Thus, replanning is triggered, yielding 33 subteams and a predicted makespan of 48.1s48.1s, with a planning time of 0.13s0.13s. The procedure continues with new missions released at 62s62s and 90s90s, which leads to a total number of 3030 tasks and 492492 subtasks. The complete mission is accomplished at 154.3s154.3s, during which 1212 replannings are triggered. As shown in Fig. 3 and 4, the agents switch among navigation, waiting for collaboration, and task execution, of which the trajectories depend heavily on the type of tasks. Fig. 4 shows that the number of subteams and their composition change dynamically online, along with the number of tasks. IV-C Comparisons The proposed method is compared against six baselines: (I) C-MILP-1, where a complete MILP is formulated for all agents N and tasks Ω¯t _t similar to [32, 24], i.e., without the subteam formation in Alg. 1; (I) C-MILP-2, which formulates a complete MILP directly for all agents N and subtasks kℓ\J _k\, i.e., without the hierarchical scheme; (I) SAMP-1, where a sampling-based planner from [18] is adopted for all agents and tasks; (IV) SAMP-2, which applies the sampling-based planner directly to subtasks; (V) Inf-H, which is the same as our method but with a infinite horizon H, i.e., all known tasks are assigned in Alg. 1; (VI) Greedy, which assigns maximum one task to each subteam, i.e., without the horizon H. As summarized in Table I. the proposed method excels at almost all metrics including response time, planning time and success rate, compared with C-MILP-1,2 and SAMP-1,2. Particularly, via the proposed hierarchical solution, the planning time is 5050 times lower than C-MILP-1 and SAMP-1 that directly assign agents to tasks. Moreover, the methods C-MILP-2 and SAMP-2 often leads to unsuccessful executions without considering uncertainties in subtasks. Lastly, the maximum planning time for Inf-H can be prohibitively long (≥15≥ 15min), while Greedy deploys 65%65\% more agents in travelling than our methods. TABLE I: Comparison with Baselines Env. Methods Resp. Time[s] Ave/Max Plan Time[s] T/W/X Agents Succ. Rate[%] N M J 80 30 492 Ours 62.7 1.4/4.9 20/11/37 100 C-MILP-1 88.5 100/192 16/6/26 100 C-MILP-2 28.3 19/64 12/10/25 86 SAMP-1 108.3 54/92 19/8/24 100 SAMP-2 40.7 5.1/16 23/5/20 85 Inf-H 77.5 >15min>15min 24/17/31 100 Greedy 112.1 0.3/0.6 33/9/30 100 TABLE I: SCALABILITY ANALYSIS Env. Resp. Time[s] Ave/Max Plan Time [s] T/W/X Agents Succ. Rate[%] N M J α 120 50 824 0.05 95 1.6/4.6 33/10/39 100 0.1 102 1.7/4.9 26/9/35 100 150 80 1319 0.05 153 1.8/5.1 37/12/37 100 0.1 165 2.1/6.2 12/11/34 97 IV-D Generalization For further validation, the fleet size is further increased and the agents can fail with a probability of α. (I) Scalability: As summarized in Table I, when the fleet size is increased to 120120 and 150150, while the number of tasks to 5050 and 8080, at α=0.05α=0.05, the average planning time is increased by 12.5%12.5\% from 1.6s1.6s to 1.8s1.8s, while the maximum planning time increases from 4.6s4.6s to 5.15.1. Moreover, the average response time decreases from 9595 to 153153, as the average number of deployed agents increases from 8282 to 8686. (I) Failure Recovery: When α=0.05α=0.05, the success rate remains 100%100\% for 150150 agents even when the task number reaches 8080. However, the success rate drops to 97%97\% when the failure rate reaches 0.10.1, due the limits of remaining agent capacities. V Conclusion This work proposes a hierarchical coordination framework (HULK) that combines the global task assignment and the local subtask coordination, under continual and uncertain collaborative tasks. Future work includes human interaction and motion 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] T. Arai, E. Pagello, L. E. Parker, et al. (2002) Advances in multi-robot systems. IEEE Transactions on robotics and automation 18 (5), p. 655–661. Cited by: §I. [3] C. Baier and J. Katoen (2008) Principles of model checking. MIT press. Cited by: §I-B, §I-B, §I-A1. [4] J. C. Boerkoel Jr, L. R. Planken, R. J. Wilcox, and J. A. Shah (2013) Distributed algorithms for incrementally maintaining multiagent simple temporal networks. In International Conference on Automated Planning and Scheduling, Cited by: §I-A. [5] P. Brucker, B. Jurisch, and B. Sievers (1994) A branch and bound algorithm for the job-shop scheduling problem. Discrete applied mathematics 49 (1-3), p. 107–127. Cited by: §I-A. [6] J. Chen, Z. Tang, and M. Guo (2024) Accelerated k-serial stable coalition for dynamic capture and resource defense. IEEE Robotics and Automation Letters 9 (1), p. 443–450. Cited by: §I-B3, §I-C2, Remark 2. [7] O. M. Cliff, R. Fitch, S. Sukkarieh, D. L. Saunders, and R. Heinsohn (2015) Online localization of radio-tagged wildlife with an autonomous aerial robot system. In Robotics: Science and Systems, Cited by: §I. [8] D. Duberg and P. Jensfelt (2022) Ufoexplorer: fast and scalable sampling-based exploration with a graph-based planning structure. IEEE Robotics and Automation Letters 7 (2), p. 2487–2494. Cited by: §I-B2. [9] J. Fink, M. A. Hsieh, and V. Kumar (2008) Multi-robot manipulation via caging in environments with obstacles. In 2008 IEEE International Conference on Robotics and Automation, p. 1471–1476. Cited by: §I. [10] R. Fukasawa, H. Longo, J. Lysgaard, M. P. De Aragão, M. Reis, E. Uchoa, and R. F. Werneck (2006) Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Mathematical programming 106 (3), p. 491–511. Cited by: §I-A. [11] M. Gini (2017) Multi-robot allocation of tasks with temporal and ordering constraints. In AAAI Conference on Artificial Intelligence, Cited by: §I-A. [12] M. Guo and D. V. Dimarogonas (2015) Multi-agent plan reconfiguration under local ltl specifications. The International Journal of Robotics Research 34 (2), p. 218–235. Cited by: §I-A. [13] M. Guo and D. V. Dimarogonas (2016) Task and motion coordination for heterogeneous multiagent systems with loosely coupled local tasks. IEEE Transactions on Automation Science and Engineering 14 (2), p. 797–808. Cited by: §I-A. [14] 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: §I-B2. [15] H. H. Hoos and T. Stützle (2004) Stochastic local search: foundations and applications. Elsevier. Cited by: §I-A. [16] A. M. Jones, K. Leahy, C. Vasile, S. Sadraddini, Z. Serlin, R. Tron, and C. Belta (2019) ScRATCHS: scalable and robust algorithms for task-based coordination from high-level specifications. In Proc. Int. Symp. Robot. Res., p. 1–16. Cited by: §I-A. [17] Y. Kantaros and M. M. Zavlanos (2018) Distributed optimal control synthesis for multi-robot systems under global temporal tasks. In 2018 ACM/IEEE 9th International Conference on Cyber-Physical Systems (ICCPS), p. 162–173. Cited by: §I-A. [18] 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-A, §I, §IV-C. [19] A. Khamis, A. Hussein, and A. Elmogy (2015) Multi-robot task allocation: a review of the state-of-the-art. Cooperative Robots and Sensor Networks 2015, p. 31–51. Cited by: §I-A. [20] M. Lahijanian, S. B. Andersson, and C. Belta (2011) Temporal logic motion planning and control with probabilistic satisfaction guarantees. IEEE Transactions on Robotics 28 (2), p. 396–409. Cited by: §I-A. [21] Z. Liu, M. Guo, W. Bao, and Z. Li (2024) Fast and adaptive multi-agent planning under collaborative temporal logic tasks via poset products. Research 7, p. 0337. Cited by: §I-A1. [22] 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-A1, §I-A1, §IV-B, Remark 1. [23] L. Luo, N. Chakraborty, and K. Sycara (2015) Distributed algorithms for multirobot task assignment with task deadline constraints. IEEE Transactions on Automation Science and Engineering 12 (3), p. 876–888. Cited by: §I-A. [24] X. Luo and M. M. Zavlanos (2021) Temporal logic task allocation in heterogeneous multi-robot systems. arXiv preprint arXiv:2101.05694. Cited by: §I-A, §IV-C. [25] R. Massin, C. J. Le Martret, and P. Ciblat (2017) A coalition formation game for distributed node clustering in mobile ad hoc networks. IEEE Transactions on Wireless Communications 16 (6), p. 3940–3952. Cited by: §I-A. [26] C. Menghi, S. Garcia, P. Pelliccione, and J. Tumova (2018) Multi-robot ltl planning under uncertainty. In International Symposium on Formal Methods, p. 399–417. Cited by: §I-A. [27] E. Nunes and M. Gini (2015) Multi-robot auctions for allocation of tasks with temporal constraints. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 29. Cited by: §I-A. [28] 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-A, Remark 1. [29] 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-A. [30] P. Schillinger (2019) Specification decomposition and formal behavior generation in multi-robot systems. Ph.D. Thesis, KTH Royal Institute of Technology. Cited by: §I-A. [31] G. L. O. Solver Note: https://developers.google.com/optimization/lp Cited by: §I-A3, §IV. [32] 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, §IV-C. [33] P. Toth and D. Vigo (2002) An overview of vehicle routing problems. The vehicle routing problem, p. 1–26. Cited by: §I. [34] J. Tumova and D. V. Dimarogonas (2016) Multi-agent planning under local ltl specifications and event-based synchronization. Automatica 70, p. 239–248. Cited by: §I-A. [35] 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.