Autonomous vehicles is a rapidly expanding field and the need for robust and efficient path planners is high. We approach the global path- planning problem for an autonomous load carrier for quarry environments, developed at Volvo Construction Equipment, using two methods: a two- step path planning and path smoothing approach, and a method based on an optimal control formulation of the path planning problem. The two-step method is based on smoothing an initial path found by A*, an efficient grid search algorithm, by fitting a curve consisting of as few clothoid segments as possible to the A* path. The smoothing is done by rewriting the non-linear optimization problem to a convex form by a linearization of the deviation constraints around the curvature of the A* path. An iterative method is then used to relax the l0-norm, which measures the number of non-zero elements in a vector, with a weighted l1-norm which, in turn, is then solved efficiently using CVX in Matlab. The optimal control based path planning method solves the nonlinear optimization problem using IPOPT. It was found that the completeness of the A* algorithm, coupled with the guaranteed solution of a convex problem, resulted in a very robust method that was able to find paths through mazes and difficult situations. The optimal control approach produced better paths, but had a tendency to sometimes show inconsistent behavior. / Autonoma fordon är ett snabbt växande forskningsområde och behovet av robusta och effektiva lösningar för vägplanering är stort. Vi undersöker ett globalt vägplaneringsproblem för en autonom dumper som utvecklas på Volvo Construction Equipment och som är byggd för att användas i bergtäkter. Två metoder undersöks: en tvåstegsmetod med grafbaserad vägplanering följt av en utslätning av vägen, och en metod som bygger på optimal styrteori. Tvåstegsmetoden går ut på att först hitta en väg fri från hinder med hjälp av A*, en effektiv grafbaserad sökalgoritm, och sedan släta ut denna väg genom att anpassa ett så lågt antal klotoid-kurvor som möjligt till vägen. Denna utslätning genomförs genom att skriva om det icke-linjära problemet på konvex form med hjälp av en linjärisering kring referensvägens kurvatur. En iterativ metod beskrivs för att relaxera l0 - normen, som mäter antalet nollskilda element i en vektor, med en viktad l1-norm. Sedan löses problemet med CVX i Matlab. I metoden baserad på optimal styrteori löser vi det icke-linjära problemet direkt med IPOPT. Det visade sig att robustheten hos A* tillsammans med ett lättlöst konvext problem gjorde att tvåstegsmetoden blev mycket robust och pålitlig och kunde hitta tillåtna vägar genom labyrinter och svåra situationer. Vägar planerade med hjälp av optimal styrteori var kortare och hade bättre egenskaper, men algoritmen hade en tendens att få svårigheter med konvergens.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-216388 |
| Date | January 2017 |
| Creators | Lundberg, Marcus |
| Publisher | KTH, Numerisk analys, NA |
| 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-MAT-E ; 2017:73 |
Page generated in 0.0024 seconds