提出一种3D受限空间路径规划的网格分解方法，提升路径可行性验证效率。
A cell-decomposition based path planner for 3D navigation in constrained workspaces
- 基于网格分解确保相邻单元间完全可视，简化路径可行性验证。
- 在9个城市级场景中，算法高效分割地图并求解可行路径。
- 结合k最短路与优化模型，兼顾速度与内存，适合大规模问题。
本文提出一种针对二值占用网格的单元分解算法，确保每个单元至少与一个相邻单元互视完全。该分解构建了一个简化的路径可行性验证框架，可轻松嵌入优化问题。为展示其效用，我们在该框架内建立了二阶锥规划（SOCP）及其混合整数变体（MISOCP）。进一步提出KSP-SOCP方法，结合Yen的k最短路径算法与SOCP，相比标准SOCP获得更优解，同时避免MISOCP的计算开销。在9个类城市工作空间中评估了该分解算法、KSP-SOCP与MISOCP方法。分解算法高效划分每张地图，使两种优化方法均可计算出可行路径。所提KSP-SOCP在时间性能上接近MISOCP，但所需内存更少，适用于大规模问题。
原文摘要 · Abstract (English)
This paper proposes a cell decomposition algorithm for binary occupancy grids that ensures mutual complete visibility from each cell to at least one adjacent cell. This decomposition establishes a simplified framework for verifying path feasibility that can be easily embedded in optimization problems. To illustrate its utility, we formulate both second-order cone programs (SOCP) and their mixed-integer variant (MISOCP) within the proposed framework. Furthermore, we propose the KSP-SOCP method, which combines Yen's k-shortest path algorithm with the SOCP, achieving improved solutions compared to a standard SOCP approach while avoiding the computational burden of MISOCP. The cell decomposition algorithm, KSP-SOCP, and MISOCP approaches were evaluated in 9 city-like workspaces. The decomposition efficiently partitioned each map, enabling both optimization methods to compute feasible paths. The proposed KSP-SOCP achieved time performance comparable to the MISOCP while requiring less memory, making it highly suitable for large-scale problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。