PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Cahit Ikbal Er, Yasin Yazicioglu

arXiv:2610.12670v1cs.ROcs.MAcs.SYeess.SY

TL;DR

Energy-constrained UAV-UGV planning has generally left monitoring points free to be visited in any order, despite missions that require precedence. This paper develops a polynomial-time heuristic that jointly plans routes and timing under energy and ordering constraints. The algorithm scales to large instances that exact solvers cannot handle and yields shorter makespans than metaheuristic and heuristic baselines.

  • Problem

    Energy-constrained UAV-UGV planning methods generally allow monitoring points to be visited in any order, while missions may require precedence constraints.

    Source: §I · p. 1

  • Method

    A polynomial-time heuristic jointly constructs team assignments, energy-feasible tours, and travel timing for precedence-constrained UAV-UGV planning.

    Source: §I · p. 1, A. Proposed Robust Planning Algorithm · p. 3

  • Results

    The algorithm scales to large instances intractable for exact solvers and yields significantly shorter makespans than metaheuristic and heuristic baselines.

    Source: §V · p. 7

  • Takeaways & Limitations

    The approach distributes ordered points across teams while guaranteeing feasible solutions in O(mn^3) time.

    Source: §V · p. 7

Abstract

from arXiv · show

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

Energy-limited UAV monitoring can use UGVs as mobile charging stations, but prior energy-constrained planning generally leaves visit order unconstrained. This paper formulates robust planning with precedence constraints, jointly choosing routes and timing to minimize mission completion time under bounded travel-time disturbances.

I. INTRODUCTION

  • The proposed heuristic jointly determines vehicle routes and timing while seeking minimum mission completion time under energy, precedence, and bounded travel-time constraints.The mixed-integer formulation is NP-hard, and the heuristic has formal feasibility and worst-case complexity guarantees.Source: §I · p. 1

II. PROBLEM FORMULATION

  • Teams use UGVs as mobile charging stations and transport UAVs between aerial tours, while precedence constraints govern the order of monitoring-point visits.The plan also chooses how long each leg takes, allowing teams to slow down rather than reroute to satisfy ordering constraints.Source: §II · pp. 1–2
  • Energy margins δa and δg protect tour feasibility, while ordering margin δo provides separation between precedence-constrained visits against bounded travel-time delays.Larger margins restrict the feasible plans and can increase the minimum achievable makespan.Source: §II · pp. 1, 3
  • The mission assigns monitoring points to multiple UAV-UGV teams, each with initial and terminal positions, and requires visits to respect a given precedence DAG.UAV endurance is modeled as a maximum flight time; UGVs are assumed to have sufficient energy for the mission.Source: §II · p. 2

III. PROPOSED SOLUTION

The proposed solution addresses an NP-hard mixed-integer planning problem with a polynomial-time heuristic; the section states that it presents formal guarantees for the algorithm.

III. PROPOSED SOLUTION

  • Problem (3) generalizes the mTSP and SOP, making it NP-hard; exact methods such as branch and cut become intractable for large |PUAV|.The section presents Alg. 1 as a polynomial-time heuristic for solving the problem.Source: §III · p. 3
  • Alg. 1 is a polynomial-time heuristic for solving the planning problem.The problem is formulated as a mixed-integer program that generalizes the mTSP and SOP.Source: §III · p. 3
  • The section presents formal guarantees for the feasibility of Alg. 1’s solution and its worst-case complexity.Source: §III · p. 3

A. Proposed Robust Planning Algorithm

Algorithm 1 jointly constructs team assignments, point sequences, tours, and timing so precedence constraints can couple teams without forcing all ordered points onto one team. It balances team workloads while maintaining energy-feasible tours and visit order.

