Track manipulation, locomotion and embodied systems.
Search papers, labs, and topics across Lattice.
This paper introduces STAG, a Sparse Traversability-Aware Graph representation derived from grid-based costmaps to enable efficient global planning for robotic navigation in large unstructured environments. By combining a medial-axis backbone with representative nodes for traversability regions and transition nodes at gradients, STAG creates a compact graph where edges encode geometric and traversability information. Experiments on diverse datasets demonstrate significant reductions in planning time (3.4x-9.9x) and memory usage (2.1x-15.4x) with minimal path-length degradation, offering a practical trade-off for large-scale autonomous navigation.
Robotic navigation planning scales dramatically with map size, but a novel sparse graph representation slashes planning time by up to 9.9x and memory by 15.4x while preserving near-optimal paths.
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.