Volumetric Topological Map Representation

Topological methods in robotics is a new and emerging area of research. It has already been proved that a map with high understanding of the environment can lead to a more efficient solution of the robots's task in the actual scene. One main application at present is the navigation of robots. With excellent navigation or planning, the robots can move to the goal site efficiently and fluently. The topological map representation can also apply to multi-robot collaborative task such as robotic vacuum cleaners and UAVs. In both of these use cases, reliable navigation within a global coordinate frame is crucial. Over the past several years, different topology method for 2D topological map generation have been widely researched. The Topological map generation algorithms that build on top of the Voronoi diagram are mostly widely seen. Our work concentrated on topological data analysis techniques on large 3D point clouds. 

     

In this paper, we propose a 3D hierarchical topometric map representation. There are four basic levels in our map: building - storey - region - volume. The region abstract the navigation areas in the topological map. The volume indicate the free space of objects and region. The connection between volume are shown in parametric plane. Given a point cloud of the whole building, (the storey can be distinguished by detecting the ceiling and floor.) Then on each storey, we take three steps to segment the environment. First, we transform the free space in the point cloud into columns. The length and width of the columns are the specified parameters. The height is adaptively determined according to the height of the free space in the environment. Secondly, we apply height-based merge method combine columns with the similar height into regions.  In the last step, we segment the big region into several small volumes according to area graph segmentation, A 2D voronoi segmentation method we proposed. 

 

Having divided the free space in the point cloud into regions, we can derive topological graphs of different dimensions. The 0-dimension graph show the nodes which represent the volumes (or regions?) in abstract topological relationship. The 1-dimension graph 2 add spatial location information for each node. The 2-dimension graph shows the metric 2D planar information of each node. And 3-dimension graph contain the full metric 3D information of each node. Topological maps of different dimensions can be applied in different fields.For example, for robotic vacuum cleaners a two-dimensional graph is sufficient, while for UAVs, a three-dimensional graph is required. 0 and 1 dimensions are more conducive to global navigation. At the same time, our free space is generated by octree, so we can quickly infer the node from where the robot is. The parameterized passage can ensure that the robot can go from one node to another without collision. Our method is more general because to the best of our knowledge, our method is the first system for full 3D point cloud.

 

Fig 1: Method

Fig 2: Results

 

The project results have been submitted to the journal "Autonomous Robots".