Enveloped Generalized Voronoi Graph and Multihomotopy Path Planning for Navigation in Unknown Environments

Authors:
Publisher website
Google Scholar
Abstract
Efficient navigation in unknown environments relies on a compact yet geometrically expressive map that enables optimal path generation. Among various representations, Voronoi diagram offers advantages in structural compactness and global connectivity. However, in partially explored environments, its limited spatial expressiveness degrades planning performance. To address this, we propose the enveloped generalized Voronoi graph (EGVG) and a multihomotopy path-planning algorithm, integrated within a unified navigation framework. EGVG enhances the original Voronoi skeleton by incorporating Euclidean signed distance field (ESDF) contours to envelop obstacles, enriching spatial representation and bridging the gap between the Voronoi skeleton and the optimal solution space. Next, a multihomotopy search is performed on the EGVG, where the planner deactivates key vertices after each iteration, forcing the exploration of multiple homotopy classes and increasing the likelihood of finding globally shortest paths (i.e., solution optimality). Finally, a motion-consistency criterion is applied to select the most efficient path for execution. Experimental results demonstrate that the proposed method achieves up to an 88% improvement in solution optimality over the original generalized Voronoi graph. Compared to roadmap and visibility-graph representations, it reduces planning time and graph size by over an order of magnitude. In unknown navigation tasks, our planner outperforms state-of-the-art methods, achieving shorter travel distances and execution times.
Funding Information
  • National Natural Science Foundation of China (62088101)
  • Fundamental and Interdisciplinary Disciplines Breakthrough Plan of the Ministry of Education of China (JYB2025XDXM208)
  • Beijing Natural Science Foundation (L243004)

This publication has 32 references indexed in Scilit: