 ICACT20230128 Slide.00
[Big Slide]
[YouTube] |
Chrome  Click!! |
 |
Hello everybody, this is Junqi Bao from Macau Polytechnic University. The topic of my paper is Path planning for Cellular-connected UAV using Heuristic Algorithm and Reinforcement Learning.
|
| ICACT20230128 Slide.01
[Big Slide]
|
Chrome Click!! |
 |
The content of this presentation is divided into 4 parts. In the first part, I want to introduce the introduction of this research. In the second part, I will talk about the proposed method in detail. The experiment results are demonstrated in the third part. And finally, in the last part, I will give a short conclusion to this paper.
|
| ICACT20230128 Slide.02
[Big Slide]
|
Chrome Click!! |
 |
I will start with the introduction part |
| ICACT20230128 Slide.03
[Big Slide]
|
Chrome Click!! |
 |
Traditional UAVs relies on simple point-to-point (P2P) wireless links to communicate with the ground base station (GBS), which may cause some problems such as low data rate transportation, system vulnerability, and so on. Previous research usually transforms the 3-Dimension traditional path planning into a Shortest Path Problem in graph theory and uses some algorithm such as A Star algorithm to solve an SPP. With the research on the cellular network, 4G and 5G have been proven useful and ultra-reliable in long-range communication, especially for UAVs. To enhance the data transportation performance between UAV and GBS, a novel technology called cellular-connected UAV has been developed. How to plan a path for UAV while maintaining a cellular network became a hot problem. In this case, we propose to abstract this problem into a Travel Salesman Problem, TSP defines a question of giving a list of cities and the distances between each pair of cities, which is the shortest possible route that a salesman can visit each city and returns to the origin city. In other words, it is to find the shortest path to traveling each point from a start point to an endpoint. The way to find the answer to TSP is to find all the possible paths first and choose the best path from the possible paths.
|
| ICACT20230128 Slide.04
[Big Slide]
|
Chrome Click!! |
 |
Then I will talk about the proposed method in detail. |
| ICACT20230128 Slide.05
[Big Slide]
|
Chrome Click!! |
 |
We first construct a grid map base on the signal coverage area as the Figure demonstrates. The white areas are the cellular network coverage area, and each area is tangent. UAVs have to fly over the signal coverage area from a start point to an endpoint. To maintain the cellular network, the UAV is not allowed to fly over the black areas. In our scenario, we assume that there are 6 cellular network ground base stations, and there are a total of N cities covered by the cellular network.
|
| ICACT20230128 Slide.06
[Big Slide]
|
Chrome Click!! |
 |
As for the data, each data contains the coordinates of N cities. We randomly create 128K data with N = 20 for training data. And 1K data with N equals 5, 10, 20, and 50 respectively for testing data.
|
| ICACT20230128 Slide.07
[Big Slide]
|
Chrome Click!! |
 |
