Robust and Scalable UAV-UGV Planning for Aerial Monitoring under Energy and Precedence Constraints

Cahit Ikbal Er; Yasin Yazicioglu

cs.ROOct 8, 2026

Robust and Scalable UAV-UGV Planning for Aerial Monitoring under Energy and Precedence Constraints

Authors: Cahit Ikbal Er, Yasin Yazicioglu

Organizations: Department of Mechanical and Industrial Engineering, Northeastern University, Boston, MA, USA · Departments of Mechanical and Industrial Engineering and Electrical and Computer Engineering, Northeastern University, Boston, MA, USA

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.

Figures & tables

Fig. 1 : Alg. 1 for

n{=}25

and

m{=}4

. (a)

G_{\prec}{=}(\mathcal{P}_{\text{UAV}},E_{\prec})

, 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

p^{\mu}_{\text{s}}

and

p^{\mu}_{\text{f}}

, shared by all teams here. The plan respects the ordering requirements.

Parameter	Value
$\bar{x},\bar{y}$ (Environment size)	4000 m
$\underline{z}$ (Monitoring height)	100 m
$\{p^{\mu}_{\text{s}},p^{\mu}_{\text{f}}\}_{\mu=1}^{m}$ (Start, finish positions)	$(0,0,0)$ , $(4000,4000,0)$
$d$ (Precedence density)	$0.5$
$\ell(u,v)$ (Shortest path)	$\lVert u{-}v\rVert_{2}$
$s_{H},s_{V}$ (UAV cruise, climb speed)	10 m/s, 2 m/s

TABLE I : Mission and Method Parameters

	$m=1$		$m=2$
$n$	$\max_{\mu}\tau$ (s)	Comp. (s)	$\max_{\mu}\tau$ (s)	Comp. (s)
25	8900 $\pm$ 1200	0.004 $\pm$ 0.001	5400 $\pm$ 850	0.006 $\pm$ 0.001
50	10900 $\pm$ 1700	0.015 $\pm$ 0.002	6800 $\pm$ 810	0.026 $\pm$ 0.003
75	13300 $\pm$ 1400	0.038 $\pm$ 0.004	7500 $\pm$ 760	0.064 $\pm$ 0.006
100	15100 $\pm$ 1600	0.071 $\pm$ 0.005	8300 $\pm$ 880	0.126 $\pm$ 0.015
	$m=4$		$m=10$

TABLE II : Makespan (

\max_{\mu}\tau

) and computation time under Alg. 1 across numbers of points (

n

) and numbers of teams (

m

)

		$\max_{\mu}\tau$ (s)
$d$	$c/n$	$m{=}1$	$m{=}4$	$m{=}10$	Red. (%)
0.5	0.04	15100 $\pm$ 1600	5300 $\pm$ 540	3900 $\pm$ 310	74
1	0.06	17900 $\pm$ 1600	6200 $\pm$ 570	4200 $\pm$ 260	77
3	0.12	27600 $\pm$ 2500	7600 $\pm$ 530	4900 $\pm$ 240	82
8	0.26	40400 $\pm$ 4600	9900 $\pm$ 890	5500 $\pm$ 360	86
20	0.51	57100 $\pm$ 4800	12000 $\pm$ 1100	6000 $\pm$ 410	89

TABLE III : Makespan (

\max_{\mu}\tau

) of Alg. 1 across precedence densities (

d

) and numbers of teams (

m

) at

n{=}100

c

is the longest chain in

G_{\prec}

, and Red. is the makespan reduction from

m{=}1

m{=}10

Fig. 2 : Makespan under Alg. 1 against the energy margins

\delta_{a}{=}\delta_{g}

(left) and the ordering margin

\delta_{o}

(right), at

n{=}100

, each sweep holding the remaining margins at zero. Error bars are

\pm 1

std.

		Branch & Cut			Alg. 1
$m$	$n$	$\max_{\mu}\tau$ (s)	Comp. (s)	Gap (%)	$\max_{\mu}\tau$ (s)	Comp. (s)
1	2	2800 $\pm$ 380	0.19 $\pm$ 0.12	1.2 $\pm$ 2.0	3100 $\pm$ 750	$<0.001$
	3	2800 $\pm$ 360	1.4 $\pm$ 1.0	1.5 $\pm$ 1.9	3200 $\pm$ 800	$<0.001$
	4	3100 $\pm$ 330	19 $\pm$ 16	2.1 $\pm$ 1.8	3900 $\pm$ 890	$<0.001$
2	2	2600 $\pm$ 290	0.49 $\pm$ 0.33	1.5 $\pm$ 1.8	2800 $\pm$ 310	$<0.001$
	3	2600 $\pm$ 330	13 $\pm$ 12	2.8 $\pm$ 2.2	2800 $\pm$ 210	$<0.001$

TABLE IV : Makespan (

\max_{\mu}\tau

), computation time, and optimality gap of the Branch and Cut (B&C) against Alg. 1 across different number of points