A. Proposed Robust Planning Algorithm

  • Assignment, sequences, tours, and timing are constructed simultaneously, allowing ordered points to be distributed across teams rather than planned independently.Precedence constraints between points assigned to different teams couple their plans through visit times.Source: A. Proposed Robust Planning Algorithm · p. 3
  • The guarantees cover feasibility and worst-case runtime, but establish no approximation bound on solution quality relative to the optimum.The stated formal guarantees concern feasibility and worst-case time complexity.Source: A. Proposed Robust Planning Algorithm · p. 3
  • Only points whose predecessors are placed enter the ready set, and each new visit is timed against its predecessors’ known visit times.The algorithm imposes the ordering margin δo through a lower bound on the candidate visit time.Source: A. Proposed Robust Planning Algorithm · p. 3
  • For each team–point option, the algorithm either adds the point to an open tour if energy-feasible or opens a new tour and accounts for waiting, recharge, and UGV relocation.When a point joins an open tour, candidate collect points are filtered for UAV and UGV energy feasibility; closing a tour includes recharge and travel to the next release point.Source: A. Proposed Robust Planning Algorithm · pp. 3–4
  • The algorithm commits the team–point pairing that minimizes the maximum accumulated team cost, distributing workload rather than greedily choosing the earliest individual visit.The selected option is then committed to the team plan, with a tour opened or closed as needed.Source: A. Proposed Robust Planning Algorithm · p. 4

B. Formal Guarantees

Under Assumption 1, Algorithm 1 returns a feasible solution whenever one exists and has worst-case time complexity O(mn3). Its feasibility argument relies on the precedence graph being acyclic and on every point admitting an energy-feasible single-point tour.

B. Formal Guarantees

  • Assumption 1 requires each monitoring point to admit an energy-feasible single-point tour from its ground projection.The condition covers the UAV flight out and back, with the stated energy margins.Source: B. Formal Guarantees · p. 5
  • Under Assumption 1, Algorithm 1 returns a feasible solution to (3) if one exists, with worst-case time complexity O(mn3).The bound is for m teams and n monitoring points.Source: B. Formal Guarantees · p. 5
  • Because the precedence graph is a DAG, each iteration has a ready point to assign, and Assumption 1 makes opening a new tour energy-feasible.The algorithm places every monitoring point and commits visit times satisfying each precedence edge with margin δo.Source: B. Formal Guarantees · p. 5
  • The complexity analysis bounds the inner loop by O(m|E≺| + mn2) per iteration and concludes that the overall O(mn3) term dominates.The bound uses |E≺| ≤ n(n − 1)/2 for a DAG.Source: B. Formal Guarantees · p. 5

IV. NUMERICAL EVALUATIONS

The evaluation covers scalability, precedence-density and robustness-margin effects, and comparisons with exact and heuristic baselines. Its setup generates acyclic precedence graphs and reports results over randomly generated instances.

IV. NUMERICAL EVALUATIONS

  • The evaluation examines scalability, precedence density, robustness margins, branch and cut, simulated annealing, and a decoupled precedence-greedy baseline.Experiments used Python 3.9 on an Intel i9-13900H CPU with 16 GB RAM.Source: §IV · p. 5
  • Precedence graphs are generated from a random point permutation, with edges directed from earlier to later points to prevent cycles.The environment and monitoring points are specified as part of the mission setup.Source: §IV · pp. 5–6
  • Unless specified otherwise, results are means ± standard deviations over 25 randomly generated instances, using the parameters in Table I.Table I is identified as listing mission and method parameters.Source: §IV · p. 6, Table I · p. 6

A. Scalability

Algorithm 1 solves the largest tested configuration, n=100 and m=10, in under 0.35 seconds. Empirical runtime scaling is consistent with the theoretical O(mn3) bound.

A. Scalability

  • Empirical computation time scales as n2.15–n2.26 and m0.62–m0.68, consistent with the theoretical O(mn3) bound.Source: A. Scalability · p. 6
  • Makespan increases with the number of points and decreases as additional teams parallelize the mission.Source: A. Scalability · p. 6
  • Under 0.35 s, Algorithm 1 solves the largest tested configuration, n=100 and m=10.Table II reports makespan and computation time across n ∈ {25, 50, 75, 100} and m ∈ {1, 2, 4, 10}.Source: Table II · p. 6, A. Scalability · p. 6

