OptimalControlTheory.pdf_optimalcontrol

最优控制理论

需积分: 49 67 浏览量更新于2023-03-16 评论 4 收藏 223KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

To appear in Bayesian Brain, Doya, K. (ed), MIT Press (2006)

Optimal Control Theory

Emanuel Todorov

University of California San Diego

Optimal control theory is a mature mathematical discipline with numerous applications

in both s cien ce and engineering. It is emerging as the computational framework of choice

for studying the neural control of movement, in much the same way that probabilistic infer-

ence is emerging as the computational framework of choice for studying sensory information

processing. Despite the growing popularity of optimal control models, however, the elab-

orate mathematical machinery behind them is rarely exposed and the big picture is hard

to grasp without reading a few technical books on the subject. While this chapter cannot

replace such books, it aims to provide a self-contained mathematical introduction to opti-

mal control theory that is su¢ ciently broad and yet su¢ ciently detailed when it comes to

key concepts. The text is not tailored to the …eld of motor control (apart from the last

section, and the overall emphasis on systems with continuous state) so it will hopefully

be of interest to a wider audience. Of special interest in the context of this book is the

material on the duality of optimal control and probabilistic inference; such duality suggests

that neural information processing in sensory and motor areas may be more similar than

currently thought. The chapter is organized in the following sections:

1. Dynamic programming, Bellman equations, optimal value functions, value and policy

iteration, shortest paths, Markov decision processes.

2. Hamilton-Jacobi-Bellman equations, approximation methods, …nite and in…nite hori-

zon formulations, basics of stochastic calculus.

3. Pontryagin’s maximum principle, ODE and gradient descent methods, relationship to

classical mechanics.

4. Linear-quadratic-Gaussian control, Riccati equations, iterative linear approximations

to nonlinear problems.

5. Optimal recursive estimation, Kalman …lter, Zakai equation.

6. Duality of optimal control and optimal estimation (including new results).

7. Optimality models in motor control, promising research directions.

1 Discrete control: Bellman equations

Let x 2 X denote the state of an agent’s environment, and u 2 U (x) the action (or

control) which the agent choose s while at state x. For now both X and U (x) are …nite

sets. Let next (x; u) 2 X denote the state which results f rom applying action u in state

x, and cost (x; u)  0 the cost of applying action u in state x. As an example, x may be

the city where we are now, u the ‡ight we choose to take, next (x; u) the city where that

‡ight lands, and cost (x; u) the price of the ticket. We can now pose a simple yet practical

optimal control problem: …nd the cheapest way to ‡y to your destination. Th is problem

can be formalized as follows: …nd an action sequence (u

; u

; u

n1

) and corresponding

state sequence (x

; x

; x

) minimizing the total cost

J (x



; u



) =

n1

k=0

cost (x

; u

)

where x

k+1

= next (x

; u

) and u

2 U (x

). The initial state x

= x

init

and destination

state x

= x

dest

are given. We can visualize this setting with a directed graph where the

states are nodes and the actions are arrows connecting the nodes. If cost (x; u) = 1 for all

(x; u) the problem reduces to …nding the shortest path from x

init

to x

dest

in the graph.

1.1 Dynamic programming

Optimization problems such as the one stated above are e¢ ciently solved via dynamic

programming (DP). DP relies on the following obvious fact: if a given state-action sequen ce

is optimal, and we were to remove the …rst state and action, the remaining sequence is also

optimal (with the second state of the original sequence now acting as initial state). This

is the Bellman optimality principle. Note the close resemblance to the Markov property of

stochastic processes (a process is Markov if its future is conditionally independent of the

past given the present state). The optimality principle can be reworded in similar language:

the choice of optimal actions in the f uture is independent of the past actions which led to

the present state. Thus optimal state-action sequences can be constructed by starting at

the …nal state and extending backwards. Key to this procedure is the optimal value function

(or optimal cost-to-go function)

v (x) = "minimal total cost for completing the task starting from state x"

This fun ction captures the long-term cost for starting from a given state, and makes it

possible to …nd optimal actions through the following algorithm:

Consider every action available at the current state,

add its immediate cost to the optimal value of the resulting next state,

and choose an action for which the sum is minimal.

