Parallelization of Dijkstra’s Algorithm for Robot Motion Planning: Is It Worth Increasing Speed Without Losing Accuracy?

Abstract

This paper examines the problem of parallelizing Dijkstra’s algorithm, as an algorithm for robot motion planning was a challenge to twist the algorithm in such a way so it can be executed in parallel, rather than sequentially. In this paper, we test the validity of a research hypothesis that the speed of Dijkstra’s algorithm can be increased by parallelizing and keeping the same accuracy. The developed use-case of Dijkstra’s algorithm as a robot motion planning algorithm was tested against performance, both in execution speed and accuracy. Finally, we elaborate on the benefits of this parallelizing approach.