PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2610.11943v1cs.RO

TL;DR

Large unstructured environments require global planning that accounts for terrain difficulty, but dense costmap search becomes expensive as maps grow. STAG converts costmaps into sparse graphs combining a medial-axis backbone with traversability-aware nodes and edge attributes. Across the reported environments, it reduces planning time and memory while keeping geometric path length close to the grid baseline, with increased traversability penalty on complex DARPA-derived maps.

  • Problem

    Dense costmap search becomes increasingly expensive as mapped areas grow, while long-range autonomous missions have limited onboard computation and need terrain-aware planning.

    Source: §I · p. 1

  • Method

    STAG converts traversability costmaps into compact graphs combining a medial-axis backbone, traversability-region and transition nodes, and geometric and terrain-cost edge attributes.

    Source: §I · p. 1, §VI · pp. 7–8

  • Results

    STAG consistently reduced query time and peak Python allocations, yielding approximately 3× to 10× faster planning and 2× to 15× lower peak allocations than grid-based A*, while keeping geometric path length close to the grid baseline; accumulated traversability penalty increased on the more complex DARPA-derived maps.

    Source: E. Discussion · p. 6, §VI · p. 8

  • Takeaways & Limitations

    STAG is suited to sparse global planning, long-range navigation, and repeated queries, with local planning on the original costmap recommended for precise terrain-cost optimization.

    Source: F. Limitations and Scope · p. 7

    Sparse abstraction can lose fine local traversability variations, reflected by increased accumulated traversability cost on DARPA-style maps; the authors recommend combining STAG with a local planner or trajectory optimizer on the original costmap.

    Source: F. Limitations and Scope · p. 7

Abstract

from arXiv · show

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.

I. INTRODUCTION

Dense costmap search grows costly on large maps, while many graph abstractions do not preserve terrain-cost variation. STAG combines sparse geometric and traversability structure, with reported gains in planning efficiency and a trade-off in traversability optimality.

I. INTRODUCTION

  • Dense-grid planning grows increasingly expensive as map area expands because every traversable cell can become a search state, burdening repeated long-range queries.The passage frames this as a practical limitation for missions with limited onboard computation and communication.Source: §I · p. 1
  • Existing topological graphs mainly encode geometry, while traversability-aware graph methods may be tied to particular sensing modalities, connection strategies, or planners.These limitations motivate an abstraction that retains terrain information while searching fewer states.Source: §I · p. 1
  • STAG converts costmaps into a sparse graph that preserves free-space connectivity and selected traversability structure.Its components are a medial-axis backbone, nodes for homogeneous traversability regions, and nodes near strong traversability gradients; edges encode geometry and terrain attributes.Source: §I · p. 1
  • STAG reduces the number of planning states compared with the original grid-based traversability costmap.The paper presents this as a core contribution of its sparse representation.Source: §I · p. 1
  • STAG reduces query time and memory relative to dense-grid search while preserving global path geometry closely, with a measurable trade-off in traversability optimality.The evaluation compares grid-based A* and STAG-based A* across synthetic cave and mine maps and DARPA-derived traversability maps.Source: §I · pp. 1–2

II. RELATED WORK

Prior representations reduce search complexity through grids, topological graphs, or terrain-aware structures, but leave a need for a reusable graph that combines connectivity with costmap traversability. STAG targets that role with deterministic node sources and explicit edge attributes.

A. Grid-Based and Multi-Resolution Representations

  • Grid-based costmaps retain spatial and terrain-cost resolution, but search-state counts grow with map extent and resolution; multi-resolution methods reduce the burden while remaining tied to a grid hierarchy.STAG instead builds an explicit reusable graph from the input costmap.Source: A. Grid-Based and Multi-Resolution… · p. 2, §II · p. 2

B. Skeleton and Topological Graphs

  • Skeleton and topological graphs compactly preserve free-space connectivity, but geometry-driven construction can leave areas with different traversal difficulty indistinguishable.STAG retains a medial-axis backbone while adding nodes selected from traversability and terrain statistics on edges.Source: B. Skeleton and Topological Graphs · p. 2

C. Traversability-Aware and Region-Based Graphs

  • Traversability-aware graphs encode terrain risk but are often coupled to a sensing modality, sampling procedure, or specialized planner; region-based methods may instead focus on perception or terrain estimation.STAG targets compression of an already available two-dimensional planning costmap, with backbone, homogeneous-region, and high-gradient transition nodes and explicit edge geometry, clearance, and traversability.Source: C. Traversability-Aware and… · p. 2

III. METHODOLOGY

STAG constructs a sparse graph from an input traversability costmap by combining topological and traversability-selected nodes. Its backbone derives from the medial axis of traversable space and preserves connectivity with fewer planning states.

III. METHODOLOGY

  • STAG builds a graph from a traversability costmap using a topological backbone, homogeneous traversability-region nodes, and nodes near high-gradient terrain transitions.Edges retain geometric and terrain-related attributes so graph search can evaluate distance and terrain difficulty without expanding all traversable cells.Source: §III · p. 2, Figure 1 · p. 3

A. Input Representation

  • The input is represented by a normalized traversability score field, with obstacle and unknown cells invalidated; cells below the minimum accepted score are nontraversable.The terrain penalty assigns higher values to more difficult terrain.Source: A. Input Representation · pp. 2–3

B. Topological Backbone

  • An Euclidean distance transform of the traversable mask yields the medial-axis skeleton, whose endpoints, junctions, and connecting chains form a compact graph backbone.Backbone edges store geometric length and clearance statistics, preserving main free-space connectivity while reducing planning states.Source: B. Topological Backbone · p. 3

C. Traversability-Aware Nodes

STAG adds traversability-aware nodes because a topological graph preserves connectivity but does not fully represent terrain difficulty. Region nodes summarize connected areas with similar traversability values.

1) Region Nodes:

  • Traversability is discretized into classes, and connected components are extracted independently within each class.Each component is a connected region of cells.Source: 1) Region Nodes · p. 3
  • The selected region nodes summarize areas with similar traversability values.Source: 1) Region Nodes · p. 3
  • Each region node is the valid cell in its connected component closest to that component’s centroid.This selects one representative cell per component.Source: 1) Region Nodes · p. 3

2) Transition Nodes:

STAG adds transition nodes near strong local changes in traversability, which region nodes do not explicitly represent.

2) Transition Nodes:

  • Transition-node candidates are traversable local maxima of the smoothed traversability gradient that exceed a threshold.Large gradient magnitudes indicate strong local changes in terrain difficulty.Source: 2) Transition Nodes · p. 3
  • Candidates are processed in decreasing gradient magnitude, with minimum spatial separation enforced to avoid redundant nodes.Source: 2) Transition Nodes · pp. 3–4
  • The retained candidates form the transition-node set, whose distribution is illustrated in Fig. 2c.Source: 2) Transition Nodes · p. 4

D. Unified Graph Construction

STAG combines topological, region, and transition nodes into one graph while preserving the topological backbone’s connectivity and retaining traversability information for path planning.

D. Unified Graph Construction

  • The unified graph’s node set combines topological, region, and transition nodes.The topological set also includes nodes inserted when existing edges are split.Source: D. Unified Graph Construction · p. 4
  • Connectors from region and transition nodes are retained only when their paths remain traversable and meet minimum clearance.A connector ending inside a topological edge causes that edge to be split at a newly inserted topological node.Source: D. Unified Graph Construction · p. 4
  • Each edge stores geometric length, minimum and mean clearance, and minimum and mean traversability scores for planning over distance and terrain difficulty.Source: D. Unified Graph Construction · p. 4
  • The resulting graph preserves the environment’s main connectivity while retaining traversability information needed for path planning.Source: D. Unified Graph Construction · p. 4

IV. EXPERIMENTS

The experiments compare A* on STAG with A* on the original grid costmap using matched start-goal queries. They evaluate 203 maps across five categories and 101,200 queries, with query measurements excluding graph construction.

IV. EXPERIMENTS

  • Both representations use A* on the same start-goal queries, isolating the representation’s effect from the planner’s.Reported results are medians over accepted queries for each map.Source: §IV · p. 4

A. Benchmark Setup

  • Timing and memory are measured during planning queries, excluding graph construction; STAG timing includes start-goal attachment.Start and goal cells are attached to graph nodes through traversable straight-line connections.Source: §IV · p. 4, A. Benchmark Setup · p. 4
  • 203 traversability-map instances across five benchmark categories were evaluated using 101,200 planning queries.The categories include 100 synthetic caves, 100 synthetic mines, one long synthetic mine, and two DARPA-derived maps.Source: A. Benchmark Setup · p. 4
  • Only matched pairs for which both grid-based A* and STAG-based A* return valid paths are included in the metrics.Source: A. Benchmark Setup · p. 4

B. Cost Function and Metrics

The section defines a shared A* cost that balances geometric length and terrain difficulty, then specifies the path measures and query metrics used for comparison.

B. Cost Function and Metrics

  • A* minimizes a cost combining geometric length and terrain difficulty, with λ = 4 used for both grid and STAG representations.The terrain influence is controlled by λ.Source: B. Cost Function and Metrics · pp. 4–5
  • For each path, the evaluation records geometric length and accumulated traversability penalty, alongside cumulative planning cost.The section also defines relative path-length and penalty differences for matched queries; positive differences mean STAG has a longer path or larger terrain penalty than the grid path.Source: B. Cost Function and Metrics · p. 5
  • The evaluation measures representation size, per-query planning time and peak memory, geometric path length, and accumulated traversability penalty.Representation size counts traversable cells for the grid and nodes and edges for STAG.Source: B. Cost Function and Metrics · pp. 5–6

