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

Choe, Ronald

Permalink

https://hdl.handle.net/2142/97378 Copy

Description

Title

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

Author(s)

Choe, Ronald

Issue Date

2017-04-18

Director of Research (if dissertation) or Advisor (if thesis)

Hovakimyan, Naira

Doctoral Committee Chair(s)

Hovakimyan, Naira

Committee Member(s)

• Voulgaris, Petros G.
• Baryshnikov, Yuliy
• Nedic, Angelia
• Salapaka, Srinivasa M.

Department of Study

Aerospace Engineering

Discipline

Aerospace Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

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

Abstract

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.

Graduation Semester

2017-05

Type of Resource

text

Permalink

http://hdl.handle.net/2142/97378

Copyright and License Information

Copyright 2017 Ronald Choe

Owning Collections