cs.ROSep 25, 2026

dRVG: Quadtree-Guided, Resolution-Complete Online Motion Planning for Polygonal Robots in Unknown Environments

Authors: Duo Zhang, Hechen Zhang, Junshan Huang, Jingjin Yu

Organizations: Department of Computer Science, Rutgers, the State University of New Jersey, Piscataway, NJ, USA

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

We present the dynamic rotation-stacked visibility graph (dRVG), an online motion planner that guides polygonal robots to specified goals in initially unknown, static environ- ments. It merges local roadmaps from successive observations to plan collision-free translations and rotations without a uniform position grid. A spatial quadtree schedules sensing goals across regions to reduce repeated visits while retaining all orientation configurations for routing. Under exact sensing and geometric computation and star-shaped robot and envelope assumptions, dRVG with center scans is resolution-complete relative to full- map RVG at the same angular resolution. In experiments using footprint scans, dRVG solves all 140 cases across 20 difficult maps and seven angular resolutions within a 20 s planning budget, with a median planning time of 1.18 s at 360 orientation layers. Six microMVP demonstrations illustrate the complete online planning loop on a physical robot.

Figures & tables

Fig. 1 : Online dRVG execution on microMVP: (a) setup; (b–f) navigation. Temporary sensing goals (magenta) guide translation and reorientation until the robot reaches its goal. Blue is the executed trajectory, green the planned path, and black the space not yet observed.
Fig. 2 : Two consecutive sensing-goal selections ( N=36N=36 ). (a) The quadtree built from the start observation selects qtq_{t} (purple diamond), with its known-free route from qsq_{s} shown in blue. (b) After reaching qtq_{t} , the robot scans and builds a local RVG patch: blue dots are existing sites and orange dots are newly added sites. (c) The quadtree incorporates both sets before selecting qt+1q_{t+1} ; the region served at qtq_{t} remains deferred during the current epoch. Diamonds denote leaf representatives; purple highlights selected representatives and served regions. The blue curve in (c) connects the two sensing goals.
Fig. 3 : For a robot that is not star-shaped about its sensing center, a center scan can leave part of the footprint unobserved. (a) The obstacle in the U-shaped robot’s concavity hides the hatched part of the footprint from a single origin (orange). (b) Scans from the footprint vertices (blue) collectively cover both arms and the connecting body, providing the full-footprint coverage missing from the single-origin scan. Green denotes observed free space; gray denotes obstacles.
Fig. 4 : Geometric limit at N=8N=8 . Static RVG can rotate the non-star-shaped hook from the blue start footprint to the orange goal footprint. The initial footprint scan leaves the marked goal-footprint point unobserved and offers no temporary goal. Green is observed free space. This example lies outside Assumption V.1 .
Fig. 5 : Ten hard cases at N=360N=360 : executed dRVG routes (blue) and full-map RVG routes (gray dashed). Footprints show robot orientation; green and orange mark start and goal.
Fig. 7 : Comparison on 20 hard maps with a 20 s planning budget. Rows correspond to occupancy-grid cell sizes Δx\Delta x ; columns show success, planning time, cost relative to full-map RVG, and the number of graph nodes or grid states. Success rates use all runs. For runtime, cost, and the counts in the last column, markers show medians over successful runs and bars span the 25th–75th percentiles; missing markers indicate no success. Here Δx\Delta x denotes the occupancy-grid cell size; it also sets collision-check spacing for continuous planners.
Fig. 8 : Quadtree dRVG and naive greedy dRVG without quadtree scheduling. Success rates use all runs. Runtime and normalized cost summarize successful runs with medians and interquartile ranges.
More in this topic

Motion Planning

Motion planning finds safe, feasible paths and trajectories for robots and vehicles amid geometric, dynamic, and task constraints.

See all 405 papers

Explore similar work

CardsList

  1. Visual-RRT: Finding Paths toward Visual-Goals via Differentiable Rendering

    Mar 27, 2026Sebin Lee, Jumin Lee, Taeyeon Kim +3Motion PlanningRobot Motion Planning

    1KAIST · 2Samsung Electronics

  2. STAG: A Sparse Traversability-Aware Graph Representation from Grid-Based Costmaps for Robotic Navigation

    Oct 8, 2026Gabriel Manuel Garcia, Stéphanie Aravecchia, Miguel Angel Olivares-MendezRobot NavigationGraph-Based Planning

    University of Luxembourg, Luxembourg · IRL Georgia Tech-CNRS, Metz, France

  3. Serialized Red-Green-Gray: Quicker Heuristic Validation of Edges in Dynamic Roadmap Graphs

    Mar 30, 2026Yulie Arad, Stav Ashur, Marta Markowicz +3Roadmap-Based Motion PlanningMotion Planning

    Siebel School of Computing and Data Science, University of Illinois, 201 N. Goodwin Avenue, Urbana, IL 61801, USA · Department of Computer Science, Instituto Tecnológico Autónomo de México (ITAM), Mexico City, 01080, México