При оптимизации динамических процессов необходимо определить оп- тимальную траекторию движения управляемого объекта из первоначального состояния в желаемое и последовательность управляющих воздействий, ко- торая позволяет реализовать эту оптимальную траекторию.
В динамическом программировании как и ранее при оптимизации стати- ческих процессов состояние объекта описывается вектором X. При этом со- стояние объекта на первом шаге управления описывается вектором Х 0; на втором шаге (т.е. состояние после первого шага управления) вектором X 1, значения координат которого отличны от значений координат вектора Х 0; на
k -м шаге – Хk; конечное состояние, в которое попадает управляемый объект
после m -го шага управления – вектором Xm.
Считается, что на каждом шаге управления имеется доступное множество управляющих воздействий Uk, из которого выбирается то управление uk, ко- торое будет переводить объект в последующее состояние. Этот k -й шаг
управления записывается так:
Xk –1
uk U k
= X k.
Выбирая различные управляющие воздействия на том или ином шаге управления, в итоге можно получить различные траектории движения объек- та из состояния Х 0 в состояние Хm. Это значит, что каждой возможной траек- тории соответствует своя последовательность управляющих воздействий, ко- торая называется также стратегией управления:
U = (u 1, u 2, u 3, … uk, … um).
Задача состоит в том, чтобы найти такую стратегию управления, которая была бы оптимальной, т.е. соответствовала оптимальной траектории движе- ния объекта (в зависимости от смысла задачи можно говорить о первичности стратегии управления и траектории, которая ей соответствует). Оптимальная стратегия управления обозначается U * оптимальная траектория – X *.
|
|
Для количественной оценки оптимальности вводится функция затрат на управление, которая может быть на каждом шаге разная, значение ее зависит от выбранного в данном состоянии управления: f k (X k –1, uk).
Функция затрат показывает, какие затраты на управление на k -м шаге по- требуются, если для перевода объекта из состояния Х k –1 в состояние Xk при- менить управляющее воздействие uk. Задача оптимизации заключается в том, чтобы минимизировать суммарные затраты на управление за все шаги:
m
k i
f k (X k –1, uk) → min.
При ограничениях на возможности выбора управляющих воздействий uk Uk (можно отметить, что в конкретной задаче могут присутствовать и другие ограничения).
Трудность оптимизации заключается в том, что выбирая в одном состоя- нии управление, трудно оценивать его оптимальность с точки зрения сум- марных затрат на последующих шагах. Иными словами, выбор на k -м шаге управления, которое наименьшее по затратам именно на этом шаге, в итоге может привести в такие состояния на последующих шагах, которые потре- буют значительных затрат для вывода объекта в желаемое состояние; наобо- рот, менее предпочтительное управление на данном шаге может оказаться выгодным в том смысле, что приведет в такие состояния, которые на следу- ющих шагах потребуют минимальных затрат. Чтобы преодолеть эти трудно- сти, метод динамического программирования основывается на использова- нии так называемого принципа оптимальности (принцип Беллмана). Одна из его формулировок следующая: каково бы ни было состояние объекта на не- котором, k -м шаге управления, управляющее воздействие на этом шаге нуж- но выбирать так, чтобы затраты на этом шаге плюс затраты на всех последу- ющих шагах были наименьшие по сравнению со всеми другими возможными управляющими воздействиями.
|
|
Принцип, конечно же, хорош, однако остается вопрос, как практически его реализовать (прогнозирование оптимальности действий при управлении со- стояниями объектов (особенно сложных объектов) остается проблематичным, т. к. требует прогнозирования возможных траекторий развития объекта (путей развития ситуации), сравнения их между собой и прогнозирования возможных затрат на управление. Жизненные реалии же таковы, что выбор, который де- лает человек на данном этапе и который кажется во всех отношениях опти- мальным сегодня, оказывается отнюдь не таковым по прошествии лет).
В методе динамического программирования проблема разрешается таким образом: поиск оптимальной стратегии управления осуществляется с конеч- ного, желаемого состояния объекта. Находясь в конечном состоянии X m, определяют возможные предыдущие состояния X m –1, из которых можно было объект перевести в состояние, конечное за один шаг управления при имею- щемся множестве возможных управляющих воздействий Um. Точнее, речь
идет о вариантах состояния объекта на предыдущем шаге, которые обозна-
– второй, Xj
m –1
– j -й вариант состояния на
m -шаге управления и т.д. Для каждого варианта из условия минимума
|
|
Fm (Xjm –1, um) → min
находится то управляющее воздействие, которое требует наименьших затрат при переходе в желаемое состояние Хm. Это управляющее воздействие назо- вем условно-оптимальным и обозначим u 0(Xjm –1) – управление, которое поз- воляет перевести объект из состояния Xjm –1 в конечное состояние при мини- муме затрат. Те наименьшие затраты, которые все же появятся при переводе объекта из Xjm –1 в Xm обозначим F (Xjm –1) – условные затраты для данного ва- рианта состояния на m – 1 шаге.
Далее все повторяется, только теперь определение предыдущего состоя- ния осуществляется не из конечного Хm, а из состояний Xjm –1, т.е. определя- ются те варианты состояний Xjm –2, из которых можно перейти в Xjm– 1. Переби- рая все возможные управления, для каждого из Xjm –2 находят величину услов- ных затрат по формуле
F (Xjm –2) = min [ f m –1(Xjm –2, um –1)+ F (Xjm –1)].
|
и ранее u 0(Xjm –2). Внимательный читатель уже может обнаружить определен-
ную закономерность и спрогнозировать, что же и как делается далее. Далее выполняются аналогичные действия, т.е. продолжается движение от конца к началу, вплоть до перехода к начальному состоянию X 0. При движении из со- стояния X 1 уже никаких вариантов не предполагается, т.к. начальное состоя-
ние X 0 считается известным и заранее определено. Общая формула этого движения, которая называется рекуррентной формулой динамического про- граммирования и по которой осуществляется определение условных затрат на каждом шаге и выбор условно-оптимального управления, запишется так
F (Xjk –1) = min [ f k (Xjk –1, uk)+ F (Xjk)],
uk Uk,
где нижняя запись означает, что выбор минимального значения на каждом шаге осуществляется путем перебора управляющих воздействий из множе- ства доступных на данном шаге Uk.
Таким образом, в результате описанного процесса получены следующие
результаты:
– для каждого шага управления спрогнозированы возможные варианты состояний, из которых в итоге можно прийти в конечное;
– для каждого варианта состояний на всех шагах определены условно- оптимальные управляющие воздействия, которые позволяют из этого состо- яния прийти в конечное с наименьшими затратами.
Далее остается только, двигаясь в обратном направлении, от начала к концу, применить найденные условно-оптимальные управления. Это делает- ся так: сначала из состояния X 0 применяется условно-оптимальное управле- ние u 0(X 0), которое сразу же записывается в оптимальную стратегию U *, т.е.
u i* = u 0(Х 0). Потом смотрим, куда же объект попал под действием этого
* 0 1 * *
тегию управления, т.е. u 2
*
= u (X 2). Аналогичным образом находим u 3, u 4 и
т.д. вплоть до um. Итак, оптимальная стратегия управления и оптимальная
траектория найдены.
Подводя итог вышесказанному, отметим, что алгоритм динамического программирования состоит из двух этапов. На первом этапе, двигаясь от ко- нечного состояния, для всех вариантов предшествующих состояний находят-
ся условно-оптимальные управления, которые переводят объект в конечное состояние с наименьшими затратами. На втором этапе, двигаясь от начально- го состояния, применяют найденное условно-оптимальные управление, кото- рое переводит объект из начального состояния в последующее; в этом после- дующем состоянии применяют найденное для него условно-оптимальное управление, которое переводит объект дальше и т.д. до конечного состояния (все эти состояния и их условно-оптимальные управления уже известны из первого этапа). Таким образом, среди всего множества состояний, найденных на первом этапе, находят оптимальную траекторию и среди множества всех условно-оптимальных управлений - оптимальную стратегию управления.