A Review of Constrained Multi-Objective Evolutionary Algorithm-Based Unmanned Aerial Vehicle Mission Planning: Key Techniques and Challenges

Abstract

UAV mission planning is one of the core problems in the field of UAV applications. Currently, mission planning needs to simultaneously optimize multiple conflicting objectives and take into account multiple mutually coupled constraints, and traditional optimization algorithms struggle to effectively address these difficulties. Constrained multi-objective evolutionary algorithms have been proven to be effective methods for solving complex constrained multi-objective optimization problems and have been gradually applied to UAV mission planning. However, recent advances in this area have not been summarized. Therefore, this paper provides a comprehensive overview of this topic, first introducing the basic classification of UAV mission planning and its applications in different fields, proposing a new classification method based on the priorities of objectives and constraints, and describing the constraints of UAV mission planning from the perspectives of mathematical models and planning algorithms. Then, the importance of constraint handling techniques in UAV mission planning and their advantages and disadvantages are analyzed in detail, and the methods for determining individual settings in multiple populations and improvement strategies in constraint evolution algorithms are discussed. Finally, the method from the related literature is presented to compare in detail the application weights of constrained multi-objective evolutionary algorithms in UAV mission planning and provide directions and references for future research.

1. Introduction

With the rapid development of Unmanned Aerial Vehicle (UAV) technology, UAV mission planning (UMP) has become an important research area that has attracted much attention. UMP has been increasingly used in a variety of fields, such as agriculture, logistics, rescue, and environmental monitoring [1,2], which has placed higher demands on UAVs in complex and changing environments and created higher requirements for UAVs to fulfil their tasks efficiently and safely. The core goals of UMP include mission assignment, trajectory planning, and obstacle avoidance. Through accurate mathematical models and advanced planning algorithms, it aims to enable a planning system to quickly respond to changes in the environment and adjust and optimize a planning scheme in real time. Therefore, UMP needs to be applicable not only in static environments but also in dynamic and uncertain environments, ensuring that UAVs can safely perform their missions in a variety of environments.

Traditional optimization methods often face a number of challenges when dealing with UMP problems [3]. First, UMP usually involves multiple conflicting optimization objectives, such as the conflict between the shortest trajectory and the lowest energy consumption. In practice, UAVs need to select the shortest trajectory to shorten their flight times, and at the same time, they need to reduce energy consumption to improve their efficiency when performing their missions. However, UAVs usually need to detour or adjust their flight altitudes in order to effectively avoid obstacles or unfavorable weather conditions, which increases their energy consumption. Second, UMP also needs to satisfy various coupled constraints, such as flight time, flight altitude limits, and environmental changes, which constrain each other and increase the complexity of UMP. Traditional optimization methods usually struggle to deal with multiple conflicting objectives at the same time [4,5] and perform poorly when faced with complex constraints, making it difficult to find an effective UMP solution.

The proposal of constrained multi-objective evolutionary algorithms (CMOEAs) has provided an effective approach to address these challenges. CMOEAs transform a problem into a multi-dimensional space by introducing the theory of multi-objective optimization to solve the Pareto optimal solution set, which determines the optimal balance of various optimization objectives. Secondly, CMOEAs incorporate constraint handling techniques, using methods such as adaptive functions, penalty functions, and repair strategies to deal with constraints and ensure that the UMP solutions generated during the search process satisfy the constraints. This approach provides a large set of candidate solutions so that the decision maker can choose the most appropriate solution according to their specific needs. It can also effectively deal with complex environmental changes and constraints. Therefore, CMOEAs improve the efficiency and flexibility of UAV mission planning and enhance the adaptability and reliability of UAVs in uncertain environments [6,7,8].

This paper provides a comprehensive review of CMOEAs in UMP. A detailed review of the mathematical models, classification of constraint handling techniques, and improvement strategies for UMP is presented from a new perspective, aiming to provide valuable references for scholars in the field of UMP research. To the best of our knowledge, no study has systematically summarized this topic. The main contributions of this paper can be summarized as follows:

• Firstly, UMP is classified in detail according to the execution links and operation modes of the planning system, and a new classification method is proposed according to the constraint processing techniques of UAV goal priority and constraint priority. Then, the key factors constraining the performance of UMP are discussed from the perspectives of both the mathematical model of UMP and the planning algorithm.
• By elaborating the UMP execution process based on a differential evolutionary algorithm, we clarify the embedded modules based on the constraint handling techniques in CMOEAs and outline the advantages and disadvantages of each current constraint handling technique. In addition, we introduce the CMOEA framework for solving optimization problems.
• According to the UMP execution process based on CMOEAs, we highlight individual setup methods for different populations and improvement strategies to help researchers and scholars quickly find suitable setup methods for different planning scenarios. At the same time, we propose for the first time to evaluate UMP performance from the perspective of UAV performance metrics and algorithm performance metrics together.

The rest of this paper is organized as follows: Section 2 describes the classification of UMP, its applications in different domains, and its constraints. Section 3 discusses the mathematical models of UMP and classical algorithm-based planning methods. Section 4 describes the constraint handling techniques in CMOEA-based UMP and the related literature. Section 5 details methods for determining individual settings in different populations, improvement strategies, and performance evaluation metrics. Section 6 describes the methodology for searching the literature on CMOEA-based UMP. The last section provides a summary and identifies future research directions.

2. Preliminary Information

This section first introduces the basic classification of UMP problems and the application areas involved. Then, the key role of UMP in 3D map reconstruction is described. Finally, the challenges and constraints faced by UMP are discussed from the perspectives of both mathematical modeling and planning algorithms for UAVs.

2.1. Basic Classification of UMP

