Ivannikov Institute for System Programming of the RAS

Topological Mapping Complex 3D Environments Using Occupancy Octrees.


Konstantine Kazakov, Vitaly Semenov, Vladislav Zolotov


Global path planning is a challenging problem arisen in many fields of research. Unfortunately, path planning algorithms have relatively high complexity that extremely grows with the input data volume. Being oriented on accurate metric schemes, traditional local path planning methods have significant limitations in the case of large-scale environments. Their inability to use overall information on the whole environment creates critical shortcoming in global planning. Topological schemes try to overcome this drawback by representing the original environment by means of route graphs. Topological schemes scale better than metric ones, but being resistant to geometric representation errors may yield incorrect or suboptimal solutions. In the paper we propose an effective method of generating topological maps for global path planning in complex large-scale 3D environments. The method utilizes adaptive spatial decomposition in conformity to occupancy octree structures and uses original criteria for identifying spaces and gates. Thus generated maps provide for whole coverage of environments and enable to effectively resolve multiple path planning requests using graph search algorithms. Conducted experiments proved the feasibility and effectiveness of the method presented as well as its suitability to industry meaningful problem statements.


GraphiCon'2011: The 21st International Conference on Computer Graphics and Vision, September 26-30, 2011, Moscow, Russia: Conference Proceedings. Publisher: МАКС Пресс, 2011. Pp. 111-114.

Research Group

System integration and multi-disciplinary collaborative environments

All publications during 2011 All publications