A GPU Implementation of Kinodynamic Path Planning in Large Continuous Costmap Environments : Using Dijkstra's Algorithm and Simulated Annealing

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