V. RESULTS AND DISCUSSION

Across the evaluated environments, STAG reduces planning time and peak query memory while substantially reducing planning states. Path lengths remain close to the grid baseline, with a clearer traversability-penalty trade-off on DARPA-derived maps.

A. Representation Compression

  • STAG used 1,550 nodes versus 14,502 traversable grid cells in synthetic caves, and 1,274 nodes versus 14,756 cells in the DARPA 0.25 m map.Graph edges may remain numerous, but each represents a larger traversable segment than a grid-cell transition.Source: A. Representation Compression · p. 6

B. Planning Time and Memory

  • Planning time fell 8× in synthetic caves, from 658 ms on the grid to 82.5 ms on STAG, while peak-memory reduction ranged from 2.1× to 15.4× across categories.The Long synthetic mine had a 9.9× planning-time speed-up and a 6.9× memory reduction.Source: B. Planning Time and Memory · p. 6

C. Path Quality

  • Median relative path-length differences were +7.6% for Synthetic caves, +0.9% for Synthetic mines, and −2.9% for the Long synthetic mine.The two DARPA-derived maps had increases of +6.0% and +6.2%; the negative Long synthetic mine difference does not necessarily indicate a better solution because the representations use different motion primitives.Source: C. Path Quality · p. 6
  • Median traversability-penalty differences reached +50.9% at 0.5 m and +38.2% at 0.25 m on DARPA-derived maps.The corresponding differences were +6.9% for Synthetic caves, +3.4% for Synthetic mines, and +2.0% for the Long synthetic mine.Source: C. Path Quality · p. 6

D. Component Ablation

The ablation identifies region nodes as central to robust query coverage. The discussion frames STAG as a sparse, efficient global-planning abstraction rather than a reproduction of dense-grid optimal paths.

D. Component Ablation

  • The ablation compares backbone-only, region-node, transition-node, and full-STAG variants on four maps using the same 1,700 grid-valid start-goal queries.Source: D. Component Ablation · p. 6
  • Region nodes remove nearly all failures and chiefly support query coverage and traversability-aware path quality; transition nodes encode cost discontinuities but do not consistently lower traversability penalty under current A* weighting.Source: D. Component Ablation · p. 6, Table II · p. 7

E. Discussion

  • STAG is suited to global planning, long-range navigation, and repeated queries; precise local terrain-cost optimization should use a local planner on the original costmap.Source: E. Discussion · p. 6
  • Across benchmark categories, STAG reduces planning states, time, and peak query memory while keeping path length close; traversability cost is nearly preserved in synthetic mines but increases on DARPA-style maps.Source: E. Discussion · p. 6, Table I · p. 7, Figure 3 · p. 7
  • The evaluation’s claims are limited to comparing STAG with the original grid using the same A*, cost function, and queries, while acknowledging a measurable path-quality trade-off.Source: E. Discussion · pp. 6–7

F. Limitations and Scope

STAG is presented as a lightweight global-planning representation: geometric path lengths stay close to the grid baseline, while sparse abstraction can increase traversability penalties. The authors recommend pairing it with local planning on the original costmap.

F. Limitations and Scope

  • The evaluation compares grid-based and STAG-based A* on identical start-goal queries, without claiming superiority over dedicated traversability-graph planners or evaluating dynamic replanning and online graph updates.Source: F. Limitations and Scope · p. 7

VI. CONCLUSION

  • STAG combines a medial-axis backbone with traversability-aware region and transition nodes, storing geometric, clearance, and terrain-cost attributes on graph edges.Source: §VI · pp. 7–8
  • Approximately 3×–10× faster planning and 2×–15× lower peak allocations than grid-based A*, while geometric path length stays close to the baseline.The evaluation covers synthetic cave and mine environments and two DARPA-derived maps.Source: §VI · p. 8

F. Limitations and Scope

  • On more complex DARPA-derived maps, accumulated traversability penalty increases even when path length remains close to the grid baseline.The authors recommend using a local planner or trajectory optimizer on the original costmap near the robot or selected global route.Source: F. Limitations and Scope · p. 7, §VI · p. 8

VI. CONCLUSION

  • In the component ablation, region nodes contribute most to endpoint coverage, graph-query success, and traversability-aware path-quality recovery; transition nodes add terrain-cost structure not consistently used by current A* weighting.Source: §VI · p. 8
  • STAG is intended as a lightweight global-planning representation, not a replacement for dense local costmap planning; future work includes adaptive refinement and hybrid graph-grid planning.Source: §VI · p. 8
Loading 2610.11943v1…