Ivannikov Institute for System Programming of the RAS

Global path planning in complex dynamic scenes.


Kazakov K.A., Semenov V.A.


Path planning problems arise in many industrial domains such as mechanical engineering, robotics, geoinformatics and visual modeling of projects. Due to high complexity the path planning methods are usually applied in simplified local statements implying search of collision-free routes in relatively simple static scenes. Popular methods based on Voronoi diagrams, visibility graphs, probabilistic roadmaps, rapidly exploring random trees exhibit good performance when searching local paths, however, their use in large-scale dynamic scenes looks problematic. In the paper we survey actual methods as well as present a promising computational strategy for global path planning based on concordant octant, metric and topological representations. Ultimately it enables to reduce the original computational problem to typical search in a graph associated with the free space topology of whole scene. Admitting incremental updates, the strategy can be applied to both static and dynamic scenes. Conducted computational experiments prove the effectiveness of the proposed strategy.


Proceedings of XIX Baikal Conference "Information and Mathematical Technologies in Science and Management". Vol 2. Publisher: ISEM SB RAS, 2014. Pp. 40-46.

Research Group

System integration and multi-disciplinary collaborative environments

All publications during 2014 All publications