From Obstacle-Based Space Partitioning to Corridors and Path Planning. A Convex Lifting Approach

Abstract : This letter proposes a novel methodology for path generation in known and congested multi-obstacle environments. Our aim is to solve an open problem in navigation within such environments the feasible space partitioning in accordance with the distribution of obstacles. It is shown that such a partitioning is a key concept toward the generation of a corridor in cluttered environments. Once a corridor between an initial and a final position is generated, the selection of a path is considerably simplified in comparison with the methods which explore the original non-convex feasible regions of the environment. The core of the methodology presented here is the construction of a convex lifting which boils down to a convex optimization. This letter covers both the mathematical foundations and the computational details of the implementation and aims to illustrate the concepts with geometrical examples