Načrtovanje gladke poti v trirazsežnem okolju

Križmančič, Klemen (author), Klančar, Gregor (mentor)

Načrtovanje poti predstavlja postopek določanja optimalne poti od začetne do končne točke. Igra ključno vlogo pri zagotavljanju gibanja mobilnega sistema skozi okolje. Načrtovanje gladke poti predstavlja svojevrsten izziv. Dobljena pot mora upoštevati različne omejitve, predvsem se mora izogibati oviram. Obenem mora biti čim bolj optimalna. Zglajena pot zagotavlja boljše delovanje mobilnega sistema. Cilj magistrskega dela je razvoj algoritma, ki nam generira zglajeno pot v trirazsežnem statičnem okolju. Okolje enakomerno razdelimo na celice v obliki kock, ki jih imenujemo voksli. Celice, na katerih ležijo ovire, so zasedene, ostale so proste. Z uporabo algoritma za iskanje poti, kot je Dijkstrov algoritem ali algoritem A*, za vsako prosto celico določimo razdaljo do ciljne celice. Okolje obravnavamo kot potencialno polje, medtem ko so vrednosti potencialnega polja razdalje, ki smo jih dobili z uporabo Dijkstrovega algoritma ali algoritma A*. Potencialno polje si lahko predstavljamo kot navidezno višino in kroglico, ki se bo v smeri negativnega gradienta pomikala proti globalnemu minimumu. Potencial in gradient v poljubni točki trirazsežnega diskretnega potencialnega polja dobimo z uporabo trilinearne interpolacije potencialnega polja. Zaradi uporabe linearne interpolacije dobljeni negativni gradient ni zvezen in nam ne zagotavlja gladke poti. Za zagotovitev gladke poti uporabimo dodatno interpolacijo gradienta. Rezultat je gladka pot od začetne točke do končne točke, ki se izogne oviram. V rezultatih sta podani primerjava dolžine poti in gladkosti pri uporabi različnih metod iskanja poti ter njihova računska zahtevnost. Ugotovimo, da najkakovostnejšo pot dobimo z uporabo Dijkstrovega algoritma, ki je računsko najzahtevnejši. Računsko zahtevnost lahko zmanjšamo z izbiro manjšega števila sosednjih vozlišč, pri iskanju poti ali z uporabo A* algoritma in ustrezno izbiro hevristike.

• Language: Slovenian
• Keywords: mobilni sistemi, načrtovanje poti, Dijkstrov algoritem, algoritem A*, potencialno polje, trilinearna interpolacija
• Work type: Master's thesis/paper
• Organization: FE - Faculty of Electrical Engineering
• Year: 2024
• PID: 20.500.12556/RUL-159308
• COBISS.SI-ID: 201649411
• Publication date in RUL: 05.07.2024

Secondary language

• Language: English
• Title: Smooth path planning in a three-dimensional environment

Abstract

Path planning is the procedure of defining the optimal path from the start point to the end point. It plays a key role in enabling the movement of a mobile system through an environment. Planning a smooth path is a special challenge. The obtained path must take into account various limitations and, above all, must avoid obstacles. Moreover, the obtained path must be as optimal as possible. A smoothed path enables better operation of the mobile system. The aim of the thesis is to develop an algorithm that generates a smoothed path in a three-dimensional static environment. The environment is divided evenly into cube-shaped cells called voxels. The cells with obstacles are occupied, while the rest are unoccupied. Using a pathfinding algorithm, such as Dijkstra's algorithm or A* algorithm, we define the distance to the target cell for each vacant cell. The environment is treated as a potential field and the values of the potential field are the distances we have obtained using Dijkstra's algorithm or A* algorithm. We can picture the potential field as a virtual height and ball that moves towards the global minimum in the direction of the negative gradient. We obtain the potential and gradient at a random point in the three-dimensional discrete potential field using trilinear interpolation of the potential field. Due to using linear interpolation, the obtained negative gradient is not continuous and does not ensure a smooth path. In order to ensure a smooth path, we use additional gradient interpolation. The result is a smooth path from the start point to the end point, which avoids obstacles. The results give a comparison of path length and smoothness using different pathfinding methods and their temporal complexity. It has been determined that the highest-quality path is obtained using Dijkstra's algorithm, which is the most computationally demanding. We can reduce computational complexity by choosing a smaller number of adjacent nodes when searching for a path or by using the A* algorithm and choosing a suitable heuristic.

• Keywords: mobile systems, path planning, Dijkstra's algorithm, A* algorithm, potential field, trilinear interpolation