1

ME233 Advanced Control II
Lecture 1
Dynamic Programming &Optimal Linear Quadratic Regulators (LQR)(ME233 Class Notes DP1-DP4)

2

Outline1. Dynamic Programming

2. Simple multi-stage example

3. Solution of finite-horizon optimal
Linear Quadratic Reguator (LQR)

3

Dynamic Programming
Invented by Richard Bellman in 1953
• From IEEE History Center: Richard Bellman:– “His invention of dynamic programming in
1953 was a major breakthrough in the theoryof multistage decision processes…”– “A breakthrough which set the stage for theapplication of functional equation techniques
in a wide spectrum of fields…”– “…extending far beyond the problem-areas
which provided the initial motivation for hisideas.”

4

Dynamic Programming
Invented by Richard Bellman in 1953
• From IEEE History Center: Richard Bellman:– In 1946 he entered Princeton as a graduate
student at age 26.
– He completed his Ph.D. degree in a record
time of three months.
– His Ph.D. thesis entitled “Stability Theory ofDifferential Equations" (1946) wassubsequently published as a book in 1953,
and is regarded as a classic in its field.

5Dynamic Programming
We will use dynamic programming to derive thesolution of:• Discrete time LQR and related problems• Discrete time Linear Quadratic Gaussian(LQG) controller.
– Optimal estimation and regulation

6

Dynamic Programming Example
6Illustrative Example:

913

Find “optimal” path:
From A to B

10

Aby moving only to the right.

135 86612 77 1512 6775 10

11 14

10 8

914

88101091112

115Boknot ok

15 96 121210ok

if we are here…

B

7

Dynamic Programming Example
6

Illustrative Example:
Find “optimal” path:
From A to B
by moving only to the right.

91310A135 89612 77 15

12 6

775 10

11 14

10 86

• Number next to line is the“cost” in going along thatparticular path.

15 9

6 12

1210

14

8810

105

9

11
11

12B

8

Dynamic Programming Example
6

Illustrative Example:

913

Find “optimal” path:
From A to B

10A
13

by moving only to the right.

5 8

67B

612 7

7 15

12 6

775 10

11 14

10 8

91115 96 12

1210

14

8

8

101059111112B

9

Dynamic Programming Example
6Illustrative Example:
Find “optimal” path:
From A to B

91310A
13by moving only to the right.

5 8

616B

612 7

7 15

12 6

775 10

11 14

10 8

92315 9

6 12

12

10

1488

10

105

9

11
11

12

B

10

Dynamic Programming Example
6Illustrative Example:
Find optimal path:
From A to B

91310

A

by moving only to the right.

135 89612 77 15

12 6775 10

11 14

10 86

• Optimal path from A to B
is the one with thesmallest overall cost.

15 96 1212101488101091112115• There are 70 possible
routes starting from A.

B11

Dynamic Programming
Key idea:• Convert a single “large” optimization problem
into a series of “small” multistage optimizationproblems.
– Principle of optimality: “From any point on
an optimal trajectory, the remaining trajectoryis optimal for the corresponding problem
initiated at that point.”– Optimal Value Function: Compute theoptimal value of the cost from each state tothe final state.

12

Dynamic Programming Example
6

Illustrative Example:•••

Use principle of optimality
13
Compute Optimal Value Function and105
optimal control at each stateA
12Start from the final state B

87612 77 1512 6

775 1011 1410 86915 96 1213

9determine theoptimal path
fromto B

910

14

88

10

10

911

B

12

115

B

11
12

assume that
we are here…

13

Dynamic Programming Example
6

Illustrative Example:•••

Use principle of optimality
13
Compute Optimal Value Function and
105
optimal control at each stateA
12Start from the final state B

99897 + 9 = 16
711 + 12 = 23111212 714881010B

67 15

12 6

775 10

11 14

10 8

6

two options:

15 96 1213

1059111112B

14

Dynamic Programming Example
6Illustrative Example:•••

Use principle of optimality
13
Compute Optimal Value Function and
105
optimal control at each stateA
12Start from the final state B

81212 7

14

8

8

10

10

B

16

6

7 15

12 6

775 10

11 14

10 86

915 9

6 12

13

9

Assign:• optimal path
• optimal cost

91059111112B

15

Dynamic Programming Example
6Illustrative Example:•••

Use principle of optimality
13
Compute Optimal Value Function and105optimal control at each state
A12Start from the final state B

9Continue…
10 + 15 = 259158912 + 16 = 28

81010B

16
1212 71481267 1512 6

775 1011 14

10 861015 96 1213

1059111112B

16

Dynamic Programming Example
Illustrative Example:•••

Use principle of optimality
Compute Optimal Value Function andoptimal control at each state
Start from the final state B

15Continue…
10 + 15 = 25925

12 + 16 = 28

B

1612

17

Dynamic Programming Example
Continue until
A is reached

Optimal cost:

18

