Programación dinámica diferencial

Algoritmo de optimización de trayectoria.

La programación dinámica diferencial ( DDP ) es un algoritmo de control óptimo de la clase de optimización de trayectoria . El algoritmo fue introducido en 1966 por Mayne ^[1] y posteriormente analizado en el libro homónimo de Jacobson y Mayne. ^[2] El algoritmo utiliza modelos localmente cuadráticos de las funciones dinámica y de costos, y muestra convergencia cuadrática . Está estrechamente relacionado con el método paso a paso de Newton de Pantoja. ^{[3] [4]}

Problemas de tiempo discreto de horizonte finito

la dinámica

describir la evolución del estado dado el control de vez en cuando . El costo total es la suma de los costos de funcionamiento y el costo final , incurrido al partir del estado y aplicar la secuencia de control hasta alcanzar el horizonte: ${\displaystyle \textstyle \mathbf {x} }$ ${\displaystyle \mathbf {u} }$ ${\displaystyle i}$ ${\displaystyle i+1}$ ${\displaystyle J_{0}}$ ${\displaystyle \textstyle \ell }$ ${\displaystyle \ell _{f}}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {U} \equiv \{\mathbf {u} _{0},\mathbf {u} _{1}\dots ,\mathbf {u} _{N-1}\}}$

${\displaystyle J_{0}(\mathbf {x} ,\mathbf {U} )=\sum _{i=0}^{N-1}\ell (\mathbf {x} _{i},\mathbf {u} _{i})+\ell _{f}(\mathbf {x} _{N}),}$

donde , y for están dados por la ecuación. 1 . La solución del problema de control óptimo es minimizar la secuencia de control. La optimización de la trayectoria significa encontrar un estado inicial particular , en lugar de todos los estados iniciales posibles. ${\displaystyle \mathbf {x} _{0}\equiv \mathbf {x} }$ ${\displaystyle \mathbf {x} _{i}}$ ${\displaystyle i>0}$ ${\displaystyle \mathbf {U} ^{*}(\mathbf {x} )\equiv \operatorname {argmin} _{\mathbf {U} }J_{0}(\mathbf {x} ,\mathbf {U} ).}$ ${\displaystyle \mathbf {U} ^{*}(\mathbf {x} )}$ ${\displaystyle \mathbf {x} _{0}}$

Programación dinámica

Sea la secuencia de control parcial y defina el costo pendiente como la suma parcial de los costos desde hasta : ${\displaystyle \mathbf {U} _{i}}$ ${\displaystyle \mathbf {U} _{i}\equiv \{\mathbf {u} _{i},\mathbf {u} _{i+1}\dots ,\mathbf {u} _{N-1}\}}$ ${\displaystyle J_{i}}$ ${\displaystyle i}$ ${\displaystyle N}$

${\displaystyle J_{i}(\mathbf {x} ,\mathbf {U} _{i})=\sum _{j=i}^{N-1}\ell (\mathbf {x} _{j},\mathbf {u} _{j})+\ell _{f}(\mathbf {x} _{N}).}$

El costo total o función de valor óptimo en el momento es el costo total dada la secuencia de control minimizante: ${\displaystyle i}$

${\displaystyle V(\mathbf {x} ,i)\equiv \min _{\mathbf {U} _{i}}J_{i}(\mathbf {x} ,\mathbf {U} _{i}).}$

Al establecer , el principio de programación dinámica reduce la minimización de una secuencia completa de controles a una secuencia de minimizaciones de un solo control, retrocediendo en el tiempo: ${\displaystyle V(\mathbf {x} ,N)\equiv \ell _{f}(\mathbf {x} _{N})}$

Esta es la ecuación de Bellman .

Programación dinámica diferencial

DDP procede realizando iterativamente un pase hacia atrás en la trayectoria nominal para generar una nueva secuencia de control, y luego un pase hacia adelante para calcular y evaluar una nueva trayectoria nominal. Comenzamos con el pase hacia atrás. Si

${\displaystyle \ell (\mathbf {x} ,\mathbf {u} )+V(\mathbf {f} (\mathbf {x} ,\mathbf {u} ),i+1)}$

es el argumento del operador en la ecuación. 2 , sea la variación de esta cantidad alrededor del -ésimo par: ${\displaystyle \min[\cdot ]}$ ${\displaystyle Q}$ ${\displaystyle i}$ ${\displaystyle (\mathbf {x} ,\mathbf {u} )}$

${\displaystyle {\begin{aligned}Q(\delta \mathbf {x} ,\delta \mathbf {u} )\equiv &\ell (\mathbf {x} +\delta \mathbf {x} ,\mathbf {u} +\delta \mathbf {u} )&&{}+V(\mathbf {f} (\mathbf {x} +\delta \mathbf {x} ,\mathbf {u} +\delta \mathbf {u} ),i+1)\\-&\ell (\mathbf {x} ,\mathbf {u} )&&{}-V(\mathbf {f} (\mathbf {x} ,\mathbf {u} ),i+1)\end{aligned}}}$

y expandirse a segundo orden

