Distributed cooperative trajectory generation for multiple autonomous vehicles using Pythagorean Hodograph Bézier curves

Trajectory generation;Path planning;Motion planning;Multi-vehicle;Distributed optimization;Bézier curves;Bundle methods;Nonsmooth optimization

Choe, Ronald

关键词: Trajectory generation;    Path planning;    Motion planning;    Multi-vehicle;    Distributed optimization;    Bézier curves;    Bundle methods;    Nonsmooth optimization;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/97378/CHOE-DISSERTATION-2017.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

This dissertation presents a framework for multi-vehicle trajectory generation that enables efficient computation of sets of feasible, collision-free trajectories for teams of autonomous vehicles executing cooperative missions with common objectives. Existing methods for multi-vehicle trajectory generation generally rely on discretization in time or space and, therefore, ensuring safe separation between the paths comes at the expense of an increase in computational complexity. On the contrary, the proposed framework is based on a three-dimensional geometric-dynamic approach that uses continuous Bézier curves with Pythagorean hodographs, a class of polynomial functions with attractive mathematical properties and a collection of highly efficient computational procedures associated with them. The use of these curves is critical to generate cooperative trajectories that are guaranteed to satisfy minimum separation distances, a key feature from a safety standpoint. By the differential flatness property of the dynamic system, the dynamic constraints can be expressed in terms of the trajectories and, therefore, in terms of Bézier polynomials. This allows the proposed framework to efficiently evaluate and, hence, observe the dynamic constraints of the vehicles, and satisfy mission-specific assignments such as simultaneous arrival at predefined locations. The dissertation also addresses the problem of distributing the computation of the trajectories over the vehicles, in order to prevent a single point of failure, inherently present in a centralized approach. The formulated cooperative trajectory-generation framework results in a semi-infinite programming problem, that falls under the class of nonsmooth optimization problems. The proposed distributed algorithm combines the bundle method, a widely used solver for nonsmooth optimization problems, with a distributed nonlinear programming method. In the latter, a distributed formulation is obtained by introducing local estimates of the vector of optimization variables and leveraging on a particular structure, imposed on the local minimizer of an equivalent centralized optimization problem.