ETH Library Path Planning for Fixed-Wing Unmanned Aerial Vehicles Master Thesis Author(s): Schneider, Daniel Publication date: 2016 Permanent link: https://doi.org/10.3929/ethz-a-010646508 Rights / license: In Copyright - Non-Commercial Use Permitted This page was generated automatically upon download from the ETH Zurich Research Collection. For more information, please consult the Terms of use. Autonomous Systems Lab Prof. Roland Siegwart Master Thesis Path Planning for Fixed-Wing Unmanned Aerial Vehicles Autumn Term 2016 Supervised by: Author: Philipp Oettershagen Daniel Schneider Enric Galceran Yebenes Declaration of Originality I hereby declare that the written work I have submitted entitled Path Planning for Fixed-Wing Unmanned Aerial Vehicles isoriginalworkwhichIalonehaveauthoredandwhichiswritteninmyownwords.1 Author(s) Daniel Schneider Student supervisor(s) Philipp Oettershagen Enric Galceran Yebenes Supervising lecturer Roland Siegwart With the signature I declare that I have been informed regarding normal academic citationrulesandthatIhavereadandunderstoodtheinformationon’Citationeti- quette’(https://www.ethz.ch/content/dam/ethz/main/education/rechtliches- abschluesse/leistungskontrollen/plagiarism-citationetiquette.pdf). The citation conventions usual to the discipline in question here have been respected. The above written work may be tested electronically for plagiarism. 9XXMKIR(cid:16)(cid:4)(cid:20)(cid:22)(cid:4)1E](cid:4)(cid:22)(cid:20)(cid:21)(cid:26) Place and date Signature 1Co-authored work: The signatures of all authors are required. Each signature attests to the originalityoftheentirepieceofwrittenworkinitsfinalform. i Contents Abstract iv Symbols, Notation, Terms And Definitions vi 1 Introduction 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Goal of this thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 Background 4 2.1 Terms and definitions . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Motion planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2.1 Problem formulation . . . . . . . . . . . . . . . . . . . . . . . 6 2.2.2 Sampling-based motion planning . . . . . . . . . . . . . . . . 7 2.2.3 Geometric planning . . . . . . . . . . . . . . . . . . . . . . . 9 2.2.4 Control-based planning . . . . . . . . . . . . . . . . . . . . . 9 2.2.5 Informed sampling . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2.6 Sampling-based motion planning algorithms . . . . . . . . . . 14 2.3 Optimality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.4 Collision checking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.4.1 Flexible Collision Library . . . . . . . . . . . . . . . . . . . . 21 2.4.2 Height checking . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.5 System dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.5.1 Dubins car . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.5.2 Dubins airplane . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3 Path planning method 28 3.1 Software structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.2 Collision checking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.3 Airplane motion model . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.3.1 Non-optimal Dubins airplane paths . . . . . . . . . . . . . . . 31 3.3.2 Dubins set classification . . . . . . . . . . . . . . . . . . . . . 32 3.3.3 Dubins airplane state space for OMPL . . . . . . . . . . . . . 32 3.4 Path planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.4.1 Control-based planning . . . . . . . . . . . . . . . . . . . . . 35 3.4.2 Informed sampling . . . . . . . . . . . . . . . . . . . . . . . . 36 3.4.3 Dubins airplane adapted sampling . . . . . . . . . . . . . . . 36 3.4.4 Combining the use of straight lines and non-optimal Dubins airplane paths . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.4.5 Forward propagation . . . . . . . . . . . . . . . . . . . . . . . 38 3.4.6 Optimal fast marching tree using non-optimal Dubins air- plane paths (D-FMT*). . . . . . . . . . . . . . . . . . . . . . 39 ii 3.5 Manual code optimization . . . . . . . . . . . . . . . . . . . . . . . . 41 4 Experiments and results 42 4.1 Parameter tuning for planners . . . . . . . . . . . . . . . . . . . . . . 42 4.2 Preliminary results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4.2.1 FCL and height checking . . . . . . . . . . . . . . . . . . . . 44 4.2.2 Determine the time complexity of FMT* . . . . . . . . . . . 46 4.2.3 Non-optimal vs. optimal Dubins airplane paths . . . . . . . . 46 4.2.4 Manual code optimizations . . . . . . . . . . . . . . . . . . . 49 4.3 Final results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.3.1 Block experiment . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.3.2 Gap experiment . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.3.3 Random map experiment . . . . . . . . . . . . . . . . . . . . 53 4.3.4 Slalom experiment . . . . . . . . . . . . . . . . . . . . . . . . 55 4.3.5 Mountain experiment . . . . . . . . . . . . . . . . . . . . . . 57 4.3.6 Kandervalley experiment . . . . . . . . . . . . . . . . . . . . 61 4.4 Summary and analysis of the experiments . . . . . . . . . . . . . . . 63 5 Conclusion and future work 69 5.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.2 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 Bibliography 81 A Additional material 82 A.1 Proof: Eq. 3.6 is a pseudometric . . . . . . . . . . . . . . . . . . . . 82 A.2 Proof: The length of non-optimal Dubins airplane paths is a premetric 82 B More results 84 B.1 Block experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 B.2 Gap experiment. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 B.3 Random map experiment . . . . . . . . . . . . . . . . . . . . . . . . 85 B.4 Slalom experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 B.5 Mountain experiment. . . . . . . . . . . . . . . . . . . . . . . . . . . 85 B.6 Kandervalley experiment . . . . . . . . . . . . . . . . . . . . . . . . . 93 Abstract This thesis presents a first implementation of a real-time capable onboard path planningframeworkcomputingshortestpathsforfixed-wingaerialvehiclesformany start-goal configurations. The framework provides kinodynamic planning based on the Dubins airplane motion model. TheframeworkisimplementedasaROSnodewhatmakesitexecutableoncommon companion-computers installed on fixed-wing aerial vehicles. We evaluated 8 different sampling-based motion planning algorithms in theoretical andrealexperimentalsetups. Twonewideastoreducethetimeforfindingshortest pathsfortheDubinsairplaneareexplainedandcomparedagainstexistingplanning methods. Ontheonehand,theinformedsubsetoftheDubinsairplaneforminimum pathlengthisapproximatedasasubsetoftheinformedsubsetforasystemwithout differential constraints. On the other hand, in order to find initial paths as fast as possible,theinitialpathisplannedusingstraight-lineconnectionsbetweensamples insteadofdynamicallyfeasiblepaths. AmodificationtotheoptimalFastMarching Treealgorithm(FMT*)ispresented. Themodificationallowstopredicttheamount of samples workable in the time available for planning and thereby makes FMT* usable for real-time and onboard path planning. Experimentshaveshownthatplanninginitialpathswithstraightlinesandapproxi- matingtheinformedsubsetfortheDubinsairplaneforminimumpathlengthallows findinginitialpathsinlessthan1secondandexpeditestheconvergencetotheopti- mal path such that after 2 seconds reasonably short paths are found. Furthermore, planners iteratively drawing one sample at a time, e.g. optimal Rapidly-exploring Random Tree (RRT*), perform better than planners drawing batches of samples, e.g. Batch Informed Tree (BIT*), if planning in wide open spaces. For cluttered, narrow and twisted maps, it is the other way round. Additional experiments have shown that computing non-optimal paths for start-goal configurations occurring rarely in real application scenarios, speeds up the computation of the paths up to 40 times. Further experiments have shown that using a light collision checking algorithm reduces the time spent for collision checking more than 10 times. iv Acknowledgement I would first like to thank my thesis advisors, Philipp Oettershagen and Enric Galceran Yebenes of the Autonomous Systems Lab at ETH in Zurich, who steered me in the right direction and supported my work with a lot of helpful answers and bright ideas. I also owe much to Prof. Dr. Roland Siegwart, the Autonomous Systems Lab and all members thereof, who made this thesis possible and in some way promoted it. Finally, I must express my profound gratitude to my parents, siblings, cousins and friends for providing me with permanent support and continuous encouragement throughout this thesis. v Symbols, Notation, Terms And Definitions Symbols φ,ψ,θ Roll, pitch and yaw angle C Configuration space q Configuration q Start/ initial configuration I q Goal configuration G X State space x State x Start/ initial state I x Goal state G x x-component of a configuration q or state x y y-component of a configuration q or state x z z-component of a configuration q or state x Θ Yaw-component of a configuration q or state x c Minimum possible cost of a path connecting start and goal in obstacle-free space min c Cost of current best path best r Minimum turning radius of the Dubins airplane min γ Maximum climb and sink angle of the Dubins airplane max Acronyms and Abbreviations ETH Eidgen¨ossische Technische Hochschule ASL Autonomous Systems Lab UAV Unmanned aerial vehicle RRT Rapidly-Exploring Random Tree FMT Fast-Marching Tree BIT Batch Informed Tree KPIECE Kinodynamic Motion Planning by Interior-Exterior Cell Exploration BVP Boundary value problem RRT Rapidly-exploring Random Tree RRT* Optimal Rapidly-exploring Random Tree FMT* Optimal Fast Marching Tree BIT* Batch Informed Tree vi