Homotopy-Based Divide-and-Conquer Strategy for Optimal Trajectory Planning via Mixed-Integer Programming

Abstract

This paper proposes an optimal trajectory generation framework in which the global obstacle-avoidance problem is decomposed into simpler subproblems, corresponding to distinct path homotopies. In classical approaches to homotopic trajectory planning, trajectory planning and homotopy identification are performed simultaneously, leading to a substantial computational burden. The main benefit of the proposed approach is the development of a method to enumerate and explicitly represent distinct homotopy classes before trajectory planning or optimization, which allow the problem to be decomposed into simpler independent subproblems. The main contribution of the paper is twofold. The first contribution is the description of a method for utilizing existing cell-decomposition methods to enumerate and represent local trajectory generation problems that can be solved efficiently and independently. In addition, a relationship between the proposed cell-sequence representation and homotopy classes is analyzed. The second contribution is a computationally efficient novel formulation of the trajectory optimization problem within a cell sequence via mixed-integer quadratic programming (MIQP). Computational efficiency and increased solution richness of the proposed approach are demonstrated through simulation studies. The proposed MIQP formulation fits into a linear model-predictive control framework with nonconvex collision-free constraints.