Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Path planning for autonomous vehicles using clothoid based smoothing of A* generated paths and optimal control
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Numerical Analysis, NA.
2017 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
Vägplanering för autonoma fordon med hjälp av en klotoid- baserad utjämning av A*-genererade vägar och optimal styrteori (Swedish)
Abstract [en]

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.

Abstract [sv]

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.

Place, publisher, year, edition, pages
2017.
Series
TRITA-MAT-E ; 2017:73
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-216388OAI: oai:DiVA.org:kth-216388DiVA, id: diva2:1150741
External cooperation
Volvo Construction Equipment
Subject / course
Scientific Computing
Educational program
Master of Science - Applied and Computational Mathematics
Supervisors
Examiners
Available from: 2017-10-19 Created: 2017-10-19 Last updated: 2017-10-19Bibliographically approved

Open Access in DiVA

fulltext(3112 kB)390 downloads
File information
File name FULLTEXT01.pdfFile size 3112 kBChecksum SHA-512
864a95633e615179af8b3350b37437783d51812192b90bb8a37489f2723e36377b1075ea571f6f7d093923826755d092dae086ab33a9c0833daab797e98c8863
Type fulltextMimetype application/pdf

By organisation
Numerical Analysis, NA
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 390 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 223 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf