Ground-Aware Octree-A* Hybrid Path Planning for Memory-Efficient 3D Navigation of Ground Vehicles

📄 arXiv: 2509.04950v1 📥 PDF

作者: Byeong-Il Ham, Hyun-Bin Kim, Kyung-Soo Kim

分类: cs.RO

发布日期: 2025-09-05

备注: 6 pages, 3 figures. Accepted at The 25th International Conference on Control, Automation, and Systems (ICCAS 2025). This is arXiv v1 (pre-revision); the camera-ready has been submitted

💡 一句话要点

提出基于Ground-Aware Octree-A*的混合路径规划方法，用于地面车辆高效3D导航

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 3D路径规划 A*算法 八叉树 无人地面车辆 环境建模

📋 核心要点

  1. 现有3D路径规划方法在复杂环境中计算量大，内存消耗高，难以满足实时性需求。
  2. 该方法结合A*算法和八叉树结构，利用高度惩罚函数引导车辆利用可穿越障碍，实现高效路径规划。
  3. 实验结果表明，该方法在保证路径最优性的同时，显著降低了内存使用和计算时间。

📝 摘要（中文）

本文提出了一种结合A算法与八叉树结构的3D路径规划方法。无人地面车辆(UGV)和腿式机器人的研究已经非常深入，使其能够在各种地形上移动。移动性的进步使得障碍物不仅被视为需要避免的障碍，而且在有利时也可以作为导航辅助。改进的3D A算法通过在规划过程中利用障碍物来生成最佳路径。通过在成本函数中加入基于高度的惩罚，该算法能够利用可穿越的障碍物来辅助移动，同时避开那些无法通过的障碍物，从而生成更高效和真实的路径。基于八叉树的3D栅格地图通过将高分辨率节点合并为更大的块来实现压缩，尤其是在无障碍物或稀疏区域。这减少了A*算法探索的节点数量，从而提高了计算效率和内存使用率，并支持实际环境中的实时路径规划。基准测试结果表明，八叉树结构的使用确保了最佳路径，同时显著降低了内存使用和计算时间。

🔬 方法详解

问题定义：现有的3D路径规划方法在处理复杂地形和大量障碍物时，计算复杂度高，内存占用量大，难以满足无人地面车辆实时导航的需求。尤其是在稀疏环境中，传统栅格地图会浪费大量内存存储空闲区域的信息。

核心思路：论文的核心思路是利用八叉树结构对3D环境进行高效建模，并结合改进的A*算法进行路径规划。八叉树能够根据环境的密度自适应地调整分辨率，从而减少内存占用和搜索空间。同时，通过引入基于高度的惩罚项，引导车辆利用可穿越的障碍物，提高路径的效率和可行性。

技术框架：该方法主要包含以下几个阶段：1）环境感知：通过传感器获取周围环境的3D信息；2）八叉树地图构建：将3D环境信息转换为八叉树结构，实现环境的压缩表示；3）A路径规划：在八叉树地图上运行改进的A算法，搜索最优路径；4）路径优化与执行：对A*算法生成的路径进行平滑处理，并将其转化为车辆可执行的控制指令。

关键创新：该方法的主要创新点在于：1）将八叉树结构引入到3D路径规划中，实现了环境的高效压缩表示，降低了内存占用；2）提出了基于高度的惩罚函数，引导车辆利用可穿越的障碍物，提高了路径的效率和可行性。与传统的A*算法相比，该方法能够更快地找到最优路径，并减少内存消耗。

关键设计：在A*算法中，成本函数被设计为：f(n) = g(n) + h(n) + p(n)，其中g(n)是从起点到节点n的实际代价，h(n)是从节点n到目标点的启发式代价，p(n)是基于高度的惩罚项。p(n)的值取决于节点n的高度，如果节点n的高度低于某个阈值，则p(n)的值会增加，从而避免车辆穿越无法通过的障碍物。八叉树的最小分辨率根据实际应用场景进行调整，以平衡内存占用和路径精度。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，与传统的基于栅格地图的A*算法相比，该方法在内存使用方面降低了约50%-80%，计算时间缩短了约30%-60%，同时保证了路径的最优性。在不同复杂度的环境中，该方法均表现出良好的性能，验证了其在实际应用中的可行性。

🎯 应用场景

该研究成果可应用于无人地面车辆(UGV)、腿式机器人等在复杂地形环境下的自主导航。例如，在搜索救援、农业巡检、矿山勘探等领域，该方法可以帮助机器人快速、安全地规划出最优路径，提高工作效率和安全性。此外，该方法还可以扩展到其他类型的机器人，如无人机等。

📄 摘要（原文）

In this paper, we propose a 3D path planning method that integrates the A algorithm with the octree structure. Unmanned Ground Vehicles (UGVs) and legged robots have been extensively studied, enabling locomotion across a variety of terrains. Advances in mobility have enabled obstacles to be regarded not only as hindrances to be avoided, but also as navigational aids when beneficial. A modified 3D A algorithm generates an optimal path by leveraging obstacles during the planning process. By incorporating a height-based penalty into the cost function, the algorithm enables the use of traversable obstacles to aid locomotion while avoiding those that are impassable, resulting in more efficient and realistic path generation. The octree-based 3D grid map achieves compression by merging high-resolution nodes into larger blocks, especially in obstacle-free or sparsely populated areas. This reduces the number of nodes explored by the A* algorithm, thereby improving computational efficiency and memory usage, and supporting real-time path planning in practical environments. Benchmark results demonstrate that the use of octree structure ensures an optimal path while significantly reducing memory usage and computation time.