Стандартная процедура

Численные методы динамического программирования для задач небольшой размерности могут быть реализованы на ЭВМ. В более сложных случаях решение затрудняется, однако исключительная ценность результата (достигается абсолютный экстремум), гарантируемого методом, быстрое усовершенствование ЭВМ заставляют совершенствовать численные методы динамического программирования .

Рассмотрим рекуррентное уравнение (24.10) для задачи терминального управления (24.1), (24.2), (24.3), (24.7).

Каждую координату х( вектора х квантуем по уровню, т. е. будем считать, чтох( может принимать значения х},х?,...х?‘ на отрезке [а„ Ь(], которые определяются формулой хр = а{ + (к-1)ДХ[, к — 1, 2,..., Р,, где Р( = (Ь( - а()/Ах,- + 1; Дх( — шаг квантования. В результате квантования в пространстве {Ц х(0} образуется фазовая сетка (рис. 24.1).

Рис. 24.1

Перед началом процедуры функция Я(х(Л/)) вычисляется в узлах сетки с абсциссой С = О и полученные значения запоминаются. Таким образом, функция Веллмана = Я(х(М)) в узлах решетки при будет известна. На рис. 24.1 значения хк, для которых вычислена Уы, обведены кружком. Теперь по формуле (24.10) можно приступить к расчету У^—У^Ы-!, х(ЛГ-1)) в узлах фазовой сетки при - й - ДС.

В общем случае, когда нет никакой специальной информации об оптимальном управлении, поступают следующим образом. Путем квантования координат управления множество значений и допустимых управлений покрывают сеткой (рис. 24.2). Пусть и1, и2, ..., им узлы сетки, лежащие в и.

Рис. 24.2

Для вычисления значений функции Уы_г У(Л/-1, х(7У-1)) в узле хк={х$,х%,...хк} при Г^_1 = (0 - А) вычисляем векторы, показанные на рис. 24.3.

Рис. 24.3

В общем случае не все векторы (24.12) попадут в узлы фазовой сетки. Поэтому значения функции VN = (N, x(N)) при различных ик находятся с помощью интерполирования известных значений функции V(N, x(N)J = R(x(N)) в узлах решетки при t = o. Среди вычисленных значений VN находится минимальное, которое в силу формулы (24.10) равно V(N - 1, xk(N - 1)). Это значение для узла xk(N - 1) запоминается. Управление u(N-1,(N-l,xk(N-1)), на котором достигается минимум, также запоминается. Подобным образом перебираются все узлы сетки для t = О - At. В результате будут записаны в память ЭВМ значения функции Беллмана V(N - 1, x(N - 1)) для этих узлов. Будут известны и значения u(N - l,x(N -1)) в этих узлах. Теперь значения V(N, х(ЛГ)) могут быть убраны из памяти.

Следующие шаги процедуры в точности повторяют первый, и процесс продолжается вычислением функции V(t,x(t),U(t,x(t))) в узлах фазовой сетки в направлении убывания аргумента t. Через N- 1 шагов получаются функции V(t0,x(t0),u(t0,x(t0))) при t = t0.

Исходную задачу оптимального терминального управления можно считать решенной, ибо V(t0, x(t0)) — минимальное значение критерия качества для заданных начальных условий.

Оптимальное управление и траектория находятся по записанным функциям u(t0,x(t0)), u(t0 + At,x(t0 + At)), ..., u(O- At,x(d- At)) элементарно:

Проанализируем полученный результат.

Отметим сначала достоинства:

  • — процедура не использует никаких аналитических свойств функции /(1,х(Г),и(1)), Я(й,х(О)), ?(1,х(1),н(1)) и множества и — они могут быть заданы любым способом;
  • — управление й(х,х(х')'), Г е [^0,0 — АС] доставляет критерию качества абсолютный минимум (а не относительный);
  • — оптимальное управление получено не для одной точки х0, а для всех узлов фазовой сетки с абсциссой 1 > 10, что позволяет проанализировать чувствительность решения к изменению начальных условий.

Один из главных недостатков процедуры — чрезмерные требования к объему оперативной памяти. На каждом шаге нужно хранить 7(1,х(1)), У(С 4- Д1,х(1 + Д1)),й(т,х(т)) для всех узлов сетки при т > 1. В совокупности число точек в памяти к моменту времени (О - кД1) п

не более (2 + т/с)]^[Р(, где т - размерность вектора управления. 1=1

Поскольку число 100 < Р{ < 150 можно считать обычным, то уже для п = 4 получаем число, превосходящее 1004 = 108, что для объема оперативной памяти ЭВМ очень велико. Этот недостаток процедуры Веллман назвал «проклятием размерности».

Другой недостаток — опасность расширяющейся сетки. Он состоит в следующем. Нетрудно построить процессы, для которых в каждой точке (1, х(1)) совокупность векторов (24.12) имеет вид, изображенный на рис. 24.4, когда концы векторов попадают выше и ниже горизонтальной линии. В такой ситуации начальная фазовая сетка может оказаться недостаточной для завершения процесса вычислений, и вычисления функции 7(1, х(1)) оборвутся, так как для некоторых точек в памяти ЭВМ нет значений функции Веллмана. Во всех узлах, не обведенных кружком, значения 7(1, х(1)) нельзя вычислить, если фазовая сетка в момент 1 = й недостаточно велика. Увеличение сетки ведет к увеличению необходимой памяти.

Рис. 24.4

Интересно отметить, что наличие фазовых ограничений упрощает решение задачи, так как уменьшается расчетное поле сетки.

Для сокращения объема вычислений разработан ряд методов:

  • — аппроксимация функции Веллмана;
  • — аппроксимация законов управления;
  • — метод переменного шага сетки;
  • — учет специфики задачи;
  • — применение метода последовательных приближений для решения некоторых видов рекуррентных уравнений для функции Веллмана;
  • — введение искусственных ограничений;
  • — использование областей достижимости и др.
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >