Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • apa.csl
  • 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
A GPU Implementation of Kinodynamic Path Planning in Large Continuous Costmap Environments: Using Dijkstra's Algorithm and Simulated Annealing
Karlstad University, Faculty of Health, Science and Technology (starting 2013), Department of Engineering and Physics (from 2013).
2023 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
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.

Place, publisher, year, edition, pages
2023. , p. 92
National Category
Computer graphics and computer vision
Identifiers
URN: urn:nbn:se:kau:diva-96039OAI: oai:DiVA.org:kau-96039DiVA, id: diva2:1780866
External cooperation
SAAB Dynamics AB
Educational program
Engineering: Engineering Physics (300 ECTS credits)
Supervisors
Examiners
Available from: 2023-07-07 Created: 2023-07-06 Last updated: 2025-02-07Bibliographically approved

Open Access in DiVA

fulltext(57701 kB)546 downloads
File information
File name FULLTEXT01.pdfFile size 57701 kBChecksum SHA-512
5dcc88241dcef72fec3dade9f25b587fd636254f5285458a31c2b06911c465673a94cb1d5e465d03b25829a6d9d713763f2b028499165f1749956413e3ecdf2c
Type fulltextMimetype application/pdf
Arkivfil(57701 kB)94 downloads
File information
File name FULLTEXT02.pdfFile size 57701 kBChecksum SHA-512
5dcc88241dcef72fec3dade9f25b587fd636254f5285458a31c2b06911c465673a94cb1d5e465d03b25829a6d9d713763f2b028499165f1749956413e3ecdf2c
Type fulltextMimetype application/pdf

By organisation
Department of Engineering and Physics (from 2013)
Computer graphics and computer vision

Search outside of DiVA

GoogleGoogle Scholar
Total: 640 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: 591 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • apa.csl
  • 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