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.
|
