制約環境下での3次元ナビゲーションのためのセル分割に基づく経路計画手法
A cell-decomposition based path planner for 3D navigation in constrained workspaces
占有グリッドを隣接セル間で相互可視性を保証するセルに分割し、その枠組みでSOCPやMISOCPによる経路最適化を可能にし、さらにYenのk最短経路とSOCPを組み合わせたKSP-SOCP法を提案した。都市様の環境で評価し、大規模問題に適した性能を示した。
詳しい要約
1. どんなもの?
2. 先行研究と比べてどこがすごい?
3. 技術・手法の肝は?
4. どうやって有効だと検証した?
5. 議論はある?
6. 次に読むべき論文は?
※ AIが要旨から生成した要約です。正確性は原文をご確認ください。
著者: João P. L. Morais, Luciano C. A. Pimenta, Marcelo A. Santos, Guilherme V. Raffo
分類: cs.RO
原文アブストラクト
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.
