The paper reviews the ways and methods to the neural networks (NN) usage for solving combinatorial optimization (CO) problems, appearing when using unmanned aerial vehicles and based on their specifics. It is determined that the use of neural networks (with supervised learning, reinforcement learning and deep learning) is possible for many types of CO routing problems (salesman's problem, VRP problem in different versions, etc.) and other unmanned aerial vehicles CO problems. NN with reinforcement learning, as well as recurrent NN with controlled learning may be successfully used to directly solve combinatorial optimization problems mentioned above, or to adjust combinatorial optimization algorithms parameters.
Today, decision support tools are used more and more often all over the world, for example, in
transportation, military affairs, supply chains and logistics, energy, finance, and operations planning
[
Research and development of decision support tools, which are also called administrative
analytics, began during World War II as an initiative to use mathematics and computer science to help
military planners to make decisions [
Routing problems that arise when using UAVs has led to the appearance of numerous studies
conducted in recent decades. There were many attempts (including successful ones) to solve the
problems of CO with the use of ML. They were considered by relevant researchers and publications
all over the world [
As it was mentioned earlier, recently, significant progress has been made with the use of ML –
through in-depth training [
How NP-complex problems can be solved in a reasonable time? Let us consider the classical
example of an NP-complex problem, applicable for UAV routing task – the traveling salesman
problem (TSP). TSP may be defined in a graph where we look for a minimum length solution by
visiting each node once and only once [
Although theoretically Euclidean example of the problem is as complex as the general case of the
TSP, the approximate solution can be effectively found in Euclidean space using the structure of
graphs [
According to current research, next types of NN are applicable for solving UAV’ CO problems: • Hopfield Network • Supervised learning • Unsupervised learning • Reinforcement learning • Deep learning
There are two popular ways for the ML use to solve CO problems (and not only for UAV’ specific ones) – with and without expert knowledge. In this case, the decision-making function is called a policy that, given all available information (state of the environment, if the information is sufficient to fully characterize the environment at this step), issues output (possibly stochastically), which should be performed in the next step of the algorithm. Policy is a function that we want to teach with the help of ML. Consider how the above two motivations determine the parameters of learning.
The purpose of this work is to determine the applicability of NN to solve routing problems that
arise when using UAVs, i.e., to highlight promising areas of research of the NN usage to solve the CO
problems. NN can be successfully used for CA tasks that arise when using UAVs, primarily – when
planning routes for UAVs and especially – for UAV groups. This is because the task of constructing
routes and allocating points to be visited between vehicles is a classic CO task – the task of VRP
(Vehicle Routing Problem) [
Although, as mentioned above, the use of NN for solving the CO problems is actively studied all over the world, its use for UAV-specific tasks has not been studied enough to date.
The use of NN to solve the UAV-specific CA problems can improve the quality of the resulting solutions, which will increase the efficiency of the UAVs use in general and potentially – to expand the UAVs scope.
NN can help improve UAV-specific CO algorithms (and CO algorithms in general) in two ways. First, the researcher can use expert knowledge of the CO algorithm to replace resource-intensive calculations with rapid approximation. NN can be used to calculate such approximations. The challenge is to explore the space for possible solutions and thus be able to choose the appropriate policies that have led to the best of these solutions. Second, from the point of view of using NN to solve CO problems, NN can decompose the problem into smaller, simpler problems. For example, if we have group of UAVs that should visit set of points on the map (VRP problem), NN may be used to divide set of target points between UAVs. Then we would have to solve just a set of TSP problems (one per each UAV), which is much simpler task.
Let us consider features, specific for UAVs CO problems. Mostly such tasks are TSP or VRP problems, some other types also may be considered (for example, choosing optimal set of UAVs for completing some certain task), but this is outside the scope of this work. Therefore, for TSP/VRP problems, specific for UAVs, next features should be considered: • UAVs have limited time of work (limited maximum route length) – and if ground-based vehicle may wait some time without losing fuel (for example, in VRP with time windows when vehicle arrived at the point before time window start), for UAVs in most cases it is not possible – it can’t just land anywhere so would have to spend accumulator resource even while remaining on the same location; • For some tasks third dimension (altitude) should be taken into account, as it was described earlier; • Weather conditions affect UAVs more than ground vehicles or bigger airplanes, for example, wind (especially for small, lighter UAVs), cold (may affect UAVs accumulator capacity greatly) etc.; • UAV swarms are using more and more often, and therefore their specifics should be considered (which differs much from usual vehicles paradigm).
Now let us consider the main types of NN that can be used to solve UAV-specific CO problems. 6.1.
The first attempt to formalize the description of nerve cell function for applying in computational
algorithms was a model proposed in 1943 by McCulloch and Pitts. The McCulloch-Pitts model
became the starting point for building a simple unidirectional neural network called a perceptron.
Such a network was proposed and researched by Rosenblatt in the late 1950s and early 1960s. And in
1960, Adaline systems (Adaptive Linear Neuron) were proposed. Later, the Hopfield neural network
was suggested. The Hopfield neural network is a fully connected NN with a symmetric matrix of
connections [
In supervised learning during the input, we have a set of input data (functions) / target pairs, the task is to find the function of converting input data into output, which for each set of input data provides output that meets the specified constraints and has the value of the objective function closest to the target. Finding such a function is called learning and may be completed by solving an optimization problem on a family of available functions. The loss function, i.e., the degree of discrepancy between the source and target values, can be selected depending on the task (regression, classification, etc.) and optimization methods.
Mathematically speaking, let X and Y, which have a common probability distribution P, be random variables that represent the input data and the objective function. Let ℓ be a minimization function of losses and let {fθ | θ ∈ Rp} is a family of machine learning models for optimization (in this case, parametric). The problem of controlled learning is defined as:
A limitation of Hopfield networks is that they are sensitive to hyperparameters and parameter
initialization [
Supervised learning is completely applicable for UAV-specific CO tasks, first, for various versions of VRP problem, such as VRP with time windows, VRP with dynamic depos and so on. The only limitation that supervised learning have for UAV-specific problems is a general flaw of the supervised learning: pupil in most cases can’t overcome his teacher. It means that if target values for the problem are non-optimal, then NN after learning completion would also have non-optimal results. So, for complicated CO problems, for which we don’t have optimal solutions, supervised learning may not be the best solution to use. 6.3.
In unsupervised learning [
As it was said before, controlled learning is not applicable to the most UAV-specific CO problems
because it does not have access to the optimal distribution of source data. However, you can compare
the quality of the solution set using an evaluation data set for the validation and determine the reward
for the learning algorithm. Therefore, it is possible to adhere to the paradigm of neural reinforcement
learning (RL) to solve the UAV-specific CO problems. Moreover, even when using optimal solutions
as labeled data to optimize controlled learning, the quality of the results is quite poor compared to
machine RL, which receives a corresponding reward for good solutions [
Defining the reward function is not always easy, and UAV-specific tasks are not the exception. Because RL is built on a dynamic process, it is naturally able to anticipate states / transitions that lead to future rewards. However, the above setting of rewards is difficult and not always effective, as it does not allow learning until the agent (randomly or through advanced approaches) solves the problem. Therefore, at the first step of algorithm we would have to get some solution, that later we would improve. In addition, when an approximate policy is applied (for example, using linear functions), learning does not guarantee finding the optimal solution and may easily fall to local lows, so it should be considered as well. 6.5.
Deep learning is a method of constructing NN, consisting of the large number of layers. In the case of the simplest NN architecture, a NN with a direct connection, also called a multilayer perceptron (MLP), the input data is sequentially transmitted through several layers. For each layer on the input vector, an affine transformation is applied, followed by the application of a nonlinear scalar function (called the activation function). The output from the layer, called the intermediate activation function, is passed to the next layer. All affine transformations are independent and presented in practice as different matrices of coefficients. They are trainable, i.e., optimized using a stochastic gradient descent (SGD), an optimization algorithm used to minimize the selected loss function. Stochasticity comes from the limited number of data points used to calculate losses before applying a gradient update. Deep neural networks (DNNs) may be difficult to optimize, especially for UAV-specific VRP tasks, so several methods and approaches have been developed to make o better optimization, often by changing the architectural aspects of the network. Because DNNs have a large dimension amount, i.e., they can correspond to essentially any data set, they are prone to excessive content problem. DNMs are also subject to active regularization. Learning such networks with SGD also regulates them through gradient noise, which makes DNNs generally reliable for excessive content problems. In addition, there are many hyperparameters for DNN and various combinations of them are evaluated (this approach is known as hyperparameter optimization). DNNs move away from more traditional machine learning methods, using all available raw input data, such as all image pixels, to learn, while traditional ML usually requires the use of a limited number of features specific to a particular task.
Deep learning researchers have developed various methods for adapting to a variety of structured input data in such a way as to process variable-sized data structures, such as variable-length sequences, which is perfectly applicable for the UAV-specific VRP tasks.
Consider the following modern techniques.
The first presented architecture, applicable for UAV-specific CO tasks is recurrent neural networks (RNN). RNNs can work on sequential data by exchanging parameters at different stages of the sequence. More precisely, the same NN block is consistently applied at each step of the sequence, i.e., with the same values of architecture and parameters at each step of time. The specificity of such a network is the presence of repeating layers: layers that take as input both the activation vector from the previous layer and the actual activation vector at the previous stage of the sequence (it is called the hidden state vector), as illustrated in Figure 1. On the left, a black square indicates a one-step delay. On the right, the same RNN is shown unfolded. Three sets of parameters U, V and W are presented and reused at each step.
Another important technique that makes the UAV-specific problem invariant to input data sizes is
the attention mechanism [
The affinity function takes a request at the input (which is any kind of contextual information and informs where to focus) and a representation of the input set element (both are activation vectors) and outputs a scalar. This process is repeated over all elements of the set for the same query. The obtained scalarized source data are normalized (for example, using the softmax function) and used to determine the weighted sum of the representations of the elements in the set. This weighted amount, in turn, can be used in the NN.
The attention mechanism can be used to construct NNs of graphs, i.e., NNs capable of processing
structured input data of graphs [
Deep learning and RNN can be used for supervised, unsupervised or reinforced learning [
There are several approaches of using NN for solving UAV-specific CO problems. Let us start with the RNN. 7.1.
Neural CO can be used to solve UAV-specific CO problems using RL. Let us consider two
approaches based on gradient policy [
The second approach, called active search, does not involve prior RNN training. The search begins
with a random policy and iteratively optimizes the RNN parameters on a single UAVs routes test
instance, also using the expected reward as a goal, while maintaining the best solution selected during
the search. The combination of PTR and active search works best in practice [
There are different ways to use ML to solve UAV-specific CO problems. There are two main motivations for using ML: approximation and the creation of new policies. There are also various ways to combine ML and traditional algorithmic elements.
As it was mentioned earlier, there are two main ways of ML usage – with and without expertise knowledge. Both motivations are identified within the MDP states/actions described in the reinforced learning section. In this case, the decision-making function is called a policy that, given all available information (state of the environment, if the information is sufficient to fully characterize the environment in the MDP at this step), issues output (possibly stochastically), which should be performed in the next step of the algorithm. Policy is a function that we want to teach with the help of ML. In the case of using ML to obtain approximate solutions, for example, for UAVs VRP problem, policy is often taught using simulation training, through demonstrations, with expert behavior shown (demonstrated) by the ML model. This process is illustrated in Figure 3. When using this approach, the NN is trained not to optimize performance, but to blindly follow the actions of the expert.
When using simulation training (not only for UAV-specific tasks, but in general), the policy learns to reproduce the actions of expert policy by minimizing some differences in the space of action.
In the case where the goal is to create new policies, i.e., to optimize the solution-finding function from the scratch, as it is often needed for complicated UAV-specific problems, the policy can be learned through reinforcement learning, as shown in Figure 4. Even if we present the problem of learning under the main MDP through RL, this does not limit the use of basic RL algorithms (approximate dynamic programming and gradient policy) to maximize the expected rewards amount. Alternative optimization methods, such as greedy algorithms, genetic algorithms, direct/local search, can also be used to solve RL problems.
In the case of RL a reward signal is used, no expert participates in the training process; only the maximization of the expected amount of future rewards (return) matters.
It is important to understand that when using simulation training, the NN learns with controlled goals set by the expert for each action (and without reward), whereas in the case of experient ial learning, the NN learns by receiving a reward (possibly with a delay) and using reinforced training (without an expert). When using simulation training, the NN is taught what to do, while in training with reinforced NN, it is recommended to quickly accumulate rewards. The distinction between these two parameters is a much more complex and broader issue than the information provided here, and should be considered in general, not only for mentioned UAV-specific tasks. Results of approaches to use NN for solving UAV-specific CO problems comparison are presented in Table 1. 7.3.
NN can be used to improve the quality of solutions (including for TSP and various VRP problems,
specific for UAVs) by improving the current local solution with cutting planes (boundaries) [
Among many heuristics, a well-functioning approach is the use of strong branching [
Considering the task of the TSP for UAV route, presented on the graph described above, it is easy
to make a greedy heuristic that builds a route, consistently selecting nodes among those that have not
yet been visited, and therefore, building a permutation. The choice of the nearest node is an intuitive
choice of criterion, but in most cases, it is far from optimal. Therefore, a greedy heuristic structure is
built, where the node selection policy is studied using NN on a graph, a type of NN capable of
processing at the input of a graph of any limited size using a message transmission mechanism [
On a two-dimensional Euclidean graph, described above, containing up to 100 vertices that UAV
should use, the RL for the TSP significantly exceeds the controlled approach to learning [
Thus, the paper reviews the approaches to the use of NN in the UAV-specific CO problems. It is determined that the use of NN (including deep learning NN) is possible in the tasks of CO for UAVs in routing problems, so they can be used to solve problems that arise when planning the operation of UAVs. At the same time, recurrent NNs with nonparametric normalized exponential functions of controlled learning are successfully used to solve the problems of CO. It has been determined that the most effective to date is the use of RL training to solve such problems. This method is recommended to use. Prospects for the use of research results: preparing mathematical model of the specific UAVspecific CA problem, developing an algorithm for solving this problem using the proposed NN architecture and comparing the results with the results of classical methods for solving such CA problem. 9. References