Comparison of A* and RRT in real–time 3D path planning of UAVs

Abstract

Unmanned Aerial Vehicles (UAVs) are being integrated into a wide range of military, industrial and commercial applications. Such applications require faultless autonomous systems to coordinate, guide, navigate and control different UAVs of different sizes, designed for different purposes with different capabilities. In this regard, different path planning algorithms were developed to ensure that UAVs are supplied with collision-free path paramount to which are the A* and the RRT algorithms, a graph-based and a sampling-based algorithm respectively. Such algorithms shall ideally operate in real-time to furnish the UAV navigation system with real-time, valid, obstacle-free paths in view of changes in the environment or other external or user-defined restrictions. Owing this need, in this paper a real-time platform to assess the performance of the A* and RRT algorithm with an associated smoothing algorithm was developed and tested using 3, 3D obstacle environment with different complexities. The salient user-defined, system-defined and internal constants were independently considered and their effect on performance assessed. Results showed that the A* outperformed the RRT algorithm in both path length and computational time for all scenarios considered with difference increasing with scenario complexity. But, both algorithms can be utilised if the associated parameters are attentively chosen based on the scenario the UAV will operate as both algorithm reached a 100% success rate for all scenario at specific parameter assignments.