A Mission Planning Method for Long-Endurance Unmanned Aerial Vehicles: Integrating Heterogeneous Ground Control Resource Allocation

Kai Li, Cheng Zhu, Xiaogang Pan, Long Xu, Kai LiuDrones 2024 · DOI

TL;DR

This paper tackles the complex problem of planning missions for long-endurance UAVs that require human operators (Ground Control Resources - GCRs). It introduces a novel optimization framework that integrates UAV mission sequencing with the allocation of heterogeneous GCRs, considering their varying capabilities and fatigue. The proposed Bilevel Programming Algorithm (BPA) significantly outperforms CPLEX in solving large-scale instances, achieving better solutions much faster.

What Problem Does This Paper Address?

Modern long-endurance UAVs (LE-UAVs) are powerful tools for tasks like surveillance and delivery, but they still rely on human operators (GCRs) for complex mission execution due to limited autonomous intelligence. Existing multi-UAV mission planning research often assumes full autonomy or overlooks crucial real-world factors: the varying skills and effectiveness of different GCRs, and how their performance degrades over time due to fatigue. This oversight can lead to suboptimal mission plans. The paper addresses this gap by proposing an integrated approach that simultaneously plans UAV routes and assigns tasks to specific GCRs, accounting for their unique capabilities and fatigue.

Methods

The authors formulate this integrated problem as a Mixed-Integer Linear Programming (MILP) model, termed the Heterogeneous Ground Control and Unmanned Aerial Vehicle Integrated Optimization Problem (H-G&U IOP). To solve this complex, NP-hard problem, especially for large-scale instances where traditional solvers struggle, they develop a Bilevel Programming Algorithm (BPA).

The BPA operates in two levels:

  1. Upper Level (Mission Planning): This level determines the optimal task sequence for each UAV. It employs a Hybrid Genetic Algorithm (HGA) framework. The HGA uses three novel initial solution generation strategies (Randomized Nearest Neighbor, Randomized Average Generation, Distributed Nearest Neighbor) and a Local Search-Variable Neighborhood Descent (LS-VND) strategy to improve solution quality.
  2. Lower Level (GCR Allocation): Once the UAV mission plan is set, this level allocates the most suitable heterogeneous GCR to each task. It uses a greedy algorithm combined with local search to assign GCRs, considering their profit maximization and availability.

The HGA's fitness function combines profits from both levels, penalizes constraint violations, and accounts for trajectory costs.

Datasets

The paper uses parameters inspired by Solomon's benchmark data for VRP problems to define airports, customer locations, and demands. Specific parameters for task execution time, GCR capability, UAV capacity, and endurance are randomly generated or set based on typical values. No new benchmark datasets were introduced.

Key Insights and Ideas

  • GCR Heterogeneity and Fatigue are Critical: The paper strongly emphasizes that ignoring the varying capabilities and fatigue of GCRs leads to suboptimal mission plans. Figure 1 vividly illustrates how a flexible GCR allocation strategy can yield significantly higher profits than fixed or ignored GCR considerations.
  • Integrated Planning is Necessary: Mission planning and GCR allocation are not independent problems. Coupling these decisions creates a more complex but ultimately more effective approach to maximizing mission profit.
  • Bilevel Programming for Complex Optimization: The bilevel structure effectively decomposes the problem into manageable sub-problems (mission planning and GCR allocation), allowing for a more efficient solution than a monolithic approach.
  • Hybrid Genetic Algorithm with LS-VND is Powerful: The combination of HGA with LS-VND proves highly effective in exploring the solution space and finding high-quality solutions for this complex problem.

Key Results

  • Superior Performance vs. CPLEX: The proposed BPA significantly outperforms the advanced optimization toolkit CPLEX. For small-scale instances, BPA achieves comparable or better solutions in a fraction of the time (average time ratio of 6.564% for 5 customers). For larger instances (15+ customers), CPLEX struggles to find feasible solutions within hours, while BPA provides superior solutions in seconds.
  • Speedup for Large Instances: For large-scale instances (20-100 customers), BPA consistently finds solutions much faster than CPLEX. For example, for instances with 20 customers, BPA achieves solutions in seconds, while CPLEX takes hours.
  • LS-VND Enhances BPA: The inclusion of the LS-VND module in the BPA significantly accelerates convergence and improves solution quality, as demonstrated by a 83.82% average time ratio improvement and a 0.36% average gap reduction compared to BPA without LS-VND.
  • GCR Degradation Impact: Sensitivity analysis shows that as GCR capability degrades faster (higher β), the system prioritizes high-value customers earlier, increasing their early-stage profit, but potentially decreasing overall profit if not managed well.

Limitations and Future Work

  • Model Linearization: While the MILP model is formulated, the paper notes that the objective function is nonlinear. Linearization via precomputation and lookup tables is used, which is a common technique but might introduce approximations.
  • Dynamic Scenarios: The current model assumes static conditions. Future work could address dynamic changes like customer demand fluctuations or UAV malfunctions, requiring faster replanning capabilities.
  • GCR Capability Modeling: The authors suggest that the GCR capability modeling could be further refined, although their current approach allows for linearization of various functions.
  • Broader Applicability: The proposed model and method are suggested to be extendable to other multi-robot systems beyond UAVs, such as USVs or UGVs.
  • Deep Reinforcement Learning: For faster response times in dynamic scenarios, exploring deep reinforcement learning methods is recommended.

Summary updated

Abstract

Long-endurance unmanned aerial vehicles (LE-UAVs) are extensively used due to their vast coverage and significant payload capacities. However, their limited autonomous intelligence necessitates the intervention of ground control resources (GCRs), which include one or more operators, during mission execution. The performance of these missions is notably affected by the varying effectiveness of different GCRs and their fatigue levels. Current research on multi-UAV mission planning inadequately addresses these critical factors. To tackle this practical issue, we present an integrated optimization problem for multi-LE-UAV mission planning combined with heterogeneous GCR allocation. This problem extends traditional multi-UAV cooperative mission planning by incorporating GCR allocation decisions. The coupling of mission planning decisions with GCR allocation decisions increases the dimensionality of the decision space, rendering the problem more complex. By analyzing the problem’s characteristics, we develop a mixed-integer linear programming model. To effectively solve this problem, we propose a bilevel programming algorithm based on a hybrid genetic algorithm framework. Numerical experiments demonstrate that our proposed algorithm effectively solves the problem, outperforming the advanced optimization toolkit CPLEX. Remarkably, for larger-scale instances, our algorithm achieves superior solutions within 10 s compared with CPLEX’s 2 h runtime.
BibTeX
@inproceedings{li2024mission,
  author = {Kai Li and Cheng Zhu and Xiaogang Pan and Long Xu and Kai Liu},
  title = {{A Mission Planning Method for Long-Endurance Unmanned Aerial Vehicles: Integrating Heterogeneous Ground Control Resource Allocation}},
  booktitle = {Drones},
  year = {2024},
  doi = {10.3390/drones8080385},
}
Figure