arXiv:2508.13392cs.RO2025-08中稿 · IEEE RA-L, Nov 202…被引 3

提出动态调整搜索策略的IGHA*,让机器人在复杂地形中更快找到安全路径。

Incremental Generalized Hybrid A*

  • 基于增量式树搜索,不依赖固定网格,动态组织节点扩展顺序。
  • 在汽车类机器人上,相比优化版HA*减少6倍扩展次数,且保证最优性。
  • 适合需要实时规划的自动驾驶、无人车等复杂动态场景使用。

针对大规模树结构搜索效率问题,本文聚焦于非结构化环境下的实时自主规划需求。传统方法依赖运动基元图并利用支配关系剪枝,但复杂动力学下反复求解两点边值问题导致建图过慢。混合A*(HA*)通过树状搜索和网格化支配检查实现近似剪枝,但网格分辨率难以调优:过粗易失败,过细则增加扩展。为此,本文提出增量式广义混合A*(IGHA*),一种无需固定剪枝的在线树搜索框架,可动态组织顶点扩展。理论证明其性能不低于甚至优于HA*。在车辆类机器人的道路与非道路场景中,不同变体的IGHA*相较优化版HA*(HA*M)减少6倍扩展次数以达成最优解。仿真测试表明,在高保真模拟器中结合模型预测控制器运行时,IGHA*仍显著优于HA*M。实验证明其可在仿真及小型非道路车辆上实现实时规划,支持复杂动力学下的快速稳健路径生成。

原文摘要 · Abstract (English)

We address the problem of efficiently organizing search over very large trees, which arises in many applications ranging from autonomous driving to aerial vehicles. Here, we are motivated by off-road autonomy, where real-time planning is essential. Classical approaches use graphs of motion primitives and exploit dominance to mitigate the curse of dimensionality and prune expansions efficiently. However, for complex dynamics, repeatedly solving two-point boundary-value problems makes graph construction too slow for fast kinodynamic planning. Hybrid A* (HA*) addressed this challenge by searching over a tree of motion primitives and introducing approximate pruning using a grid-based dominance check. However, choosing the grid resolution is difficult: too coarse risks failure, while too fine leads to excessive expansions and slow planning. We propose Incremental Generalized Hybrid A* (IGHA*), an anytime tree-search framework that dynamically organizes vertex expansions without rigid pruning. IGHA* provably matches or outperforms HA*. For both on-road kinematic and off-road kinodynamic planning queries for a car-like robot, variants of IGHA* use 6x fewer expansions to the best solution compared to an optimized version of HA* (HA*M, an internal baseline). In simulated off-road experiments in a high-fidelity simulator, IGHA* outperforms HA*M when both are used in the loop with a model predictive controller. We demonstrate real-time performance both in simulation and on a small-scale off-road vehicle, enabling fast, robust planning under complex dynamics. Website: https://personalrobotics.github.io/IGHAStar/

路径规划机器人实时搜索强化学习

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。