UMP can be divided into mission assignment, trajectory planning, and trajectory replanning according to the execution aspects [9]. The mission assignment stage focuses on the reasonable assignment of different missions to multiple UAVs, with the goal of optimizing the efficiency of mission execution and resource utilization. A UAV can dynamically adjust a UAV mission assignment scheme through intelligent algorithms and data analysis according to the nature of the mission, the degree of urgency, and the demand for resources. Trajectory planning plans optimal trajectories for UAVs to ensure the successful completion of a mission. Obstacles and dangerous areas must be avoided during the planning process, the core of which lies in the use of a Geographic Information System (GIS), sensor data, and advanced trajectory optimization algorithms to solve safe and efficient flight trajectories. Trajectory replanning is a key technology used to cope with unexpected situations during UMP execution, ensuring mission flexibility and safety by adjusting a UAV’s flight trajectory in real time. This process involves rapid responses and the analysis of real-time environmental data, such as weather changes, the appearance of obstacles, or adjustments to mission requirements. This class division method not only helps to systematically study the various execution aspects of UMP but also promotes the development and application of related technologies. By continuously improving mission assignment, trajectory planning, and trajectory replanning technologies, UMP systems can meet the needs of different application scenarios and enable UAVs to have higher autonomy and reliability when facing various complex environments [10,11].

UMP can be classified as offline or online based on its mode of operation [12]. Offline planning is usually performed prior to mission execution with pre-collected environmental data, identified mission requirements, and comprehensive mission assignment and trajectory planning using optimization algorithms and simulation techniques, which can provide detailed mission scenarios and trajectory coordinates to ensure optimal UMP performance in known environments [13]. However, offline planning is less flexible and is not able to cope with sudden environmental changes or dynamic constraints during mission execution. An online planning system, on the other hand, obtains real-time environmental sensing and mission status data during mission execution and adjusts a UAV’s mission assignment and flight trajectory in real time through dynamic planning and real-time optimization algorithms, such as online learning, local search, and reinforcement learning. The advantage of online planning systems is that they can flexibly respond to dynamically changing environments and unexpected situations to ensure the reliability and safety of task execution. This classification method is applicable to different mission requirements and operating environments, providing different solutions for UMP. At the same time, it is also possible to design a hybrid planning system by integrating the advantages of offline and online planning systems. This type of system performs comprehensive offline planning before mission execution and makes real-time adjustments using online planning during execution, providing the optimal UMP solution [14].

UMP can be categorized as objective-first or constraint-first. Objective-first UMP focuses on prioritizing the optimization of a UAV’s objectives with the aim of improving the efficiency of mission planning, reducing energy consumption, minimizing flight time, maximizing the mission completion rate, etc. These optimization techniques usually use advanced planning algorithms such as genetic algorithms, particle swarm optimization, and ant colony algorithms to solve for the optimal solutions. Constraint prioritization focuses on constraint handling techniques for UAVs, concentrating on complex constraints in mission planning such as flight altitude limits, obstacle avoidance requirements, communication coverage, and energy constraints. Commonly used constraint handling techniques include the penalty function method, the constraint dominance relation, and the feasibility-first method [15,16,17]. The penalty function method deals with constraint violation by adding penalty terms to the objective function, the constraint dominance relation compares the advantages and disadvantages of different solutions based on the satisfaction of constraints, and the feasibility-first method gives preference to solutions satisfying hard constraints and optimizes the soft constraints on this basis. Through this class division method, UMP research can be targeted to solve different practical problems and provide strong support for the efficient execution of complex missions, which not only promotes progress related to constrained multi-objective optimization problems but also facilitates the wide application of UAV technology in various fields.

2.2. UMP Applications in Different Fields

UMP involves knowledge from several disciplines, such as computer science, control theory, communication technology, and artificial intelligence [18,19,20], and with the rapid development of UAV technology and the continuous expansion of application scenarios, the application of UMP in various fields has become increasingly widespread. This section first introduces the different stages and execution processes of UMP, then explores the application of UMP in various areas.

Figure 1 illustrates the different execution stages of UMP, the execution process, and its specific applications in various fields. UMP can be divided into four main phases: preparation, planning, execution, and post-processing. The preparation stage mainly involves the definition of mission requirements, initialization, and self-testing of the UAV; these steps ensure that the mission requirements are clear and that the UMP system is able to function properly. The planning stage focuses on environmental awareness, cooperative communication, mission analysis, and optimization theory and uses advanced algorithms and optimization techniques to develop efficient and safe mission scenarios that meet specific optimization objectives and constraints. The execution phase involves mission implementation, real-time monitoring, and dynamic adjustment, which ensure that the UAV performs the mission as planned and can adjust the planning scheme in real time. The reprocessing stage involves data processing, result analysis, and report generation, which provide optimization recommendations for the UMP system through in-depth analysis of data from the execution process. Currently, UMP is used in a variety of fields: in the field of agriculture, UMP is used for precision agriculture and crop monitoring [21]; in the field of environmental monitoring, UMP is used to collect and analyze data in real time to evaluate environmental changes [22]; and in the field of logistics and distribution, UMP ensures that parcels are delivered to their destinations efficiently and accurately [23]. In addition, UMP plays a crucial role in areas such as search and rescue and infrastructure inspection [24,25]. The efficient execution process of UMP not only improves the efficiency and safety of the application field but also enhances the accuracy and resource utilization of the executed missions. In this section, the execution process of UMP is elaborated in detail, using the 3D map reconstruction technique in UMP as an example, as shown in Figure 2.

Figure 2 demonstrates the 3D map reconstruction technique in UMP. Urban reconstruction after a natural disaster such as a flood is carried out as follows:

• The preparation stage begins with a comprehensive assessment of the scope and severity of the impact of the disaster, including the collection of geographic information and data on the damage to buildings, roads, and infrastructure in the disaster area. Based on this information, specific missions for UAVs are defined, such as panoramic photography of the disaster area, detailed surveys of damaged buildings, assessments of road access conditions, inspections of critical infrastructure, and search and rescue missions. In addition, the type, number, and configuration of UAVs need to be determined to ensure that the various mission requirements can be met.
• In the planning stage, a UAV uses high-resolution cameras and sensors to sense the environment and collect a large amount of image information, which is transmitted to a ground control center or the cloud for processing through wireless communication technology. Then, image stitching and matching algorithms are used to preprocess the collected image data and build a 3D model of the disaster area. Next, a UAV mission assignment plan and a flight trajectory are developed to ensure that all critical areas are covered while avoiding obstacles and dangerous areas. The mission analysis includes the prioritization of missions, resource allocation, and time scheduling to optimize the UAV’s mission execution strategy.
• In the execution stage, the UAV carries out the actual operation in accordance with the planned mission assignment and flight trajectory, and real-time monitoring and adjustment of the UAV’s flight status and mission execution are carried out through the ground control station to ensure the smooth progression of the mission. At the same time, the real-time data transmission and processing system provides instant feedback on the situation, making it possible to respond quickly to emergencies and dynamically adjust the mission.
• In the reprocessing stage, the data collected by the UAV are processed and analyzed, which includes data collation, screening, cleaning, and storage, and high-precision maps of the disaster area are generated using image processing technology. Data analysis tools provide detailed assessments of the damage, reconstruction needs, and resource allocation in the disaster area, providing an accurate and reliable basis for decision makers.