The above algorithm is "greedy" in the sense that actions are chosen based on local infor-

mation, without explicit consideration of all future scenarios. And yet the resulting actions

are optimal. This is possible because the optimal value function contains all information

about future scenarios that is relevant to the present choice of action. Thus the optimal

value function is an extremely useful quantity, and indeed its calculation is at the heart of

many methods for optimal control.

The above algorithm yields an optimal action u =  (x) 2 U (x) for every s tate x. A

mapping from states to actions is called control law or control policy. Once we have a control

law  : X ! U (X) we can start at any state x

, generate action u

=  (x

), transition to

state x

= next (x

; u

), generate action u

=  (x

), and keep going until we reach x

dest

Formally, an optimal control law  satis…es

 (x) = arg min

u2U (x)

fcost (x; u) + v (next (x; u))g (1)

The minimum in (1) may be achieved for multiple actions in the set U (x), which is why 

may not be unique. However the optimal value function v is always uniquely de…ned, and

satis…es

v (x) = min

u2U (x)

fcost (x; u) + v (next (x; u))g (2)

Equations (1) and (2) are the Bell man equations.

If for some x we already know v (next (x; u)) for all u 2 U (x), then we can apply the

Bellman equations directly and compute  (x) and v (x). Thus dynamic programming is

particularly simple in acyclic graphs where we can start from x

dest

with v



dest



= 0, and

perform a backward pass in w hich every state is visited after all its successor states have

been visited. It is straightforward to extend the algorithm to the case where we are given

non-zero …nal costs for a number of destination states (or absorbing states).

1.2 Value iteration and policy iteration

The s ituation is more complex in graphs with cycles. Here the Bellman equations are

still valid, but we cannot apply them in a single pass. This is because the presence of

cycles makes it impossible to visit each state only after all its successors have been visited.

Instead the Bellman equations are treated as consistency conditions and used to design

iterative relaxation schemes –much like partial di¤erential equations (PDEs) are treated as

consistency conditions and solved with corresponding relaxation schemes. By "relaxation

scheme" we mean guessing the solution, and iteratively improving the guess so as to make

it more compatible with the cons istenc y condition.

The two main relaxation schemes are value iteration and policy iteration. Value iteration

uses only (2). We start with a guess v

(0)

of the optimal value function, and construct a

sequence of improved guesses:

(i+1)

(x) = min

u2U (x)

cost (x; u) + v

(i)

(next (x; u))

(3)

This process is guaranteed to converge to the optimal value function v in a …nite number

of iterations. The proof relies on the important idea of contraction mappings: one de…nes

the approximation error e



(i)



= max



(i)

(x)  v (x)



, and shows that the iteration (3)

causes e



(i)



to decrease as i increases. In othe r words, the mapping v

(i)

! v

(i+1)

given

by (3) contracts the "size" of v

(i)

as measured by the error norm e



(i)



Policy iteration uses both (1) and (2). It starts with a guess 

(0)

of the optimal control

law, and constructs a sequence of improved guesses:



(i)

(x) = cost



x; 

(i)

(x)



+ v



(i)



x; 

(i)

(x)



(4)



(i+1)

(x) = arg min

u2U (x)

cost (x; u) + v



(i)

(next (x; u))

The …rst line of (4) requires a separate relaxation to compute the value function v



(i)

for

the control law 

(i)

. This function is de…ned as the total cost for starting at state x and

acting according to 

(i)

thereafter. Policy iteration can also be proven to converge in a

…nite number of iterations. It is not obvious which algorithm is better, because each of

the two nested relaxations in policy iteration converges faster than the single relaxation in

value iteration. In practice both algorithms are used depending on the problem at hand.

1.3 Markov decision processes

The problems considered thus far are deterministic, in the sense that applying action u

at state x always yields the same next state next (x; u). Dynamic programming easily

generalizes to the stochastic case where we have a probability distribution over possible

next states:

p (yjx; u) = "probability that next (x; u) = y"

In order to qualify as a probability distribution the function p must satisfy

y2X

p (yjx; u) = 1

p (yjx; u)  0

In the stochastic case the value function equation (2) becomes

v (x) = min

u2U (x)

fcost (x; u) + E [v (next (x; u))]g (5)

