Efficient Hierarchical Any-Angle Path Planning on Multi-Resolution 3D Grids
2026-02-24 • Robotics
RoboticsArtificial Intelligence
AI summaryⓘ
The authors study how to find the shortest paths in large 3D maps that represent complex spaces. They improve on current methods by combining any-angle path planning, which draws straight lines between key points, with multi-resolution map representations to speed up the search. Their approach keeps the benefits of finding optimal paths but works faster than traditional search methods and even sampling-based ones. The authors also tested their method in different environments and made their code publicly available.
hierarchical mappingmulti-resolutionvolumetric mappingpath planningany-angle planningA* algorithmsampling-based methodstrajectory optimizationconnectivityrobot navigation
Authors
Victor Reijgwart, Cesar Cadena, Roland Siegwart, Lionel Ott
Abstract
Hierarchical, multi-resolution volumetric mapping approaches are widely used to represent large and complex environments as they can efficiently capture their occupancy and connectivity information. Yet widely used path planning methods such as sampling and trajectory optimization do not exploit this explicit connectivity information, and search-based methods such as A* suffer from scalability issues in large-scale high-resolution maps. In many applications, Euclidean shortest paths form the underpinning of the navigation system. For such applications, any-angle planning methods, which find optimal paths by connecting corners of obstacles with straight-line segments, provide a simple and efficient solution. In this paper, we present a method that has the optimality and completeness properties of any-angle planners while overcoming computational tractability issues common to search-based methods by exploiting multi-resolution representations. Extensive experiments on real and synthetic environments demonstrate the proposed approach's solution quality and speed, outperforming even sampling-based methods. The framework is open-sourced to allow the robotics and planning community to build on our research.