The UMP implementation process stage can assist urban planners in redesigning urban layouts, road networks, and infrastructure layouts to improve the resilience of cities.

2.3. Limitations of UMP

UMP faces many limitations, including the complexity of heterogeneous UAV maneuvering performance, the diversity of multi-objective optimization requirements, the impacts of dynamic changes in real-time environments, and the stringent limitations of complex mission constraints [26,27]. These limitations make it extremely difficult to construct accurate mathematical models and design efficient optimization algorithms.

2.3.1. Complexity of Mathematical Models

The complexity of a mathematical model lies in the fact that UAV maneuvering performance and the planning environment place high demands on the mathematical model; for example, the maneuvering performances of UAVs make their flight dynamics highly nonlinear, and this nonlinear behavior is difficult to accurately describe using simple mathematical models, although it can reflect the flight characteristics and responses of UAVs in real time [28]. UAVs are affected by dynamic factors such as meteorological conditions and wind speed and direction during flight, and uncertainties in the planning environment sensing data (e.g., sensor errors and data delays) and the system’s own uncertainties (e.g., navigational errors and control noise) lead to the need for real-time adjustments and optimization of the UMP program, which increases the modeling difficulty [29]. Second, the motion of the UAV is controlled by multiple variables, such as attitude, velocity, position, and acceleration. There is a high degree of coupling between these variables, meaning that changing one variable affects multiple other variables, increasing the complexity of the modeling [30]. Finally, UAVs need to adjust their flight trajectories and attitudes in real time during flight, which puts high demands on the computational speed and accuracy of the mathematical model, which must be able to compute the optimal solution quickly to ensure a safe and efficient flight for the UAV.

2.3.2. Limitations of Planning Algorithms

The limitation of the UMP algorithm is that high-dimensional and multi-constraint optimization problems usually have complex search spaces, and the UAV planning system needs to deal with a large number of candidate solutions during the planning process, which leads to a drastic increase in the computation and memory requirements [31]. Meanwhile, when facing dynamically changing environments (e.g., sudden obstacles and real-time mission changes), the state-space and action-space data of UAVs are very large and continuous. Although UMP algorithms based on deep reinforcement learning perform well in handling continuous and high-dimensional data with high adaptability and real-time performance, their training process may require a large amount of computational resources and time [32]. Secondly, in practical applications, UAVs have limited computing power and energy, and complex algorithms struggle to perform efficient planning and real-time optimization when running on UAVs. Finally, the planning algorithms are highly dependent on high-quality environmental data and accurate UAV model data, and possible errors in the data in the real environment will affect the accuracy and reliability of the planning results. These limitations indicate that the existing UMP algorithms still need to be further improved in practical applications to enhance their efficiency, flexibility, and robustness to better meet complex mission requirements.

3. Description of UMP

This section first introduces the mathematical model of UMP and its main considerations, details the classification of UAV constraints, and classifies UAV constraints into deterministic constraints and uncertainty constraints. Then, the current classical algorithms used in UMP are summarized, classified, and briefly described.

3.1. Mathematical Modeling of UMP

UMP defines and optimizes UAV mission execution strategies and flight trajectories through precise mathematical descriptions [33]. These models typically include objective functions and constraints to meet specific mission requirements and environmental constraints. The objective function may involve minimizing flight time, reducing energy consumption, or maximizing mission coverage. Constraints incorporate aspects such as flight altitude limitations, obstacle avoidance, communication coverage, energy consumption, etc. Commonly used mathematical modeling methods include linear programming [34], nonlinear programming [35], integer programming [36], and dynamic programming [37]. Accurate optimization models can be built using these methods to ensure efficient and safe operation of UAVs in complex environments. Figure 3 shows the factors affecting the accurate mathematical modeling of UMP.

Environmental perception is crucial for UMP [38]. Weather constraints, geographic constraints, and communication constraints directly affect UAV flight safety and mission execution efficiency. Bad weather such as strong winds and precipitation may lead to unstable flight, and UAVs will not take off for mission execution if the weather conditions are not conducive to flight. At the same time, complex terrain and obstacles increase flight difficulty, and insufficient communication signal coverage and interference affect communication and data transmission with the ground control center. Therefore, when planning UAV missions, the impact of environmental perception on UMP needs to be considered comprehensively to ensure smooth mission execution.

UAV dynamics and performance constraints directly affect the UMP program and its execution. A UAV’s dynamics include its flight performance, maneuverability, and flight stability [39]. These characteristics determine parameters such as a UAV’s speed, flight altitude, and fastest flight time when it is performing its mission. In addition, the performance constraints of a UAV, such as its load capacity, battery life, and sensor performance, also have significant impacts on UMP. Decision makers need to take these factors into account to determine the optimal flight trajectory, flight altitude, and flight speed to maximize the efficiency and success of mission execution.

The determination of the mission type, mission urgency, and planning time also has a significant impact on UMP [40]. Different types of missions (e.g., monitoring, search and rescue, delivery, etc.) have different models and execution modes for UAVs and thus require corresponding mission plans for different planning scenarios. The urgency of a mission directly affects its priority and execution schedule; urgent missions may require immediate deployment of UAVs, while non-urgent missions can be scheduled over a longer timeframe. In addition, sufficient planning time allows decision makers to more fully consider the various factors of a mission and develop a more reasonable and effective mission plan, whereas tight planning times may lead to imperfect and insufficient mission plans, increasing the risk and uncertainty of mission execution [41,42].

In general, the mathematical model of UMP is usually regarded as an optimal control problem, and the mathematical expression of an optimal control problem usually involves an objective function (performance index) and constraints (including dynamics constraints and control constraints). Together, these elements define a control system that needs to be optimized. The following is a general mathematical expression for the objective function of an optimal control problem [43,44,45], which is usually an integral form representing some performance metric that needs to be minimized or maximized:

$$J={\displaystyle {\int }_{t_0}^{t_f}L(x(t),u(t),t)}dt+\Phi (x(t_f),t_f)$$

(1)

where $J$ denotes the performance metric or objective function to be minimized (or maximized). $t_0$ and $t_f$ denote the initial and termination times, respectively. $x(t)$ and $u(t)$ denote the vector of state variables and the vector of control variables, respectively. $L(x(t),u(t),t)$ is a Lagrangian function representing the operating cost of the system at time t for $x(t)$ and $u(t)$. $\Phi (x(t_f),t_f)$ denotes the state cost at the termination time $t_f$.

Dynamic constraints are usually represented by a set of differential equations that describe the evolution of the system state $x(t)$ over time t:

$$\dot{x}(t)=f(x(t),u(t),t),x(t_0)=x_0$$

(2)

where $\dot{x}\left(t\right)$ is the derivative of the state $x\left(t\right)$ with respect to time t; $f(x(t),u(t),t)$ is the dynamical equation of the system; and $x(t_0)=x_0$ is the initial condition, which denotes the state of the system at the initial moment $t_0$.

Control constraints limit the range of values of the control variable $u(t)$:

$$u_{\min }(t)\le u(t)\le u_{\max }(t)$$

(3)

where $u_{\min }(t)$ and $u_{\max }(t)$ are the upper and lower bounds of the control variables, which may be constants or functions of time.

3.2. UMP Based on Traditional Optimization Algorithms

UMP based on traditional optimization algorithms uses different strategies and methods to find optimal or near-optimal planning solutions in a search space [46,47,48,49]. UMP based on traditional optimization algorithms is not only able to effectively cope with some types of mission requirements and environmental constraints but also ensures that UAVs are efficient and reliable during execution. We illustrate the application scope of UMP based on traditional optimization algorithms through the classification of UAV mission assignment, UAV trajectory planning, and UAV trajectory replanning, as shown in Figure 4.

The UAV mission assignment problem aims to address whether it is reasonable to optimize the mission and UAV resources [50]. Task assignment is characterized by the need to efficiently assign missions among multiple UAVs in order to minimize the total mission time or maximize the mission benefit, taking into account resource constraints and mission priorities. The generation of critical trajectory points is crucial in this process. These trajectory points need to take into account environment modeling, obstacle avoidance requirements and optimization of UAV trajectories to ensure that the UAVs are able to complete their respective missions safely and efficiently. This not only improves the success rate of mission execution, but also makes effective use of UAV resources for the purpose of overall optimization.

UAV mission planning algorithms can be classified into two categories: heuristic and meta-heuristic based algorithms as follows: Genetic algorithm (GA) [51], Ant colony optimization (ACO) [52], Particle swarm optimization (PSO) [53] Discrete particle swarm optimization [54], Imperialist competitive algorithm [55], Adaptive genetic algorithm (AGA) [56]. Another class of algorithms is based on co-operation and distribution as follows: Cooperative co-evolutionary algorithm (CCEA) [57], Distributed task allocation algorithm (DTAA) [58], Ant colony optimization with distributed agents (ACO-DA) [59].

The UAV trajectory planning problem aims to plan the optimal trajectory of a UAV from the start point to the end point. Trajectory planning is characterized by the need to avoid obstacles and meet flight performance constraints while ensuring the shortest or safest path. Trajectory optimization performs an important role in this process by fine-tuning the initially planned trajectory through optimization algorithms in order to further improve the efficiency and safety of the trajectory. However, the methods of trajectory optimization in this category usually show excellent performance in solving UAV trajectory planning in static environments.

UAV trajectory planning algorithms include three categories, one is based on graph search algorithms, specifically: A* search algorithm [60,61], D* search algorithm [62,63], D* lite algorithm [64,65], Lifelong planning A (LPA) [66], Hybrid algorithm [67]. A class of sampling-based algorithms, specifically include: Rapidly exploring random tree (RRT) [68], RRT* algorithm [69,70], Hybrid RRT-PSO algorithm [71]. Another category is learning-based algorithms, specifically: Deep reinforcement learning (DRL) [72], Deep Q-network [73].

The UAV trajectory replanning problem aims to adjust the flight trajectory of a UAV in real time in a dynamic environment. Trajectory replanning is characterized by the need to respond in real time to changes in the environment or changes in the mission to ensure that the UAV is able to update its trajectory in real time during flight to avoid new obstacles or respond to new mission commands with a high degree of flexibility and real-time performance. In dynamic environments, trajectory optimization is still very important to ensure that the UAV is able to respond to unexpected situations and environmental changes with the best trajectory by continuously fine-tuning the local trajectory. This type of trajectory optimization not only provides refined adjustments to the initial trajectory, but also continuously optimizes it during the replanning process, enabling the UAV to perform efficient and safe flights in the face of complex dynamic environments.

UAV trajectory replanning algorithms mainly include three categories: one is based on graph search algorithms, specifically: Dynamic A (D) [74,75], D lite algorithm [76,77], D* lite algorithm [78], Anytime dynamic A (AD) [79], Fast replanning algorithm (FRA) [80]. One class of algorithms is based on incremental planning, specifically, Incremental path planning [81,82], Lifelong planning A (LPA) [83]. Another category is learning-based algorithms, specifically: Deep learning-based replanning algorithm [84].

Traditional optimization algorithms have many advantages, such as fast convergence, ease of implementation, and fewer parameters and implementation steps, and a large number of well-established tools and libraries (e.g., MATLAB, SciPy, Gurobi, etc.) are already available to be directly invoked. However, UMP (UAV mission planning) currently involves multiple conflicting optimization objectives. Conventional optimization algorithms usually deal with this by weighting multiple optimization objectives in a composite objective function, which may result in the absence of some important objective information. In addition, if UMP involves multiple nonlinear constraints or multiple coupled constraints that result in a feasible domain space with a complex shape, the convergence of traditional optimization algorithms is slower and the algorithms are less robust. When dealing with complex and multi-peaked optimization problems, traditional optimization algorithms usually focus on only one solution in a single search process, and they do not have a diversity mechanism. Therefore, they are prone to fall into a local optimum.