La notación utilizada aquí es una variante de la notación de Morimoto donde los subíndices denotan diferenciación en la disposición del denominador. ^[5] Eliminando el índice para facilitar la lectura, los números primos indican el siguiente paso de tiempo , los coeficientes de expansión son ${\displaystyle Q}$ ${\displaystyle i}$ ${\displaystyle V'\equiv V(i+1)}$

${\displaystyle {\begin{alignedat}{2}Q_{\mathbf {x} }&=\ell _{\mathbf {x} }+\mathbf {f} _{\mathbf {x} }^{\mathsf {T}}V'_{\mathbf {x} }\\Q_{\mathbf {u} }&=\ell _{\mathbf {u} }+\mathbf {f} _{\mathbf {u} }^{\mathsf {T}}V'_{\mathbf {x} }\\Q_{\mathbf {x} \mathbf {x} }&=\ell _{\mathbf {x} \mathbf {x} }+\mathbf {f} _{\mathbf {x} }^{\mathsf {T}}V'_{\mathbf {x} \mathbf {x} }\mathbf {f} _{\mathbf {x} }+V_{\mathbf {x} }'\cdot \mathbf {f} _{\mathbf {x} \mathbf {x} }\\Q_{\mathbf {u} \mathbf {u} }&=\ell _{\mathbf {u} \mathbf {u} }+\mathbf {f} _{\mathbf {u} }^{\mathsf {T}}V'_{\mathbf {x} \mathbf {x} }\mathbf {f} _{\mathbf {u} }+{V'_{\mathbf {x} }}\cdot \mathbf {f} _{\mathbf {u} \mathbf {u} }\\Q_{\mathbf {u} \mathbf {x} }&=\ell _{\mathbf {u} \mathbf {x} }+\mathbf {f} _{\mathbf {u} }^{\mathsf {T}}V'_{\mathbf {x} \mathbf {x} }\mathbf {f} _{\mathbf {x} }+{V'_{\mathbf {x} }}\cdot \mathbf {f} _{\mathbf {u} \mathbf {x} }.\end{alignedat}}}$

Los últimos términos de las últimas tres ecuaciones denotan la contracción de un vector con un tensor. Minimizando la aproximación cuadrática (3) con respecto a tenemos ${\displaystyle \delta \mathbf {u} }$

dando un término de bucle abierto y un término de ganancia de retroalimentación . Volviendo a conectar el resultado a (3) , ahora tenemos un modelo cuadrático del valor en el momento : ${\displaystyle \mathbf {k} =-Q_{\mathbf {u} \mathbf {u} }^{-1}Q_{\mathbf {u} }}$ ${\displaystyle \mathbf {K} =-Q_{\mathbf {u} \mathbf {u} }^{-1}Q_{\mathbf {u} \mathbf {x} }}$ ${\displaystyle i}$

${\displaystyle {\begin{alignedat}{2}\Delta V(i)&=&{}-{\tfrac {1}{2}}Q_{\mathbf {u} }^{T}Q_{\mathbf {u} \mathbf {u} }^{-1}Q_{\mathbf {u} }\\V_{\mathbf {x} }(i)&=Q_{\mathbf {x} }&{}-Q_{\mathbf {xu} }Q_{\mathbf {u} \mathbf {u} }^{-1}Q_{\mathbf {u} }\\V_{\mathbf {x} \mathbf {x} }(i)&=Q_{\mathbf {x} \mathbf {x} }&{}-Q_{\mathbf {x} \mathbf {u} }Q_{\mathbf {u} \mathbf {u} }^{-1}Q_{\mathbf {u} \mathbf {x} }.\end{alignedat}}}$

Calcular recursivamente los modelos cuadráticos locales de y las modificaciones de control , desde abajo hasta , constituye el paso hacia atrás. Como arriba, el Valor se inicializa con . Una vez que se completa el pase hacia atrás, un pase hacia adelante calcula una nueva trayectoria: ${\displaystyle V(i)}$ ${\displaystyle \{\mathbf {k} (i),\mathbf {K} (i)\}}$ ${\displaystyle i=N-1}$ ${\displaystyle i=1}$ ${\displaystyle V(\mathbf {x} ,N)\equiv \ell _{f}(\mathbf {x} _{N})}$

${\displaystyle {\begin{aligned}{\hat {\mathbf {x} }}(1)&=\mathbf {x} (1)\\{\hat {\mathbf {u} }}(i)&=\mathbf {u} (i)+\mathbf {k} (i)+\mathbf {K} (i)({\hat {\mathbf {x} }}(i)-\mathbf {x} (i))\\{\hat {\mathbf {x} }}(i+1)&=\mathbf {f} ({\hat {\mathbf {x} }}(i),{\hat {\mathbf {u} }}(i))\end{aligned}}}$

Los pases hacia atrás y hacia adelante se repiten hasta la convergencia.

Regularización y búsqueda de líneas.

