Задача гарантированного динамического поиска

Работа посвящена одной из задач гарантированного управления динамической системой в условия неопределенности — задаче гарантированного динамического поиска.

В литературе рассматриваются различные постановки задач динамического поиска. Большинство из них характеризуются следующими понятиями: динамическая система, описывающая процесс поиска, множество допустимых стратегий ищущего объекта, множество допустимых стратегий прячущегося объекта и условие, выполнение которого означает обнаружение прячущегося объекта ищущим. Цель ищущего объекта, при выборе своей стратегии, — обеспечить выполнение условия обнаружения, цель прячущегося объекта — избежать выполнения условия обнаружения. Задачи поиска характеризуются тем, что ищущий объект при выборе своей стратегии обладает только априорно известной до начала процесса поиска информацией, такой как множество возможных стратегий прячущего объекта и множество возможных начальных положений системы. Никакой дополнительной информации о текущем положение динамической системы и стратегии, выбранной прячущимся объектом, во время процесса поиска не поступает. Другая, важная черта задач поиска состоит в том, что момент выполнения условия обнаружения не фиксирован. Таким образом, задачи поиска составляют отдельный класс задач управления.

Среди постановок задач динамического поиска можно выделить три основ-' ных класса: стохастические, игровые и гарантированные задачи поиска. Данное деление определяется различным понимаем решения задачи.

Примером стохастической задачи поиска является задача, в которой априорно известна (или удовлетворяет заданным уравнениям) функция распределения вероятности выбора прячущимся объектом заданной стратегии из множества допустимых стратегий. Под решением задачи понимается допустимая стратегия ищущего объекта, максимизирующая некоторый функционал, который отражает эффективность стратегии поиска. Например, таким функционалом может быть вероятность выполнения условия обнаружения на заданном отрезке времени. Стохастические задачи поиска исследовались в работах В. И. Аркина, О. Хеллмана, В. А. Абчука, В. Г. Суздаля, Л. А. Петросяна,.

JI. А. Емельянова. Варианты постановок таких задач и подходы к их решению рассмотрены в [ 1,84].

В игровой постановке, задача поиска является игрой двух лиц с нулевой суммой (в случае одного ищущего игрока). В качестве функционала, который минимизирует ищущий и максимизирует прячущийся, часто рассматривают время прошедшее до момента выполнения условия обнаружения при выбранных стратегиях игроков. Под решением задачи понимается пара — стратегия ищущего и стратегия прячущегося игрока, — которые соответствуют седло-вой точке функционала. Как правило, в игровой задаче поиска решение ищут в смешанных стратегиях, т. е. находят вероятностные распределения на множествах допустимых стратегий игроков. Игровые задачи поиска рассматривали: Р. Айзеке [3], JI. А. Петросян, Н. А. Зенкевич, А. Ю. Гарнаев, М. И. Зели-кин, S. Gal, В. О. Кооршап. Варианты постановок игровых задач рассмотрены в [60].

Задачу гарантированного поиска рассматривают в различных постановках, в зависимости от предположений о динамики прячущегося объекта. Так рассматривают задачи о поиске неподвижного объекта, о поиске объекта с заданным параметрическим семейством возможных траекторий, о поиске управляемого (другим лицом) объекта. Под решением задачи понимается допустимая стратегия ищущего объекта, обеспечивающая выполнение условия обнаружения при любой допустимой стратегии прячущегося объекта. Гарантированный поиск рассмотрен в работах Ф. JT. Черноусько, Л. А. Петросяна, В. В. Ски-товича, С. В. Чистякова, А. Ю. Гарнаева, Н. А. Зенкевича, О. А. Малафеева, Д. П. Кима, Е. В. Шикина, С. М. Губайдуллина, А. Г. Чхартишвили, С. Б. Березина, П. М. Ларина, А. А. Скворцова, С. В. Местникова.

Задача гарантированного поиска неподвижного объекта предполагает, что прячущийся объект в начальный момент времени выбирает точку своего положения из заданного множества и остается в этой точке в течение всего процесса поиска. Ищущий объект должен выбрать такую траекторию движения, чтобы гарантировать выполнение условия обнаружения для любой точки множества возможных положений прячущегося объекта. Следующей задачей гарантированного поиска является задача, когда прячущийся объект подвижен и выбирает траекторию своего движения из заданного параметрического семейства кривых. Соответственно, ищущий объект должен выбрать такую траекторию движения, чтобы гарантировать выполнение условия обнаружения для любой возможной кривой движения прячущегося объекта. В работах В. В. Скитовича и С. В. Чистякова [78] предложен метод, который позволяет свести эту задачу к задаче поиска неподвижного объекта.

Задача поиска управляемого прячущегося объекта предполагает, что прячущийся объект выбирает допустимое программное управление, которое порождает его траекторию движения. Ищущий объект не обладает информацией о сделанном выборе. Он должен выбрать свою траекторию движения, гарантирующую выполнение условия обнаружения для любой допустимой траектории прячущегося объекта. Этой задаче гарантированно поиска в предположении, что динамика ищущего и прячущегося объектов является простой, посвящен целый ряд работ. В работах Ф. Л. Черноусько [85] рассмотрена задача поиска в двумерном и трехмерном пространстве, когда прячущийся объект может перемещаться только в пределах заданной области. Большая серия работ написана Е. В. Шикиным [86] и его учениками А. Г. Чхартишвили, С. Б. Бере-зиным [87], П. М. Лариным [43], А. А. Скворцовым [77], в которых исследуется задача поиска на некотором классе поверхностей, в двухмерных и трехмерных областях, приводятся достаточные условия существования и численные методы построения траекторий поиска. Основной инструмент этих исследований — анализ области неопределенности, т. е. множества точек, где может находиться прячущийся объект в определенный момент времени. Метод аппроксимации области неопределенности для сложной динамики ищущего и прячущегося объектов рассмотрен в работах С. В. Местникова [49].

В данной работе рассматривается задача гарантированного поиска управляемого прячущегося объекта, которая в общем виде формулируется следующий образом. Динамика системы описывается системой обыкновенных дифференциальных уравнений z = f{t, z, u, v). (1).

Функция и = u (t) — программное управление, которое требуется выбрать из заданного множества допустимых управлений U, в соответствии с заданной целью. Функция v = v (t) — неизвестное возмущение, которое может возникнуть в системе, причем известно множество возможных возмущений V. В начальный момент времени t = t0 положение системы определено неточно. Известно, что начальная точка z (to) принадлежит заданному множеству Z0. Обозначим решение дифференциального уравнения (1) к моменту времени t с начальной точкой z (to) = z0 и функциями и (-), v (-) через z (tto, zq, u (-), v (-)).

Задачу гарантированного динамического поиска сформулируем следующим образом: найти момент времени Ts и найти такое допустимое управление us (-) е U, что для каждой начальной точки zq е Zq и для каждого возможного возмущения v (-) € V найдется момент времени t = t (z0)v (-)) е [to, Ts], для которого выполнится терминальное условие (условие обнаружения).

K{t)z (ttQ, z0, us{-), v{-)) е М{1), (2) где 7 г (t) — матричная функция и M (t) — многозначное отображение, заданные на отрезке времени [?<), Ts].

Отметим, что в соответствии с поставленной задачей, требуется найти такое программное управление us (-) е К, до начала движение системы, которое обеспечит выполнение терминального условия (2), каким бы ни оказалось начальное положение системы z (t0) е Z0 и какое бы допустимое возмущение v (-)? V ни возникло в системе. Причем момент выполнение терминального условия не фиксирован и, вообще говоря, зависит от пары (z (to), v (-)). Выбор управления и3(-) определяется только дифференциальным уравнением (1), множествами Z0, U, V, матричной функцией 7 г (t) и многозначным отображением M (t).

Частным является случай, когда динамическая система распадается на две независимые части x = g (t, x, u), ^ V = h{t, y, v).

В начальный момент времени t = to для начальной точки x (to) выполняется равенство x (t0) = xq, а для начальной точки y (tQ) известно только то, что выполняется включение у (to) € Y0, где Уо — заданное множество.

Движение вектора x (t) определяется заданной начальной точкой x (to) = хо и выбранной функцией и (-) е U и не зависит от неизвестной функции v (-). Будем считать, что вектор x (t) описывает положение некоторого, управляемого нами, объекта, которого обозначим буквой S. Аналогично, движение вектора y (t), определяемое начальной точкой y (t0) е Yq и функцией v (-)? V и не зависящее от функции и (-), определяет движение другого объекта, которого обозначим буквой Я. Движение объекта Я не контролируемо нами и, более того, не известно, так как не известны ни начальная точка у (to), ни функция v (-).

В этом случае, задачу гарантированного динамического поиска сформулируем следующим образом: найти момент времени Ts и найти такое допустимое управление щ (-) еЫ, что для каждой начальной точки у0 е Y0 и для каждого возможного возмущения v (-) е V найдется момент времени t = t (yQ, v (-)) е [£о, Ts], для которого выполнится терминальное условие где 7Гя (£), -кsit) — матричные функции и M{t) — многозначное отображение, заданные на отрезке времени [to, Ts]. Описанный частный случай сводится к общей задаче (1), (2), если положить.

Задача (3), (4) допускает следующую геометрическую интерпретацию. В начальный момент времени to объект Н находится в некоторой точке y (to) € У0. Затем он начинает движение с некоторым допустимым управлением v (-) € V. Объект 5 в начальный момент времени находится в заданной точке x (to) = яо. Он не знает точного значения у (to), не знает выбранного управления v (-) и не получает никакой информации о траектории y (t) движения объекта Я. Цель объекта S заключается в выборе управления us (-) € Ы, обеспечивающее выполнение терминального условия (4) для любой возможной пары (y (to), v (-)) € Уо х V. Или, другими-словами, объект S выбирает управление щ (-) так, чтобы найти движущийся объект Я, если условием обнаружения объекта Я является включение (4). Такая геометрическая интерпретация описанной задачи объясняет название работы. Будем называть объект S —.

7Гн (Ы**0, Уо, О) е KS (t)x (it0, х0, щ (-)) + M (t),.

4).

K (t) = (-*s (t), KH (t)). ищущим, объект Н — прячущимся, управление и (-) — управлением ищущего объекта, управление v (-) —управлением прячущегося объекта, управление и3(-), решающее задачу, — управлением поиска.

В традиционной постановке задач поиска динамика ищущего и прячущегося объектов считается независимой друг от друга. В работе сформулирована и исследуется более общая задача (в первой и третьей главе), когда динамику объектов нельзя разделить на независимые части. Постановка задачи формулируется как задача управления в условиях неопределенности в классе программных управлений. Подходы к решению задач управления в условиях неопределенности в классе программных управлений в случае, когда момент времени прихода на целевое множества задан, исследовались А. Б. Куржан-ским [38], В. В. Скитовичем, С. В. Чистяковым и др. В задаче поиска момент времени прихода на целевое множество (т.е. выполнения условия обнаружения) не фиксирован. Методы решения таких задач нуждаются в дальнейшем развитии.

Вторая задача, которая рассматривается в работе и связана с задачей гарантированного поиска, заключается в построении множества начальных точек Z0, для которых заданное управление и (-) на заданном отрезке времени [to, T] является управлением поиска.

Эта задача пересекается с задачей построения множества начальных позиций разрешимости задачи преследования в нелинейных нестационарных дифференциальных играх. Подход к построению множества начальных позиций в дифференциальных играх основан на понятии стабильного моста, введенного в работах Н. Н. Красовского и А. И. Субботина [35]. Методы построения стабильных мостов исследовались в работах Н. Н. Красовского, А. И. Субботина, Б. Н. Пшеничного [72], В. В. Остапенко, В. Н. Ушакова [82], А. А. Успенского, Т. Б. Токманцева, А. М. Тарасьева, В. С. Пацко, А. А. Меликяна, Е. С. Половинкина.

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

Краткое содержание работы.

В первой главе рассматривается задача поиска для линейной нестационарной системы z = B (t)u + v на заданном отрезке времени [to, Т], где вектор zgR", 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 G R", u (t) € U, U — выпуклый компакт в пространстве Rp, v (t)? V, V — выпуклый компакт в пространстве R9. Элементы матриц A (t) в Rnxr B (t) € Rnxp, C (t) е Rnx, J — непрерывные функции на отрезке to, П.

Пусть задано непрерывное многозначное отображение M (t) на отрезке [U, T] во множество непустых выпуклых компактов пространства Rm, матрица 7 г (t) е Rmxn с непрерывными элементами на отрезке [t0,T] и выпуклый компакт Z0 в пространстве Rn.

Задача гарантированного динамического поиска формулируется следующим образом: найти такое допустимое управление us (t) на отрезке времени [to, T], что для каждой точки zq € Zq и каждого допустимого v (-) существует момент времени t = t (zo, v (-)) € [to, T], для которого выполняется терминальное условие.

K{t)z{tto, zQ, us{-), v (-)) € M (T).

Сформулированная задача называется непрерывной задачей поиска. Совместно с непрерывной рассматривается дискретная задача. Зафиксируем произвольное конечное разбиение отрезка [to, Т] и = {Ml, • • •, tjv}, где ti-1 < U для г = 1,., N и t^ = Т. Дискретная задача поиска для заданного разбиения и формулируется следующим образом. Найти такое допустимое кусочно-постоянное управление uf (t) = щ для t е t{], г = 1,., N, что для каждой точки zq б Zq и каждого допустимого v{-) существует момент времени t = i (zQ, v (-))? и, для которого выполняется условие.

Tr{t)z (ito, zo, us{-), v{-)) е M (t).

Решение дискретной задачи поиска для любого конечного разбиения аявляется решением непрерывной задачи поиска.

Выпуклые компакты M (ti), tj? и, i = 0,., N, представляются в виде.

M{U) = {хе Rm| < с (М (и), ф%ф* е Ф<}, где множества Фг С б^ДО), г = 0,., N, являются компактами. Будем обозначать через с (А, ф) опорную функцию множества, А в направление ф.

На основе выпуклого анализ получено следующее необходимое и достаточное условие, которому удовлетворяет кусочно-постоянное управление, решающее задачу поиска, если выполнение условия обнаружения проверяется в заданные фиксированные моменты времени tk, к = 0,., N.

Теорема. Пусть задано кусочно-постоянное управление й (-): u (t) = tik? U, t? {tk~i, tk, к = 1 ,., N. Тогда для каждой точки zq? Zq и каждого допустимого v{-) существует момент времени t = t (zQ, v (-))? и такой, что ir (t)z{it0,zQ, u (-), v{-))eM (t), тогда и только тогда, когда f N max min { c (Z0, У] а{тгТ (и)фг) — c (M (t0), аоФ°) + г=0,.Д/ / n ?

5=1 i=0 n n.

В% Y, ОСг-КТШ) + с (V, i=j / i=j.

0, где множество Vk, k = 1,., N, определяется через интеграл Аумана от многозначного отображения V (t).

— tk.

VK = f t к V (s)ds Jtk-i и матрица.

Вк= Г B (s)ds. Jtk-i.

Применение метода динамического программирования приводит к рассмотрению конечной последовательности рекуррентно заданных функций.

Ro (x, а) = max {c (Z0, атт.

Rk (x, а) = max min {Rk-i (akirT (tk)if)k + х, -ак + а) + ¦фке-Ч>к аке[0,а] (Вкйк, ак1гт (Ьк)фк + х} + c{Vk, актгтЦк) фк + х) c (M (tk), акфк)}, к = 1,., N, где функция Rk (x, а) определена на множестве Dk С Rn х R1:

Dk = co ({Gk, 0) U (0,1)), k = 0,., N, Gk. i = со (-тгт (**)Ф* U Gk), fc = l,., JV, Gn = {0}.

Основной результат первой главы сформулирован в следующей теореме. Теорема. (Необходимое и достаточное условие, которому удовлетворяет кусочно-постоянное управление, решающее задачу поиска, если условие обнаружения проверяется в заданные моменты времени, количество которых конечно).

Пусть задано кусочно-постоянное управление й (-): u (t) = йк 6 U, t € (tk-i, tk], к = 1 Тогда для каждой точки z0 в Z0 и каждого допустимого v (-) существует момент времени t — t (zo, v (-)) е со такой, что тогда и только тогда, когда /?дг (0,1) < 0.

В первой главе исследованы свойства множеств Dk и функций Rk (x, a), k = 0,., N, которые отражены в следующих леммах.

Лемма. Множество Dk) к = Оявляется выпуклым компактом.

Лемма. Функция Rk (x, а), к = О,., N, является выпуклой на множестве Dk.

Лемма. Пусть (х, а) е Dk, (Ах, Ха)? Dk и X > О, тогда.

Rk (Xx, Xa) = XRk (x, a), k = 0,., N.

Вторая глава работы посвящена задаче поиска в случае, когда динамика ищущего и прячущегося объектов является линейной и независимой и терминальное множество является двумерным выпуклым компактом.

В первой части второй главы рассматривается следующая динамика объектов.

S: х = и, Н: y = Cy + Dv, где х G R2, у G R" H, u (t) в U С R2 — управление объекта 5, v (t) € V С Rq — управление объекта Н. Здесь U — выпуклый компакт в пространстве R2 и У — выпуклый компакт в Rq. •.

В начальный момент времени t = to выполняются соотношения x (to) — хо, у (to) е Yq, где хо — заданная точка и Уо — заданное выпуклое компактное множество в Кпн.

Задача поиска объекта Я объектом S формулируется следующим образом: найти момент времени Ts и такое допустимое управление щ (-) на отрезке времени [?0, Т8], что для любой начальной точки уо е Y0 и для любого допустимого управления v (-) найдется момент времени t = t (y0, v (-)) в [£о> Ts], для которого выполнится условие обнаружения ппу (Цуо, v (-)) € ХШХо, w"(0) + К где М — заданное выпуклое компактное множество в R2 (терминальное множество) и 7г# € R2xnjT — матрица ортогонального проектирования на R2.

Предлагается метод построения управления поиска. Основным инструментом является понятие области неопределенности, которая отражает состояние процесса поиска к данному моменту времени.

Определение. Областью неопределенности в момент времени t, отвечающей управлению и (-), называется множество концов траекторий у (Цуо, v{-)), для всех начальных точек уо € Уо и всех допустимых управлений i>(-), таких, что Kny (tyo, v (-))? x (tx0,u (-)) + М для всех t.

Из определения следует, что управление us (-) решает задачу поиска на отрезке времени [t0, Та], если.

0(Tsus (-)) = 0. .

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

Управление щ (-) строится последовательно на отрезках времени [U-i, ti] таким образом, чтобы соответствующая последовательность областей неопределенности в моменты U.

0(U, us ('))} состояла из выпуклых множеств и для некоторого номера is стало верно соотношение 0(tie, щ (-)) = 0. Чтобы на некотором шаге выполнилось условие пустоты области неопределенности, нужно потребовать уменьшение множеств в некотором смысле, с каждым шагом. Например, под уменьшением области неопределенности Гl (t") по сравнению с областью 0,(1?) можно понимать условие.

KH0(t") + ?S + yC7rH0(t').

Если это условие выполняется для некоторого г > е > 0 и некоторого у € R2, то область неопределенности уменьшилась.

Построение следующего элемента последовательности областей неопределенности осуществляется следующим образом. Пусть 0(t') — элемент последовательности. Ищутся два выпуклых компакта © и И^, удовлетворяющие следующим свойствам на отрезке времени [t', t" ]:

1) В момент времени t' выполняется включение тгH0(t') С в + 2 М. 14.

2) Если 7rHy (t) ев+ {tt')W + 2M, то тгHRH{rt, y{t)) С 0 + (т — t')W + 2 М, где т > t и t, r G.

3) Если 7Гну (Ь) eQ + (tt')W, то nHRH{Tt, y (t))cQ + (T-t')W, щет > tnt, r e[t', t" ].

Здесь RH{rt, y (t)) — множество точек, куда в момент времени т может попасть прячущийся объект, если в момент времени t он находился в точке y (t). Условия 1, 2, 3 говорят о непроницаемости границы множеств © + {t — t')W+2M, Q + (t-t')W для прячущегося объекта, т. е. если прячущийся объект оказался внутри множества @ + (t-t')W+2M (аналогично 0 + (t-t')W), то с течением времени он не сможет его покинуть. Таким образом, изменяющееся во времени множество в + {t — t')W + 2М) (Q + (tt')W) образуют коридор, который ограничивают область неопределенности и при этом покрывает ее часть.

Согласно условию обнаружения, в момент времени t прячущийся объект является обнаруженным, если его положение y (t) удовлетворяет условию.

KHy (t)ex (tx0,u{-)) + M.

Положение множества обнаружения x (tx0, и (-)) + М определяется выбором управления и (-) ищущего объекта. В работе строится управление ищущего объекта, которое перемещает область обнаружения внутрь коридора, а затем осуществляет движение вдоль него, гарантируя обнаружение прячущего объекта, если он остается в коридоре. Управление, осуществляющее движение вдоль коридора, находится как решение задачи оптимального управления со смешанными ограничениями. После того, как гарантировано отсутствие прячущегося объекта в коридоре, получившаяся область неопределенности является следующим элементом в последовательности выпуклых областей неопределенности. При построении управления используется не опорная функция области неопределенности, которую в общем случае найти можно лишь приближенно, а опорные функции множеств © и W, которые находятся в аналитическом виде.

Предлагаемые конструкции, позволяют строить управления поиска в случае, когда поиск осуществляется несколькими ищущими объектами.

В качестве примера применения метода рассматривается задача поиска для случая, когда области управления ищущего и прячущегося объектов являются эллипсоидами. В этом случае все конструкции метода переписываются в терминах эллипсоидального исчисления, которое позволяет заменить теоретико-множественные операции аналитическими формулами.

Во второй части второй главы рассматривается простая динамика прячущегося объекта.

Я: y = v} где у G R2, v{t) е V = aBf (0). Для такой динамика прячущегося объекта и заданной траектории x (t) ищущего объект описывается граница области неопределенности в виде параметрической кривой. Последовательность шагов поиска соответствует первой части. Отличие состоит в том, что управление выбирается таким, что осуществляет движение области обнаружения x (t)+M непосредственно вдоль границы области неопределенности, а не вдоль ограничивающего ее коридора. Осуществимость такого движения предполагает жесткие требования гладкости границы области неопределенности. Эти требования можно удовлетворить, расширив границу области неопределенности и при этом наделив ее нужными свойствами.

Третья глава работы посвящена нелинейной задаче поиска. В ней предлагаются конструкции, которые позволяют построить множества начальных позиций, для которых заданное управление ищущего объекта является управлением поиска.

Рассматривается управляемая динамическая система, которая описывается системой нелинейных дифференциальных уравнений z = f{z, u, v), где 2 € Rn, u{t) eU С Rp, v (t) G V С Rq, множества U, V — компакты. В начальный момент времени точка z (0) € Zq.

Задача поиска для заданного отрезка времени [0, в] формулируется следующим образом: найти такое допустимое управление и3(-) на отрезке времени [0,6), что для любой начальной точки zo? Z0 и для любого допустимого управления v (-) найдется момент времени t = t (zQ, v (-))? [0, в], для которого выполнится терминальное условие z (tz0,us{-), v{-)) е м, где М — заданное замкнутое множество в пространстве Rn (не обязательно ограниченное).

Глава посвящена решению следующей задачи: для заданного допустимого управления «(•) на отрезке времени t? [0,9) построить такое множество, что управление и (-) решает задачу поиска для множества начальных позиций Zq = Qq^ ^.

Определение. Оператор Se>u^, где в > 0 и и (-) —допустимое управление, ставит в соответствие каждому замкнутому множеству W? Rn множество Se^W всех таких точек zq? Rn, что для любого допустимого управления v (-) выполняется одно из следующих условий: z (ez0M-), v (-)) ?WM или для некоторого t? [0, в) z (tz0,u (-), v{-))? М.

С помощью операций над множествами определение оператора записывается в виде.

•)eV[o, 0].

J {z0?Rnz (tz0,u (-), v (-))?M}}, te[o, e] где V[0, в] — множество допустимых управлений v (-).

Согласно определению оператора 5 $^.), управление ?(•), на отрезке времени t? [0,0], является решением для задачи поиска с начальным множество Zq = Setu (.)M и терминальным множеством М.

Затем рассматриваются два оператора, аппроксимирующие оператор S^.). В определение первого оператора пересечение по всем допустимым управлениям v (-) заменяется на пересечение только по кусочно—постоянным допустимым управлениям. Для этого вначале строится вспомогательный оператор

Доопределение. Оператор где е > 0 и и (-) —допустимое управление, ставит в соответствие каждому замкнутому множеству W е Rn множество S?, u{-)W всех таких точек zo € Rn, что для любого постоянного управления v (t) = v е V, t е [0, е], выполняется одно из следующих условий: z{ez0,u (-), v) eWM или для некоторого t е [0, е] z (tz0,u (-), v) е М.

С помощью операций над множествами определение оператора записывается в виде.

§ e, vi-)w = П[Ь €Rnz (sz0,"(.), V) е WM}и vev.

U {z0eRaz (tz0,u (-), v) eM}]. te[0,e].

Определение. Для конечного разбиение ш отрезка [0, в] и допустимого управления и (-) обозначим.

Su (-)w = SSuUl^SS2iU2{.).SSkjUk{.)W, где.

5{ = Т{ — Ti-1, i = l,., k, Ui (t) = u (t^iИ), i = 1, ., k.

Связь между оператором и оператором S^W отражает следующая теорема.

Теорема. Справедливо равенство.

М 18 где пересечение берется по всем конечным разбиениям и отрезка [0, в.

Следующем шагом аппроксимации оператора Se}U (.) является замена траектории z (*zq, и (-), v (-)) ломанной Эйлера.

Для фиксированного числа he R и вектора и е U рассматривается оператор м^=П к U U (* - v))} U{ U (* - hf (z> u>*))}]• vev zeM ie[o, h] ¦ z&wM.

Затем для равномерного разбиения lo = {0. h,., (m — l) h:mh}, mh = t: отрезка времени [0, t] и допустимого кусочно-постоянного управление и (-) с участками постоянства, соответствующими разбиению ш, т. е. и (т) = щ (т — (i-l)h) = щ€.и длят G ((i—l)h, ih], г = 1,., ш, рассматривается оператор m.

В работе доказывается близость множеств StiU^M, Ej^Af в метрике Ха-усдорфа, если терминальное множество М — удовлетворяет условию телесности.

Определение. Пусть множество М — компактно. Обозначим.

B (a, M) = dM + aS,.

W (a, M) = В (а, М) ПМ, L, m В (а, M)-*dS — непрерывная функция, К (г, и, г, 1а! м) = (J S (z + laM (z)r, Tr).

0 <�т<�и>

Множество М удовлетворяет условию телесности с положительными константами а, и, г и функцией если для любого z G W (a, М).

K (z, U), r, latM) с М.

Теорема. Пусть множество М удовлетворят условию телесности с некоторыми константами, тогда существует такая константа во >

О, что если t < во, то для любого г]>0 существует такое натуральное число то, что для всех т > то справедливо неравенство p{St, u (-)M, E™u^M) < г], где mh = t и р (.,.) — расстояние Хаусдорфа между множествами.

Основные результаты работы.

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

2) Предложен конструктивный метод нахождения управления поиска в задаче с линейной динамикой прячущегося объекта, простой динамикой ищущего объекта и двумерным терминальным множеством. Доказана теорема о достаточном условии разрешимости этой задачи.

3) Доказаны теоремы о точном представлении и приближенном построении с любой наперед заданной точность в метрике Хаусдорфа множества начальных позиций, из которых разрешима нелинейная задача поиска при заданном управлении ищущего объекта.

Основные результаты опубликованы в работах [20,62—64].

Автор выражает глубокую благодарность своему научному руководителю Николаю Леонтьевичу Григоренко за постоянное внимание к работе.

Основные обозначения.

N — множество натуральных чисел Rn — п—мерное вещественное евклидово пространство ||х|| — евклидова норма вектора х, равна xi)1 ||x||i — норма вектора х, равная Ya=i хг (х, у) — скалярное произведение векторов х и у (а) — сфера радиуса г и центром в точке, а в n-мерном пространстве с евклидовой нормой (если г = 1, то обозначаем Sn) В™(а) — шар радиуса г и центром в точке, а в n-мерном пространстве с евклидовой нормой S^ — единичная сфера в п—мерном пространстве с нормой || • ||i Ат — транспонированная матрица, А I — единичная матрица Тг (А) — след матрицы Л с (А, ф) — опорная функция множества, А в направление ф с{А, ф) = swpxeA (х, ф) со, А — выпуклая оболочка множества, А А + В — алгебраическая сумма множеств, А и В.

А + В = {c = a + bae A, b€ В} DA — произведение матрицы D на множество А.

DA = {с = Daa е А} А-В — геометрическая разность множеств Л и Б А-В = {сс + В С А}.

1. Абчук В. А., Суздаль В. Г. Поиск объектов.— М.: Советское радио, 1977.

2. Аввакумов С. Н. Гладкая аппроксимация выпуклых компактов//Труды института математики и механики. — Т. 4. — Екатеринбург: УрО РАН, 1996.—С. 184−200.

3. Айзеке Р. Дифференциальные игры. — М.: Мир, 1967.

4. Алексеев В. М., Тихомиров В. М., Фомин С. В. Оптимальное управление. — М.: Наука, 1979.

5. Андрамонов М. Ю. Методы глобальной мимнимизации для некоторого класса обобщенно выпуклых функций. — Казань: Издательство Казанского математического общества, 2001.

6. Афанасьев В. И., Колмановский В. Б., Носов В. Р. Математическая теория конструирования систем управления. — М.: Высшая школа, 1989.

7. Байокки К., Капело А. Вариационные и квазивариационные неравенства. — М.: Наука, 1988.

8. Балашевич Н. В., Габасов Р., Кириллова Ф. М. Алгоритмы программной и позиционной оптимизации систем управления с промежуточными фазовыми ограничениями //Журнал вычислительной математики и математической физики. — 2001. — Т. 41, № 10.— С. 1485−1504.

9. Беккенбах Э., Беллман Р. Неравенства. — М.: Мир, 1965.

10. Беллман Р. Динамическое программирование. — М.: Издательство иностранной литературы, 1960.

11. Бердышев Ю. И. Об одной задаче последовательной оптимизации без декомпозиции во времени // Кибернетика. — 1987. — № 4. — С. 32— 35.

12. Бердышев Ю. И. К задаче последовательного обхода нелинейным управляемым объектом совокупности гладких многообразий // Дифференциальные уравнения и процессы управления. Электронный журнал (http://www.neva.ru/journal).— 1999.— № 2.

13. Бердышев Ю. И., Ченцов А. Г. Оптимизация взвешенного критерия в одной задаче управления // Кибернетика.— 1986.— № 1.— С. 59— 64.

14. Березин С. Б. Информационные множества в задаче динамического поиска объектов с несколькими ищущими // Вестник Московского университета, Сер. 15, Вычислительная математика и кибернетика.— 2001.— № 3.

15. Благодатских В. И.

Введение

в оптимальное управление.— М.: Высшая школа, 2001.

16. Васильев Ф. П. Методы решения экстремальных задач.— М.: Наука, 1981.

17. Васильев Ф. П. Численные методы решения экстремальных задач. — М.: Наука, 1988.

18. Габасов Р., Кириллова Ф. М. Основы динамического программирования. — Минск: Издательство Белорусского университета, 1975.

19. Григоренко Н. JI. Математические методы управления несколькими динамическими процессами. — М.: Издательство МГУ, 1990.

20. Демьянов В. Ф., Малоземов В. Н.

Введение

в минимакс. — М.: Наука, 1972.

21. Демьянов В. Ф., Рубанов А. М. Основы негладкого анализа и квазидифференциальное исчисление. — М.: Наука, 1990.

22. Дикусар В. В., Милютин А. А. Качественные и численные методы в принципе максимума. — М.: Наука, 1989.

23. Зеликин М. И. Об одной дифференциальной игре с неполной информацией // Доклады АН СССР. — 1972. — Т. 202, № 5.

24. Иоффе А. Д., Тихомиров В. М. Теория экстремальных задач. — М.: Наука, 1979.

25. Киселев О. И., Поляк Б. Т. Эллипсоидальное оценивание по обобщенному критерию// Автоматика и Телемеханика.— 1991.— № 9.— С. 133−144.

26. Киселев Ю. Н. Линейная теория быстродействия с возмущениями. — М.: Издательство МГУ, 1986.

27. Киселев Ю. Н. Оптимальное управление. — М.: Издательство МГУ, 1988.

28. Кларк Ф. Оптимизация и негладкий анализ. — М.: Наука, 1988.

29. Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. — М.: Наука, 1981.

30. Коробов В. И., Маринич А. П., Подольский Е. Н. Управляемость линейных автономных систем при наличии ограничений на управление // Дифференциальные уравнения. — 1975. — Т. 11. — С. 11.

31. Красовский Н. Н. Теория управления движением. — М.: Наука, 1968.

32. Красовский Н. Н. Игровые задачи о встрече движений. — М.: Наука, 1970.

33. Красовский Н. Н. К задаче унификации дифференциальных игр // Доклады АН СССР. — 1976. — Т. 226, № 6. — С. 1260−1263.

34. Красовский Н. Н., Субботин А. И. Позиционные дифференциальные игры. — М.: Наука, 1974.

35. Кряжимский А. В., Осипов Ю. С. Экстремальные задачи с отделимыми графиками // Кибернетика и системный анализ. — 2002. — № 2. — С. 32−55.

36. Кунцевич В. М., Пшеничный Б. Н. Решение одного класса задач сближения в условиях неопределенности // Кибернетика и системный анализ. — 1995. — № 3. — С. 63−70.

37. Куржанский А. Б. Управление и наблюдение в условиях неопределенности. — М.: Наука, 1977.

38. Куржанский А. Б. Об аналитическом описании пучка выживающих траекторий дифференциальной системы // Даклады АН СССР. — 1986. — Т. 287, № 5.—С. 1047−1050.

39. Куржанский А. Б., Осипов Ю. С. К задаче об управлении с ограниченными фазовыми координатами // Прикладная математика и механика. — 1968. — Т. 32. — С. 194−202.

40. Куржанский А. Б., Осипов Ю. С. К задачам об управлении при стесненных координатах // Прикладная математика и механика.— 1969. —Т. 33.—С. 705−719.

41. Куржанский А. Б., Осипов Ю. С. К задачам программного преследования в линейных системах // Известия АН СССР, сер. Техническая кибернетика. — 1970. — № 3. — С. 18—29.

42. Ларин П. М. О неразрешимости задачи гарантированного поиска в достаточно большой области // Вестник Московского университета, Сер. 15, Вычислительная математика и кибернетика.— 2000.— № 1.— С. 44−47.

43. Ли Э. В., Маркус Л. Основы теории оптимального управления. — М.: Наука, 1972.

44. Лотов А. В. Численный метод построения множеств достижимости для линейных управляемых систем с фазовыми ограничениями // Журнал вычислительной математики и математической физики. — 1975.—Т. 15, № 1.

45. Люстерник Л. А., Соболев В. И. Краткий курс функционального анализа. — М.: Высшая школа, 1982.

46. Математическая теория оптимальных процессов / Л. С. Понтрягин, В. Г. Болтянский, Р. В. Гамкрелидзе, Е. Ф. Мищенко. — М.: Наука, 1983.

47. Меликян А. А., Черноусько Ф. Л. Некоторые минимаксные задачи управления с неполной информацией // Прикладная математика и механика.— 1971. — Т. 35.— С. 952—961.

48. Местников С. В. Аппроксимация области неопределенности в дифференциальных играх поиска // Дифференциальные уравнения.—1992. — Т. 28, № 6. — С. 967−972.

49. Милютин А. А., ДМитрукА. В., Осмоловский Н. П. Принцип максимума в оптимальном управлении. — М.: Издательство ЦПИ при мех.-мат. факультете МГУ, 2004.

50. Моисеев Н. И. Элементы теории оптимальных систем.— М.: Наука, 1975.

51. Назин А. В., Назин С. А., Поляк Б. Т. О сходимости внешних эллипсоидальных аппроксимаций областей достижимости линейных дискретных систем // Автоматика и Телемеханика. — 2004. — № 8. — С. 39—61.

52. Никольский М. С. Управление линейными объектами с возможным нарушением в динамике // Труды института математики и механики УрО РАН. — Т. 3. — Екатеринбург: 1995.

53. Никольский М. С. Об одной задаче осуществления заданного движения, гибкие системы. //Доклады академии наук. — 1996. — Т. 350, № 6.— С. 739−741.

54. Об одном алгоритме численного решения линейных дифференциальных игр / Е. С. Половинкин, Г. Е. Иванов, М. В. Балашов и др. //Математический сборник. — 2001. — Т. 192. — С. 95−122.

55. Овсеевич А. И., Черноусько Ф. Л. Двусторонние оценки областей достижимости управляемых систем // Прикладная математика и механика. — 1982. — Т. 40, № 5. — С. 737−744.

56. Оптимальное управление движением / В. В. Александров, В. Г. Болтянский, С. С. Лемак и др. — М.: ФИЗМАТЛИТ, 2005.

57. Орлова Г. Б., Силин Д. Б. Приближенное вычисление выпуклой оболочки положительно однородной функции // Вестник Московского университета. Сер. 15, Вычислительная математика и кибернетика. — 1997. — № 2. — С. 32−35.

58. Панасюк А. И., Панасюк В. И. Асимптотическая магистральная оптимизация управляемых систем. — Минск: Наука и техника, 1986.

59. Петросян Л. А., Гарнаев А. Ю. Игры поиска. — Л.: Изд. ЛГУ, 1992.

60. Петросян Л. А., Зенкевич Н. А. Оптимальный поиск в условиях конфликта. — Л.: Изд. ЛГУ, 1987.

61. ПивоварчукД. Г. Об одном подходе к исследованию нелинейной задачи динамическго поиска // Материалы научной школы-конференции «Мобильные роботы и мехатронные системы». — М.: Издательство Московского университета, 2003. — С. 264−288.

62. ПивоварчукД. Г. Задача динамического поиска на плоскости с простой динамикой убегающего // Проблемы динамического управления. — М.: Издательский отдел факультета ВМиКМГУ, 2005. — С. 230−252.

63. ПивоварчукД. Г. Операторный подход к исследованию нелинейной задачи поиска // Труды международного семинара «Теория управления и теория обобщенных решений уравнений Гамильтона-Якоби» .— Екатеринбург, 2006. — Т. 1. — С. 126−135.

64. Половинкин Е. С., Балашов М. В. Элементы выпуклого и сильно выпуклого анализа. — М.: ФИЗМАТЛИТ, 2004.

65. Понтрягин Л. С. О линейных дифференциальных играх i // Доклады АН СССР. — 1967. — Т. 174, № 6. — С. 1278−1280.

66. Понтрягин Л. С. О линейных дифференциальных играх и // Доклады АН СССР. — 1967. — Т. 175, № 4. — С. 764−766.

67. Понтрягин Л. С. Обыкновенные дифференциальные уравнения.— М.: Наука, 1974.

68. Понтрягин Л. С. Линейные дифференциальные игры преследования // Математический сборник. — 1980. — Т. 112. — С. 307−330.

69. Пшеничный Б. Н. Линейные дифференциальные игры // Автоматика и телемеханика. — 1968. — № 1. — С. 65—78.

70. Пшеничный Б. Н. Необходимые условия экстремума.— М.: Наука, 1969.

71. Пшеничный Б. П., Остапенко В. В. Дифференциальные игры. — Киев: Наукова думка, 1992.

72. Решетняк Ю. Н. Суммирование эллипсоидов в задаче гарантированного оценивания // Прикладная математика и механика. — 1989. — Т. 53, № 2. — С. 249−254.

73. Рокафеллар Р. Выпуклый анализ. — М.: Мир, 1973.

74. Савинов В. Б. Дифференциальная игра преследования одним преследователем нескольких убегающих // Труды института математики и механики УрО РАН. — Т. 3. — Екатеринбург: 1995.

75. Силин Д. Б., Тринько Н. Г. Модификация алгоритма грехема для овы-пукления положительно однородной функции //Журнал вычислительной математики и математической физики.— 1994.— Т. 34, № 4.—С. 631−636.

76. Скворцов А. А. Динамический поиск в выпуклых областях // Фундаментальная и прикладная математика.— 1998.— Т. 4, № 2.— С. 785−790.

77. Скитович В. В., Чистяков С. В. Игровые задачи сближения и поиска. — М.: Изд-во МАИ, 1985.

78. Сотсков А. И. О критерии минимакса и некоторые приложения к задачам оптимального управления // Кибернетика. — 1969. — № 4. — С. 110−116.

79. Субботин А. И., Ченцов А. Г. Оптимизация гарантии в задачах управления. — М.: Наука, 1981.

80. Ушаков В. Н. К задаче построения стабильных мостов в дифференциальной игре сближения-уклонения // Извести АН СССР, сер. Техническая кибернетика. — 1980. — № 4. — С. 29—36.

81. Ушаков В. Н., Успенский А. А., Токманцев Т. Б. Стабильные мосты в дифференциальных играх на конечном промежутке времени // Труды института математики и механики УрО РАН. — 2004. — Т. 10, № 2.

82. Филиппов А. Ф. Дифференциальные уравнения с разрывной правой частью. — М.: Наука, 1985.

83. Хеллман О.

Введение

в теорию оптимального поиска. — М.: Наука, 1985.

84. Черноусько Ф. Л. Управляемый поиск подвижного объекта // Прикладная математика и механика. — 1980. — Т. 44, № 1.

85. Чхартишвили А. Г., Шикин Е. В. Динамический поиск объектов, геометрический взгляд на проблему. // Фундаментальная и прикладная математика. — 1995. — Т. 1, № 4.

86. Шикин Е. В., Березин С. Б. Поиск объектов, динамика, геометрия, графика // Фундаментальная и прикладная математика.— 2005.— Т. 11, № 1.— С. 3−34.

87. Bridgland Т. F. Trajectory integrals of set valued function // Pacific journal of mathematics. — 1970. — Vol. 33, no. 1. — Pp. 43—68.

88. Gal S. Search games with mobile and immobile hider // SI AM J. Control and optimization. — 1979.— Vol. 17, no. 1. — Pp. 99−122.

89. Garnaev A. Remark on the princess and monster search game I I International Journal of Game Theory. — 1992. — Vol. 20. — Pp. 269 276.

90. Krayzhimskii A. V., Paschenko S. V. On the problem of optimal compatibility // J. Ill-Posed Problems.— 2001.— Vol. 9, no. 3, — Pp. 283−300.

91. Kurzhanski А. В., Varaiya P. Ellipsoidal techniques for reachability analysis: internal approximation // Systems & Control Letters 4.— 2000. —Vol.41.—Pp. 201−211.

92. Kurzhanski А. В., Varaiya P. On ellipsoidal techniques for reachability analysis, part i: External approximations // Optimization Methods and Software. — 2001. — Vol. 17. — P. 177−206.

93. Schmitendorf W. E. Differential games without pure strategy saddle-point solutions // Journal of optimization theory and applications.— 1979. — Vol. 18, no. 1. — Pp. 81−92.