4. UMP Based on CMOEAs

This section first introduces a UMP flowchart, lists the classic CMOEA literature, and describes the core ideas of these algorithms. Next, the commonly used constraint handling techniques in CMOEAs are described in detail. Finally, a framework for CMOEAs based on constraint handling techniques is explored.

4.1. Flowchart of UMP

Figure 5 is based on the differential evolution (DE) algorithm [85], and the evolutionary process is divided into four modules: the initiation module, the main loop module of the algorithm, the termination module, and the output module. In the initiation module, first environmental information is obtained to determine the UAV start point and the mission. Next, the objective function and constraints are constructed, and the estimated voyage cost matrix is calculated. Then, the population (Pop) is initialized; the iteration number (Gen), variation rate (Rm), and crossover rate (Rc) are determined; and the fitness value is calculated for each individual. The main loop module of the algorithm generates the sub-generation population using the variation operator, crossover operator, and selection operator and re-evaluates the fitness value of each individual in the population after each iteration. The termination module determines whether a predefined termination condition (e.g., reaching the maximum number of iterations or converging to some optimal solution) has been reached. If the termination condition is reached, the output module is entered. Otherwise, the main loop module continues. The output module outputs the UMP solution that satisfies the conditions. However, using only differential evolutionary algorithms may lead to the following problems: (1) a lack of feasible solutions, as the algorithm may generate a large number of solutions that do not satisfy the actual constraints; (2) low-quality solutions, as the generated solutions may not be able to balance multiple optimization objectives; and (3) convergence, as the algorithm may have difficulty efficiently converging to the optimal solution in the presence of a large number of constraints.

In order to overcome the above mentioned problems, constraint handling techniques are introduced in the main loop stage of the algorithm which include penalty function method [86], constraint domination method [87], multi-objective optimization method [88], learning-based method [89] and hybrid method [90,91]. In optimization algorithms, a series of methods and strategies are used to ensure that the generated solutions satisfy specific constraints (e.g., physical, environmental, and performance limitations, etc.) [92,93,94], and constraint processing techniques guide the algorithms in generating feasible and high-quality solutions by introducing constraints during the optimization process and eliminating or correcting solutions that do not satisfy the constraints. The advantages of multi-objective evolutionary algorithms based on constraint handling techniques are as follows:

• Guaranteed solution feasibility: In multi-objective optimization, constraint handling techniques ensure that each solution is optimized while satisfying all constraints. This means that all generated solutions are within the feasible domain, thus avoiding the generation of solutions that do not satisfy the constraints.
• Enhanced solution quality and diversity: multi-objective optimization requires finding a balance between different objectives, and constraint handling techniques help to generate a collection of solutions with a high degree of diversity, allowing the final solution to balance multiple optimization objectives.
• Accelerated convergence: constraint handling techniques allow algorithms to focus on the feasible domain faster by eliminating infeasible solutions, greatly reducing invalid searches and accelerating convergence.
• Enhanced robustness and adaptability of algorithms: In dynamically changing environments, UMP needs to adapt to different mission requirements and constraint changes. Constraint handling techniques increase the robustness and adaptability of an algorithm. Even when faced with new task insertions or changes in the environment, the constraint handling technique ensures that the solution set is able to adjust and satisfy the new constraints in a timely manner.

Table 1 describes the classical CMOEAs and some of the commonly used CMOEAs and details the core ideas of these algorithms.

4.2. Constraint Handling Techniques

Currently, common approaches to constraint handling include penalty function methods, constraint domination methods, multi-objective optimization methods, learning-based methods, and hybrid methods [103,104,105], which play different roles. Penalty function methods deal with constraints by adding a penalty term to the objective function for violating the constraints to ensure that the solution set satisfies the constraints [106]; constraint domination methods improve the efficiency of the algorithms by comparing the feasibility of the solutions with the dominance relationship and prioritizing feasible solutions [107]; multi-objective optimization methods aim to optimize multiple conflicting objectives at the same time by balancing more than one optimization objective [108]; learning-based methods use machine learning techniques to predict and improve the planning process, which improves the robustness of the algorithm [109]; and hybrid methods combine multiple optimization techniques [110], which integrates the advantages of different constraint handling techniques to improve the overall performance and solving efficiency of the algorithm. The specific advantages and disadvantages of different constraint handling techniques are shown in Table 2.

4.3. A Framework for CMOEAs Based on Constraint Handling Techniques

In addition to the common constraint handling techniques described in Section 4.2, a CMOEA framework based on dual populations, dual stages, multiple populations, and multiple stages has also shown better performance when dealing with constrained multi-objective optimization problems in recent years [128,129,130]. Unlike constraint handling techniques, dual-population, dual-stage, multi-population, and multi-stage techniques improve global search capability and local optimization accuracy through the parallel computation of populations and the stage processing strategy, and their specific advantages and disadvantages are shown in Table 3.

5. Modifications to CMOEAs for UMP

In this section, we first classify the information contained in the individuals of the population. Before planning, we need to set the information for the individuals in the population, which contains key information such as the sequence of the UAVs, the sequence of the mission points, the cost of the voyage, the constraints, etc. The advantages and disadvantages of the individual setups will directly affect the degree of coverage of the CMOEAs in the search space and the efficiency of the execution [139]. Then, the improvement strategy in the UMP algorithm can improve the flexibility and adaptability of the algorithm. A reasonable improvement strategy is one of the key factors to ensure the stability of the algorithm. Finally, after UMP is completed, it is crucial to evaluate the effectiveness of the execution scheme, which can be carried out based on the performance indices of the UAV and the algorithm. After the comprehensive evaluation, the effectiveness of the information contained in different individuals and the improvement operators can be verified, and the individual information and optimization of the improvement operators can be updated.

5.1. Individual Expressions of Populations for UMP Based on CMOEAs

In CMOEA-based UMP, the form of representation of individuals in a population is crucial, and each solution is usually represented via encoding, which can be in the form of real-number encoding, binary encoding, or trajectory encoding, depending on the characteristics of the problem and the optimization objectives [140,141]. For example, in trajectory planning, an individual can be represented as an ordered sequence of nodes, where each node corresponds to a key point on the UAV flight trajectory. Each individual contains trajectory information as well as relevant parameters such as the order of task execution, flight altitude, and speed.