La programación dinámica diferencial es un algoritmo de segundo orden como el método de Newton . Por lo tanto, se necesitan grandes pasos hacia el mínimo y, a menudo, se requiere regularización y/o búsqueda de líneas para lograr la convergencia. ^{[6] [7]} La ​​regularización en el contexto DDP significa garantizar que la matriz en la ecuación. 4 es positivo definido . La búsqueda de líneas en DDP equivale a escalar la modificación del control de bucle abierto en algunos puntos . ${\displaystyle Q_{\mathbf {u} \mathbf {u} }}$ ${\displaystyle \mathbf {k} }$ ${\displaystyle 0<\alpha <1}$

Versión Montecarlo

La programación dinámica diferencial muestreada (SaDDP) es una variante Monte Carlo de la programación dinámica diferencial. ^{[8] [9] [10]} Se basa en tratar el coste cuadrático de la programación dinámica diferencial como la energía de una distribución de Boltzmann . De esta manera, las cantidades de DDP se pueden hacer coincidir con las estadísticas de una distribución normal multidimensional . Las estadísticas se pueden volver a calcular a partir de trayectorias muestreadas sin diferenciación.

La programación dinámica diferencial de muestra se ha ampliado a la ruta de mejora integral de políticas con programación dinámica diferencial. ^[11] Esto crea un vínculo entre la programación dinámica diferencial y el control integral de ruta, ^[12] que es un marco de control óptimo estocástico.

Problemas restringidos

La programación dinámica diferencial de puntos interiores (IPDDP) es una generalización del método de puntos interiores de DDP que puede abordar el problema de control óptimo con estados no lineales y restricciones de entrada. ^[13]

Ver también

• Control óptimo

Referencias

1. Mayne, DQ (1966). "Un método de gradiente de segundo orden para optimizar sistemas de tiempo discretos no lineales". Control Int J. 3 : 85–95. doi : 10.1080/00207176608921369.
2. Mayne, David Q.; Jacobson, David H. (1970). Programación dinámica diferencial. Nueva York: Pub americano Elsevier. ISBN del condado 978-0-444-00070-5.
3. de O. Pantoja, JFA (1988). "Programación dinámica diferencial y método de Newton". Revista Internacional de Control . 47 (5): 1539-1553. doi :10.1080/00207178808906114. ISSN  0020-7179.
4. Liao, LZ; C. Un zapatero (1992). "Ventajas de la programación dinámica diferencial sobre el método de Newton para problemas de control óptimo en tiempo discreto". Universidad de Cornell . hdl : 1813/5474 .
5. Morimoto, J.; G. Zeglin; CG Atkeson (2003). "Programación dinámica diferencial Minimax: Aplicación a un robot caminante bípedo". Robots y sistemas inteligentes, 2003 (IROS 2003). Actas. 2003 Conferencia Internacional IEEE/RSJ sobre . vol. 2. págs. 1927-1932.
6. Liao, LZ; C. Un zapatero (1991). "Convergencia en programación dinámica diferencial de tiempo discreto sin restricciones". Transacciones IEEE sobre control automático . 36 (6): 692. doi : 10.1109/9.86943.
7. Tassa, Y. (2011). Teoría e implementación de controladores de motores biomiméticos (PDF) (Tesis). Universidad Hebrea. Archivado desde el original (PDF) el 4 de marzo de 2016 . Consultado el 27 de febrero de 2012 .
8. "Programación dinámica diferencial muestreada". Conferencia internacional IEEE/RSJ 2016 sobre robots y sistemas inteligentes (IROS) . doi :10.1109/IROS.2016.7759229. S2CID  1338737.
9. Rajamäki, Joose; Hämäläinen, Perttu (junio de 2018). Regularización de la programación dinámica diferencial muestreada: publicación de la conferencia IEEE. Conferencia Anual Americana de Control (ACC) 2018. págs. 2182-2189. doi :10.23919/ACC.2018.8430799. S2CID  243932441 . Consultado el 19 de octubre de 2018 .
10. Rajamäki, Joose (2018). Algoritmos de búsqueda aleatoria para un control óptimo. Universidad Aalto. ISBN 978-952-60-8156-4. ISSN  1799-4942.
11. Lefebvre, Tom; Crevecoeur, Guillaume (julio de 2019). "Ruta de mejora de políticas integrales con programación dinámica diferencial". Conferencia internacional IEEE/ASME 2019 sobre mecatrónica inteligente avanzada (AIM). págs. 739–745. doi : 10.1109/AIM.2019.8868359. hdl : 1854/LU-8623968 . ISBN 978-1-7281-2493-3. S2CID  204816072.
12. Theodorou, Evangelos; Buchli, Jonás; Schaal, Stefan (mayo de 2010). "Aprendizaje por refuerzo de habilidades motoras en altas dimensiones: un enfoque integral del camino". Conferencia Internacional IEEE 2010 sobre Robótica y Automatización . págs. 2397–2403. doi :10.1109/ROBOT.2010.5509336. ISBN 978-1-4244-5038-1. S2CID  15116370.
13. Pavlov, Andrés; Qué vergüenza, Imán; Manzie, Chris (2020). "Programación dinámica diferencial de puntos interiores". arXiv : 2004.12710 [matemáticas.OC].

enlaces externos

• Una implementación Python de DDP
• Una implementación MATLAB de DDP