Je-Kwan Park, Tai-Myoung Chung, Journal of Information Processing Systems Vol. 16, No. 6, pp. 1324-1342, Dec. 2020  

10.3745/JIPS.04.0196
Keywords: collision avoidance, Drone, Global Path Planning, Local Path Planning, Planner, Rapidly-exploring Random Tree (RRT), RRT* (RRT star), Torus, Unmanned Aerial Vehicle (UAV), Velocity Obstacle
Fulltext: PDF Full Text PubReader

Abstract

Various modified algorithms of rapidly-exploring random tree (RRT) have been previously proposed. However, compared to the RRT algorithm for collision avoidance with global and static obstacles, it is not easy to find a collision avoidance and local path re-planning algorithm for dynamic obstacles based on the RRT algorithm. In this study, we propose boundary-RRT*, a novel-algorithm that can be applied to aerial vehicles for collision avoidance and path re-planning in a three-dimensional environment. The algorithm not only bounds the configuration space, but it also includes an implicit bias for the bounded configuration space. Therefore, it can create a path with a natural curvature without defining a bias function. Furthermore, the exploring space is reduced to a half-torus by combining it with simple right-of-way rules. When defining the distance as a cost, the proposed algorithm through numerical analysis shows that the standard deviation (σ) approaches 0 as the number of samples per unit time increases and the length of epsilon ε (maximum length of an edge in the tree) decreases. This means that a stable waypoint list can be generated using the proposed algorithm. Therefore, by increasing real-time performance through simple calculation and the boundary of the configuration space, the algorithm proved to be suitable for collision avoidance of aerial vehicles and replanning of local paths.

Statistics
Cite this article