Programación Dinámica De La Mit
Páginas: 19 (4703 palabras)
Publicado: 22 de octubre de 2011
MIT OpenCourseWare http://ocw.mit.edu
16.323 Principles of Optimal Control
Spring 2008
For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.
16.323 Lecture 3 Dynamic Programming • Principle of Optimality • Dynamic Programming • Discrete LQR
Figure by MIT OpenCourseWare.
Spr 2008
Dynamic Programming
16.323 3–1
• DP is acentral idea of control theory that is based on the Principle of Optimality: Suppose the optimal solution for a problem passes through some intermediate point (x1, t1), then the optimal solution to the same problem starting at (x1, t1) must be the continuation of the same path.
• Proof? What would the implications be if it was false? • This principle leads to: – Numerical solution procedure calledDynamic Programming for solving multi-stage decision making problems. – Theoretical results on the structure of the resulting control law. • Texts: – Dynamic Programming (Paperback) by Richard Bellman (Dover) – Dynamic Programming and Optimal Control (Vol 1 and 2) by D. P. Bertsekas
June 18, 2008
Spr 2008
16.323 3–2
Classical Examples
• Shortest Path Problems (Bryson figure 4.2.1) –classic robot naviga tion and/or aircraft flight path problems
Figure by MIT OpenCourseWare.
• Goal is to travel from A to B in the shortest time possible – Travel times for each leg are shown in the figure – There are 20 options to get from A to B – could evaluate each and compute travel time, but that would be pretty tedious • Alternative approach: Start at B and work backwards, invoking theprinciple of optimality along the way. – First step backward can be either up (10) or down (11)
10 6 x 7 11 B
Figure by MIT OpenCourseWare.
• Consider the travel time from point x – Can go up and then down 6 + 10 = 16
June 18, 2008
Spr 2008
16.323 3–3
– Or can go down and then up 7 + 11 = 18 – Clearly best option from x is go up, then down, with a time of 16 – From principleof optimality, this is best way to get to B for any path that passes through x. • Repeat process for all other points, until finally get to initial point ⇒ shortest path traced by moving in the directions of the arrows.
Figure by MIT OpenCourseWare.
• Key advantage is that only had to find 15 numbers to solve this problem this way rather than evaluate the travel time for 20 paths – Modestdifference here, but scales up for larger problems. – If n = number of segments on side (3 here) then: � Number of routes scales as ∼ (2n)!/(n!)2 � Number DP computations scales as ∼ (n + 1)2 − 1
June 18, 2008
Spr 2008
Example 2
16.323 3–4
• Routing Problem [Kirk, page 56] through a street maze
Figure by MIT OpenCourseWare.
– Similar problem (minimize cost to travel from c to h) witha slightly more complex layout • Once again, start at end (h) and work backwards – Can get to h from e, g directly, but there are 2 paths to h from e.
� – Basics: Jgh = 2, and � � Jf h = Jf g + Jgh = 5
– Optimal cost from e to h given by
� � Jeh = min{Jef gh, Jeh} = min{[Jef + Jf h], Jeh} = min{2 + 5, 8} = 7 e → f → g → h � � � • Also Jdh = Jde + Jeh = 10
– Principle of optimality tellsthat, since we already know the best way to h from e, do not need to reconsider the various options from e again when starting at d – just use the best. • Optimal cost from c to h given by
� � � Jch = min{Jcdh, Jcf h} = min{[Jcd + Jdh], [Jcf + Jf h]} = min{[5 + 10], [3 + 5]} = 8 c → f → g → h
June 18, 2008
Spr 2008
16.323 3–5
• Examples show the basis of dynamic programming and useof principle of optimality. – In general, if there are numerous options at location α that next lead to locations x1, . . . , xn, choose the action that leads to � � � � � � Jαh = min [Jαx1 + Jx1h], [Jαx2 + Jx2h], . . . , [Jαxn + Jxnh]
xi
• Can apply the same process to more general control problems. Typi cally have to assume something about the system state (and possible control...
16.323 Principles of Optimal Control
Spring 2008
For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.
16.323 Lecture 3 Dynamic Programming • Principle of Optimality • Dynamic Programming • Discrete LQR
Figure by MIT OpenCourseWare.
Spr 2008
Dynamic Programming
16.323 3–1
• DP is acentral idea of control theory that is based on the Principle of Optimality: Suppose the optimal solution for a problem passes through some intermediate point (x1, t1), then the optimal solution to the same problem starting at (x1, t1) must be the continuation of the same path.
• Proof? What would the implications be if it was false? • This principle leads to: – Numerical solution procedure calledDynamic Programming for solving multi-stage decision making problems. – Theoretical results on the structure of the resulting control law. • Texts: – Dynamic Programming (Paperback) by Richard Bellman (Dover) – Dynamic Programming and Optimal Control (Vol 1 and 2) by D. P. Bertsekas
June 18, 2008
Spr 2008
16.323 3–2
Classical Examples
• Shortest Path Problems (Bryson figure 4.2.1) –classic robot naviga tion and/or aircraft flight path problems
Figure by MIT OpenCourseWare.
• Goal is to travel from A to B in the shortest time possible – Travel times for each leg are shown in the figure – There are 20 options to get from A to B – could evaluate each and compute travel time, but that would be pretty tedious • Alternative approach: Start at B and work backwards, invoking theprinciple of optimality along the way. – First step backward can be either up (10) or down (11)
10 6 x 7 11 B
Figure by MIT OpenCourseWare.
• Consider the travel time from point x – Can go up and then down 6 + 10 = 16
June 18, 2008
Spr 2008
16.323 3–3
– Or can go down and then up 7 + 11 = 18 – Clearly best option from x is go up, then down, with a time of 16 – From principleof optimality, this is best way to get to B for any path that passes through x. • Repeat process for all other points, until finally get to initial point ⇒ shortest path traced by moving in the directions of the arrows.
Figure by MIT OpenCourseWare.
• Key advantage is that only had to find 15 numbers to solve this problem this way rather than evaluate the travel time for 20 paths – Modestdifference here, but scales up for larger problems. – If n = number of segments on side (3 here) then: � Number of routes scales as ∼ (2n)!/(n!)2 � Number DP computations scales as ∼ (n + 1)2 − 1
June 18, 2008
Spr 2008
Example 2
16.323 3–4
• Routing Problem [Kirk, page 56] through a street maze
Figure by MIT OpenCourseWare.
– Similar problem (minimize cost to travel from c to h) witha slightly more complex layout • Once again, start at end (h) and work backwards – Can get to h from e, g directly, but there are 2 paths to h from e.
� – Basics: Jgh = 2, and � � Jf h = Jf g + Jgh = 5
– Optimal cost from e to h given by
� � Jeh = min{Jef gh, Jeh} = min{[Jef + Jf h], Jeh} = min{2 + 5, 8} = 7 e → f → g → h � � � • Also Jdh = Jde + Jeh = 10
– Principle of optimality tellsthat, since we already know the best way to h from e, do not need to reconsider the various options from e again when starting at d – just use the best. • Optimal cost from c to h given by
� � � Jch = min{Jcdh, Jcf h} = min{[Jcd + Jdh], [Jcf + Jf h]} = min{[5 + 10], [3 + 5]} = 8 c → f → g → h
June 18, 2008
Spr 2008
16.323 3–5
• Examples show the basis of dynamic programming and useof principle of optimality. – In general, if there are numerous options at location α that next lead to locations x1, . . . , xn, choose the action that leads to � � � � � � Jαh = min [Jαx1 + Jx1h], [Jαx2 + Jx2h], . . . , [Jαxn + Jxnh]
xi
• Can apply the same process to more general control problems. Typi cally have to assume something about the system state (and possible control...
Leer documento completo
Regístrate para leer el documento completo.