EECI09: Optimizationbased control
Prev: Introduction to NCS  Course home  Next: Information patterns 
This lecture will briefly summarize a number of standard results in control theory and embedded systems programming to define techniques and terminology that will be used later in the course:
 Optimizationbased control: we describe how realtime optimization can be used to design feedback control algorithms for nonlinear, constrained systems. The receding horizon control (RHC) principle is described and the main ingredients required for its stability are discussed. Efficient numerical methods can then be used to find trajectories that satify the system dynamics and constraints, as well as minimizing a cost function. We concentrate on methods for realtime trajectory generation, and in particular the NTG software package.
 State estimation: we briefly summarize the standard formalism for estimation and sensor fusion using Kalman filtering, as well as more recent approaches such as moving horizon estimation (MHE) and particle filters.
 Embedded systems programming: we briefly describe some of the software infractructure used to implement modern networked control systems, with a focus on networked and distributed systems. We focus on the use of spread as a specific example of a lowlevel message transfer subsystem and describe how it can be used in a NCS context. We then describe the Pthreads programming environment, which provides a standardized API for managing process threads.
This lecture covers a number of important concepts that we will build upon in a very concise manner. We assume that students are familiar with at least some of the basic concepts of optimal control, state estimators and random processes.
Lecture Materials
 Lecture slides: Optimizationbased control
 Background reading: the material in this section is described in more detail in the course notes on OptimizationBased Control:
 Chapter 1: Trajectory Generation and Tracking
 Chapter 2: Optimal Control
 Chapter 3: Receding Horizon Control
 Chapter 4: Stochastic Systems
 Chapter 5: Kalman Filtering
 Chapter 6: Sensor Fusion
Further Reading
Optimizationbased control

Constrained model predictive control: Stability and optimality, D. Q. Mayne, J. B. Rawlings, C. V. Rao and P. O. M. Scokaert. Automatica, 2000, Vol. 36, No. 6, pp. 789814. This is one of the most referenced comprehensive survey papers on MPC. Gives a nice overview about its history and explains the most important issues and various approaches.

Online Control Customization via OptimizationBased Control, R. M. Murray et al. In SoftwareEnabled Control: Information Technology for Dynamical Systems, T. Samad and G. Balas (eds.), IEEE Press, 2001. This paper talks about the CLFbased nonlinear RHC approach and its application on the Caltech ducted fan using NTG.

Unconstrained RecedingHorizon Control of Nonlinear Systems, A. Jadbabaie, J. Yu and J. Hauser. IEEE Transactions on Automatic Control, May 2001, Vol. 46, No. 5, pp. 776783. This paper might be a little dense for the first read, but contains an essence of A. Jadbabaie's PhD thesis on CLFbased nonlinear RHC.
Kalman filtering and state estimation

An Introduction to the Kalman Filter, G. Welch and G. Bishop. A brief introduction to the Kalman filter in discrete time. No proofs are given, but it is a good first read.

Wikipedia: Kalman Filter A webpage that gives a proof and some applications.

A New Approach to Linear Filtering and Prediction Problem, R.E. Kalman. Transactions of the ASME, Series D, 1960. A classical paper. Still very readable. It uses different notation than the lecture, and present a different and more general proof.

Optimal Filtering, B.D.O Anderson and J.B. Moore. Dover Books on Engineering, 2005. A reissue of a book from 1979. It contains a detailed mathematical presentation of filtering problems and the Kalman filter. A very good book.
Messaging Systems

Time, clocks, and the ordering of events in a distributed system, L. Lamport. Communications of the ACM, 21(7):558565, 1978. This is a classic paper on ordering of messages in distributed systems. A must read for distributed systems.

Exploiting virtual synchrony in distributed systems, K. Birman and T. Joseph. ACM Symposium on Operating Systems Principles, 1987. This paper gives a nice overview of some of the problems in group messaging systems and is one of the sets of papers that motivated the work that lead to Spread.
A Users Guide to Spread, J. Stanton. 2002. This is the documentation for the Spread Toolkit. The first and second chapters provide most of the information you need to understand the basic ideas, although the way in which Spread servers are configured, described in Chapter 3, is also useful.

The Spread Wide Area Group Communication System, Y. Amir and J. Stanton. Technical Report CNDS984, The Center for Networking and Distributed Systems, The Johns Hopkins University, 1998. The paper provides a detailed technical description of how Spread works. It is mainly useful if you want to know more about what spread does. Requires some background in network protocols if you want to understand the details.

A Low Latency, Loss Tolerant Architecture and Protocol for Wide Area Group Communication, Yair Amir, Claudiu Danilov, and Jonathan Stanton. International Conference on Dependable Systems and Networks (DSN00), New York, New York, June 2528, 2000. The paper is similar to the one above but with more technical details.
Threads

POSIX Threads Programming, Lawrence Livermore National Laboratory. 2006. This tutorial provides an introduction to Pthreads, the standard implementation of threads under linux. It's a pretty quick read, with examples of the code and pretty good descriptions of the basic pthreads functionality.

Monitors: An Operating System Structuring Concept, C. A. R. Hoare. Communciations of the ACM, 17(10):549557, 1974. This paper describes the concept of a "monitor", which is basically a function that uses mutexes to access a shared resourse. This is one of the early papers on concurrent computing and is cited as one of the design patterns for using threads and mutexes.

Cooperating Sequential Processes, E. W. Dijkstra. In Structured Programming, Academic Press, 1972. This is one of the most widely cited papers in concurrent programming and is often labelled as the paper that started the field. I haven't been able to locate an online copy yet (and haven't read it either).
Additional Information

Constrained Control and Estimation  An Optimisation Approach, G. C. Goodwin, M. M. Seron, J. A. De Dona. Springer Verlag, 2005. This is a recent book treating constrained control and estimation in a unified framework (including finite horizon optimal control and RHC) using discretetime formulation. The website has a lot of additional useful and interesting material.

Nonlinear Receding Horizon Control: A Control Lyapunov Function Approach, A. Jadbabaie. PhD Thesis, 2000.

RealTime Optimal Trajectory Generation for Constrained Dynamical Systems, M. Milam. PhD Thesis, 2003.

NTG software, version 2.2a, 2002. This is the last publically released version of NTG. The documentation is a bit sparse, but the examples are heavily commented.

Optragen, version 1.0, 2006. This is a new MATLAB toolbox for optimal trajectory generation written by Raktim Bhattacharya, a former postdoc at Caltech. This version does not run in realtime, but has a much more userfriendly interface than NTG.
 Spread Toolbox  The Spread Wide Area Group Communication System
 Neutral Message Language (NML) Programmers Guide  part of the NIST Realtime Control System library
 RoboFlag documentation  includes discussion of how RoboFlag network communications are implemented