          |
GRASP Seminar Series: Fall 2005
September 16, 11:00 AM, 307 Levine Hall
Mireille Broucke
University of Toronto
"Necessary and Sufficient Conditions for Reachability on a Simplex"
Abstract: An area of sustained investigation over the last 15 years in hybrid system theory has been problems concerning reachability. These problems are split roughly between synthesis questions and verification questions. We consider the synthesis problem of designing controllers to satisfy reachability specifications. Examples of reachability specifications are safety specifications: a unsafe region of the state space may not be reached from a set of initial conditions; and (related to safety) invariance specifications: trajectories remain in a region of the state space.
In 2005 Tabuada and Pappas proposed a methodology based on bisimulations for solving the synthesis problem for linear discrete time systems when the reachability specification arises from a linear temporal logic (LTL) formula. In 2001 Habets and Van Schuppen proposed a highly constructive approach for linear affine systems that is based on triangulating the state space and then imposing reachability specifications on each simplex.
In this talk I will discuss extensions of the work of Habets and Van Schuppen. In particular, we focus on the problem of designing a linear affine control such that all trajectories of a linear affine system in a simplex exit via a set of facets, without first exiting through a set of restricted facets. I will discuss new necessary and sufficient conditions for reachability on a simplex, which are inspired by and generalize those of Habets and Van Schuppen. It will be shown through examples that even if the conditions of Habets and Van Schuppen fail, the problem of reachability may still be solvable. The essential observation in obtaining new necessary and sufficient conditions is that if a compact, convex set contains no equilibria, then all trajectories exit the set. This no-equilibrium requirement is translated to a so-called flow condition and this condition along with the conditions on the restricted facets give rise to a set of bilinear inequalities.
The solution of bilinear inequalities is NP-complete, so by exploiting the properties of linear affine systems, we devise an algorithm that reduces the problem to a series of linear programs. The complexity of this algorithm is still exponential in the state dimension. For the special case of a linear affine system with n-1 inputs, we devise an algorithm whose complexity is linear in the state dimension.
Examples will be given showing the effectiveness of the approach.
This is joint work with Bartek Roszak.
Biography: Mireille Broucke obtained the BSEE degree
in Electrical Engineering from the University of Texas at Austin in 1984
and the MSEE and PhD degrees from the University of California, Berkeley
in 1987 and 2000, respectively. She has six years industry experience
at Integrated Systems, Inc. and several aerospace companies. From 1993
to 1996 she acted as program manager and researcher at Partners for Advanced
Transportation and Highways (PATH). She is presently an Assistant Professor
in Electrical and Computer Engineering at the University of Toronto. Her
research interests are in hybrid system theory, multivehicle systems,
and nonlinear and geometric control theory.
GRASP
Laboratory
Site maintained by graspadm@grasp.cis.upenn.edu
Last update:
23 August, 2005