Figure 6 presents the individual expressions of UMP populations based on CMOEAs. Currently, the individual expressions of a population are usually classified into the following categories: UAV and mission sequences, trajectory points and flight information, environmental information, and constraint processing information.

• UAV and mission sequences constitute individual information, which can directly affect the assignment and scheduling of missions. This method can effectively balance the mission load of a UAV, reduce the conflict and waiting time between missions, and improve the efficiency of mission execution. However, this representation is relatively simple, and the UMP scheme is prone to violating constraints when faced with complex missions.
• Based on individual information contained in trajectory points and flight information, this method pays more attention to the performance metrics of UAVs, which can improve the accuracy of UMP and ensure safety and reliability when executing a mission. However, this method requires real-time monitoring and updating of the UAV status, which increases the complexity of the UMP system.
• Based on individual information obtained via environmental sensing, this method can help a UAV make more accurate decisions based on real-time data and help identify and avoid potential risks, thereby improving flight safety. However, the acquisition and processing of environmental information is complex and requires a large number of sensors and algorithms to analyze the data in real time, leading to increased demand for computational resources.
• Based on individual information obtained via constraint processing, this method is able to cope with different types of constraints and enhance the feasibility of the solution, thus generating a more reliable mission planning solution. However, conflicts may arise between different constraints, and trade-offs and adjustments are required when dealing with these conflicts, which increases the complexity of the algorithm in space and time.

5.2. Classification of UMP Improvement Strategies Based on CMOEAs

In addition to changing the forms of individual populations, some researchers and scholars have proposed different improvement strategies for the UMP algorithm [142,143]. The population collaboration modes can be divided into the adaptive population size strategy, the multiple independent populations parallel optimization strategy, and the multiple-population co-evolution strategy. The detailed improvement strategies are shown in Table 4:

• The adaptive population size strategy improves the performance of the algorithm by dynamically adjusting the size of the population during the optimization process. With the current number of iterations, the population size is automatically increased or decreased to balance explorability and convergence. The solution space is extensively explored by larger populations in the early stage and quickly converged by smaller populations in the later stage. This method improves the search efficiency and solution quality of the algorithm.
• The multiple independent populations parallel optimization strategy optimizes multiple independent populations in parallel, each of which searches independently in a different region of the solution space. This method increases the diversity of the solutions and prevents the algorithm from falling into local optimal solutions, and parallel computation can significantly improve computational efficiency. Meanwhile, multiple independent populations can explore different regions of the solution space, which improves the probability of finding a globally optimal solution.
• The multiple-population co-evolution strategy improves the performance of the algorithm through information interaction and collaboration between different populations during the optimization process. Optimal individuals or some individuals can be exchanged between populations to promote diversity of understanding and information sharing. Through collaboration between populations, the global search ability of the algorithm is enhanced, overcoming the fact that a single population can easily fall into a local optimum and improving the global optimization effect.

The improvement operator strategies of the algorithm can be divided into the adaptive crossover and mutation strategy and the hybrid algorithm strategy as follows:

• The adaptive crossover and mutation strategy adapts to different stages by dynamically adjusting the probabilities of the crossover and mutation operators during the optimization process. The mutation probability is increased in the exploration phase and the crossover probability is increased in the exploitation phase to improve the search efficiency of the algorithm, while the convergence speed and global search capability of the algorithm are improved by balancing the exploration and exploitation processes using an adaptive adjustment strategy.
• By fusing the advantages of different optimization algorithms, the hybrid algorithm strategy enhances the robustness and global search ability of the algorithm and adapts to more complex multi-objective optimization problems.

The constraint processing techniques can be divided into the dynamic constraint processing strategy and the hybrid constraint processing strategy as follows:

• In the dynamic constraint processing strategy, the constraint processing method is dynamically adjusted during the optimization process according to the characteristics of the current solution and the changes in the constraints. By dynamically adjusting the constraint processing strategy, the flexibility and adaptability of the algorithm in dealing with complex constraints are enhanced and the feasibility of the algorithm is improved.
• The hybrid constraint processing strategy selects or combines different constraint processing techniques according to the actual situation during the optimization process in order to improve the effectiveness of constraint processing. By combining multiple constraint processing techniques, the algorithm’s ability to deal with complex constraints is improved to ensure the feasibility and optimality of the solution.

5.3. Performance Evaluation Metrics for CMOEA-Based UMP

A comprehensive evaluation of a solution is needed after UMP has been carried out, and this section focuses on the importance of algorithm performance for UMP from the perspectives of both UAV and algorithm performance metrics. Through these performance evaluation metrics, researchers and scholars are able to comprehensively understand and compare the performances of different algorithms in order to optimize the algorithms of UMP.

Figure 7 presents the performance evaluation metrics of CMOEA-based UMP. The performance metrics of the UAVs and algorithms can be used together to evaluate the effectiveness of UMP. The performance metrics of the UAVs include the shortest range, shortest flight time, lowest energy consumption, mission execution success rate, response time, and feasibility of the planning system [154,155]. The performance metrics of the algorithms include the diversity of solution sets, convergence, constraint handling efficiency, and algorithm scalability [156,157]. The diversity of the solution set measures the degree of diversity among the solutions in the set of Pareto optimal solutions, and a higher diversity indicates that the algorithm is able to find more non-dominated solutions, thus covering more solution space [158,159]. The convergence of the solution set measures the degree of approximation of the solution set to the true Pareto frontier. The higher the convergence, the closer the obtained solution is to the optimal solution, reflecting the algorithm’s ability to approximate the optimal solution during the solution process. Constraint handling efficiency refers to the ability of the algorithm to effectively handle constraints when solving multi-objective optimization problems. Efficient constraint handling not only improves the search efficiency and optimization effect of the algorithm but also ensures that high-quality feasible solutions can be generated in a complex mission environment. The constraint handling efficiency can be expressed by calculating the proportion of feasible solutions. The scalability of the algorithm refers to whether the algorithm is able to replace different algorithmic components through modular design to significantly improve the performance and efficiency of the UMP system when dealing with UMP problems of a larger scale. Therefore, the performance metrics of the UAVs and algorithms can comprehensively reflect the UMP performance.

6. Discussion

