Abstract
Shortest-path roadmaps, also known as reduced visibility graphs, provide a highly efficient multi-query method for computing optimal paths in two-dimensional environments. Combined with Minkowski sum computations, shortest-path roadmaps can compute optimal paths for a translating robot in 2D. In this study, we explore the intuitive idea of stacking up a set of reduced visibility graphs at different orientations for a polygonal holonomic robot to support the fast computation of near-optimal paths, allowing simultaneous 2D translation and rotation. The resulting algorithm, rotation-stacked visibility graph (RVG), is shown to be resolution-complete and asymptotically optimal. Extensive computational experiments show RVG significantly outperforms state-of-the-art single- and multi-query sampling-based methods on both computation time and solution optimality fronts. Source code and supplementary materials are available at github.com/arc-l/rvg.
Introduction
What Does a Rotation-Stacked Visibility Graph (RVG) Do?
RVG constructs a layered visibility graph over multiple discrete orientations, allowing efficient, high-quality path planning for polygonal robots with both translation and rotation in 2D environments. It maintains completeness and asymptotic optimality while enabling rapid queries across diverse planning scenarios. The video below (with narrations) illustrates how RVG works.
Comparisons with SOTA SE(2) Rigid Body Planners
RVG, as a multi-query method dedicated to path planning for rigid bodies in SE(2), outperforms sampling-based planners in such settings, producing shorter paths with significantly lower planning times. Below, we observe that RVG does better in efficiency and optimality for ten typical problem instances similar to the example on the right above.
Given RVG’s time budget, sampling-based methods often produce longer paths, with cost ratios exceeding 1.0. This further corroborates RVG’s superior solution quality under the same amount of compute.
Additional Examples
Non-Convex Rigid Bodies
RVG works with rigid bodies that are non-convex:
Different Translation/Rotation Weighting
RVG can produce different solutions based on the relative weighting of translation and rotation during the search process.
Citation
If you find this project helpful for your research, please consider citing the following BibTeX entry.
@inproceedings{ZhaYeYu25ICRA,
author = {Duo Zhang and Zihe Ye and Jingjin Yu},
title = {Asymptotically-Optimal Multi-Query Path Planning for a Polygonal Robot},
booktitle={IEEE International Conference on Robotics and Automation},
year={2025}}