Improving Lower Bounds of the Shortest Path Problem in a 3D Environment of Axis Aligned Cuboids

This article addresses a 3D shortest path problem in the presence of obstacles. These obstacles are axis aligned cuboids. Our approach relaxes the collision constraint to compute a lower bound of the shortest path. The obstacles are decomposed into line segments that are treated as nodes in a graph. This method also allows for discontinuity between the entering and exiting points of the line segments. Numerical results demonstrate that the gap between our lower bound and the upper bound narrows and that the proposed method outperforms the traditional Euclidean distance as a lower bound.