3D Path Planning for UAVs in Dynamic Environments in the Presence of Uncertainties
Christian Zammit · Research Repository (Delft University of Technology) · 2021
Unmanned Aerial Vehicles (UAVs) are being integrated into all spheres of life, for a wide range of application in civil, commercial and military applications in both indoor and outdoor environments. UAV onboard intelligence is a paramount requirement in the realisation of UAV Traffic Management System (UTM) and Air Traffic Management (ATM) integration. The UAV onboard intelligence requirement is more envisaged in indoor applications where the use of Global Positioning Systems (GPS) is severely restricted and more complex localisation technology is required and traffic management systems are less supportive. For UAVs to be considered for specific tasks, their use must positively outweigh the use of other established, conventional systems. A key feature for UAVs would be a capability to perform autonomous, onboard real–time path planning. Path planning is defined as the process of automatically generating feasible and optimal paths to a predefined goal point in view of static and dynamic environmental and model constraints and uncertainties. This functionality allows UAVs to require minimal human intervention once its working environment and goals are defined. Therefore, autonomous and robust path planning is fundamental for UAVs to be considered for indoor applications in industrial, commercial, military and home applications. The need for autonomous path planning initiated with the introduction of robotics in industrial repetitive applications several decades ago. Since then, path planning extended outside factory floors evolving from 2D to 3D, operating in both static and dynamic environments with a wide spectrum of constraints and uncertainties. Path planning algorithms for autonomous vehicles can be broadly categorised into three main categories: Graph–based or Grid–based algorithms; Sampling–based algorithms and Interpolation algorithms. Although the use of UAVs has increased, the UAVs’ potential is far from reached. This can be mainly attributed to a number of challenges that have not been fully tackled and are hindering the use of small UAVs in indoor environments. This research will focus on path planning challenges in indoor, obstacle–rich environments with no UTM availability except for goal point definitions. In such scenario’s, the UAV is expected to operate using only onboard facilities. In this regard, three challenges are identified, which can be summarised as follows: Construct in real-time, non-colliding paths from the current UAV position to a goal position using only onboard UAV resources in the presence of both static and dynamic obstacles and in the presence of uncertainties. The following research goal is formulated to address these three challenges for the realisation of path planning algorithm of UAVs in indoor environments. Assess the performance of state-of-the-art path planning rationales in the context of UAVs operating in 3D real–time, dynamic indoor environments in the presence of uncertainty and identify a customised configuration based on the application. To tackle this research goal, five research questions are formulated: Research Question 1: What is the state-of-the-art in the field of path planning for UAVs in 3D and how do these algorithms compare? To investigate the potential of different path planning algorithms, the current state of-the-art in all fields of engineering are considered. The literature review shows that graph–based and sampling–based methods are potential candidates for 3D UAV path planning. The most often utilised algorithms from each category, that is the A* and Rapidly– Exploring Random Tree (RRT), and their variants, namely RRT without step size constraints and the Multiple RRT (MRRT) are tested in 3D scenarios of different complexity. A path smoothing interpolation algorithm is also developed to attenuate non–optimal paths, especially for the sampling-based methods. The same path smoothing algorithm is implemented on each path planning variant with the same parameters to offer a fair comparison. These algorithms are tested on the same set of different complexity 3D scenarios using the same computer. For comparison, the path length and the computational time are the considered performance measures. The A* with a spectrum of resolutions, the standard RRTwith different step–size constraints, RRT without step size constraints and the Multiple RRT (MRRT) with various seeds are implemented and their performance measures compared. For A*, tests show an inherent ripple in path length with change in resolution for all scenarios. This results due to the grid-based nature of the A* algorithm that creates situations in which a small increase in resolution, which theoretically shall slightly decrease the path length, effectively generates longer or shorter paths. This ripple is mitigated by randomly shifting the environment in all three dimensions by a distance varying between zero and half the distance between adjacent graph points. Results confirm that all algorithms are able to generate a path in all scenarios for all resolutions, step sizes and seeds considered. In comparison, the A* algorithm generates shorter paths in less time with respect to RRT algorithms, although the A* algorithm only explores areas necessary for path construction while RRT algorithms explore the environment evenly. Results show that A* outperformed the RRT, both in terms of path length and path generation time in offline situations with static obstacles, with 100% success rate for both in all scenarios considered. A* allows the environment to be discretised differently according to different exigencies of different parts of the scenario, making optimal use of resources. Oppositely, RRT and its variants are suited to generate paths efficiently in evenly distributed and focused 3D area exploration applications. Based on the results obtained, and their implication to UAV path planning, the second research question is tackled. Research Question 2: Can the selected path planning algorithms be applied in real-time static environments using the computational resources onboard small UAVs? This research question assumes that all path planning computation, sensing and environmental modelling and actuator controls must be computed onboard and in real–time. Another implication is that the path planner can only visualise the environment within the sensing distance determined by the on-board sensing systems and therefore can only construct, if possible, a path to an intermediate goal point. For the scope of this research question, a sphere equal to the sensing range of the UAV is considered, assuming that the sensing system has a 360 degrees field-of-view (FOV) in all three dimensions. It is further assumed that static obstacles within the sensing range are known with certainty, while other obstacles are unknown and become visible only if the UAV moves in their direction. To simulate real-time path planning, the computational time must be less than or equal to the time needed by the UAV tomove from the current position to a new position. The same test environment used to tackle Research Question 1 is used, using the same performance measures. Results show that the A* algorithm again outperforms the RRT algorithm in both path length and computational time for all scenarios considered, with the difference increasing with scenario complexity. A* is successful 90% or more of all tests for all scenarios considered provided the look-ahead distance is at least double the distance moved per iterate. In general, the RRT algorithmresults in a lower success rate than A* owing to the longer computational time required to construct intermediate paths with respect to A*. The UAV speed, sensor range and computational power are defined based on different studies that analyse these parameters onboard a range of UAVs [1–3]. The path planning results, based on these UAV parameters, show that 3D real-time path planning can be realised using only UAV onboard systems. The results outline the best empirical values for the different parameters. The setting of these parameters will configure the 3D real-time path planning platform, optimising its performance to each particular indoor application. Research Question 2 considered only static obstacles but in real UAV application obstacles can move and rotate, hence a dynamic environment needs to be considered to assess the usability of the developed 3D real-time UAV path planning algorithm. This requirement is investigated in the following research question: Research Question 3: What is the effect on path planning performance if static obstacles are replaced with dynamic obstacles? The inclusion of dynamic environments is external to the path planning algorithm but it can affect the path that the UAV will traverse. Dynamic obstacles within an indoor environment can be represented by symmetrical shapes. For the scope of this work, four different scenarios with different complexity are constructed. These incorporate rotating and non-rotating cubes, rotating V-shaped obstacles and static 2D planes with windows. Both obstacle movement and orientation are considered in the dynamic environment modelling. The random obstacle movement speed is assumed to be smaller than or equal to the speed of the UAV, as otherwise obstacle avoidance is not possible. A real-time environment with a limited range creates situations where an intermediat