In this section, we first introduce the method of searching for CMOEA-based UMP research, which was obtained by entering keywords into a data platform and filtering the relevant literature based on the year of publication and the type of publication. Then, we counted the number of studies on CMOEAs and the number of UMP studies based on CMOEAs in the last 20 years. Next, we counted the percentages of classical algorithms and CMOEAs in UMP research. Finally, we present the specific constraints and the proportions of optimization objectives in CMOEA-based UMP.

6.1. Collection of Statistical Data from the Literature

Figure 8 presents the scheme of this review for searching for UMP-related research based on CMOEAs. First, relevant keywords and key information (e.g., UAV mission planning, UAV scheduling, constraint handling techniques, etc.) were entered into digital libraries or academic databases (e.g., IEEE Xplore, SpringerLink, ScienceDirect, etc.). Then, the UMP literature based on CMOEAs was further filtered by setting restrictions on the timeframe and the publication categories (e.g., journals, conference papers, reviews, etc.). Using this method, we could usually retrieve the literature related to UMP cooperative mission planning, UMP path planning, UMP replanning, and so on. Ultimately, we needed to precisely find research that was relevant and representative of UMP and CMOEAs to ensure the comprehensiveness and accuracy of this study.

6.2. Research Published on CMOEAs and CMOEA-Based UMP

In recent years, research on CMOEAs and CMOEA-based UMP has involved various aspects such as the theoretical improvement of algorithms, practical applications, and performance evaluation. Researchers have proposed various improved CMOEAs to enhance the effectiveness of UMP under complex constraints and verified their effectiveness in UMP through a large number of experiments. Figure 9 presents the numbers of CMOEA publications and CMOEA-based UMP publications in the literature from 2004 to 2024.

Figure 9 summarizes the proportions of CMOEAs and the numbers of CMOEA-based UMP publications in journals, etc., from 2004 to 2024. In Figure 9a, the variation in the total number of journal papers, conferences, and patents published on CMOEAs over the last 20 years is shown. It can be observed that the number of published CMOEAs has been growing steadily. In Figure 9b, it can be seen that journal papers have had the largest share, while patents and scientific and technological achievements have had the smallest number of publications. Figure 9c demonstrates the total numbers of UMP journal papers, conference papers, and patents involving CMOEA-based UMP over the last 20 years, which reflect the specific application of CMOEAs in UMP, and it can be seen that CMOEA-based UMP research results have been increasing in recent years. Figure 9d shows the proportions of CMOEA-based UMP literature in the total literature over the last 20 years, from which it can be seen that journal papers still have the largest proportion. Patents and scientific and technological achievements also account for large proportions. Therefore, the results of UMP based on CMOEAs are significant and tend to be converted into practical patents and scientific and technological achievements.

6.3. Proportions of Traditional Optimization Algorithms and CMOEAs in UMP

Due to the rapid development of machine learning and multiple intelligent algorithms, static UMP is rapidly undergoing a shift to dynamic UMP. In order to clearly show the change in the share of each algorithm, we describe the years 2004–2024 based on the first 10 years (2004–2013) and the last 10 years (2014–2024).

Figure 10a presents the proportions of each UMP algorithm from 2004 to 2013. Due to the high number of static path planning and UMP scenarios with fixed constraints studied in this time period, UMP based on the mathematical planning method was dominant. This method is suitable for solving exact optimization problems, and performs especially well on the trajectory planning problem. Comparatively speaking, UMP based on the graph theory method has obvious advantages in trajectory planning and obstacle avoidance, especially when topology and trajectory optimization need to be taken into account, and this method is able to effectively deal with the influence of moving obstacles on UAV trajectory planning. Secondly, UMP based on the sampling method and graph theory method accounted for comparable proportions. This was mainly due to the good performance of the sampling method in continuous space. Subsequently, there has been rapid development of UMP based on machine learning and reinforcement learning techniques, which are able to learn from data and optimize the mission planning process and perform especially well when facing complex and dynamic UMP environments. Finally, due to the limitations of computer arithmetic and the immaturity of CMOEAs, UMP based on CMOEAs accounted for a relatively small proportion of UMP during this period.

Figure 10b presents the proportions of each UMP algorithm from 2014 to 2024. Firstly, the emergence of UMP for dynamic scenarios has led to a decrease in the share of mathematical planning methods. However, mathematical planning still maintains a certain proportion in some specific fields, such as air traffic control and logistics and distribution, which indicates that mathematical planning methods still play an important role in solving precise optimization problems. Secondly, graph theory-based UMP has gradually evolved from traditional mission assignment and trajectory planning towards more complex application fields, including UAV networks, communication switching, and securing UAV communications. Subsequently, optimization problems in continuous space have gradually occupied a major position compared to discrete space, so graph theory-based UMP still occupies a large proportion. With the rapid development of artificial intelligence and machine learning technologies, the application of learning strategy-based methods, such as reinforcement learning and deep learning, in UMP has gradually increased. Finally, with the significant increase in computer arithmetic power and the emergence of more mature CMOEAs, CMOEAs have become an effective solution for complex UMP problems, and thus the proportion of UMP based on CMOEAs has increased significantly.

These trends suggest that research and applications in the field of UMP are no longer limited to exact optimization problems and are moving towards more diverse, intelligent, and adaptable optimization problems.

6.4. Constraints and Optimization Objectives of UMP Based on CMOEAs

Figure 11 illustrates the weighting of constraints and optimization objectives for the mathematical model of UMP for the period from 2004 to 2024. As can be seen in Figure 11a, the constraints considered in the UMP literature included terrain constraints, UAV dynamics constraints, communication and control constraints, UAV performance constraints, and obstacle constraints. Terrain constraints ensure that a UAV flight trajectory avoids terrain obstacles. UAV dynamics constraints consider the flight dynamics of a UAV to ensure that it remains stable during flight. Communication and control constraints ensure that the communication and control signals between a UAV and the ground control station or other UAVs are smooth. UAV performance constraints focus on the flight capability of the UAV itself. Obstacle constraints consider obstacles in the planning environment to ensure safe UAV flight. These constraints accounted for almost equal proportions of the literature, indicating that all types of constraints were valued in UMP.

As can be seen in Figure 11b, the optimization objectives considered for UMP included the minimum flight distance, minimum flight time, maximum mission benefit, minimum mission risk, and minimum energy consumption. The minimum flight distance not only reduces energy consumption but also improves the efficiency of mission accomplishment; the minimum flight time ensures that the mission can be accomplished in the shortest possible time; the maximum mission benefit focuses on the economic benefits and outcomes of the mission; the minimum mission risk considers potential risks and threats during mission execution; and the minimum energy consumption aims to prolong the endurance of the UAV and the time of mission execution. Among them, the shortest flight distance is the focus of current research, as it means that a UAV can reach a designated location in the shortest time and even return to load in time for the next mission, thus improving the overall mission effectiveness.

In summary, both the constraints and optimization objectives in UMP have been widely studied and applied in the literature, and both have important implications.

7. Future Research Directions and Conclusions

7.1. Future Research Directions

7.1.1. Integration with MCDA

The integration of CMOEA-based UMP with Multi-Criteria Decision Analysis (MCDA) methods remains one of the frontiers of current research. ELECTRE (Elimination et choix traduisant la realité) [160] and PROMETHEE (Preference ranking organization method for enrichment evaluations) [161] are two important MCDA methods that provide systematic and scientific decision support in the face of complex, multi-objective mission planning. For example, in UMP, the ELECTRE method helps decision makers to eliminate undesirable choices among multiple alternatives and find the optimal one by constructing transcendental relationships and evaluation matrices. And the PROMETHEE method provides a detailed basis for ranking and selection by comparing the strength of preferences between options, considering factors such as flight time, fuel consumption, mission priority and risk. By introducing these MCDA methods, UMP research can better cope with complex environments with multiple objectives and constraints, thus improving the efficiency and safety of mission execution. The integration of these methods will help develop a more intelligent and optimized UMP system, enhance UAV capabilities in mission assignment, trajectory optimization and risk assessment, and lay the foundation for the efficient deployment of future UAVs in various complex application scenarios. This not only promotes the development of UAV technology, but also provides new ideas and tools for the solution of CMOEAs.

7.1.2. Integration with 6G Networks

The integration of CMOEA-based UMP with sixth-generation mobile communication networks (6G) is a cutting-edge technology currently being researched. By combining CMOEAs and 6G networks, the efficiency and performance of UMP can be significantly improved. However, this integration faces a number of technical difficulties, including long communication delays, unstable data rates, and strict communication constraints. The details are as follows: First, when UAVs perform real-time missions, their high maneuverability and 6G network topology dynamics lead to UAV communication delays, which are due to the frequent switching of base station connections during the high-speed movements of the UAVs, thus increasing the network load and delay. Second, high-resolution, real-time video transmission requires a large amount of bandwidth and high data rates, and continuous data transmission may trigger network congestion. Finally, edge computing performs data processing through on-board devices, which reduces the need for continuous communication with a central server and thus shortens the response time. Therefore, UMP must consider communication constraints.

7.1.3. Integration with Area Blockchain Technology

The integration of CMOEA-based UMP with blockchain technology is also a current research hotspot. By combining CMOEAs and blockchain technology, the data security and integrity of airborne UAVs can be ensured, and this integration can help to enhance supply chain cooperation. However, it also faces many challenges, including data security, privacy protection, and scalability. The details are as follows: First, blockchain technology needs to handle a large amount of data in UMP, including information such as flight trajectories, mission execution statuses, and environmental monitoring, which require a high degree of security, and although blockchain technology can provide a certain degree of security, it also increases the complexity of data management. To ensure the security and reliability of UMP data, the constraints of data transmission and storage must be considered in the design. Secondly, UMP itself is a complex multi-constraint, multi-objective optimization problem, and the addition of blockchain technology requires additional consideration of issues such as data synchronization, which increases the complexity of the system design significantly. The constraints must be considered to balance these issues in multi-objective optimization while ensuring the proper functioning of the UMP system. Finally, the sizes of UAVs are likely to keep increasing, and UMP system design needs to be optimized under scalability constraints to ensure that it can handle increases in the amount of data and the number of nodes.

7.1.4. Integration with Quantum Computing

The integration of CMOEA-based UMP with quantum computing is also a current research frontier. By combining the powerful computational capability of quantum computing, the optimization of UMP can be significantly improved. The details are as follows: Firstly, the powerful computational ability of quantum computing can significantly improve the efficiency of CMOEAs, but quantum algorithms need to adapt to the constraint processing mechanisms of classical evolutionary algorithms. Deep modifications of the quantum computing framework are required to adapt to these constraint processing techniques. Second, quantum computing requires efficient encoding and quantum state representation of UMP constraints when processing UMP, which not only increases the complexity of algorithm design but also increases the demand for computational resources due to the ultra-high dimensionality of quantum states. This makes it difficult to perform accurate constraint evaluation among quantum states. In addition, the non-determinism of quantum computation and quantum error correction pose serious challenges to the real-time performance of UMP. A UMP system needs to respond to environmental changes in real time, and the results of quantum computation have a probabilistic nature to a certain degree. Therefore, when designing quantum evolutionary algorithms, it is necessary to consider how to deal with constraints stably and efficiently under the uncertainty of quantum computation. Finally, the integration of quantum computing and CMOEAs also faces challenges in data transmission and processing, as UAVs need to exchange and process data frequently during their missions. Determining how to efficiently achieve data synchronization and constraint processing under the framework of quantum computing is a major technical challenge.

7.2. Conclusions

This paper has provided a detailed summary of UMP based on CMOEAs. First, this paper described the traditional UMP classification method and proposed a new classification method from the new perspective of whether UAVs prioritize objectives or constraints. Then, according to the execution flow of CMOEAs, the embedded modules of constraint handling techniques were clarified, the classification of constraint handling techniques was elaborated in detail, and the algorithmic framework for solving multi-objective optimization problems was described. Then, we quickly found suitable planning scenarios based on the method for determining the individual settings in a population and the improvement strategy in CMOEAs. At the same time, we proposed UAV performance metrics and algorithmic metrics to evaluate the algorithm’s performance. Finally, we provided a detailed summary of the publication of CMOEAs, the publication of research on UMP based on CMOEAs, and the weights of the constraints and optimization objectives used in the mathematical model of UMP for the period from 2004 to 2024.