Premium
Parallel algorithms constructing the cell graph
Author(s) -
Kaczmarski Krzysztof,
Rzążewski Paweł,
Wolant Albert
Publication year - 2016
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.3943
Subject(s) - computer science , heuristics , graph , graph algorithms , algorithm , graphics processing unit , parallel computing , implementation , construct (python library) , general purpose computing on graphics processing units , graphics , theoretical computer science , computer graphics (images) , programming language , operating system
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.