A non-uniform quadtree map building method including dead-end semantics extraction

Abstract

To reduce the complexity of large-scene high-resolution maps while using the dead-end information distributed in the unmanned vehicle driving environment, we propose a novel non-uniform quadtree map-building method including dead-end semantic information extraction. By utilizing quadtree data structures, submaps and a positive-order tree depth organization approach, our proposed map can adapt to the large-scale high-resolution requirement and expand more easily to larger environments. To verify the practicality of our proposed map, we have successfully implemented map matching and path planning in real environments. Additionally, we effectively extract the dead-end semantic information that widely distributes in the environment, which can help unmanned vehicles avoid collisions and improve the search efficiency of the planning procedure. We evaluate our method with KITTI datasets, CARLA Simulator, and our self-collected real-world datasets. The experimental results show that our proposed method significantly reduces the complexity of large-scale high-resolution maps, effectively extracts dead-end semantic information, and has good practicality in real environments. The implementation of our method is released here: https://github.com/biter0088/Non-uniform-quadtree-map.

Keywords

• Unmanned vehicles
• Mapping
• Path planning
• Quadtree
• Dead-end