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.RO
发布日期: 2026-10-08
💡 一句话要点
提出STAG以解决机器人导航中的高效全局规划问题
🎯 匹配领域: 支柱三：空间感知与语义 (Perception & Semantics)
关键词: 稀疏图 全局规划 地形可 traversability 机器人导航 路径搜索 计算效率 内存优化
📋 核心要点
- 现有方法在处理大规模非结构化环境时，密集网格代价图的计算复杂度高，导致规划效率低下。
- STAG通过将代价图转换为稀疏图，结合中轴线拓扑和代表节点，优化了路径搜索的效率和内存使用。
- 实验结果显示，STAG在多个基准测试中显著提高了规划速度，减少了内存占用，同时保持了路径质量。
📝 摘要（中文）
自主探测车在大型非结构化环境中导航时，需要高效的全局规划来考虑地形可 traversability。然而，随着映射区域的扩大，搜索密集的网格代价图变得计算上昂贵。本文提出了STAG（稀疏可 traversability 感知图），将代价图转换为紧凑的图结构。STAG结合了中轴线拓扑骨架、同质可 traversability 区域的代表节点和靠近强可 traversability 梯度的过渡节点。边缘编码几何形状和可 traversability，以考虑路径长度和地形难度。通过在合成洞穴图、矿山图和DARPA CERBERUS数据集上比较STAG与密集网格的A*算法，STAG在203个地图实例和101,200个查询的五个基准类别中，将中位规划时间减少了3.4倍至9.9倍，峰值查询内存减少了2.1倍至15.4倍，中位相对路径长度差异为-2.9%至+7.6%。STAG为全局规划提供了一种紧凑的表示，牺牲了密集网格的可 traversability 最优性，以实现更快、更少内存消耗的搜索。
🔬 方法详解
问题定义：本文旨在解决自主探测车在大规模非结构化环境中进行高效全局规划的问题。现有的密集网格代价图方法在计算上非常昂贵，尤其是在大面积映射时，导致规划效率低下。
核心思路：STAG的核心思路是将密集的代价图转换为稀疏的图结构，通过中轴线拓扑和代表节点来简化搜索过程，从而提高规划效率和降低内存消耗。
技术框架：STAG的整体架构包括三个主要模块：中轴线拓扑骨架、同质可 traversability 区域的代表节点和过渡节点。中轴线提供了地形的基本结构，代表节点简化了同质区域的表示，而过渡节点则帮助处理强梯度区域的路径选择。
关键创新：STAG的主要创新在于其稀疏图表示方法，结合了地形几何信息和可 traversability 信息，显著提高了路径搜索的效率，与传统的密集网格方法相比，能够在保持路径质量的同时大幅降低计算复杂度。
关键设计：在设计中，STAG使用了特定的参数设置来优化节点的选择和边的构建，确保了图的紧凑性和有效性。此外，边缘的几何和可 traversability 编码方式也经过精心设计，以便在路径搜索时能够快速评估路径的可行性和难度。
🖼️ 关键图片
📊 实验亮点
实验结果表明，STAG在203个地图实例和101,200个查询中，规划时间中位数减少了3.4倍至9.9倍，峰值查询内存减少了2.1倍至15.4倍。尽管路径长度中位数相对变化为-2.9%至+7.6%，STAG仍然保持了良好的路径质量，展示了其在高效导航中的优势。
🎯 应用场景
STAG的研究成果在自主机器人导航、无人驾驶汽车和探测任务等领域具有广泛的应用潜力。通过提高全局规划的效率和降低内存需求，STAG能够支持更复杂的环境探索和实时决策，推动相关技术的进步与应用。未来，STAG可能在动态环境下的实时导航中发挥更大作用。
📄 摘要（原文）
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.