This thesis project investigates a method for performing dynamic path planning in three dimensions, targeting the application of autonomous unmanned aerial vehicles (UAVs). Three different path planning algorithms are evaluated, based on the framework of rapidly-exploring random trees (RRTs): the original RRT, RRT*, and a proposed variant called RRT-u, which differs from the two other algorithms by considering dynamic constraints and using piecewise constant accelerations for edges in the planning tree. The path planning is furthermore applied for unexplored environments. In order to select a path when there are unexplored parts between the vehicle and the goal, it is proposed to test paths to the goal location from every vertex in the planning graph to get a preliminary estimate of the total cost for each partial path in the planning tree. The path with the lowest cost given the available information can thus be selected, even though it partly goes through unknown space. For cases when no preliminary paths can be obtained due to obstacles, dynamic resizing of the sampling region is implemented increasing the region from which new nodes are sampled. This method using each of the three different algorithms variants, RRT, RRT*, and RRT-u, is tested for performance and the three variants are compared against each other using several test cases in a realistic simulation environment. Keywords / Detta examensarbete undersöker metoder för att utföra dynamisk ruttplanering i tre dimensioner, med applicering på obemannade luftfarkoster. Tre olika ruttplaneringsalgoritmer testas, vilka är baserade på snabbt-utforskande slumpmässiga träd (RRT): den ursprungliga RRT, RRT*, och en föreslagen variant, RRT-u, vilken skiljer sig från dom två första algoritmerna genom att ta hänsyn till dynamiska begränsningar och använda konstanta accelerationer över delar av rutten. Ruttplaneraren används också i okända miljöer. För att välja en rutt när det finns outforskade delar mellan farkosten och målet föreslås det att testa rutten till målpunkten från varje nod i som ingår i planeringsträdet för att erhålla en preliminär total kostnad till målpunkten. Rutten med lägsta kostanden kan då väljas, givet tillgänglig information, även om den delvis går genom outforskade delar. För tillfällen när inga preliminära rutter kan erhållas på grund av hinder har dynamisk storleksjustering av samplingsområdet implementerats för att öka området från vilket nya noder samplas. Den här metoden har testats med dom tre olika algoritmvarianterna, RRT, RRT*, och RRT-u, och dom tre varianterna jämförs med avseende på prestanda i ett flertal testfall i en realistisk simuleringsmiljö.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-241243 |
| Date | January 2018 |
| Creators | Eriksson, Urban |
| Publisher | KTH, Skolan för elektroteknik och datavetenskap (EECS) |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-EECS-EX ; 2018:780 |
Page generated in 0.0021 seconds