Constrained Multi-Objective Optimization

## Abstract

Abstract Over the last decade, developments in Unmanned Aerial Vehicles (UAVs) has greatly increased, and they are being used in many fields including surveillance, crisis management or automated mission planning. This last field implies the search of plans for missions with multiple tasks, UAVs and Ground Control Stations (GCSs) ; and the optimization of several objectives, including makespan, fuel consumption or cost, among others. In this work, this problem has been solved using a Multi-Objective Evolutionary Algorithm (MOEA) combined with a Constraint Satisfaction Problem (CSP) model, which is used in the fitness function of the algorithm. The algorithm has been tested on several missions of increasing complexity, and the computational complexity of the different element considered in the missions has been studied.

###### Keywords:

## 1 Introduction

The potential applications of Unmanned Aircraft System (UAS) are varied, including infrastructure inspection , surveillance of coast borders  and road traffic , disaster and crisis management , and agriculture or forestry , among others. Therefore, over the past 20 years, a large number of UAS research works have been carried out applying varied techniques and algorithms .

The systems developed to increase the autonomous capabilities of a UAS can be mostly organized into three main categories: Guidance, Navigation, and Control (GNC). The Guidance System (GS) is in charge of the planning and decision-making functions to achieve assigned missions or goals. Mission planning is the process of generating tactical goals, a commanding structure, coordination, and timing for a team of Unmanned Aerial Vehicles (UAVs). The mission plans can be generated either in advance or in real time, manually by operators or by onboard software systems, and in either centralized or distributed ways.

Currently, UAVs are operated remotely by human operators from Ground Control Stations (GCSs), using rudimentary guidance systems, such as following preplanned or manually provided waypoints. There is an active research topic that tries to outperform guidance systems to achieve more complex tasks and missions, in order to provide a new degree of high-level autonomy to guidance systems including mission planning and decision-making capabilities.

In this work, the Mission Planning Problem (MPP) is modelled as a Constraint Satisfaction Problem (CSP) and solved using a Multi-Objective Evolutionary Algorithm (MOEA) optimizing several variables of the problem, such as the makespan, the cost of the mission or the risk.

