Parallel algorithm for approximating the work space of a robot

Andrei Gorchakov, Andrei Ignatov, Dmitry Malyshev, Mikhail Posypkin


The workspace of a robot is the set of positions that can be taken by its working tool. The understanding of the workspace is necessary when designing robots, planning their location, assessing their functionality, the path planning of the robot. So far many methods have been developed to determine the workspace. It should be noted that deterministic methods have the greatest potential, allowing to obtain approximations with a given accuracy in the automatic mode. A known disadvantage of deterministic methods is their high computational complexity, which prevents the effective wide application of these methods in practice. The paper proposes a parallel algorithm for constructing the approximation of the working area with guaranteed accuracy. The OpenMP package is used to create a multithreaded application. An original technique has been developed that allows to evenly distribute the load across the threads without explicit balancing. The results of experiments showing high efficiency of parallelization for multicore systems are presented. Another important problem is to visualize the constructed approximations. The workspace often has a complex structure with internal cavities. In this paper, we propose approaches for effective visualization of the working area of the robot, based on augmented reality technology, allowing not only to study the structure of the object, but also to place it in the desired visual context.

Full Text:

PDF (Russian)


Merlet J. P. Parallel Robots. — Springer Publishing Company, Incorporated, 2010.

Merlet J. P. Determination of 6D workspaces of Gough-type parallel manipulator and comparison between different geometries //The International Journal of Robotics Research. – 1999. – V. 18. – #. 9. – pp. 902-916.

Jaulin Luc. Applied interval analysis: with examples in parameter and state estimation, robust control and robotics. — Springer Science & Business Media, 2001.

Evtushenko Y., Posypkin M., Sigal I. A framework for parallel large-scale global optimization // Computer Science-Research and Development. – 2009. – V. 23. – #. 3-4. – pp. 211-215.

Chakroun I., Melab N. Towards a heterogeneous and adaptive parallel Branch-and-Bound algorithm //Journal of Computer and System Sciences. – 2015. – V. 81. – #. 1. – pp. 72-84.

Mezmaz M. et al. A multi-core parallel branch-and-bound algorithm using factorial number system //Parallel and Distributed Processing Symposium, 2014 IEEE 28th International. – IEEE, 2014. –pp. 1203-1212.

Gorchakov A.Ju., Posypkin M.A., Jamchenko Ju.V. Jeksperimental'noe issledovanie treh variantov realizacii metoda neravnomernyh pokrytij dlja mnogojadernyh sistem s obshhej pamjat'ju //International Journal of Open Information Technologies. – 2018. – T. 6. – #. 11 – S. 34-41.

Evtushenko Y., Posypkin M. A deterministic approach to global box-constrained optimization //Optimization Letters. – 2013. – V. 7. – #. 4. – pp. 819-829.

Strongin R. G., Sergeyev Y. D. Global optimization with non-convex constraints: Sequential and parallel algorithms. – Springer Science & Business Media, 2013.

The OpenMP API specification for parallel programming. URL:

Gibridnyj vysokoproizvoditel'nyj vychislitel'nyj kompleks COD FIC IU RAN. URL:


  • There are currently no refbacks.

Abava  Кибербезопасность MoNeTec 2024

ISSN: 2307-8162