3D Path Planning for UAVs in Dynamic Environments in the Presence of Uncertainties

Abstract

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 intermediate goal point is not available. In this regard, two different rationales are developed to mitigate this situation. In the waiting rationale, the UAV waits in its current position until the defined intermediate goal position becomes available. In the moving rationale, the intermediate goal position is moved closed to the current UAV position, consequently increasing the chances of the UAV moving closer to the final goal position. Both rationales are integrated within the A* and RRT path planning algorithms and tested in all scenarios with dynamic obstacles.

Results show that the moving option yields better overall results in terms of path
length, computational time and success rate for A* and RRT with respect to the waiting option. Both A* and RRT produce similar results in relatively simple scenarios with RRT recording better results in path length, computational time and success rate. For complex scenarios, the RRT is better if time is not limited while the A* algorithm is less susceptible to time constraints. Also, as speed increases in complex scenarios the success rate drops due to lack of path planning time in both A* and RRT.

The results show that the developed 3D real-time path planning platform with both A* and RRT algorithms has potential to be used in low obstacle density dynamic obstacle scenarios. The waiting variant is suited in situations where safety is paramount. In home environments, this is usually the case as the UAV cannot collide with obstacles, especially if these are humans. The moving variant would be ideal in situations where goal achievement is more important than safety. Such situations include search and rescue.

Until now it is assumed that no uncertainties are present within the UAV systems. In real scenarios a range of uncertainties are present. In the next research question, uncertainty in a UAV operating in an indoor environment is investigated.

Research Question 4: Do uncertainties affect 3D path planning of UAVs? If yes,
how can these uncertainties be modelled?

This research question queries whether uncertainties affect path planning of UAVs in indoor environments. This requires a thorough literature survey and consequently the identification and modelling of uncertainty sources that might affect path planning performance.

For the scope of this work, only uncertainties within the UAV model and the
environment (perceived through UAV onboard sensing systems), are considered. Other uncertainties, such as communication with user/s, are not considered as they are out of scope for this analysis.

Literature identifies the need for uncertainty consideration in real-time 3D UAV path planning, due to the possible negative implications on path planning performance if uncertainties are neglected. The fidelity with which uncertainties can be predicted is essential in determining the usability of the proposed path planning algorithms. Furthermore, literature portrays the bounding shapes and probabilistic distributions methods as key candidates for uncertainty modelling in UAV applications. After considering the characteristics of both methods, uncertainty is modelled using bounded shapes around the current UAV position and obstacle volume.

Once uncertainty sources are identified, estimated and modelled, the developed 3D real-time path planning algorithms are assessed in the presence of dynamic obstacles and uncertainties.

Research Question 5: Can uncertainties be mitigated to ensure collision-free 3D
path planning of UAVs in real-time in the presence of dynamic obstacles?
The same test environment constructed to assess Research Question 3 is considered using the same real-time 3D UAV path planning platform. Tests are performed using both A* and RRT path planning algorithms with the moving method. Uncertainty bounds are quantified based on literature and varied between 2% and 20% for both UAV position and obstacles. Uncertainty is included by adding an offset to the actual respective parameter. The effect of each uncertainty source will be analysed independently and collectively with dynamic obstacles to identify how real-time path planning algorithms can safely operate.

Results show that both sources of uncertainty (UAV position and obstacles), deteriorate path planning performance of both A* and RRT algorithms, for all scenarios considered, with RRT exhibiting the larger effect. The concurrent inclusion of both uncertainty sources further deteriorates path planning performance. RRT results in the fastest and shortest paths, with approximately the same success rate as A*, for relatively simpler scenarios, while A* performs better in the relatively complex case. Furthermore, RRT has a higher risk of collision than A* as RRT nears obstacles more often than A*.

From the results it is confirmed that uncertainty must be considered as it has an
effect on path planning performance. The accuracy with which uncertainty is modelled affects path planning performance for both path planning rationales considered.

In this thesis, each research question built on the previous one, in such a way to
reach the final research goal and tackling the research challenges. In the process of assessing the path planning performance (first part of research goal) of each algorithm, the response of each method with respect to each additional complication, can be independently analysed. This knowledge can be used to guide future UAV designers in selecting the best configuration, based on their application, hence reaching the second part of the research goal.

The implementation of the developed 3D real-time path planning algorithms to configure a real UAV for autonomous 3D UAV navigation in an indoor, obstacle-rich environment is the ultimate future goal that can lead into the commercialisation of this system for use in domestic applications. Moreover, this real-time 3D UAV path planning system can be proposed for integration in outdoor UAVs. Finally, this dissertation’s ultimate aim is to contribute in reducing the gap that still exists to integrate UAVs into domestic environments with the aim of improving current and future services that rely on UAVs with the ultimate aim of enhancing people in their daily lives.

REFERENCES
[1] Hrabar, S., “3D Path Planning and Stereo-based Obstacle Avoidance for Rotorcraft UAVs”, IEEE/RSJ International Conference on Intelligent Robots and Systems, Nice, France, 22-26 Sep. 2008, pp. 807-814.

[2] Yao, P.,Wang, H. and Su, Z., “Real-time path planning of unmanned aerial vehicle for target tracking and obstacle avoidance in complex dynamic environment,” Aerospace Science and Technology, Vol. 47, pp. 269-279, 2015.

[3] Ferguson, D. and Stentz, A. “Using interpolation to improve path planning: The field D* algorithm”, Journal of Field Robotics, Vol. 23, No. 2, pp. 79-101, 2006.