Diferenciální dynamické programování

Diferenciální dynamické programování (DDP) je optimální ovládání algoritmus optimalizace trajektorie třída. Algoritmus zavedl v roce 1966 Mayne^[1] a následně analyzovány ve stejnojmenné knize Jacobsona a Mayna.^[2] Algoritmus používá lokálně kvadratické modely dynamických a nákladových funkcí a displeje kvadratická konvergence. Úzce souvisí s Pantojovou postupnou Newtonovou metodou.^[3]^[4]

Konečný horizont v diskrétním čase

Dynamika

{ displaystyle mathbf {x} _ {i + 1} = mathbf {f} ( mathbf {x} _ {i}, mathbf {u} _ {i})}

(1)

popsat vývoj státu ${ displaystyle textstyle mathbf {x}}$ vzhledem k ovládání ${ displaystyle mathbf {u}}$ od času ${ displaystyle i}$ na čas ${ displaystyle i + 1}$ . The Celkové náklady ${ displaystyle J_ {0}}$ je součet provozních nákladů ${ displaystyle textstyle ell}$ a konečné náklady ${ displaystyle ell _ {f}}$ , vzniklé při startu ze státu ${ displaystyle mathbf {x}}$ a použití kontrolní sekvence ${ displaystyle mathbf {U} equiv { mathbf {u} _ {0}, mathbf {u} _ {1} dots, mathbf {u} _ {N-1} }}$ dokud není dosaženo horizontu:

{ displaystyle J_ {0} ( mathbf {x}, mathbf {U}) = součet _ {i = 0} ^ {N-1} ell ( mathbf {x} _ {i}, mathbf {u} _ {i}) + ell _ {f} ( mathbf {x} _ {N}),}

kde ${ displaystyle mathbf {x} _ {0} equiv mathbf {x}}$ a ${ displaystyle mathbf {x} _ {i}}$ pro ${ displaystyle i> 0}$ jsou dány Rov. 1. Řešením optimálního regulačního problému je minimalizace řídicí sekvence ${ displaystyle mathbf {U} ^ {*} ( mathbf {x}) equiv operatorname {argmin} _ { mathbf {U}} J_ {0} ( mathbf {x}, mathbf {U} ).}$ Optimalizace dráhy znamená najít ${ displaystyle mathbf {U} ^ {*} ( mathbf {x})}$ pro konkrétní ${ displaystyle mathbf {x} _ {0}}$ , spíše než pro všechny možné počáteční stavy.

Dynamické programování

Nechat ${ displaystyle mathbf {U} _ {i}}$ být dílčí kontrolní sekvence ${ displaystyle mathbf {U} _ {i} ekviv { mathbf {u} _ {i}, mathbf {u} _ {i + 1} tečky, mathbf {u} _ {N-1 } }}$ a definovat náklady do konce ${ displaystyle J_ {i}}$ jako dílčí součet nákladů z ${ displaystyle i}$ na ${ displaystyle N}$ :

{ displaystyle J_ {i} ( mathbf {x}, mathbf {U} _ {i}) = součet _ {j = i} ^ {N-1} ell ( mathbf {x} _ {j }, mathbf {u} _ {j}) + ell _ {f} ( mathbf {x} _ {N}).}

Optimální náklady na cestu nebo funkce hodnoty v čase ${ displaystyle i}$ je zbývající cena vzhledem k minimalizaci řídicí sekvence:

{ displaystyle V ( mathbf {x}, i) ekviv min _ { mathbf {U} _ {i}} J_ {i} ( mathbf {x}, mathbf {U} _ {i}) .}

Nastavení ${ displaystyle V ( mathbf {x}, N) equiv ell _ {f} ( mathbf {x} _ {N})}$ , princip dynamického programování snižuje minimalizaci přes celou sekvenci ovládacích prvků na posloupnost minimalizací přes jednu ovládací prvek a postupuje zpět v čase:

{ displaystyle V ( mathbf {x}, i) = min _ { mathbf {u}} [ ell ( mathbf {x}, mathbf {u}) + V ( mathbf {f} ( mathbf {x}, mathbf {u}), i + 1)].}

(2)

To je Bellmanova rovnice.

DDP pokračuje iterativním provedením zpětného průchodu nominální trajektorie, aby se vygenerovala nová řídicí sekvence, a následným průchodem pro výpočet a vyhodnocení nové nominální trajektorie. Začínáme zpětným pasem. Li

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

je argumentem ${ displaystyle min []}$ operátor v Rov. 2, nechť ${ displaystyle Q}$ být variací tohoto množství kolem ${ displaystyle i}$ -th ${ displaystyle ( mathbf {x}, mathbf {u})}$ pár:

{ displaystyle { begin {zarovnáno} 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 {zarovnáno}}}

a rozbalte se do druhého řádu

{ displaystyle cca { frac {1} {2}} { začátek {bmatrix} 1 delta mathbf {x} delta mathbf {u} end {bmatrix}} ^ { mathsf {T}} { begin {bmatrix} 0 & Q _ { mathbf {x}} ^ { mathsf {T}} a Q _ { mathbf {u}} ^ { mathsf {T}} Q _ { mathbf {x }} & Q _ { mathbf {x} mathbf {x}} & Q _ { mathbf {x} mathbf {u}} Q _ { mathbf {u}} & Q _ { mathbf {u} mathbf {x} } & Q _ { mathbf {u} mathbf {u}} end {bmatrix}} { begin {bmatrix} 1 delta mathbf {x} delta mathbf {u} end {bmatrix} }}

(3)

The ${ displaystyle Q}$ zde použitý zápis je variantou zápisu Morimoto, kde dolní indexy označují diferenciaci v rozložení jmenovatele.^[5]Zrušení indexu ${ displaystyle i}$ z důvodu čitelnosti prvočísla označující další časový krok ${ displaystyle V ' equiv V (i + 1)}$ , koeficienty roztažnosti jsou

{ 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}}}

Poslední členy v posledních třech rovnicích označují kontrakci vektoru s tenzorem. Minimalizace kvadratické aproximace (3) s ohledem na ${ displaystyle delta mathbf {u}}$ my máme

{ displaystyle { delta mathbf {u}} ^ {*} = operatorname {argmin} limity _ { delta mathbf {u}} Q ( delta mathbf {x}, delta mathbf {u }) = - Q _ { mathbf {u} mathbf {u}} ^ {- 1} (Q _ { mathbf {u}} + Q _ { mathbf {u} mathbf {x}} delta mathbf { X} ),}

(4)

dát termín otevřené smyčky ${ displaystyle mathbf {k} = -Q _ { mathbf {u} mathbf {u}} ^ {- 1} Q _ { mathbf {u}}}$ a termín získání zpětné vazby ${ displaystyle mathbf {K} = -Q _ { mathbf {u} mathbf {u}} ^ {- 1} Q _ { mathbf {u} mathbf {x}}}$ . Připojte výsledek zpět do (3), nyní máme kvadratický model hodnoty v čase ${ 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}}}

Rekurzivní výpočet lokálních kvadratických modelů ${ displaystyle V (i)}$ a úpravy ovládání ${ displaystyle { mathbf {k} (i), mathbf {K} (i) }}$ , z ${ displaystyle i = N-1}$ dolů ${ displaystyle i = 1}$ , představuje zpětnou přihrávku. Jak je uvedeno výše, hodnota je inicializována pomocí ${ displaystyle V ( mathbf {x}, N) equiv ell _ {f} ( mathbf {x} _ {N})}$ . Jakmile je zpětný průchod dokončen, dopředný průchod vypočítá novou trajektorii:

{ 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 {zarovnáno}}}

Zpětné průchody a přední průchody jsou iterovány až do konvergence.

Regularizace a vyhledávání linek

Diferenciální dynamické programování je algoritmus druhého řádu Newtonova metoda. Proto podniká velké kroky k minimu a často vyžaduje regulace a / nebo line-search dosáhnout konvergence^[6].^[7] Regularizace v kontextu DDP znamená zajistit, aby: ${ displaystyle Q _ { mathbf {u} mathbf {u}}}$ matice v Rov. 4 je pozitivní určitý. Řádkové vyhledávání v DDP se rovná změně měřítka úpravy řízení s otevřenou smyčkou ${ displaystyle mathbf {k}}$ některými ${ displaystyle 0 < alpha <1}$ .

Verze Monte Carlo

Vzorek diferenciálního dynamického programování (SaDDP) je variantou diferenciálního dynamického programování v Monte Carlu.^[8]^[9]^[10] Je založen na léčbě kvadratických nákladů na diferenciální dynamické programování jako na energii a Boltzmannova distribuce. Tímto způsobem lze množství DDP porovnat se statistikami a vícerozměrné normální rozdělení. Statistiky lze přepočítat ze vzorkovaných trajektorií bez rozlišení.

Ukázkové diferenciální dynamické programování bylo rozšířeno na Path Integral Policy Improvement with Differential Dynamic Programming.^[11] Tím se vytvoří spojení mezi diferenciálním dynamickým programováním a integrálním řízením cesty,^[12] což je rámec stochastické optimální kontroly.

Omezené problémy

Interní bodové diferenciální dynamické programování (IPDDP) je metoda vnitřního bodu zobecnění DDP, které může řešit problém optimálního řízení s nelineárním stavem a omezeními vstupu. ^[13]

Viz také

Optimální ovládání

Reference

^ Mayne, D. Q. (1966). "Metoda gradientu druhého řádu optimalizující nelineární diskrétní časové systémy". Int J Control. 3: 85–95. doi:10.1080/00207176608921369.
^ Mayne, David H. a Jacobson, David Q. (1970). Diferenciální dynamické programování. New York: American Elsevier Pub. Co. ISBN 978-0-444-00070-5.
^ de O. Pantoja, J. F. A. (1988). "Diferenciální dynamické programování a Newtonova metoda". International Journal of Control. 47 (5): 1539–1553. doi:10.1080/00207178808906114. ISSN 0020-7179.
^ Liao, L. Z .; C. Švec (1992). "Výhody diferenciálního dynamického programování oproti Newtonově metodě pro problémy diskrétního optimálního řízení". Cornell University, Ithaca, NY. hdl:1813/5474. Citovat deník vyžaduje | deník = (Pomoc)
^ Morimoto, J .; G. Zeglin; C.G. Atkeson (2003). "Minimax diferenciální dynamické programování: Aplikace na dvojnohého kráčícího robota". Inteligentní roboti a systémy, 2003. (IROS 2003). Řízení. 2003 Mezinárodní konference IEEE / RSJ o. 2. 1927–1932.
^ Liao, L. Z; C. Švec (1991). "Konvergence v neomezeném diferenciálním dynamickém programování v diskrétním čase". Transakce IEEE na automatickém ovládání. 36 (6): 692. doi:10.1109/9.86943.
^ Tassa, Y. (2011). Teorie a implementace bio-mimetických motorových regulátorů (PDF) (Teze). Hebrejská univerzita. Archivovány od originál (PDF) dne 04.03.2016. Citováno 2012-02-27.
^ "Ukázkové diferenciální dynamické programování - publikace IEEE Conference". doi:10.1109 / IROS.2016.7759229. S2CID 1338737. Citovat deník vyžaduje | deník = (Pomoc)
^ „Regularizace vzorkovaného diferenciálního dynamického programování - publikace IEEE Conference“. ieeexplore.ieee.org. Citováno 2018-10-19.
^ Joose, Rajamäki (2018). Algoritmy náhodného vyhledávání pro optimální ovládání. Aalto University. ISBN 9789526081564. ISSN 1799-4942.
^ Lefebvre, Tom; Crevecoeur, Guillaume (červenec 2019). „Cesta ke zlepšení integrální politiky s diferenciálním dynamickým programováním“. 2019 Mezinárodní konference IEEE / ASME o pokročilé inteligentní mechatronice (AIM): 739–745. doi:10.1109 / AIM.2019.8868359. hdl:1854 / LU-8623968. ISBN 978-1-7281-2493-3. S2CID 204816072.
^ Theodorou, Evangelos; Buchli, Jonas; Schaal, Stefan (květen 2010). „Posílení motorických dovedností ve vysokých dimenzích: integrální přístup k cestě“. 2010 Mezinárodní konference IEEE o robotice a automatizaci: 2397–2403. doi:10.1109 / ROBOT.2010.5509336. ISBN 978-1-4244-5038-1. S2CID 15116370.
^ Pavlov, Andrei; Shames, Iman; Manzie, Chris (2020). "Diferenční dynamické programování vnitřních bodů". arXiv:2004.12710 [matematika.OC ].

