Некоторые минимаксные задачи управления и маршрутизации

• Автор: Серов, Вячеслав Петрович
• Шифр специальности: 01.01.02
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Екатеринбург
• Количество страниц: 107 с.

Оглавление
Введение

Глава 1. Задача обхода системы множеств в

классе позиционных стратегий

1.1. Постановка задачи последовательного обхода системы множеств в классе позиционных
стратегий

1.2. Уравнение Веллмана

1.3. Оптимальная минимаксная стратегия

1.4. Задача на узкие места

1.5. Эвристические стратегии

Глава 2. Минимаксные задачи последовательного управления

2.1. Одна минимаксная задача управления с импульсным ограничением на управление и ее расширение в
в классе конечно-аддитивных мер
2.2. Необходимые условия оптимальности обобщенного управления
2.3. Задача последовательного программного уклонения для собственно линейной системы с комбинированным ограничением на управления
2.4. Необходимые условия оптимальности в задаче программного уклонения с геометрическими ограничениями на управление
2.5. Примеры
Приложение
Литература

ВВЕДЕНИЕ
Настоящая диссертационная работа посвящена минимаксным задачам последовательного управления с элементами маршрутизации.
В последние годы классические задачи комбинаторной оптимизации (в первую очередь, задача коммивояжера (ЗК), задача о наикратчайших путях (ЗНП), задача о минимальном остовном дереве) стали изучаться в обобщенной постановке, когда вместо фиксированного узла Х{ рассматривается множество Мг, которому может принадлежать узел хг. Преимуществом таких обобщенных постановок задач комбинаторной оптимизации является то, что появляется дополнительная свобода варьировать узлы Х( для достижения лучшего качества (скажем, при проектировании конкретной технической системы).
В настоящей работе делается следующий шаг в этом направлении, и предлагается постановка, в которой проектировщик не имеет возможности выбирать точки х* или управлять ими. Таким образом, получаем игровую ситуацию, когда распоряжение точками ж* отдается игроку-противнику или (противостоящей) природе. Множествами Мг моделируется (непредсказуемое) поведение точек Х{ (они могут представлять собой, в зависимости от конкретной задачи, помехи, ошибки, возмущения, шумы, сбои и т.п., или разумные управления игрока-противника).
Особый интерес представляют позиционные динамические задачи (ЗК, ЗНП и др.), когда решения принимаются игроками в динамике, в зависимости от предыдущих действий противника. Построение позиционных стратегий управления (т.е. правил принятия решений по принципу обратной связи) является новым, неисследованным и трудным кругом задач. Основной вопрос при решении задач этого класса заключается в следующем: как конструировать позиционное управление в динами-

ческой игре с комбинаторным функционалом, и как сформулировать и решить задачу в замкнутом виде?
В настоящей работе вводится и изучается игровая обобщенная ЗК в классе позиционных стратегий. Для постановки и решения задачи используется подход, связанный с минимизацией гарантированного результата в классе позиционных стратегий, см. монографии H.H. Кра-совского, А.И. Субботина, А.Г. Ченцова [25, 27, 63, 95].
Обобщенная (неигровая) ЗК и ее решение методом динамического программирования рассматривались А.Г. Ченцовым и его сотрудниками [23, 83]. Следует отметить, что многие комбинаторные задачи могут быть переформулированы в виде ЗК или обобщенной ЗК. Как отмечается в литературе, ЗК занимает центральное место в комбинаторной оптимизации, и она явилась прототипической задачей современной комбинаторной оптимизации. Простота ее формулировки сочетается с трудностью решения. Многие подходы к решениям, ставшие стандартными в комбинаторной оптимизации, сначала были развиты и опробованы в контексте ЗК. Таким образом, в данной работе объединяются рамки и инструментарий теории динамических игр (программное движение, позиционная стратегия, движение, порожденное позиционной стратегией, многократный минимакс, позиционный минимакс, и др.) и весьма нетривиальная комбинаторная задача, каковой является обобщенная ЗК. Таким образом, тематика первой части органически связана с задачами управления.
Вторая часть диссертации посвящена программным минимаксным задачам оптимального управления. Основой рассматриваемых далее конструкций является теория принципа максимума Л.С. Понтрягина. Здесь рассматриваются, в частности, задачи сближения и уклонения траекторий управляемой системы относительно дискретной по времени системы выпуклых компактов, при различных типах ограничений на
После этого игрок 2 выбирает точку Х2 £ МГ2, и так далее. На (к + 1)-м шаге игрок 1 на основании информации о Г,... ,Гк и Хк £ МГк выбирает номер Гк+г следующего множества для посещения, затем игрок 2 выбирает точку Хк+1 € МГм, так что траектория приходит в точку Хк+ь На последнем, т-м, шаге игрок 1 не имеет больше выбора (т.к. остается посетить только одно множество МГт), но игрок 2 выбирает точку хт £ МГт. В результате получаем маршрут обхода г = (гц,..., гт) и траекторию то, х,..., хт. При такой игровой формализации игрок 1 на каждом шаге, взависимости от того, какая неопределенность хк реализовалась, может генерировать различные продолжения пройденной части маршрута. Получая во время движения информацию о точках Хк, он может, в частности, использовать ’’неправильное” поведение противника с тем, чтобы улучшить для себя итоговое значение I.
Вышеописанная поочередная игра двух игроков является игрой с информационной дискриминацией первого игрока (в том смысле, что на каждом шаге он ’’ходит первым” и не знает, каким будет ход противника на этом шаге, тогда как игрок 2, ’’ходит вторым”, зная ход игрока 1 на этом шаге). Итак, игроки ходят поочередно, при этом первый игрок ходит первым.
В качестве игрока 2 может рассматриваться как реальный игрок, разумно противодействующий игроку 1 и стремящийся максимизировать I, так и противостоящая природа, ’’управляющая” неопределенными факторами, ограниченными условиями Хк е М/., к Е 1,т.
Мы рассматриваем задачу оптимизации обхода только с точки зрения игрока 1. Отметим, что в случае реального игрока 2 он может использовать любую мыслимую информацию о действиях игрока 1 и о траектории. Для определенности, будем интерпретировать игру как ’’игру с природой”, и, таким образом, интерпретировать векторы Хк € Мк как неопределенные факторы. Далее, удобно формализовать эту задачу как