STAG: A Sparse Traversability-Aware Graph Representation from Grid-Based Costmaps for Robotic Navigation

Gabriel Manuel Garcia; Stéphanie Aravecchia; Miguel Angel Olivares-Mendez

cs.ROOct 8, 2026

STAG: A Sparse Traversability-Aware Graph Representation from Grid-Based Costmaps for Robotic Navigation

Authors: Gabriel Manuel Garcia, Stéphanie Aravecchia, Miguel Angel Olivares-Mendez

Organizations: University of Luxembourg, Luxembourg · IRL Georgia Tech-CNRS, Metz, France

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.

Figures & tables

Fig. 1 : Overview of the STAG pipeline. An input traversability costmap is preprocessed to extract a topological backbone and traversability-aware region and transition nodes, which are combined into a unified sparse graph for A* planning and evaluation.

Panel of Figure 2 — Fig. 2 : Representative stages of STAG construction. Panels (a), (b), and (d) show the topological backbone, traversability-region representatives, and unified STAG graph, respectively, for the same traversability costmap. Panel (c) uses a separate costmap to illustrate the gradient-magnitude field and the selection of transition nodes near strong local traversability changes.

Fig. 3 : Query-level distributions of grid-based and STAG-based A* planning metrics for a representative synthetic mine, the Long synthetic mine, and the two DARPA-derived environments. The figure complements the aggregate five-category results in Table I . STAG reduces CPU time and peak query memory, while the path-quality trade-off varies with the environment.

Environment	Open cells	Queries	Nodes	Edges	CPU time [ms]			Peak memory [KiB]			$\boldsymbol{\Delta L}$	$\boldsymbol{\Delta C_{P}}$
					Grid	STAG	Factor	Grid	STAG	Factor	[%]	[%]
Synth caves	14,502	50,000	1,550	7,755	$658.0\pm 294.6$	$\mathbf{82.5\pm 31.8}$	8.0 $\times$	$1679.2\pm 605.4$	$\mathbf{203.4\pm 113.2}$	8.3 $\times$	+7.6	+6.9
Synth mines	5,918	50,000	1,416	7,536	$264.8\pm 48.9$	$\mathbf{77.2\pm 14.8}$	3.4 $\times$	$407.7\pm 76.7$	$\mathbf{198.1\pm 44.3}$	2.1 $\times$	+0.9	+3.4
Long synth mine	24,132	200	3,448	18,829	$1797.2\pm 500.6$	$\mathbf{181.2\pm 41.2}$	9.9 $\times$	$4158.3\pm 1493.4$	$\mathbf{603.4\pm 96.8}$	6.9 $\times$	-2.9	+2.0
DARPA 0.5 m	3,688	500	967	4,834	$260.6\pm 95.8$	$\mathbf{68.9\pm 37.4}$	3.8 $\times$	$400.2\pm 162.5$	$\mathbf{105.8\pm 17.1}$	3.8 $\times$	+6.0	+50.9
DARPA 0.25 m	14,756	500	1,274	5,897	$744.8\pm 478.8$	$\mathbf{98.2\pm 82.7}$	7.6 $\times$	$1883.3\pm 1000.4$	$\mathbf{122.0\pm 14.4}$	15.4 $\times$	+6.2	+38.2

TABLE I : Grid-based and STAG-based A* comparison. CPU time and peak memory correspond to the planning query, including endpoint attachment for STAG. CPU and memory entries report the median

\pm

one standard deviation. For Synthetic caves and Synthetic mines, the standard deviation is computed over the 100 environment-level medians; for the three single-map environments, it is computed over planning queries. The CPU speed-up and memory-reduction factors are computed from the reported medians as the grid value divided by the corresponding STAG value. Positive values of

\Delta L

and

\Delta C_{P}

indicate that the STAG path is longer or has a higher terrain penalty than the grid path.

Variant	Success	Failures	Main observation
Topology only	1560/1700	140	Sparse but less robust
Topology + region	1699/1700	1	Restores connectivity
Topology + transition	1605/1700	95	Adds detail, limited coverage
Full STAG	1699/1700	1	Robust coverage and transition

TABLE II : Component ablation on four representative maps comprising 1,700 grid-valid start-goal queries.

Explore similar work

Learning Traversability for Long Horizon Off-Road Navigation
Date pendingKasi Viswanath, Jason M. Gregory, Shaunak Kolhe +1Off-Road Robot Navigation Geospatial Representation Learning
Department of Mechanical Engineering, Texas A&M University, College Station, TX 77840, USA · DEVCOM Army Research laboratory, Adelphi, MD, USA
HOPHY: A Hierarchical Hypergraph Representation for Off-Road Path and Mission Planning
Sep 17, 2026Pranay Meshram, Charuvahan Adhivarahan, Prithvi Poddar +4Hierarchical Planning Graph-Based Planning
Department of Computer Science and Engineering, University at Buffalo, NY 14260, USA. · Department of Mechanical and Aerospace Engineering, University at Buffalo, NY 14260, USA.
SE(2) Navigation Mesh
Jul 1, 2026Shuyang Shi, Kaixian Qu, Changan Chen +3Constrained Motion Planning Robot Navigation
Robotic Systems Lab, ETH Zurich, Switzerland.

Date pending, cs.ROJ/K move · Enter open · S save

Learning Traversability for Long Horizon Off-Road Navigation

Kasi Viswanath, Jason M. Gregory, Shaunak Kolhe, Srikanth Saripalli

Department of Mechanical Engineering, Texas A&M University, College Station, TX 77840, USA · DEVCOM Army Research laboratory, Adelphi, MD, USA

Off-Road Robot Navigation Geospatial Representation Learning Robot Navigation Safe Robot Navigation

Open paper AskPDF arXiv

Autonomous navigation across large off-road environments remains a challenging problem. Onboard sensors perceive only the immediate surroundings, yet safe and efficient routes depend on terrain features that extend well beyond the sensor horizon. Geo-spatial data sources such as satellite imagery, aerial LiDAR, and vector maps can close this gap, but learning traversability from them is difficult: dense labels are unavailable at scale, and existing methods rely on short-range sensing. We propose an efficient formulation that learns a continuous traversability map from overhead data, supervised directly by human-driven GPS trajectories and shaped by supervised geometric priors from LiDAR. Alongside the model, we release a dataset, curated from public sources, consisting of 299 scenes spanning

\sim\!1{,}244\,\mathrm{km}^{2}

of diverse terrain, paired with

1{,}130\,\mathrm{km}

of human driving. In field trials on a Clearpath Warthog across seven routes at two sites,our method achieves trajectories within

5.5\%

of human path length and reduces operator interventions by

\sim\!85\%

compared to local-planner-only autonomy.

Abstract

Explore similar work

Learning Traversability for Long Horizon Off-Road Navigation

HOPHY: A Hierarchical Hypergraph Representation for Off-Road Path and Mission Planning

SE(2) Navigation Mesh