Sparse graph speeds up rover navigation in complex terrain
STAG: A Sparse Traversability-Aware Graph Representation from Grid-Based Costmaps for Robotic Navigation
Robotics
Summary
Planning paths for robots across rough landscapes can be slow and use a lot of memory when using detailed maps. The authors designed a method called STAG that turns these detailed maps into simpler graphs by focusing on important route features and terrain changes. This lets robots plan routes much faster and with less memory but sometimes with slightly longer paths. Their tests showed STAG can be three to ten times faster while using less memory, making it a compact way to help rovers find their way.
What this means in practice
- •For robotic system engineers: Enable faster global path planning for ground robots operating in large unstructured environments by replacing dense maps with compact graphs.
- •For autonomous vehicle developers: Reduce memory usage and planning times for navigation in complex terrains such as caves or mines by incorporating traversability-aware graph representations.
Authors
Gabriel Manuel Garcia, Stéphanie Aravecchia, Miguel Angel Olivares-Mendez
Abstract
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.