Алгоритм покоординатного спуску в методі динамічного програмування для задач цифрового оптимального керування



Анотація. Запропоновано модифікацію алгоритму розв’язання задачі оптимального керування дискретними об’єктами методом динамічного програмування шляхом за-стосування методу покоординатного спуску.

Ключові слова: динамічне програмування, оптимальне керування, метод рівномірного пошуку, метод покоординатного спуску, моделювання, MATLAB /Simulink.

Майєр І.В.

КПІ ім. Ігоря Сікорського

Київ, Україна

Писаренко А.В.

КПІ ім. Ігоря Сікорського

Київ, Україна

Algorithm of Coordinate Descent in the Method of Dynamic Programming for Digital Optimal Control Problems

Abstract. The modification of the algorithm for discrete optimal control problem by the dynamic programming method applying a coordinate descent method is proposed.

Keywords: dynamic programming, optimal control, method of uniform search, method of coordinate descent, simulation, MATLAB/Simulink.

Iryna Mayer

Igor Sikorsky Kyiv Polytechnic Institute

Kyiv, Ukraine Andrii Pysarenko

Igor Sikorsky Kyiv Polytechnic Institute

Kyiv, Ukraine om

Значне число задач, що виникають в суспільстві, пов’язані з процесами прийняття рішень. Параметри цих процесів вибираються таким чином, щоб забезпечити екстремальне значення певного показника (вартість, ма-са, час роботи, тощо) при умові наявних обмежень на параметри процесу. Сьогодні більшість систем керування проектують на основі різного роду цифрових обчислюва-льних пристроїв, що забезпечує високу точність, швидко-дію, гнучкість при налаштуванні та збалансовану вар-тість. Розроблення та вдосконалення алгоритмів, що реа-лізують (зокрема) методи оптимального керування для побудови високошвидкісних цифрових систем автоматич-ного керування є актуальної задачею сьогодення. При проектуванні і оптимізації системи важливим мо-ментом є формування цілі оптимізації, яка математично виражається як вимога забезпечення екстремального зна-чення деякого критерію оптимальності. Динамічне програмування – це підхід до розв’язання складних задач шляхом їх розбиття на більш прості підзадачі. Даний метод заснований на принципі оптима-льності Беллмана, який дозволяє скоротити перебір рі-шень в багатоетапних нелінійних задачах [1]. Метод динамічного програмування для задачі опти-мального керування полягає у тому що потрібно з почат-кової заданої точки траєкторії об’єкту керування оптима-льно потрапити в задану кінцеву точку, частіше всього це 0. Для цього задачу ділять на підзадачі і починають вирі-шувати її з кінця – це називається зворотній прохід. Він полягає в тому, що на кожному кроці знаходять відповідно до правил обчислень усі можливі оптимальні рішення. Далі застосовується прямий прохід, який з усіх можливих знайдених рішень для кожної підзадачі дозволяє сформу-вати оптимальне рішення основної задачі. Відомий підхід до розв’язання задачі оптимального ке-рування об’єктом першого порядку методом динамічного програмування [2] для знаходження на кожному проміжку часу мінімального рішення використовує метод рівномір-ного пошуку. Хоча даний метод і є легким у реалізації, але він не є ефективним, оскільки витрачається багато часу та обчислювальних потужностей для вирішення задачі. Для позбавлення від вказаних недоліків замість методу рівномірного пошуку для функції однієї змінної було обрано метод покоординатного спуску для функції багатьох змінних. Застосуємо метод покоординатного спуску для розв’язання підзадач зворотного проходу методу динамі-чного програмування.

На першому кроці методу покоординатного спуску в якості початкового наближення обираємо одну із коорди-нат ${{M}_{0}}(x_{1}^{(0)},x_{2}^{(0)},...,x_{n}^{(0)})$ на заданій області допустимих значень. Підставляємо в кри-терій оптимальності $I$ усі точки початкового набли-ження крім першої. Далі отримаємо функцію однієї змінної $I=\int{(x_{1}^{(0)},x_{2}^{(0)},...,x_{n}^{(0)})}$. Знайшовши для даної функції точку мінімуму, переходимо від точки ${{M}_{0}}$ до точки ${{M}_{1}}(x_{1}^{(1)},x_{2}^{(0)},...,x_{n}^{(0)})$, в якій критерій оптимальності $I$приймає мінімальне зна-чення по координаті ${{x}_{1}}$. Це перший крок оптимі-зації, що складається з спуску по координаті ${{x}_{1}}$. Для знаходження мінімуму можна використовувати метод золотого перетину, метод Фібоначі, тощо. Далі потрібно підставити в критерій \[I\]всі координати точки ${{M}_{1}}$ крім ${{M}_{2}}$ та розглянути функцію виду $I=\int{(x_{1}^{(1)},x_{2}^{(0)},...,x_{n}^{(0)})}$. Знову вирішити одновимірну задачу оптимізації та знайти нову точку ${{M}_{2}}(x_{1}^{(1)},x_{2}^{(1)},...,x_{n}^{(0)})$, в якій критерій $I$ приймає мінімальне значення по коор-динаті ${{x}_{2}}$. Аналогічно проводиться пошук за координатами ${{x}_{3}},{{x}_{4}},\ldots {{x}_{n}}$. Після цього все повторюється від ${{x}_{1}}$ до ${{x}_{n}}$. В результаті буде отримана послідовність точок ${{M}_{0}},\text{ }{{M}_{1}},\ldots {{M}_{n}}$ в яких значення цільової функції складають монотонно спадну послідовність $I\left( {{M}_{0}} \right)~\ge I\left( {{M}_{1}} \right)\ge \text{ }I\left( {{M}_{2}} \right)\ge \ldots $. Також на будь-якому i-му кроці можна даний процес призупинити та в якості мінімального значення викорис-товувати значення критерію в точці ${{M}_{i}}$ [3]. Таким чином, метод покоординатного спуску зводить задачу про знаходження найменшого значення функції багатьох змінних до багаторазового рішення одновимір-них задач оптимізації по кожній з цих змінних.

В середовищі MATLAB було написано скрипт для розв’язання задачі оптимального керування методом ди-намічного програмування з використанням методу покоо-рдинатного спуску. Розглянемо приклад. Задано об’єкт другого порядку у вигляді дискретної моделі у просторі станів:

\[\left\{ \begin{align} & {{x}_{1}}[k+1]=0,1765{{x}_{1}}[k]-0,7686{{x}_{2}}[k]+0,25u[k], \\ & {{x}_{2}}[k+1]=0,5{{x}_{1}}[k]+0,5{{x}_{2}}[k], \qquad (1)\\ & y[k]={{x}_{1}}[k]+{{x}_{2}}[k]. \\ \end{align} \right.\]

Необхідно знайти таку оптимальну керуючу послідов-ність u, що переведе об’єкт керування з початкового стану $Xstart=\left[ 5\text{ ;}-5 \right]$ в кінцевий стан $Xend=\left[ 0\text{ ;}0 \right]$ за $N=13$ кроків кванту-вання, а значення критерію якості $I=\int{(x_{1}^{2}+x_{2}^{2}+{{u}^{2}})}$ буде мініма-льним. Область допустимих керувань: $\Omega (u):\left| u \right|\le 1$. Області допустимих станів: $V({{x}_{1}}):{{x}_{1}}\left[ \text{-8; }12 \right]$, $~V({{x}_{2}}):{{x}_{2}}\left[ -9\text{ ;12} \right]$.

В результаті роботи скрипту оптимано послідовність керувань та станів об’єкту в кожний момент квантування :

k=0; x1=-5.000; x2=5.000; U=-0.0345

k=1; x1=-4.733; x2=0.000; U=-0.0345

k=2; x1=-0.843; x2=-2.366; U=-0.0345

k=3; x1=1.662; x2=-1.605; U=-0.0345

k=4; x1=1.518; x2=0.000; U=-0.0345

k=5; x1=0.238; x2=0.773; U=-0.0345

k=6; x1=-0.561; x2=0.505; U=0.0345

k=7; x1=-0.478; x2=0.000; U=-0.0345

k=8; x1=-0.072; x2=-0.253; U=-0.0345

k=9; x1=0.175; x2=-0.162; U=0.0345

k=10; x1=0.175; x2=0.000; U=-0.0345

k=11; x1=0.016; x2=0.085; U=-0.0345

k=12; x1=-0.071; x2=0.0505; U=0.0345

k=13; x1=0.000; x2=0.000; U=-0.0345

На рис. 1 представлено побудовану в MATLAB /Simulink модель дискретної системи керування. Отрима-ну послідовність керувань подаємо на об’єкт (Discrete State-Space) за допомогою блоку From Workspace. На рис. 2 представлено графіки перехідних процесів за станами ${{x}_{1}}$ (суцільна лінія) та ${{x}_{2}}$ (штрихова лінія). На рис. 3 зображено оптимальну траєкторію об’єкту керування, а на рис. 4 – графік керування системи.

Рис. 1 – Модель дискретної системи керування у MATLAB/Simulink

Рис. 2 – Перехідні процеси за станами x1 та x2

Рис. 3 – Траєкторія руху об’єкту

Рис. 4 – Графік керування

З отриманих графіків видно, що знайдена оптимальна послідовність керування переводить його з заданого по-чаткового стану у заданий кінцевий стан за визначену кількість тактів квантування.

ЛІТЕРАТУРА

$1.$ Denardo E. V. Dynamic Programming: Models and Applications / Eric V. Denardo. – NY: Dover Publications, 2003.

$2.$ Чураков, Е. П. Оптимальные и адаптивные системы : учебное пособие для вузов по специальности "Автоматика и телемеханика" / Е. П. Чураков . – М.: Энергоатомиздат, 1987 . – 256 с.

$3.$ Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высшая школа, 1986

May 17, 2018