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=36 ). (a) The quadtree built from the start observation selects qt (purple diamond), with its known-free route from qs shown in blue. (b) After reaching qt , 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+1 ; the region served at qt 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=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=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 ; 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 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.
Rapidly-exploring random trees (RRTs) have been widely adopted for robot motion planning due to their robustness and theoretical guarantees. However, existing RRT-based planners require explicit goal configurations specified as numerical joint angles, while many practical applications provide goal specifications through visual observations such as images or demonstration videos where precise goal configurations are unavailable. In this paper, we propose visual-RRT (vRRT), a motion planner that enables visual-goal planning by unifying gradient-based exploitation from differentiable robot rendering with sampling-based exploration from RRTs. We further introduce (i) a frontier-based exploration-exploitation strategy that adaptively prioritizes visually promising search regions, and (ii) inertial gradient tree expansion that inherits optimization states across tree branches for momentum-consistent gradient exploitation. Extensive experiments across various robot manipulators including Franka, UR5e, and Fetch demonstrate that vRRT achieves effective visual-goal planning in both simulated and real-world settings, bridging the gap between sampling-based planning and vision-centric robot applications. Our code is available at https://sgvr.kaist.ac.kr/Visual-RRT.
Autonomous rovers navigating large unstructured environments need efficient global planning that accounts for terrain traversability. However, searching dense grid-based costmaps becomes computationally expensive as the mapped area grows. We introduce STAG, a Sparse Traversability-Aware Graph that converts costmaps into compact graphs. STAG combines a medial-axis topological backbone, representative nodes for homogeneous traversability regions, and transition nodes near strong traversability gradients. Edges encode geometry and traversability to account for path length and terrain difficulty. We compare A* on STAG and dense grids using synthetic cave maps, mine maps and the DARPA CERBERUS dataset. Across five benchmark categories comprising 203 map instances and 101,200 queries, STAG reduces median planning time by 3.4x to 9.9x and peak query memory by 2.1x to 15.4x, with median relative path-length differences of -2.9% and +7.6%. STAG offers a compact representation for global planning, trading dense-grid traversability optimality for faster, less memory-intensive search.
Gabriel Manuel Garcia, Stéphanie Aravecchia, Miguel Angel Olivares-Mendez
University of Luxembourg, Luxembourg · IRL Georgia Tech-CNRS, Metz, France
Motion planning in dynamic environments, such as robotic warehouses, requires fast adaptation to frequent changes in obstacle poses. Traditional roadmap-based methods struggle in such settings, relying on inefficient reconstruction of a roadmap or expensive collision detection to update the existing roadmap. To address these challenges we introduce the Red-Green-Gray (RGG) framework, a method that builds on SPITE to quickly classify roadmap edges as invalid (red), valid (green), or uncertain (gray) using conservative geometric approximations. Serial RGG provides a high-performance variant leveraging batch serialization and vectorization to enable efficient GPU acceleration. Empirical results demonstrate that while RGG effectively reduces the number of unknown edges requiring full validation, SerRGG achieves a 2-9x speedup compared to the sequential implementation. This combination of geometric precision and computational speed makes SerRGG highly effective for time-critical robotic applications.
Yulie Arad, Stav Ashur, Marta Markowicz +3
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