externí odkazy

[1] Mayne, D. Q. (1966). "Metoda gradientu druhého řádu optimalizující nelineární diskrétní časové systémy". Int J Control. 3: 85–95. doi:10.1080/00207176608921369.

[2] Mayne, David H. a Jacobson, David Q. (1970). Diferenciální dynamické programování. New York: American Elsevier Pub. Co. ISBN 978-0-444-00070-5.

[3] O. Pantoja, J. F. A. (1988). "Diferenciální dynamické programování a Newtonova metoda". International Journal of Control. 47 (5): 1539–1553. doi:10.1080/00207178808906114. ISSN 0020-7179.

[4] Liao, L. Z .; C. Švec (1992). "Výhody diferenciálního dynamického programování oproti Newtonově metodě pro problémy diskrétního optimálního řízení". Cornell University, Ithaca, NY. hdl:1813/5474. Citovat deník vyžaduje | deník = (Pomoc)

[5] Morimoto, J .; G. Zeglin; C.G. Atkeson (2003). "Minimax diferenciální dynamické programování: Aplikace na dvojnohého kráčícího robota". Inteligentní roboti a systémy, 2003. (IROS 2003). Řízení. 2003 Mezinárodní konference IEEE / RSJ o. 2. 1927–1932.

[6] Liao, L. Z; C. Švec (1991). "Konvergence v neomezeném diferenciálním dynamickém programování v diskrétním čase". Transakce IEEE na automatickém ovládání. 36 (6): 692. doi:10.1109/9.86943.

[7] Tassa, Y. (2011). Teorie a implementace bio-mimetických motorových regulátorů (PDF) (Teze). Hebrejská univerzita. Archivovány od originál (PDF) dne 04.03.2016. Citováno 2012-02-27.

[8] "Ukázkové diferenciální dynamické programování - publikace IEEE Conference". doi:10.1109 / IROS.2016.7759229. S2CID 1338737. Citovat deník vyžaduje | deník = (Pomoc)

[9] „Regularizace vzorkovaného diferenciálního dynamického programování - publikace IEEE Conference“. ieeexplore.ieee.org. Citováno 2018-10-19.

[10] Joose, Rajamäki (2018). Algoritmy náhodného vyhledávání pro optimální ovládání. Aalto University. ISBN 9789526081564. ISSN 1799-4942.

[11] Lefebvre, Tom; Crevecoeur, Guillaume (červenec 2019). „Cesta ke zlepšení integrální politiky s diferenciálním dynamickým programováním“. 2019 Mezinárodní konference IEEE / ASME o pokročilé inteligentní mechatronice (AIM): 739–745. doi:10.1109 / AIM.2019.8868359. hdl:1854 / LU-8623968. ISBN 978-1-7281-2493-3. S2CID 204816072.

[12] Theodorou, Evangelos; Buchli, Jonas; Schaal, Stefan (květen 2010). „Posílení motorických dovedností ve vysokých dimenzích: integrální přístup k cestě“. 2010 Mezinárodní konference IEEE o robotice a automatizaci: 2397–2403. doi:10.1109 / ROBOT.2010.5509336. ISBN 978-1-4244-5038-1. S2CID 15116370.

[13] Pavlov, Andrei; Shames, Iman; Manzie, Chris (2020). "Diferenční dynamické programování vnitřních bodů". arXiv:2004.12710 [matematika.OC ].

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]