Paper deep dive
UMBRELLA: Uncertainty-aware Multi-robot Reactive Coordination under Dynamic Temporal Logic Tasks
Qisheng Zhao, Meng Guo, Hengxuan Du, Lars Lindemann, Zhongkui Li
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 95%
Last extracted: 3/27/2026, 1:13:13 AM
Summary
UMBRELLA is an online planning framework for multi-robot coordination that addresses dynamic temporal logic tasks. It integrates Conformal Prediction (CP) for uncertainty-aware target motion estimation with Monte Carlo Tree Search (MCTS) for task assignment. The framework minimizes the Conditional Value at Risk (CVaR) of the makespan, ensuring spatial-temporal constraints are met under dynamic conditions.
Entities (5)
Relation Signals (3)
UMBRELLA → enforces → Linear Temporal Logic
confidence 95% · Spatial and temporal constraints among the tasks are always ensured
UMBRELLA → optimizes → Conditional Value at Risk
confidence 95% · The objective is to minimize the Conditional Value at Risk (CVaR) of the average makespan.
UMBRELLA → utilizes → Conformal Prediction
confidence 95% · The proposed framework (UMBRELLA) combines the Monte Carlo Tree Search (MCTS) over partial plans with uncertainty-aware rollouts, and introduces a CP-based metric
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Multi-robot systems can be extremely efficient for accomplishing team-wise tasks by acting concurrently and collaboratively. However, most existing methods either assume static task features or simply replan when environmental changes occur. This paper addresses the challenging problem of coordinating multi-robot systems for collaborative tasks involving dynamic and moving targets. We explicitly model the uncertainty in target motion prediction via Conformal Prediction(CP), while respecting the spatial-temporal constraints specified by Linear Temporal Logic (LTL). The proposed framework (UMBRELLA) combines the Monte Carlo Tree Search (MCTS) over partial plans with uncertainty-aware rollouts, and introduces a CP-based metric to guide and accelerate the search. The objective is to minimize the Conditional Value at Risk (CVaR) of the average makespan. For tasks released online, a receding-horizon planning scheme dynamically adjusts the assignments based on updated task specifications and motion predictions. Spatial and temporal constraints among the tasks are always ensured, and only partial synchronization is required for the collaborative tasks during online execution. Extensive large-scale simulations and hardware experiments demonstrate substantial reductions in both the average makespan and its variance by 23% and 71%, compared with static baselines.
Tags
Links
- Source: https://arxiv.org/abs/2603.25395v1
- Canonical: https://arxiv.org/abs/2603.25395v1
Trouble viewing inline? Open PDF directly →
Full Text
56,956 characters extracted from source content.
Expand or collapse full text
UMBRELLA: Uncertainty-aware Multi-robot Reactive Coordination under Dynamic Temporal Logic Tasks Qisheng Zhao1, Meng Guo1, Hengxuan Du1, Lars Lindemann2, and Zhongkui Li1 The authors are with: 1School of Advanced Manufacturing and Robotics, Peking University, Beijing 100871, China; and 2Automatic Control Laboratory, ETH Zürich, Zürich 8092, Switzerland. This work was supported by the National Natural Science Foundation of China under grants 62425301, U2241214, T2121002. Corresponding author: Zhongkui Li (zhongkui.li@pku.edu.cn). Abstract Multi-robot systems can be extremely efficient for accomplishing team-wise tasks by acting concurrently and collaboratively. However, most existing methods either assume static task features or simply replan when environmental changes occur. This paper addresses the challenging problem of coordinating multi-robot systems for collaborative tasks involving dynamic and moving targets. We explicitly model the uncertainty in target motion prediction via Conformal Prediction (CP), while respecting the spatial-temporal constraints specified by Linear Temporal Logic (LTL). The proposed framework (UMBRELLA) combines the Monte Carlo Tree Search (MCTS) over partial plans with uncertainty-aware rollouts, and introduces a CP-based metric to guide and accelerate the search. The objective is to minimize the Conditional Value at Risk (CVaR) of the average makespan. For tasks released online, a receding-horizon planning scheme dynamically adjusts the assignments based on updated task specifications and motion predictions. Spatial and temporal constraints among the tasks are always ensured, and only partial synchronization is required for the collaborative tasks during online execution. Extensive large-scale simulations and hardware experiments demonstrate substantial reductions in both the average makespan and its variance by 23%23\% and 71%71\%, compared with static baselines. I Introduction Recent advances in computation, perception and communication enable the deployment of autonomous robots in large, remote and hazardous environments, such as offshore drilling platforms [21] and construction sites [4]. Concurrent motion and actions can greatly improve the team efficiency [23, 6], while direct collaboration on a single task further extends system capabilities [24]. To specify complex tasks beyond simple sequential visiting, many studies employ formal languages such as Linear Temporal Logic (LTL) formulas [2], as an intuitive yet powerful way to describe both spatial and temporal requirements on the team behavior [11, 8]. However, while tasks are commonly defined over static features such as regions and landmarks, many real-world applications involve dynamic targets, e.g., monitoring animal flocks or tracking moving vehicles [18]. These scenarios pose particular challenges for traditional offline methods that are designed for tasks over static features [16, 19, 14], as the future motion of targets can significantly impact the performance and even correctness of the overall plan. Figure 1: Top: Task plans with 1212 robots coordinating to track 44 dynamic targets across 1212 tasks in two scenes (Scene-1: left and middle; Scene-2: right). Middle: ROS simulation with 88 robots and 33 dynamic targets executing 1010 tasks. Bottom: Hardware experiments with 44 robots and 22 dynamic targets performing 77 tasks, showing snapshots at different times. I-A Related Work Extensive work has addressed task planning for team-wise temporal-logic specifications. Centralized methods are often used to ensure optimality and completeness. A sampling-based method in [11] avoids synchronized products of individual models. The work in [20] decomposes team tasks into subtasks and assigns them to individual robots. Works [16, 19] formulate task constraints and assignments as integer optimization programs. However, these works typically assume static propositions and operate offline. For dynamic workspaces, [7] performs local replanning for LTL tasks using updated workspace models. A reactive planning framework for heterogeneous robots is introduced in [26], allowing dynamic adaptation to collaborative temporal logic missions through local reallocation and path adjustment, minimizing task violations. A sampling-based coordination method in [10] addresses environments with uncertain semantic labels and known target motions. To handle online temporal tasks, [14] proposes computing products of partially-ordered subtasks and reassigning them after each task update. However, for tasks defined over dynamically moving features, the aforementioned methods would mostly plan over the current system state, neglecting their future motions and more importantly, the inherent uncertainties. Furthermore, Conformal Prediction (CP) has recently been used in robotics to quantify uncertainties in prediction [13, 22, 25]. In [13], CP is integrated with model predictive control to ensure motion safety for simple navigation tasks in dynamic environments. Temporal correlations are predicted using CP in [22] to enhance long-horizon performance for single-robot navigation. CP-based trajectory predictors for uncontrollable dynamic agents are applied to Signal Temporal Logic (STL) control in [25]. However, the planning problem for multi-robot collaborative tasks involving dynamic and uncertain targets remains an open challenge. I-B Our Method This work proposes UMBRELLA, an online planning framework for multi-robot coordination under dynamic temporal tasks. It integrates CP-based motion prediction with MCTS for task assignment. Predicted target motions and quantified uncertainty are used after “Expansion” to filter child nodes, and incorporated into “Simulation” to evaluate partial plans under the Conditional Value at Risk (CVaR) metric. To handle online updates of target motions and newly released tasks, a receding-horizon scheme is adopted to dynamically adjust task assignments. The framework ensures LTL-specified spatial-temporal constraints while accounting for target motion uncertainty, requiring only partial synchronization during collaborative task execution. Compared with offline baselines assuming static workspaces or simple periodic replanning, our method significantly reduces both the mean and variance of the average makespan. The main contribution is two-fold: (I) the incorporation of CP-based prediction into online multi-robot coordination under complex temporal tasks associated with dynamic targets; (I) a substantial reduction in the average makespan for temporal tasks specified offline and released online, with a 23%23\% and 71%71\% decrease in mean and variance, respectively. I Problem Description I-A Robots and Targets Consider a team of N autonomous robots operating within a workspace ⊂ℝ3W ^3. The state of robot n∈≜1,⋯,Nn \1,·s,N\ at time t is xt∈x_t . The maximum velocity of robot n is denoted by vnv_n. Each robot n can execute actions from a set nA_n. Let ≜⋃n∈nA _n A_n. The team is pre-programmed with collaborations ≜C1,⋯,CkC \C_1,·s,C_k\, where each collaboration Ck∈C_k consists of a list of actions that must be executed by different robots, denoted by: Ck≜[a1,a2,⋯,aℓk]C_k [a_1,\,a_2,·s,a_ _k ], where ℓk>0 _k>0 is the number of required actions, and aℓ∈a_ for ∀ℓ=1,⋯,ℓk∀ =1,·s, _k. Each action aℓ∈Cka_ ∈ C_k should be performed by a capable robot n, i.e., aℓ∈na_ _n. Each collaboration has a fixed duration ρ:→ℝ+ρ:C _+. Moreover, the workspace contains M dynamic targets with unknown trajectories. The position of target m∈ℳ≜1,⋯,Mm \1,·s,M\ at time t is modeled as a random variable Yt,m∈ℝ2Y_t,m ^2, with the joint target state Yt≜(Yt,1,⋯,Yt,M)∈ℝ2MY_t (Y_t,1,·s,Y_t,M ) ^2M. Their trajectories are assumed to follow an unknown distribution D, i.e., (Y0,Y1,⋯)∼ (Y_0,Y_1,·s ) . A total of K¯ K independent trajectory samples Y(i)≜(Y0(i),Y1(i),⋯)Y^(i) (Y_0^(i),Y_1^(i),·s) are available, partitioned into a calibration set Dcal≜Y(1),⋯,Y(K)D_ cal \Y^(1),·s,Y^(K)\ and a training set Dtra≜Y(K+1),⋯,Y(K¯)D_ tra \Y^(K+1),·s,Y^( K)\. The distribution D is independent of robot behaviors, i.e., it does not depend on the team state x. Perfect observations of target positions and velocities are continuously available, denoted by Y0:t≜(Y0,⋯,Yt)Y_0:t (Y_0,·s,Y_t ) and V0:t≜(V0,⋯,Vt)V_0:t (V_0,·s,V_t ), where Vt≜(Vt,1,⋯,Vt,M)V_t (V_t,1,·s,V_t,M ). A centralized scheme aggregates all measurements and fuses them into real-time estimates of target states. For simplicity, static task regions and obstacles are modeled as targets with zero velocity. I-B Task Specification Consider two types of atomic propositions: (I) pnmp^m_n is true if the distance between robot n∈n and target m∈ℳm is below a given threshold. Let p≜pnm,∀m∈ℳ,n∈p \p^m_n,\,∀ m ,n \; (I) ckmc_k^m is true if collaboration CkC_k is executed on target m. Let c≜ckm,∀m∈ℳ,∀Ck∈,∀ac∈Ckc \c_k^m,∀ m ,∀ C_k ,∀ a^c∈ C_k\. Thus, the complete set of propositions is denoted by AP≜p∪cAP . Given these propositions, a team-wise task is represented as a syntactically co-safe LTL (sc-LTL) formula: φi=sc-LTL(AP) _i=sc-LTL(AP). The overall task specification is represented as a set of LTL formulas, which consists of two parts: φ≜φstatic⋀e¯∈E¯□(φobse¯→◇φrepe¯), _ static _ e∈ E ( _ obs e→ _ rep e ), (1) where φstatic _ static is a predefined set of sc-LTL formulas; E¯ E is the set of events triggered by online observations; φobse¯ _ obs e is the propositional condition for event e¯∈E¯ e∈ E; and φrepe¯ _ rep e is the corresponding response task, also specified as sc-LTL. Specifically, if φobse¯ _ obs e holds, then φrepe¯ _ rep e must eventually be satisfied. We adopt the standard LTL syntax [2]: φ≜⊤|p|φ1∧φ2|¬φ|○φ|φ1Uφ2, \;|\;p\;|\; _1 _2\;|\; \;|\; \;|\; _1\, U\, _2, where ⊤≜True True, p∈APp∈ AP, ○ (next), U (until) and ⊥≜¬⊤ . sc-LTL [3] is a fragment of LTL restricted to operators ○ , U, and ◇ (eventually), written in positive normal form without the negation operator ¬ preceding temporal operators. Moreover, the task plan for the robot team is defined as Π≜(π1,π2,⋯,πN), _N ( _1, _2,·s, _N), (2) where πn≜(tn1,an1,mn1)(tn2,an2,mn2)⋯(tnKn,anKn,mnKn) _n (t^1_n,a^1_n,m^1_n)(t^2_n,a^2_n,m^2_n)·s(t^K_n_n,a^K_n_n,m^K_n_n) is the timed sequence of actions and corresponding targets for robot n∈n . Each action ank∈na^k_n _n is executed on target mnk∈ℳm^k_n at time tnk>0t^k_n>0, where k∈n≜1,⋯,Knk _n \1,·s,K_n\. Given Π _N, the induced trace is given by the sequence of propositions satisfied by the actions, i.e., wΠ=σ1σ2⋯σLw_ = _1 _2·s _L where σℓ∈2AP _ ∈ 2^AP. The language of φ is ℒφ≜|w⊧φL_ \ w\,|\,w \, where ⊧ is the satisfaction relation. Since sc-LTL formulas admit satisfaction by finite traces [3, 2], the plan satisfies φ if wΠ∈ℒφw_ _ , denoted by Π⊧φ _N . The makespan TφT_ is defined as the minimal time to generate a trace satisfying φ . As the tasks assigned to the robot system consist of initially issued tasks and online triggered tasks during execution, for a sequence of tasks φ(t)≜φ1,…,φL (t) \ _1,…, _L\ received up to time t, the average makespan is defined as: T¯φ≜1L∑ℓ=1LTφℓ. T_ 1L _ =1^LT_ _ . I-C Problem Statement Given task formulas φ(t) (t) and observations Y0:t,V0:t\Y_0:t,V_0:t\, the overall objective is to synthesize the team-wise plan Π _N to satisfy φ(t) (t) and minimize the average makespan T¯φ T_ . Example 1 Consider a fleet of UAVs and ground robots (GRs) deployed for wildlife monitoring in a workspace labeled with poacher, trap and animal. An offline collaborative task φ1 _ 1 is specified as: φ1=φp−s1∧φmf−a,φp−s1=◇patrols1, _ 1= _ p- s_1 _ mf- a,\> _ p- s_1= patrol_ s_1, (3) φmf−a=◇(monitora∧¬filma∧◇filma), _ mf- a= ( monitor_ a film_ a film_ a), which requires to patrol region s1 s_1, monitor and film antelopes in sequence. GRs must avoid obstacles in the workspace. The reactive protocol specifies: (poacher→◇arrest)( poacher→ arrest), where an “arrest” task is triggered upon detecting a poacher, and (trap∧animal→◇rescue)( trap animal→ rescue), triggers a “rescue” task when an animal is trapped. ■ I Proposed Solution Figure 2: Overview of the proposed framework, consisting of four main components: (i) trajectory estimation via LSTM and CP, (i) task decomposition into an R-poset, (i) CP-MCTS for uncertainty-aware assignment, and (iv) online execution and receding-horizon adaptation. In the R-poset illustration, precedence and mutual-exclusion relations are marked by black and red arrows, respectively. As illustrated in Fig. 2, the proposed solution consists of four components: the dynamic target trajectory estimation in Sec. I-A; the derivation of the relaxed partially-ordered set (R-poset) in Sec. I-B; the uncertainty-aware task assignment via CP-MCTS in Sec. I-C; and a receding-horizon planning scheme for real-time adaptation in Sec. I-D. I-A Trajectory Estimation of Dynamic Targets I-A1 Trajectory Predictor Given a task horizon TφT_ and the history of target observations Y0:tY_0:t, we train an independent trajectory predictor for each target based on the training dataset DtraD_ tra. Let Dtram⊂DtraD_ tra^m⊂ D_ tra collect trajectories of target m, Y0:T,m(i)≜(Y0,m(i),⋯,Yt,m(i),Yt+1,m(i),⋯,YTφ,m(i))Y_0:T,m^(i) (Y_0,m^(i),·s,Y_t,m^(i),Y_t+1,m^(i),·s,Y_T_ ,m^(i)) denotes the i-th trajectory in DtramD_ tra^m. The trajectory predictor is defined as Υm:ℝ2(t+1)→ℝ2(Tφ−t) _m:R^2(t+1) ^2(T_ -t) that estimates the future states of target m as Y^ℋt,m≜Υm(Y0:t,m),ℋt≜t+1,⋯,Tφ Y_H_t,m _m(Y_0:t,m),H_t \t+1,·s,T_ \, where Υm(Y0:t,m)≜(Y^t+1∣t,m,⋯,Y^Tφ∣t,m) _m(Y_0:t,m) ( Y_t+1 t,m,·s, Y_T_ t,m). Let ≜(Υ1,⋯,ΥM) ( _1,·s, _M). In principle, any trajectory predictor can be employed, including long short-term memory (LSTM) networks [9], recurrent neural networks (RNN) [17], and gated recurrent units (GRU) [5]. In this work, a LSTM network is adopted for each target and trained by minimizing the following loss function: minΥm1|Dtram|∑i=1|Dtram|‖Yℋt,m(i)−Υm(Y0:t,m(i))‖2, _mmin 1|D_ tra^m| _i=1^|D_ tra^m| \|Y_H_t,m^(i)- _m(Y_0:t,m^(i)) \|^2, which is the Mean Squared Error (MSE) over the predicted trajectory for target m. Stacking per-target predictions gives Y^ℋt≜(Y^ℋt,1,⋯,Y^ℋt,M) Y_H_t ( Y_H_t,1,·s, Y_H_t,M). Furthermore, based on the velocity measurements V0:tV_0:t, we define vm∗(t)≜max|Vς,m|:ς≤tv _m(t) \|V_ ,m|: ≤ t \ as the maximum historical velocity of target m up to time t. This velocity bound serves as an input parameter for the subsequent planning module. I-A2 Conformal Prediction Regions The CP framework can construct regions around predicted trajectories that contain the true trajectory with high probability, see [1] for detailed descriptions. More specifically, we adopt the method in [13] to construct valid prediction regions for each target independently. Given observations Y0:tY_0:t at time t, the trajectory predictors generate predictions Y^ℋt Y_H_t for the task horizon TφT_ . For each target m∈ℳm , given a failure probability δ∈(0,1)δ∈(0,1), the prediction regions Gℋt,m≜(Gt+1∣t,m,⋯,GTφ∣t,m)G_H_t,m (G_t+1 t,m,·s,G_T_ t,m) are constructed such that: Pr(‖Yh,m−Y^h∣t,m‖≤Gh∣t,m,∀h∈ℋt)≥1−δ,Pr ( \|Y_h,m- Y_h t,m \|≤ G_h t,m, . .∀ h _t )≥ 1-δ, (4) where Gh∣t,mG_h t,m denotes the h-step prediction error for target m at time t. The nonconformity score is defined as Rh|t,m(i)≜‖Yh,m(i)−Y^h|t,m(i)‖,R_h|t,m^(i) \|Y_h,m^(i)- Y_h|t,m^(i) \|, (5) for calibration trajectories Y(i)∈DcalmY^(i)∈ D_ cal^m, where DcalmD_ cal^m is the calibration dataset for target m. Specifically, predictions Y^h|t,m(i) Y_h|t,m^(i) are computed for each Y(i)∈DcalmY^(i)∈ D_ cal^m, and the corresponding nonconformity scores Rh|t,m(i)R_h|t,m^(i) are calculated. These scores are sorted in non-decreasing order after adding Rh|t,m(|Dcalm|+1)≜∞R_h|t,m^(|D_ cal^m|+1) ∞. The error bound Gh|t,mG_h|t,m is then chosen as the p-th smallest score, where p=⌈(|Dcalm|+1)(1−δ¯)⌉p= (|D_ cal^m|+1)(1- δ) . Finally, the prediction regions for all targets are aggregated as: Gℋt≜(Gh∣t,1,⋯,Gh∣t,M)G_H_t (G_h t,1,·s,G_h t,M). I-B R-posets for Task Formulas To efficiently capture the temporal constraints embedded in a sc-LTL formula φ , we adopt the notion of relaxed partially ordered sets (R-posets) as proposed in [15]. Given φ , we first translate it into a Nondeterministic Büchi Automaton (NBA) φ=(S,Σ,δ,S0,SF)A_ =(S,\, ,\,δ,\,S_0,\,S_F), where S is the set of states; Σ=AP =AP is the alphabet; δ:S×Σ→2Sδ:S× → 2^S is the transition relation; S0,SF⊆S_0,S_F S denote the initial and accepting states. Along a satisfying run of φA_ , a subtask ω is defined as the minimal symbol enabling a transition between states. Each subtask represents a unit of progress, and the collection of all subtasks forms Ωφ _ . Definition 1 (R-poset) An R-poset over φ is defined as the triple: Pφ=(Ωφ,⪯φ,≠φ)P_ =( _ , _ , _ ): (I) Ωφ _ is the set of subtasks; (I) ⪯φ⊆Ωφ×Ωφ _ _ × _ is the precedence relation: if (ω1,ω2)∈⪯φ( _1, _2)∈ _ , then ω2 _2 cannot start before ω1 _1 starts; (I) ≠φ⊆2Ωφ _ 2 _ is the mutual exclusion relation: subtasks in the same set cannot be executed simultaneously. ■ Although an R-poset is not unique for a given φ , the set of all possible R-posets PφP_ is as expressive as the original NBA. Any plan consistent with an R-poset must satisfy φ , since Words(Pφ)⊂Words(φ)Words(P_ ) ( ). In practice, we construct PφP_ using the algorithm in [15], denoted as Compute_poset(⋅) Compute\_poset(·). An example of an R-poset is illustrated in Fig. 2. I-C Uncertainty-Aware Task Assignment Given the estimation of target motions (Y^ℋt,Gℋt)( Y_H_t,G_H_t) and the final R-poset Pφ=(Ωφ,⪯φ,≠φ)P_ =( _ , _ , _ ), the objective is to find an efficient assignment of all subtasks in Ωφ _ given the robot team N such that all partial orders in ⪯φ,≠φ _ ,\, _ are respected and the average makespan of all tasks T¯φ T_ is minimized. I-C1 CP-based Monte Carlo Tree Search Monte Carlo Tree Search (MCTS) is a well-known heuristic search algorithm for solving complex planning problems in dynamic scenes. Built upon this algorithm, this work introduces CP-based Monte Carlo Tree Search (CP-MCTS). As summarized in Alg. 1 and Fig. 2, it is a centralized task planning algorithm designed to efficiently handle complex temporal tasks associated with dynamic targets. It repeats four stages until the time budget expires: selection, expansion, simulation, and backpropagation. Notably, as the number of robots and tasks increases, the nodes generated during the “Expansion” phase grow rapidly. If “Simulation” is performed for all expanded nodes, the algorithm becomes biased toward breadth-first search, neglecting depth exploration and thus reducing efficiency. To mitigate this, a CP-based metric is introduced to efficiently evaluate and select the most promising child nodes, which are then advanced to the “Simulation” stage. I-C2 Selection and Expansion Each node in the search tree represents a partial assignment of subtasks, i.e., ν≜(τ1,τ2,⋯,τN)ν ( _1,\, _2,·s, _N), where τn _n is the ordered sequence of subtasks assigned to robot n∈n . Input : Robots N, poset PφP_ , duration func. ρ, time budget tbt_b, target estimations Y^ℋt,Gℋt Y_H_t,G_H_t. Output : Plan Πc⋆ _ c , average makespan ηc⋆ _ c . 1 Initialize root node ν0 _0, ηc⋆←∞ _ c ←∞; 2 while time<tbtime<t_b do 3 Leaf node ν←ν← Selection(ν0 _0); 4 Child nodes ν+\ _+\ ← Expansion(ν,Pφν,\,P_ ); 5 Filtered nodes νs\ _ s\ via ζ in (7); 6 for νs∈νs _ s∈\ _ s\ do /* Simulation = Rollout + Eval */ 7 Πc← _ c← Rollout(νs,Pφ,ρ,Y^ℋt,xt _ s,\,P_ ,\,ρ,\, Y_H_t,\,x_t); 8 ηc←Eval(Πc,Pφ,ρ,Y^ℋt,Gℋt,xt) _ c← Eval( _ c,\,P_ ,\,ρ,\, Y_H_t,\,G_H_t,\,x_t); 9 if ηc<ηc⋆ _ c< _ c then 10 ηc⋆←ηc,Πc⋆←Πc _ c ← _ c,\, _ c ← _ c; 11 Backpropagate(νs,ξc _ s,\, _ c); 12 Algorithm 1 CP-based MCTS (CP-MCTS) During “Selection”, the Upper Confidence Bound applied to Trees (UCT) [12] is used to choose nodes for “Expansion”. The UCT value is computed as (ξ¯i+Q×lnBbi)( ξ_i+Q× lnBb_i), where ξ¯i ξ_i is the estimated value of the i-th child node, bib_i is its visit count, B is the visit count of the current node, and Q>0Q>0 is a parameter that balances exploration and exploitation. Starting from the root, at each level the child with the highest UCT value is recursively selected until a leaf node is reached. During “Expansion”, unless a terminal state with a complete assignment is reached, child nodes are generated from the leaf node by assigning the next subtask to the robot team. Let Ων≜ω∈τn,∀n∈ _ν \ω∈ _n,\,∀ n \ be the set of subtasks already assigned in node ν, and Ων−≜Ωφ\Ων ^-_ν _ _ν the remaining ones. To ensure feasibility, the next subtask ω is chosen from Ωνa≜ω|ω∈Ων−,ω′∈Ων,∀ω′∈Pre(ω) a_ν \ω\,|\,ω∈ ^-_ν,ω ∈ _ν,∀ω (ω) \, where Pre(ω)Pre(ω) represents the set of subtasks that must be completed before ω according to R-poset PφP_ . In other words, a subtask ωi _i cannot be assigned to node ν if some ωj _j with (ωj,ωi)∈⪯φ( _j, _i)∈ _ has not yet been assigned. When a subtask ω∈Ων+ω∈ ^+_ν is selected, a child node ν+ν^+ is created by assigning ω to a robot group ℐωI_ω, i.e., by appending it to the local plan τn _n of each robot n∈ℐωn _ω. For child node ν+ν^+, define key subtasks Ων+s⊂Ων+ s_ν^+⊂ _ν^+ as: Ων+s≜ω|ω=τn[0],ω∉τn′[1:],∀n,n′∈ s_ν^+ \ω\,|\,ω= _n[0],\,ω∉ _n [1:],\,∀ n,n \, where Ων+s s_ν^+ contains the first-to-execute subtasks across robots, independent of others. Stepwise simulation is then performed based on the predicted target trajectories Y^ℋt Y_H_t, as described in the sequel, resulting in the predicted completion time T^ω T_ω for each assigned subtask ω∈Ων+ω∈ _ν^+. I-C3 Simulation The “Simulation” procedure consists of three steps: (I) rollout to complete an assignment; (I) sample the makespan distribution; (I) evaluate the plan based on this distribution. First, a rollout policy is applied recursively from the selected child node until all subtasks are assigned. In each iteration, the next subtask is selected as in “Expansion” and assigned to a robot group either randomly or greedily according to stepwise simulation results. To enhance rollout diversity, we use a random factor ϵ∈[0,1]ε∈[0,1]: with probability ϵε, a feasible robot group is chosen uniformly at random; with probability 1−ϵ1-ε, the group expected to initiate this subtask earliest is selected. Once a complete plan Πc _ c is obtained, a sampling-based method derives its average makespan distribution ¯c T_ c via stepwise simulation with z∈ℕz samples drawn from the prediction regions Y^ℋt,Gℋt Y_H_t,G_H_t. Definition 2 (VaR and CVaR) The value at risk (VaR) at risk level α∈(0,1]α∈(0,1] is defined as VaRα(Πc)≜infρ∈ℝ,Prob(¯c≥ρ)≥αVaR_α( _ c) inf \ρ ,\,Prob( T_ c≥ρ)≥α \, i.e., the α-quantile of the distribution ¯c T_ c. The associated conditional value at risk (CVaR) is defined as: CVaRα(Πc)≜[¯c|¯c≥VaRα(Πc)]CVaR_α( _ c) [ T_ c| T_ c _α( _c) ], as the expected value of the worst α-quantile of ¯c T_ c. ■ As shown in Fig. 2, VaR captures the maximum loss at a given confidence level, while CVaR assesses the expected loss beyond the VaR threshold, providing a more informative measure of tail risk. Accordingly, we use ηc≜CVaRα(Πc) _ c _α( _ c) as the evaluation metric for each plan based on its average makespan distribution. The procedure of deriving the distribution and computing the CVaR is encapsulated as Eval(⋅) Eval(·). During the search, the best plan Πc⋆ _ c and its minimal risk value ηc⋆ _ c are maintained. For each new candidate Πc _ c, if ηc<ηc⋆ _ c< _ c , both Πc⋆ _ c and ηc⋆ _ c are updated. I-C4 Backpropagation To support the tree search, we define a normalized performance measure: ξc≜2−ηcηc⋆, _ c 2- _ c _ c , (6) which facilitates comparison across different branches of the search tree. During “Backpropagation”, the evaluation values and visit counts of nodes are propagated and updated along the path from the selected node to the root. Lemma 1 Given an expanded node ν+ν^+, the completion times of key subtasks in Ων+s s_ν^+ satisfy that Pr(Tω≤T^ω+GT^ω,mminn∈ℐωvn−vm⋆,∀ω∈Ων+s)≥(1−δ)|Ων+s|,Pr (T_ω≤ T_ω+ G_ T_ω,m n _ωmin\v_n\-v _m, . .∀ω∈ s_ν^+ )≥(1-δ)^| s_ν^+|, where TωT_ω is the actual completion time of subtask ω∈Ων+sω∈ s_ν^+; m is the associated target; ℐωI_ω is the set of robots executing ω; vnv_n and vm⋆v _m are the velocities of robot n and target m. Proof: From the simulation results, all robots n∈ℐωn _ω assigned to subtask ω∈Ων+sω∈ s_ν^+ would reach the predicted position Y^T^ω,m Y_ T_ω,m of target m by time instance T^ω T_ω. By the probability guarantee in (4), it holds that Pr(∥ Y_^T_ω, m - ^Y_^T_ω, m ∥ ≤G_^T_ω, m, ∀ω∈Ω^s_ν^+ ) ≥(1 - δ)^—Ω^s_ν^+—. The additional delay required to reach target m is upper-bounded by T^ωe=GT^ω,m/(minn∈ℐωvn−vm⋆) T_ω e=G_ T_ω,m/(min_n _ω\v_n\-v _m), this completes the proof. ∎ The actual completion time of a first executed subtask TωT_ω is probabilistically bounded by the predicted time T^ω T_ω plus an uncertainty term determined by the prediction region GT^ω,mG_ T_ω,m and the velocity difference between the slowest robot and the target. Hence, with confidence level (1−δ)(1-δ), each key subtask completion time can be reliably estimated. The evaluation metric for a child node ν+ν^+ is then defined as: ζν+≜∑i=1|Ων+|T^ωi+∑j=1|Ων+s|T^ωje|Ων+|, _ν^+ _i=1^| _ν^+| T_ _i+ _j=1^| s_ν^+| T_ _j e| _ν^+|, (7) which approximates the average completion time of assigned subtasks with uncertainty adjustment. After “Expansion”, for each next subtask, the child node with the smallest ζ is selected to enter “Simulation”, forming the filtered set νs\ _ s\. Remark 1 For a child node ν+ν^+, if a subtask ω∈Ων+sω∈ s_ν^+ is assigned to a robot n∈ℐωn _ω with velocity vn≤vm⋆v_n≤ v _m, the robot may be unable to complete the subtask. In this case, the predicted completion time is T^ω=∞ T_ω=∞, which yields ζν+=∞ _ν^+=∞; thus the node is excluded from the “Simulation” step. ■ I-D Online Execution and Adaptation I-D1 Online Execution and Adaptation Input : Robots N, task formula φ(t) (t), duration func. ρ, trajectory predictors , prediction regions GℋtG_H_t, observations Y0:t,V0:t\Y_0:t,V_0:t\. Output : Assignment Π⋆ . 1 Initialize PφP_ ←Compute_poset(φ(0))← Compute\_poset( (0)), Ωι←∅ _ ← ; 2 Initialize Π⋆,η⋆←CP-MCTS(Pφ,ρ,Y^ℋ0,Gℋ0,x0) ,\,η ← CP-MCTS(P_ ,ρ, Y_H_0,G_H_0,x_0); 3 while not terminated do 4 Each robot n∈n applies πn _n; 5 Sense xtx_t and YtY_t; 6 Obtain predictions Y^ℋt Y_H_t; 7 Update φ(t) (t) by (8); 8 Update PφP_ by Compute_poset(φ(t)) Compute\_poset( (t)); 9 if φr(t) _ r(t) then 10 Π⋆,η⋆ ,\,η ← CP-MCTS(Pφ,ρ,Y^ℋt,Gℋt,xtP_ ,ρ, Y_H_t,G_H_t,x_t); 11 12 else 13 η⋆←η⋆−1η ←η -1; 14 if Ωc(t)≠∅ _ c(t)≠ then 15 Update η⋆η by (9); 16 Ωι←Ωι∪Ωc(t) _ ← _ ∪ _ c(t); 17 18 ηt⋆←Eval(Π⋆,Pφ,ρ,Y^ℋt,Gℋt,xt)η _t← Eval( ,P_ ,ρ, Y_H_t,G_H_t,x_t); 19 if ηt⋆>(1+γ)η⋆η _t>(1+γ)η then 20 Π^t,η^t←CP-MCTS(Pφ,ρ,Y^ℋt,Gℋt,xt) _t,\, η_t← CP-MCTS(P_ ,ρ, Y_H_t,G_H_t,x_t); 21 if η^t<ηt⋆ η_t<η _t then 22 Π⋆←Π^t,η⋆←η^t ← _t,\,η ← η_t; 23 24 t←t+1;t← t+1; Algorithm 2 Online Dynamic Task Assignment As illustrated in Fig. 2 and summarized in Alg. 2, the planning scheme consists of two stages: initial planning and online adaptation. Following the initial plan, each robot n∈n executes its local plan πn _n by navigating to the targets specified by the assigned subtasks and then performing the corresponding actions. When executing action anKna^K_n_n on target mnKnm^K_n_n, the robot n must wait for collaborators if anKna^K_n_n belongs to a multi-robot collaboration CkC_k (i.e., |Ck|>1|C_k|>1). Such partial synchronization is essential to handle uncertainties in navigation and task execution times. If the action is non-collaborative, the robot proceeds independently without waiting. At each time step t>0t>0, the robot states xtx_t and target observations YtY_t are updated, and new predictions Y^ℋt Y_H_t are generated from Y0:tY_0:t using the trajectory predictors . Moreover, the task formula φ(t) (t) is updated by integrating triggered reactive task formula, i.e., φ(t)≜φ(t−)∧φr(t), (t) (t^-) _ r(t), (8) where φ(t−) (t^-) is the previous formula and φr(t)≜⋀e¯∈E¯◇φrepe¯(t) _ r(t) _ e∈ E _ rep e(t) is the reactive tasks released at time t. The current R-poset PφP_ is updated accordingly. Replanning is triggered under two conditions: (I) new reactive tasks appear, i.e., φr(t)≠∅ _ r(t)≠ , or (I) the current plan’s performance degrades significantly, i.e., ηt⋆>(1+γ)η⋆η _t>(1+γ)η , where γ∈(0,1)γ∈(0,1) is the replanning triggering ratio. Here, the performance metric ηt⋆η _t is computed via Eval(⋅) Eval(·) given the latest observations. For completed tasks, the expected value η⋆η is updated as η+⋆≜(|φ(t)|−|Ωι|+|Ωc(t)|)|φ(t)|−|Ωι|η−⋆,η _+ (| (t)|-| _ |+| _ c(t)| )| (t)|-| _ |η _-, (9) where η+⋆η _+ and η−⋆η _- denote the updated and previous values; |φ(t)|| (t)| is the total number of tasks; |Ωι|| _ | is the number of completed tasks; and |Ωc(t)|| _ c(t)| is the number of tasks finished at time t. When replanning is triggered, CP-MCTS generates a candidate plan Π^t _t with metric η^t η_t. The system adopts this new plan only if it offers improved performance as η^t<ηt⋆ η_t<η _t. Otherwise, the current plan Π⋆ is maintained and the metric η⋆η is monotonically decreased to reflect progress. This procedure repeats until the system terminates. I-D2 Complexity Analysis The computational complexity of Alg. 2 is analyzed as follows. Generating a R-poset has worst-case complexity (J2)O(J^2), where J is the number of subtasks, bounded by the number of edges in the NBA. For task assignment, the worst-case search space is (J!⋅NJ)O(J!· N^J), as subtask orderings are combinatorial and assignments grow exponentially with the number of robots N. In contrast, the rollout process remains (J⋅N)O(J· N), as subtasks are assigned randomly or greedily. The complexity of stepwise simulation is (zT⋅(J+N)Δt)O( zT·(J+N) t), where z is the number of samples, T is the makespan and Δt t is the time step. I-D3 Generalization There are two notable extensions of the proposed scheme. (I) Robot Failures. In the event of robot failures, a modified CP-MCTS is employed to generate a new plan. The root node is updated to exclude failed robots and include completed subtasks. If a failure occurs during execution, the affected subtask is rescheduled. The standard CP-MCTS procedure is then applied to update the assignment. (I) Dynamic Task Priority. When tasks are associated with different priorities αℓ _ , the optimization objective shifts from the average makespan T¯φ T_ to the weighted makespan T~φ≜∑ℓ=1LtαℓTφℓ T_ _ =1^L_t _ T_ _ , which emphasizes high-priority tasks. IV Numerical Experiments This section presents numerical validations of the proposed method over large-scale multi-robot systems. The implementation is in Python3 and tested on a laptop with an AMD Ryzen 9 7845HX CPU. Simulation and experiment videos are available in the supplementary material. IV-A Scenario Description For the wildlife protection scenario in Fig. 1, four types of animals: antelope, rabbit, elephant, and tiger, move within an 800m×800m800m× 800m outdoor area containing obstacles such as reservoirs and hills. A total of 20002000 synthetic trajectories are collected for the four types of animals as the training and calibration datasets (10001000 each), where initial and target positions are specified and Gaussian noise is added to sampled waypoints. Four robots of each type are deployed: fast GRs GfG_ f to monitor, patrol and arrest; slow GRs GsG_ s to monitor, patrol and rescue; and UAVs U to monitor and film. GRs can navigate safely around obstacles as a team. Tasks are specified by the following LTL formulas, which require to monitor, film, and rescue animals, while also patrolling and arresting poachers in designated areas: φstatic=φp−s1∧φp−s2∧φmf−a∧φmf−r∧φmf−e,φr(50)=φmf−t,φr(90)=◇arrests3∧◇rescuee, split& _ static= _ p- s_1 _ p- s_2 _ mf- a _ mf- r _ mf- e,\\ & _ r(50)= _ mf- t,\; _ r(90)= arrest_ s_3 rescue_ e, split where φp _ p, φmf _ mf follow the same structure as in (3). Two scenes with different animal motion patterns are considered (Fig. 1): Scene-1: targets exhibit piecewise uniform linear motion; Scene-2: targets follow general smooth trajectories. The main parameters are: CP failure probability δ=0.15δ=0.15, CP-MCTS time budget tb=10st_b=10s, exploration factor Q=1.5Q=1.5, random factor ϵ=0.3ε=0.3, number of samples z=50z=50, risk level α=0.05α=0.05, and replanning triggering ratio γ=0.2γ=0.2. Figure 3: The average makespan and the number of explored nodes with different random factors ϵε and expansion strategies (with or without CP-based metric ζ in (7)) during initial planning in Scene-1. IV-B Results The results are shown in Figs. 1 and 4. At t=0t=0, trajectory prediction takes 0.050.05s, R-posets computation for 88 static tasks takes 0.030.03s, and the “Simulation” at each node averages 0.250.25s with z=50z=50 samples. The metric ζν+ _ν^+ in (7) ranges from 24.524.5s to 72.372.3s, and a plan with average makespan η0⋆=48η _0=48s is generated after exploring 118118 nodes within tb=10t_b=10s. At t=43st=43s, replanning is triggered due to performance degradation, with η43⋆=14.2η _43=14.2s exceeding the threshold (1+γ)η⋆=13.7(1+γ)η =13.7s for γ=0.2γ=0.2. After exploring 140140 nodes, the new plan yields η^43=16.4 η_43=16.4s, which does not improve performance; thus, the current plan is retained. At t=50st=50s, the appearance of a new target tiger and task φmf-t _ mf-t triggers replanning with 44 subtasks, where 389389 nodes are explored, producing η50⋆=28.2η _50=28.2s. At t=90st=90s, reactive tasks arrests3 arrest_ s_3 and rescuee rescue_ e trigger replanning with 33 unfinished subtasks, exploring 155155 nodes and yielding η90⋆=40.3η _90=40.3s. The system terminates at t=147t=147s, with an average makespan of 67.667.6s over 1212 subtasks. Fig. 3 illustrates convergence and node exploration at t=0t=0. The algorithm is deemed converged when the best plan remains unchanged for more than 100100s. As the random factor ϵε increases, more nodes are explored, but convergence time grows. With heuristic-based robot selection during rollout, convergence is achieved within 1010s for ϵ=0ε=0 and ϵ=0.3ε=0.3. Moreover, using ζν+ _ν^+ as in (7) to filter child nodes accelerates tree exploration and improves performance. Figure 4: Left: Gantt chart of Scene-1, where replanning happens when the predicted value ηt⋆η _t exceeds a threshold (orange line) and new tasks are triggered (green and blue lines). Right: Gantt chart of Scene-1 where two robots fail at 40s40s and 70s70s (in grey), respectively. IV-C Comparisons To evaluate the effectiveness of our method (Ours), we compare against six baselines: Mixed Integer Linear Programming (MILP): task decomposition and assignment via integer optimization [16]; Branch and Bound (BnB): a search-based method from [15]; No Trajectory Prediction (NTP) and No Uncertainty (NU): Ours without trajectory prediction or without uncertainty regions, respectively; Ours-G: Ours with a GRU-based trajectory predictor; Ours-P10: Ours with periodic replanning every 10s instead of event-triggered replanning. All methods are first evaluated for task allocation at t=0t=0 in Scene-1, executed over 500500 target trajectory samples. Metrics include the mean and variance of average makespan and the solution time. They are further tested online in Scene-1 and Scene-2 with 500500 samples, together with a clairvoyant strategy (CS) that has access to future trajectories and applies NU for assignment. Static methods (MILP, BnB, NTP) model each dynamic target as fixed at its most recently observed position during planning. As shown in Table I, Ours outperforms static methods with reductions of 16.5%16.5\%, 24.6%24.6\%, and 22.5%22.5\% in mean makespan and 64.9%64.9\%, 67.3%67.3\%, and 74.8%74.8\% in variance across Scene-1 (t=0t=0), Scene-1, and Scene-2, respectively. BnB finds the first feasible solution quickly but converges slowly due to random exploration. MILP is the most time-consuming because of its exponential complexity. Ours requires more computation than NTP and BnB due to sampling and stepwise simulation, but achieves more reliable outcomes. Although NU achieves a 6.7%6.7\% lower mean makespan than Ours in Scene-1 at t=0t=0, it incurs 1.2×1.2× higher variance and performs worse in online settings, confirming that Ours offers more risk-averse assignments via CP. Ours-G performs comparably to Ours, showing adaptability to different predictors. Ours-P10 increases mean makespan by 10.2%10.2\% and variance by 4.2%4.2\% relative to Ours, underscoring the benefit of event-triggered replanning. Finally, Ours remains within 6.0%∼7.5%6.0\% 7.5\% of CS in mean makespan with only minor variance increases, indicating performance close to CS without prior knowledge of target motion. TABLE I: COMPARISON AGAINST BASELINES Method Scene-1 (=t=0) Scene-1 Scene-2 M(¯ϕ T_φ), V(¯ϕ T_φ) a [s]bt_p[s] b M(¯ϕ T_φ), V(¯ϕ T_φ) M(¯ϕ T_φ), V(¯ϕ T_φ) Ours 48.0, 3.25 1.22, 4.70 67.6, 5.32 68.5, 4.34 NU 44.8, 7.05 0.30, 2.74 72.5, 14.32 71.8, 12.59 NTP 56.2, 10.05 0.25, 0.53 81.9, 12.41 83.0, 17.21 MILP 59.1, 8.79 3.24, 905.6 94.9, 16.33 94.8, 18.12 BnB 57.1, 8.91 0.06, 35.22 92.0, 20.13 87.5, 16.24 Ours-G 49.9, 3.98 1.31, 5.21 66.9, 6.12 70.2, 5.43 Ours-P10 / / 79.3, 11.45 77.8, 12.67 CS / / 63.8, 3.24 65.3, 2.96 a M(¯ϕ T_φ), V(¯ϕ T_φ): mean and variance of average makespan T¯ϕ T_φ. b The solution time t_p is measured by two timestamps: (i) when the first solution is returned; (i) when the algorithm converges. c Best values are in bold; second-best are underlined. TABLE I: SCALABILITY ANALYSIS RESULTS (fG_ f, sG_ s, U)a t_p (=M=3)[s][s] (=t_p(F=16)[s][s] =F=8 =F=12 =F=16 =M=6 =M=9 (4, 4, 4) 1.22, 4.7 2.03, 8.2 3.93, 15.5 2.04, 13.2 1.63, 15.6 (8, 8, 8) 2.71, 4.1 5.15, 9.2 7.64, 18.1 5.29, 12.1 7.59, 19.1 (12, 12, 12) 3.81, 4.9 6.19, 9.5 9.39, 18.3 8.35, 12.8 9.59, 16.3 a (fG_ f, sG_ s, U): the number of three types of robots. IV-D Generalization IV-D1 Scalability Analysis Scalability is evaluated with respect to the number of robots N, tasks F, and targets M, as summarized in Table I. With fixed F=8F=8 and M=3M=3, increasing N from 1212 to 3636 raises the computation time for the first solution from 1.221.22s to 3.813.81s, while the convergence time remains around 4.74.7s. With fixed M=3M=3 and N=12N=12, increasing F from 88 to 1616 extends convergence time from 4.74.7s to 15.515.5s, whereas the time for the first solution grows only modestly from 1.221.22s to 3.933.93s, owing to the polynomial complexity of rollout. With fixed F=16F=16 and N=12N=12, increasing M from 33 to 99 causes fluctuations in the first-solution time, but convergence time stays around 15.015.0s. IV-D2 Robot Failure In Scene-1, ground robot Gf2G_ f2 fails at t=40st=40s, and UAV U4U4 at t=70st=70s. As shown in the Gantt chart of Fig. 4, the failure of Gf2G_ f2 during antelope monitoring triggers replanning, where U3U3 replaces it. At t=70st=70s, the failure of UAV U4U4 during antelope filming leads to another update, assigning U2U2 and U3U3 to complete the task. Despite these failures, the team successfully completes all tasks by t=151st=151s, with an average makespan of 74.9s74.9s. IV-D3 Dynamic Task Priority In Scene-1, the antelope-related task φmf−a _ mf- a is assigned a priority coefficient of 0.30.3, while other tasks are given 0.10.1. When optimizing for the average makespan T¯φ T_ , the completion times for monitoring and filming the antelope are Tm−a=92sT_ m- a=92s and Tf−a=112sT_ f- a=112s. Under weighted makespan T~φ T_ minimization, these times decrease to 82s82s and 102s102s, respectively, each reduced by 10s10s. IV-D4 High-fidelity ROS Simulation In the second scenario (Figs. 1 and 5), three types of suspects: on foot f, by bike b, and by car c flee through city roads. Two types of robots, four of each, are deployed: UAVs UtU_ t for tracking suspects and scouting, and UAVs UiU_ i for interception and scouting. Tasks are given by φstatic=φs−s1∧φs−s2∧φti−f∧φti−b∧φti−c _ static= _ s- s_1 _ s- s_2 _ ti- f _ ti- b _ ti- c, φr(40)=φs−s3,φr(80)=φs−s4,φs−s1=◇scouts1 _ r(40)= _ s- s_3,\; _ r(80)= _ s- s_4, _ s- s_1= scout_ s_1, φti−f=◇(trackf∧¬interceptf∧◇interceptf) _ ti- f= ( track_ f intercept_ f intercept_ f). Task assignments are updated at t=40st=40s and t=80st=80s when new reactive tasks appear. Additional replanning occurs at t=64st=64s, t=79st=79s, and t=104st=104s, though the plan remains unchanged. The system terminates at t=136st=136s, completing all 1010 tasks with an average makespan of 66.9s66.9s. Figure 5: ROS simulation results. Top: Robot and target trajectories. Bottom: Gantt chart of the execution timeline with task allocation and replanning. IV-E Hardware Experiments For further validation with hardware, we built a setup similar to the second scenario with 44 robots (UAV: 2Ut2U_ t, 2Ui2U_ i) and 22 targets (UGV: a1a_1, a2a_2) in a 4.95m×4.95m4.95m× 4.95m workspace, with the motion capture system OptiTrack providing their global states. Each robot communicates wirelessly with a control PC via ROS1. Mature navigation controllers are adopted and omitted for brevity. The tasks are specified as: φstatic=φs−s1∧φs−s2∧φti−a1∧φti−a2 _ static= _ s- s_1 _ s- s_2 _ ti- a_1 _ ti- a_2, φr(80)=φs−s3. _ r(80)= _ s- s_3. The algorithm uses the same parameters as in simulation. Assignments are updated at t=47st=47s (due to performance degradation) and t=80st=80s (due to a new task). The system terminates at t=113st=113s, completing all 77 tasks with an average makespan of 64.7s64.7s. The resulting trajectory, snapshots, and Gantt chart are shown in Figs. 1 and 6. V Conclusion This paper has presented UMBRELLA, an online multi-robot coordination framework for collaborative temporal tasks with dynamic targets. It achieves substantial reductions in both the mean and variance of the average makespan, while guaranteeing satisfaction of spatial-temporal task specifications. Future work includes intention-aware prediction for dynamic targets and finer motion constraints for robots. Figure 6: Hardware experiment results. Left: Recorded robot and target trajectories. Top-right: Example trajectory snapshots highlighting robot-target interactions. Bottom-right: Gantt chart of the execution timeline. References [1] A. N. Angelopoulos and S. Bates (2021) A gentle introduction to conformal prediction and distribution-free uncertainty quantification. arXiv:2107.07511. Cited by: §I-A2. [2] C. Baier and J. Katoen (2008) Principles of model checking. MIT Press. Cited by: §I, §I-B, §I-B. [3] C. Belta, B. Yordanov, and E. A. Gol (2017) Formal methods for discrete-time dynamical systems. Vol. 15, Springer. Cited by: §I-B, §I-B. [4] T. Bock (2007) Construction robotics. Auton. Robots 22 (3), p. 201–209. Cited by: §I. [5] K. Cho, B. Van Merriënboer, D. Bahdanau, and Y. Bengio (2014) On the properties of neural machine translation: encoder-decoder approaches. arXiv preprint arXiv:1409.1259. Cited by: §I-A1. [6] 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 Sci. Syst., Cited by: §I. [7] M. Guo and D. V. Dimarogonas (2015) Multi-agent plan reconfiguration under local ltl specifications. Int. J. Robot. Res. 34 (2), p. 218–235. Cited by: §I-A. [8] M. Guo and M. M. Zavlanos (2018) Multirobot data gathering under buffer constraints and intermittent communication. IEEE Trans. Robot. 34 (4), p. 1082–1097. Cited by: §I. [9] S. Hochreiter (1997) Long short-term memory. Neural Comput.. Cited by: §I-A1. [10] S. Kalluraya, G. J. Pappas, and Y. Kantaros (2023) Multi-robot mission planning in dynamic semantic environments. In IEEE Int. Conf. Robot. Autom., p. 1630–1637. Cited by: §I-A. [11] Y. Kantaros and M. M. Zavlanos (2020) Stylus*: a temporal logic optimal control synthesis algorithm for large-scale multi-robot systems. Int. J. Robot. Res. 39 (7), p. 812–836. Cited by: §I-A, §I. [12] L. Kocsis and C. Szepesvári (2006) Bandit based monte-carlo planning. In Eur. Conf. Mach. Learn., p. 282–293. Cited by: §I-C2. [13] L. Lindemann, M. Cleaveland, G. Shim, and G. J. Pappas (2023) Safe planning in dynamic environments using conformal prediction. IEEE Robot. Autom. Lett. 8 (8), p. 5116–5123. Cited by: §I-A, §I-A2. [14] 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-A, §I. [15] 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. External Links: ISSN 0005-1098 Cited by: §I-B, §I-B, §IV-C. [16] X. Luo and M. M. Zavlanos (2022) Temporal logic task allocation in heterogeneous multi-robot systems. IEEE Trans. Robot. 38 (6), p. 3602–3621. Cited by: §I-A, §I, §IV-C. [17] L. R. Medsker, L. Jain, et al. (2001) Recurrent neural networks. Design and Applications 5 (64-67), p. 2. Cited by: §I-A1. [18] C. Robin and S. Lacroix (2016) Multi-robot target detection and tracking: taxonomy and survey. Auton. Robots 40, p. 729–760. Cited by: §I. [19] Y. E. Sahin, P. Nilsson, and N. Ozay (2019) Multirobot coordination with counting temporal logics. IEEE Trans. Robot. 36 (4), p. 1189–1206. Cited by: §I-A, §I. [20] P. Schillinger, M. Bürger, and D. V. Dimarogonas (2018) Simultaneous task allocation and planning for temporal logic goals in heterogeneous multi-robot systems. Int. J. Robot. Res. 37 (7), p. 818–838. Cited by: §I-A. [21] A. Shukla and H. Karki (2016) Application of robotics in offshore oil and gas industry—a review part i. Robotics Auton. Syst. 75, p. 508–524. Cited by: §I. [22] S. Tonkens, S. Sun, R. Yu, and S. Herbert (2023) Scalable safe long-horizon planning in dynamic environments leveraging conformal prediction and temporal correlations. In IEEE Int. Conf. Robot. Autom., Cited by: §I-A. [23] P. Toth and D. Vigo (2002) An overview of vehicle routing problems. The Vehicle Routing Problem, p. 1–26. Cited by: §I. [24] 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 Sci. Syst., p. 696–700. Cited by: §I. [25] X. Yu, Y. Zhao, X. Yin, and L. Lindemann (2023) Signal temporal logic control synthesis among uncontrollable dynamic agents with conformal prediction. arXiv:2312.04242. Cited by: §I-A. [26] Y. Zhang, S. Kalluraya, G. J. Pappas, and Y. Kantaros (2024) Reactive planning for teams of heterogeneous robots with dynamic collaborative temporal logic missions. In IEEE Conf. Decis. Control, p. 1599–1606. Cited by: §I-A.