Paper deep dive
Robust and Scalable UAV-UGV Planning for Aerial Monitoring under Energy and Precedence Constraints
Cahit Ikbal Er, Yasin Yazicioglu
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 96%
Last extracted: 10/12/2026, 5:38:51 AM
Summary
This paper addresses the robust and scalable planning problem for teams of Unmanned Aerial Vehicles (UAVs) and Unmanned Ground Vehicles (UGVs) in aerial monitoring missions. The system involves multiple UAV-UGV pairs where UGVs act as mobile charging stations and transporters for UAVs. The core challenge is to minimize mission completion time while satisfying UAV energy constraints (endurance) and precedence constraints (ordering requirements) on monitoring points, even under bounded travel-time disturbances. The authors formulate the problem as a mixed-integer program (NP-hard) and propose a polynomial-time heuristic algorithm that jointly determines vehicle routes and timing, allowing teams to slow down to satisfy ordering constraints. The approach provides feasibility guarantees and computational complexity characterizations.
Entities (8)
Relation Signals (6)
Authors → affiliatedwith → Northeastern University
confidence 99% · C. I. Er is with the Department of Mechanical and Industrial Engineering, Northeastern University... Y. Yazıcıoğlu is with... Northeastern University
UGV → servesas → Mobile Charging Stations
confidence 98% · The UGVs serve as mobile charging stations and transport the UAVs between consecutive aerial tours.
UAV → hasconstraint → Energy Constraints
confidence 97% · UAV energy limitations are modeled through endurance, defined as the maximum flight time on a full battery.
Proposed Algorithm → solves → Planning Problem
confidence 97% · We develop a polynomial-time algorithm that generates efficient solutions to the underlying NP-hard planning problem.
Monitoring Points → subjectto → Precedence Constraints
confidence 96% · Given a set of monitoring points subject to ordering constraints... the objective is to minimize mission completion time while satisfying... the required visit order
Planning Problem → formulatedas → Mixed-Integer Program
confidence 95% · We formulate this planning problem as a mixed-integer program, which is NP-hard.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We consider planning for unmanned aerial vehicle (UAV) and unmanned ground vehicle (UGV) teams in aerial monitoring missions with ordering requirements on the monitoring points to be visited by the UAV. The system consists of multiple UAV-UGV teams, each comprising one UAV and one UGV. UAV energy limitations are modeled through endurance, defined as the maximum flight time on a full battery. The UGVs serve as mobile charging stations and transport the UAVs between consecutive aerial tours. Given a set of monitoring points subject to ordering constraints and the teams' initial and terminal positions, the objective is to minimize mission completion time while satisfying UAV energy limits and the required visit order under bounded travel-time disturbances that may arise during execution. Unlike prior work, the plan jointly determines vehicle routes and their timing, allowing teams to slow down as needed to satisfy the ordering constraints. We develop a polynomial-time algorithm that generates efficient solutions to the underlying NP-hard planning problem. We establish feasibility guarantees, characterize the algorithm's computational complexity, and evaluate its performance via numerical comparisons.
Tags
Links
- Source: https://arxiv.org/abs/2610.12670v1
- Canonical: https://arxiv.org/abs/2610.12670v1
Trouble viewing inline? Open PDF directly →
Full Text
59,545 characters extracted from source content.
Expand or collapse full text
Robust and Scalable UAV-UGV Planning for Aerial Monitoring under Energy and Precedence Constraints Cahit Ikbal Er Yasin Yazıcıoğlu †thanks: C. I. Er is with the Department of Mechanical and Industrial Engineering, Northeastern University, Boston, MA, USA (email: er.c@northeastern.edu).†thanks: Y. Yazıcıoğlu is with the Departments of Mechanical and Industrial Engineering and Electrical and Computer Engineering, Northeastern University, Boston, MA, USA (email: y.yazicioglu@northeastern.edu). Abstract We consider planning for unmanned aerial vehicle (UAV) and unmanned ground vehicle (UGV) teams in aerial monitoring missions with ordering requirements on the monitoring points to be visited by the UAV. The system consists of multiple UAV-UGV teams, each comprising one UAV and one UGV. UAV energy limitations are modeled through endurance, defined as the maximum flight time on a full battery. The UGVs serve as mobile charging stations and transport the UAVs between consecutive aerial tours. Given a set of monitoring points subject to ordering constraints and the teams’ initial and terminal positions, the objective is to minimize mission completion time while satisfying UAV energy limits and the required visit order under bounded travel-time disturbances that may arise during execution. Unlike prior work, the plan jointly determines vehicle routes and their timing, allowing teams to slow down as needed to satisfy the ordering constraints. We develop a polynomial-time algorithm that generates efficient solutions to the underlying NP-hard planning problem. We establish feasibility guarantees, characterize the algorithm’s computational complexity, and evaluate its performance via numerical comparisons. I Introduction Unmanned aerial vehicles (UAVs) are used in various domains such as agriculture and environmental monitoring (e.g., [1, 2]). However, their limited energy restricts missions defined over large areas or long time-horizons. Using unmanned ground vehicles (UGVs) as mobile charging stations addresses this limitation by providing a flexible alternative to fixed recharging infrastructure. Recently, energy-constrained planning of UAV-UGV teams has gained significant attention (e.g., [3, 4, 5, 6, 7, 8, 9]). However, these methods generally assume that points of interest may be visited in any order. In practice, aerial monitoring missions may require some locations to be visited before others. In multi-robot task allocation, such ordering requirements are formalized as cross-schedule dependencies [10]. Exact methods have addressed vehicle-routing problems with temporal synchronization [11], while polynomial-time sequencers handle task allocation under temporal and spatial constraints [12]; however, these approaches generally do not model vehicle energy. Similarly, [13] schedules cooperative tasks using greedy construction and local search, but focuses on task scheduling rather than energy-constrained spatial planning. More recently, [14] computes optimal precedence-constrained plans for heterogeneous UAV teams under energy limits, though its computational complexity grows significantly with team size and recharging relies on static infrastructure. In this paper, we propose a heuristic algorithm for robust UAV-UGV planning in aerial monitoring missions with precedence constraints. The goal is to minimize the overall mission completion time while respecting the energy constraints and the required visit order under bounded travel-time disturbances. We formulate this planning problem as a mixed-integer program, which is NP-hard. Our main contribution is an efficient heuristic (Alg. 1) that jointly determines vehicle routes and their timing, with formal guarantees on feasibility and worst-case time complexity (Theorem 1). We validate our approach via numerical comparisons against branch-and-cut, simulated annealing, and a heuristic baseline that assigns all locations that are weakly connected by precedence constraints to the same team. I Problem Formulation We consider an aerial monitoring mission executed by multiple UAV-UGV teams. The energy-constrained UAVs must visit a set of monitoring points, supported by the UGVs which serve as mobile charging stations and transport the UAVs between take-off and landing locations. Two features distinguish this formulation from prior work (e.g., [8, 9]). First, precedence requirements constrain the order in which the monitoring points may be visited. Second, the plan selects not only where the vehicles go but how long each leg takes, allowing a team to slow down if needed rather than reroute to satisfy these ordering constraints. Uncertainty is treated in the deterministic, worst-case sense of robust optimization under interval uncertainty [15]. Following [8], the plan incorporates margins δa _a and δg _g to ensure that unexpected travel delays do not deplete a UAV’s energy. However, these margins do not preserve the mission’s visit order: a delay at one point could cause it to be visited after a point it must precede. To prevent this, we introduce an ordering margin, δo _o. This enforces a minimum temporal separation between precedence-constrained points, ensuring bounded delays do not violate the required visit order. In the remainder, ℝR and ℝ≥0R_≥ 0 denote the sets of real and non-negative real numbers. Let the environment be ≔(x,y,z)∈ℝ≥03∣x≤x¯,y≤y¯,z≤z¯,Q \(x,y,z) _≥ 0^3 x≤ x,\,y≤ y,\,z≤ z\, (1) containing a feasible space f⊆Q_f determined by the obstacles known a priori, with ground and air subsets fg=(x,y,z)∈f∣z=0Q^g_f=\(x,y,z) _f z=0\ and fa=f∖fgQ^a_f=Q_f ^g_f. Both fQ_f and fgQ^g_f are assumed connected, so that a feasible path exists between any pair of points within the respective sets, and ℓ:f×f→ℝ≥0 :Q_f×Q_f _≥ 0 returns the length of the shortest path between two points of fQ_f. Additionally, let π:f→fgπ:Q_f _f^g be the feasible ground projection function, defined as π(p)=argminq∈Qfgℓ(p,q)π(p)= _q∈ Q_f^g (p,q). The mission is specified by a set of n aerial monitoring points UAV=p1,…,pn⊂faP_UAV=\p_1,…,p_n\ ^a_f. There are m teams (UAV-UGV pairs) indexed by μ∈1,…,mμ∈\1,…,m\, each starting from a start position psμ∈fgp^μ_s ^g_f and required to reach a specified final position pfμ∈fgp^μ_f ^g_f. The teams must collectively visit every point of UAVP_UAV11footnotemark: 1 in an order consistent with a given precedence relation, specified as a directed acyclic graph (DAG) G≺=(UAV,E≺)G_ =(P_UAV,E_ ) whose edges (p,q)∈E≺(p,q)∈ E_ require p to be visited before q.11 1 No assumption is made on how UAVP_UAV and E≺E_ arise: the points may encode imaging viewpoints at a desired resolution, and the ordering a requirement such as surveying the perimeter of a site before entering it. Acyclicity ensures that a valid visit order always exists, as any topological sort of G≺G_ provides one [16]. The graph G≺G_ can encode any partial order and need not be connected; isolated vertices carry no ordering requirements. A UAV cannot fly continuously longer than its maximum flight time τ¯a τ_a. Because power consumption is approximately constant for UAVs flown at constant average speed (e.g., [17]), flight time acts as a direct proxy for energy consumption, making τ¯a τ_a the energy budget, as is standard in the literature (e.g., [3, 4, 6, 5, 8, 7, 9]). UGVs carry larger batteries and are assumed to have sufficient energy for the mission. To respect τ¯a τ_a, the UGVs transport the UAVs through a sequence of tours. In each tour, a UAV takes off from a release point on the ground, visits a subset of UAVP_UAV, and lands on the UGV at the corresponding collect point to recharge. The UGV then carries it to the next release point, or to pfμp^μ_f if the mission is complete. Because a single tour can visit at most n monitoring points, the plan of team μ is encoded as the matrix Xμ=[X1,1μ⋯X1,n+2μ⋱Xn,1μ⋯Xn,n+2μ],X^μ= bmatrixX^μ_1,1&·s&X^μ_1,n+2\\ & & \\ X^μ_n,1&·s&X^μ_n,n+2 bmatrix, where Xi,jμ∈fX^μ_i,j _f is a release point if j=1j=1, a collect point if j=n+2j=n+2, and a monitoring point to be visited by the UAV if j∈2,…,n+1j∈\2,…,n+1\. Row i, denoted XiμX^μ_i, represents one such tour. Setting Xi,1μ=⋯=Xi,n+2μX^μ_i,1=·s=X^μ_i,n+2 in a row yields a trivial tour of zero length, ensuring plans with fewer than n tours are representable. The overall mission plan is X=X1,…,XmX=\X^1,…,X^m\. Let θ¯a:f×f→ℝ≥0 θ_a:Q_f×Q_f _≥ 0 and θ¯g:fg×fg→ℝ≥0 θ_g:Q_f^g×Q_f^g _≥ 0 be the fastest travel times in which the UAVs and the UGVs can traverse a shortest path between respective points,22 2 We do not commit to specific forms for θ¯a θ_a, θ¯g θ_g and τc _c. The simplest instance takes shortest paths and divides them with fixed speeds, with τc _c modeling either proportional recharging or a constant battery swap. with θ¯a(p,p)=θ¯g(p,p)=0 θ_a(p,p)= θ_g(p,p)=0. The duration of each leg is assigned independently and lower-bounded by these fastest travel times. These durations form the timing of the mission. Let the timing for team μ be defined by the tuple Θμ=(Θaμ,Θgμ,Θgaμ,θsμ,θfμ) ^μ=( _a^μ, _g^μ, _ga^μ, _s^μ, _f^μ). Here, Θaμ∈ℝ≥0n×(n+1) _a^μ _≥ 0^n×(n+1) is the flight timing matrix, where entry θaμ,i,j _a^μ,i,j is the UAV’s flight time from Xi,jμX_i,j^μ to Xi,j+1μX_i,j+1^μ. The vector Θgμ∈ℝ≥0n _g^μ _≥ 0^n defines UGV relocation times, with entry θgμ,i _g^μ,i denoting the time from the release Xi,1μX_i,1^μ to the collect Xi,n+2μX_i,n+2^μ within tour i. Between consecutive tours, the gap timing vector Θgaμ∈ℝ≥0n−1 _ga^μ _≥ 0^n-1 provides the transport time θgaμ,i _ga^μ,i from Xi,n+2μX_i,n+2^μ to Xi+1,1μX_i+1,1^μ. Finally, the scalars θsμ _s^μ and θfμ _f^μ denote the initial and final transport times from psμp_s^μ to X1,1μX_1,1^μ and from Xn,n+2μX_n,n+2^μ to pfμp_f^μ, respectively. The overall mission timing is Θ=Θμ=1m =\ ^μ\_μ=1^m. The times to complete the UAV and UGV portions of tour i are τa(Xiμ,Θμ)=∑j=1n+1θaμ,i,j _a(X^μ_i, ^μ)= _j=1^n+1 _a^μ,i,j and τg(Xiμ,Θμ)=θgμ,i _g(X^μ_i, ^μ)= _g^μ,i, while the subsequent UGV transport time is τga(Xiμ,Θμ)=θgaμ,i _ga(X^μ_i, ^μ)= _ga^μ,i. Concurrently, the UAV requires a recharge time defined by τc(max(τa(Xiμ,Θμ),τg(Xiμ,Θμ)))≥0 _c ( ( _a(X^μ_i, ^μ), _g(X^μ_i, ^μ)) )≥ 0, where τc:ℝ≥0→ℝ≥0 _c:R_≥ 0 _≥ 0 with τc(0)=0 _c(0)=0 maps the airborne time on a tour to the time needed to recharge the UAV. The total execution time for team μ, denoted τ(Xμ,Θμ)τ(X^μ, ^μ), is the sum of its initial and final transport times, the time spent executing the tours, and the time spent between tours while the UGV carries and recharges the UAV: τ(Xμ,Θμ)= τ(X^μ, ^μ)= θsμ+θfμ+∑i=1nmax(τa(Xiμ,Θμ),τg(Xiμ,Θμ)) _s^μ+ _f^μ+ _i=1^n ( _a(X^μ_i, ^μ),\, _g(X^μ_i, ^μ)) (2) +∑i=1n−1max(τga(Xμi,Θμ),τc(max(τa(Xμi,Θμ),τg(Xμi,Θμ)))). + _i=1^n-1 ( _ga(X^μ_i, ^μ),\, _c ( ( _a(X^μ_i, ^μ),\, _g(X^μ_i, ^μ)) ) ). A plan X and timing Θ determine the time each monitoring point is reached. Let tp(X,Θ)t_p(X, ) denote the visit time of p, defined as the earliest time any UAV reaches p relative to the mission start. Since tp(X,Θ)t_p(X, ) accumulates preceding leg durations, a delay in any leg propagates to all subsequent visits dependent on it. We define the planning problem as minimizing the makespan over the m teams as: minX,Θmaxμ∈1,…,mτ(Xμ,Θμ) X,\, min 9.24994pt _μ∈\1,…,m\\;τ(X^μ, ^μ) (3a) s.t. [ $ X,\, min$][c] [ $min$][l] 0.92505pts.t. 9.24994pt ∀pk∈UAV,∃Xi,jμ=pk, ∀ p_k _UAV,\;∃\,X^μ_i,j=p_k, (3b) τa(Xiμ,Θμ)+δa≤τ¯a,∀i,∀μ, _a(X^μ_i, ^μ)+ _a≤ τ_a,\, ∀ i,∀μ, (3c) τg(Xiμ,Θμ)+δg≤τ¯a,∀i,∀μ, _g(X^μ_i, ^μ)+ _g≤ τ_a,\, ∀ i,∀μ, (3d) Xi,1μ,Xi,n+2μ∈fg,∀i,∀μ, X^μ_i,1,\,X^μ_i,n+2 _f^g,\, ∀ i,∀μ, (3e) Xi,jμ∈UAV∪Xi,j−1μ,∀j∈2,…,n+1,∀i,∀μ, X^μ_i,j _UAV∪\X^μ_i,j-1\,\, ∀ j∈\2,…,n+1\,∀ i,∀μ, (3f) θaμ,i,j≥θ¯a(Xi,jμ,Xi,j+1μ),∀j∈1,…,n+1,∀i,∀μ, _a^μ,i,j≥ θ_a(X^μ_i,j,X^μ_i,j+1),\, ∀ j∈\1,…,n+1\,∀ i,∀μ, (3g) θgμ,i≥θ¯g(Xi,1μ,Xi,n+2μ),∀i,∀μ, _g^μ,i≥ θ_g(X^μ_i,1,X^μ_i,n+2),\, ∀ i,∀μ, (3h) θgaμ,i≥θ¯g(Xi,n+2μ,Xi+1,1μ),∀i∈1,…,n−1,∀μ, _ga^μ,i≥ θ_g(X^μ_i,n+2,X^μ_i+1,1),\, ∀ i∈\1,…,n-1\,∀μ, (3i) θsμ≥θ¯g(psμ,X1,1μ),θfμ≥θ¯g(Xn,n+2μ,pfμ),∀μ, _s^μ≥ θ_g(p^μ_s,X^μ_1,1),\ \ _f^μ≥ θ_g(X^μ_n,n+2,p^μ_f),\, ∀μ, (3j) tp(X,Θ)+δo≤tq(X,Θ),∀(p,q)∈E≺. t_p(X, )+ _o≤ t_q(X, ),\, ∀(p,q)∈E_ . (3k) Constraint (3b) ensures that every monitoring point is visited by at least one team. Constraints (3c) and (3d) encode the UAVs’ energy limitation: a UAV arriving at the collect point ahead of the UGV must hover until it arrives, so it remains airborne for the longer of its own flight and the UGV’s relocation, both are bounded by τ¯a τ_a even if the corresponding travel times increase by δa _a and δg _g during the mission. Since the plan selects those times, (3c) and (3d) also limit how much longer a leg may take: a point can be delayed only as long as the UAVs’ energy permits. Constraint (3e) places all release and collect points on feasible ground, and (3f) ensures that each entry of a row other than the first and the last is either a point of UAVP_UAV or a repetition of the previous entry, imposing no restriction on how many points a tour may contain. Constraints (3g)-(3j) keep every selected time at or above the fastest traverse between the points involved. Finally, (3k) enforces the ordering requirement: whenever p must precede q, the p is visited at least δo _o earlier than q. The three parameters, δa _a, δg _g, and δo _o, provide robustness to disturbances that increase travel times during execution, such as terrain effects, wind, or avoidance of previously unknown obstacles. The margins δa _a and δg _g help ensure that each tour remains feasible under the UAV endurance constraint, while δo _o provides robustness against violations of the precedence constraints. For each (p,q)∈E≺(p,q)∈ E_ , precedence is preserved as long as the accumulated delay at p exceeds that at q by no more than δo _o. Larger values of these margins restrict the feasible set to plans with greater robustness to travel-time disturbances, which can increase the minimum achievable makespan. I Proposed Solution Problem (3) is a mixed-integer program (MIP) that generalizes both the multiple traveling salesperson problem (mTSP) [18] and the sequential ordering problem (SOP) [19]33 3 The mTSP asks a set of agents to collectively visit every node at minimum cost; the SOP asks for a minimum-cost Hamiltonian path respecting a partial order on the nodes with a single agent. it is therefore NP-hard, and exact methods such as branch and cut [20] become intractable for large |UAV||P_UAV|. We propose Alg. 1, a polynomial-time heuristic, to solve (3) and present its formal guarantees in this section.44 4 These concern feasibility and worst-case time complexity. No approximation ratio or bound on solution quality relative to the optimum is established. I-A Proposed Robust Planning Algorithm The constraint (3k) is what makes (3) hard to divide among the teams. One could avoid the difficulty by assigning each weakly connected component of G≺G_ to an individual team and ordering that team’s visits consistently with G≺G_ , after which every team could be planned independently. We do not, because the number of components then bounds how many teams can be assigned points: when G≺G_ forms a single component, one team receives the entire mission regardless of m, and all remaining teams are forced to stay idle. Instead, Alg. 1 distributes ordered points across teams, so two points with precedence constraint may be visited by different teams. Without (3k), the points can be assigned among the m teams and each team can then be planned independently. Such a decoupled sequential approach (e.g., [8]) is inadequate under (3k) since precedence constraints between points assigned to different teams couple the team plans through their visit times. In our approach, the assignment, the sequences, the tours, and the timing are constructed simultaneously by placing one point per iteration. Accordingly, the visit time of each point is known when it is added to a team’s plan, and each new visit is planned with respect to the already determined visit times of its predecessors. Fig. 1 illustrates the output of Alg. 1. Fig. 1: Alg. 1 for n=25n=25 and m=4m=4. (a) G≺=(UAV,E≺)G_ =(P_UAV,E_ ), shaded by longest-path depth (light for sources, dark for sinks), hollow circles unordered points. (b) The plan in space (top view), color-coded by team: squares release points, filled pentagons selected collect points, hollow pentagons feasible collect points not taken, solid lines UAV flights, dashed lines UGV paths, triangles psμp^μ_s and pfμp^μ_f, shared by all teams here. The plan respects the ordering requirements. Algorithm 1 Precedence-Aware Robust UAV-UGV Planning Input : UAVP_UAV (n points to visit), G≺=(UAV,E≺)G_ =(P_UAV,E_ ) (Precedence graph), m (Number of teams), psμ,pfμ=1m\p^μ_s,p^μ_f\_μ=1^m (Team start/finish positions) , π(⋅)π(·) (Projection function), fg,faQ_f^g,Q_f^a (Feasible ground, air space), θ¯a,θ¯g θ_a, θ_g (UAV, UGV travel time lower bounds), τc _c (Recharge function), τ¯a τ_a (Max. flight time), δa,δg,δo _a, _g, _o (Robustness margins) Output : (X,Θ)(X, ), X=Xμ=1mX=\X^μ\_μ=1^m (Mission plan), Θ=Θμ=1m =\ ^μ\_μ=1^m (Timing) Initialize: ∀μ∀μ: Xμ←∅X^μ← ; Θaμ←n×(n+1) _a^μ 0_n×(n+1); Θgμ←n _g^μ 0_n; Θgaμ←n−1 _ga^μ 0_n-1; θsμ←0 _s^μ← 0; θfμ←0 _f^μ← 0; iμ←0i_μ← 0; jμ←2j_μ← 2; Γμ←0 _μ← 0; ημ←0 _μ← 0; Cμ←∅C_μ← ; Tμ←0T_μ← 0 1 ←∅A← ; ℛ←q∈UAV∣(p,q)∉E≺∀p∈UAVR←\q _UAV (p,q)∉ E_ \ \,∀ p _UAV\ 2 while ℛ≠∅R≠ do 3 foreach μ∈1,…,mμ∈\1,…,m\ and q∈ℛq do 4 wq←max(0∪tp+δo∣(p,q)∈E≺)w_q← (\0\∪\t_p+ _o (p,q)∈ E_ \ ) 5 C′←∅C ← ; r←nullr ; c←nullc ; Γ′←null 6 if iμ≥1i_μ≥ 1 then 7 e←Γμ+ημ+θ¯a(Xiμ,jμ−1μ,q)e← _μ+ _μ+ θ_a(X^μ_i_μ,j_μ-1,q) 8 σa←max(0,wq−e) _a← (0,\,w_q-e ); σg←0 _g← 0 9 P←π(Xiμ,kμ)2≤k<jμ∪π(q)P←\π(X^μ_i_μ,k)\_2≤ k<j_μ∪\π(q)\ 10 C′←c^∈P|ημ+θ¯a(Xiμ,jμ−1μ,q)+σa+θ¯a(q,c^)+δa≤τ¯aandθ¯g(Xiμ,1μ,c^)+δg≤τ¯aC ← \ c∈ P\ |\ _μ+ θ_a(X^μ_i_μ,j_μ-1,q)+ _a+ θ_a(q, c)+ _a≤ τ_a\ and\ θ_g(X^μ_i_μ,1, c)+ _g≤ τ_a \ 11 t←e+σat← e+ _a 12 if C′=∅C = then 13 r←π(q)r←π(q) 14 if iμ=0i_μ=0 then 15 e←θ¯g(psμ,r)+θ¯a(r,q)e← θ_g(p^μ_s,r)+ θ_a(r,q) 16 σg←max(0,wq−e) _g← (0,\,w_q-e ); σa←0 _a← 0 17 Γ′←θ¯g(psμ,r)+σg ← θ_g(p^μ_s,r)+ _g 18 else 19 c←argminc^∈Cμb^+max(θ¯g(c^,r),τc(b^))|b^=max(ημ+θ¯a(Xiμ,jμ−1μ,c^),θ¯g(Xiμ,1μ,c^))c← arg\,min _ c∈ C_μ \ b+ ( θ_g( c,r),\, _c( b) )\ |\ b= ( _μ+ θ_a(X^μ_i_μ,j_μ-1, c),\, θ_g(X^μ_i_μ,1, c) ) \ 20 b←max(ημ+θ¯a(Xiμ,jμ−1μ,c),θ¯g(Xiμ,1μ,c))b← ( _μ+ θ_a(X^μ_i_μ,j_μ-1,c),\, θ_g(X^μ_i_μ,1,c) ) 21 e←Γμ+b+max(θ¯g(c,r),τc(b))+θ¯a(r,q)e← _μ+b+ ( θ_g(c,r),\, _c(b) )+ θ_a(r,q) 22 σg←max(0,wq−e) _g← (0,\,w_q-e ); σa←0 _a← 0 23 Γ′←Γμ+b+max(θ¯g(c,r),τc(b))+σg ← _μ+b+ ( θ_g(c,r),\, _c(b) )+ _g 24 t←Γ′+θ¯a(r,q)t← + θ_a(r,q); C′←rC ←\r\ 25 ⟨t,r,c,σa,σg,C′,Γ′⟩μ,q←⟨t,r,c,σa,σg,C′,Γ′⟩ t,r,c, _a, _g,C , ^μ,q← t,r,c, _a, _g,C , 26 (μ⋆,q⋆)←argminμ∈1,…,m,q∈ℛmax(tμ,q,maxν≠μTν)(μ ,q )← arg\,min _μ∈\1,…,m\,\,q (t^μ,q,\, _ν≠μT_ν ) 27 ⟨t,r,c,σa,σg,C′,Γ′⟩←⟨t,r,c,σa,σg,C′,Γ′⟩μ⋆,q⋆ t,r,c, _a, _g,C , ← t,r,c, _a, _g,C , ^μ ,q 28 μ←μ⋆μ←μ ; q←q⋆q← q 29 if r=nullr=null then 30 Xiμ,jμ←qX^μ_i_μ,j_μ← q 31 θaμ,iμ,jμ−1←θ¯a(Xiμ,jμ−1μ,q)+σaθ^μ,i_μ,j_μ-1_a← θ_a(X^μ_i_μ,j_μ-1,q)+ _a 32 ημ←ημ+θaμ,iμ,jμ−1 _μ← _μ+θ^μ,i_μ,j_μ-1_a 33 else 34 if iμ≥1i_μ≥ 1 then 35 Xμiμ,jμ:n+1←Xμiμ,jμ−1X^μ_i_μ,\,j_μ:n+1← X^μ_i_μ,j_μ-1; Xiμ,n+2μ←cX^μ_i_μ,n+2← c 36 θaμ,iμ,n+1←θ¯a(Xiμ,jμ−1μ,c)θ^μ,i_μ,n+1_a← θ_a(X^μ_i_μ,j_μ-1,c) 37 θgμ,iμ←θ¯g(Xiμ,1μ,c)θ^μ,i_μ_g← θ_g(X^μ_i_μ,1,c) 38 b←max(ημ+θaμ,iμ,n+1,θgμ,iμ)b← ( _μ+θ^μ,i_μ,n+1_a,\,θ^μ,i_μ_g); θgaμ,iμ←max(θ¯g(c,r),τc(b))+σgθ^μ,i_μ_ga← ( θ_g(c,r),\, _c(b) )+ _g 39 else 40 θsμ←θ¯g(psμ,r)+σgθ^μ_s← θ_g(p^μ_s,r)+ _g 41 iμ←iμ+1i_μ← i_μ+1; jμ←2j_μ← 2; Γμ←Γ′ _μ← 42 Xiμ,1μ←rX^μ_i_μ,1← r; Xiμ,2μ←qX^μ_i_μ,2← q 43 θaμ,iμ,1←θ¯a(r,q)θ^μ,i_μ,1_a← θ_a(r,q); ημ←θaμ,iμ,1 _μ←θ^μ,i_μ,1_a 44 Cμ←C′C_μ← C ; jμ←jμ+1j_μ← j_μ+1; tq←t_q← t; Tμ←tT_μ← t 45 ←∪qA ∪\q\ 46 ℛ←(ℛ∖q)∪s∣(q,s)∈E≺,p∈∀(p,s)∈E≺R← (R \q\ )∪\s (q,s)∈ E_ ,\ \,p \ ∀(p,s)∈ E_ \ 47 for μ←1μ← 1 to m do 48 if iμ≥1i_μ≥ 1 then 49 c←argminc^∈Cμb^+θ¯g(c^,pfμ)|b^=max(ημ+θ¯a(Xiμ,jμ−1μ,c^),θ¯g(Xiμ,1μ,c^))c← arg\,min _ c∈ C_μ \ b+ θ_g( c,p^μ_f)\ |\ b= ( _μ+ θ_a(X^μ_i_μ,j_μ-1, c),\, θ_g(X^μ_i_μ,1, c) ) \ 50 Xμiμ,jμ:n+1←Xμiμ,jμ−1X^μ_i_μ,\,j_μ:n+1← X^μ_i_μ,j_μ-1; Xiμ,n+2μ←cX^μ_i_μ,n+2← c 51 θaμ,iμ,n+1←θ¯a(Xiμ,jμ−1μ,c)θ^μ,i_μ,n+1_a← θ_a(X^μ_i_μ,j_μ-1,c) 52 θgμ,iμ←θ¯g(Xiμ,1μ,c)θ^μ,i_μ_g← θ_g(X^μ_i_μ,1,c); θfμ←θ¯g(c,pfμ)θ^μ_f← θ_g(c,p^μ_f) 53 Xμiμ+1:n,:←cX^μ_i_μ+1:n,\,:← c 54 else 55 Xμ1:n,:←pμfX^μ_1:n,\,:← p^μ_f 56 θsμ←θ¯g(psμ,pfμ)θ^μ_s← θ_g(p^μ_s,p^μ_f) 57 return (X,Θ)(X, ) Alg. 1 operates iteratively, placing one monitoring point per loop (lines 3-47). Line 1 initializes the state for each team μ: the plan matrix XμX^μ and timing matrices Θaμ,Θgμ,Θgaμ _a^μ, _g^μ, _ga^μ alongside their start/finish scalars θsμ,θfμ _s^μ, _f^μ strictly to zero, the active tour (row) index iμi_μ, the column index jμj_μ, the clock Γμ _μ tracking the time the current tour is released from the UGV, the accumulated flight time ημ _μ of the tour, the candidate collect points CμC_μ of the tour, and the team’s accumulated cost TμT_μ. Line 2 initializes the placed set A and the ready set ℛR, holding the points whose required predecessors in G≺G_ are in A. Lines 4-26 evaluate every pairing of a team μ and a ready point q. Line 5 computes wqw_q, the earliest visit time permitted by the precedence constraints, ensuring q occurs at least δo _o after all its placed predecessors. Line 6 initializes local provisional variables: candidate collect set C′C , next release point r, collect point c, and tour release clock Γ′ . Line 7 checks if team μ currently has an open tour (iμ≥1i_μ≥ 1). If so, line 8 calculates the express time e, the earliest possible arrival at q, by adding the accumulated flight ημ _μ and the new flight leg to the release clock Γμ _μ. Line 9 calculates the airborne wait σa _a necessary to delay this arrival until wqw_q, setting the ground wait σg _g to 0. Line 10 gets the potential collect points P, the ground projections of all air points currently in the tour plus q. Line 11 filters P to retain only the subset C′C that maintains UAV and UGV energy feasibility when σa _a is included. Line 12 sets the final arrival time t at q by adding the airborne wait σa _a to the express time e. Line 13 checks if C′C is empty, which occurs if q violates the energy check (line 11) or if it is the team’s first tour. If empty, q opens a new tour, and line 14 sets the new release point r to q’s feasible ground projection π(q)π(q). If this is the team’s first tour (line 15), line 16 calculates the express time e by summing the fastest UGV drive from psμp_s^μ to r and the fastest UAV flight from r to q. Line 17 calculates the required ground wait σg _g, setting σa _a to 0. Line 18 sets the provisional release clock Γ′ by adding the drive time and the wait σg _g. If a prior tour is already open (line 19), it must be closed first. Line 20 selects a collect point c∈Cμc∈ C_μ that minimizes the total time to finish the closing tour, recharge the UAV, and drive the UGV to the new release point r. Line 21 defines the closing tour’s airborne time b as the longer of the UGV’s drive to c and the UAV’s total flight (the accumulated flight ημ _μ plus the landing leg from the latest point to c). Line 22 gets the express time e at q from the release clock Γμ _μ, adding the airborne time b, the gap time (the longer of the UGV transit to r or the UAV recharge), and the initial flight to q. Line 23 calculates the required ground wait σg _g. Line 24 calculates the provisional release clock Γ′ for the new tour by adding the flight, gap time, and wait σg _g to the release clock Γμ _μ. Line 25 sets the final arrival time t at q and sets the new tour’s candidate collect set to r\r\. Line 26 stores this evaluated option. Line 27 selects the pairing (μ⋆,q⋆)(μ ,q ) minimizing the maximum accumulated team cost TνT_ν (breaking ties lexicographically, if applicable). This distributes the workload rather than greedily visiting individual points early. Lines 28 and 29 unpack and commit this winning option. Lines 30-47 commit the selected pairing. The algorithm prioritizes the standard case: line 30 checks if r=nullr=null, meaning q simply joins the existing open tour. If so, line 31 writes q into the next free matrix entry, and lines 32-33 apply the airborne wait σa _a to the inbound flight leg and update the accumulated flight ημ _μ. Conversely, if r≠nullr (line 34), a new tour is opened. Line 35 checks if a currently open tour must be closed first. If so, line 36 pads the unused air columns with the current location Xiμ,jμ−1μX^μ_i_μ,j_μ-1, and lines 37-39 write the landing leg, UGV relocation, and transport timing, explicitly including the ground wait σg _g in the transport time. For a team’s first tour, line 41 instead writes the initial UGV drive time plus the wait σg _g to θsμ _s^μ. Lines 42-44 then advance the team state: the row index iμi_μ increments, the column index jμj_μ resets to 2, the active release clock Γμ _μ updates to the provisional clock Γ′ , the accumulated flight ημ _μ is reset, and the new tour is initialized with r and q in the first two entries of the new row. Line 45 then finalizes the shared state updates: it commits the candidate collect set CμC_μ, increments the column index jμj_μ, sets the final visit time tqt_q, and updates the team’s cost TμT_μ. Lines 46-47 add q to A and update ℛR by admitting any successors whose predecessors are now all placed. Lines 48-58 execute a closure pass once ℛ=∅R= . For active teams (iμ≥1i_μ≥ 1), line 50 selects the final collect point c∈Cμc∈ C_μ minimizing the drive to pfμp_f^μ. Line 51 closes the final active row, and lines 52-53 assign the landing leg, final UGV relocation, and final transport timing θfμ _f^μ. If a team remains idle, lines 56-57 bypass these steps, routing the UGV directly from psμp_s^μ to pfμp_f^μ. Lines 54 and 56 pad unused matrix entries, and line 58 returns the plan X and timing Θ . I-B Formal Guarantees We now state formal guarantees on the feasibility of the solution returned by Alg. 1 and on its worst-case complexity. Assumption 1 Every point q∈UAVq _UAV admits a feasible single-point tour from its ground projection π(q)π(q) i.e., θ¯a(π(q),q)+θ¯a(q,π(q))+δa≤τ¯a θ_a(π(q),q)+ θ_a(q,π(q))+ _a≤ τ_a and θ¯g(π(q),π(q))+δg≤τ¯a θ_g(π(q),π(q))+ _g≤ τ_a.55 5 This is a mild condition: the UAVs must at least have the energy to complete a single-point tour (taking off from a stationary UGV, visiting the point, and landing back on the UGV). Theorem 1 Under Assumption 5, Alg. 1 returns a feasible solution to (3) if one exists, and has worst-case time complexity (mn3)O(mn^3), where m is the number of UAV-UGV teams and n=|UAV|n=|P_UAV| is the number of monitoring points. Proof: (Feasibility.) Alg. 1 iteratively constructs the mission plan via a while loop (lines 3-47). Since G≺G_ is a DAG, the shrinking subset of unplaced points always contains at least one point with no unplaced predecessors; by construction (lines 2, 47), this point belongs to the ready set ℛR. Each iteration assigns one point q∈ℛq to a team. The algorithm appends q to an open tour if energy constraints permit (lines 11, 30-33), or otherwise opens a new tour at the ground projection π(q)π(q) (lines 13-14, 34-44). Under Assumption 5, this new tour is energy-feasible. Since a valid assignment is always available, the loop terminates in exactly n iterations, placing every monitoring point into exactly one team’s plan, satisfying (3b). If q joins an open tour, the algorithm enforces energy-feasibility (line 11) before committing the point to the plan (lines 30-33). If q instead opens a new tour, the release and candidate collect points are set to π(q)π(q) (lines 14, 25) and committed to the plan (lines 34-44). Under Assumption 5, this tour is also energy-feasible, satisfying (3c) and (3d). If appending to an open tour, candidate collect points P are generated using the feasible ground projection π(⋅)π(·) (line 10) and filtered into a subset C′C (line 11). If opening a new tour instead, the release point is set to the ground projection π(q)π(q) (line 14) and C′C is populated with this projected point (line 25). In both cases, C′C updates the team’s candidate set CμC_μ (line 45). Since the collect point c is selected from CμC_μ (lines 20, 50), every release and collect point of the plan (lines 36, 43, 51, 54, 56) is from fgQ_f^g, satisfying (3e). The target q∈UAVq _UAV is added to the tour either when appending to an open tour (line 31) or when opening a new tour (line 43). Unused entries within an active row are padded with the last visited point Xiμ,jμ−1μX^μ_i_μ,j_μ-1 (lines 36, 51), while any completely unused subsequent rows are padded with the final collect point c or pfμp_f^μ (lines 54, 56), satisfying (3f). The algorithm computes wait times σa,σg≥0 _a, _g≥ 0 (lines 9, 17, 23). For active legs, each timing variable in Θ is initialized to zero (line 1) and assigned either the fastest travel time, or the fastest travel time plus the corresponding wait (lines 32, 37-39, 41, 44, 52-53, 57). Since the matrices are zero-initialized and σa,σg≥0 _a, _g≥ 0, every active duration is greater than or equal to its fastest travel time, and padded edges remain zero, satisfying (3g), (3h), (3i), and (3j). A point q enters the ready set ℛR only after all of its predecessors are placed (line 47). Since every placed predecessor already has a known visit time tpt_p from a previous iteration (line 45), the algorithm can compute a lower bound wqw_q that strictly enforces the ordering margin δo _o against all of them (line 5). By calculating and imposing the wait times σa,σg _a, _g (lines 9, 17, 23), the resulting candidate visit time t is forced to satisfy t≥wqt≥ w_q (lines 12, 25). When q is assigned to a team, its final visit time tqt_q is committed as t (line 45). Thus, tq≥tp+δot_q≥ t_p+ _o for all (p,q)∈E≺(p,q)∈ E_ , satisfying (3k). Therefore, under Assumption 5, Algorithm 1 returns a feasible solution to (3), if one exists. (Complexity.) Alg. 1 initializes the ready set ℛR (line 2), taking (n+|E≺|)O(n+|E_ |) time to scan G≺G_ . The main while loop (line 3) terminates in n iterations. Within each iteration, a nested foreach loop (lines 4-26) evaluates all pairings of team μ∈1,…,mμ∈\1,…,m\ and q∈ℛq . Since |ℛ|≤n|R|≤ n, this inner loop checks at most mnmn options. During this foreach, computing wqw_q (line 5) across all q∈ℛq for a given team takes (|E≺|)O(|E_ |) time. Checking energy feasibility (lines 10-11) requires finding feasible ground projections π(⋅)π(·) for each point in the active tour of at most n points. Assuming a bounded number of obstacle faces, each projection takes fixed time, requiring (n)O(n) time per pairing. Selecting a collect point c∈Cμc∈ C_μ (line 20) scans at most n candidates, adding (n)O(n) time per pairing. All remaining calculations and assignments within the loop take fixed time. Consequently, the inner loop operations require a total of (m|E≺|+mn2)O(m|E_ |+mn^2) time per outer iteration. After the foreach, selecting the (μ⋆,q⋆)(μ ,q ) (line 27) takes (mn)O(mn) time per iteration. Committing this selection and updating the state matrices (lines 28-45) requires padding up to n column entries (line 36), taking (n)O(n) time per iteration. Updating ℛR (line 47) takes an aggregate (n+|E≺|)O(n+|E_ |) time across all n iterations by tracking in-degrees. Finally, a for loop over the m teams (lines 48-58) scans at most n candidates to select the final collect point (line 50), taking (n)O(n) time per team. The remaining matrix assignments (lines 51, 54, 56) pad up to n rows of length n+2n+2, taking (n2)O(n^2) time per team, requiring a total of (mn2)O(mn^2) time. Summing these yields (n+|E≺|+mn|E≺|+mn3+mn2+n2+mn2)O(n+|E_ |+mn|E_ |+mn^3+mn^2+n^2+mn^2). Since G≺G_ is a directed acyclic graph, |E≺|≤n(n−1)/2|E_ |≤ n(n-1)/2. Thus, the (mn3)O(mn^3) term dominates, yielding an overall worst-case time complexity of (mn3)O(mn^3). IV Numerical Evaluations We evaluate Alg. 1 on: (i) scalability, (i) precedence density effect, (i) robustness margin effect, and compare against (iv) branch and cut, (v) simulated annealing, and a (vi) decoupled precedence greedy baseline. Python 3.9 on running on Intel i9-13900H CPU with 16GB RAM was used. The environment is (1), and UAVP_UAV is drawn uniformly from faQ^a_f at altitude z¯ z. A VTOL UAV is used, flying the horizontal component ℓH _H of each leg at speed sHs_H and the vertical component ℓV _V at speed sV<sHs_V<s_H [21].66 6 In practice, most UAVs have higher horizontal speeds than vertical. G≺G_ is generated by drawing a random permutation of UAVP_UAV and adding ⌊dn⌉ dn edges between random pairs, each directed from the earlier point in the permutation to the later, so no cycle can form. Unless otherwise specified, (i) all results77 7 For brevity, the makespan maxμτ(Xμ,Θμ) _μτ(X^μ, ^μ) is denoted by maxμτ _μτ. are reported as mean ± standard deviation over 25 randomly generated instances, each with its own G≺=(UAV,E≺)G_ =(P_UAV,E_ ), and (i) the parameters of Table I are used. TABLE I: Mission and Method Parameters Parameter Value x¯,y¯ x, y (Environment size) 4000 m z¯ z (Monitoring height) 100 m psμ,pfμ=1m\p^μ_s,p^μ_f\_μ=1^m (Start, finish positions) (0,0,0)(0,0,0), (4000,4000,0)(4000,4000,0) d (Precedence density) 0.50.5 ℓ(u,v) (u,v) (Shortest path) ∥u−v∥2 u-v _2 sH,sVs_H,s_V (UAV cruise, climb speed) 10 m/s, 2 m/s sgs_g (UGV speed) 2.5 m/s θ¯a(u,v) θ_a(u,v) (UAV fastest travel time) ℓH(u,v)/sH+ℓV(u,v)/sV _H(u,v)/s_H+ _V(u,v)/s_V θ¯g(u,v) θ_g(u,v) (UGV fastest travel time) ℓ(u,v)/sg (u,v)/s_g τc(⋅) _c(·) (Recharge function) γmax(τa(Xiμ,Θμ),τg(Xiμ,Θμ))γ ( _a(X^μ_i, ^μ),\, _g(X^μ_i, ^μ) ) γ (Recharge ratio) 1 τ¯a τ_a (Max flight time) 600 s δa,δg _a, _g (Energy robustness margins) 0 s δo _o (Ordering robustness margin) 0 s IV-A Scalability Table I evaluates the scalability of Alg. 1 across n∈25,50,75,100n∈\25,50,75,100\ and m∈1,2,4,10m∈\1,2,4,10\. Empirical computation times scale at n2.15n^2.15–n2.26n^2.26 and m0.62m^0.62–m0.68m^0.68, consistent with the theoretical (mn3)O(mn^3) bound (Thm. 1). Makespan predictably increases with n and decreases as m parallelizes the teams. Alg. 1 reliably computes large-scale instances, solving the most demanding configuration (n=100n=100, m=10m=10) in under 0.350.35 s. TABLE I: Makespan (maxμτ _μτ) and computation time under Alg. 1 across numbers of points (n) and numbers of teams (m) m=1m=1 m=2m=2 n maxμτ _μτ (s) Comp. (s) maxμτ _μτ (s) Comp. (s) 25 8900 ± 1200 0.004 ± 0.001 5400 ± 850 0.006 ± 0.001 50 10900 ± 1700 0.015 ± 0.002 6800 ± 810 0.026 ± 0.003 75 13300 ± 1400 0.038 ± 0.004 7500 ± 760 0.064 ± 0.006 100 15100 ± 1600 0.071 ± 0.005 8300 ± 880 0.126 ± 0.015 m=4m=4 m=10m=10 n maxμτ _μτ (s) Comp. (s) maxμτ _μτ (s) Comp. (s) 25 4000 ± 570 0.009 ± 0.001 3500 ± 290 0.015 ± 0.002 50 4400 ± 470 0.042 ± 0.004 3500 ± 320 0.072 ± 0.007 75 4900 ± 480 0.107 ± 0.011 3600 ± 230 0.181 ± 0.016 100 5300 ± 540 0.205 ± 0.021 3900 ± 310 0.342 ± 0.033 IV-B Effect of Precedence Density We evaluate precedence densities d∈0.5,1,3,8,20d∈\0.5,1,3,8,20\ for m∈1,4,10m∈\1,4,10\ and n=100n=100, spanning 5050 to 20002000 precedence edges (|E≺||E_ |), summarized in Table I. Increasing d from 0.50.5 to 2020 severely restricts routing freedom; the mean size of the ready set ℛR drops from 31.631.6 to 2.02.0, and the longest chain (c) forces 51%51\% of the points into a sequential bottleneck (c/n=0.51c/n=0.51). To counter this, Alg. 1 parallelizes teams. Even when dense edges (high d) merge the entire G≺G_ into a single connected component, the algorithm continues to distribute points across teams. Consequently, expanding from m=1m=1 to m=10m=10 teams achieves an 89%89\% makespan reduction at d=20d=20, exceeding the 74%74\% reduction observed in d=0.5d=0.5. TABLE I: Makespan (maxμτ _μτ) of Alg. 1 across precedence densities (d) and numbers of teams (m) at n=100n=100. c is the longest chain in G≺G_ , and Red. is the makespan reduction from m=1m=1 to m=10m=10 maxμτ _μτ (s) d c/nc/n m=1m=1 m=4m=4 m=10m=10 Red. (%) 0.5 0.04 15100 ± 1600 5300 ± 540 3900 ± 310 74 1 0.06 17900 ± 1600 6200 ± 570 4200 ± 260 77 3 0.12 27600 ± 2500 7600 ± 530 4900 ± 240 82 8 0.26 40400 ± 4600 9900 ± 890 5500 ± 360 86 20 0.51 57100 ± 4800 12000 ± 1100 6000 ± 410 89 IV-C Effect of Robustness Margins We evaluate the energy margins (δa=δg∈[0,490] _a= _g∈[0,490] s) and the ordering margin (δo∈[0,1600] _o∈[0,1600] s) independently for m∈1,2,4,10m∈\1,2,4,10\ teams at n=100n=100, summarized in Fig. 2. These margins affect parallelism differently. Increasing energy margins shortens tours, but these tours remain easy to distribute; thus, the makespan reduction from m=1m=1 to m=10m=10 remains stable around 75%75\% to 80%80\%. Conversely, increasing the ordering margin forces teams to wait, causing the makespan curves to converge. At large δo _o, the makespan reduction from m=1m=1 to m=10m=10 drops to 58%58\%, and the benefit of expanding from m=4m=4 to m=10m=10 shrinks from 28%28\% to 8%8\%. Small ordering margins (δo≤200 _o≤ 200 s) are absorbed with almost no extra time. Ultimately, the margins constrain the problem differently: δa _a and δg _g impose spatial costs that multiple teams can divide, whereas δo _o imposes strict wait times that inherently limit parallel efficiency. Fig. 2: Makespan under Alg. 1 against the energy margins δa=δg _a= _g (left) and the ordering margin δo _o (right), at n=100n=100, each sweep holding the remaining margins at zero. Error bars are ±1± 1 std. IV-D Comparison to Branch and Cut We encode (3) as a Mixed-Integer Quadratically Constrained Program (MIQCP) solved with Branch & Cut (B&C) via Gurobi88 8 MipGap: 5%, TimeLimit: 600 s, FeasibilityTol: 10−410^-4, IntFeasTol: 10−510^-5, OptimalityTol: 10−310^-3, NonConvex: 2 to establish a near-optimal reference (Table IV). As expected, B&C experiences combinatorial explosion, therefore, we use n∈2,3,4n∈\2,3,4\ and m∈1,2m∈\1,2\ for tractability. As n increases from 2 to 4, computation time scales exponentially, surging to over 200 seconds for m=2m=2 at n=4n=4 to reach the 5% optimality threshold. In contrast, Alg. 1 computes in less than a millisecond across all configurations, achieving makespans within roughly 8%8\% to 28%28\% of near-optimal. TABLE IV: Makespan (maxμτ _μτ), computation time, and optimality gap of the Branch and Cut (B&C) against Alg. 1 across different number of points (n)(n) and team sizes (m) Branch & Cut Alg. 1 m n maxμτ _μτ (s) Comp. (s) Gap (%) maxμτ _μτ (s) Comp. (s) 1 2 2800 ± 380 0.19 ± 0.12 1.2 ± 2.0 3100 ± 750 <0.001<0.001 3 2800 ± 360 1.4 ± 1.0 1.5 ± 1.9 3200 ± 800 <0.001<0.001 4 3100 ± 330 19 ± 16 2.1 ± 1.8 3900 ± 890 <0.001<0.001 2 2 2600 ± 290 0.49 ± 0.33 1.5 ± 1.8 2800 ± 310 <0.001<0.001 3 2600 ± 330 13 ± 12 2.8 ± 2.2 2800 ± 210 <0.001<0.001 4 2500 ± 360 210 ± 110 1.5 ± 1.6 3200 ± 490 <0.001<0.001 IV-E Comparison to Simulated Annealing We compare Alg. 1 against Simulated Annealing (SA) using a logarithmic cooling schedule [22] with Tmin=0.1T_min=0.1 (Table V). We restrict this evaluation to n=15n=15 and m∈1,2m∈\1,2\ because SA computation times become prohibitive for larger n and m. SA relies on local search, which struggles to explore efficiently because standard local search operators frequently generate precedence-violating sequences, resulting in high rejection rates, even at its best configuration (200k steps). By directly constructing feasible assignments, Alg. 1 avoids this bottleneck, achieving shorter makespans (7200±15507200± 1550 s for m=1m=1, 4500±7904500± 790 s for m=2m=2) while reducing computation time by roughly four orders of magnitude (0.001±0.000CLOSE(0.001± 0.000 s for m=1m=1, and 0.002±0.0000.002± 0.000 s for m=2m=2). TABLE V: Makespan (maxμτ _μτ) and computation time of Simulated Annealing across maximum temperatures (TmaxT_ ) and cooling steps for different number of teams (m) Comp. (s) maxμτ _μτ (s) m TmaxT_ 100k 150k 200k 100k 150k 200k 1 500 18.6 ± 1.2 27.7 ± 1.8 36.8 ± 2.3 8600 ± 1200 8100 ± 1200 7800 ± 1200 750 18.9 ± 1.2 28.3 ± 2.0 37.7 ± 2.5 8400 ± 1200 8100 ± 1200 7800 ± 1200 1000 19.6 ± 1.6 29.3 ± 2.4 38.7 ± 3.1 8800 ± 1200 8200 ± 1200 7900 ± 1100 2 500 37.8 ± 2.4 55.8 ± 3.3 73.5 ± 4.0 6400 ± 1000 6000 ± 900 5700 ± 790 750 41.4 ± 4.7 61.7 ± 7.5 82.0 ± 9.8 7200 ± 1000 6800 ± 1100 6400 ± 1100 1000 46.3 ± 5.3 69.2 ± 8.7 92 ± 12 7900 ± 1200 7400 ± 1200 7200 ± 1200 IV-F Comparison to the Decoupled Precedence Baseline To isolate the impact of cross-team precedence, we compare Alg. 1 against a decoupled baseline that assigns each weakly connected component of G≺G_ to an individual team. The baseline estimates workloads via a precedence-respecting nearest-neighbor walk, distributes components using a Longest Processing Time (LPT) heuristic (i.e., assigning the component with the largest travel time to the team with the lowest accumulated time at the moment), and applies the identical tour-cutting and timing subroutines as Alg. 1. Keeping precedence edges internal guarantees feasibility and speeds up computation by avoiding cross-team timing checks. Evaluated for n=100n=100, m∈1,4,10m∈\1,4,10\, and d∈0.5,3,8,20d∈\0.5,3,8,20\ (Table VI), the baseline and Alg. 1 yield similar makespans for a single team. However, at d≥8.0d≥ 8.0, G≺G_ merges into a single connected component. The baseline assigns the entire mission to one team, freezing the makespan at 5880058800 s (for d=20d=20) regardless of m. Alg. 1 successfully distributes ordered points across multiple teams, achieving an 89.8%89.8\% makespan reduction for m=10m=10 at d=20d=20: a parallelization trend that continues to scale for larger number of teams. By skipping cross-team comparisons, the baseline computes faster in sparse scenarios (up to 57 times faster at d=0.5d=0.5). However, this trade-off heavily favors Alg. 1 in high-density missions, where it yields a nearly 10 times shorter makespan for a negligible time cost (0.0430.043 s versus 0.0100.010 s at d=20,m=10d=20,m=10). Furthermore, the computation time of Alg. 1 inversely scales with precedence density while operating strictly within its O(mn3)O(mn^3) worst-case guarantee. Denser precedence constraints shrink the ready set ℛR, which directly reduces the m×|ℛ|m×|R| pairings evaluated per iteration. Conversely, sparse precedence increases |ℛ||R|, causing Alg. 1 to evaluate a higher number of cross-team pairings. TABLE VI: Makespan (maxμτ _μτ) and computation time comparison between Alg. 1 and the decoupled precedence baseline for different precedence densities (d) and numbers of teams (m), at n=100n=100 maxμτ _μτ (s) Comp. (s) d m Baseline Alg. 1 Baseline Alg. 1 0.5 1 15400±210015400± 2100 ±15100± 1600 0.007±0.0000.007± 0.000 0.071±0.0050.071± 0.005 4 10400±110010400± 1100 ±5300± 540 0.006±0.0000.006± 0.000 0.205±0.0210.205± 0.021 10 8900±17008900± 1700 ±3900± 310 0.006±0.0010.006± 0.001 0.342±0.0330.342± 0.033 3.0 1 28800±290028800± 2900 ±27600± 2500 0.007±0.0010.007± 0.001 0.017±0.0020.017± 0.002 4 28700±290028700± 2900 ±7600± 530 0.008±0.0000.008± 0.000 0.055±0.0070.055± 0.007 10 28700±290028700± 2900 ±4900± 240 0.007±0.0010.007± 0.001 0.104±0.0140.104± 0.014 8.0 1 42400±360042400± 3600 ±40400± 4600 0.008±0.0000.008± 0.000 0.010±0.0010.010± 0.001 4 42400±360042400± 3600 ±9900± 890 0.008±0.0010.008± 0.001 0.029±0.0040.029± 0.004 10 42400±360042400± 3600 ±5500± 360 0.008±0.0010.008± 0.001 0.061±0.0060.061± 0.006 20 1 58800±520058800± 5200 ±57100± 4800 0.009±0.0000.009± 0.000 0.007±0.0010.007± 0.001 4 58800±520058800± 5200 ±12000± 1100 0.010±0.0010.010± 0.001 0.020±0.0010.020± 0.001 10 58800±520058800± 5200 ±6000± 410 0.010±0.0010.010± 0.001 0.043±0.0040.043± 0.004 V Conclusion We addressed precedence-constrained planning for energy-constrained UAV-UGV teams. We formulated a mixed-integer program (3) for this NP-hard planning problem and introduced a polynomial-time heuristic (Alg. 1) that simultaneously constructs assignments, energy-feasible tours, and travel timing. Guaranteed to find feasible solutions in (mn3)O(mn^3) time (Thm. 1), our approach effectively distributes ordered points across multiple teams. Numerical evaluations demonstrate that Alg. 1 scales to large instances that are intractable for exact solvers, and yields significantly shorter makespans than metaheuristic and heuristic baselines. Future work will extend the method to support additional spatio-temporal constraints, such as time windows and temporal logic. Additionally, we will incorporate online replanning to mitigate travel time disturbances during execution, alongside validation through real-world experimentation. References [1] P. Tokekar, J. Vander Hook, D. Mulla, and V. Isler (2016) Sensor planning for a symbiotic uav and ugv system for precision agriculture. IEEE transactions on robotics 32 (6), p. 1498–1511. Cited by: §I. [2] H. Ren, Y. Zhao, W. Xiao, and Z. Hu (2019) A review of uav monitoring in mining areas: current status and future perspectives. International Journal of Coal Science & Technology 6, p. . External Links: Document Cited by: §I. [3] K. Yu, A. K. Budhiraja, S. Buebel, and P. Tokekar (2019) Algorithms and experiments on routing of unmanned aerial vehicles with mobile recharging stations. Journal of Field Robotics 36 (3), p. 602–616. Cited by: §I, §I. [4] F. Ropero, P. Muñoz, and M. D. R-Moreno (2019) TERRA: a path planning algorithm for cooperative ugv–uav exploration. Engineering Applications of Artificial Intelligence 78, p. 260−272260--272. External Links: ISSN $0952-1976$, Document, Link Cited by: §I, §I. [5] S. Ramasamy, J. F. Reddinger, J. M. Dotterweich, M. A. Childers, and P. A. Bhounsule (2021) Cooperative route planning of multiple fuel-constrained unmanned aerial vehicles with recharging on an unmanned ground vehicle. In 2021 International Conference on Unmanned Aircraft Systems (ICUAS), p. 155–164. Cited by: §I, §I. [6] Y. Chen, M. Chen, Z. Chen, L. Cheng, Y. Yang, and H. Li (2021) Delivery path planning of heterogeneous robot system under road network constraints. Computers & Electrical Engineering 92, p. 107197. Cited by: §I, §I. [7] C. I. Er, S. Juttu, and Y. Yazicioglu (2026) Energy-aware collaborative exploration for a uav-ugv team. arXiv preprint arXiv:2603.22507. Cited by: §I, §I. [8] C. I. Er, A. Kashiri, and Y. Yazıcıoğlu (2026) Rspect: robust and scalable planner for energy-aware coordination of uav-ugv teams in aerial monitoring. Journal of Intelligent & Robotic Systems. Cited by: §I, §I, §I, §I, §I-A. [9] R. Fowler, C. I. Er, B. Johnsenberg, and Y. Yazicioglu (2026) PRO-spect: probabilistically safe scalable planning for energy-aware coordinated uav-ugv teams in stochastic environments. arXiv preprint arXiv:2604.02142. Cited by: §I, §I, §I. [10] G. A. Korsah, A. Stentz, and M. B. Dias (2013) A comprehensive taxonomy for multi-robot task allocation. The International journal of robotics research 32 (12), p. 1495–1512. Cited by: §I. [11] D. Bredstrom and M. Rönnqvist (2007) A branch and price algorithm for the combined vehicle routing and scheduling problem with synchronization constraints. NHH Dept. of Finance & Management Science Discussion Paper (2007/7). Cited by: §I. [12] M. C. Gombolay, R. J. Wilcox, and J. A. Shah (2018) Fast scheduling of robot teams performing tasks with temporospatial constraints. IEEE Transactions on Robotics 34 (1), p. 220–239. Cited by: §I. [13] E. Bischoff, F. Meyer, J. Inga, and S. Hohmann (2020) Multi-robot task allocation and scheduling considering cooperative tasks and precedence constraints. In 2020 IEEE international conference on systems, man, and cybernetics (SMC), p. 3949–3956. Cited by: §I. [14] A. Sojo, I. Maza, and A. Ollero (2024) Optimal planning for heterogeneous autonomous teams with precedence and compatibility constraints and its application on power grid inspection with unmanned aerial vehicles. arXiv preprint arXiv:2410.20849. Cited by: §I. [15] A. Ben-Tal, A. Nemirovski, and L. El Ghaoui (2009) Robust optimization. Cited by: §I. [16] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein (2009) Introduction to algorithms. p. 612–615. External Links: ISBN 978-0-262-03384-8 Cited by: §I. [17] A. Abdilla, A. Richards, and S. Burrow (2015) Power and endurance modelling of battery-powered rotorcraft. In 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), p. 675–680. Cited by: §I. [18] T. Bektas (2006) The multiple traveling salesman problem: an overview of formulations and solution procedures. omega 34 (3), p. 209–219. Cited by: §I. [19] L. F. Escudero (1988) An inexact algorithm for the sequential ordering problem. European Journal of Operational Research 37 (2), p. 236–249. Cited by: §I. [20] J. E. Mitchell (2002) Branch-and-cut algorithms for combinatorial optimization problems. Handbook of applied optimization 1 (1), p. 65–77. Cited by: §I. [21] Y. Guo, J. Guo, C. Liu, H. Xiong, L. Chai, and D. He (2020) Precision landing test and simulation of the agricultural uav on apron. Sensors 20 (12), p. 3369. Cited by: §IV. [22] Y. Nourani and B. Andresen (1998) A comparison of simulated annealing cooling strategies. Journal of Physics A: Mathematical and General 31 (41), p. 8373–8385. Cited by: §IV-E.