Paper deep dive
PRO-SPECT: Probabilistically Safe Scalable Planning for Energy-Aware Coordinated UAV-UGV Teams in Stochastic Environments
Roger Fowler, Cahit Ikbal Er, Benjamin Johnsenberg, Yasin Yazicioglu
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 95%
Last extracted: 4/2/2026, 11:46:14 PM
Summary
PRO-SPECT is a polynomial-time planning algorithm for energy-aware coordination of UAV-UGV teams in stochastic environments. It uses a Mixed-Integer Program formulation with joint chance constraints to bound the probability of mission failure (energy depletion) while minimizing expected completion time. The framework supports both offline planning and online re-planning via a receding horizon approach, ensuring robustness against environmental disturbances.
Entities (5)
Relation Signals (3)
UGV → charges → UAV
confidence 100% · relying on the UGV as a mobile charging station
PRO-SPECT → plansfor → UAV-UGV Team
confidence 100% · PRO-SPECT, a polynomial-time algorithm that generates risk-bounded plans for energy-aware coordinated UAV-UGV teams
PRO-SPECT → optimizes → Mission Time
confidence 90% · minimizing mission time
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We consider energy-aware planning for an unmanned aerial vehicle (UAV) and unmanned ground vehicle (UGV) team operating in a stochastic environment. The UAV must visit a set of air points in minimum time while respecting energy constraints, relying on the UGV as a mobile charging station. Unlike prior work that assumed deterministic travel times or used fixed robustness margins, we model travel times as random variables and bound the probability of failure (energy depletion) across the entire mission to a user-specified risk level. We formulate the problem as a Mixed-Integer Program and propose PRO-SPECT, a polynomial-time algorithm that generates risk-bounded plans. The algorithm supports both offline planning and online re-planning, enabling the team to adapt to disturbances while preserving the risk bound. We provide theoretical results on solution feasibility and time complexity. We also demonstrate the performance of our method via numerical comparisons and simulations.
Tags
Links
- Source: https://arxiv.org/abs/2604.02142v1
- Canonical: https://arxiv.org/abs/2604.02142v1
Trouble viewing inline? Open PDF directly →
Full Text
55,224 characters extracted from source content.
Expand or collapse full text
PRO-SPECT: Probabilistically Safe Scalable Planning for Energy-Aware Coordinated UAV–UGV Teams in Stochastic Environments Roger Fowler∗, Cahit Ikbal Er∗, Benjamin Johnsenberg, and Yasin Yazıcıoğlu ∗These authors contributed equally.R. Fowler is with the Khoury Department of Computer Sciences at Northeastern University, Boston, MA and a Draper Scholar with The Charles Stark Draper Laboratory, Inc., Cambridge, MA.C. I. Er is with the Department of Mechanical and Industrial Engineering at Northeastern University, Boston, MA.B. Johnsenberg is with The Charles Stark Draper Laboratory, Inc., Cambridge, MA.Y. Yazıcıoğlu is with the Departments of Mechanical and Industrial Engineering and Electrical and Computer Engineering at Northeastern University, Boston, MA.emails: fowler.ro@northeastern.edu, er.c@northeastern.edu, bcjohnson@draper.com, y.yazicioglu@northeastern.edu Abstract We consider energy-aware planning for an unmanned aerial vehicle (UAV) and unmanned ground vehicle (UGV) team operating in a stochastic environment. The UAV must visit a set of air points in minimum time while respecting energy constraints, relying on the UGV as a mobile charging station. Unlike prior work that assumed deterministic travel times or used fixed robustness margins, we model travel times as random variables and bound the probability of failure (energy depletion) across the entire mission to a user-specified risk level. We formulate the problem as a Mixed-Integer Program and propose PRO-SPECT, a polynomial-time algorithm that generates risk-bounded plans. The algorithm supports both offline planning and online re-planning, enabling the team to adapt to disturbances while preserving the risk bound. We provide theoretical results on solution feasibility and time complexity. We also demonstrate the performance of our method via numerical comparisons and simulations. I Introduction Unmanned aerial vehicles (UAVs) are used in various domains such as agriculture, disaster response, and environmental monitoring (e.g., [tokekar2016sensor, boccardo2015uav, manfreda2018use]). However, their limited batteries restrict long-horizon missions. Using unmanned ground vehicles (UGVs) as mobile charging stations addresses this limitation by providing a flexible alternative to building a fixed recharging infrastructure. Leveraging this flexibility requires coordinated planning of the vehicles. Recently, energy-aware UAV-UGV planning problems have gained significant attention. In [yu2018algorithms], UAV landing locations on stationary or mobile UGVs are determined via a generalized traveling salesperson problem (GTSP) formulation. In [cai2025energyawareroutingalgorithmmobile], energy-constrained UAV-UGV routing is addressed with a TSP-guided Monte Carlo Tree Search. In [ropero2019terra], UAV-UGV trajectories are computed separately via a genetic algorithm and modified A*, with rendezvous locations determined through Voronoi tessellations. In [maini2019coverage], a two-stage heuristic leverages a road-network-constrained UGV as a refueling station for energy-aware UAV-UGV route planning. In [yu2021rl], a multi-agent deep reinforcement learning approach guides heterogeneous UAV-UGV teams based on environmental conditions. However, most of these approaches assume complete knowledge of the environment, including obstacle-free environments and known travel times. In practice, disturbances such as wind, obstacles, or navigation errors can render a plan infeasible. In [thelasingha2024iterative], an iterative planning framework is proposed to improve solutions online as new information becomes available. In [shi2022risk], a chance-constrained Markov Decision Process formulation is used to handle stochastic UAV energy consumption with a probabilistic rendezvous policy. In [albarakati2021multiobjective], multiobjective optimization is applied to the similar problem of Autonomous Underwater Vehicle risk-aware path planning under stochastic water currents. In [Lin2022, er2025rspectrobustscalableplanner], scalable robust planning algorithms are proposed for persistent surveillance and aerial monitoring with energy-constrained UAV-UGV teams. In this work, unlike prior approaches that rely on deterministic margins (e.g., [er2025rspectrobustscalableplanner]), we instead optimize under a probabilistic safety requirement encoded as a joint chance constraint. This coupling fundamentally changes the problem structure and requires an approach to ensure global probabilistic safety guarantees. Our contributions are: 1. A Mixed-Integer Program formulation for stochastic UAV–UGV energy-aware planning with a joint chance constraint encoding a global safety requirement (3). 2. An integrated offline-online polynomial-time planning framework, PRO-SPECT (Alg.1), that computes risk-bounded offline solutions, and adapts to run-time disturbances online via a receding horizon approach. 3. Formal guarantees on feasibility and worst-case time complexity of PRO-SPECT (Thm.1). 4. Validation via numerical comparisons against well-known optimization methods (Branch and Cut, Simulated Annealing), and related works [ropero2019terra, er2025rspectrobustscalableplanner]; and ROS simulations with wind induced uncertainty. I Problem Formulation We consider an aerial monitoring mission in a stochastic environment, where a UAV is supported by a UGV (mobile charging station) that transports the UAV through take-off/landing sites. Let ℝR and ℝ≥0R_≥ 0 denote the real numbers and non-negative real numbers. Let the environment be: :=(x,y,z)∈ℝ3| 0≤x≤x¯, 0≤y≤y¯, 0≤z≤z¯,Q:=\(x,y,z) ^3|\,\,0≤x≤ x,\,0≤y≤ y,\,0≤z≤ z\, (1) containing a feasible space f⊆Q_f Q. Let faQ^a_f and fgQ^g_f denote the feasible points on air and ground, i.e., fa=f∖fgQ^a_f=Q_f Q^g_f, ga=f∖agQ^a_g=Q_f Q^g_a.111Both fQ_f and fgQ_f^g are connected, i.e., a feasible path exists between any pair of points within these sets. Let ℓ:f×f→ℝ≥0 :Q_f×Q_f→R_≥ 0 be a distance function (shortest path length) between any two points in fQ_f. The mission goal is for the UAV-UGV team to visit a set of n aerial points, UAV=x1,…,xn⊂faP_UAV=\x_1,…,x_n\⊂Q_f^a. The team starts from initial position x0∈fgx_0∈Q_f^g, and must reach the final position xf∈fgx_f∈Q_f^g while ensuring every point in UAVP_UAV is visited without violation of the UAV’s energy constraint, while minimizing mission time. The UAV cannot continuously fly longer than a specific duration τ¯a τ_a due to its limited energy.222For UAVs with near constant power draw, energy depletion can be approximated by flight time. To this end, we consider an approach where the UGV carries the UAV through a sequence of points, which are release and collect points. The UAV takes off at a release point, samples a subset of UAVP_UAV, and lands on the UGV at a collect point to be charged and transferred to the next release point. With at most n+2n+2 points per tour333Clearly, a solution also cannot be optimal unless the UAV visits at least one point from UAVP_UAV in every tour. (release, collect, and n aerial points), we encode the mission plan as: 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 each Xi,j∈fX_i,j∈Q_f denotes an air point if j∈2,…,n+1j∈\2,…,n+1\, a release point if j=1j=1, and a collect point if j=n+2j=n+2. Each row of X (denoted as XiX_i) encodes a tour that involves the UAV traveling through the sequence of waypoints in that row via shortest paths and meeting with the UGV at the collect point. Thus, any plan with less than n tours can be encoded with the remaining rows as Xi,1=Xi,2=…=Xi,n+2X_i,1=X_i,2=…=X_i,n+2 i.e., zero length, trivial tours. After each tour is executed, the UGV transfers the UAV from Xi,n+2X_i,n+2 (collect point) to Xi+1,1X_i+1,1 (next release point), or xfx_f if i=ni=n, while recharging the UAV. For the team, the total time to execute the plan X is τ(X) τ(X) =τg(x0,X1,1)+τg(Xn,n+2,xf) = _g(x_0,X_1,1)+ _g(X_n,n+2,x_f) (2) +∑i=1nmax(τa(Xi),τg(Xi,1,Xi,n+2)) + _i=1^n ( _a(X_i), _g(X_i,1,X_i,n+2)) +∑i=1n−1max(τg(Xi,n+2,Xi+1,1),τc(Xi)), + _i=1^n-1 ( _g(X_i,n+2,X_i+1,1), _c(X_i)), where τa _a and τg _g denote UAV tour time and UGV travel time respectively, and τa=τg=0 _a= _g=0 for zero-length paths. Here, τa(Xi) _a(X_i) is the UAV time for tour i from release point Xi,1X_i,1 through points Xi,2,…,Xi,n+1X_i,2,…,X_i,n+1 to collect point Xi,n+2X_i,n+2. The terms τg(x0,X1,1) _g(x_0,X_1,1) and τg(Xn,n+2,xf) _g(X_n,n+2,x_f) are the UGV times from start to first release and from final collect to end, respectively. The term τg(Xi,n+2,Xi+1,1) _g(X_i,n+2,X_i+1,1) is the UGV travel time between consecutive tours. The recharge time after tour i is τc(Xi)≥0 _c(X_i)≥0, ensuring the UAV begins each tour fully charged.444Battery swapping can be modeled by setting τc(Xi) _c(X_i) to a small constant. Different from earlier works such as [er2025rspectrobustscalableplanner] that consider deterministic travel times (energy consumption), we model stochastic travel times and impose probabilistic guarantees on safety, i.e., the UAV never has to fly longer than τ¯a τ_a. More specifically, we consider the problem of minimizing the expected time to complete the mission while achieving a desired bound on the probability of failure as in (3c) where prp_r is a user-specified acceptable risk level, i.e., minX _X [τ(X)], [τ(X)], (3a) s.t. ∀xk∈UAV,∃Xi,j=xk, ∀ x_k _UAV, ∃ X_i,j=x_k, (3b) P(max[τa(Xi),τg(Xi,1,Xi,n+2)]≤τ¯a∀i)≥1−pr, P ( [ _a(X_i), _g(X_i,1,X_i,n+2) ]≤ τ_a\;∀ i )≥ 1-p_r, (3c) Xi,1,Xi,n+2∈fg,∀i, X_i,1,X_i,n+2 _f^g, ∀ i, (3d) Xi,j∈UAV∪Xi,j−1,∀j∈2,…,n+1, X_i,j _UAV∪\X_i,j-1\, ∀ j∈\2,…,n+1\, (3e) where (3a) minimizes expected mission completion time, (3b) ensures all points in UAVP_UAV are visited, (3c) bounds the probability of failure across all tours by user-specified prp_r,555If no feasible solution exists when each air point comprises its own tour, then τ¯a τ_a is insufficient to reach some air points, and we assume the problem admits no feasible solution. (3d) constrains release/collect points to the feasible ground, and (3e) allows only release/collect points or their immediate repetitions to deviate from UAVP_UAV. I Proposed Solution I-A Environmental Model To model uncertainty, we define mean and variance functions to estimate travel times. We consider only the first two cumulants, as higher-order moments are typically unavailable or unreliable in practical environmental models. Let ta(u,v)∼Ta(u,v)t_a(u,v) T_a(u,v) denote the UAV travel time between two points, analogous to τg _g. We define the UAV environmental model as: Mθ,a(u,v)≡[ta(u,v)],Vθ,a(u,v)≡Var[ta(u,v)],Cθ,a(u,v,w,x)≡Cov[ta(u,v),ta(w,x)], splitM_θ,a(u,v) [t_a(u,v)],& V_θ,a(u,v) [t_a(u,v)],\\ C_θ,a(u,v,w,x)≡&~Cov[t_a(u,v),t_a(w,x)], split (4) where Mθ,a(u,v)M_θ,a(u,v) and Vθ,a(u,v)V_θ,a(u,v) denote the expected travel time and its variance for the UAV between points u and v, respectively, and Cθ,a(u,v,w,x)C_θ,a(u,v,w,x) denotes the travel time covariance between edges (u,v)(u,v) and (w,x)(w,x). For the UGV: Mθ,g(u,v)≡[τg(u,v)],Vθ,g(u,v)≡Var[τg(u,v)],M_θ,g(u,v) [ _g(u,v)], V_θ,g(u,v) [ _g(u,v)], (5) where Mθ,g(u,v)M_θ,g(u,v) and Vθ,g(u,v)V_θ,g(u,v) denote the expected travel time and its variance for the UGV between points u and v, respectively. The parameter vector θ captures environmental variables such as wind, obstacles, and navigation uncertainty. Note that the approach is otherwise agnostic to the underlying noise model and user preferences. We assume Mθ,∗M_θ,*, Vθ,∗V_θ,*, and Cθ,aC_θ,a depend only on endpoints, allowing the functions to be evaluated and cached per edge. This enables the total tour statistics to decompose as sums over edges. For tour i with waypoints Xi,1,…,Xi,n+2X_i,1,…,X_i,n+2: μ^a,i=∑j=1n+1Mθ,a(Xi,j,Xi,j+1),σ^a,i2=∑j=1n+1Vθ,a(Xi,j,Xi,j+1)+∑j=1n+1∑k≠jCθ,a(Xi,j,Xi,j+1,Xi,k,Xi,k+1),μ^g,i=Mθ,g(Xi,1,Xi,n+2),σ^g,i2=Vθ,g(Xi,1,Xi,n+2). split μ_a,i&= _j=1^n+1M_θ,a(X_i,j,X_i,j+1),\\ σ^2_a,i&= _j=1^n+1V_θ,a(X_i,j,X_i,j+1)+ _j=1^n+1 _k≠ jC_θ,a(X_i,j,X_i,j+1,X_i,k,X_i,k+1),\\ μ_g,i&=M_θ,g(X_i,1,X_i,n+2), σ^2_g,i=V_θ,g(X_i,1,X_i,n+2). split (6) I-B Probabilistic Constraint Evaluation Given mean and variance estimates for UAV or UGV (μ^,σ^)( μ, σ) from (6), we construct a Gaussian surrogate for the distribution of each tour travel time. Note that we do not assume the true distribution is Gaussian. As we will discuss, these Gaussian surrogates yield a tractable analysis that conservatively over-approximates the underlying risk of violating the flight time constraint. For any such Gaussian surrogate, (μ^,σ^)N( μ, σ), the cumulative distribution function (CDF) is: Φ(x−μ^σ^)=P(x≥t|t∼(μ^,σ^))=12(1+erf(x−μ^σ^2)), ( x- μ σ )=P(x≥ t|t ( μ, σ))= 12 (1+erf ( x- μ σ 2 ) ), (7) where erf is the error function. Using the Gaussian CDF, the probability of tour i not exceeding the UAV’s flight time constraint τ¯a τ_a is P(τ¯a≥t|t∼(μ^∗,i,σ^∗,i))P( τ_a≥ t|t ( μ_*,i, σ_*,i)) for both agents: ps,a(Xi) p_s,a(X_i) =Φ(τ¯a−μ^a,iσ^a,i2), = ( τ_a- μ_a,i σ^2_a,i ), (8) ps,g(Xi,1,Xi,n+2) p_s,g(X_i,1,X_i,n+2) =Φ(τ¯a−μ^g,iσ^g,i2). = ( τ_a- μ_g,i σ^2_g,i ). (9) Unless the acceptable risk prp_r in (3c) is high and the number of tours m is small, each tour requires a high success probability (ps,a,ps,gp_s,a,p_s,g close to 1), as the product across all tours must remain above 1−pr1-p_r. Since the Gaussian surrogate has heavier tails than typical physical processes [nemirovski2007convex], it yields lower cumulative probabilities P(τ¯a≥t)P( τ_a≥t) for large t, conservatively underestimating ps,a,ps,gp_s,a,p_s,g under the true distribution. Accordingly, satisfaction of the risk bound (3c) under the Gaussian surrogate implies satisfaction under any thinner-tailed distribution, except in the case of planning only a few tours with a high risk tolerance. I-C Tour Construction The key challenge of (3) is the constraint (3c). Unlike [er2025rspectrobustscalableplanner], where constraints could be applied per tour, all tours are now coupled through a joint probability bound. As a result, tour boundaries and release/collect points must be selected jointly across the mission, rather than per tour: 1−pr<ps=∏i=1mps,i,1-p_r<p_s= _i=1^mp_s,i, (10) where m is the number of tours. To make the joint optimization more tractable, we decouple the problem by fixing the visit order. To this end, we solve a TSP on UAVP_UAV using edge costs from Mθ,aM_θ,a to obtain an ordered sequence S.666If Mθ,∗(u,v)=Mθ,∗(v,u)M_θ,*(u,v)=M_θ,*(v,u) and Vθ,∗(u,v)=Vθ,∗(v,u)V_θ,*(u,v)=V_θ,*(v,u) the environmental model is symmetric. If the environmental model is not symmetric, we consider an asymmetric TSP (ATSP) without loss of generality. Subsequent optimization focuses on selecting tour boundaries and release/collect points. We represent tour partitioning by a set of cut indices K=k1,…,km−1K=\k_1,…,k_m-1\, partitioning S into tours: i=1:ki−1if i=1ki−1:nif i=mki−1:ki−1otherwiseT_i= casesS_1:k_i-1&if i=1\\ S_k_i-1:n&if i=m\\ S_k_i-1:k_i-1&otherwise cases (11) Each tour (row) includes a release point rir_i (visited first), a collect point cic_i (visited last), and their ground projections, with cic_i repeated such that |Xi,:|=n+2|X_i,:|=n+2: Xi,:=(π(ri),ri,i∖ri,ci,ci×(n−|i|+1),π(ci)),X_i,:=(π(r_i),r_i,T_i \r_i,c_i\,c_i^×(n-|T_i|+1),π(c_i)), (12) where π:Qfa→Qfgπ:Q_f^a→ Q_f^g denotes a projection function that maps an aerial point to a feasible ground point. Specifically, π(u)π(u) returns the closest feasible ground point to u, defined as π(u)=argminv∈Qfgℓ(u,v).π(u)= *argmin_v∈ Q_f^g\, (u,v). Assuming independence, tour success probability combines UAV and UGV success: ps,i=ps,a[(π(ri),ri,i∖ri,ci,ci,π(ci))]⋅ps,g[(π(ri),π(ci))].p_s,i=p_s,a[(π(r_i),r_i,T_i \r_i,c_i\,c_i,π(c_i))]· p_s,g[(π(r_i),π(c_i))]. (13) We then pose the tour construction problem by maximizing the product of probabilities, equivalent to maximizing the sum of log-probabilities since ps,i∈[0,1]p_s,i∈[0,1]: maxK,R,C∑i=1mlog(ps,i), _K,R,C _i=1^m (p_s,i), (14) where R=r1,…,rmR=\r_1,…,r_m\ and C=c1,…,cmC=\c_1,…,c_m\ are the sets of release and collect points, respectively. Then, (14) is solved for the minimum m satisfying (10). I-D Dynamic Program We solve (14) with dynamic programming. We define Dj,mD_j,m as the maximum log-probability achievable by partitioning S1:jS_1:j into m tours. The function f(a,b,r,c)f(a,b,r,c) returns the log-probability contribution of a single tour segment a:bS_a:b with release index r and collect index c: f(a,b,r,c)=log(ps,a[(π(r),r,(a:b)∖r,c,c,π(c))])+log(ps,g[(π(r),π(c))]). splitf(a,b,r,c)&= (p_s,a[(π(S_r),S_r,S_(a:b) \r,c\,S_c,π(S_c))])\\ & + (p_s,g[(π(S_r),π(S_c))]). split (15) Using the definition of Dj,mD_j,m and the segment cost function f, the recurrence relation is: Dj,m=maxrm,cm∈1:jf(1,j,rm,cm)if m=1maxkm−1∈m+1:j−1rm,cm∈km−1:jDkm−1−1,m−1+f(km−1,j,rm,cm)if m>1D_j,m= \ array[]clc _r_m,c_m∈\1:j\&f(1,j,r_m,c_m)&if m=1\\[10.0pt] _ subarrayck_m-1∈\m+1:j-1\\\ r_m,c_m∈\k_m-1:j\ subarray& split&D_k_m-1-1,m-1\\ &+f(k_m-1,j,r_m,c_m) split&if m>1 array . (16) We sweep m from 1 to n until Dn,m≥log(1−pr)D_n,m≥ (1-p_r), storing optimal km−1,rm,cmk_m-1,r_m,c_m for each (j,m)(j,m) to reconstruct K,R,CK,R,C. When the given travel-time model is symmetric, i.e., f(a,b,r,c)=f(a,b,c,r)f(a,b,r,c)=f(a,b,c,r), we choose r<cr<c to ensure the release point precedes the collect point in S, respecting the TSP ordering and likely minimizing UGV inter-tour time. I-E Offline Planning Offline planning considers problem (3) in full. Some algorithm inputs include tildes as they may differ during online planning. For offline planning, inputs follow as: UAV points ~UAV=UAV P_UAV=P_UAV, initial positions x~0,a=x~0,g=x0 x_0,a= x_0,g=x_0, flight time τ~0=0 τ_0=0, final position x~f=xf x_f=x_f, and allowable risk p~r=pr p_r=p_r. Output mission plan X~ X is n×n+2n× n+2 as required. I-F Online Re-planning Offline planning assumes agents start co-located with full battery. Online re-planning relaxes these assumptions with a receding horizon approach, re-solving a subset of the offline problem at tour boundaries with an adjusted risk budget to preserve the global guarantee (10). I-F1 Re-planning Between Tours When the UAV and UGV are together before tour i, we have current UAV position x~0,a x_0,a and UGV position x~0,g x_0,g satisfying x~0,a=x~0,g x_0,a= x_0,g, but the UAV can have a residual charge deficit τ~0≥0 τ_0≥0 from the previous tour, modifying the recharge time before the next tour. To re-plan the next m~ m tours: i) Select planning horizon: m~∈0:m−i m∈\0:m-i\ i) Solve with modified inputs: • ~UAV=⋃k=i+m~Xk,2,…,Xk,n+1 P_UAV= _k=i^i+ m\X_k,2,…,X_k,n+1\ • x~0,a=x~0,g=Xi,2 x_0,a= x_0,g=X_i,2, x~f=π(Xi+m~,n+1) x_f=π(X_i+ m,n+1) • p~r=1−exp(log(1−pr)−∑j=i+m~+1mlogps,j) p_r=1- ( (1-p_r)- _j=i+ m+1^m p_s,j ) i) Update plan: Xi:i+m~,:=X~X_i:i+ m,:= X The risk budget p~r p_r is derived from (10) with the success probabilities of tours beyond the horizon, ensuring the bound is preserved regardless of when re-planning occurs. I-F2 Re-planning During a Tour Re-planning can occur at any time during execution. When the UAV and UGV are not together during tour i, we have current UAV position x~0,a≠x~0,g x_0,a≠ x_0,g with elapsed flight time τ~0≥0 τ_0≥0, reducing the remaining energy budget for the current tour. m~ m, p~r p_r, and x~f x_f are the same as above. If j~ j is the next index in the tour, we have ~UAV=Xk,j~,…,Xk,n+1∪⋃k=i+1i+m~Xk,2,…,Xk,n+1 P_UAV=\X_k, j,…,X_k,n+1\∪ _k=i+1^i+ m\X_k,2,…,X_k,n+1\. We modify the DP to handle the partial tour by replacing f with f′f , where the release point has already passed: f′(1,b,⋅,c)=log(ps,a[(x~0,a,(1:b)∖c,c,π(c))])+log(ps,g[(x~0,g,π(c))]), splitf (1,b,·,c)&= (p_s,a[( x_0,a,S_(1:b) \c\,S_c,π(S_c))])\\ & + (p_s,g[( x_0,g,π(S_c))]), split (17) and update success probabilities to account for elapsed time: ps,a=Φ(τ¯a−τ~0−μ^a,1σ^a,12),ps,g=Φ(τ¯a−τ~0−μ^g,1σ^g,12),p_s,a= ( τ_a- τ_0- μ_a,1 σ^2_a,1 ), p_s,g= ( τ_a- τ_0- μ_g,1 σ^2_g,1 ), (18) where (μ^∗,1,σ^∗,12)( μ_*,1, σ^2_*,1) are summed only over remaining points. I-G Proposed Algorithm We propose PRO-SPECT (Alg. 1), which returns a feasible solution to (3) with a polynomial-time worst-case complexity. A visualization of the algorithm is provided in Fig.1. Input : ~UAV P_UAV (Set of n~ n points to visit), n (Size of full UAVP_UAV), fgQ_f^g (Feasible Ground), faQ_f^a (Feasible Air), x~0,a x_0,a (UAV start position), τ~0 τ_0 (UAV initial flight time), x~0,g x_0,g (UGV start position), x~f x_f (Final position), τ¯a τ_a (Maximum flight time), p~r p_r (User-specified risk parameter), Mθ,a,Vθ,aM_θ,a,V_θ,a, Cθ,aC_θ,a, Mθ,g,Vθ,gM_θ,g,V_θ,g (UAV and UGV travel time functions) Output : X~ X (Mission Plan) Step 1: Finding an approximate solution ~ S to TSP on ~UAV P_UAV Use an approximate TSP solver [christofides2022worst]777We can use any other TSP solver in these steps. However, this might change the worst-case time complexity of Alg. 1.on ~UAV P_UAV to find ~ S such that the edge cost is calculated with Mθ,aM_θ,a and ~1=argminx∈UAVMθ,a(x~0,a,x),~n~=argminx∈UAVMθ,a(x,x~f) S_1= x _UAV *argmin\,M_θ,a( x_0,a,x), S_ n= x _UAV *argmin\,M_θ,a(x, x_f) Step 2: Creating feasible UAV tours from ~ S Initialize: X~,D,K,R,C←∅ X,D,K,R,C← , ValidPlanFlag ← False n~←|~UAV| n←| P_UAV| for m←1m← 1 to n~ n do for j←mj← m to n~ n do if x~0,a≠x~0,g x_0,a≠ x_0,g and m=1m=1 then c^←argmaxc∈1:jf′(1,j,⋅,c) c← c∈\1:j\ *argmax f (1,j,·,c) Dj,m←f′(1,j,⋅,c^)D_j,m← f (1,j,·, c) Kj,m←−1K_j,m←-1, Rj,m←−1R_j,m←-1, Cj,m←c^C_j,m← c else if m=1m=1 then r^,c^←argmaxr,c∈1:jf(1,j,r,c) r, c← r,c∈\1:j\ *argmax f(1,j,r,c) Dj,m←f(1,j,r^,c^)D_j,m← f(1,j, r, c) Kj,m←−1K_j,m←-1, Rj,m←r^R_j,m← r, Cj,m←c^C_j,m← c else k^,r^,c^←argmaxk∈m+1:j−1r,c∈1:jDk−1,m−1+f(k,j,r,c) k, r, c← subarrayck∈\m+1:j-1\\\ r,c∈\1:j\ subarray *argmax D_k-1,m-1+f(k,j,r,c) Dj,m←Dk^−1,m−1+f(k^,j,r^,c^)D_j,m← D_ k-1,m-1+f( k,j, r, c) Kj,m←k^K_j,m← k, Rj,m←r^R_j,m← r, Cj,m←c^C_j,m← c if Dn~,m≥log(1−pr)D_ n,m≥ (1-p_r) then ValidPlanFlag ← True break if not ValidPlanFlag then return ∅ n^←n~ n← n, m^←m m← m while m^>1 m>1 do km^←Kn^,m^k_ m← K_ n, m, rm^←Rn^,m^r_ m← R_ n, m, cm^←Cn^,m^c_ m← C_ n, m X~m^,:←(π(~rm^),~rm^,~(km^:n^)∖rm^,cm^, X_ m,:←(\,π( S_r_ m),\, S_r_ m,\, S_(k_ m: n) \r_ m,c_ m\, ~cm^×(n−n^+km^−1),π(~cm^)) S_c_ m^×(n- n+k_ m-1),\,π( S_c_ m)\,) n^←km−1 n← k_m-1, m^←m^−1 m← m-1 r1←Rn^,1r_1← R_ n,1, c1←Cn^,1c_1← C_ n,1 if x0,a≠xo,gx_0,a≠ x_o,g then X~1,:←(x0,g,x0,a,~(1:n^)∖c1,~c1×(n−n^),π(~c1)) X_1,:←(\,x_0,g,x_0,a,\, S_(1: n) \c_1\,\, S_c_1^×(n- n),\,π( S_c_1)\,) else X~1,:←(π(~r1),~r1,~(1:n^)∖r1,c1,~c1×(n−n^),π(~c1)) X_1,:←(\,π( S_r_1),\, S_r_1,\, S_(1: n) \r_1,c_1\,\, S_c_1^×(n- n),\,π( S_c_1)\,) X~m+1:n,:←x~f X_m+1:n,:← x_f return X~ X Algorithm 1 Probabilistically Safe UAV-UGV Planning (PRO-SPECT) (a) UAVP_UAV (b) Step 1 (c) Step 2 Figure 1: Offline plan generated by PRO-SPECT : (a) UAVP_UAV; (b) TSP solution for S with x0x_0 (lower left) and xfx_f (upper right); (c) tour construction via dynamic programming with UGV path (gray) and UAV tours (blue). In Step 1, an approximate TSP is solved on ~UAV P_UAV using Mθ,aM_θ,a as edge costs, producing the sequence ~ S (lines 1-3). Here, ~1 S_1 is set to the point closest to the UAV start position, and ~n~ S_ n to the point closest to the final position. In Step 2, the tours are constructed. First, X~ X (plan), K (cut indices storing the optimal km−1k_m-1 for each segment), R (release indices storing the optimal release point r for each segment), C (collect indices storing the optimal collect point c for each segment), and D (DP table storing the maximum log-probability achievable for each (j,m)(j,m)) are initiated (line 5). Then, the number of tours m is swept from 11 to n~ n (line 7), and for each m, the endpoint index j is swept from m to n~ n (line 8). Three cases are distinguished: (i) if the team is separated and m=1m=1 (lines 9-12), then the partial first tour is handled using f′f , optimizing only the collect point; (i) if m=1m=1 and the team is co-located (lines 13-16), then both release and collect points are optimized using f; (i) if m>1m>1 (lines 17-20), then the cut, release, and collect are jointly optimized for the last segment and combined with the best prior solution. The sweep terminates once Dn~,mD_ n,m (the maximum log-probability achievable by partitioning all n~ n points into m tours) exceeds log(1−pr) (1-p_r) (lines 21-23). The backtracking phase (lines 26-36) traces through the stored tables to create the tours. Each tour is reconstructed by retrieving the optimal cut, release, and collect indices and assembling the corresponding waypoint sequence (lines 28-30). The notation ~c×(n−n^) S_c^×(n- n) denotes the repetition of point ~c S_c exactly (n−n^)(n- n) times, padding the remaining points in the row. The first tour is then constructed from the current robot positions if they are separated (line 33), or via standard projected release otherwise (line 35), with padding applied analogously in both cases. Finally, the rows after the last tour are set to x~f x_f (line 36), and X~ X is returned. We provide formal guarantees on the computational complexity of Alg.1 and the feasibility of the returned solution. Alg.1 returns a feasible plan to visit each point in ~UAV⊆UAV P_UAV P_UAV, with a worst case time complexity that is polynomial with the number of points in ~UAV P_UAV. When ~UAV=UAV P_UAV=P_UAV, the algorithm exactly solves (3) and n~=n=|UAV| n=n=|P_UAV|. Otherwise it solves a subset of the problem. Theorem 1. Algorithm 1 returns a feasible solution to (3), with worst-case time complexity O(n~5)O( n^5). Proof. Feasibility: Step 1 solves a TSP, ensuring all points in ~UAV P_UAV appear in ~ S, satisfying (3b). Step 2 terminates only when Dn~,m≥log(1−pr)D_ n,m≥ (1-p_r), satisfying (3c). Release and collect points X~i,1 X_i,1 and X~i,n+2 X_i,n+2 are from feasible ground via π, satisfying (3d). All other elements of X~1−m,: X_1-m,: are points drawn from ~UAV P_UAV or repeat previous air points, and all elements of X~m+1,: X_m+1,: are x~f x_f, satisfying (3e). If no feasible partition exists for m≤n~m≤ n, the algorithm returns ∅ . Therefore, Alg. 1 returns a feasible solution to (3), if one exists. Complexity: Step 1 solves a TSP on n~ n points, which runs in O(n~3)O( n^3) via Christofides’ algorithm [christofides2022worst]. Step 2 builds Dn~,mD_ n,m by sweeping m from 11 to minm_min (outer loop, min≤n~m_min≤ n). For each m, the inner loop iterates over j∈m:n~j∈\m: n\ with ≤n~≤ n iterations. The maximization over (km−1,rm,cm)(k_m-1,r_m,c_m) requires ≤n~≤ n iterations for km−1k_m-1 and worst-case n~ n iterations each for rm,cmr_m,c_m. The total is then O(n~4min)O( n^4m_min). Since worst-case for minm_min is min=n~m_min= n, overall complexity becomes O(n~5)O( n^5). The projection function π runs in O(n~b)O( nb) total for n~ n points and b known convex obstacles (each with a bounded number of faces), as each projection reduces to a convex quadratic program per face [QP]; which is dominated by Step 2 assuming b is bounded. Therefore, the worst-case time complexity of Alg.1 is O(n~5)O( n^5). ∎ IV Numerical Evaluations We compare the scalability and performance of Alg.1 to four different algorithms: 1) Branch and Cut [mitchell2002branch], 2) a metaheuristic, Simulated Annealing, and 3) two heuristics from literature [ropero2019terra, er2025rspectrobustscalableplanner]. Python 3.9 running on an Intel Ultra 7 155h (22 processors) with 32GB RAM was used. As environmental models require bounded distributions, the Uniform distribution (U) is used. Travel time along an edge of length l is modeled as t∼l⋅(μ−3σ,μ+3σ)t l·U (μ- 3σ,μ+ 3σ ) where the constant 3 3 scales for variance. Edge times are independent. The planning model follows: Mθ=l⋅μM_θ=l·μ, Vθ=l2⋅σ2V_θ=l^2·σ^2, and Cθ=0C_θ=0. The UAV model uses μ=0.1smμ=0.1 sm and σ=0.01smσ=0.01 sm, and the UGV model uses μ=0.4smμ=0.4 sm and σ=0.04smσ=0.04 sm. Recharging is modeled as: τc(Xi)=γ⋅max(τa(Xi),τg(Xi,1,Xi,n+2)),γ≥0, _c(X_i)=γ· ( _a(X_i), _g(X_i,1,X_i,n+2)),γ≥ 0, (19) where γ is a recharge ratio. For n∈25,50,75,100n∈\25,50,75,100\ and pr=0.1p_r=0.1, 10 random UAVP_UAV were created inside the environment defined in (1) with x¯=y¯=4000m x= y=4000m, and fixed z-coordinate equal to 100m100m. Since UAVs’ horizontal speeds are greater than their vertical speeds [guo2020precision], the UAV vertical travel time is scaled by a factor of 5, i.e., tv∼z⋅5⋅(μ−3σ,μ+3σ)t_v z·5·U (μ- 3σ,μ+ 3σ ). For each value of n, computation time and mission time (τ(X)τ(X)) were reported with mean ± standard deviation over the 10 realizations. Unless otherwise specified, all results are from offline planning only. Remaining parameters are in Table I. TABLE I: Mission Parameters for Numerical Evaluations Parameter Value Parameter Value x0x_0 (Initial point) (0,0,0)(0,0,0) xfx_f (Final point) (4000,4000,0)(4000,4000,0) τ¯a τ_a (Max flight time) 600600 s γ (Recharge ratio) 11 IV-A Scalability Table I demonstrates the scalability of PRO-SPECT for different n. Step 2 of PRO-SPECT is well-suited to parallelization, as D:,mD_:,m can be solved independently across m. Results are reported for both serial and parallel implementations. Computation time increases with n as expected from the worst-case O(n5)O(n^5) complexity (see Theorem 1). Empirical fits for serial and parallel implementations match O(n4.25)O(n^4.25) and O(n3.05)O(n^3.05), respectively. The results demonstrate PRO-SPECT’s ability to handle a large range of problem sizes. TABLE I: PRO-SPECT Comp. Time and Mission Time, τ(X)τ(X), Varying n n Comp. Time (s) Parallel Comp. Time (s) () τ(X) (s) 25 8.1±0.218.1± 0.21 4.7±1.24.7± 1.2 5400±6705400± 670 50 120±1.1120± 1.1 25±6.525± 6.5 6500±5706500± 570 75 850±1.6850± 1.6 110±31110± 31 7600±5607600± 560 100 2800±7.52800± 7.5 330±14330± 14 8200±5108200± 510 IV-B Validation of Probabilistic Constraints Table I reports the mean empirical failure rate (p^r p_r) of PRO-SPECT for different n and prp_r. For each (n,pr)(n,p_r) combination, a plan is generated for each of the 10 random UAVP_UAV instances and executed 1000 times under independent stochastic travel time realizations to estimate mean p^r p_r. Then, p^r p_r is reported across the 10 instances. In all cases, p^r p_r remains below the user-specified prp_r, validating (3c). TABLE I: PRO-SPECT Mean Empirical Failure Rate, p^r p_r, Varying n and prp_r n p_r (user-specified) 0.01 0.10 0.20 0.50 25 0.00010.0001 0.0180.018 0.0180.018 0.100.10 50 0.00070.0007 0.0110.011 0.0110.011 0.0330.033 75 0.00050.0005 0.0150.015 0.0240.024 0.110.11 100 0.00010.0001 0.00610.0061 0.00610.0061 0.110.11 IV-C Online Re-planning Table IV evaluates the online re-planning component of PRO-SPECT against the offline-only plan in terms of empirical failure rate p^r p_r and expected mission time τ(X)τ(X). For each n∈20,30,40,50n∈\20,30,40,50\, a plan is generated for each of the 10 random UAVP_UAV instances and executed 25 times under independent stochastic travel time realizations. The mean p^r p_r is then reported across the 10 instances. Re-planning is triggered after each air point, with earlier interventions yielding larger reductions in p^r p_r. The re-planning horizon m~ m controls the trade-off between solution quality and computation time; all runs use m~=2 m=2. Runs with online planning rarely encounter failure due to the ability to end a tour before serious risk. This has a mixed effect on mission time, as the planner can also save time when available. Overall the online planner provides flexibility and maintains p^r<pr p_r<p_r. TABLE IV: PRO-SPECT Offline vs. Online: Empirical Failure Rate, p^r p_r, and Empirical Successful Mission Time, τ^(X) τ(X), for pr=0.1p_r=0.1 and Varied n n Offline Online p_r ^() τ(X) (s) p_r ^() τ(X) (s) 20 0.0120.012 5300±6505300± 650 0 ± 5100± 510 30 0.0200.020 5800±7605800± 760 0 5800±10005800± 1000 40 0.00580.0058 ± 5800± 420 0.004 0.004 6200±5606200± 560 50 0.0110.011 6500±5706500± 570 0 6500±4506500± 450 IV-D Comparison to Branch and Cut Table V compares PRO-SPECT against Branch and Cut, which returns the global optimum for (3). Due to the NP-hardness of (3), Branch and Cut computation time grows exponentially with n, limiting its applicability to very small n. In contrast, PRO-SPECT achieves competitive mission times at a fraction of the computation cost. TABLE V: Branch and Cut vs. PRO-SPECT: Computation Time and Mission Time, τ(X)τ(X), Varying n n Branch and Cut PRO-SPECT Comp. Time (s) () (s) τ(X) (s) Comp. Time (s) () (s) τ(X) (s) 2 0.43±0.360.43± 0.36 ± 2400± 140 0.0051±0.0007 0.0051± 0.0007 2900±6402900± 640 3 3.0±1.33.0± 1.3 ± 2800± 510 0.0075±0.0016 0.0075± 0.0016 3100±6603100± 660 4 18±1418± 14 ± 3500± 900 0.015±0.0049 0.015± 0.0049 3700±9803700± 980 IV-E Comparison to Simulated Annealing Table VI compares PRO-SPECT against Simulated Annealing (SA) for n=10n=10 across 10 random UAVP_UAV instances. A logarithmic cooling schedule was used for SA [nourani1998sa] with Tmin=0.01T_min=0.01 and Tmax∈500,1000,1500T_max∈\500,1000,1500\. Each instance was run 3 times due to the stochastic nature of SA. While increasing the number of steps increases computation cost, solution quality does not improve consistently, suggesting diminishing returns. PRO-SPECT achieves significantly better computation and mission times: 0.13±0.050.13± 0.05 s and τ(X)=4400±1300τ(X)=4400± 1300 s respectively. TABLE VI: Simulated Annealing Average Computation Time and Mission Time, τ(X)τ(X), Varying TmaxT_max and Number of Steps max T_max Comp. Time (s) () τ(X) (s) Steps Steps 50k 100k 150k 50k 100k 150k 500 40±1.540± 1.5 40±3.740± 3.7 41±3.541± 3.5 8700±12008700± 1200 9100±13009100± 1300 8700±11008700± 1100 1000 80±1480± 14 80±1180± 11 79±8.279± 8.2 7900±8307900± 830 7800±13007800± 1300 8300±11008300± 1100 1500 120±7.0120± 7.0 110±9.8110± 9.8 120±8.4120± 8.4 7700±10007700± 1000 7700±11007700± 1100 8000±8208000± 820 IV-F Comparison to State-of-the-Art PRO-SPECT is compared with two methods that address similar energy-aware UAV-UGV planning problems: 1) TERRA [ropero2019terra], and 2) RSPECT [er2025rspectrobustscalableplanner]. Since the methods are deterministic, their planning budgets are scaled conservatively i.e., reducing τ¯a τ_a during planning, so that the deterministic plan accounts for likely travel time deviations. Plans are executed under the full stochastic travel times. All methods use parameters from Table I, unless otherwise specified. TSPs and GTSPs are solved using [christofides2022worst] and [smith2016GLNS], respectively. IV-F1 Comparison to TERRA TERRA [ropero2019terra] is deterministic and assumes a known environment; its planning UAV range is scaled by μ+3σ μ+ 3σ (i.e., conservative planning bounds) to provide a more fair comparison under stochastic travel times. Note that if runtime conditions still violate the actual flight time (τ¯a τ_a) TERRA might require complete mission re-planning, whereas PRO-SPECT can perform online re-planning. As TERRA does not support distinct xfx_f and x0x_0, we set xf=x0=(0,0,0)x_f=x_0=(0,0,0). A plan is generated for each of the 10 UAVP_UAV and executed 100 times via independent stochastic travel time realizations to obtain mean p^r p_r. TERRA uses rendezvous points (UGV points), where the UGV remains stationary while the UAV visits monitoring points (UAVP_UAV) and meets with the UGV. This design choice can significantly slow missions when monitoring points are far apart. PRO-SPECT addresses this by allowing the UGV to move concurrently with the UAV. As shown in Table VII, PRO-SPECT consistently achieves lower mission times and substantially lower failure rates that always satisfy p^r<pr p_r<p_r, while TERRA’s p^r p_r reaches up to 0.85 in some configurations. TABLE VII: TERRA vs. PRO-SPECT: Computation Time, Mission Time, τ(X)τ(X), and Empirical Failure Rate, p^r p_r, Varying n n TERRA PRO-SPECT Comp. Time (s) () τ(X) (s) p_r Comp. Time (s) () τ(X) (s) p_r 25 0.017±0.0069 0.017± 0.0069 12000±110012000± 1100 0.0760.076 4.0±0.214.0± 0.21 ± 6200± 500 0.0095 50 0.09±0.044 0.09± 0.044 16000±140016000± 1400 0.310.31 68±2.768± 2.7 ± 6900± 780 0.014 75 0.31±0.23 0.31± 0.23 19000±160019000± 1600 0.680.68 380±6.5380± 6.5 ± 7600± 790 0.014 100 0.82±0.37 0.82± 0.37 22000±190022000± 1900 0.850.85 1300±141300± 14 ± 8600± 480 0.0013 IV-F2 Comparison to RSPECT Unlike TERRA, RSPECT [er2025rspectrobustscalableplanner] supports distinct xfx_f and x0x_0, and does not require a known environment a priori. RSPECT handles uncertainty through its deterministic margins (δa,δg)( _a, _g), offering lower bounds on plan robustness; however, it cannot bound the probability of failure to a user-specified risk level. In contrast, PRO-SPECT uses a joint chance constraint, directly bounding the probability of failure globally to prp_r. RSPECT’s δa _a and δg _g are set by estimating prp_r as a fraction of the uniform distribution, which is then used to scale τ¯a τ_a (i.e., conservative planning bounds). This assumes the worst-case travel time μ+3σμ+ 3σ for pr=0p_r=0; the mean μ at pr=0.5p_r=0.5; and the best-case μ−3σμ- 3σ at pr=1p_r=1: δ∗=τ¯a(1−μ+3σ(1−2pr)). _*= τ_a (1- μ+ 3σ(1-2p_r) ). (20) This approximation is necessitated by RSPECT’s lack of a probabilistic planning mechanism: without a chance constraint, this represents the closest feasible equivalence under the assumed uniform distribution. For each combination of n and pr∈0.01,0.1,0.2,0.5p_r∈\0.01,0.1,0.2,0.5\ a plan is generated for each of the 10 UAVP_UAV instances, and executed 1000 times under independent stochastic travel time realizations to estimate mean p^r p_r. As shown in Table VIII, computation time is independent of prp_r for both RSPECT and PRO-SPECT. For RSPECT, this is expected as (20) is used. For PRO-SPECT, this is a stronger result. Since DP optimizes under a joint chance constraint, tighter prp_r would be expected to demand more tours and computation effort. However, this effect is weak, as the increase in number of tours remains modest. As demonstrated in all cases of Table VIII, PRO-SPECT achieves mission times up to 10%10\% lower than RSPECT, while maintaining p^r<pr p_r<p_r. The difference is more evident in higher prp_r cases: at pr=0.5p_r=0.5 and n=100n=100, RSPECT’s p^r p_r rises to 0.9; while PRO-SPECT maintains p^r=0.11 p_r=0.11, within the specified prp_r. This is an important limitation: the deterministic margin cannot adapt to specified prp_r, causing p^r p_r to diverge. RSPECT achieves much lower computation times and has an O(n3)O(n^3) time complexity, which permits a design decision between plan efficiency and safety, and computation cost. TABLE VIII: RSPECT vs. PRO-SPECT: Comp. Time, Mission Time, τ(X)τ(X), and Empirical Failure Rate, p^r p_r, Varying n, prp_r p_r n RSPECT PRO-SPECT Comp. Time (s) () τ(X) (s) p_r Comp. Time (s) () τ(X) (s) p_r 0.01 25 0.057±0.012 0.057± 0.012 5900±7505900± 750 0 6.6±0.116.6± 0.11 ± 5800± 720 0.00010.0001 50 0.16±0.017 0.16± 0.017 7100±6407100± 640 0 140±8.8140± 8.8 ± 6700± 530 0.00210.0021 75 0.32±0.048 0.32± 0.048 8100±4908100± 490 0.0006 790±2.5790± 2.5 ± 7700± 440 0.00100.0010 100 0.52±0.098 0.52± 0.098 9000±6009000± 600 0.00130.0013 3300±333300± 33 ± 8400± 640 0.0003 0.1 25 0.055±0.012 0.055± 0.012 5800±5905800± 590 0.0250.025 8.1±0.218.1± 0.21 ± 5400± 670 0.018 50 0.14±0.02 0.14± 0.02 7100±8207100± 820 0.0290.029 120±1.1120± 1.1 ± 6500± 570 0.011 75 0.32±0.05 0.32± 0.05 8200±3808200± 380 0.0250.025 850±1.6850± 1.6 ± 7600± 560 0.015 100 0.53±0.075 0.53± 0.075 8800±5208800± 520 0.0270.027 2800±7.52800± 7.5 ± 8200± 510 0.0061 0.2 25 0.052±0.005 0.052± 0.005 6100±5306100± 530 0.0400.040 7.7±0.137.7± 0.13 ± 5400± 670 0.018 50 0.15±0.030 0.15± 0.030 6900±5506900± 550 0.0750.075 120±1.5120± 1.5 ± 6500± 570 0.011 75 0.32±0.053 0.32± 0.053 7800±6007800± 600 0.150.15 800±2800± 2 ± 7500± 620 0.024 100 0.54±0.096 0.54± 0.096 8500±5608500± 560 0.130.13 2900±102900± 10 ± 8200± 510 0.0061 0.5 25 0.051±0.0055 0.051± 0.0055 5500±6005500± 600 0.490.49 6.2±0.286.2± 0.28 ± 5200± 550 0.10 50 0.13±0.017 0.13± 0.017 6600±4306600± 430 0.630.63 110±1.3110± 1.3 ± 6500± 620 0.033 75 0.30±0.041 0.30± 0.041 7600±6407600± 640 0.740.74 800±2.6800± 2.6 ± 7400± 610 0.11 100 0.53±0.085 0.53± 0.085 8300±5508300± 550 0.900.90 3100±203100± 20 ± 8100± 470 0.11 V Simulations V-A Setup To validate PRO-SPECT, we simulate the UAV-UGV team in ROS2 using a ROSflight-based UAV (ROScopter) [moore2025rosflight20leanros] and a Clearpath Jackal UGV. Stochasticity is introduced via an unknown zero-mean spatial wind field generated by Perlin Noise [perlin1985image]. This distribution produces smooth vector fields with spatial self-correlation, consistent with structured atmospheric disturbances, providing a suitable stochastic environment. UAVP_UAV instances were created inside (1) with x¯=y¯=40 x= y=40m and fixed z=5z=5m, with n=10n=10 and pr=0.1p_r=0.1 repeated over 1010 trials. Online re-planning is enabled with horizon m~=2 m=2. Simulation parameters are presented in Table IX. TABLE IX: Mission Parameters for Simulations Parameter Value Parameter Value x0x_0 (Initial point) (0,0,0)(0,0,0) xfx_f (Final point) (40,40,0)(40,40,0) τ¯a τ_a (Max flight time) 6060 s γ (Recharge ratio) 11 w¯x,w¯y w_x, w_y (Max wind speed, x, y) 11 m/s w¯z w_z (Max wind speed, z) 0.30.3 m/s [v¯a,v¯a][ v_a, v_a] (UAV speed) [1.5,2][1.5,2] m/s [v¯g,v¯g][ v_g, v_g] (UGV speed) [0.15,0.25][0.15,0.25] m/s V-A1 Agent Models To connect the travel models (4), (5) to the spatial wind field, we use the fact that wind speed is bounded. Consider a UAV edge from u to v with length L in direction d d with closed-loop along-track speed va∈[v¯a,v¯a]v_a∈[ v_a, v_a] under PID tracking. Given component-wise wind bounds |wx|≤w¯x|w_x|≤ w_x, |wy|≤w¯y|w_y|≤ w_y, |wz|≤w¯z|w_z|≤ w_z (Table IX), the along-track component satisfies |d^⊤w|≤w¯∥| d w|≤ w_ , where w¯∥:=|d^x|w¯x+|d^y|w¯y+|d^z|w¯z w_ :=| d_x| w_x+| d_y| w_y+| d_z| w_z. Assuming v¯a>w¯∥ v_a> w_ ,888Unbounded wind may make the problem infeasible. the UAV edge travel time is bounded: tmin,a(u,v)=Lv¯a+w¯∥,tmax,a(u,v)=Lv¯a−w¯∥.t_ ,a(u,v)= L v_a+ w_ , t_ ,a(u,v)= L v_a- w_ . (21) Since only bounds are available, we construct (4) assuming a uniform distribution, which conservatively inflates V because Perlin noise tends to cluster about the mean. We assume independence (Cθ=0C_θ=0) in the absence of a known wind distribution. Mθ,a(u,v)=tmin.a(u,v)+tmax,a(u,v)2,Vθ,a(u,v)=(tmax,a(u,v)−tmin,a(u,v))212.M_θ,a(u,v)= t_ .a(u,v)+t_ ,a(u,v)2, V_θ,a(u,v)= (t_ ,a(u,v)-t_ ,a(u,v) )^212. (22) The UGV moments are obtained similarly, with tmin,g(u,v)=L/v¯gt_ ,g(u,v)=L/ v_g and tmax,g(u,v)=L/v¯gt_ ,g(u,v)=L/ v_g from vg∈[v¯g,v¯g]v_g∈[ v_g, v_g] under PID tracking. Figure 2: Simulation setup. (a) UAV-UGV team in the simulated environment. (b) Simulated wind field applied to the UAV, with arrow direction and magnitude indicating local wind velocity. V-B Results Across all 10 trials, one trial experienced one tour time above τ¯a τ_a, giving total p^r=0.1 p_r=0.1 and maintaining the specified pr=0.1p_r=0.1. The mean of the ratio of empirical to planned mission time τ^(X)τ(X) τ(X)τ(X) was 1.02±0.091.02± 0.09 across successful trials. Fig. 3 illustrates a representative run: at t=0t=0 the full plan (m=4m=4) is initialized (Fig. 3(a)), and as the mission progresses the online re-planner updates after each UAV point to refine the remaining tours in response to wind-induced disturbances. Re-planning is visible in the evolving plans at t=150t=150 s and t=410t=410 s: (Fig. 3(b)) and (Fig. 3(c)). (a) t=0t=0 (b) t=150t=150 (c) t=410t=410 Figure 3: Mission plan in the simulations with online re-planning. (3(a)) at mission start, (3(b)) partway through second tour, and (3(c)) at mission end Less than 1%1\% of mission time was spent waiting for computation; online re-planning was fast enough to execute on the run. Therefore the increase of the mission time is largely due to wind-induced delay rather than re-planning overhead. These results confirm that probabilistic energy constraints hold under realistic wind-induced uncertainty, and that online re-planning restores feasibility on the fly. VI Conclusion We presented PRO-SPECT, a scalable algorithm for energy-aware UAV-UGV planning in stochastic environments. The problem was formulated as a Mixed-Integer Program with a joint chance constraint. The integrated offline-online framework combines TSP-based visit ordering with a dynamic program for tour construction, with an online re-planner that provably preserves the global risk bound under disturbances. Feasibility and worst-case time complexity were formally guaranteed (Thm.1). Validations via numerical evaluations and ROS simulations were carried out. Failure rate was observed below the allowable limit in all cases, with mission times competitive with or better than all baselines. Future work includes extending our method to multi-UAV fleets and incorporation of more complex (spatial, temporal, logical) planning specifications. References