PATH PLANNING FOR UNMANNED AERIAL VEHICLES USING VISIBILITY LINE-BASED METHODS Thesis submitted for the degree of Doctor of Philosophy at the University of Leicester by Rosli bin Omar Control and Instrumentation Research Group Department of Engineering University of Leicester March 2011 Abstract PATH PLANNING FOR UNMANNED AERIAL VEHICLE USING VISIBILITY LINE-BASED METHOD Rosli bin Omar This thesis concerns the development of path planning algorithms for unmanned aerial vehicles (UAVs) to avoid obstacles in two- (2D) and three-dimensional (3D) urban environments based on the visibility graph (VG) method. As VG uses all nodes (vertices) in the environments, it is computationally expensive. The proposed 2D path planning algorithms, on the contrary, select a relatively smaller number of vertices using the so-called base line (BL), thus they are computationally efficient. The computational efficiency of the proposed algorithms is further improved by limiting the BL’s length, which results in an even smaller number of vertices. Simulation results have proven that the proposed 2D path planning algorithms are much faster in comparison with the VG and hence are suitable for real time path planning applications. While vertices can be explicitly defined in 2D environments using VG, it is difficult to determine them in 3D as they are infinite in number at each obstacle’s border edge. This issue is tackled by using the so-called plane rotation approach in the proposed 3D path planning algorithms where the vertices are the intersection points between a plane rotated by certain angles and obstacles edges. In order to ensure that the 3D path planning algorithms are computationally efficient, the proposed 2D path planning algorithms are applied into them. In addition, a software package using Matlab for 2D and 3D path planning has also been developed. The package is designed to be easy to use as well as user-friendly with step-by-step instructions. Acknowledgements First of all, thanks to Allah for the blessing and opportunity for me to successfully complete my studies. I would like to express my deepest gratitude to my thesis advisor Professor Da-Wei Gu for his continued guidance and support. His drive and enthusiasm for research is captivating, and he was able to continuously motivate me throughout this research. His insight and knowledge in the subject matter were invaluable to my success. I must also express my gratitude to the sponsors of this research effort namely The Ministry of Higher Education (MOHE) of Malaysia and Universiti Tun Hussein Onn Malaysia (UTHM). Their support is gratefully acknowledged. I would also like to thank my peers in the Control Systems Research laboratory including Dr. Halim Alwi, Naeem Khan, Mangal Kothari, Bharani Chandra, Dr Sajjad Fekri, Dr. Andrade Emmanuel and Dr. Georgios Kladis. All of them could be counted on to provide necessary insight into the research at hand. Special acknowledgement goes to my wife, Zaharah Mohamed Nor. She has given me unconditional support throughout my studies. Last but not least I would like to express my special thanks to my parents and family for their prayers and support. i Contents Acknowledgements i 1 Introduction ................................................................................................................. 1 1.1 Motivation ........................................................................................................ 1 1.2 Autonomy in UAV ........................................................................................... 3 1.3 Path Planning Overview and Issues ................................................................. 5 1.3.1 Criteria of Path Planning ........................................................................... 6 1.3.2 Path Planning Steps ................................................................................... 6 1.3.3 C-space Representation ............................................................................. 7 1.3.4 Graph Search Algorithms ......................................................................... 8 1.3.5 Real Time and Off-line Path Planning ...................................................... 9 1.4 Assumptions and Problem Statement ............................................................... 9 1.5 Thesis Contributions ...................................................................................... 10 1.6 Thesis Structure .............................................................................................. 11 2 Path Planning ............................................................................................................ 13 2.1 Introduction .................................................................................................... 13 2.2 Workspace Representation ............................................................................. 15 2.2.1 Configuration space ................................................................................ 15 2.2.2 C-Space Representation Techniques ....................................................... 18 2.2.3 Visibility Line ......................................................................................... 19 2.3 Graph Search Algorithms ............................................................................... 23 2.3.1 Depth-first Search ................................................................................... 23 ii 2.3.2 Breadth-first Search ................................................................................ 24 2.3.3 Dijkstra’s Algorithm ............................................................................... 25 2.3.4 Best-first Search ...................................................................................... 28 2.3.5 A*Algorithm ........................................................................................... 30 2.4 Path Planning Using Direct Optimisation Methods ....................................... 32 2.5 Real-Time Path Planning ............................................................................... 32 2.6 Path Planning in 3D Environment .................................................................. 33 2.7 Conclusion ...................................................................................................... 35 3 2D Path Planning Using Visibility Line-Based Methods ....................................... 37 3.1 Introduction .................................................................................................... 37 3.2 Visibility Line (VL) ....................................................................................... 39 3.2.1 Definitions and Algorithm ...................................................................... 39 3.2.2 Path Planning Using VL ......................................................................... 39 3.2.3 Advantages and Drawbacks of VL ......................................................... 41 3.3 Core Algorithm .............................................................................................. 43 3.3.1 The Idea of Core ..................................................................................... 44 3.3.2 Path Planning Using Core ....................................................................... 45 3.4 BLOVL Algorithm ......................................................................................... 51 3.4.1 The Idea of BLOVL ................................................................................ 51 3.4.2 Path Planning Using BLOVL ................................................................. 53 3.5 Performance Comparisons of VL and BLOVL .............................................. 57 3.6 BLOVL Path .................................................................................................. 62 3.7 Safety Margin ................................................................................................. 65 3.8 BLOVL for Real Time Path Planning ............................................................ 67 3.9 Improvement to BLOVL ................................................................................ 71 iii 3.10 Conclusion ...................................................................................................... 74 4 3D Visibility Line Based Path Planning .................................................................. 76 4.1 Introduction .................................................................................................... 76 4.2 Direct Applications of BLOVL 2D Path Planning Algorithm in 3D Environment .............................................................................................................. 77 4.2.1 p and p With Identical Altitude .................................................. 77 start target 4.2.2 p and p With Different Altitudes ................................................. 80 start target 4.2.3 Find a Path on a Vertical Plane ............................................................... 83 4.3 Path on the Base Plane ................................................................................... 85 4.3.1 Creating a Base Plane ............................................................................. 85 4.3.2 Finding Intersection Points ..................................................................... 88 4.3.3 Finding a 3D Path on the Base Plane ...................................................... 91 4.4 BLOVL 3D Algorithms ................................................................................. 94 4.4.1 Rotating a Base Plane ............................................................................. 97 4.4.2 3D Path Planning Using BLOVL3D2................................................... 100 4.4.3 BLOVL3D2 Performances ................................................................... 109 4.5 Conclusion .................................................................................................... 116 5 Software Packages for Path Planning ................................................................... 117 5.1 Introduction .................................................................................................. 117 5.2 The GUIs Aims ............................................................................................ 118 5.3 The GUIs Features ....................................................................................... 118 5.4 Path Planning using 2D GUI ........................................................................ 119 5.4.1 Operating the 2D GUI ........................................................................... 119 5.4.2 Real-Time Path Planning Using the GUI .............................................. 127 5.5 Path Planning Using 3D GUI ....................................................................... 131 iv 5.5.1 Operating the 3D GUI ........................................................................... 131 5.6 Conclusion .................................................................................................... 138 6 Conclusions and Future Work ............................................................................... 140 6.1 Conclusions .................................................................................................. 140 6.1.1 Path Planning in 2D environments ....................................................... 140 6.1.2 Path Planning in 3D environments ....................................................... 141 6.1.3 Path Planning Package for 2D and 3D environments ........................... 142 6.2 Future work .................................................................................................. 143 References ................................................................................................................... 144 v List of Figures Figure 1.1: Pathfinder UAV used for environmental research. ...................................... 1 Figure 1.2: A UAV, RQ-1 predator is equipped with missiles ....................................... 2 Figure 1.3: UAV autonomy levels and trend (adapted from [33]) ................................. 4 Figure 2. 1: A circular vehicle is transformed into a point in C-space ......................... 16 Figure 2.2: A scenario represented in (a) original form (b) configuration space. The darker rectangles in (a) are those with actual dimensions while in (b) are those enlarged according to the size of vehicle A. The white areas are the free space. ......... 17 Figure 2.3: Path planning representation techniques categories ................................... 18 Figure 2.4: A path planned by VL method ................................................................... 19 Figure 2.5: A summary of path planning methods based on VG .................................. 22 Figure 2.6: Graph search algorithms ............................................................................. 23 Figure 2.7: Depth-first search (adapted from [12]) ....................................................... 24 Figure 2.8: Breadth-First search (adapted from [12]) ................................................... 25 Figure 2.9: Dijkstra’s algorithm illustration ................................................................. 27 Figure 2.10: Illustration of Best-first search algorithm. ............................................... 29 Figure 2.11: Illustration of A* algorithm ...................................................................... 31 Figure 3.1: The algorithm to construct VL set .............................................................. 39 Figure 3.2: A randomly generated scenario for path planning ..................................... 40 Figure 3.3: The network of visibility line ..................................................................... 40 vi Figure 3.4: The path planned using Visibility line and Dijkstra’s algorithm ............... 41 Figure 3.5: A scenario with 2 rectangular obstacles ..................................................... 42 Figure 3.6: The numbers of obstacles in C-space increase the number of segments in VL ................................................................................................................................. 43 Figure 3.7: The process of Core ................................................................................... 44 Figure 3.8: The base line (dashed red) that is used to identify the obstacles for path planning ......................................................................................................................... 46 Figure 3.9: The network created by Core ..................................................................... 48 Figure 3.10: The planned path by Core ........................................................................ 48 Figure 3.11: BLOVL algorithm. ................................................................................... 51 Figure 3.12: BLOVL Algorithm ................................................................................... 52 Figure 3.13: The paths generated by Core and BLOVL ............................................... 54 Figure 3.14: The final path calculated by BLOVL. ...................................................... 55 Figure 3.15: Path planning complex and structured scenario ....................................... 56 Figure 3.16: The resultant paths calculated by (a) BLOVL, (b) VL ............................. 56 Figure 3.17: A scenario with increased number of obstacles ....................................... 57 Figure 3.18: A path generated by BLOVL ................................................................... 58 Figure 3.19: A path generated by VL ........................................................................... 58 Figure 3.20: Computation time of VL from different number of obstacles .................. 59 Figure 3.21: Computation time of BLOVL from different number of obstacles .......... 60 Figure 3.22: Comparison of VL’s and BLOVL’s computation time in log scale ......... 60 Figure 3.23: Paths lengths of VL and BLOVL in environments with different number of obstacles. ................................................................................................................... 61 Figure 3.24: A scenario for path planning. ................................................................... 62 Figure 3.25: The paths planned by BLOVL (black) and VL (magenta) ....................... 63 vii Figure 3.26: BLOVL updates the path as the path planning progresses. ...................... 63 Figure 3.27: BLOVL updates the path as the path planning progresses. ...................... 64 Figure 3.28: The paths planned by BLOVL (black) and VL (magenta) ....................... 64 Figure 3.29: A piece-wise linear segments path in the worst case scenario ................. 65 Figure 3.30: The enlarged obstacle with safety margin ................................................ 66 Figure 3.31: The obstacles with safety margin. ............................................................ 66 Figure 3.32: A path with safety margin generated by BLOVL .................................... 67 Figure 3.33: The scenario in which a real-time path planning will take place. ............ 68 Figure 3.34: BLOVL for real time path planning ......................................................... 69 Figure 3.35: The resultant path using BLOVL with a pop-up obstacle ........................ 70 Figure 3.36: BL identifies the obstacles to be used by BLOVL. .................................. 71 Figure 3.37: BL with limited range identifies the obstacles to be used by BLOVL .... 72 Figure 3.38: Computation time comparison between BLOVL and BLOVL with limited range ................................................................................................................. 73 Figure 3.39: Paths lengths comparison between BLOVL and BLOVL with limited range .............................................................................................................................. 74 Figure 4.1: A 3D environment with a 3D obstacle, in which the starting and target points have an equal altitude; (a) top view, (b) side view, (c) 3D view. ...................... 78 Figure 4.2: The visibility lines network; (a) top view, (b) side view, (c) 3D view. ..... 79 Figure 4.3: The 2D path (solid magenta lines) in 3D scenario; (a) top view, (b) 3D view. .............................................................................................................................. 79 Figure 4.4: A 3D environment with a 3D obstacle. (a) top view, (b) side view, (c) 3D view. .............................................................................................................................. 80 viii