Source-linked AI summary
dRVG: Quadtree-Guided, Resolution-Complete Online Motion Planning for Polygonal Robots in Unknown Environments
Duo Zhang, Hechen Zhang, Junshan Huang, Jingjin Yu
TL;DR
Robots navigating unfamiliar environments must reach specified goals before a complete map is available, including when their polygonal shape requires rotation. dRVG merges local visibility graphs and schedules sensing goals with a quadtree. It solved all 140 tested map–resolution cases within the planning budget, while its center-scan completeness guarantee holds only under stated assumptions.
Problem
Robots must reach specified goals in initially unknown environments, where polygonal shape can make feasible motion depend on rotation.
Source: §I · p. 1, §III · p. 2Method
dRVG merges local visibility graphs from successive observations and uses a spatial quadtree to schedule sensing goals while retaining orientation configurations for routing.
Source: §I · p. 1Results
140/140 map–resolution cases were solved within a 20 s planning budget across 20 difficult maps and seven angular resolutions.
Source: §I · p. 1Takeaways & Limitations
Under the stated assumptions, center-scan dRVG reaches goals connected in full-map RVG at the same angular resolution.
Source: §I · p. 1, §VII · p. 7The completeness analysis does not establish the guarantee for arbitrary polygonal robots or footprint scans.
Source: §VII · p. 7
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
dRVG plans translation and rotation for polygonal robots navigating to specified goals in initially unknown environments. It merges local visibility graphs and schedules sensing goals with a quadtree; its center-scan completeness guarantee is conditional, while footprint-scan experiments report success across all tested cases.
I. INTRODUCTION
- The planner targets specified positions and orientations among unknown static obstacles, where polygonal robot shape can require rotation to pass through constrained spaces.The motivating applications include inspection and delivery before a complete map is available.Source: §I · p. 1
- dRVG builds and merges local visibility graphs as observations arrive, while a spatial quadtree schedules sensing goals without removing orientation configurations from routing.If the final goal is unreachable, the robot follows a known-free route to a temporary sensing goal.Source: §I · p. 1
- With exact sensing and the stated star-shaped robot and envelope assumptions, center-scan dRVG reaches goals connected in full-map RVG at the same angular resolution.The guarantee does not extend to all polygonal robots; footprint scans are used in experiments.Source: §I · pp. 1–2
- 140/140 map–resolution cases were solved within a 20 s planning budget; at 360 orientation layers, median planning time was 1.18 s.Repeated A*, D* Lite, RRTX, and EIT* solved at most 18, 10, 1, and 5 maps, respectively, under the stated protocol; quadtree scheduling improved success from 93/140 to 140/140 over naive greedy selection.Source: §I · p. 1
- The paper evaluates dRVG against lattice and sampling-based planners, studies spatial scheduling by ablation, and demonstrates the online planning loop in hardware.The benchmark includes 20 difficult maps at seven angular resolutions.Source: §I · pp. 1–2
II. RELATED WORK
Prior work addresses geometric route planning, replanning, sensor-based roadmaps, and goal-directed sensing. The paper frames its contribution against these approaches, defines a configuration-space path problem, and describes RVG’s orientation-layered visibility graph.
II. RELATED WORK
- Prior planners update routes in a current map, while unknown-space navigation also requires choosing where to observe; dRVG couples incremental planning with sensing decisions.Related approaches include incremental search, sampling-based repair, frontier exploration, and learned guidance for unseen space.Source: §II · p. 2
- Compared with sensor-based roadmaps and exploration methods, dRVG preserves connections between local roadmaps and schedules reachable sensing sites across quadtree regions.Its sensing objective is to reveal a feasible route to the goal, not to cover the full workspace.Source: §II · p. 2
III. PRELIMINARIES
- The problem is to find a low-cost collision-free path between start and goal poses for a polygonal robot in a workspace with initially unknown static obstacles.The cost weights translation length and cumulative rotation.Source: §III · p. 2
A. Rotation-Stacked Visibility Graphs
- RVG divides orientation into N intervals with representative angles, builds a reduced visibility graph in each layer, and links adjacent layers for collision-free rotations.Conservative polygonal envelopes bound the robot over each interval and converge to the exact swept region as N increases.Source: A. Rotation-Stacked Visibility Graphs · p. 2
B. Observation Model
The observation model combines center and footprint scans, while dRVG repeatedly senses, builds local roadmaps, merges them, and moves toward the goal or another sensing site.
B. Observation Model
- A footprint scan combines the center scan with visibility scans from the footprint’s vertices.At a collision-free pose, every footprint point is covered by vertex scans; a center scan can miss part of a nonconvex footprint.Source: B. Observation Model · pp. 2–3
A. Sense–Construct–Merge–Move
- Each observation adds sensed space and the current site to the observed-free-space set and scanned-site set.The robot takes either a center scan or a footprint scan at its current pose.Source: A. Sense–Construct–Merge–Move · p. 3
- The local roadmap encodes collision-free translations and rotations using visibility edges and links between adjacent orientation layers.It is constructed in the scan domain, with query edges added when feasible.Source: A. Sense–Construct–Merge–Move · p. 3
- Merging retains earlier graph components, including those not yet reachable, and joins a reached temporary goal’s local component to the accumulated graph.Under Assumption V.1, the reached goal’s layer envelope lies in both observed domains.Source: A. Sense–Construct–Merge–Move · p. 3
- If the final goal is unreachable, the robot follows a shortest known-free route to a reachable unscanned site, senses there, and repeats.The loop stops at goal arrival, exhaustion of reachable unscanned sites, or the planning-time limit.Source: A. Sense–Construct–Merge–Move · p. 3
B. Quadtree-Based Selection of Temporary Sensing Goals
The quadtree schedules temporary sensing goals by spatial region, while keeping configurations at different orientations available for routing.
Spatial sites
- Configurations at the same position are grouped into a spatial site, but all orientations remain in the roadmap for later routes.After one configuration at a site is scanned, the site is no longer a sensing target; for center scans, its configurations share an observation.Source: B. Quadtree-Based Selection of… · p. 3
Quadtree scheduling
- Leaves are served in epochs: after supplying a sensing goal, a leaf is deferred until every eligible leaf has been served.Scanned sites stay excluded across epochs, and revisiting a region requires a new site.Source: B. Quadtree-Based Selection of… · p. 3
Goal selection
- Each eligible leaf nominates its lowest-score reachable configuration, and the best nominee becomes the temporary goal.The default score combines position and orientation differences from the final goal; the g + h variant also accounts for route cost.Source: B. Quadtree-Based Selection of… · p. 3
Candidate sets
- Candidates are reachable configurations at unscanned sites within a leaf, and leaves with candidates are eligible for selection.For the g + h variant, both nomination steps use d(v) + h(v).Source: B. Quadtree-Based Selection of… · pp. 3–4
V. RESOLUTION-COMPLETENESS ANALYSIS
The analysis proves fixed-resolution completeness relative to full-map RVG for center scans under Assumption V.1, and specifies the guarantee’s scope and limits.
Assumptions
- The proof assumes exact sensing and geometry, a robot star-shaped about its reference point, and layer envelopes star-shaped about the origin.The analysis fixes N and has no time limit.Source: §V · p. 4
Reachability preservation
- A scanned site makes every full-map neighbor of a represented vertex represented and connected to it.The argument uses the conservative sweep of the full-map edge and the center scan’s visibility of that sweep.Source: §V · p. 4
- Reachability is nondecreasing as reached temporary goals join new local components to the accumulated start component.Earlier vertices and edges are retained, though a scan need not add new space or connections.Source: §V · p. 5
Quadtree reordering
- Quadtree scheduling changes only sensing order; every persistent reachable unscanned site is selected after finitely many successful moves unless the goal is reached first.The proof relies on a finite set of candidate roadmap positions for fixed N.Source: §V · p. 5
Completeness guarantee
- Under Assumption V.1, quadtree-guided dRVG with center scans reaches the goal whenever full-map RVG at the same fixed resolution contains a path.If the goal remains unreachable after all reachable unscanned sites are exhausted, the start and goal are disconnected in full-map RVG—not necessarily infeasible in continuous space.Source: §V · p. 5
Resolution refinement and limits
- Under angular refinement, a feasible query meeting static RVG’s clearance and envelope-convergence conditions has a finite N at which dRVG reaches the goal.The guarantee does not extend to all polygonal robots: the non-star-shaped hook example fails at N = 8, and footprint-scan completeness is not established.Source: Figure 4 · p. 4, §V · p. 5
VI. EVALUATION
The evaluation examines scaling with angular resolution, spatial scheduling benefits, and physical execution of the online planning loop.
Evaluation scope
- The evaluation studies how planning scales with angular resolution on difficult maps.Source: §VI · p. 5
- It assesses the benefit of spatial scheduling.Source: §VI · p. 5
- It also evaluates physical execution of the online planning loop.Source: §VI · p. 5
A. Protocol and Metrics
The evaluation compares dRVG with grid-based, sampling-based, and full-map planners across difficult maps and angular resolutions. It measures success, planning time, normalized path cost, and graph or grid size under a shared planning-time budget.
A. Protocol and Metrics
- The study tests 20 maps at seven angular resolutions, while grid-based planners also vary occupancy-grid cell size across three values.Static RVG solves every tested map–resolution case.Source: A. Protocol and Metrics · p. 5
- The 2,100-run comparison assigns 140 runs each to static RVG and two dRVG selectors, and 420 runs each to four baselines.The baselines are repeated A*, D* Lite, RRTX, and EIT*.Source: A. Protocol and Metrics · p. 5
- Success requires reaching the goal within the cumulative 20 s planning budget and passing complete-map collision validation.Reported success rates use all runs; runtime, normalized cost, and graph or grid counts summarize successful runs.Source: A. Protocol and Metrics · p. 6
- All online planners use a scan–plan–move–scan cycle, and a run fails if no path is returned for the next move.Repeated A* and D* Lite use conservative SE(2) lattices; RRTX and EIT* use continuous SE(2), with ∆x controlling collision-check spacing.Source: A. Protocol and Metrics · p. 7
B. Planner Comparison
dRVG solves the tested map–resolution cases more consistently than the compared online baselines, while its executed paths can cost more than full-map planning. Grid resolution affects baseline success under the planning-time budget.
B. Planner Comparison
- dRVG solves all 140 map–resolution cases, while repeated A*, D* Lite, and RRTX take 4.40×, 11.15×, and 5.09× as long as dRVG, respectively, using each baseline’s lowest median runtime.At N = 360, dRVG’s median planning time is 1.18 s; EIT* succeeds in only 4/20, 5/20, and 5/20 cases at ∆x = 0.05, 0.1, and 0.2, respectively.Source: B. Planner Comparison · p. 7
- EIT* succeeds in 101 of 420 runs across tested resolutions, and 10 additional reported solutions fail final collision checking.At ∆x = 0.1 and N = 72, success rises from 0/20 to 3/20 to 7/20 as query budgets increase from 10 to 50 to 100 ms.Source: B. Planner Comparison · p. 7
- At N = 360, default dRVG uses a median 40,358 vertices versus 87,370 for static RVG, while grid lattices contain approximately 201–3,211 times as many states as the median dRVG roadmap.Grid-state counts are 129.6, 32.4, and 8.1 million at ∆x = 0.05, 0.1, and 0.2, respectively.Source: B. Planner Comparison · p. 7
- At N = 360, median J/JRVG is 1.477 for default dRVG and 1.306 for g + h, while baseline medians range from 1.122 to 1.457.Cost medians may cover different maps because successful subsets vary.Source: B. Planner Comparison · p. 7
- At N = 360, repeated A* solves no cases at ∆x = 0.05, 10/20 at 0.1, and 18/20 at 0.2; D* Lite solves 10/20 only at 0.2.RRTX solves 1/20 at every collision-check resolution.Source: B. Planner Comparison · p. 7
C. Naive Selector Reference
The selector comparison tests quadtree scheduling against naive greedy selection using the same maps, angular resolutions, and footprint-scan model. Quadtree selection achieves more successes and lower runtime on jointly solved cases.
C. Naive Selector Reference
- Both selectors exclude previously scanned positions, while quadtree selection additionally defers served regions.Naive greedy minimizes Eq. (6) over reachable configurations at unscanned sites.Source: C. Naive Selector Reference · p. 7
- Quadtree dRVG solves 140/140 cases versus 93/140 for naive greedy, whose 47 failures are all timeouts at the 20 s budget.Across jointly solved cases, greedy requires 5.51× the runtime and 2.75× as many scan–plan–move iterations in geometric mean.Source: C. Naive Selector Reference · p. 7
- At N = 360, quadtree solves 20/20 cases versus greedy’s 6/20, with a 3.84× paired geometric-mean runtime ratio.Across each method’s successful runs, median runtimes are 1.18 s for quadtree and 2.36 s for greedy.Source: C. Naive Selector Reference · p. 7
D. Real-Robot Demonstration
The physical demonstrations use the microMVP platform to run dRVG’s online planning loop in six polygonal-obstacle arrangements. The robot reaches its requested goal pose through successive translations and rotations, with some workspace still unobserved at arrival.
D. Real-Robot Demonstration
- In six arrangements of polygonal obstacles, the robot reaches its requested goal pose through successive translation and rotation motions.At each iteration, footprint-scan observations and visible obstacle geometry are computed from an overhead-camera image; the demonstrations use N = 36 orientations.Source: D. Real-Robot Demonstration · p. 7
- A representative run visits temporary sensing goals, incorporates newly observed space, and reorients around obstacles until a route to the final goal becomes available.Parts of the workspace remain unobserved at goal arrival.Source: D. Real-Robot Demonstration · p. 7
VII. CONCLUSION
The conclusion summarizes dRVG’s roadmap-merging approach and its reported performance, while bounding the completeness guarantee to its stated assumptions. It also notes hardware demonstrations and directions for extending the planner.
VII. CONCLUSION
- Default footprint-scan dRVG solved all 140 map–resolution cases within the planning budget, but the analysis does not establish this guarantee for footprint scans.The completeness guarantee is also limited to the stated assumptions and is not established for arbitrary polygonal robots.Source: §VII · p. 7
- dRVG merges local RVGs and uses quadtree sensing to navigate polygonal robots among unknown static obstacles.The stated completeness result applies to center scans and goals connected in full-map RVG at the same angular resolution.Source: §VII · p. 7
- Six microMVP demonstrations use overhead-camera observations.Source: §VII · p. 8
- Proposed extensions include SLAM integration, finite-range sensing, and assessing how map uncertainty affects collision margins.Loop closures would require revising roadmap geometry and revalidating affected connections.Source: §VII · p. 8