Multi-UAV coordinated path planning based on many-objective optimization

Xingjuan Cai, Zhaoming Hu, Zhixia Zhang, Qian Wang, Zhihua Cui, Wensheng ZhangScientia 2021 · DOI

Abstract

With the expansion of unmanned aerial vehicle (UAV) applications, coordinated path planning has become a critical challenge. This paper presents a many-objective optimization model that simultaneously addresses track distance, threat avoidance, energy consumption, and fleet coordination. By introducing the NSGAIII-ICO algorithm, which utilizes a novel individual evaluation mating strategy, the proposed method effectively balances convergence and diversity to find optimal flight paths in complex environments.

Introduction

Planning paths for multiple Unmanned Aerial Vehicles (UAVs) is a complex balancing act. Mission success depends on minimizing distance, avoiding threats (such as radar or air defense), optimizing energy consumption, and ensuring fleet coordination to prevent collisions. Traditionally, these conflicting goals are combined into a single score using weighted summation—a process known as scalarization. However, this approach is highly subjective and often fails to capture the nuances of high-dimensional trade-offs.

To overcome these limitations, researchers have shifted toward Many-Objective Optimization Problems (MaOPs), where each goal is treated as a separate objective. In such high-dimensional spaces, standard algorithms often struggle as most solutions appear equally viable, leading to a breakdown in the selection process. This paper introduces a robust model and a specialized algorithm to navigate these challenges.

The Many-Objective Model

The proposed model evaluates potential flight paths across four distinct dimensions:

  1. Track Distance: Minimizing the total length of the flight to ensure mission efficiency.
  2. Threat Cost: Navigating around modeled cylindrical penalty areas representing radar and missile zones.
  3. Energy Consumption: Specifically modeling the power required to maintain a stable data link between the UAVs and the ground station.
  4. Spatial Coordination: Ensuring a minimum safe distance between UAVs to prevent collisions while maintaining the proximity required for fleet communication.

The NSGAIII-ICO Algorithm

To solve the MaOP, the researchers developed NSGAIII-ICO, an enhancement of the popular NSGA-III algorithm. The core innovation is the Individual Evaluation Mating Strategy (ICO), which guides the evolution of paths more effectively than random selection.

In this framework, an "individual" represents a set of paths for the entire fleet. These paths are encoded as a sequence of tokens or control points representing the path segments.

Individual representation in the evolutionary algorithm

The algorithm utilizes a Comprehensive Evaluation Indicator (CAD) to score individuals based on two critical factors:

  • Convergence: How close the solution is to the theoretical Pareto-optimal front.
  • Diversity: How well-distributed the solutions are, ensuring a wide variety of trade-offs are explored.

By dynamically shifting focus from convergence in the early stages to diversity in the later stages, NSGAIII-ICO avoids the stagnation that plagues simpler many-objective algorithms.

Experimental Setup and Results

The model was validated in a simulated 3D environment (200 km × 200 km × 4 km) featuring four circular threat zones. The fleet consisted of two UAVs, with each flight path divided into 40 segments for optimization.

NSGAIII-ICO was benchmarked against three leading algorithms: NSGA-III, RVEA, and GrEA. The results demonstrated that the proposed algorithm achieved superior median values across distance, energy, and synergy objectives. Furthermore, box plot analysis indicated a tighter distribution of results, suggesting that NSGAIII-ICO consistently finds high-quality paths rather than relying on occasional optimal runs. Visual simulations confirmed that the UAVs successfully navigated between threat zones while maintaining a coordinated formation.

Conclusion and Future Work

The NSGAIII-ICO algorithm provides a powerful tool for multi-UAV path planning by effectively managing the complexities of many-objective optimization. While it excels at spatial coordination in static environments, future work will address temporal coordination (simultaneous arrival) and the challenges of dynamic mission spaces with moving threats. Additionally, scaling the model to handle large-scale UAV swarms remains a key objective for future research.

Summary updated

Abstract

With the increase in the application areas of unmanned aerial vehicles (UAVs), the problem of coordinated path planning for multi-UAVs becomes more and more significant. However, most of the existing methods optimize this problem by converting multi-objective weighting into a single-objective problem. To reduce the subjectivity of multi-objective weighting, a coordinated path planning model based on many-objective optimization is proposed to optimize the multi-UAVs track distance cost, track threat cost, track energy cost, and coordination performance. In the many-objective evolutionary algorithm (MaOEA), the convergence and diversity of the individuals are both important indicators to evaluate the performance of individuals. To solve the problem that individuals in the algorithm are not easy to evaluate, an NSGA-III algorithm based on the individual evaluation mating strategy (NSGAIII-ICO) is proposed, which can comprehensively evaluate the performance of individuals according to the generation of the algorithm and guide the mating operation. Simulation results show that this model can effectively provide coordinated tracks for multi-UAVs, and by comparing it with other MaOEAs, it can be proved that this proposed algorithm can effectively improve the performance of coordinated path planning for multi-UAVs.
BibTeX
@inproceedings{cai2021multi,
  author = {Xingjuan Cai and Zhaoming Hu and Zhixia Zhang and Qian Wang and Zhihua Cui and Wensheng Zhang},
  title = {{Multi-UAV coordinated path planning based on many-objective optimization}},
  booktitle = {Scientia},
  year = {2021},
  doi = {10.1360/ssi-2020-0218},
}
Figure