SBCR-A*: Supercover-Based Corridor Reconstruction for Optimal Path Length in Grid-Based Navigation

Abstract

Abstract Grid-based path planning and optimization remain widely used in robotics and autonomous navigation because real environments can be discretized into binary occupancy grids, allowing algorithms such as A* to guarantee a solution whenever a collision-free path exists. However, the resulting grid paths are often suboptimal in length and contain unnecessary directional changes, which increase traversal time, energy consumption, and control effort. This paper proposes Supercover-Based Corridor Reconstructed A* (SBCR-A*), a framework that combines an A* search backbone with an SBCR reconstruction pipeline to convert discrete grid paths into trajectories with improved path-length optimality while preserving collision-freedom. SBCR-A* utilizes a supercover-based line-of-sight formulation together with obstacle-boundary-guided refinement to replace stepwise grid paths with a small number of long, straight, feasible segments. On the Göttingen Maze Dataset, SBCR-A* achieves a path optimality of $$107.72\%$$ 107.72 % relative to standard A*, which is the highest path optimality among all methods evaluated in this study, including recent learning-based planners and existing A*-based improvements. Moreover, when the SBCR-A* reconstruction pipeline is decoupled from its own search component and applied to paths produced by these A*-based variants, it delivers additional average path-length reductions in the range $$1.85\%-5.71\%$$ 1.85 % - 5.71 % . To the best of our knowledge, no existing reconstruction method achieves higher path optimality on these benchmarks while providing equally general, planner-agnostic integration. Consequently, SBCR-A* can be regarded as a state-of-the-art reconstruction framework for improving the geometric quality and optimality of grid-based paths.