A multi-scale path-planning method for large-scale scenes based on a framed scale-elastic grid map

Abstract

Environment modeling serves as the foundation for path planning in unmanned systems. Single-scale maps have many nodes and impose large memory requirements; tree-based multi-scale grid maps used for representing large-scale urban scenes have limited aggregation ability in the presence of dimensional anisotropy. This study proposes a novel multi-scale map-construction method based on a scale-elastic discrete grid structure. The method provides more flexible node aggregation in grid-based representations, reducing the number of grid and border-grid nodes while maintaining the same modeling accuracy. Furthermore, a novel multi-scale A* path-planning algorithm that modifies the neighborhood-expansion phase of A* is proposed to reduce the number of algorithm search nodes in framed multi-scale maps while ensuring optimal path planning. The experimental results demonstrate that the proposed map-construction method requires 71.5% fewer grids and 10.8% fewer border grids than framed-octree grid maps in three-dimensional scenarios with the same modeling accuracy. Consequently, memory requirements are smaller, making this method more efficient on devices with limited performance. The multi-scale A* algorithm also improves path-planning efficiency by reducing the number of search nodes. The proposed method is suitable for path planning in large-scale and complex urban scenes.

Keywords

• Grid map
• path planning
• scale-elastic grid structure
• voxel-based modeling