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.
able to perform most of the tasks that are currently solved by manned aerial vehicles. And in Ukraine, due to the difficult political and economic situation, a deeply rational solution will be to use the methods of CO to increase the efficiency of such tasks for UAVs. Moreover, the rapid expansion of UAV applications in recent years has created a need for new classes of problems, like route building for swarms of UAVs, performing same task as a team etc.
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, the traveling salesman problem (TSP), that could be presented in
a graph where we look for a minimum length solution by visiting each node once and only once [
There is a large amount of literature on heuristic algorithms, i.e., algorithms designed to calculate
practically acceptable solutions of CO problems with no guaranteeing optimality. These heuristic
methods are very important, using in CO and some of them will be considered in this paper. The most
popular are the following [
According to current research, next types of NN are or were applicable for solving CO problems (some of them aren’t using for this task at modern time): • Hopfield Networks • Supervised learning • Unsupervised learning • Reinforcement learning • Deep learning
There are two popular ways for the ML use to solve CO problems – with and without expert knowledge. In this case, the decision-making function (DMF) is called a policy. DMF provides all present information (state of the environment, if the information able to describe the environment in enough details 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 CO algorithms 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.
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 NN is a fully connected, with a symmetric matrix of connections [
Such a network can be used as auto-associative memory, as a filter, and to solve many CO problems. Unlike many NN, which work to receive a response through a certain number of cycles, Hopfield networks work until equilibrium is reached, when the next state of the network is equal to the previous one.
Each neuron in the system yi can take one of two states (like the output of a neuron with a threshold activation function): 1 yi .
1
A limitation of Hopfield networks is that they are vulnerable to the problem of hyperparameters
[
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. This is how we may define learning process. This process may be completed by finding a solution for an optimization problem on a set 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 selected (for example, regression, classification, etc.) and optimization methods.
Let X and Y, which have a common probability distribution P, be variables for the input data and the objective function. Let ℓ be a minimization function of losses and let {fθ | θ ∈ Rp} is a set of ML models for CO (in this case, parametric). The problem of controlled learning is defined as: miRnp EX ,Y P (Y, f (X )). (2) 6.3.
In this type of learning [
Controlled learning is not applicable to most CO problems because it does not have access to
optimal distribution of source data. However, you can compare the quality of the solution set using an
evaluation data set for validation and determine the reward for the learning algorithm. Therefore, it is
possible to adhere to the paradigm of neural reinforcement learning (RL) to be used for finding
solutions of the CO problems. But unfortunately, even when we know optimal solutions of CO
problem already and may use this information as training 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 [
Sometimes it may be complicated to build the reward function. 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 (using some kind of policy, or just randomness) looking for the solution. In addition, when an approximate policy is applied (for example, using greedy search), RL does not have 100% probability of finding the best possible solution and may fall to local lows. 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. The output, given by the current layer, is known as the function of intermediate activation. This output is passed to the next layer.
All operations, presented on different layers are independent and may be shown as different matrices of coefficients. They are trainable, i.e., optimized with, for example, a stochastic gradient descent (SGD), an algorithm for obtaining minimum of the selected loss function. Stochasticity is generated by the finite number of data used to calculate losses before using SGD routine.
Deep neural networks (DNNs) may be difficult to optimize, 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 classical ML methods and algorithms, processing all present input data, for example, all pixels of the digital image file, to learn, while traditional ML usually requires the use of a limited number of features specific to a particular task.
DNN researchers have created various methods for adapting to a variety of structured input data in such a way as to process these input data of different dimension or size, for example – variable-length sequences.
Consider the following modern techniques.
The first presented architectures, applicable for CO problems, are 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. Individual layer uses as input two sets of data: first one is the activation vector, which is the output, generated by the previous layer. Second one is the actual activation vector at the previous stage of the sequence, as it is shown on Figure 1.
On the left side of the Figure 1, the dot of the black color presents a one-step delay. More detailed indication of this RNN layer with previous and next ones shown the right. U, V and W are parameters sets, which are presented and reused at each step of the RNN sequence.
One more important technique that makes the problem invariant to input data sizes is the attention
mechanism [
The classical mechanism of attention – the query q is calculated for a set of input values (vi)i. The f function is used for pairs of queries and sets of input data values. If it includes some parameters, the mechanism of attention is amenable to learning.
The affinity function takes a request at the input (which is any info type, used to find out, what exactly should be put into attention, where to focus) and a representation of the input set element (as we know, both will be used for the next layer) and produces a scalar. This process is happening on the set, including all its elements, and repeated for every other query. The obtained scalarized source data are normalized (for example, using the softmax function) and used to determine the operation result for 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 CO problems. Let us start with the RNN. 7.1.
Neural CO can be used to solve CO problems using RL. We will examine 2 possible approaches
based on gradient policy [
Second way of using RL for solving CO is an active search. It doesn’t involve prior RNN training.
The search begins with a randomly chosen way to build a solution (for example, greedy search) and
then from run to run optimizes the RNN parameters on a test data set, also using the expected reward
as a goal, while maintaining the best solution selected during the search. The combination of PTR and
active search provided best results after multiple practical comparisons [
There are different ways to use ML to solve 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 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 the case of using ML to obtain approximate solutions, policy is often taught using simulation training, through demonstrations, with data from the expert, provided 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, the policy learns to how to repeat success of the expert (trainer), looking for ways to obtain minimal 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, the policy can be trained using 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 (such as, for example, approximate dynamic programming algorithm or usage of the gradient policy) to get the best amount of reward that is possible to get. Alternative optimization methods, such as greedy algorithms, branch-and-bound, genetic algorithms, metaheuristic approaches, direct/local search, can be applied as well to find solutions of 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 is very important.
It is important to understand that when using simulation training, the NN learns with controlled goals set by the expert for each step of the algorithm (and without getting any reward), when in the case of experiential learning, the NN learns by receiving a reward (possibly with a delay) and using reinforced training (and without an expert). When using simulation training, the NN is taught what to do, while in training with reinforced NN, it is recommended to use rewards as main parameter and do the best trying to maximize it. However, it should be taken into account, that connections of these two parameters is a much more complex and broader issue than the information provided here.
Results of approaches to use NN for solving UAV CO problems comparison are presented in Table 1. 7.3.
NN can be used to improve the quality of solutions by improving the current local solution with
cutting planes (boundaries) [
After analyzing significant amount of heuristics, it could be said that a well-functioning approach
is the use of strong branching [
Considering the task of the TSP, that can be shown 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 containing up to 100 vertices, the RL for the travelling
salesman task significantly exceeds the controlled approach to learning [
On KnapSack problem, which is NP-hard, in [
Thus, the paper reviews the approaches to the use of NN in the problems of CO. 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 may be undoubtedly used for finding solutions of the CO problems. 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 CA problem for UAVs, 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