Načrtovanje poti z algoritmom A* na mikrokrmilniku Arduino

Mesojedec, Matej (avtor), 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.

• Jezik: Slovenski jezik
• Ključne besede: načrtovanje poti, načrtovanje trajektorije, A* algoritem, hevristika, Arduino, mobilni robot
• Vrsta gradiva: Diplomsko delo/naloga
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: FS - Fakulteta za strojništvo
• Kraj izida: Ljubljana
• Založnik: [M. Mesojedec]
• Leto izida: 2020
• Št. strani: XXII, 43 str.
• PID: 20.500.12556/RUL-120209
• UDK: 004.451.25:004.421:007.52(043.2)
• COBISS.SI-ID: 32413699
• Datum objave v RUL: 17.09.2020

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Path planning with A* algorithm on Arduino microcontroller

Izvleček

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.

• Ključne besede: path planning, trajectory planning, A* algorithm, heuristic technique, Arduino, mobile robot