Дифференциальное динамическое программирование

Дифференциальное динамическое программирование ( ДДП ) — алгоритм оптимального управления класса оптимизации траектории . Алгоритм был представлен в 1966 году Мэйном. ^[1] и впоследствии проанализированы в одноименной книге Джейкобсона и Мейна. ^[2] Алгоритм использует локально-квадратичные модели динамики и функции стоимости и отображает квадратичную сходимость . Он тесно связан с пошаговым методом Ньютона Пантойи. ^[3]^[4]

Задачи дискретного времени на конечном горизонте

Динамика

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

( 1 )

описать эволюцию государства $\textstyle \mathbf {x}$ учитывая контроль $\mathbf {u}$ со времени $i$ ко времени $i+1$ . Общая стоимость $J_{0}$ это сумма текущих расходов $\textstyle \ell$ и окончательная стоимость $\ell _{f}$ , возникший при старте из состояния $\mathbf {x}$ и применяя управляющую последовательность $\mathbf {U} \equiv \{\mathbf {u} _{0},\mathbf {u} _{1}\dots ,\mathbf {u} _{N-1}\}$ пока не будет достигнут горизонт:

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

где $\mathbf {x} _{0}\equiv \mathbf {x}$ и $\mathbf {x} _{i}$ для $i>0$ даны уравнением 1 . Решением задачи оптимального управления является минимизирующая управляющая последовательность $\mathbf {U} ^{*}(\mathbf {x} )\equiv \operatorname {argmin} _{\mathbf {U} }J_{0}(\mathbf {x} ,\mathbf {U} ).$ Оптимизация траектории означает нахождение $\mathbf {U} ^{*}(\mathbf {x} )$ для конкретного $\mathbf {x} _{0}$ , а не для всех возможных начальных состояний.

Динамическое программирование

Позволять $\mathbf {U} _{i}$ быть частичной управляющей последовательностью $\mathbf {U} _{i}\equiv \{\mathbf {u} _{i},\mathbf {u} _{i+1}\dots ,\mathbf {u} _{N-1}\}$ и определите себестоимость $J_{i}$ как частичная сумма затрат от $i$ к $N$ :

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

Оптимальная себестоимость или функция ценности во времени $i$ – это себестоимость с учетом минимизирующей последовательности управления:

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

Параметр $V(\mathbf {x} ,N)\equiv \ell _{f}(\mathbf {x} _{N})$ , принцип динамического программирования сводит минимизацию всей последовательности элементов управления к последовательности минимизаций одного элемента управления, идущей назад во времени:

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

( 2 )

Это уравнение Беллмана .

Дифференциальное динамическое программирование

DDP итеративно выполняет обратный проход по номинальной траектории для создания новой управляющей последовательности, а затем прямой проход для вычисления и оценки новой номинальной траектории. Начинаем с паса назад. Если

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

является аргументом $\min[\cdot ]$ оператор в уравнении 2 , пусть $Q$ будет изменение этой величины вокруг $i$ -й $(\mathbf {x} ,\mathbf {u} )$ пара:

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

и расшириться до второго порядка

\approx {\frac {1}{2}}{\begin{bmatrix}1\\\delta \mathbf {x} \\\delta \mathbf {u} \end{bmatrix}}^{\mathsf {T}}{\begin{bmatrix}0&Q_{\mathbf {x} }^{\mathsf {T}}&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 $Q$ Используемые здесь обозначения представляют собой вариант обозначений Моримото, где индексы обозначают дифференцирование в расположении знаменателя. ^[5]Удаление индекса $i$ для удобства чтения штрихи обозначают следующий временной шаг $V'\equiv V(i+1)$ , коэффициенты расширения равны

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

Последние члены в последних трёх уравнениях обозначают сжатие вектора тензором. Минимизация квадратичного приближения (3) по $\delta \mathbf {u}$ у нас есть

{\delta \mathbf {u} }^{*}=\operatorname {argmin} \limits _{\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 )

давая термин разомкнутого цикла $\mathbf {k} =-Q_{\mathbf {u} \mathbf {u} }^{-1}Q_{\mathbf {u} }$ и коэффициент усиления обратной связи $\mathbf {K} =-Q_{\mathbf {u} \mathbf {u} }^{-1}Q_{\mathbf {u} \mathbf {x} }$ . Подставив результат обратно в (3) , мы теперь имеем квадратичную модель значения во времени. $i$ :

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

Рекурсивное вычисление локальных квадратичных моделей $V(i)$ и модификации управления $\{\mathbf {k} (i),\mathbf {K} (i)\}$ , от $i=N-1$ вплоть до $i=1$ , представляет собой обратный проход. Как указано выше, значение инициализируется с помощью $V(\mathbf {x} ,N)\equiv \ell _{f}(\mathbf {x} _{N})$ . После завершения обратного прохода прямой проход вычисляет новую траекторию:

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

Обратные и прямые проходы повторяются до сходимости.

Регуляризация и поиск строк

Дифференциальное динамическое программирование — это алгоритм второго порядка, подобный методу Ньютона . Поэтому он делает большие шаги в направлении минимума и часто требует регуляризации и/или линейного поиска для достижения сходимости. ^[6]^[7] Регуляризация в контексте DDP означает обеспечение того, что $Q_{\mathbf {u} \mathbf {u} }$ матрица в уравнении 4 положительно определен . Поиск линии в DDP представляет собой масштабирование модификации управления с разомкнутым контуром. $\mathbf {k}$ некоторыми $0<\alpha <1$ .

Версия Монте-Карло

Выборочное дифференциальное динамическое программирование (SaDDP) — это вариант дифференциального динамического программирования Монте-Карло. ^[8]^[9]^[10] Он основан на рассмотрении квадратичной стоимости дифференциального динамического программирования как энергии распределения Больцмана . Таким образом, количества DDP могут быть сопоставлены со статистикой многомерного нормального распределения . Статистику можно пересчитать по выборочным траекториям без дифференциации.

Выборочное дифференциальное динамическое программирование было расширено до улучшения интегральной политики пути с помощью дифференциального динамического программирования. ^[11] Это создает связь между дифференциальным динамическим программированием и интегральным управлением по траектории. ^[12] который представляет собой основу стохастического оптимального управления.

Ограниченные проблемы

Дифференциальное динамическое программирование внутренней точки (IPDDP) представляет собой обобщение метода DDP внутренней точки , которое может решать задачу оптимального управления с нелинейным состоянием и входными ограничениями. ^[13]

См. также

Оптимальное управление

Ссылки

^ Мейн, DQ (1966). «Градиентный метод второго порядка оптимизации нелинейных систем с дискретным временем». Внутренний J-контроль . 3 : 85–95. дои : 10.1080/00207176608921369 .
^ Мейн, Дэвид К.; Джейкобсон, Дэвид Х. (1970). Дифференциальное динамическое программирование . Нью-Йорк: Американский паб Elsevier. компании ISBN 978-0-444-00070-5 .
^ де О. Пантоха, JFA (1988). «Дифференциальное динамическое программирование и метод Ньютона». Международный журнал контроля . 47 (5): 1539–1553. дои : 10.1080/00207178808906114 . ISSN 0020-7179 .
^ Ляо, LZ; В. Сапожник (1992). «Преимущества дифференциального динамического программирования перед методом Ньютона для задач оптимального управления с дискретным временем» . Корнеллский университет . hdl : 1813/5474 .
^ Моримото, Дж.; Г. Зеглин; К.Г. Аткесон (2003). «Минимаксное дифференциальное динамическое программирование: применение к двуногому шагающему роботу». Интеллектуальные роботы и системы, 2003 г. (IROS 2003). Слушания. 2003 Международная конференция IEEE/RSJ по . Том. 2. стр. 1927–1932.
^ Ляо, LZ; В. Сапожник (1991). «Сходимость в дифференциальном динамическом программировании без ограничений в дискретном времени». Транзакции IEEE при автоматическом управлении . 36 (6): 692. дои : 10.1109/9.86943 .
^ Тасса, Ю. (2011). Теория и реализация биомиметических контроллеров двигателей (PDF) (Диссертация). Еврейский университет. Архивировано из оригинала (PDF) 4 марта 2016 г. Проверено 27 февраля 2012 г.
^ «Выборочное дифференциальное динамическое программирование». Международная конференция IEEE/RSJ по интеллектуальным роботам и системам (IROS) , 2016 г. дои : 10.1109/IROS.2016.7759229 . S2CID 1338737 .
^ Раджамяки, Йоосе; Хямяляйнен, Пертту (июнь 2018 г.). Регуляризация выборочного дифференциального динамического программирования — Публикация конференции IEEE . Ежегодная Американская конференция по контролю (ACC) 2018 г. п.п. 2182–2189. дои : 10.23919/ACC.2018.8430799 . S2CID 243932441 . Проверено 19 октября 2018 г.
^ Раямяки, Йоосе (2018). Алгоритмы случайного поиска для оптимального управления . Университет Аалто. ISBN 978-952-60-8156-4 . ISSN 1799-4942 .
^ Лефевр, Том; Кревекёр, Гийом (июль 2019 г.). «Путь интегрального улучшения политики с помощью дифференциального динамического программирования» . Международная конференция IEEE/ASME по передовой интеллектуальной мехатронике (AIM) 2019 . стр. 739–745. дои : 10.1109/AIM.2019.8868359 . hdl : 1854/LU-8623968 . ISBN 978-1-7281-2493-3 . S2CID 204816072 .
^ Теодору, Евангелос; Бухли, Йонас; Шааль, Стефан (май 2010 г.). «Укрепление двигательных навыков в больших измерениях: интегральный подход» . 2010 Международная конференция IEEE по робототехнике и автоматизации . стр. 2397–2403. дои : 10.1109/РОБОТ.2010.5509336 . ISBN 978-1-4244-5038-1 . S2CID 15116370 .
^ Павлов, Андрей; Позор, Иман; Манзи, Крис (2020). «Дифференциальное динамическое программирование внутренних точек». arXiv : 2004.12710 [ math.OC ].

Внешние ссылки

[1] Мейн, DQ (1966). «Градиентный метод второго порядка оптимизации нелинейных систем с дискретным временем». Внутренний J-контроль . 3 : 85–95. дои : 10.1080/00207176608921369 .

[2] Мейн, Дэвид К.; Джейкобсон, Дэвид Х. (1970). Дифференциальное динамическое программирование . Нью-Йорк: Американский паб Elsevier. компании ISBN 978-0-444-00070-5 .

[3] де О. Пантоха, JFA (1988). «Дифференциальное динамическое программирование и метод Ньютона». Международный журнал контроля . 47 (5): 1539–1553. дои : 10.1080/00207178808906114 . ISSN 0020-7179 .

[4] Ляо, LZ; В. Сапожник (1992). «Преимущества дифференциального динамического программирования перед методом Ньютона для задач оптимального управления с дискретным временем» . Корнеллский университет . hdl : 1813/5474 .

[5] Моримото, Дж.; Г. Зеглин; К.Г. Аткесон (2003). «Минимаксное дифференциальное динамическое программирование: применение к двуногому шагающему роботу». Интеллектуальные роботы и системы, 2003 г. (IROS 2003). Слушания. 2003 Международная конференция IEEE/RSJ по . Том. 2. стр. 1927–1932.

[6] Ляо, LZ; В. Сапожник (1991). «Сходимость в дифференциальном динамическом программировании без ограничений в дискретном времени». Транзакции IEEE при автоматическом управлении . 36 (6): 692. дои : 10.1109/9.86943 .

[7] Тасса, Ю. (2011). Теория и реализация биомиметических контроллеров двигателей (PDF) (Диссертация). Еврейский университет. Архивировано из оригинала (PDF) 4 марта 2016 г. Проверено 27 февраля 2012 г.

[8] «Выборочное дифференциальное динамическое программирование». Международная конференция IEEE/RSJ по интеллектуальным роботам и системам (IROS) , 2016 г. дои : 10.1109/IROS.2016.7759229 . S2CID 1338737 .

[9] Раджамяки, Йоосе; Хямяляйнен, Пертту (июнь 2018 г.). Регуляризация выборочного дифференциального динамического программирования — Публикация конференции IEEE . Ежегодная Американская конференция по контролю (ACC) 2018 г. п.п. 2182–2189. дои : 10.23919/ACC.2018.8430799 . S2CID 243932441 . Проверено 19 октября 2018 г.

[10] Раямяки, Йоосе (2018). Алгоритмы случайного поиска для оптимального управления . Университет Аалто. ISBN 978-952-60-8156-4 . ISSN 1799-4942 .

[11] Лефевр, Том; Кревекёр, Гийом (июль 2019 г.). «Путь интегрального улучшения политики с помощью дифференциального динамического программирования» . Международная конференция IEEE/ASME по передовой интеллектуальной мехатронике (AIM) 2019 . стр. 739–745. дои : 10.1109/AIM.2019.8868359 . hdl : 1854/LU-8623968 . ISBN 978-1-7281-2493-3 . S2CID 204816072 .

[12] Теодору, Евангелос; Бухли, Йонас; Шааль, Стефан (май 2010 г.). «Укрепление двигательных навыков в больших измерениях: интегральный подход» . 2010 Международная конференция IEEE по робототехнике и автоматизации . стр. 2397–2403. дои : 10.1109/РОБОТ.2010.5509336 . ISBN 978-1-4244-5038-1 . S2CID 15116370 .

[13] Павлов, Андрей; Позор, Иман; Манзи, Крис (2020). «Дифференциальное динамическое программирование внутренних точек». arXiv : 2004.12710 [ math.OC ].

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]