Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • apa.csl
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
A GPU Implementation of Kinodynamic Path Planning in Large Continuous Costmap Environments: Using Dijkstra's Algorithm and Simulated Annealing
Karlstads universitet, Fakulteten för hälsa, natur- och teknikvetenskap (from 2013), Institutionen för ingenjörsvetenskap och fysik (from 2013).
2023 (engelsk)Independent thesis Advanced level (degree of Master (Two Years)), 20 poäng / 30 hpOppgave
Abstract [en]

Path planning that takes kinodynamic constraints into account is a crucial part of critical missions where autonomous vehicles must function independently without communication from an operator as this ensures that the vehicle will be able to follow the planned path. In this thesis, an algorithm is presented that can plan kinodynamically feasible paths through large scale continuous costmap environments for different constraints on the maximum allowed acceleration and jerk along the path. The algorithm begins by taking a small stochastic sample of the costmap, with a higher probability to keep more information from the cheaper, interesting areas of the map. This random sample is turned into a graph to which Dijkstra's algorithm is applied in order to obtain an initial guess of a path. Simulated annealing is then used to first smooth this initial guess to obey the kinodynamic constraints and then optimize the path with respect to cost while keeping the kinodynamics below the set limits. The majority of the simulated annealing iterations utilize a GPU to significantly reduce the computational time needed.

The performance of the algorithm was evaluated by studying the paths generated from a large number of different start and end points in a complex continuous costmap with a high resolution of 2551×2216 pixels. To evaluate the robustness of the algorithm a large number of paths were generated, both with the same and with different start and end points, and the paths were inspected both visually, and the spread of the cost of the different paths was studied. 

It was concluded that the algorithm is able to generate paths of high quality for different limits on the allowed acceleration and jerk as well as achieving a low spread in cost when generating multiple paths between the same pair of points. The utilization of a GPU to improve computational performance proved successful as the GPU executed between 2.4 and 2.8 times more simulated annealing iterations in a given time compared to the CPU. This result hopefully inspires future work to utilize GPUs to improve computational performance, even in problems that traditionally are solved using sequential algorithms.

sted, utgiver, år, opplag, sider
2023. , s. 92
HSV kategori
Identifikatorer
URN: urn:nbn:se:kau:diva-96039OAI: oai:DiVA.org:kau-96039DiVA, id: diva2:1780866
Eksternt samarbeid
SAAB Dynamics AB
Utdanningsprogram
Engineering: Engineering Physics (300 ECTS credits)
Veileder
Examiner
Tilgjengelig fra: 2023-07-07 Laget: 2023-07-06 Sist oppdatert: 2023-07-07bibliografisk kontrollert

Open Access i DiVA

fulltext(57701 kB)37 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 57701 kBChecksum SHA-512
5dcc88241dcef72fec3dade9f25b587fd636254f5285458a31c2b06911c465673a94cb1d5e465d03b25829a6d9d713763f2b028499165f1749956413e3ecdf2c
Type fulltextMimetype application/pdf
Arkivfil(57701 kB)47 nedlastinger
Filinformasjon
Fil FULLTEXT02.pdfFilstørrelse 57701 kBChecksum SHA-512
5dcc88241dcef72fec3dade9f25b587fd636254f5285458a31c2b06911c465673a94cb1d5e465d03b25829a6d9d713763f2b028499165f1749956413e3ecdf2c
Type fulltextMimetype application/pdf

Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 84 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

urn-nbn

Altmetric

urn-nbn
Totalt: 201 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • apa.csl
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf