Содержание к диссертации
Введение
1 Линейная нестационарная задача поиска 22
1.1 Постановка задачи 22
1.2 Вспомогательные определения и утверждения 24
1.3 Множество всех возможных траекторий динамической системы 26
1.4 Условие уклонения траектории от терминального множества . 30
1.5 Необходимое и достаточное условие решения дискретной задачи поиска 32
1.6 Декомпозиция необходимого и достаточного условие решения дискретной задачи поиска
1.7 Свойства функций Rk(x,a) 40
2 Задача поиска в случае двумерного терминального множества 45
2.1 Задача поиска с линейной динамикой прячущегося объекта . 45
2.1.1 Постановка задачи 45
2.1.2 Вспомогательные определения и утверждения 46
2.1.3 Алгоритм построения управления поиска 49
2.1.4 Построение управления движения вдоль границы гладкого выпуклого компакта 53
2.1.5 Построение управления поиска 62
2.1.6 Оценки скорости изменения области неопределенности . 70
2.1.7 Построение ограничивающего множества 73
2.1.8 Запись алгоритма поиска в терминах эллипсоидального исчисления 75
2.1.9 Некоторые особенности численной реализации алгоритма поиска 85
2.2 Задача поиска с простой динамикой прячущегося объекта 87
2.2.1 Постановка задачи 87
2.2.2 Динамика области неопределенности на плоскости 87
2.2.3 Траектория обхода области неопределенности 100
2.2.4 Примеры применения метода 105
3 Операторные конструкции в нелинейной задаче поиска 111
3.1 Постановка задачи 111
3.2 Вспомогательные определения и утверждения 112
3.3 Операторные конструкций в задаче поиска 114
3.4 Телесные множества и их свойства 122
3.5 Аппроксимирующий оператор 123
Литература 130
- Вспомогательные определения и утверждения
- Необходимое и достаточное условие решения дискретной задачи поиска
- Вспомогательные определения и утверждения
- Вспомогательные определения и утверждения
Введение к работе
Работа посвящена одной из задач гарантированного управления динамической системой в условия неопределенности — задаче гарантированного динамического поиска.
В литературе рассматриваются различные постановки задач динамического поиска. Большинство из них характеризуются следующими понятиями: динамическая система, описывающая процесс поиска, множество допустимых стратегий ищущего объекта, множество допустимых стратегий прячущегося объекта и условие, выполнение которого означает обнаружение прячущегося объекта ищущим. Цель ищущего объекта, при выборе своей стратегии, — обеспечить выполнение условия обнаружения, цель прячущегося объекта — избежать выполнения условия обнаружения. Задачи поиска характеризуются тем, что ищущий объект при выборе своей стратегии обладает только априорно известной до начала процесса поиска информацией, такой как множество возможных стратегий прячущего объекта и множество возможных начальных положений системы. Никакой дополнительной информации о текущем положение динамической системы и стратегии, выбранной прячущимся объектом, во время процесса поиска не поступает. Другая, важная черта задач поиска состоит в том, что момент выполнения условия обнаружения не фиксирован. Таким образом, задачи поиска составляют отдельный класс задач управления.
Среди постановок задач динамического поиска можно выделить три основ-' ных класса: стохастические, игровые и гарантированные задачи поиска. Данное деление определяется различным понимаем решения задачи.
Примером стохастической задачи поиска является задача, в которой априорно известна (или удовлетворяет заданным уравнениям) функция распределения вероятности выбора прячущимся объектом заданной стратегии из множества допустимых стратегий. Под решением задачи понимается допустимая стратегия ищущего объекта, максимизирующая некоторый функционал, который отражает эффективность стратегии поиска. Например, таким функционалом может быть вероятность выполнения условия обнаружения на заданном отрезке времени. Стохастические задачи поиска исследовались в работах В. И. Аркина, О. Хеллмана, В. А. Абчука, В. Г. Суздаля, Л. А. Петросяна,
Л. А. Емельянова. Варианты постановок таких задач и подходы к их решению рассмотрены в [ 1,84].
В игровой постановке, задача поиска является игрой двух лиц с нулевой суммой (в случае одного ищущего игрока). В качестве функционала, который минимизирует ищущий и максимизирует прячущийся, часто рассматривают время прошедшее до момента выполнения условия обнаружения при выбранных стратегиях игроков. Под решением задачи понимается пара — стратегия ищущего и стратегия прячущегося игрока, — которые соответствуют седло-вой точке функционала. Как правило, в игровой задаче поиска решение ищут в смешанных стратегиях, т.е. находят вероятностные распределения на множествах допустимых стратегий игроков. Игровые задачи поиска рассматривали: Р. Айзеке [3], Л. А. Петросян, Н. А. Зенкевич, А. Ю. Гарнаев, М. И. Зели-кин, S. Gal, В. О. Koopman. Варианты постановок игровых задач рассмотрены в [60].
Задачу гарантированного поиска рассматривают в различных постановках, в зависимости от предположений о динамики прячущегося объекта. Так рассматривают задачи о поиске неподвижного объекта, о поиске объекта с заданным параметрическим семейством возможных траекторий, о поиске управляемого (другим лицом) объекта. Под решением задачи понимается допустимая стратегия ищущего объекта, обеспечивающая выполнение условия обнаружения при любой допустимой стратегии прячущегося объекта. Гарантированный поиск рассмотрен в работах Ф. Л. Черноусько, Л. А. Петросяна, В. В. Ски-товича, С. В. Чистякова, А. Ю. Гарнаева, Н. А. Зенкевича, О. А. Малафеева, Д. П. Кима, Е. В. Шикина, С. М. Губайдуллина, А. Г. Чхартишвили, С. Б. Березина, П. М. Ларина, А. А. Скворцова, С. В. Местникова.
Задача гарантированного поиска неподвижного объекта предполагает, что прячущийся объект в начальный момент времени выбирает точку своего положения из заданного множества и остается в этой точке в течение всего процесса поиска. Ищущий объект должен выбрать такую траекторию движения, чтобы гарантировать выполнение условия обнаружения для любой точки множества возможных положений прячущегося объекта. Следующей задачей гарантированного поиска является задача, когда прячущийся объект подвижен и выбирает траекторию своего движения из заданного параметрического семейства кривых. Соответственно, ищущий объект должен выбрать такую траекторию движения, чтобы гарантировать выполнение условия обнаружения для любой возможной кривой движения прячущегося объекта. В работах В. В. Скитовича и С. В. Чистякова [78] предложен метод, который позволяет свести эту задачу к задаче поиска неподвижного объекта.
Задача поиска управляемого прячущегося объекта предполагает, что прячущийся объект выбирает допустимое программное управление, которое порождает его траекторию движения. Ищущий объект не обладает информацией о сделанном выборе. Он должен выбрать свою траекторию движения, гарантирующую выполнение условия обнаружения для любой допустимой траектории прячущегося объекта. Этой задаче гарантированно поиска в предположении, что динамика ищущего и прячущегося объектов является простой, посвящен целый ряд работ. В работах Ф. Л. Черноусько [85] рассмотрена задача поиска в двумерном и трехмерном пространстве, когда прячущийся объект может перемещаться только в пределах заданной области. Большая серия работ написана Е. В. Шикиным [86] и его учениками А. Г. Чхартишвили, С. Б. Бере-зиным [87], П. М. Лариным [43], А. А. Скворцовым [77], в которых исследуется задача поиска на некотором классе поверхностей, в двухмерных и трехмерных областях, приводятся достаточные условия существования и численные методы построения траекторий поиска. Основной инструмент этих исследований — анализ области неопределенности, т.е. множества точек, где может находиться прячущийся объект в определенный момент времени. Метод аппроксимации области неопределенности для сложной динамики ищущего и прячущегося объектов рассмотрен в работах СВ. Местникова [49].
В данной работе рассматривается задача гарантированного поиска управляемого прячущегося объекта, которая в общем виде формулируется следующий образом. Динамика системы описывается системой обыкновенных дифференциальных уравнений z = f{t,z,u,v). (1)
Функция и = u(t) — программное управление, которое требуется выбрать из заданного множества допустимых управлений U, в соответствии с заданной целью. Функция v = v(t) — неизвестное возмущение, которое может воз- никнуть в системе, причем известно множество возможных возмущений V. В начальный момент времени t = tQ положение системы определено неточно. Известно, что начальная точка z{to) принадлежит заданному множеству Zq. Обозначим решение дифференциального уравнения (1) к моменту времени t с начальной точкой z(to) = z0 и функциями и(-), v(-) через z(t\to, zq, u(-), v(-)). Задачу гарантированного динамического поиска сформулируем следующим образом: найти момент времени Ts и найти такое допустимое управление us(-) Є U, что для каждой начальной точки zq Є Zq и для каждого возможного возмущения v(-) Є V найдется момент времени t = t(z0)v(-)) [to,Ts], ддя которого выполнится терминальное условие (условие обнаружения) п(1)г(Що,го,и,(-)А-)) Є Af, (2) где 7г(і) — матричная функция и M(t) — многозначное отображение, заданные на отрезке времени [to, Ts).
Отметим, что в соответствии с поставленной задачей, требуется найти такое программное управление us{-) Є К, до начала движение системы, которое обеспечит выполнение терминального условия (2), каким бы ни оказалось начальное положение системы z{to) є Zq и какое бы допустимое возмущение г;(-) Є V ни возникло в системе. Причем момент выполнение терминального условия не фиксирован и, вообще говоря, зависит от пары (z(to),v(-)). Выбор управления и3(-) определяется только дифференциальным уравнением (1), множествами Z0, U, V, матричной функцией 7г(і) и многозначным отображением М(і).
Частным является случай, когда динамическая система распадается на две независимые части (x = g(t,x,u), \ y = h(t,y,v).
В начальный момент времени t = to для начальной точки x(to) выполняется равенство x(t0) = хо, а для начальной точки y(tQ) известно только то, что выполняется включение у(t0) Є Y0, где Уо — заданное множество.
Движение вектора x(t) определяется заданной начальной точкой xfo) = хо и выбранной функцией и(-) Є U и не зависит от неизвестной функции v(-).
Будем считать, что вектор x(t) описывает положение некоторого, управля- емого нами, объекта, которого обозначим буквой S. Аналогично, движение вектора y(t), определяемое начальной точкой y(t0) Є Yq и функцией v(-) Є V и не зависящее от функции и(-), определяет движение другого объекта, которого обозначим буквой Я. Движение объекта Я не контролируемо нами и, более того, не известно, так как не известны ни начальная точка у (to), ни функция v(-).
В этом случае, задачу гарантированного динамического поиска сформулируем следующим образом: найти момент времени Ts и найти такое допустимое управление щ(-) еЫ,что для каждой начальной точки у0 Yq и Для каждого возможного возмущения і>(-) е V найдется момент времени t = t(yQ, v(-)) є [to, Ts], для которого выполнится терминальное условие тгяЙ2/№о, Уо, О) Є 7rs(i>№o, аго, «*()) + M(t), (4) где 7Гя(), tts() — матричные функции и M(t) — многозначное отображение, заданные на отрезке времени [to,^]- Описанный частный случай сводится к общей задаче (1), (2), если положить K(t) = (-*s(t),KH(t)).
Задача (3), (4) допускает следующую геометрическую интерпретацию. В начальный момент времени to объект Я находится в некоторой точке y(to) Yq. Затем он начинает движение с некоторым допустимым управлением v(-) є V. Объект 5 в начальный момент времени находится в заданной точке x(to) = xq. Он не знает точного значения у (to), не знает выбранного управления v(-) и не получает никакой информации о траектории y(t) движения объекта Я. Цель объекта S заключается в выборе управления us(-) U, обеспечивающее выполнение терминального условия (4) для любой возможной пары (y(to),v(-)) Є Yq х V. Или, другими-словами, объект S выбирает управление щ(-) так, чтобы найти движущийся объект Я, если условием обнаружения объекта Я является включение (4). Такая геометрическая интерпретация описанной задачи объясняет название работы. Будем называть объект S — ищущим, объект Н — прячущимся, управление и(-) — управлением ищущего объекта, управление v(-) —управлением прячущегося объекта, управление и3(-), решающее задачу, — управлением поиска.
В традиционной постановке задач поиска динамика ищущего и прячущегося объектов считается независимой друг от друга. В работе сформулирована и исследуется более общая задача (в первой и третьей главе), когда динамику объектов нельзя разделить на независимые части. Постановка задачи формулируется как задача управления в условиях неопределенности в классе программных управлений. Подходы к решению задач управления в условиях неопределенности в классе программных управлений в случае, когда момент времени прихода на целевое множества задан, исследовались А. Б. Куржан-ским [38], В. В. Скитовичем, С. В. Чистяковым и др. В задаче поиска момент времени прихода на целевое множество (т.е. выполнения условия обнаружения) не фиксирован. Методы решения таких задач нуждаются в дальнейшем развитии.
Вторая задача, которая рассматривается в работе и связана с задачей гарантированного поиска, заключается в построении множества начальных точек Zq, для которых заданное управление и(-) на заданном отрезке времени [to,T] является управлением поиска.
Эта задача пересекается с задачей построения множества начальных позиций разрешимости задачи преследования в нелинейных нестационарных дифференциальных играх. Подход к построению множества начальных позиций в дифференциальных играх основан на понятии стабильного моста, введенного в работах Н. Н. Красовского и А. И. Субботина [35]. Методы построения стабильных мостов исследовались в работах Н. Н. Красовского, А. И. Субботина, Б. Н. Пшеничного [72], В. В. Остапенко, В. Н. Ушакова [82], А. А. Успенского, Т. Б. Токманцева, А. М. Тарасьева, В. С. Пацко, А. А. Меликяна, Е. С. Половинкина.
При применении подобного подхода к задачам поиска необходимо учитывать, что нестационарность задачи поиска возникает в результате подстановки в правую часть дифференциального уравнения управляющей функции.
Краткое содержание работы.
В первой главе рассматривается задача поиска для линейной нестационарной системы z = B(t)u + v на заданном отрезке времени [to, Т), где вектор z є Rn, u(t) eU,U — выпуклый компакт в пространстве Rp, v(t) Є V(t), V(t) —измеримое ограниченное многозначное отображение отрезка [to,T] во множество непустых выпуклых компактов пространства R9, элементы матрицы B(t) — непрерывные функции на отрезке [to,T].
Такая система включает в себя как частный случай линейную систему z = A(t)z + B{t)u + C(t)v, где вектор z Є Rn, u(t) Є U, U — выпуклый компакт в пространстве Кр, v(t) Є V, V — выпуклый компакт в пространстве R9. Элементы матриц A(t) Є Rnxn, B(t) Є Rnxp, C(t) Rnxq — непрерывные функции на отрезке [to, П.
Пусть задано непрерывное многозначное отображение M(t) на отрезке [to,T] во множество непустых выпуклых компактов пространства Rm, матрица 7г() є Rmxn с непрерывными элементами на отрезке [t0,T] и выпуклый компакт Zq в пространстве Rn.
Задача гарантированного динамического поиска формулируется следующим образом: найти такое допустимое управление us(t) на отрезке времени [to,T], что для каждой точки z0 Zq и каждого допустимого v(-) существует момент времени t = t(zo, v(-)) Є [to, Т], для которого выполняется терминальное условие K{t)z{t\t0, Zq, Us{-), V(-)) Є М(ї).
Сформулированная задача называется непрерывной задачей поиска. Совместно с непрерывной рассматривается дискретная задача. Зафиксируем произвольное конечное разбиение отрезка [to, Т] UJ = {to,t\,... ,ttf}, где ti-i < U для і = 1,..., N и tju = Т. Дискретная задача поиска для заданного разбиения ui формулируется следующим образом. Найти такое допустимое кусочно-постоянное управление uf(t) = щ для t Є (U-u U], і — 1, , N> что для каждой точки zq є Zq и каждого допустимого v{-) существует момент времени t = t(zo, v(-)) Є uj, для которого выполняется условие Tt{t)z(t\t0,z0,us{-),v{-)) Є M(t).
Решение дискретной задачи поиска й(-) для любого конечного разбиения а; является решением непрерывной задачи поиска.
Выпуклые компакты М(и), U Є и, і = 0,..., JV, представляются в виде M{U) = {хе Rm\ {х,ф1) < с(М(и),ф%ф* Є }, где множества Фг С 5о (0), г = 0,..., N, являются компактами. Будем обозначать через с(А,ф) опорную функцию множества А в направление ф.
На основе выпуклого анализ получено следующее необходимое и достаточное условие, которому удовлетворяет кусочно-постоянное управление, решающее задачу поиска, если выполнение условия обнаружения проверяется в заданные фиксированные моменты времени tk, к = 0,..., N.
Теорема. Пусть задано кусочно-постоянное управление й(-): u(t) = йк Є U, t Є {tk-htk], к = 1,...,N. Тогда для каждой точки zq Є Zq и каждого допустимого v{-) существует момент времени t = t(zo,v(-)) є со такой, что K(t)z{t\t0,zQ,u(-),v{-))eM(t), тогда и только тогда, когда { N max min { c(Z0, У] а{тгТ(и)фг) - c(M(t0), а0ф) + \г=0,...Д/\ EUo«i=l / + N \ N
В% Y, осі^Ш ) + c(W, y <ьЛи)Р) - jf=l L \ i=j I i=j -c(Mfe),^) где множество Vk, k = 1,...,N, определяется через интеграл Аумана от многозначного отображения V(t)
I V(s)ds VK = и матрица
Вк= Г B{s)ds. Jtk-i
Применение метода динамического программирования приводит к рассмотрению конечной последовательности рекуррентно заданных функций
Щх, a) = max {c(Z0, a^T(to)ip + х) - c(M(t0), аф0)} , Rk(x, a) = max min {Rk-i(akirT(tk)ipk + x, -ak + a) + фкЄ-Ч!к акЄ[0,а] + (Вкйк, ак1ГТ(Ьк)фк + x) + c{Vk, ак7гТ{ік)фк + x)- -с(М(ік),акфк)}, k = l,...,N, где функция Rk(x, а) определена на множестве Dk С Rn x R1: Dk = co({Gk,0) U (0,1)), к = 0,...,N, Gfc_! = со(-ітт(ік)Ук U Gk), к = 1,..., N, GN = {0}.
Основной результат первой главы сформулирован в следующей теореме.
Теорема. (Необходимое и достаточное условие, которому удовлетворяет кусочно-постоянное управление, решающее задачу поиска, если условие обнаружения проверяется в заданные моменты времени, количество которых конечно)
Пусть задано кусочно-постоянное управление й(-): й(І) = йк Є U, t (tk-i,tk], к = 1,..., JV. Тогда для каждой точки г0 G ZQ и каждого допустимого v(-) существует момент времени t = t(zo,v(-)) є w такой, что v(t)z{t\t0,zQ,u(-),v(-))eM(t), тогда и только тогда, когда Rn(0, 1) < 0.
В первой главе исследованы свойства множеств Dk и функций Rk(x,a), k = 0,...,N, которые отражены в следующих леммах.
Лемма. Множество Dk, к = 0,...,iV, является выпуклым компактом.
Лемма. Функция Rk(x, а), к = О,..., N, является выпуклой на множестве Dk.
Лемма. Пусть (х, а) Є Dk> (Ах, Ха) Є Dk и X > О, тогда Rk(Xx,Xa) = XRk(x,a), k = 0,...,N.
Вторая глава работы посвящена задаче поиска в случае, когда динамика ищущего и прячущегося объектов является линейной и независимой и терминальное множество является двумерным выпуклым компактом.
В первой части второй главы рассматривается следующая динамика объектов S : х = и,
Н : y = Cy + Dv, где х Є R2, у Є RUH, u(t) Є U С R2 —управлениеобъекта 5, v(t) Є V С Rq — управление объекта Н. Здесь U — выпуклый компакт в пространстве R2 и У — выпуклый компакт в Rq.
В начальный момент времени t = to выполняются соотношения x(to) — хо, у (to) Є Yq, где хо — заданная точка и Уо — заданное выпуклое компактное множество в Rnfl.
Задача поиска объекта Я объектом S формулируется следующим образом: найти момент времени Ts и такое допустимое управление щ(-) на отрезке времени [t0, Ts], что для любой начальной точки уо є Y0 и для любого допустимого управления v(-) найдется момент времени t = t(y0, v(-)) Є [to, Ts], для которого выполнится условие обнаружения ппу(Цуо, v(-)) Є x(t\x0, щ(-)) + М, где М — заданное выпуклое компактное множество в R2 (терминальное множество) и 7г# Є R2xnjT — матрица ортогонального проектирования на R2.
Предлагается метод построения управления поиска. Основным инструментом является понятие области неопределенности, которая отражает состояние процесса поиска к данному моменту времени.
Определение. Областью неопределенности 0(Ци(-)) в момент времени Ї, отвечающей управлению и(-), называется множество концов траекторий у(Цуо, v(-)), для всех начальных точек уо Є Yq и всех допустимых управлений !>(), таких, что тг//у(і|їЛ),г;(-)) x(t\x0,u(-)) + М для всех і < t.
Из определения следует, что управление us(-) решает задачу поиска на отрезке Времени [t0, Та], ЄСЛИ
ВД«.(-)) = 0.
Вообще говоря, область неопределенности является невыпуклым несвязанным множеством. Предлагаемый алгоритм построения управления поиска позволяет описать динамику области неопределенности с помощью выпуклых множеств, которые, в свою очередь, эффективно описываются с помощью опорных функций.
Управление us(-) строится последовательно на отрезках времени [i_i,j] таким образом, чтобы соответствующая последовательность областей неопределенности в моменты U {Cl(UM-))} состояла из выпуклых множеств и для некоторого номера is стало верно соотношение 0(tie, щ(-)) = 0. Чтобы на некотором шаге выполнилось условие пустоты области неопределенности, нужно потребовать уменьшение множеств ti(U,us(-)), в некотором смысле, с каждым шагом. Например, под уменьшением области неопределенности 0(t") по сравнению с областью 0,(1/) можно понимать условие TrH0(t") + eS + yC7rH0(t').
Если это условие выполняется для некоторого є > є > 0 и некоторого у Є R2, то область неопределенности уменьшилась.
Построение следующего элемента последовательности областей неопределенности осуществляется следующим образом. Пусть 0(t') — элемент последовательности. Ищутся два выпуклых компакта в и W, удовлетворяющие следующим свойствам на отрезке времени [t', t"]:
1) В момент времени t' выполняется включение тгяЮ(0 С в + 2М. 14
2) Если irHy(t) Є Є + {t - t')W + 2М, то тгяЯя(тІ*, y{t)) С 0 + (т - f )W + 2М, где Г >tKt,T Є [i',t"].
3) Если тгяЗ/М Є в + (t - t')W, то nHRH{T\t,y(t))ce + (r-t')W, rn$T>tnt,T e[t',t"].
Здесь і?я(т|і,у(і)) — множество точек, куда в момент времени т может попасть прячущийся объект, если в момент времени t он находился в точке y(t). Условия 1, 2, 3 говорят о непроницаемости границы множеств 0 + {t — t')W+2M, Q + (t-t')W для прячущегося объекта, т.е. если прячущийся объект оказался внутри множества @ + (t-t')W+2M (аналогично Q + (t — t')W), то с течением времени он не сможет его покинуть. Таким образом, изменяющееся во времени множество (0 + {t - t')W + 2М) \ (0 + {t - t')W) образуют коридор, который ограничивают область неопределенности и при этом покрывает ее часть.
Согласно условию обнаружения, в момент времени t прячущийся объект является обнаруженным, если его положение y(t) удовлетворяет условию KHy(t)ex(t\x0,u{-)) + M.
Положение множества обнаружения x(t\x0, «()) + М определяется выбором управления и(-) ищущего объекта. В работе строится управление ищущего объекта, которое перемещает область обнаружения внутрь коридора, а затем осуществляет движение вдоль него, гарантируя обнаружение прячущего объекта, если он остается в коридоре. Управление, осуществляющее движение вдоль коридора, находится как решение задачи оптимального управления со смешанными ограничениями. После того, как гарантировано отсутствие прячущегося объекта в коридоре, получившаяся область неопределенности является следующим элементом в последовательности выпуклых областей неопределенности. При построении управления используется не опорная функция области неопределенности, которую в общем случае найти можно лишь приближенно, а опорные функции множеств в и W, которые находятся в аналитическом виде.
Предлагаемые конструкции, позволяют строить управления поиска в случае, когда поиск осуществляется несколькими ищущими объектами.
В качестве примера применения метода рассматривается задача поиска для случая, когда области управления ищущего и прячущегося объектов являются эллипсоидами. В этом случае все конструкции метода переписываются в терминах эллипсоидального исчисления, которое позволяет заменить теоретико-множественные операции аналитическими формулами.
Во второй части второй главы рассматривается простая динамика прячущегося объекта
Я: y = v} где у Є R2, v{t) Є V = сгВ^(О). Для такой динамика прячущегося объекта и заданной траектории x(t) ищущего объект описывается граница области неопределенности в виде параметрической кривой. Последовательность шагов поиска соответствует первой части. Отличие состоит в том, что управление выбирается таким, что осуществляет движение области обнаружения x(t)+M непосредственно вдоль границы области неопределенности, а не вдоль ограничивающего ее коридора. Осуществимость такого движения предполагает жесткие требования гладкости границы области неопределенности. Эти требования можно удовлетворить, расширив границу области неопределенности и при этом наделив ее нужными свойствами.
Третья глава работы посвящена нелинейной задаче поиска. В ней предлагаются конструкции, которые позволяют построить множества начальных позиций, для которых заданное управление ищущего объекта является управлением поиска.
Рассматривается управляемая динамическая система, которая описывается системой нелинейных дифференциальных уравнений z = f{z,u,v), где z Є Rn, u{t) Є U С Rp, v(t) Є V С Rq, множества U, V — компакты. В начальный момент времени точка z(0) Є Zq.
Задача поиска для заданного отрезка времени [0, в] формулируется следующим образом: найти такое допустимое управление щ(-) на отрезке времени [0, в], что для любой начальной точки zq Є Z0 и для любого допустимого управления v(-) найдется момент времени t — t(zQ, v(-)) Є [0, в], для которого выполнится терминальное условие z(t\z0,us{-),v{-))eM, где М — заданное замкнутое множество в пространстве Rn (не обязательно ограниченное).
Вспомогательные определения и утверждения
Никакой дополнительной информации о текущем положение динамической системы и стратегии, выбранной прячущимся объектом, во время процесса поиска не поступает. Другая, важная черта задач поиска состоит в том, что момент выполнения условия обнаружения не фиксирован. Таким образом, задачи поиска составляют отдельный класс задач управления.
Среди постановок задач динамического поиска можно выделить три основ- ных класса: стохастические, игровые и гарантированные задачи поиска. Данное деление определяется различным понимаем решения задачи.
Примером стохастической задачи поиска является задача, в которой априорно известна (или удовлетворяет заданным уравнениям) функция распределения вероятности выбора прячущимся объектом заданной стратегии из множества допустимых стратегий. Под решением задачи понимается допустимая стратегия ищущего объекта, максимизирующая некоторый функционал, который отражает эффективность стратегии поиска. Например, таким функционалом может быть вероятность выполнения условия обнаружения на заданном отрезке времени. Стохастические задачи поиска исследовались в работах В. И. Аркина, О. Хеллмана, В. А. Абчука, В. Г. Суздаля, Л. А. Петросяна, Л. А. Емельянова. Варианты постановок таких задач и подходы к их решению рассмотрены в [ 1,84].
В игровой постановке, задача поиска является игрой двух лиц с нулевой суммой (в случае одного ищущего игрока). В качестве функционала, который минимизирует ищущий и максимизирует прячущийся, часто рассматривают время прошедшее до момента выполнения условия обнаружения при выбранных стратегиях игроков. Под решением задачи понимается пара — стратегия ищущего и стратегия прячущегося игрока, — которые соответствуют седло-вой точке функционала. Как правило, в игровой задаче поиска решение ищут в смешанных стратегиях, т.е. находят вероятностные распределения на множествах допустимых стратегий игроков. Игровые задачи поиска рассматривали: Р. Айзеке [3], Л. А. Петросян, Н. А. Зенкевич, А. Ю. Гарнаев, М. И. Зели-кин, S. Gal, В. О. Koopman. Варианты постановок игровых задач рассмотрены в [60].
Задачу гарантированного поиска рассматривают в различных постановках, в зависимости от предположений о динамики прячущегося объекта. Так рассматривают задачи о поиске неподвижного объекта, о поиске объекта с заданным параметрическим семейством возможных траекторий, о поиске управляемого (другим лицом) объекта. Под решением задачи понимается допустимая стратегия ищущего объекта, обеспечивающая выполнение условия обнаружения при любой допустимой стратегии прячущегося объекта. Гарантированный поиск рассмотрен в работах Ф. Л. Черноусько, Л. А. Петросяна, В. В. Ски-товича, С. В. Чистякова, А. Ю. Гарнаева, Н. А. Зенкевича, О. А. Малафеева, Д. П. Кима, Е. В. Шикина, С. М. Губайдуллина, А. Г. Чхартишвили, С. Б. Березина, П. М. Ларина, А. А. Скворцова, С. В. Местникова.
Задача гарантированного поиска неподвижного объекта предполагает, что прячущийся объект в начальный момент времени выбирает точку своего положения из заданного множества и остается в этой точке в течение всего процесса поиска. Ищущий объект должен выбрать такую траекторию движения, чтобы гарантировать выполнение условия обнаружения для любой точки множества возможных положений прячущегося объекта. Следующей задачей гарантированного поиска является задача, когда прячущийся объект подвижен и выбирает траекторию своего движения из заданного параметрического семейства кривых. Соответственно, ищущий объект должен выбрать такую траекторию движения, чтобы гарантировать выполнение условия обнаружения для любой возможной кривой движения прячущегося объекта. В работах В. В. Скитовича и С. В. Чистякова [78] предложен метод, который позволяет свести эту задачу к задаче поиска неподвижного объекта.
Необходимое и достаточное условие решения дискретной задачи поиска
Задача поиска управляемого прячущегося объекта предполагает, что прячущийся объект выбирает допустимое программное управление, которое порождает его траекторию движения. Ищущий объект не обладает информацией о сделанном выборе. Он должен выбрать свою траекторию движения, гарантирующую выполнение условия обнаружения для любой допустимой траектории прячущегося объекта. Этой задаче гарантированно поиска в предположении, что динамика ищущего и прячущегося объектов является простой, посвящен целый ряд работ. В работах Ф. Л. Черноусько [85] рассмотрена задача поиска в двумерном и трехмерном пространстве, когда прячущийся объект может перемещаться только в пределах заданной области. Большая серия работ написана Е. В. Шикиным [86] и его учениками А. Г. Чхартишвили, С. Б. Бере-зиным [87], П. М. Лариным [43], А. А. Скворцовым [77], в которых исследуется задача поиска на некотором классе поверхностей, в двухмерных и трехмерных областях, приводятся достаточные условия существования и численные методы построения траекторий поиска. Основной инструмент этих исследований — анализ области неопределенности, т.е. множества точек, где может находиться прячущийся объект в определенный момент времени. Метод аппроксимации области неопределенности для сложной динамики ищущего и прячущегося объектов рассмотрен в работах СВ. Местникова [49].
В данной работе рассматривается задача гарантированного поиска управляемого прячущегося объекта, которая в общем виде формулируется следующий образом. Динамика системы описывается системой обыкновенных дифференциальных уравнений z = f{t,z,u,v). (1) Функция и = u(t) — программное управление, которое требуется выбрать из заданного множества допустимых управлений U, в соответствии с заданной целью. Функция v = v(t) — неизвестное возмущение, которое может воз никнуть в системе, причем известно множество возможных возмущений V. В начальный момент времени t = tQ положение системы определено неточно. Известно, что начальная точка z{to) принадлежит заданному множеству ZQ. Обозначим решение дифференциального уравнения (1) к моменту времени t с начальной точкой z(to) = z0 и функциями и(-), v(-) через z(t\to, ZQ, U(-), V(-)). Задачу гарантированного динамического поиска сформулируем следующим образом: найти момент времени Ts и найти такое допустимое управление us(-) Є U, что для каждой начальной точки ZQ Є ZQ и для каждого возможного возмущения v(-) Є V найдется момент времени t = t(z0)v(-)) [to,Ts], ддя которого выполнится терминальное условие (условие обнаружения) п(1)г(Що,го,и,(-)А-)) Є Af, (2) где 7г(і) — матричная функция и M(t) — многозначное отображение, заданные на отрезке времени [to, Ts).
Отметим, что в соответствии с поставленной задачей, требуется найти такое программное управление us{-) Є К, до начала движение системы, которое обеспечит выполнение терминального условия (2), каким бы ни оказалось начальное положение системы z{to) є ZQ И какое бы допустимое возмущение г;(-) Є V ни возникло в системе. Причем момент выполнение терминального условия не фиксирован и, вообще говоря, зависит от пары (z(to),v(-)). Выбор управления и3(-) определяется только дифференциальным уравнением (1), множествами Z0, U, V, матричной функцией 7г(і) и многозначным отображением М(і). Частным является случай, когда динамическая система распадается на две независимые части (x = g(t,x,u), \ y = h(t,y,v). В начальный момент времени t = to для начальной точки x(to) выполняется равенство x(t0) = хо, а для начальной точки y(tQ) известно только то, что выполняется включение у(t0) Є Y0, где Уо — заданное множество. Движение вектора x(t) определяется заданной начальной точкой xfo) = хо и выбранной функцией и(-) Є U и не зависит от неизвестной функции v(-). Будем считать, что вектор x(t) описывает положение некоторого, управля емого нами, объекта, которого обозначим буквой S. Аналогично, движение вектора y(t), определяемое начальной точкой y(t0) Є YQ И функцией v(-) Є V и не зависящее от функции и(-), определяет движение другого объекта, которого обозначим буквой Я. Движение объекта Я не контролируемо нами и, более того, не известно, так как не известны ни начальная точка у (to), ни функция v(-).
Вспомогательные определения и утверждения
Задача (3), (4) допускает следующую геометрическую интерпретацию. В начальный момент времени to объект Я находится в некоторой точке y(to) YQ. Затем он начинает движение с некоторым допустимым управлением v(-) є V. Объект 5 в начальный момент времени находится в заданной точке x(to) = XQ. Он не знает точного значения у (to), не знает выбранного управления v(-) и не получает никакой информации о траектории y(t) движения объекта Я. Цель объекта S заключается в выборе управления us(-) U, обеспечивающее выполнение терминального условия (4) для любой возможной пары (y(to),v(-)) Є YQ х V. Или, другими-словами, объект S выбирает управление щ(-) так, чтобы найти движущийся объект Я, если условием обнаружения объекта Я является включение (4). Такая геометрическая интерпретация описанной задачи объясняет название работы. Будем называть объект S — ищущим, объект Н — прячущимся, управление и(-) — управлением ищущего объекта, управление v(-) —управлением прячущегося объекта, управление и3(-), решающее задачу, — управлением поиска.
В традиционной постановке задач поиска динамика ищущего и прячущегося объектов считается независимой друг от друга. В работе сформулирована и исследуется более общая задача (в первой и третьей главе), когда динамику объектов нельзя разделить на независимые части. Постановка задачи формулируется как задача управления в условиях неопределенности в классе программных управлений. Подходы к решению задач управления в условиях неопределенности в классе программных управлений в случае, когда момент времени прихода на целевое множества задан, исследовались А. Б. Куржан-ским [38], В. В. Скитовичем, С. В. Чистяковым и др. В задаче поиска момент времени прихода на целевое множество (т.е. выполнения условия обнаружения) не фиксирован. Методы решения таких задач нуждаются в дальнейшем развитии.
Вторая задача, которая рассматривается в работе и связана с задачей гарантированного поиска, заключается в построении множества начальных точек ZQ, для которых заданное управление и(-) на заданном отрезке времени [to,T] является управлением поиска.
Эта задача пересекается с задачей построения множества начальных позиций разрешимости задачи преследования в нелинейных нестационарных дифференциальных играх. Подход к построению множества начальных позиций в дифференциальных играх основан на понятии стабильного моста, введенного в работах Н. Н. Красовского и А. И. Субботина [35]. Методы построения стабильных мостов исследовались в работах Н. Н. Красовского, А. И. Субботина, Б. Н. Пшеничного [72], В. В. Остапенко, В. Н. Ушакова [82], А. А. Успенского, Т. Б. Токманцева, А. М. Тарасьева, В. С. Пацко, А. А. Меликяна, Е. С. Половинкина.
При применении подобного подхода к задачам поиска необходимо учитывать, что нестационарность задачи поиска возникает в результате подстановки в правую часть дифференциального уравнения управляющей функции. Краткое содержание работы. В первой главе рассматривается задача поиска для линейной нестационарной системы z = B(t)u + v на заданном отрезке времени [to, Т), где вектор z є Rn, u(t) eU,U — выпуклый компакт в пространстве Rp, v(t) Є V(t), V(t) —измеримое ограниченное многозначное отображение отрезка [to,T] во множество непустых выпуклых компактов пространства R9, элементы матрицы B(t) — непрерывные функции на отрезке [to,T]. Такая система включает в себя как частный случай линейную систему z = A(t)z + B{t)u + C(t)v, где вектор z Є Rn, u(t) Є U, U — выпуклый компакт в пространстве Кр, v(t) Є V, V — выпуклый компакт в пространстве R9. Элементы матриц A(t) Є Rnxn, B(t) Є Rnxp, C(t) Rnxq — непрерывные функции на отрезке [to, П. Пусть задано непрерывное многозначное отображение M(t) на отрезке [to,T] во множество непустых выпуклых компактов пространства Rm, матрица 7г() є Rmxn с непрерывными элементами на отрезке [t0,T] и выпуклый компакт ZQ В пространстве Rn.
Вспомогательные определения и утверждения
Задача гарантированного динамического поиска формулируется следующим образом: найти такое допустимое управление us(t) на отрезке времени [to,T], что для каждой точки z0 ZQ И каждого допустимого v(-) существует момент времени t = t(zo, v(-)) Є [to, Т], для которого выполняется терминальное условие K{t)z{t\t0, ZQ, US{-), V(-)) Є М(ї). Сформулированная задача называется непрерывной задачей поиска. Совместно с непрерывной рассматривается дискретная задача. Зафиксируем произвольное конечное разбиение отрезка [to, Т] UJ = {to,t\,... ,ttf}, где ti-i U для і = 1,..., N и tju = Т. Дискретная задача поиска для заданного разбиения ui формулируется следующим образом. Найти такое допустимое кусочно-постоянное управление uf(t) = щ для t Є (U-u U], і — 1, N что для каждой точки ZQ Є ZQ И каждого допустимого v{-) существует момент времени t = t(zo, v(-)) Є UJ, для которого выполняется условие Tt{t)z(t\t0,z0,us{-),v{-)) Є M(t). Решение дискретной задачи поиска й(-) для любого конечного разбиения а; является решением непрерывной задачи поиска. Выпуклые компакты М(и), U Є и, і = 0,..., JV, представляются в виде M{U) = {хе Rm\ {х,ф1) с(М(и),ф%ф Є }, где множества Фг С 5о (0), г = 0,..., N, являются компактами. Будем обозначать через с(А,ф) опорную функцию множества А в направление ф. На основе выпуклого анализ получено следующее необходимое и достаточное условие, которому удовлетворяет кусочно-постоянное управление, решающее задачу поиска, если выполнение условия обнаружения проверяется в заданные фиксированные моменты времени tk, к = 0,..., N. Теорема. Пусть задано кусочно-постоянное управление й(-): u(t) = йк Є U, t Є {tk-htk], к = 1,...,N. Тогда для каждой точки ZQ Є ZQ и каждого допустимого v{-) существует момент времени t = t(zo,v(-)) є со такой, что K(t)z{t\t0,zQ,u(-),v{-))eM(t), тогда и только тогда, когда { N max min { c(Z0, У] а{тгТ(и)фг) - c(M(t0), а0ф) + i=0 \г=0,...Д/\ EUo«i=l / + JV. N \ N В% Y, ОСІ Ш ) + c(W, Y ьЛи)Р) jf=l L \ i=j I i=j -c(Mfe), ) o, где множество Vk, k = 1,...,N, определяется через интеграл Аумана от многозначного отображения V(t) I V(s)ds VK = и матрица Вк= Г B{s)ds. Jtk-i Пусть задано кусочно-постоянное управление й(-): й(І) = йк Є U, t (tk-i,tk], к = 1,..., JV. Тогда для каждой точки г0 G ZQ и каждого допустимого v(-) существует момент времени t = t(zo,v(-)) є w такой, что v(t)z{t\t0,zQ,u(-),v(-))eM(t), тогда и только тогда, когда RN(0, 1) 0. В первой главе исследованы свойства множеств Dk и функций Rk(x,a), k = 0,...,N, которые отражены в следующих леммах. Лемма. Множество Dk, к = 0,...,iV, является выпуклым компактом. Лемма. Функция Rk(x, а), к = О,..., N, является выпуклой на множестве Dk. Лемма. Пусть (х, а) Є Dk (Ах, Ха) Є Dk и X О, тогда Rk(Xx,Xa) = XRk(x,a), k = 0,...,N.
Вторая глава работы посвящена задаче поиска в случае, когда динамика ищущего и прячущегося объектов является линейной и независимой и терминальное множество является двумерным выпуклым компактом. В первой части второй главы рассматривается следующая динамика объектов S : х = и, Н : y = Cy + Dv, где х Є R2, у Є RUH, u(t) Є U С R2 —управлениеобъекта 5, v(t) Є V С Rq — управление объекта Н. Здесь U — выпуклый компакт в пространстве R2 и У — выпуклый компакт в Rq. В начальный момент времени t = to выполняются соотношения x(to) — хо, у (to) Є YQ, где хо — заданная точка и Уо — заданное выпуклое компактное множество в Rnfl. Задача поиска объекта Я объектом S формулируется следующим образом: найти момент времени Ts и такое допустимое управление щ(-) на отрезке времени [t0, Ts], что для любой начальной точки уо є Y0 и для любого допустимого управления v(-) найдется момент времени t = t(y0, v(-)) Є [to, Ts], для которого выполнится условие обнаружения ппу(Цуо, v(-)) Є x(t\x0, щ(-)) + М, где М — заданное выпуклое компактное множество в R2 (терминальное множество) и 7г# Є R2xnjT — матрица ортогонального проектирования на R2. Предлагается метод построения управления поиска. Основным инструментом является понятие области неопределенности, которая отражает состояние процесса поиска к данному моменту времени. Определение. Областью неопределенности 0(Ци(-)) в момент времени Ї, отвечающей управлению и(-), называется множество концов траекторий у(Цуо, v(-)), для всех начальных точек уо Є YQ И всех допустимых управлений ! (), таких, что тг//у(іїЛ),г;(-)) x(t\x0,u(-)) + М для всех і t. Из определения следует, что управление us(-) решает задачу поиска на отрезке Времени [t0, Та], ЄСЛИ ВД«.(-)) = 0. Вообще говоря, область неопределенности является невыпуклым несвязанным множеством. Предлагаемый алгоритм построения управления поиска позволяет описать динамику области неопределенности с помощью выпуклых множеств, которые, в свою очередь, эффективно описываются с помощью опорных функций.
Управление us(-) строится последовательно на отрезках времени [i_i,j] таким образом, чтобы соответствующая последовательность областей неопределенности в моменты U {Cl(UM-))} состояла из выпуклых множеств и для некоторого номера is стало верно соотношение 0(tie, щ(-)) = 0. Чтобы на некотором шаге выполнилось условие пустоты области неопределенности, нужно потребовать уменьшение множеств ti(U,us(-)), в некотором смысле, с каждым шагом. Например, под уменьшением области неопределенности 0(t") по сравнению с областью 0,(1/) можно понимать условие TrH0(t") + eS + yC7rH0(t ).