B. Effect of Precedence Density

The section examines how precedence density affects routing freedom and makespan for n=100. Alg. 1 continues to distribute ordered points across teams even when dense edges form a single connected component.

B. Effect of Precedence Density

C. Effect of Robustness Margins

At n=100, the section varies energy margins and the ordering margin independently. Energy margins preserve much of the parallel-team benefit, while large ordering margins constrain it.

C. Effect of Robustness Margins

  • At large δo, the makespan reduction from m=1 to m=10 falls to 58%, and the benefit of m=4 to m=10 shrinks from 28% to 8%.Small ordering margins, δo≤200 s, are absorbed with almost no extra time.Source: C. Effect of Robustness Margins · p. 6
  • Increasing energy margins leaves the m=1-to-m=10 makespan reduction stable at around 75% to 80%.The energy-margin sweep uses δa=δg∈[0,490] s.Source: C. Effect of Robustness Margins · p. 6
  • The independent sweeps vary δa=δg and δo at n=100, holding the other margins at zero in each sweep.Fig. 2 plots makespan, with error bars of ±1 standard deviation.Source: Figure 2 · p. 6, C. Effect of Robustness Margins · p. 6

D. Comparison to Branch and Cut

The comparison uses Branch and Cut as a near-optimal reference for Alg. 1. Branch and Cut becomes costly as instance size grows, while Alg. 1 runs quickly with makespans within roughly 8% to 28% of the reference.

D. Comparison to Branch and Cut

  • The reference encodes the problem as an MIQCP and solves it with Gurobi Branch and Cut.The reported solver settings include a 5% MIP gap and a 600-second time limit.Source: D. Comparison to Branch and Cut · p. 6
  • Alg. 1 computes in less than a millisecond across configurations, with makespans within roughly 8% to 28% of near-optimal.The cited comparison uses n∈{2,3,4} and m∈{1,2}.Source: D. Comparison to Branch and Cut · p. 7, Table IV · p. 7
  • Branch and Cut computation time scales exponentially as n increases from 2 to 4, exceeding 200 seconds for m=2 at n=4 to reach the 5% optimality threshold.The comparison restricts instance sizes for tractability.Source: D. Comparison to Branch and Cut · p. 7

E. Comparison to Simulated Annealing

The comparison evaluates Alg. 1 against simulated annealing at n=15. Alg. 1 produces shorter makespans while taking roughly four orders of magnitude less computation time.

E. Comparison to Simulated Annealing

F. Comparison to the Decoupled Precedence Baseline

When precedence links merge the mission into one component, the decoupled baseline assigns it to one team, while Alg. 1 distributes ordered points across teams and reduces makespan. The conclusion presents Alg. 1 as a feasible polynomial-time heuristic that scales to large instances.

F. Comparison to the Decoupled Precedence Baseline

  • At d = 0.5, the baseline runs up to 57 times faster, but at d = 20 and m = 10, Alg. 1 yields a nearly 10 times shorter makespan at 0.043 s versus 0.010 s.Alg. 1's computation time inversely scales with precedence density and remains within its O(mn3) worst-case guarantee; denser constraints shrink the ready set and reduce cross-team pairings.Source: F. Comparison to the Decoupled… · p. 7
  • 89.8% makespan reduction for m = 10 at d = 20: Alg. 1 distributes ordered points across teams when the baseline assigns the single-component mission to one team.The comparison covers n = 100, with precedence density d ≥ 8.0 producing a single connected component; Table VI reports makespan and computation time.Source: Table VI · p. 7, F. Comparison to the Decoupled… · p. 7

V. CONCLUSION

  • Alg. 1 guarantees feasible solutions in O(mn3) time and scales to large instances intractable for exact solvers, with shorter makespans than metaheuristic and heuristic baselines.Future work includes additional spatiotemporal constraints, online replanning, and real-world validation.Source: §V · pp. 7–8
Loading 2610.12670v1…