A cell-decomposition based path planner for 3D navigation in constrained workspaces
2026-05-11 • Robotics
Robotics
AI summaryⓘ
The authors developed a method to split a map into smaller parts so that each part can clearly 'see' at least one neighbor, helping to check if a path exists between them. They used this method to create ways for computers to find paths efficiently, including simpler and more complex optimization techniques called SOCP and MISOCP. They also combined a path-finding algorithm with SOCP to make a faster and less memory-heavy solution named KSP-SOCP. Tested in city-like settings, their approach made it easier and faster for computers to find workable paths, especially in big maps.
binary occupancy gridcell decompositionpath feasibilitysecond-order cone programming (SOCP)mixed-integer SOCP (MISOCP)Yen's k-shortest path algorithmoptimizationvisibility graphworkspace
Authors
João P. L. Morais, Luciano C. A. Pimenta, Marcelo A. Santos, Guilherme V. Raffo
Abstract
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.