Načrtovanje poti z algoritmom A* na mikrokrmilniku Arduino

Mesojedec, Matej (author), Vrabič, Rok (mentor)

V tem diplomskem delu je predstavljena implementacija A* algoritma za načrtovanje poti in trajektorije na mikrokrmilniku Arduino UNO. Načrtovanje poti pogosto obravnavamo kot problem iskanja najkrajše poti od začetnega do končnega vozlišča v grafu. Glavni izziv pri implementaciji predstavljajo omejene zmogljivost mikrokrmilnika, saj algoritem zasede veliko delovnega pomnilnika. Rezultat dela predstavlja implementirani program, ki je časovno in prostorsko optimiziran z ustreznimi podatkovnimi tipi, prioritetno vrsto ter časovno in prostorsko varčnim načinom izračuna hevristične vrednosti.

• Language: Slovenian
• Keywords: načrtovanje poti, načrtovanje trajektorije, A* algoritem, hevristika, Arduino, mobilni robot
• Work type: Bachelor thesis/paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FS - Faculty of Mechanical Engineering
• Place of publishing: Ljubljana
• Publisher: [M. Mesojedec]
• Year: 2020
• Number of pages: XXII, 43 str.
• PID: 20.500.12556/RUL-120209
• UDC: 004.451.25:004.421:007.52(043.2)
• COBISS.SI-ID: 32413699
• Publication date in RUL: 17.09.2020

Secondary language

• Language: English
• Title: Path planning with A* algorithm on Arduino microcontroller

Abstract

The thesis presents an implementation of the A* algorithm and trajectory planning on microcontroller Arduino UNO. Path planning is usually formulated as a problem of searching for the shortest path, from start to end node in a graph. The biggest challenge of the implementation are the limited sources of the microcontroller because the algorithm consumes a lot of memory. The result of the work is an A* implementation which is time and space-optimized by choosing the right data types, using a priority queue, and choosing time and space-efficient methods for defining the heuristic value needed by the algorithm.

• Keywords: path planning, trajectory planning, A* algorithm, heuristic technique, Arduino, mobile robot