In the following section a state of the art on mission planning, CSPs and MOEAs is presented. Section [3](#S3) presents the MPP aimed to solve and its modelization as a CSP. Section [4](#S4) presents the MOEA designed to solve the MPP. Then, in section [5](#S5), a set of experiments is performed to prove the efficiency of the MOEA and show complexity of the problem as the number of variables and constraints considered increase. Finally, section [6](#S6) brings some conclusions and propose future works with this approach.

## 2 State of the art

In this section, an overview of the state of the art of the problem and techniques used in this paper is presented. First, a general introduction to the mission planning problem for UAVs and some research studies on this topic is presented. After this, an overview of CSPs is presented, showing the different methods used in the literature to solve them. Finally, a description of Multi-Objective Optimization Problems (MOPs) and the use of MOEAs to solve them is carried out.

### 2.1 Mission Planning

Automated planning and scheduling has been an area of research in artificial intelligence for over four decades, and its application in UAV missions is a known problem. A mission consists of as a set of goals that must be achieved by performing some tasks with a group of resources (the sensors possessed by the UAVs) over a period of time. The whole problem can be summed up in finding the correct schedule of resource-task assignments that satisfies the proposed constraints. In addition, when several UAVs are involved, they usually require several GCSs for controlling all the vehicles involved. This generates a new Multi-GCS approach that makes the problem even harder to solve.

One concept that relates with mission planning and that is sometimes confused with it, is path planning. In path planning, the vehicles are assigned a set a waypoints which compose their route, i.e. it is similar to Travelling Salesman Problem (TSP) or Vehicle Routing Problem (VRP). On the other hand, mission planning is more related with task and resource allocation, being more similar with scheduling problems. Anyway, once mission planning is performed, path planning must also be performed on each vehicle (with their assignments) to create the final route.

The MPP is a big challenge in actual NP-hard optimization problems. Classic planners based on graph search or logic are not suitable for this problem due to the high computational cost that the algorithms need to solve these missions. For this reason, there has been some research in the last decade proposing novel methods to solve this problem.

Sakamoto proposed a linear programming formulation of the MPP as an extension of the VRP with time windows for the tasks, and solved it using robust optimization. Evers et al. presented a similar approach with robust optimization, but they extended from the orienteering problem.

Karaman et al. extended the VRP with lineal temporal logic, formulated it using network flows and solved it using Mixed-Integer Linear Programming (MILP). Fabiani et al. modelled the problem using Markov Decision Process (MDP) and solve it with dynamic programming algorithms. Another approach by Kvarnstrom et al. combines ideas from forward-chaining planning with partial-order planning, leading to a new hybrid Partial-Order Forward-Chaining (POFC) framework.

Other works focus on distributed approaches for solving mission planning of a swarm of UAVs, using the Belief–Desire–Intention (BDI) model , Dynamic Data Driven Applications Systems (DDDASs) , etc.

Finally, there are other approaches that formulate the MPP as a CSP , using constraint techniques to solve it. Moreover, some modern approaches use bio-inspired algorithms. These methods will be discussed in the following sections.

### 2.2 Constraint Satisfaction Problems

A CSP consists of a set of variables, each one with its own set of possible values or domain, and a set of constraints restricting the values that variables can simultaneously take. This formulation is quite appropriate for the MPP, where a set of assignments (variables) must be done while assuring some constraints given by the different components and capabilities of the UAVs involved.

CSPs are usually represented as graphs where the variables are the nodes and the constraints are the edges. There exists several methods to search the space of solutions of a CSP, including Backtracking (BT), Backjumping (BJ) or Forward Checking (FC), among others. Most methods have a propagation phase where the constraints of the problem are checked. These methods are usually combined with consistency techniques (domain consistency, arc consistency or path consistency) to modify the CSP and ensure its local consistency conditions.

When CSPs treat with time variables (time points, time intervals or durations), as with the MPP, these type of problems are usually called Temporal Constraint Satisfaction Problem (TCSP) . In these problems, the temporal constraints are characterized by the underlying set of Basic Temporal Relations (BTR). Depending on the nature of the time variables and the constraints used, BTR can be represented using different types of algebra, such as Point Algebra (PA), Interval Algebra (IA) or, the most known, Allen’s Interval Algebra , in which the BTR is composed of the relations presented in Table [1](#S2.T1).

**Table 1: Allen’s interval algebra**
| Relation | Illustration | Interpretation |
| --- | --- | --- |
| $T_{1}<T_{2}$ | $T_{1}$$T_{2}$ | $T_{1}$ takes place before $T_{2}$ |
| $T_{1}\;m\;T_{2}$ | $T_{1}$$T_{2}$ | $T_{1}$ meets $T_{2}$ |
| $T_{1}\;o\;T_{2}$ | $T_{1}$$T_{2}$ | $T_{1}$ overlaps $T_{2}$ |
| $T_{1}\;s\;T_{2}$ | $T_{1}$$T_{2}$ | $T_{1}$ starts $T_{2}$ |
| $T_{1}\;d\;T_{2}$ | $T_{1}$$T_{2}$ | $T_{1}$ during $T_{2}$ |
| $T_{1}\;f\;T_{2}$ | $T_{1}$$T_{2}$ | $T_{1}$ finishes $T_{2}$ |
| $T_{1}=T_{2}$ | $T_{1}$$T_{2}$ | $T_{1}$ is equal to $T_{2}$ |

Finally, many real-life applications aim to find a good solution, and not the complete space of possible solutions. For this purpose, the CSP incorporates an optimization function, becoming a Constraint Satisfaction Optimization Problem (CSOP). This optimization function maps every solution (complete labelling of variables) to a numerical value measuring the quality of the solution. The most widely used algorithm for finding optimal solutions is called Branch & Bound (B&B), which performs a depth first search pruning the sub-trees that exceed the bound of the best value so far. In the case of Multi-Objective Optimization, an extension of this method, known as Multi-Objective Branch & Bound (MOBB) can be used to find the non-dominated solutions of the problem. Other methods for solving CSOP include Russian doll search, Bucket elimination, Genetic algorithms and Swarm intelligence.

### 2.3 Evolutionary Algorithms and Multi-Objective Optimization

In the last decades, many bio-inspired algorithms have arisen to obtain fast solutions for optimization problems. These algorithms are included in some categories, where the most known are evolutionary algorithm, swarm intelligence and artificial immune systems. Evolutionary algorithms are population-based metaheuristic optimization algorithms inspired by biological evolution, where mechanism such as reproduction, mutation, recombination or selection are imitated. The most common type of evolutionary algorithms are Genetic Algorithms (GAs) , which are inspired by natural evolution and genetics. Other common methods are Evolution Strategy (ES), Differential Evolution (DE) and Genetic Programming (GP).

GAs have been successfully used in many optimization problems, demonstrating to be robust and capable of finding satisfactory solutions in highly multidimensional problems. These algorithms generate an initial population of individuals (or possible solutions), where each one has a chromosome representation, which is directly related with the variables of the problem. This population is evolved during a number of generations, where each generation reproduces, crosses, mutates and selects the best individuals of the population, which are evaluated using a fitness function.

Some works have dealed with the MPP using GAs, such as Tian et al. , where they solve a reconnaissance cooperative mission aiming to minimize the travel distance and time of the vehicles. In this approach, the chromosome representation of the GA consist of subsequences, where each one represent a reconnaissance target sequence for a UAV. Other approach by Geng et. al. proposed a graph based representation for a MPP constrained with flight prohibited zones and enemy radar sites.

Most real-life problems, including the MPP, aim to optimize several conflicting criteria at the same time. These MOPs have no single optimal solution that can be selected objectively; rather there is a set of solutions representing different performance trade-offs between the criteria. In these cases, algorithms usually focus on finding the Pareto Optimal Frontier (POF), i.e. the set of all non-dominated solutions of the problem. The goal of MOEAs is to find non-dominated objective vectors which are as close as possible to the POF (convergence) and evenly spread along the POF (diversity). Non-dominated Sorting Genetic Algorithm-II (NSGA-II) has been one of the most popular algorithms over the last decade in this field . This algorithm extends the common GA using non-dominated ranking for the convergence and crowding distance for the diversity of the solutions (see Figure [1](#S2.F1)). Other popular algorithms are Strength Pareto Evolutionary Algorithm 2 (SPEA2) , Multi-Objective Evolutionary Algorithm based on Decomposition (MOEA/D) and Non-dominated Sorting Genetic Algorithm-III (NSGA-III) .

Figure: Figure 1: NSGA-II overview of multiobjective strategies.
Refer to caption: /html/2402.06568/assets/x1.png

In order to evaluate the performance of MOEAs, there are some metrics that can be taken into account. The hypervolume indicator consists of the volume enclosed by the Pareto front approximation and a reference point. The higher the hypervolume, the better the approximated POF. Other known metrics are the Generational Distance (GD) and the Inverted Generational Distance (IGD) , which are based on the Euclidean distance between a solution and a reference point.

There exists some approaches of MOEA for the MPP. Pohl et al. compared the performance of NSGA-II and SPEA2 for the MPP defined as an extension of the VRP with time windows and minimizing the path length, the number of vehicles used and the wait time. In a previous approach , the MPP was considered as a task allocation problem aim to minimize the makespan and the fuel consumption of the mission. In this approach, a Multi-Objective Genetic Algorithm (MOGA) combined with a CSP model was used, and different encodings for the order of the performance of the task were considered.

## 3 Description of the Multi-UAV Mission Planning Problem

In this work, a more complex MPP, with more variables and constraints, than those in the state-of-the-art is considered. As was mentioned earlier, the MPP is modelled as a CSP . In this section, the variables and constraints are defined increasingly, starting with a simple approach and then adding more variables and constraints related with a new complexity element of the problem.

### 3.1 Task allocation

Initially, a mission is defined as a T-sized set of tasks $\mathcal{T}\doteq\{T_{1},T_{2},\ldots,T_{\texttt{T}}\}$ that must be performed by a swarm of U UAVs $\mathcal{U}=\{U_{1},U_{2},\ldots,U_{\texttt{U}}\}$ . Some of these tasks can be performed by several vehicles at the same time (e.g. mapping a zone or surveillance).

The first variables of the CSP that must always be considered in the MPP are:

- •
Task assignments $A_{\mathcal{T}}$: these variables are assigned a UAV or several if the task is Multi-UAV. These variables are represented as a binary $\texttt{T}\times\texttt{U}$ matrix. An assignment $A_{\mathcal{T}}[T_{t},U_{u}]=1$ means that task $T_{t}$ is assigned to UAV $U_{u}$.
- •
Orders $O_{\mathcal{T}}$: these variables define the order in which each vehicle performs the tasks assigned to it. They are represented as an $\texttt{T}\times\texttt{U}$ matrix, where the domain for each value of the matrix is $[0..\texttt{T}-1]$.

Associated with these variables, there are some order constraints that are defined to assure that tasks performed by the same vehicle have different orders and these order values are less than the number of tasks assigned to the UAV.

$$ $\displaystyle\forall T_{t}\in\mathcal{T}\quad$ $\displaystyle\forall U_{u}\in\mathcal{U}\quad A_{\mathcal{T}}[T_{t},U_{u}]=A_{\mathcal{T}}[T_{t^{\prime}},U_{u}]=1$ $\displaystyle\Rightarrow\quad O_{\mathcal{T}}[T_{t},U_{u}]\neq O_{\mathcal{T}}[T_{t^{\prime}},U_{u}]$ $\displaystyle\qquad\qquad<\sharp\left\{{T_{\tau}\in\mathcal{T}}|{A_{\mathcal{T}}[T_{\tau},U_{u}]=1}\right\}$ (1) $$

### 3.2 Temporal relations

As tasks are performed within a specific time interval, there exist some temporal constraints that must be taken into account. These constraints require the use of some extra variables that are computed in the propagation phase of the CSP:

- •
Departure time $D_{\mathcal{T}}$ when a UAV starts going to the task area.
- •
Path duration $PDur_{\mathcal{T}}$ since the UAV departs until it reaches the task area.
- •
Start time $S_{\mathcal{T}}$ of a task.
- •
Task duration $TDur_{\mathcal{T}}$. Depending on the type of task, this variable is directly provided with the mission definition (e.g. monitoring a zone) or is computed (e.g. tracking a target in a concrete path or mapping a zone using a step and stare pattern).
- •
End time $E_{\mathcal{T}}$ of a task.
- •
Loiter duration $LDur_{\mathcal{T}}$. This variable represents the time elapsed between the end of the previous task performed by the UAV and the departure for the next task, which is higher than 0 when there exists some time dependencies that impede the immediate performance of the task.
- •
Return duration $RDur_{\mathcal{U}}$ since the UAV finishes its last task until it returns to the base.
- •
Return time $R_{\mathcal{U}}$ of a UAV.

With these, some temporal constraints relating each variable are considered:

$$ $\displaystyle\forall$ $\displaystyle T_{t}\in\mathcal{T}\quad\forall U_{u}\in\mathcal{U}\quad A_{\mathcal{T}}[T_{t},U_{u}]=1$ $\displaystyle\Rightarrow\quad D_{\mathcal{T}}[T_{t},U_{u}]+PDur_{\mathcal{T}}[T_{t},U_{u}]=S_{\mathcal{T}}[T_{t},U_{u}]$ (2) $$

$$ $\displaystyle\forall$ $\displaystyle T_{t}\in\mathcal{T}\quad\forall U_{u}\in\mathcal{U}\quad A_{\mathcal{T}}[T_{t},U_{u}]=1$ $\displaystyle\Rightarrow\quad S_{\mathcal{T}}[T_{t},U_{u}]+TDur_{\mathcal{T}}[T_{t},U_{u}]=E_{\mathcal{T}}[T_{t},U_{u}]$ (3) $$

$$ $\displaystyle\forall$ $\displaystyle T_{t},T_{t^{\prime}}\in\mathcal{T}\quad\forall U_{u}\in\mathcal{U}\quad A_{\mathcal{T}}[T_{t},U_{u}]=A_{\mathcal{T}}[T_{t^{\prime}},U_{u}]=1$ $\displaystyle\qquad\qquad\qquad\quad\wedge\quad O_{\mathcal{T}}[T_{t},U_{u}]=O_{\mathcal{T}}[T_{t^{\prime}},U_{u}]-1$ $\displaystyle\Rightarrow\quad LDur_{\mathcal{T}}[T_{t^{\prime}},U_{u}]=D_{\mathcal{T}}[T_{t^{\prime}},U_{u}]-E_{\mathcal{T}}[T_{t},U_{u}]$ (4) $$

$$ $\displaystyle\forall T_{t}\in$ $\displaystyle\mathcal{T}\quad\forall U_{u}\in\mathcal{U}\quad A_{\mathcal{T}}[T_{t},U_{u}]=1$ $\displaystyle\wedge\quad O_{\mathcal{T}}[T_{t},U_{u}]=\sharp\left\{{T_{\tau}\in\mathcal{T}}|{A_{\mathcal{T}}[T_{\tau},U_{u}]=1}\right\}-1$ $\displaystyle\quad\Rightarrow\quad R_{\mathcal{U}}[U_{u}]=E_{\mathcal{T}}[T_{t},U_{u}]+RDur_{\mathcal{T}}[U_{u}]$ (5) $$

In addition, it is also necessary to assure that two tasks that collide in time are never assigned to the same vehicle:

$$ $\displaystyle\forall$ $\displaystyle T_{t},T_{t^{\prime}}\in\mathcal{T}\quad\forall U_{u}\in\mathcal{U}\quad A_{\mathcal{T}}[T_{t},U_{u}]=A_{\mathcal{T}}[T_{t^{\prime}},U_{u}]=1$ $\displaystyle\qquad\qquad\qquad\qquad\qquad\wedge\quad O_{\mathcal{T}}[T_{t},U_{u}]<O_{\mathcal{T}}[T_{t^{\prime}},U_{u}]$ $\displaystyle\qquad\qquad\qquad\qquad\Rightarrow\quad E_{\mathcal{T}}[T_{t},U_{u}]\leq D_{\mathcal{T}}[T_{t^{\prime}},U_{u}]$ (6) $$

On the other hand, a mission can have some task dependencies. These task dependencies trigger some dependency constraints in the problem. There exist two types of task dependencies: vehicle dependencies and time dependencies.

Vehicle dependencies impose if two tasks must be performed by the same or by different UAVs, triggering the following constraints:

$$ $\displaystyle\forall T_{t},T_{t^{\prime}}\in$ $\displaystyle\mathcal{T}\quad sameUAV(T_{t},T_{t^{\prime}})$ $\displaystyle\Rightarrow\quad\forall U_{u}\in\mathcal{U}\quad A_{\mathcal{T}}[T_{t},U_{u}]=A_{\mathcal{T}}[T_{t^{\prime}},U_{u}]$ (7) $$

$$ $\displaystyle\forall T_{t},T_{t^{\prime}}\in$ $\displaystyle\mathcal{T}\quad diffUAV(T_{t},T_{t^{\prime}})$ $\displaystyle\Rightarrow\quad\forall U_{u}\in\mathcal{U}\quad A_{\mathcal{T}}[T_{t},U_{u}]\neq A_{\mathcal{T}}[T_{t^{\prime}},U_{u}]$ (8) $$

Time dependencies constraint the relation of the time intervals of two tasks using Allen’s Interval Algebra (see Table [1](#S2.T1)). Henceforth, we assume $\forall T_{t},T_{t^{\prime}}\in\mathcal{T}\quad\forall U_{u}\in\mathcal{U}\quad A_{\mathcal{T}}[T_{t},U_{u}]=A_{\mathcal{T}}[T_{t^{\prime}},U_{u}]=1$, and so the following dependency constraints are defined:

$$ $T_{t}<T_{t^{\prime}}\Rightarrow\quad E_{\mathcal{T}}[T_{t},U_{u}]\leq S_{\mathcal{T}}[T_{t^{\prime}},U_{u}]$ (9) $$

$$ $T_{t}\quad m\quad T_{t^{\prime}}\Rightarrow E_{\mathcal{T}}[T_{t},U_{u}]=S_{\mathcal{T}}[T_{t^{\prime}},U_{u}]$ (10) $$

$$ $T_{t}\quad o\quad T_{t^{\prime}}\Rightarrow\begin{cases}S_{\mathcal{T}}[T_{t},U_{u}]\leq S_{\mathcal{T}}[T_{t^{\prime}},U_{u}]\\ E_{\mathcal{T}}[T_{t},U_{u}]\geq S_{\mathcal{T}}[T_{t^{\prime}},U_{u}]\\ E_{\mathcal{T}}[T_{t},U_{u}]\leq E_{\mathcal{T}}[T_{t^{\prime}},U_{u}]\end{cases}$ (11) $$

$$ $T_{t}\quad s\quad T_{t^{\prime}}\Rightarrow\begin{cases}S_{\mathcal{T}}[T_{t},U_{u}]=S_{\mathcal{T}}[T_{t^{\prime}},U_{u}]\\ E_{\mathcal{T}}[T_{t},U_{u}]\leq E_{\mathcal{T}}[T_{t^{\prime}},U_{u}]\end{cases}$ (12) $$

$$ $T_{t}\quad d\quad T_{t^{\prime}}\Rightarrow\begin{cases}S_{\mathcal{T}}[T_{t},U_{u}]\geq S_{\mathcal{T}}[T_{t^{\prime}},U_{u}]\\ E_{\mathcal{T}}[T_{t},U_{u}]\leq E_{\mathcal{T}}[T_{t^{\prime}},U_{u}]\end{cases}$ (13) $$

$$ $T_{t}\quad f\quad T_{t^{\prime}}\Rightarrow\begin{cases}S_{\mathcal{T}}[T_{t},U_{u}]\geq S_{\mathcal{T}}[T_{t^{\prime}},U_{u}]\\ E_{\mathcal{T}}[T_{t},U_{u}]=E_{\mathcal{T}}[T_{t^{\prime}},U_{u}]\end{cases}$ (14) $$

$$ $T_{t}=T_{t^{\prime}}\Rightarrow\begin{cases}S_{\mathcal{T}}[T_{t},U_{u}]=S_{\mathcal{T}}[T_{t^{\prime}},U_{u}]\\ E_{\mathcal{T}}[T_{t},U_{u}]=E_{\mathcal{T}}[T_{t^{\prime}},U_{u}]\end{cases}$ (15) $$

### 3.3 Flight Profiles

UAVs usually flight with a different speed and different altitude depending on the situation. For this, each vehicle have a set of flight profiles that define the speed, fuel consumption ratio and altitude of the UAV on a path. Henceforth, the set of flight profiles of a UAV $U_{u}$ is expressed as $FP(U_{u})$, and given a flight profile $fp$, its speed is expressed as $s_{FP}(fp)$, its fuel consumption ratio as $f_{FP}(fp)$, and its altitude as $a_{FP}(fp)$. In this work, four flight profiles are considered, being two of them used for changes of altitude and the other two for route flight at a specific altitude:

- •
Climb profile: This profile is used by the vehicle when the altitude must be increased. Instead of the altitude, it defines the climb angle used.
- •
Descent profile: This profile is used by the vehicle when the altitude must be decreased. Instead of the altitude, it defines the descent angle used.
- •
Minimum consumption profile: This profile defines the speed and altitude that permit the least fuel consumption of the vehicle.
- •
Maximum speed profile: This profile is used when the vehicle must flight at its maximum speed.

With these profiles, new variables of the CSP must be considered:

- •
Path Flight Profiles $PFP_{\mathcal{T}}$: this variable sets the flight profile that the vehicle must use in its path to the task area. These variables are represented as a $\texttt{T}\times\texttt{U}$ matrix, and their domains are the flight profiles of the UAV in the column: $PFP_{\mathcal{T}}[T_{t},U_{u}\in FP(U_{u})$.
- •
Return Flight Profiles $RFP_{\mathcal{U}}$: this variable sets the flight profile that the vehicle must use in its return to the base. There are U variables of this type, and their domain is the same as the previous variables: $RFP_{\mathcal{U}}[U_{u}\in FP(U_{u})$.

With these variables, and knowing the distances traversed for every path (geodesic distance), which are expressed $PDist_{\mathcal{T}}$ for the Path Distance and $RDist_{\mathcal{U}}$ for the Return Distance; it is possible to compute the path and return duration using the speed of the assigned flight profiles:

$$ $\displaystyle\forall$ $\displaystyle T_{t}\in\mathcal{T}\quad\forall U_{u}\in\mathcal{U}\quad A_{\mathcal{T}}[T_{t},U_{u}]=1$ $\displaystyle\quad\Rightarrow\quad PDur_{\mathcal{T}}[T_{t},U_{u}]=\frac{PDist_{\mathcal{T}}[T_{t},U_{u}]}{s_{FP}(PFP_{\mathcal{T}}[T_{t},U_{u}])}$ (16) $$

$$ $\forall U_{u}\in\mathcal{U}\quad RDur_{\mathcal{U}}[U_{u}]=\frac{RDist_{\mathcal{U}}[U_{u}]}{s_{FP}(RFP_{\mathcal{U}}[U_{u}])}$ (17) $$

### 3.4 Sensors

The different types of tasks considered in this work require different sensors carried by the UAVs to be performed. Henceforth, the set of sensors that a UAV $U_{u}$ has are expressed as $X_{\mathcal{U}}$, and the set of sensors that are capable to perform a task $T_{t}$ are expressed as $X_{\mathcal{T}}(T_{t})$. The sensors considered in this work are Electro-optical or Infrared (EO/IR) sensors, Synthetic Aperture Radar (SAR), Inverse Synthetic Aperture Radar (ISAR), Maritime Patrol Radar (MPR) and water tanks.

In addition, the different types of task considered are defined in Table [2](#S3.T2).

**Table 2: Type of tasks and the sensors capable of performing them**
| Name | Description | Multi-UAV | Sensors needed |
| --- | --- | --- | --- |
|  |  |  |  |
| Mapping a zone | Travel a zone performing a step & stare pattern | Yes | •<br>EO/IR sensor |
| Monitoring a zone | Fly circling in a zone during a specific time | No | •<br>EO/IR sensor |
| Patrol a path | Follow a path | No | •<br>SAR radar<br>•<br>ISAR radar |
| Target photographing | Go to a point and take a photo | No | •<br>EO/IR sensor |
| Tracking a target | Cycle around a target during a specific time | No | •<br>SAR radar<br>•<br>ISAR radar |
| Surveillance | Explore a zone during a specific time | Yes | •<br>EO/IR sensor<br>•<br>SAR radar<br>•<br>ISAR radar<br>•<br>MPR radar |
| Fire Extinguishing | Put out a fire in a point | No | •<br>Water tank |

Each sensor has specific values of speed and altitude for its optimal use. Henceforth, the optimal speed of a sensor $x$ is expressed as $s_{X}(x)$, and the optimal altitude is expressed as $a_{X}(x)$.

When a UAV has more than one sensor capable of performing a task assigned to it, it is necessary to select a specific sensor for performing that task. For this, new variables of the CSP are defined: the Task Sensors $TX_{\mathcal{T}}$, which set the sensor of the UAV used for the task performance. These variables are represented as a $\texttt{T}\times\texttt{U}$ matrix, being the different sensors their domain.

These sensor assignments come hand in hand with some Sensor constraints. These constraints check that the UAV has the sensors assigned to perform the task:

$$ $\displaystyle\forall$ $\displaystyle T_{t}\in\mathcal{T}\quad\forall U_{u}\in\mathcal{U}\quad A_{\mathcal{T}}[T_{t},U_{u}]=1$ $\displaystyle\qquad\Rightarrow\quad TX_{\mathcal{T}}[T_{t},U_{u}]\in X_{\mathcal{U}}(U_{u})\cap X_{\mathcal{T}}(T_{t})\neq\emptyset$ (18) $$

### 3.5 GCS assignments

When there are many UAVs in a mission, most times an only GCS is not capable of controlling all of them. In this approach, a number G of GCSs $\mathcal{G}\doteq\{G_{1},G_{2},\ldots,G_{\texttt{G}}\}$ are considered for controlling the UAVs.

This consideration leads to the last variables of the CSP: the GCS assignments $A_{\mathcal{G}}$. There are U variables of this type, one per vehicle, and their domain is $[-1..\texttt{G}-1]$, where $-1$ is only assigned when the UAV does not perform any task.

Each GCS $G_{g}$ supports a maximum number of vehicles being controlled at the same time $maxU_{\mathcal{G}}(G_{g})$, and is only capable of controlling some specific types of UAV $typeU_{\mathcal{G}}(G_{g})$. In addition, it has a within range of communications $wr_{\mathcal{G}}(G_{g})$, being not able of control the vehicles out of this range.

With these features, some GCS constraints have to be considered. These constraints assure that the UAVs assigned to the GCS are of a supported type, and the maximum number of vehicles that the GCS can handle is not overpassed:

$$ $\displaystyle\forall U_{u}\in\mathcal{U}\quad\forall G_{g}\in\mathcal{G}$ $\displaystyle\quad A_{\mathcal{G}}[U_{u}]=G_{g}$ $\displaystyle\Rightarrow\quad type(U_{u})\subset typeU_{\mathcal{G}}(G_{g})$ (19) $$

$$ $\forall G_{g}\in\mathcal{G}\;\;\sharp\left\{{U_{u}\in\mathcal{U}}|{A_{\mathcal{G}}[U_{u}]=G_{g}}\right\}<maxU_{\mathcal{G}}(G_{g})$ (20) $$

Finally, in order to check that the UAVs are inside the range of the GCS at every moment, we define the position $Pos_{\mathcal{G}}(G_{g})$ of the GCS $G_{g}$, and the position $Pos_{\mathcal{U_{u},\tau}}$ of the UAV $U_{u}$ at time $\tau$. Also, the geodesic distance function $GeoDist(p_{1},p_{2})$ is defined for each pair of (Latitude, Longitude, Altitude) points $p_{1},p_{2}$. With this, the GCS constraint is defined:

$$ $\displaystyle\forall$ $\displaystyle U_{u}\in\mathcal{U}\quad\forall G_{g}\in\mathcal{G}\quad A_{\mathcal{G}}[U_{u}]=G_{g}\quad\Rightarrow\quad\forall\tau\in\mathbb{R}$ $\displaystyle\quad GeoDist(Pos_{\mathcal{U}}(U_{u},\tau),Pos_{\mathcal{G}}(G_{g}))\leq wr_{\mathcal{G}}(G_{g})$ (21) $$

### 3.6 Checking constraints

The UAVs of a mission have some features that must be considered when checking if a plan is correct. These features include the already explained sensors and flight profiles of the vehicle, and also the type of the vehicle. In this work, the types considered are Unmanned Reconnaissance Aerial Vehicle (URAV), Medium Altitude Long Endurance (MALE), High Altitude Long Endurance (HALE) and Unmanned Combat Aerial Vehicle (UCAV), which are described in Table [3](#S3.T3).

Apart from these, there are some features that constraint the use of the vehicle: the maximum flight time $maxFT_{\mathcal{U}}(U_{u})$ that the UAV can stay in flight, the maximum distance $maxDist_{\mathcal{U}}(U_{u})$ that the UAV can traverse during a mission, the cost per hour $cost_{\mathcal{U}}(U_{u})$ of the UAV, the maximum speed $maxS_{\mathcal{U}}(U_{u})$ that the UAV can attain, the maximum altitude $maxA_{\mathcal{U}}(U_{u})$ that the UAV can reach in flight and the maximum fuel $maxF_{\mathcal{U}}(U_{u})$ in the UAV tank.

Other features that must be considered are the initial settings of the UAV $U_{u}$ at the start of the mission: its initial position $Pos_{\mathcal{U}}(U_{u})$ and its initial amount of fuel $F_{\mathcal{U}}(U_{u})$.

**Table 3: Different types of UAVs considered and their features.**
| Name | Max. Distance (NM) | Max. Flight Time (h) | Cost/h | Max. Speed (kt) | Max. Altitude (ft) | Max. Fuel (kg) | Available Sensors |
| --- | --- | --- | --- | --- | --- | --- | --- |
|  |  |  |  |  |  |  |  |
| URAV | 1000 | 20 | 5 | 120 | 20000 | 500 | •<br>EO/IR sensor<br>•<br>Water tank |
| MALE | 5000 | 30 | 10 | 250 | 40000 | 2500 | •<br>EO/IR sensor<br>•<br>MPR radar |
| HALE | 15000 | 40 | 15 | 400 | 65000 | 6000 | •<br>EO/IR sensor<br>•<br>ISAR radar |
| UCAV | 1500 | 15 | 25 | 450 | 35000 | 9000 | •<br>SAR radar |

With these, there are some Checking constraints that must be met to assure the correct functioning of the UAV.

- •
Flight time constraints: they assure that the total flight time for each vehicle is less than its maximum:
$\displaystyle\forall U_{u}\in\mathcal{U}\quad FT[U_{u}]=\sum_{\mathclap{\begin{subarray}{c}T_{t}\in\mathcal{T}\\
A_{\mathcal{T}}[T_{t},U_{u}]=1\end{subarray}}}{(PDur_{\mathcal{T}}[T_{t},U_{u}]}$
$\displaystyle+TDur_{\mathcal{T}}[T_{t},U_{u}]+LDur_{\mathcal{T}}[T_{t},U_{u}])+RDur_{\mathcal{U}}[U_{u}]$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad<maxFT_{\mathcal{U}}(U_{u})$
(22)
- •
Distance constraints: they assure that the distance traversed by each vehicle is less than its maximum. To compute these constraints, the
Path Distance $PDist_{\mathcal{T}}$, the Task Distance $TDist_{\mathcal{T}}$, the Loiter Distance $LDist_{\mathcal{T}}$ and the Return Distance $RDist_{\mathcal{U}}$ are needed.
$\displaystyle\forall U_{u}\in\mathcal{U}\quad Dist[U_{u}]=\sum_{\mathclap{\begin{subarray}{c}T_{t}\in\mathcal{T}\\
A_{\mathcal{T}}[T_{t},U_{u}]=1\end{subarray}}}{(PDist_{\mathcal{T}}[T_{t},U_{u}]}$
$\displaystyle+TDist_{\mathcal{T}}[T_{t},U_{u}]+LDist_{\mathcal{T}}[T_{t},U_{u}])+RDist_{\mathcal{U}}[U_{u}]$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad<maxDist_{\mathcal{U}}(U_{u})$
(23)
Path and return distance are computed as the sums of distances between the points of the path employed in each case. Task distance is computed similarly in the case of tasks with no specific duration. If the task has a specific duration, then the task distance of task $T_{t}$ performed by UAV $U_{u}$ can be computed using this duration and the optimal speed given by the sensor used:
$TDist_{\mathcal{T}}[T_{t},U_{u}]=TDur_{\mathcal{T}}[T_{t},U_{u}]\times s_{X}(TX_{\mathcal{T}}[T_{t},U_{u}])$
(24)
When a loiter is needed, the minimum consumption flight profile is used. Then the loiter distance of task $T_{t}$ performed by UAV $U_{u}$ can be computed as:
$LDist_{\mathcal{T}}[T_{t},U_{u}]=LDur_{\mathcal{T}}[T_{t},U_{u}]\times s_{FP}(MINC(U_{u}))$
(25)
- •
Fuel constraints: they assure that the fuel consumed by each UAV is less than its initial fuel. To compute these constraints, the Path Fuel Consumption $PF_{\mathcal{T}}$, the Task Fuel Consumption $TF_{\mathcal{T}}$, the Loiter Fuel Consumption $LF_{\mathcal{T}}$ and the Return Fuel Consumption $RF_{\mathcal{U}}$ are needed.
$\displaystyle\forall U_{u}\in\mathcal{U}\quad F[U_{u}]=\sum_{\mathclap{\begin{subarray}{c}T_{t}\in\mathcal{T}\\
A_{\mathcal{T}}[T_{t},U_{u}]=1\end{subarray}}}{(PF_{\mathcal{T}}[T_{t},U_{u}]+TF_{\mathcal{T}}[T_{t},U_{u}]}$
$\displaystyle\qquad\quad\;+LF_{\mathcal{T}}[T_{t},U_{u}])+RF_{\mathcal{U}}[U_{u}]<F_{\mathcal{U}}(U_{u})$
(26)
Each one of these fuel consumptions is computed as the product of its associated duration and the fuel consumption ratio specified by the flight profile or the sensor, or the minimum consumption in the case of loiter.
When checking the fuel consumption for each UAV, a risk can be considered when the remaining amount of fuel at the end of the mission is low. For this, the remaining fuel is used along with a risked fuel usage value provided by the operator to compute the risk of the mission.

### 3.7 Path Constraints

In realistic UAV MPPs, paths are not usually a straight line, but instead UAVs have to perform some climb or descent in order to reach the altitude specified by the flight profile or the optimal altitude for the use of the sensor. In the case of both the path of the UAV to the task area and the return to the base, the UAV departs with an initial altitude that could be bigger than the flight profile altitude (and so a descent must be done) or smaller than it (so a climb must be done). So the climb or descent is performed, the UAV flies heading to the task area (or the base) and before arriving, another change of altitude is needed to reach the optimal altitude of the sensor used in the task (or the terrain altitude in order to land). This situation is represented in Figure [2](#S3.F2).

Figure: Figure 2: Climb/Descend situation in path computing.
Refer to caption: /html/2402.06568/assets/figs/climbdescent.png

On the other hand, some missions may have No Flight Zones (NFZs) and terrain obstacles (a DTED file is used to define the terrain) that could be in the trajectory of the UAV and that must be avoided. For this, Theta* is used, returning a set of waypoints which define the route. These computations are time consuming, so when they are used, the runtime may increase significantly.

So now, the distance, duration and fuel consumption variables defined previously (see equations [3.3](#S3.Ex13) and [17](#S3.E17)) must be updated considering the climb and descent performed, and the waypoints obtained by Theta*.

On the other hand, when considering these more realistic paths, it is necessary to take into account the distance of the UAVs to the ground, in order to avoid collision risks. So, for each UAV $U_{u}$, the minimum distance to ground $minDG_{\mathcal{U}}[U_{u}]$ is computed. This variable will be used along with a risked distance to ground value provided by the operator to compute the risk of the mission.

Similarly, to avoid collision risks, the distance between UAVs must also be computed. With the time route for each pair of vehicles, the position of both vehicles at the same time is checked, storing the minimum distance obtained so far. With this, the minimum distance $minD_{\mathcal{U}}(U_{u},U_{u^{\prime}})$ between two vehicles $U_{u}$ and $U_{u^{\prime}}$ is obtained. Similarly as with the minimum distance to ground, a risked distance between UAVs value is provided by the operator, and the risk of the mission is updated.

### 3.8 LOS constraints

Apart from checking the within range of a GCS, it is also necessary to assure that the GCS and the UAV being controlled are in Line of Sight (LOS). This means that there is no obstacle in the line of communications joining them. These LOS constraints are quite important when missions are carried out in mountainous terrains.

$$ $\displaystyle\forall$ $\displaystyle U_{u}\in\mathcal{U}\quad\forall G_{g}\in\mathcal{G}\quad A_{\mathcal{G}}[U_{u}]=G_{g}$ $\displaystyle\quad\Rightarrow\quad\forall\tau\in\mathbb{R}\quad LOS(Pos_{\mathcal{U}}(U_{u},\tau),Pos_{\mathcal{G}}(G_{g}))$ (27) $$

The $LOS$ function used to compute the line of sight between two points, uses the DTED terrain file to check if there any terrain in the line joining both points. This function is quite time consuming, so the runtime of the algorithm used may increase significantly when considering these constraints.

### 3.9 Optimization variables

Apart from the variables and constraints considered in the CSP mode, the MPP is a MOP, and several objectives must be considered when optimizing the problem:

- 1.
The makespan or time when the mission ends (all the vehicles have returned):
$M=\max_{U_{u}\in\mathcal{U}}{R_{\mathcal{U}}(U_{u})}$
(28)
- 2.
The total cost of the mission, computed as the sum of the individual cost of each UAV:
$C=\sum_{U_{u}\in\mathcal{U}}{cost_{\mathcal{U}}(U_{u})\times FT[U_{u}]}$
(29)
- 3.
The risk of the mission, computed as an average of risk percentages of low distance to ground $R_{Ground}$, low distance between UAVs $R_{UAVs}$ and low fuel $R_{Fuel}$ at the end of the mission.
$R=\frac{R_{Ground}+R_{UAVs}+R_{Fuel}}{3}$
(30)
- 4.
The number of UAVs used in the mission:
$N_{\mathcal{U}}=\sharp\left\{{U_{u}\in\mathcal{U}}|{\exists T_{t}\in\mathcal{T}\quad A_{\mathcal{T}}[T_{t},U_{u}]=1}\right\}$
(31)
- 5.
The total fuel consumed by all UAVs during the mission:
$F=\sum_{U_{u}\in\mathcal{U}}{F[U_{u}]}$
(32)
- 6.
The total flight time of all UAVs during the mission:
$FT=\sum_{U_{u}\in\mathcal{U}}{FT[U_{u}]}$
(33)

## 4 MOEA-CSP Algorithm for Multi-UAV Mission Planning Problems

The MPP designed in the previous section is a quite complex problem with a large amount of constraints involved, and a huge number of solutions may be generated with classic methods. For this, and to the multi-objective nature of the problem, a MOEA has been used to solve this problem. In this approach, an extension of NSGA-II is proposed. A CSP model is used as a penalty function in the evaluation phase of the algorithm. In a second approach, in order to increase the convergence of the problem by reducing the search space, some of the constraints of the CSP are considered in the setup and operators of the algorithm.

This section describes this algorithm, including the encoding, the fitness function designed, the genetic operators implemented and the constraints considered in the assignment and mutation.

### 4.1 Encoding

The encoding of the MPP has been based on the variables of the CSP model, taking into account the chromosome representation of the orders presented in a previous work . This encoding consist of six alleles (see Figure [3](#S4.F3)):

Figure: Figure 3: Example of an individual that represents a possible solution for a problem with 5 tasks, 3 UAVs and 2 GCSs.
Refer to caption: /html/2402.06568/assets/figs/chromosome5.png

- 1.
UAV assignments for each task. Based on the task assignments, each cell contains the identifier of the UAV assigned to that task. When some task is Multi-UAV, its cell contains a vector representing the different vehicles assigned to it. The number of combinations, or space size, for this allele is, considering $\texttt{T}_{MU}$ the number of Multi-UAV tasks, $\texttt{U}^{\texttt{T}-\texttt{T}_{MU}}\times(2^{\texttt{U}}-1)^{\texttt{T}_{MU}}$.
- 2.
Permutation of the task orders. These values indicate the absolute order of the tasks. When several tasks are assigned to the same vehicle, the ones with a lower order value start first, while the tasks with higher values go last. The space size for this allele is $\texttt{T}!$.
- 3.
GCSs controlling each UAV. This is the same as the GCS assignments of the CSP model. The space size for this allele is $\texttt{G}^{\texttt{U}}$.
- 4.
Flight profiles used for each UAV in the path to the task area. The flight profiles considered in this problem are the minimum consumption profile ($min$) and the maximum speed profile ($max$). As in the first allele, some of the cells could contain a vector if the corresponding task is performed by several vehicles. The space size for this allele is $2^{\texttt{T}-\texttt{T}_{MU}}\times(2^{\texttt{U}+1}-2)^{\texttt{T}_{MU}}$.
- 5.
Sensors used for the task performance by each UAV. The values considered in this approach are eiS (EO/IR sensor), sR (SAR radar), iR(ISAR radar), mR (MPR radar) and wt (water tank). Some of the cells contain a vector because of the Multi-UAV nature of the task. Considering the worst where all vehicles have all $s$ sensors, then the space size is bounded by $s^{\texttt{T}-\texttt{T}_{MU}}\times(\sum_{i=1}^{\texttt{U}}s^{i})^{\texttt{T}_{MU}}$.
- 6.
Flight Profiles used by each UAV to return to the base. This allele corresponds to the Return Flight Profiles variable of the CSP model. The space size for this allele is $2^{\texttt{U}}$.

Multiplying the different sizes for each allele and reducing the resultant formula, the total space size of the problem is as follows:

$$ $\displaystyle\texttt{T}!\times\texttt{U}^{\texttt{T}-\texttt{T}_{MU}}\times\texttt{G}^{\texttt{U}}$ $\displaystyle\times 2^{\texttt{T}+\texttt{U}}\times(2^{\texttt{U}}-1)^{2\times\texttt{T}_{MU}}\times s^{\texttt{T}}$ $\displaystyle\quad\;\times(s^{\texttt{U}}-1)^{\texttt{T}_{MU}}\times(s-1)^{-\texttt{T}_{MU}}$ (34) $$

### 4.2 Fitness Function

The evaluation phase of the MOEA is performed using a fitness function composed of two steps:

- 1.
Given a specific solution, the CSP model handles that all constraints are fulfilled. If not, it returns the number of unfulfilled constraints, and these solutions are not considered when other valid solutions were found. For complex problems, valid solutions take much runtime as all constraints are checked.
- 2.
If all constraints are fulfilled, a multi-objective function minimizing the objectives of the problem is applied. The objectives considered were presented in section [3.9](#S3.SS9).

In the case when all the individuals of the population are invalid, those with the fewer number of invalid constraints are selected for reproduction.

As in NSGA-II approach, after the evaluation of the solutions, the Pareto front is extracted and the solutions are ordered according to the crowding distance.

### 4.3 Genetic Operators

As the encoding presented has been specifically developed for this problem, so are the operators used in the algorithm.
The crossover operator developed is used to combine the chromosomes of each pair of parents to generate a new pair of children. This operator applies a specific crossover operation at each of the alleles. The first, fourth and fifth allele, i.e. the task assignments, path flight profiles and sensor assignments, are applied a 2-point crossover, using the same cross points in all alleles so the size for Multi-Unmanned Air Vehicle (UAV) tasks is maintained. The second allele, as it is a permutation, is applied a Partially-Matched Crossover (PMX). This passes a chunk of values from one parent to the other and then performs a replacement of the invalid values of the new child based on its previous parent. Finally, the third and sixth alleles are applied another 2-point crossover with different points.

Once the new pair of individuals has been generated from crossover operation, a mutation operator is required. This genetic operator helps to avoid that the obtained solutions stagnate at local minimums. This mutation operator is designed to perform a uniform mutation over the same genes for the first, fourth and fifth allele in order to maintain the size of Multi-UAV tasks. On the other hand, the second allele is applied an Insert Mutation, which will select two random positions from the permutation and move the second one next to the first one. Finally, the third and sixth allele are updated using another uniform mutation.

### 4.4 Adding constraints to the GA process

In order to facilitate the convergence of the problem, some constraints have been taken from the CSP model and added into to the GA setup, crossover and mutation operators. This way, the algorithm will avoid assigning some invalid solutions due to these constraints, and therefore the search space is reduced. The constraints considered have been:

- •
Sensor constraints: As a sensor must be assigned after the assignment of a UAV to a task, it is pretty convenient to avoid selecting the sensors required by the task that are not available by the UAV. The setup and the mutation operation have been changed so the domain for each sensor gene is updated, after the task assignments gene are set, to $X_{\mathcal{U}}(U_{u})\cap X_{\mathcal{T}}(T_{t})$.
- •
GCS constraints: When assigning a UAV to the GCS controlling it, it is possible to check that this GCS can control this type of UAV. So the domain of the GCS gene can be reduced to the GCSs capable of controlling that type of vehicle. On the other hand, once the entire GCS assignments have been done, it is possible to check, both in the setup, crossover and mutation, if every GCS is not assigned more UAVs than the maximum it can handle.
- •
Dependency constraints: UAV dependencies are directly checked when task assignments are done in setup and mutation. If two task must be assigned the same vehicle, the second task is directly assigned the same UAV; and if two task must be performed by different UAVs, the domain of the second one is reduced by deleting the UAV assigned to the first one. Moreover, the Path Consistency algorithm used to check the time dependencies, so order assignments are correct, can be used in the GA setup and operators before generating a new solution.

### 4.5 Algorithm

The new approach is presented in Algorithm [1](#algorithm1). First, an initial population is randomly generated (Line 1) taking into account the constraints of section [4.4](#S4.SS4). Then, the evaluation of the individuals is performed using the fitness function (Lines 6-14) explained in section [4.2](#S4.SS2).

Figure: Algorithm 1 NSGA-II with CSP model for Mission Planning Problems

After that, the buildArchive process of NSGA-II (Line 15) is performed, generating a set of ranked vectors, where the first one represents the Pareto front of the solutions ranked by crowding distance. Then, an elitist selection is performed, where the $\mu$ best individuals in the population are retained (Line 20). Afterwards, a tournament selection over these $\mu$ individuals (Line 22) selects those that will be applied the crossover (Line 23) and mutation (Lines 24-25) operators explained in section [4.3](#S4.SS3) considering the constraints of section [4.4](#S4.SS4).

Finally, the stopping criteria designed for this algorithm compares the Pareto front obtained so far in each generation with the Pareto front from the previous generations (Lines 17-19). The algorithm stops when the front remains unchanged during a specific number of generation $stopGen$.

## 5 Experiments

In this section we explain the experiments carried out to test the functionality of the new NSGA-II-CSP approach for MPP.

The first experiment studies the performance of the algorithm considering different variables of the CSP model in the MPP (e.g. a first approach only takes into account task assignments and orders, another approach adds flight profiles, another adds GCS assignments, etc.).

Then, a second experiment studies the performance of the algorithm with an increasing number of constraints considered (e.g. a first approach only considers temporal constraints, then checking constraints are added, then path constraints, etc.).

Finally, the last experiments compares the performance of the algorithm when no constraints are checked inside the GA process against the final approach considering the sensor, GCS and dependency constraints in the setup and genetic operators.

Figure: (a) Mission 1.
Refer to caption: /html/2402.06568/assets/figs/D11.png

### 5.1 Experimental setup

In these experiments, 6 missions of increasing complexity have been designed to test the performance of the algorithm. These missions are described in Table [4](#S5.T4), showing the number of tasks, UAVs, GCSs, NFZs and task dependencies for each mission. Figure [4](#S5.F4) shows the scenario of each mission, where the green zones represent tasks and the red zones represent NFZs. There are also some point tasks represented with an icon, such as photographing, tracking or fire extinguishing.

**Table 4: Features of the different missions designed.**
| Mission<br>Id. | Tasks | Multi-UAV<br>Tasks | UAVs | GCSs | NFZs | Time<br>Dependencies |
| --- | --- | --- | --- | --- | --- | --- |
| 1 | 5 | 0 | 3 | 1 | 0 | 0 |
| 2 | 6 | 1 | 3 | 1 | 1 | 0 |
| 3 | 6 | 1 | 4 | 2 | 2 | 1 |
| 4 | 7 | 1 | 5 | 2 | 1 | 2 |
| 5 | 8 | 2 | 5 | 2 | 3 | 1 |
| 6 | 9 | 2 | 5 | 2 | 0 | 2 |

In the experimental phase, the number of solutions, the number of generations needed to converge, the runtime spent and the hypervolume of the solutions obtained are extracted. Every experiment is run 30 times, and the mean and standard deviation for every metric are computed.

Every execution of NSGA-II use a selection criteria $\mu+\lambda=10+100$, where $\lambda$ is the number of offspring (population size), and $\mu$ the elitism size (i.e. the number of the best parents that survive from current generation to the next). The mutation probability is $10\%$, the maximum number of generations is $300$ and the number of generations for the stopping criteria is $10$. The experiments have been run in a Intel Xeon CPU E5-2650 v3 2.30GHz with 10 cores and 250GB DDR4 RAM.

### 5.2 Experiment with different variables

In this first experiment, we consider five approaches with different variables of the CSP:

- 1.
Only task assignments. In this approach, only task assignments and orders are considered in the encoding. In addition, order and temporal constraints are considered.
- 2.
Using Flight Profiles. This approach extends the first one by adding flight profile variables and constraints.
- 3.
Using Sensors. This approach extends the first one by adding sensor variables and constraints.
- 4.
Using GCSs. This approach extends the first one by adding GCS variables and constraints.
- 5.
Complete encoding. This approach comprises all the previous ones, including all the variables of CSP model for the MPP.

Each approach is executed with NSGA-II, and the results obtained are presented in Figure [5](#S5.F5).

Figure: Figure 5: Hypervolume, number of solutions, number of generations and runtime obtained with NSGA-II for MPPs considering different approaches using different variables of the CSP.
Refer to caption: /html/2402.06568/assets/x2.png

This figure presents bar graphs with the mean and error bars with the standard deviation for the every metric considered. It can be noticed that for the first missions, the flight profile is most significant than the sensors and the GCSs, as more solutions are obtained and more runtime is spent. Obviously, the complete encoding presents the higher number of solutions, hypervolume and runtime. As the complete encoding approach considers much more variables and constraints than the rest, the runtime is always higher than any other approach.

For the most complex missions, it can be seen that the problems do not converge within the 300 generations considered. This can also be noticed as the standard deviation is quite large, specially for the number of solutions and the runtime.

The main conclusion that can be extracted here is that adding variables makes the complexity of the problem grow exponentially, and it becomes quite hard for the algorithm to find the POF.

### 5.3 Experiment with increasing number of constraints

The second experiment consists of four approaches with increasing number of constraints of the CSP:

- 1.
Basic constraints. This approach considers the complete encoding approach of the previous experiment, where temporal, order, GCS, sensor and flight profile constraints are considered.
- 2.
Adding checking constraints. This approach adds to the first one the checking constraints, i.e. flight time, fuel and distance constraints.
- 3.
Adding path constraints. This approach adds to the previous one the path constraints, including the climb and descent consideration, the NFZ avoidance and the distance to ground computation.
- 4.
Adding LOS. This approach adds the LOS constraints to the previous one, resulting in the complete CSP model for MPP defined in section [3](#S3).

Each approach is executed with NSGA-II, and the results obtained are presented in Figure [6](#S5.F6).

Figure: Figure 6: Hypervolume, number of solutions, number of generations and runtime obtained with NSGA-II for MPPs considering different approaches with increasing number of constraints of the CSP.
Refer to caption: /html/2402.06568/assets/x3.png

These results show that adding more constraints do no affect the less complex missions, as the results obtained for all metrics is similar.

On the other hand, for the most complex mission, it is appreciable that the number of solutions and the runtime decrease as the number of constraints increase. This is due to many solutions becoming invalid due to the new constraints.

It is curious that the complexity of the path and LOS constraints, which should highly increase the runtime of the algorithm, is not appreciated in the results (only Mission 2 shows a low increase in the runtime). This is because valid solutions take much more runtime to be checked, but as the number of solutions has been highly reduced, most solutions checked are invalid, which do not take so much time to be checked.

### 5.4 Experiment with different constraints in the GA

In this last experiment, we consider five approaches related with the consideration of constraints in the GA process (see section [4.4](#S4.SS4)):

- 1.
CSP Penalty Fitness. In this approach, no constraint is considered in the GA setup nor the genetic operators, so the complete CSP model works as a penalty function.
- 2.
Sensor constraints in GA. This approach considers the sensor constraints in the setup and mutation of NSGA-II, constraining the generation of solutions to those with valid sensors.
- 3.
Dependency constraints in GA. This approach considers dependency constraints in the setup and genetic operators of NSGA-II, so a solution not fulfilling the task dependencies of the problem will not be generated.
- 4.
GCS constraints in GA. This approach considers the GCS constraints in the setup and genetic operators of the algorithm, avoiding invalid types of vehicles and surpassing of the maximum number of UAVs supported by the GCS.
- 5.
Sensor, GCS and Dependency constraints in GA. This approaches combines the three types of constraints considered in the previous approaches.

All these approaches are run 30 times by the algorithm presented in section [4](#S4), and the results obtained are presented in Figure [6](#S5.F6), representing the mean and standard deviation for each metric considered.

Figure: Figure 7: Hypervolume, number of solutions, number of generations and runtime obtained with NSGA-II for MPPs considering different approaches using constraints in the GA process.
Refer to caption: /html/2402.06568/assets/x4.png

The results obtained show that the number of solutions obtained increase when adding constraints to the GA process, specially for the most complex missions. As the algorithm reached its maximum number of generations, it is clear that using these constraints in the GA setup accelerates the search of valid solutions, leading to a higher number of solutions in the end.

As can be seen, the runtime highly increases when using these constraints are used. This is because these approaches, specially the last one, find more valid solutions, which take much more time to be checked by the CSP model than the invalid ones.

Regarding at concrete constraints, it cannot be concluded if some constraint helps more than other in the search of valid solutions, as each mission got better results with different constraints. The less complex mission got better results just using sensor constraints, mission 4 got better results with dependency constraints, and the most complex obtained better results with GCS constraints.

On the other hand, it is also appreciable that, although the number of solutions increase, the hypervolume obtained when using constraints in the GA setup remains pretty similar to the one in the CSP penalty fitness approach. To study this, the solutions obtained for mission 6 have been plotted using a parallel visualization plot (see Figure [8](#S5.F8)). In order to ease the visualization and interpretation of the interplay between the different objectives, z-scores are used in these parallel plots, so changes are smoother depending on the standard deviation of the values for each objective.

Figure: (a) CSP Penalty Fitness.
Refer to caption: /html/2402.06568/assets/figs/parallelviz_plot6_LOS.png

In this representation it can be clearly seen, comparing Figure [8(a)](#S5.F8.sf1) with the rest, that the new solutions appearing when using constraints in the GA setup are close to the already obtained in the first approach. These solutions are similar to other solutions already computed in the first approach that just slightly increases one objective and slightly reduces another one. With this, the new solutions contribute very little to the hypervolume.

With this, it can be said that using constraints in the GA setup and operators helps in the convergence of the POF. But this POF becomes pretty large with complex problems, so it is difficult to obtain it entirely with the current approach; and sometimes unnecessary as the new solutions obtained are not very relevant.

## 6 Discussion

In this work, the Multi-UAV MPP has been presented and modelled as a CSP. Different variables and constraints of the CSP model defined the high complexity of this problem.

To solve this problem, a hybrid MOEA-CSP algorithm was presented for the MPP, where seven objectives of the problem must be minimized. NSGA-II was extended to deal with constraints both in the fitness function and some of them in the setup and genetic operators, aimed to reduce the search space of the problem.

Three experiments were performed using varied datasets of different complexity. First, a comparative assessment of the variables is performed using different approaches of the problem using some specific variables. This experiment showed that the problem scales quite fast with the number of variables, becoming quite much difficult to optimize the problem with all the variables.

The second experiment used different approaches with an increasing number of constraints. Here, it was proved that the constraints reduce the space of valid solutions, making it faster.

Finally, the third experiment proved that adding constraints to the setup and genetic operators of the algorithm to reduce the search space of the algorithm, makes it converge better.

Nevertheless, it was concluded that as the complexity of the mission increases, the number of solutions in the POF become huge. This implies that the time needed to obtain the completePOF becomes intractable. On the other hand, in this problem the operator will in the end select one concrete solution to be executed, so getting so many solutions will highly increase the decision making process.

In future works, some new methods will be applied to outperform the convergence of the algorithm. In addition, the Multi-Objective approach will be changed to focus the search on the most significant solutions, avoiding unnecessary solutions that are not likely to be selected by the operator.

Finally, a Decision Support System (DSS) will be provided to rank and filter the solutions obtained in order to help the operator decide the final solution to be executed.

## Compliance with Ethical Standards

Funding: This study was funded by Spanish Ministry of Science and Education and Competitivity and European Regional Development Fund FEDER (TIN2014-56494-C4-4-P and TIN2017-85727-C4-3-P), Comunidad Autónoma de Madrid (CIBERDINE S2013/ICE-3095) and Airbus Defence & Space under Savier Project (FUAM-076915).

The Authors: Cristian Ramirez-Atencia and David Camacho declare that they have no conflict of interest.

Ethical approval: This article does not contain any studies with human participants or animals performed by any of the authors.

###### Acknowledgements.

###### Acknowledgements.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 3
presentation: 1
questions: In line 132, why do the authors state that the goal of MOO is to find a Pareto optimal solution? In fact, for many real-world MOO applications, the goal is to find a set of well-distributed Pareto optimal solutions.
soundness: 1
strengths: The authors conduct a convergence analysis for MLM-CMOO and provide several theoretical proofs in the supplementary materials.
summary: This work proposes a gradient-based optimization algorithm, MLM-CMOO, to solve constrained multi-objective optimization (CMOO) problems. The authors conduct a convergence analysis and several experiments to demonstrate the effectiveness of the proposed MLM-CMOO algorithm.
weaknesses: 1. The submission focuses on constrained multi-objective optimization (CMOO), however, no CMOO algorithms are compared in the experiments. The authors should compare several CMOO algorithms in their experiments. For example, the authors reviewed some gradient-free CMOO algorithms in the related work section, which could be included in the comparisons.
2. In Section 2, only gradient-based MOO and gradient-free CMOO are discussed in the related work. The authors should also review some constraint handling techniques (CHTs).
3. The experiments in Section 5 are all multi-task learning (MTL) problems. The authors should add explanations to clarify how these MTL problems are used to evaluate the performance of CMOO algorithms, including what the constraints are in these MTL problems.
4. The presentation of experimental results lacks detail. The authors should provide detailed explanations of Table 1 and Figure 1 to help readers understand experimental results. For example, the caption for Figure 1 is too brief, the authors should clarify the meaning of each subfigure in Figure 1.
5. The symbols in the submission are inconsistent. For instance, the $i^{th}$ objective function is denoted as $f_i(x)$ or $f^i(x)$.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: Please see "Weaknesses".
soundness: 3
strengths: 1. This paper is well-written and easy to follow.
2. The technical and mathematical details are clearly presented. The proofs are well-organized and seem correct.
3. This paper is novel and original, since constrained gradient-based MOO has not been well-studied.
summary: This paper proposes a gradient-based method for constrained multi-objective optimization, named MLM-CMOO. It is proved that the proposed method guarantees a convergence rate of $O(1/\sqrt{T})$. An empirical study demonstrates the effectiveness of the proposed method.
weaknesses: 1. In some parts of the text, "multi-objective optimization" is used, while in others, "multiple-objective optimization" is used. It is recommended that the author standardize the terminology.
2. The authors claim that the proposed method outperforms the state-of-the-art. It might be somewhat controversial to regard NSGA-II as state-of-the-art as it was proposed 20 years ago.
3. L38. The authors believe that gradient-free methods can not provide a convergence guarantee. I think gradient-free methods could also have a convergence guarantee under certain assumptions [1,2]. 
4. L51, "However, this transformation can not give a stable guarantee for the convergence rate as it may give the farthest Pareto front for the given coefficient." What does "farthest Pareto front" mean? Could you please provide some clarification for this claim or some references?
5. I think the title does not accurately reflect the contributions of this paper. The author could consider using "Gradient-based Constrained Multi-Objective Optimization" or "Constrained Multiple-Gradient Descent".
6. L397. The authors believe that NSGA-II cannot handle constraints. Actually, NSGA-II is originally designed to solve constrained problems [3].
7. The empirical study is not well-designed. The proposed method is compared with two black-box methods on deep learning tasks. I believe it is more reasonable to use gradient-based methods as baselines, for instance, [4, 5]. Some experimental details are missing, e.g., the population size of NSGA-II. 
8. From Fig. 1, I did not find that CMOO significantly outperforms the baselines. It is recommended to use some performance indicators to quantitatively measure the difference.
9. L406. Typo: $1e^{-5}$ --> $10^{-5}$.

References

[1] Zheng, Weijie, Yufei Liu, and Benjamin Doerr. "A first mathematical runtime analysis of the Non-Dominated Sorting Genetic Algorithm II (NSGA-II)." AAAI 2022.

[2] Do, Anh Viet, et al. "Rigorous runtime analysis of MOEA/D for solving multi-objective minimum weight base problems." NeurIPS 2023.

[3] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput., 2002.

[4] Liu et al., Profiling Pareto front with multi-objective stein variational gradient descent, NeurIPS 2021.

[5] Chen et al., Multi-Objective Deep Learning with Adaptive Reference Vectors, NeurIPS 2022.

---

confidence: 4
contribution: 1
initial_rating: 3
presentation: 2
questions: 1. How many independent runs have you carried our for each of the comparison algorithm? All those methods including those gradient based methods and NSGA-II are stochastic ones, different runs with the same parameter setup will produce different results. 

2. Have you considered other performance evaluation measures, such as HV and IGD, comparison of Pareto-fronts?

3. Ablation studies: your proposed method has several components. Which one plays more important roles than others? Are all of them useful? 

It seems that you submitted this paper in a hurry without completing it.
soundness: 2
strengths: MOO is a good topic and approach to processing multiple potentially conflicting objectives. This paper develops a new method toward this direction, which is good.

The paper also provides an convergence analysis, which seems to be theoretically demonstrating the the proposed algorithm can be converged.
summary: This paper describes a constrained multi-objective optimisation approach. Instead of using ordinary gradient based algorithms, this paper proposes a constrained gradient based one based on multiple gradient descent algorithms. The new approach seems to have a good convergence to Pareto solutions, and produced good results.
weaknesses: There are a number of weaknesses. 

1. Why do you consider gradient based approaches only in this paper to tackle multi-objective optimisation tasks? Under what conditions, gradient based methods are good? 

2. The number of objectives in all the datasets should be explicitly identified and described clearly. 

3. In your experiments, you compared the proposed method with NSGA-II and PSL. Why didn't you consider SPEA2 and MOEA/D?

4. The results are far from complete --- only Table 1 and Figure 1 are presented. Many interesting results such as the Pareto-fronts for each dataset, the hyper-volume or IGD comparisons are missing. It is not clear to me the comparison between those algorithms are fair. Only providing the loss and time values is not sufficient to understand the effectiveness of the proposed method.

---

confidence: 4
contribution: 1
initial_rating: 1
presentation: 2
questions: Does the assumption of a convex problem refer to the objective or search space?
According to Assumption 4.1, the individual objectives f_i need to be convex. Isn't this a very extreme assumption, which severely limits the contribution of this work as hardly any MOO problems will consist exclusively of convex components?
Within the experiments, MLM-CMOO has been benchmarked agains NSGA-II and PSL. How does MLM-CMOO perform in comparison to algorithms utilizing similar concepts or other gradient-based approaches? For instance, gradient ascend and gradient sliding methods could provide a fairer comparison.
Is T referring to the number of function evaluations, generations, runtime, ...?
In the literature, you find various works that investigate multimodality in MOO and also define various properties. Is the term "Pareto criticality" identical to a multi-objective "local optimum"? If so, why would you give it a different name?
The work emphasizes its focus on constrained MOO. However, why are constraints necessary in this context? Wouldn't this work look similar, if the problems would be unconstrained?
Table 1 measures the performance until a Pareto stationary point is reached. Again, this looks like a very special case, as one of the main challenges of MOO usually is to find a good approximation of the entire Pareto set (or front, respectively).
How often is each of the three algorithms executed per test problem?
soundness: 2
strengths: - The paper proposes a novel gradient-based algorithm for constraint MOO.
- The authors provide a proof sketch for the algorithm's convergence rate.
summary: In this paper, the authors propose a gradient-based algorithm for solving multi-objective optimization problems: MLM-CMOO. Moreover, under the assumption that both the individual objectives as well as the constraints are convex, the authors provide a proof in which they show the convergence rate of their algorithm to reach a Pareto stationary solution. At last, they conduct an experimental study, in which they evaluate their approach in comparison to two competitors, NSGA-II and PSL.
weaknesses: First of all, the paper title is entirely misleading. "Constrained Multi-Objective Optimization" sounds like a book title, or at least a PhD thesis, in which the entire research field is investigated from various perspectives, such as diverse benchmark problems, algorithmic approaches, visualization methods, performance measures, etc. However, this paper is limited to the gradient-based part of that research field and essentially focusses on the introduction of a new algorithm. 
Within this work it is stated that the goal of MOO is to find a Pareto stationary solution. However, as the optima of MOO problems usually consist of entire solution sets, the goal of algorithms usually is to find a good approximation of the solution set. Claiming that MOO focusses on finding a single solution would downplay the complexity of this research area.
The proposed approach has been designed for MOO problems that are (strongly) convex. Yet, it is not clear whether this property relates to the search or objective space. 
The usefulness of MLM-CMOO remains unclear, as real-world problems likely aren't compositions of purely (strongly) convex single-objective functions. As has been shown in various publications, concatenations of convex problems are a very special case, failing to capture the complexity of most MOO problems. By integrating a single multimodal (single-objective) function, the resulting MOO problem will have several local optima, which serve as traps for gradient-based approaches.
In the benchmark study, the proposed algorithm is compared to NSGA-II and PSL. However, NSGA-II is a population-based approach that evaluates multiple solutions per iteration. In consequence, it will likely take more time to converge. Also, population-based approaches such as NSGA-II are designed to find optima in complex black-box problems. If the problem is convex, gradient-based approaches will usually win such a comparison. Therefore, fair benchmark studies should consider state-of-the-art gradient-based approaches.
The convergence rate is indicated in relation to T, however, T is not specified/defined within the paper.
For citing, in multiple cases the wrong citing command has been used. For instance, it should be "The NSGA-II (Deb et al., 2002)" instead of "The NSGA-II Deb et al. (2002)".
The experimental analysis is kept extremely brief, providing hardly any insights.

Meta-review: The paper proposes a new gradient-based method, MLM-CMOO, for constrained multi-objective optimization (CMOO). It offers a convergence guarantee to Pareto stationary solutions with a rate of O(1/sqrt(T)). However, the paper's title is misleading as it focuses solely on a single algorithm rather than providing a broad overview of CMOO. The assumptions of convexity for objectives and constraints are overly restrictive, limiting the algorithm's applicability to real-world problems. The experimental setup compares MLM-CMOO with NSGA-II but lacks sufficient details and rigor, making it difficult to assess the algorithm's performance. The paper's contribution is considered limited due to these issues, and it is hence recommended for rejection.

Decision: Reject