(n)

and team sizes (

m

)

		Comp. (s)			$\max_{\mu}\tau$ (s)
$m$	$T_{\max}$	100k	150k	200k	100k	150k	200k
1	500	18.6 $\pm$ 1.2	27.7 $\pm$ 1.8	36.8 $\pm$ 2.3	8600 $\pm$ 1200	8100 $\pm$ 1200	7800 $\pm$ 1200
	750	18.9 $\pm$ 1.2	28.3 $\pm$ 2.0	37.7 $\pm$ 2.5	8400 $\pm$ 1200	8100 $\pm$ 1200	7800 $\pm$ 1200
	1000	19.6 $\pm$ 1.6	29.3 $\pm$ 2.4	38.7 $\pm$ 3.1	8800 $\pm$ 1200	8200 $\pm$ 1200	7900 $\pm$ 1100
2	500	37.8 $\pm$ 2.4	55.8 $\pm$ 3.3	73.5 $\pm$ 4.0	6400 $\pm$ 1000	6000 $\pm$ 900	5700 $\pm$ 790
	750	41.4 $\pm$ 4.7	61.7 $\pm$ 7.5	82.0 $\pm$ 9.8	7200 $\pm$ 1000	6800 $\pm$ 1100	6400 $\pm$ 1100

TABLE V : Makespan (

\max_{\mu}\tau

) and computation time of Simulated Annealing across maximum temperatures (

T_{\max}

) and cooling steps for different number of teams (

m

)

		$\max_{\mu}\tau$ (s)		Comp. (s)
$d$	$m$	Baseline	Alg. 1	Baseline	Alg. 1
0.5	1	$15400\pm 2100$	$\mathbf{15100\pm 1600}$	$\mathbf{0.007\pm 0.000}$	$0.071\pm 0.005$
	4	$10400\pm 1100$	$\mathbf{5300\pm 540}$	$\mathbf{0.006\pm 0.000}$	$0.205\pm 0.021$
	10	$8900\pm 1700$	$\mathbf{3900\pm 310}$	$\mathbf{0.006\pm 0.001}$	$0.342\pm 0.033$
3.0	1	$28800\pm 2900$	$\mathbf{27600\pm 2500}$	$\mathbf{0.007\pm 0.001}$	$0.017\pm 0.002$
	4	$28700\pm 2900$	$\mathbf{7600\pm 530}$	$\mathbf{0.008\pm 0.000}$	$0.055\pm 0.007$

TABLE VI : Makespan (

\max_{\mu}\tau

) and computation time comparison between Alg. 1 and the decoupled precedence baseline for different precedence densities (

d

) and numbers of teams (

m

), at

n=100

Explore similar work

PRO-SPECT: Probabilistically Safe Scalable Planning for Energy-Aware Coordinated UAV-UGV Teams in Stochastic Environments
Apr 2, 2026Roger Fowler, Cahit Ikbal Er, Benjamin Johnsenberg +1Motion Planning Multi-Robot Coordination
Khoury Department of Computer Sciences, Northeastern University, Boston, MA · The Charles Stark Draper Laboratory, Inc., Cambridge, MA · Department of Mechanical and Industrial Engineering, Northeastern University, Boston, MA +1
Collaborative Planning with Concurrent Synchronization for Operationally Constrained UAV-UGV Teams
Mar 6, 2026Zihao Deng, Qianhuang Li, Peng Gao +4Multi-Robot Coordination Multi-Robot Motion Planning
Zihao Deng, Qianhuang Li, Donghyun Kim, and Hao Zhang are with the University of Massachusetts Amherst, Amherst, MA, 01002, USA. · Peng Gao is with North Carolina State University, Raleigh, NC, 27695, USA. · Maggie Wigness and John Rogers are with the U.S. Army DEVCOM Army Research Laboratory (ARL), Adelphi, MD, 20783, USA.
Energy-Aware Collaborative Exploration for a UAV-UGV Team
Mar 23, 2026Cahit Ikbal Er, Saikiran Juttu, Yasin YaziciogluMulti-Robot Exploration Multi-Robot Coordination
Department of Mechanical and Industrial Engineering at Northeastern University, Boston, MA.

Apr 2, 2026J/K move · Enter open · S save

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

Khoury Department of Computer Sciences, Northeastern University, Boston, MA · The Charles Stark Draper Laboratory, Inc., Cambridge, MA · Department of Mechanical and Industrial Engineering, Northeastern University, Boston, MA+1

Motion Planning Multi-Robot Coordination

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

PRO-SPECT: Probabilistically Safe Scalable Planning for Energy-Aware Coordinated UAV-UGV Teams in Stochastic Environments

Collaborative Planning with Concurrent Synchronization for Operationally Constrained UAV-UGV Teams

Energy-Aware Collaborative Exploration for a UAV-UGV Team