UAV Path Planning with Derivative of the Heuristic Angle
- PDF / 2,758,964 Bytes
- 11 Pages / 595.276 x 790.866 pts Page_size
- 49 Downloads / 166 Views
ORIGINAL PAPER
UAV Path Planning with Derivative of the Heuristic Angle Daehee Lim1 · Jihoon Park1 · Dongin Han1 · Hwanchol Jang2 · Wontae Park3 · Daewoo Lee1 Received: 31 March 2020 / Revised: 6 September 2020 / Accepted: 14 September 2020 © The Korean Society for Aeronautical & Space Sciences 2020
Abstract This paper introduces improved weighted A* (WA*DH), an advanced version of the weighted A* (WA*). To increase the performance of WA*, we suggest a new parameter, the heuristic angle, which is defined as the angle between the direction of an nth node to the target and the direction of the heading from the (n−1)th node to the nth node on the path. The process of WA*DH involves searching nodes that degrade the optimality of the generated path using the derivative of the heuristic angle, and then searching for escape nodes that avoid an obstacle. Finally, local re-planning of the path is performed using the nodes obtained in the aforementioned two steps. We can verify that the cost of WA*DH is lower than WA*, although the elapsed time is not shorter than WA* because of the additional procedures. Keywords Path planning · Weighted A* · Heuristic angle · Heuristic search
1 Introduction The is an essential part of unmanned aerial vehicles (UAVs), self-driving cars, and robot applications such as the aeromedical evacuation of injured people in crisis situations and air campaign planning [1–5]. The purpose of path planning is to determine the shortest path to a goal so many path planning algorithms were developed [6, 7]. A* algorithm was suggested in 1968 to satisfy this demand [8]. A* algorithm is very popular as a kind of node-based algorithm, and can get an optimal path faster than Dijkstra’s algorithm because heuristic concept is used. Also, A* algorithms was popular because of its high optimality compared to other algorithms such as sampling based algorithms such as rapidly exploring random tree (RRT), probabilistic roadmap (PRM), bioinspired algorithms such as genetic algorithm (GA), and particle swarm optimization (PSO) [6, 7]. However, A* spends so much time to get a solution. Many real-world situations such as path planning problems in unknown terrain, artificial intelligence require strict real-time constraints and quick react regardless of the map size and the complexity of the map.
B
Daewoo Lee [email protected]
1
Pusan National University, Pusan, Republic of Korea
2
Agency for Defense Development, Daejeon, Republic of Korea
3
Cheongju University, Cheongju, Republic of Korea
Researchers tried to reduce the elapsed time to use heuristic search algorithms in real-time situation. As a result of the effort, some algorithms such as lifelong planning A* (LPA*), time-bounded A*(TBA*), and learning real-time A* (LRTA*) were developed for real-time use [9–12]. Among these algorithms, WA*, which is a type of bounded suboptimal search was developed to a solution as fast as possible rather than finding an optimal solution [13, 14]. WA* reduced the elapsed time of A* significantly with the idea of inflation
Data Loading...