where E denotes expectation over next (x; u), and is computed as

E [v (next (x; u))] =

y2X

p (yjx; u) v (y)

Equations (1, 3, 4) generalize to the stochastic case in the same way as equation (2) does.

An optimal control problem with discrete states and actions and probabilistic state

transitions is called a Markov decision process (MDP). MDPs are extensively studied in

reinforcement learning –which is a sub-…eld of machine learning focusing on optimal control

problems with discrete state. In contrast, optimal control theory focuses on problems with

continuous state and exploits their rich di¤erential structure.

2 Continuous control: Hamilton-Jacobi-Bellman equations

We now turn to optimal control problems where the state x 2 R

and control u 2 U (x) 

are real-valued vectors. To simplify notation we will us e the shortcut min

instead of

min

u2U (x)

, although the latter is implied unless noted otherwise. Consider the stochastic

di¤erential equation

dx = f (x; u) dt + F (x; u) dw (6)

where dw is n

-dimensional Brownian motion. This is sometimes called a controlled Ito

di¤usion, with f (x; u) being the drift and F (x; u) the di¤usion coe¢ cient. In the absence

of noise, i.e. when F (x; u) = 0, we can simply write _x = f (x; u). However in the stochastic

case this would be meaningless because the sample paths of Brownian motion are not

di¤erentiable (the term dw=dt is in…nite). What equation (6) really means is that the

integral of the left hand s ide is equal to the integral of the right hand side:

x (t) = x (0) +

f (x (s) ; u (s)) ds +

F (x (s) ; u (s)) dw (s)

The last term is an Ito integral, de…ned for square-integrable functions g (t) as

g (s) dw (s) = lim

n!1

n1

k=0

g (s

) (w (s

k+1

)  w (s

))

where 0 = s

< s

<  < s

= t

We will stay away from the complexities of stochastic calculus to the extent possible. Instead

we will discretize the time axis and obtain results for the continuous-time case in the limit

of in…nitely small time step.

The appropriate Euler discretization of (6) is

k+1

= x

+ f (x

; u

) +

F (x

; u

) "

where  is the time step, "

 N (0; I

) and x

= x (k). The

 term appears because

the variance of Brownian motion grows linearly with time, and thus the standard deviation

of the discrete-time noise should scale as

.

To de…ne an optimal control problem we also need a cost function. In …nite-horizon

problems, i.e. when a …nal time t

is speci…ed, it is natural to separate the total cost

into a time-integral of a cost rate ` (x; u; t)  0, and a …nal cost h (x)  0 which is only

evaluated at the …nal state x (t

). Thus the total cost for a given state-c ontrol trajectory

fx (t) ; u (t) : 0  t  t

g is de…ned as

J (x () ; u ()) = h (x (t

)) +

` (x (t) ; u (t) ; t) dt

Keep in mind that we are dealing with a stochastic system. Our objective is to …nd a control

law u =  (x; t) which minimizes the expected total cost for starting at a given (x; t) and

acting according  thereafter.

In discrete time the total c ost becomes

J (x



; u



) = h (x

) + 

n1

k=0

` (x

; u

; k)

where n = t

= is the number of time steps (assume that t

= is integer).

剩余27页未读，继续阅读

杨跟的博客

粉丝: 74
资源: 5

会员权益专享

Optimal Control Theory.pdf

评论0

会员权益专享

最新资源

Optimal Control Theory.pdf

评论0

Optimal Control Theory for Applications

OPTIMAL CONTROL SYSTEMS

an introduction to be the theory of canonical matrices turnbull-matrices.djvu

robust and optimal control pdf

python hjb方程

dynamic programming and optimal control pdf

optimal control, 3rd edition

Traceback (most recent call last): File "frenet_optimal_trajectory.py", line 3, in <module> import matplotlib.pyplot as plt ImportError: No module named matplotlib.pyplot

hhaa017.pdf

convex programming method

kemin zhou, robust and optimal control, prentice hall, englewo o d cliffs, n

关于直线倒立摆的参考文献有哪些

reinforcement learning and optimal control

dynamic programming and optimal control

applied optimal control

WHY IS MOTOR control loop frequency 200KHZ

dynamic programming and optimal control1

dido optimal control

会员权益专享

最新资源