A Caltech Library Service

Real-Time Trajectory Generation for Constrained Nonlinear Dynamical Systems Using Non-Uniform Rational B-Spline Basis Functions


Flores Contreras, Melvin Estuardo (2008) Real-Time Trajectory Generation for Constrained Nonlinear Dynamical Systems Using Non-Uniform Rational B-Spline Basis Functions. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/TK01-9X60.


The thesis describes a new method for obtaining minimizers for optimal control problems whose minima serve as control policies for guiding nonlinear dynamical systems to achieve prescribed goals under imposed trajectory and actuator constraints. One of the major contributions of the present work resides in the approximation of such minimizers by piecewise polynomial functions expressed in terms of a linear combination of non-uniform rational B-spline (NURBS) basis functions and the judicious exploitation of the properties of the resulting NURBS curves to improve the computational effort often associated with solving optimal control problems for constrained dynamical systems.

In particular, by exploiting the two structures combined in a NURBS curve, NURBS basis functions and an associated union of overlapping polytopes constructed from the coefficients of the linear combination, we are able to separate an optimal control problem into two subproblems | guidance and obstacle avoidance, making the original problem tractable. This is accomplished by laying out the union of overlapping polytopes in such a way that they delineate a section of space that avoids all obstacles and then manipulating the NURBS basis functions to obtain trajectories that are guaranteed to remain bounded by this section of space without explicitly including the conjunction of disjunctions naturally induced from obstacles into the guidance problem.

In addition, we show how one can construct systematically a feasible region that corresponds to a NURBS parameterization starting from an ordered union of pairwise adjacently overlapping nonempty compact convex sets. Specifically, we show how to setup a nonlinear programming problem to solve for the feasible region in terms of an ordered union of pairwise adjacently overlapping polytopes with nonempty interiors by maximizing the sum of their volumes and starting from a feasible region described by an ordered union of pairwise adjacently overlapping nonempty convex compact simi-algebraic sets. Finally, we show how this strategy can be implemented practically for an autonomous system traversing an urban environment.

Finally, this work culminated in the filing of patent US20070179685 on behalf of Northrop Grumman for the Space Technology sector and in the development of the NURBS-based OTG software package. This C++ package contains the theoretical results of this thesis in the form of an object-oriented implementation optimized for real-time trajectory generation.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:constrained nonlinear systems; NURBS; optimal control; trajectory generation
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Control and Dynamical Systems
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Murray, Richard M.
Thesis Committee:
  • Murray, Richard M. (chair)
  • Marsden, Jerrold E.
  • Doyle, John Comstock
  • Milam, Mark B.
Defense Date:12 November 2007
Record Number:CaltechETD:etd-02192008-153449
Persistent URL:
Related URLs:
URLURL TypeDescription ItemU.S. Patent US20070179685A1
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:682
Deposited By: Imported from ETD-db
Deposited On:21 Feb 2008
Last Modified:17 Jan 2020 21:02

Thesis Files

PDF (Thesis) - Final Version
See Usage Policy.


Repository Staff Only: item control page