Asymptotically-Optimal Multi-Query Path Planning for Moving A Convex Polygon in 2D

Duo Zhang , Zihe Ye , Jingjin Yu
Accepted to ICRA 2025
Video arXiv Code PDF
Placeholder: Top README Image 1 (GitHub-hosted)
Placeholder: Top README Image 2 (GitHub-hosted)
Placeholder: Top README Image 3 (GitHub-hosted)

These correspond to the three images shown at the top of the README. Add local files or hosted URLs when ready.

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 README includes a narrated video illustrating how RVG works.

Placeholder: Narrated RVG Demo Video (README GitHub attachment)

README video attachment URL placeholder. You can replace this with an embedded video, GIF, or MP4.

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. The README highlights ten representative problem instances and compares efficiency and optimality against strong baselines.

Given RVG’s time budget, sampling-based methods often produce longer paths, with cost ratios exceeding 1.0, further corroborating RVG’s superior solution quality under matched compute.

Placeholder: Comparison Figure (README: comparison_together)

README image placeholder for the main planner comparison panel.

Placeholder: Cost Ratio Figure (README comparison follow-up image)

README image placeholder for the cost-ratio / optimality comparison figure.

Additional Examples

Non-Convex Rigid Bodies

The README shows that RVG also works with rigid bodies that are non-convex.

Placeholder: Non-convex Example 1
Placeholder: Non-convex Example 2

README image placeholders for two non-convex-body examples.

Different Translation/Rotation Weighting

RVG can produce different solutions based on the relative weighting of translation and rotation during the search process.

Placeholder: Weighting Example 1
Placeholder: Weighting Example 2
Placeholder: Weighting Example 3
Placeholder: Weighting Example 4

README image placeholders for the four weighting-based result figures.

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}}