The first step of the proposed method, is generating the distance matrix. We use A Star to find the shortest path between each of the 20 cities. Since we are using a grid map, so the distance is calculated by the Manhattan distance. We have 128K data, so there are 128K distance matrix total. Then the next step is to find the best path from the distance matrix. We consider to use Heuristic Algorithm and Reinforcement Learning to achieve this goal. Genetic Algorithm and Simulated Annealing Algorithm are two famous Heuristic Algorithm to process these problems. Thus we use these two algorithm in our method. Then we design an Actor-Critic Structure reinforcement learning model.
|
| ICACT20230128 Slide.08
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
A * search is an optimal path search algorithm using Grid Map. According to the form f(n)= g(n)+ h(n), A* search will operate on 8 neighbors of the center at each step where f(n) is the evaluation function, g(n) is the cost of moving from the starting point to the specified point. H(n) is the estimated distance from the current node to the endpoint, which is an estimate of the remaining distance, not the actual value. It is an ideal value that ignores the effect of obstacles. In order to estimate h(n), there are three kinds of distance metrics can be used in path planning which are Euclidean Distance, Manhattan Distance, Chebyshev Distance.
In our scenario, we choose Manhattan Distance to metric the distance between two points, which can be formulated by this formula. The Manhattan Distance can be used to measure the distance of a point that can be reached in four directions to another point.
This Figure shows the results of path planning using A* while the green square is the start point, the red square is the end point and the blue point is the obstacles. Also, the green border squares are points in the open list, yellow border squares are points in the close list, the yellow arrow in the square points to the father node, and the number in the upper left corner of the square represents the F value, the G value in the lower left corner, and the H value in the lower right corner.
|
| ICACT20230128 Slide.09
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
Genetic Algorithm (GA) is an intelligent optimization algorithm, mainly used to solve optimization problems. The steps of GA can be concluded as follows:
The process begins with a set of the individual called population. An individual consists of a set of character which is gene. In TSP, an individual represented by a sequence of number means the order that UAV visits each city, a gene means a city number. A fitness function determines how fit an individual is, it will give a fitness score for every individual, a sequence with a shorter tour length means higher fitness score. And then the selection phase will select several individual for the reproduction, individuals which have higher fitness score will have a higher probability to be selected. After selection, and crossover phase with process crossover for each pair of parents, which means exchange genes based on crossover points between two sequences be selected in the previous step. Those parents and offspring formed a new generation. In certain offspring, a mutation occurs, some positions of gene changes randomly, in TSP mean gene swapping at two positions. This process will repeat until the set of iteration is reached.
The Simulated Annealing Algorithm is a general probabilistic algorithm for finding the optimal solution in a large search space [19]. It is a stochastic optimality-seeking algorithm based on the Monte- Carlo iterative solution strategy. Simulated annealing algorithm is one of the effective methods to solve TSP problems. The steps of SA are:
Start with an initial solution 𝑠_0 which is calculated by A* and an initial temperature 𝑡_0.
Choose a temperature reduction function:
Given a new solution 𝑠_1 , which is a neighbor of 𝑠_0 , calculate the difference in cost between 𝑠_0 and 𝑠_1.
If 𝑠_1 is better than 𝑠_0, then accept 𝑠_1. If 𝑠_0 is better, than generate a random number 𝑟 from 0 and 1. Then we calculate the probability of accepting 𝑠_1 by 𝑝=𝑒^(−|𝑠_0−𝑠_1 |/𝑡_0 )
If 𝑟 < 𝑝 , then accept 𝑠_1. If not, go back to Step 3.
Output the best optimal solution.
|
| ICACT20230128 Slide.10
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
Since TSP is an NP-Hard Problem, it can be solved by a reinforcement learning model. In this case, we propose to use Actor-Critic Structure to solve this problem. The actor-Critic Structure is made up of an Actor-network and Critic Network. We use a Pointer Network as the Actor-Network. Then we design an RNN model with LSTM to achieve Critic Network.
|
| ICACT20230128 Slide.11
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
Then I will talk about the experimental results.
|
| ICACT20230128 Slide.12
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
First, we have calculated the mean time searching for the best path as the Table demonstrates. The reinforcement Learning method uses the least time to find the best path in all cases.
|
| ICACT20230128 Slide.13
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
Except searching time, we also calculated three main evaluation metrics, MAE RMSE and MAPE. The formula is given here.
MAE (Mean Absolute Error) is a measure of errors between paired observations expressing the same phenomenon. MAE represent the actual situation of the error of calculated distance.
RMSE (Root Mean Square Error) is the square of the difference between the true value and the predicted value, and then the average of the sum, RMSE reflect the sample standard deviation of the difference between the calculated optimal path and the true optimal path.
MAPE (Mean Absolute Percentage Error) represent the precision of the path planning algorithm.
|
| ICACT20230128 Slide.14
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
As the table demonstrate, Simulated Annealing Algorithm is the best in all cases in terms of RMSE MAE and MAPE. Since the model is trained in TSP20 data, the Genetic Algorithm perform better than Reinforcement Learning in TSP5, TSP10 and TSP20. However, Reinforcement Learning is much better than Genetic Algorithm in the scenario of TSP50. Although Reinforcement Learning is not good enough, but it is faster than both Genetic Algorithm and Simulated Annealing Algorithm. We consider that there are still lots of room for reinforcement learning method to improve in the future.
|
| ICACT20230128 Slide.15
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
Finally, I will give a short conclusion.
|
| ICACT20230128 Slide.16
[Big Slide]
|
Chrome Click!! |
 |
In conclusion, in this work, we propose to plan a path for cellular-connected UAV by solving a Travel Salesman Problem and we propose to use a Heuristic algorithm and Reinforcement Learning to solve the problem. Then the experimental results indicated that Reinforcement Learning Method is faster than Genetic Algorithm and Simulated Annealing Algorithm. However, the simulated Annealing Algorithm is the most accurate method in all cases. We think that there are still lots of room for Reinforcement Learning to improve in the future. If the scenario requires time complexity, Reinforcement Learning is more fittable. And if accuracy is required, the Simulated Annealing Algorithm is more fittable. |
| ICACT20230128 Slide.17
[Big Slide]
[YouTube] |
Chrome Click!! |
 |
Thanks for watching.
|
