3D Global Path Planning for Walking Robots on Sparse Volumetric Maps

The use of mobile robots has become increasingly common in multiple areas of daily life. To increase their autonomy for performing various tasks, efficient navigation skills are essential. The most crucial component of such navigation is the ability to calculate a global path between two points. The global path planning problem for mobile robots is typically limited to two-dimensional environments, in which the environment is projected onto a planar surface. While this approach works well in structured environments like industrial settings, it may not be suitable for all applications of mobile robots. With modern walking robots, capable of navigating complex terrain, more advanced path planning approaches are necessary. This work proposes a path-planning approach that utilizes the entire three-dimensional space, allowing for navigation in even the most challenging terrain. The central idea is to extend a traditional A* path planner to work directly on a fast volumetric map structure to generate optimal paths through the environment. Multiple optimizations and adjustments are introduced to improve the algorithm’s performance. By applying morphology operators to sparse maps, sensor inaccuracies during the map construction are mitigated. Additionally, adjustments are made to handle the added complexity introduced by the extra search space dimension and to comply with the limitations of autonomous walking robots. This is paired with an efficient caching strategy to enhance the overall path-planning speed. The capability of the path planning approach is evaluated using both artificial and real-world maps. The results demonstrate that this approach shows great potential for enabling mobile ground robots to autonomously navigate even the most demanding terrains utilizing the entire three-dimensional space.