Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.

  

Research Overview: Computational Geometry

As far as the laws of mathematics refer to reality, they are not certain; and as far as they are certain, they do not refer to reality.
- Albert Einstein

Geometry plays a central role in constrained control. There are many useful calculations that a control engineer might want to perform that come down to basic geometric operations on polyhedra such as projection, affine mapping or Minkowski sums. Control examples include operations such as computation of invariant sets, reachability analysis and parametric programming (for linear systems with linear constraints). In this section, I detail some of the work that we've done on basic polyhedral calculations.

Polytopic projection

Polytopes provide a useful representation for the linear constraints that appear in diverse fields such as control, finance and optimisation. The calculation of the orthogonal projection of a polytope is a fundamental operation that arises in many applications. For example, in control theory, projection is required for reachability analysis and in decision theory for the elimination of existential quantifiers. It can be shown that the calculation of affine maps or Minkowski sums of polytopes are both equivalent to orthogonal projection, making a projection algorithm a necessary tool for working with polytopes.

Our work on projection has gone in two directions. The first is the development of the algorithm Equality Set Projection (ESP), which is a polynomial output sensitive method for the calculation of the projection of polytopes. It should be stressed that it is (not surprisingly) only output sensitive when a particular type of general position assumption holds. However, we have also developed a perturbation method that can simulate general position for cases in which is does not hold (although the output sensitivity is lost).

We have also studied the relationship between parametric linear programming (pLP) and projection. Here we have shown that polyhedral projection can be written as a pLP and a pLP as projection. Given the significant advances in parametric programming in the last few years, this opens a large number of new methods for computing both exact and approximate projections.

The minimal invariant set of the longitudinal axis of a Boeing 747. Projections of randomly rotated hypercubes ranging from 4D to 50D.

Publications

C.N. Jones, E.C. Kerrigan, Jan M. Maciejowski, On Polyhedral Projection and Parametric Programming, Journal of Optimization Theory and Applications, volume 138 (2), April, 2008
More details available here
This note brings together two fundamental topics: polyhedral projection and parametric linear programming. First, it is shown that given a parametric linear program (pLP), a polyhedron exists whose projection provides the solution to the pLP. Second, the converse is tackled and it is shown how to formulate a pLP whose solution is the projection of an appropriately defined polyhedron described as the intersection of a finite number of halfspaces. The input to one operation can be converted to an input of the other operation and the resulting output can be converted back to the desired form in polynomial time - this implies that algorithms for computing projections or methods for solving parametric linear programs can be applied to either problem class.
C.N. Jones, E.C. Kerrigan, J.M. Maciejowski, Equality Set Projection: A new algorithm for the projection of polytopes in halfspace representation, CUED Technical Report CUED/F-INFENG/TR.463, 2004
More details available here
In this paper we introduce a new algorithm called Equality Set Projection ESP for computing the orthogonal projection of bounded, convex polytopes. Our solution addresses the case where the input polytope is represented as the intersection of a finite number of halfplanes and its projection is given in an irredundant halfspace form. Unlike many existing approaches, the key advantage offered by ESP is its output sensitivity, i.e., its complexity is a function of the number of facets in the projection of the polytope. This feature makes it particularly suited for many problems of theoretical and practical importance in which the number of vertices far exceeds the number of facets. Further, it is shown that for non-degenerate polytopes of fixed size (dimension and number of facets) the complexity is linear in the number of facets in the projection. Numerical results are presented that demonstrate that high dimensional polytopes can be projected efficiently.
C.N. Jones, Polyhedal Tools for Control, PhD Thesis, University of Cambridge, July, 2005
More details available here
Polyhedral operations play a central role in constrained control. One of the most fundamental operations is that of projection, required both by addition and multiplication. This thesis investigates projection and its relation to multi-parametric linear optimisation for the types of problems that are of particular interest to the control community. The first part of the thesis introduces an algorithm for the projection of polytopes in halfspace form, called Equality Set Projection (ESP). ESP has the desirable property of output sensitivity for non-degenerate polytopes. That is, a linear number of linear programs are needed per output facet of the projection. It is demonstrated that ESP is particularly well suited to control problems and comparative simulations are given, which greatly favour ESP. Part two is an investigation into the multi-parametric linear program (mpLP). The mpLP has received a lot of attention in the control literature as certain model predictive control problems can be posed as mpLPs and thereby pre-solved, eliminating the need for online optimisation. The structure of the solution to the mpLP is studied and an approach is presented that eliminates degeneracy. This approach causes the control input to be continuous, preventing chattering, which is a significant problem in control with a linear cost. Four new enumeration methods are presented that have benefits for various control problems and comparative simulations demonstrate that they outperform existing codes. The third part studies the relationship between projection and multi-parametric linear programs. It is shown that projections can be posed as mpLPs and mpLPs as projections, demonstrating the fundamental nature of both of these problems. The output of a multi-parametric linear program that has been solved for the MPC control inputs offline is a piecewise linear controller defined over a union of polyhedra. The online work is then to determine which region the current measured state is in and apply the appropriate linear control law. This final part introduces a new method of searching for the appropriate region by posing the problem as a nearest neighbour search. This search can be done in logarithmic time and we demonstrate speed increases from 20Hz to 20kHz for a large example system.