LTI Optimal regulators• State space description of a discrete time LTI

For now, everything is deterministic• Find “optimal” control
In some sense, to be defined later…

• That drives the state to the origin

19

Finite Horizon LQ optimal regulator
Consider the nth order discrete time LTI system:

We want to find the optimal control sequence:

which minimizes the cost functional:

20

Finite Horizon LQ optimal regulator
Consider the nth order discrete time LTI system:

Notice that the value of the cost depends on the initialcondition

To emphasize the dependence on

21

LQ Cost Functional:•total number of steps—“horizon”•penalizes the final state
deviation from the origin•

penalizes the transient state deviationfrom the origin and the control effort

symmetric

22

LQ Cost Functional:
Simplified nomenclature:

final state
costtransient
cost at eachstep

23

Additional notationFor

define:Optimal control sequence from instance m

Arbitrary control sequence from instance m:24Dynamic Programming
Optimal cost functionalFunction of initial state

Control sequence from instance 0

25

Optimal Incremental Cost Function
Fordefine:

Optimal cost function from state x(m) at instantControl sequence from instance mm

26

Optimal Cost Function
Optimal cost function at the final state x(N)… only a function of the final state x(N)27

Dynamic Programming
For
Optimal value function::

28

Dynamic Programming
Optimal value function:

29

Dynamic Programming
Optimal value function:

given x(m), these are only functions of u(m) !!
only an optimization with respect to a single vector

30

Bellman Equation

1. The Bellman equation can be solved recursively(backwards), starting from N:

2. Each iteration involves only an optimization withrespect to a single variable (u(m)) – multistage
optimization

31

Recursive Solution to the Bellman Equation

boundary condition

known function of x(N)not known

32

Recursive Solution to the Bellman Equation
Start with N-1:

assume that x(N-1) is given

findby solving:known function ofwill be a function of

33

Recursive Solution to the Bellman Equation
Continue with N-2:

assume that x(N-2) is given

findby solving:known function ofwill be a function of

34

Solving the Bellman Equation for a LQR1)

2)

Quadratic functions

35

Minimization of quadratic functions
For

we have that:•• Optimal u given by
Proof:

Completing the square

36

Minimization of quadratic functions
For

we have that:•• Optimal u given by
Proof:

37

Finite-horizon LQR solution

Where P(k) is computed backwards in time using thediscrete Riccati difference equation :38

Proof of finite-horizon LQR solution
Proof (by induction on decreasing k)

Let(Trivially holds for k=N -1 by definition of)

39

Proof of finite-horizon LQR solution

40

Proof of finite-horizon LQR solution
The Bellman equation gives

41

Proof of finite-horizon LQR solution

Using results for quadratic optimizations:

where

42

Example – Double Integrator
Double integrator with ZOH and sampling time T =1:
u(k)

ZOH

u(t)

1
sv(t)

1
Tx(t)

sposition
velocity

Tx(k)
v(k)

43

Example – Double Integrator

LQR cost:

Choose:only penalize
position x1
and control u

44

Example – Double Integrator (DI)Compute P(k) for an arbitrary

Computing backwards:and N.

45

Example – DI Finite Horizon Case 1• N = 10 , R = 10,98P22(k)P(1,1), P(1,2),P(2,2)

7654P12(k)3P11(k)2
100246k810

46

Example – DI Finite Horizon Case 2• N = 30 , R = 10,9P(1,1), P(1,2),P(2,2)

8P22(k)7654P12(k)3P11(k)2
10051015k

20

25

30

47

Example – DI Finite Horizon Case 3• N = 30 , R = 10,
9P(1,1), P(1,2),P(2,2)

8P22(k)7654P12(k)3P11(k)2
10051015k20

2530

48

Example – DI Finite Horizon
Observation:
In all cases, regardless of the choice ofwhen the horizon, N, is sufficiently large
the backwards computation of the Riccati Eq.
always converges to the same solution:

We will return to this important idea in a few lectures

49

Properties of Matrix P(k)P(k) satisfies:
1)
2)(symmetric)(positive semi-definite)

50

Properties of Matrix P(k)(symmetric)
Proof: (by induction on decreasing k)Base case, k=N :For:Transpose both sides of the equation

51Properties of Matrix P(k)(positive semi-definite)
Proof: (by induction on decreasing k)Base case, k=N :For:Algebra…

52

Summary• Bellman’s dynamic programming invention
was a major breakthrough in the theory ofmultistage decision processes andoptimization• Key ideas– Principle of optimality– Computation of optimal cost function• Illustrated with a simple multi-stage example

53

Summary• Bellman’s equation:– has to be solved backwards in time
– may be difficult to solve– the solution yields a feedback law

54

Summary
Linear Quadratic Regulator (LQR)• Bellman’s equation is easily solved• Optimal cost is a quadratic function• matrix P is solved using a Riccati equation• Optimal control is a linear time varying
feedback law