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.
Keywords
Subject
Publication details
- Journal
- Not available
- Open access
- Green open access
Cite this article
APA 7
Garcia, G. M., Aravecchia, S., & Olivares-Mendez, M. A. (2026). STAG: A Sparse Traversability-Aware Graph Representation from Grid-Based Costmaps for Robotic Navigation. https://omanscience.com/en/articles/stag-a-sparse-traversability-aware-graph-representation-from-grid-based-costmaps-for-robotic-navigation
MLA 9
Garcia, Gabriel Manuel, et al. "STAG: A Sparse Traversability-Aware Graph Representation from Grid-Based Costmaps for Robotic Navigation." https://omanscience.com/en/articles/stag-a-sparse-traversability-aware-graph-representation-from-grid-based-costmaps-for-robotic-navigation.
Chicago (author–date)
Garcia, Gabriel Manuel, Stéphanie Aravecchia, and Miguel Angel Olivares-Mendez. 2026. "STAG: A Sparse Traversability-Aware Graph Representation from Grid-Based Costmaps for Robotic Navigation." https://omanscience.com/en/articles/stag-a-sparse-traversability-aware-graph-representation-from-grid-based-costmaps-for-robotic-navigation.
Harvard
Garcia, G. M., Aravecchia, S. and Olivares-Mendez, M. A. (2026) 'STAG: A Sparse Traversability-Aware Graph Representation from Grid-Based Costmaps for Robotic Navigation', Available at: https://omanscience.com/en/articles/stag-a-sparse-traversability-aware-graph-representation-from-grid-based-costmaps-for-robotic-navigation.
Vancouver
Garcia GM, Aravecchia S, Olivares-Mendez MA. STAG: A Sparse Traversability-Aware Graph Representation from Grid-Based Costmaps for Robotic Navigation. https://omanscience.com/en/articles/stag-a-sparse-traversability-aware-graph-representation-from-grid-based-costmaps-for-robotic-navigation
IEEE
G. M. Garcia, S. Aravecchia, and M. A. Olivares-Mendez, "STAG: A Sparse Traversability-Aware Graph Representation from Grid-Based Costmaps for Robotic Navigation," https://omanscience.com/en/articles/stag-a-sparse-traversability-aware-graph-representation-from-grid-based-costmaps-for-robotic-navigation.