EECI09: Optimization-based 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:

• Optimization-based control: we describe how real-time 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 real-time 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 low-level 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: Optimization-based control
• Background reading: the material in this section is described in more detail in the course notes on Optimization-Based 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

Optimization-based 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. 789-814. 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 Optimization-Based Control, R. M. Murray et al. In Software-Enabled Control: Information Technology for Dynamical Systems, T. Samad and G. Balas (eds.), IEEE Press, 2001. This paper talks about the CLF-based nonlinear RHC approach and its application on the Caltech ducted fan using NTG.

• Unconstrained Receding-Horizon Control of Nonlinear Systems, A. Jadbabaie, J. Yu and J. Hauser. IEEE Transactions on Automatic Control, May 2001, Vol. 46, No. 5, pp. 776-783. This paper might be a little dense for the first read, but contains an essence of A. Jadbabaie's PhD thesis on CLF-based 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):558-565, 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 CNDS-98-4, 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 25-28, 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):549--557, 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 discrete-time 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.

• Real-Time 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 real-time, but has a much more user-friendly 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