双向增量广义混合A*算法提升复杂系统实时路径规划效率
Bidirectional Incremental Generalized Hybrid A*
- 通过双向搜索与多分辨率层次迭代，避免顶点冻结导致的解遗漏
- 在R3/R4/R6问题上扩张次数显著减少，性能接近最优闭环控制
- 适合高动态、非结构化环境下的高速自主导航系统
针对复杂动力学系统在非结构化环境中进行高效任意时间运动规划的问题，传统A*因维度灾难不可行。混合A*虽通过状态空间离散化解耦，但引发树探索与分辨率耦合。增量广义混合A*（IGHA*）通过分层分辨率迭代与顶点冻结实现任意时间搜索，但冻结顶点可能隐藏后续解。本文提出双向增量广义混合A*（Bi-IGHA*），利用双向搜索从根本上缓解顶点隐藏问题。理论证明其保持单调成本改进与终止性保证；实验表明，该方法在R3、R4和R6规划任务中大幅减少节点扩展次数，在高速越野自主导航中实现与最优闭环控制相当的性能，且计算开销显著更低。
原文摘要 · Abstract (English)
We focus on the problem of efficient anytime kinodynamic planning for systems with complex dynamics in unstructured environments that make precomputing motion primitives infeasible. Directly applying A* to such problems is computationally infeasible due to the curse of dimensionality. Methods such as Hybrid A* addressed this burden by discretizing the state space, but in turn creating a coupling between tree discovery and the discretization resolution. The Incremental Generalized Hybrid A* (IGHA*) performs search over a hierarchy of resolutions in an anytime fashion to break this coupling, by freezing vertices to use in later search iterations rather than pruning them. However, the frozen vertices can hide solution-supporting vertices from the search at a particular iteration. While classical bidirectional search is motivated by the reduction of search depth, extending IGHA* into the bidirectional setting (termed Bi-IGHA*) obtains additional benefit by fundamentally mitigating the behaviour induced by frozen vertices hiding solutions. We show that Bi-IGHA* preserves IGHA*'s guarantees on monotonic cost improvement and termination. We empirically show that Bi-IGHA* substantially reduces expansions on R3, R4, and R6 planning problems, and achieves equivalent closed-loop performance with kinodynamic planning for high-speed off-road autonomy while requiring significantly fewer expansions. Website: https://personalrobotics.github.io/IGHAStar/biighastar.html
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。