Parallel algorithms constructing the cell graph

Summary Motion planning is an important and well‐studied field of robotics. A typical approach to finding a route is to construct a cell graph representing a scene and then to find a path in such a graph. In this paper, we present and analyze several parallel algorithms for constructing the cell graph on a single instruction, multiple data‐like graphics processing unit (GPU) processor. GPU utilization is necessary because of insufficient processing power of CPUs reported by other authors. A GPU processor with its parallel processing capabilities promises some improvement if only proper implementations of the algorithms can be found. We show that a naive brute force algorithm, enhanced by a simple heuristics, in an average case, can be faster than comprehensive solutions based on parallel implementation of an asymptotically optimal sequential algorithm. Copyright © 2016 John Wiley & Sons, Ltd.