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*算法和八叉树结构，利用高度惩罚函数引导UGV利用可通行障碍，优化路径。
  3. 实验结果表明，该方法在保证路径最优性的前提下，显著降低了内存使用和计算时间，提升了效率。

📝 摘要（中文）

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

🔬 方法详解

问题定义：无人地面车辆在复杂3D环境中进行路径规划时，传统的基于栅格地图的A*算法会产生大量的节点，导致内存占用过高，计算速度慢，难以满足实时性要求。尤其是在空旷区域，大量的节点是冗余的，浪费计算资源。现有方法难以兼顾路径质量、内存效率和计算速度。

核心思路：利用八叉树结构对3D环境进行建模，在空旷区域使用较大的节点，在障碍物附近使用较小的节点，从而减少节点总数，降低内存占用。同时，改进A*算法，使其能够利用可通行的障碍物，并加入高度惩罚项，引导车辆选择更优的路径。

技术框架：该方法主要包含两个阶段：1) 使用八叉树结构构建3D环境地图。根据环境的稀疏程度，自适应地调整八叉树的节点大小。2) 使用改进的A算法在八叉树地图上进行路径规划。A算法的代价函数中加入了高度惩罚项，鼓励车辆利用可通行的障碍物，并避开不可通行的障碍物。

关键创新：该方法的核心创新在于将八叉树结构与A*算法相结合，并引入了高度惩罚项。八叉树结构能够有效地压缩地图，减少内存占用和计算量。高度惩罚项能够引导车辆选择更优的路径，提高路径的质量。

关键设计：高度惩罚项的设计是关键。论文中，高度惩罚项与节点的高度相关，高度越高，惩罚越大。具体的惩罚函数形式需要根据实际应用场景进行调整。此外，八叉树的最小节点大小也需要根据环境的复杂程度进行调整。A*算法的启发式函数也需要仔细选择，以保证算法的效率和路径的最优性。

📊 实验亮点

实验结果表明，与传统的基于栅格地图的A*算法相比，该方法在保证路径最优性的前提下，显著降低了内存使用和计算时间。具体而言，内存使用降低了约50%-80%，计算时间降低了约30%-60%。这些提升使得该方法能够应用于更复杂的3D环境，并满足实时性要求。

🎯 应用场景

该研究成果可应用于无人地面车辆、腿式机器人等在复杂3D环境中的自主导航。例如，在灾后救援、矿山勘探、农业巡检等场景中，可以利用该方法规划出安全、高效的路径，提高作业效率和安全性。此外，该方法还可以应用于虚拟现实、游戏等领域，提供更真实的3D导航体验。

📄 摘要（原文）

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.