Talks

C.N. Jones, Polyhedral Tools for Control, Automatic Control Lab, ETH Zentrum, Nov 2005
More details available here
This talk discusses the relationships between the three fundamental geometric operations of vertex enumeration, (multi)parametric linear programming and polyhedral projection.
C.N. Jones, Polyhedral Tools for Control, Seminar, Automatic Control Lab, ETH Zurich, 2005
More details available here
This talk discusses the relationships between the three fundamental geometric operations of vertex enumeration, (multi)parametric linear programming and polyhedral projection.

Software: Projection

The Equality Set Projection (ESP) code is available in Matlab as an alpha release here. To see how it works type 'help esp' at the Matlab command prompt.

The ESP code is included in the MPT Toolbox in the projection function (along with several other projection methods). If you find any bugs in the software I would love to hear about them.

If you would like to run the 'old favourite' fourier elimination, I have written mex-code (Matlab compatible C code), which is available here for Windows and Linux.

The work in this section was done in collaboration with

Approximation of convex bodies

Many of the operations that one may want to perform on convex sets are either very difficult, or result in very complex objects (e.g. large number of facets in the case of polyhedra). We are here interested in producing algorithms that can approximate these objects with simple polyhedra. One of our primary motivations for doing this is the production of approximate explicit control laws with good properties from the control point of view (i.e. guarantees of stability, invariance; specified complexity, etc).

Incremental approximate projection of a high-dimensional hypercube to 3D. Incremental approximate projection of a high-dimensional random polytope to 3D.
Beneath/Beyond is used to approximate the projection from the inside out, while simultaneously the double description method approximates outside/in. (See papers below)

Publications

C.N. Jones, M. Morari, The Double Description Method for the Approximation of Explicit MPC Control Laws, Conference on Decision and Control, 2008
A standard model predictive controller (MPC) can be written as a parametric optimization problem whose solution is a piecewise affine (PWA) map from the measured state to the optimal control input. The primary limitation of this optimal ‘explicit solution’ is that the complexity can grow quickly with problem size, and so in this paper we seek to compute approximate explicit control laws that can tradeoff complexity for approximation error. This computation is accomplished in a two-phase process: First, inner and outer polyhedral approximations of the the convex cost function of the parametric problem are computed with an algorithm based on an extension to the classic double-description method; a convex hull approach. The proposed method has two main advantages from a control point of view: it is an incremental approach, meaning that an approximation of any specified complexity can be produced and it operates on implicitlydefined convex sets, meaning that the optimal solution of the parametric problem is not required. In the second phase of the algorithm, a feasible approximate control law is computed that has the cost function derived in the first phase. For this purpose, a new interpolation method is introduced based on recent work on barycentric interpolation [1]. The resulting control law is continuous, although non-linear and defined over a non-simplical polytopic partition of the state space. The nonsimplical nature of the partition generates significantly simpler approximate control laws than current competing methods, as demonstrated on computational examples.
Accepted to CDC 2008. Details and pre-print to appear soon.
C.N. Jones, M. Baric, M. Morari, Multiparametric Linear Programming with Applications to Control, European Journal of Control, vol. 13, no. 2-3, pp. 152-170, Mar 2007
More details available here
Parametric programming has received a lot of attention in the control literature in the past few years due to the fact that model predictive controllers (MPC) can be posed in a parametric framework and hence pre--solved offline resulting in a significant increase in online computation speed. In this paper we survey recent work on parametric linear programming (pLP) from the point of view of the control engineer. We identify three types of algorithms, two arising from standard convex hull paradigms and one from a geometric intuition, and classify all currently proposed methods under these headings. Through this classification, we identify a third standard convex hull approach that offers significant potential for approximation of pLPs for the purpose of control. We present the resulting algorithm, based on the beneath/beyond paradigm, that computes low--complexity approximate controllers that guarantee stability and feasibility. Finally, numerical examples are provided that demonstrate the relative merits of the surveyed methods on problems of interest to control engineers.

Talks

C.N. Jones, Polyhedral Tools for Control, Automatic Control Lab, ETH Zentrum, Nov 2005
More details available here
This talk discusses the relationships between the three fundamental geometric operations of vertex enumeration, (multi)parametric linear programming and polyhedral projection.

Software: Polytopic approximation of convex objects

We have implementations of the implicit double description and beneath/beyond algorithms described in the papers above. However, they are very alpha and so we're still working out the bugs. If you'd like to help us do that, then drop me an email for a copy.

The work in this section was done in collaboration with

Further reading



Last modified: April 24 2009.