автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Моделирование конфликтов управляемых сложных систем

, на правах рукописи

НАРТОВ Борис Кимович

МОДЕЛИРОВАНИЕ КОНФЛИКТОВ УПРАВЛЯЕМЫХ СЛОЖНЫХ СИСТЕМ

05.13.16 применение вычислительной техники, математического моделирования п математических методов в научных исследованиях (в механике)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Красноярск - 1998

Работа выполнена в Красноярском государственном техническом университете н Институте вычислительного моделирования СО РАН

Научный руководитель: доктор физико-математических наук,

профессор А.Н. Горбань Официальные оппоненты: доктор физико-математических наук,

профессор Е.А. Новиков доктор технических наук, профессор В.А. Охорзин

Ведз'щая организация: Сибирский государственный технологический университет

Защита состоится 24 декабря 1998 г. в часов на заседании Специализированного совета К 064.54.01 при Красноярском государствен ном техническом университете по адресу: 660074, г. Красноярск, ул. Киренского, 26.

С диссертацией можно ознакомиться в библиотеке КГТУ. Автореферат разослан " 23 " ноября 1998 г.

Ученый секретарь Специализированного совета ¿^ЗЬ—УУ*" - Н.Г.Кузьменко

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Цель работы. Цель данной работы состояла в решении следующих основных задач:

1) построение простейшей состоятельной модели взаимодействия (конфликта) групп противодействующих подвижных объектов, связывающей характеристики объектов с характеристиками объектов противника, управлением и временем;

2) Разработка универсальных - в смысле исходной функции взаимодействия объектов - методов быстрой направленной оптимизации начальных координат и характеристик подвижных конкурирующих объектов в соответствующих задачах оптимального управления;

3) формализация общего случая классической задачи оптимального преследования в виде задачи оптимального управления и аналогичная формализация частных случаев, в том числе задачи коммивояжер;!;

4) формализация задачи планирования поиска неподвижных целей с известными функциями плотностей распределения вероятностен в виде задачи оптимального управления, в том числе •• случая управления поиском в реальном масштабе времени и случая с заданной плотностью вероятности гибели поисковой единицы;

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

Научная новизна. В работе получены следующие новые научные результаты:

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

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

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

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

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

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

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

Результаты диссертационной работы использовались п 1990-1991 гг. в рамках научно-технической программы Гособразовання СССР "Интеллектуальные системы" и были внедрены в практику обучения студентов на кафедре № 301 Московского авиационного института по учебной специальности 210500 "Системы управления летательными аппаратами". Составленная автором диссертации лабораторная работа "Система поиска и обнаружения объектов на местности" (описание и программный продукт) использовались в течение 5 лет в 1992-1996 гг. по курсу "Системы автоматического управления с элементами искусственного интеллекта" (Акт о внедрении, № 004960, от 2.02.1996 г.).

Апробация работы. Основные результаты диссертации докладывались и обсуждались па региональной конференции "Информатика и вычислительная техника в управлении" (Омск, 1988), международной конференции "Обработка изображений и дистанционные исследования" (Новосибирск, 1990), международной конференции Computer Algebra and Its Applications to Mechanics (Новосибирск, 1990), международном симпозиуме Visual Analysis and Interface (Новосибирск, 1991), международной конференции "Индустриальные системы современной эпохи и гуманитарное образование" (Омск, 1992). В 1987-95 гг. результаты диссертации докладывались и обсуждались на семинарах в Омском политехническом институте, Омском государственном университете, Институте теоретической и прикладной механики СО АН СССР, Московском авиационном институте. Институте систем информатики им. А.П. Ершова СО РАН,

Публикации. Основные результаты диссертации опубликованы в двух монографиях и десяти печатных работах и депонированных рукописях [1 12].

Структура и объем работы. Диссертация состоит т введения, грех глав (13 параграфов) и списка литературы. Диссертация изложена на 96 страницах н содержит 41 рисунок ыЗ таблицы. Список литературы содержит 65 наименований.

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

Глава 1 (§§1.1-1.6) посвящена в основном задачам конкуренции групп подвижных управляемых объектов, характеристики которых ухудшаются в результате воздействия объектов противника. Большое внимание уделено при этом проблемам оптимизации начальных условий - начальных координат и характеристик конкурирующих объектов. Предлагаемые в работе методы приложимы к достаточно широкому классу задач и позволяют перейти от переборных алгоритмов к направленной оптимизации начальных условий. Отдельно рассмотрены задачи управления направленными воздействиями и задачи оптимального преследования.

В § 1.1 предложена и обоснована простейшая состоятельная модель взаимодействия (конкуренции) групп противодействующих объектов, связывающая характеристики объектов с характеристиками объектов противника, управлением и временем и удовлетворяющая при этом принципу суперпозиции. А именно, для случая двух противодействующих объектов:

где р, - характеристики объектов игроков 1 и 2 соответственно; 9 функция взаимодействия объектов; .?(/) траектория р-объекта игрока 1; а^) - известная траектория ^-объекта игрока 2. Для модели (1) сформулирована задача

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

V = 0, а(*)),

(1)

3{х*) = вир .1(1'), жех

Г»

гдр

3{х) = 5(0) -

(3)

X = {5(011 * (01 < ^ I * (01 < 2С; 0 < / < 0} (4)

где V. С. О ~ заданные числа.

Для общего случая N и М управляемых объектов игроков 1 и 2 и несовпадающих функций взаимодействия ¡р обоснована модель

м

Рк = ~Рк Е д^2(а:1ь(0'а>(0)> 1 < к < .V,

^ (5)

Як = -Як Е 1 < к < М,

¿=1

и сформулирована соответствующая задача оптимального управления р-объектами игрока 1:

3(х*)=ЫЛх).- (6)

1бЛ

где

м N

*=1 к=1

х = {здн ¿4 (01 < (01 < 2ск- о < г < 1 < к < лг}, (8)

где Ьк2, Ук, ,Ск, - заданные числа.

(Далее, в Главе 1, задачи (1)-(4) и (5)-(8) используются в качестве демонстрационных).

В заключение § 1.1 формализуется расширение задачи (5)-(8) на случай вероятностно заданных траекторий д-объектов игрока 2.

В § 1.2 на примере задач (1)-(4) и (5)-(8) описываются два универсальных метода оптимизации начальных координат управляемых траектории групп подвижных объектов.

Метод возврата. Рассмотрим задачу, двойственную задаче (1)-(4):

| Р\ = Й1(0), ^

( Ъ = Ч\Р\Ч>{ах{£), ¿1(0),

•A(a'i) = sup Jx{xx), (10)

где

J\[x\) = q{tf) - 9(0), (11)

Xi = {.fi(i)|| ¿, (01 < Vi(i), | £i (01 < 2c; 0 < t < tf), (12) а функция Vj(<) задается формулой

Vi(t)

V при t G

v,

P,t7 -*/-&'*/ j

2c(tf — 0 при £ £

Обозначим алгоритмы решения задач (1)-(4) и (9)-(12) через [7 и Ъ\.

Предлагаемый метод направленной оптимизации начальных координат траекторий р-объектов исходной задачи (1)-(4) - метод возврата -состоит в построении сходящегося итеративного процесса

в котором в качестве части начальных условий очередного шага итерации используется часть конечных значений предыдущего шага. Исходная задача '"исчерпывания" д-объекта (17) чередуется с задачей "восстановления* (/-объекта (II1). При этом на четных шагах (7) рассматривается движение ^-объекта, обратное исходному заданному а(1), то есть ах(0 — а^/ — ¿).

Доказана сходимость процесса к оптимальной начальной координате р-объекта, описан реализующий алгоритм.

Метод модификации ограничений. Модифицируем динамические ограничения множества управлений X исходной задачи (5)-(8):

X - Хъ = {х4(0|| хк (01 < акШ£к (01 < А(0.

(13)

о < * < о, 1 < к < .V},

и обозначим решения задачи (5)-(7) с допустимым множеством управлений (13) через .(-у/). 1 < <

Функции <Ук(0 должны удовлетворять следующим условиям:

1. дифференцируемы и ак(1) < 0;

2. г*;.(() » Ук на интервале (0,Д<), Д2 « при этом ¡п{'щ.(/) на (0, и величина А г регулируются параметрами функции а*(/) независимо:

3. ам(<) может быть сделана сколь угодно близкой к константе на интервале (Д*4 + М/), где At + 6« при этом близость ок{г) к V, и величина 8 регулируются параметрами функции независимо.

Функции должны удовлетворять следующим условиям:

1. Рк{1) дифференцируемы и < 0;

2. Дь(г) » 2Ск на интервале (0,Д£ + 6), где Д£ и 6 заданы аЦ/)-а ¡п{Рк{1) на интервале (0,Д< + 6) регулируется параметрами функции

т\

3. Рк(?) может быть сделана сколь угодно близкой к константе 2Ск на интервале (At + 25,

Далее доказывается, что для любого е > 0 находятся такхге а».(<), что

|ё1о(0) - гЦД<+ 26)| < £, 1 < к < /V, (14)

где 5д-о(0) - искомые оптимальные начальные векторы управляемых траекторий р-объектов исходной задачи (5)-(8), а берутся из решений ■г£2 задачи (5)-(7) с модифицированным множеством управлений (13).

Приведена схема вычисления приближений векторов Хко(0)-

Описанный в § 1.2 метод возврата применим, по крайней мере, к задачам с монотонным исчерпыванием ресурсов противников, в том числе и в обшем случае N > 1, М > 1. Метод модификации ограничений применим ко всему классу задач с непрерывными моделями взаимодействия.

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

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

Метод фиктивных потоков. Модифицируем модель взаимодействия (5) исходной задачи (5)-(8):

Рк = -Рк Т. ~ «*(0р* + хг Е «¡(Ф,- 1 < А- < Л*,

1=1 t=i

Чк = | PiVi(ii(0.at(0)> \ < к < М и исходное множество управлений X : X —> Х3 = X ® U, где

L7 = {w(i)|0 < uk{t) < /(<), 0 < t < th \ < к < N}. (16)

со следующими требованиями к f(t):

1. j(t) дифференцируема и /(i) < 0;

2. j(t) может быть сделана сколь угодно большой на интервале (0, At). где At « tj, при этом inf j(t) на (0, At) и величина Дt регулируются параметрами функции /(<) независимо;

3. /(f) может быть сделана сколь угодно малой на интервале (At + 6.tj), где At + 6 « tj. при этом sup/(i) и величина 6 регулируются параметрами функции fit) независимо.

Далее доказывается, что для любого е > 0 найдутся такие Дt и <5, что

К(0)-рЦД< + б)|<£, 1 <k<N, (17)

где ркй (0) - искомые оптимальные начальные характеристики р-объектов

N

исходной задачи (о)-(8) (Е Рк(0) = const)-,

plz{t) - характеристики р-объектов из решения вспомогательной задачи (15), (6), (7), (16).

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

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

Поскольку, как доказывается, методы и алгоритмы, реализующие вспомогательные задачи § 1.2 (второй результат) и § 1.3, совместимы, можно воспользоваться следующей вспомогательной задачей:

1. Модель взаимодействия (5) исходнохг задачи (5) (8) заменяется моделью взаимодействия (15);

2. Множество управлений (8) исходной задачи (5)-(8) заменяется на множество управлений

Х4 = Х2®17, (18)

где Л~2 и II описаны формулами (13) и (16) соответственно.

Решая теперь полученную вспомогательную задачу (15), (6), (7), (18), можно утверждать, что для любого е > 0 найдутся такие функции <Аь(0> с параметрами At а 6 , что

£ К(0) - Р;4(Л* + 26)1 + £ \хко(0) - ¿:Ч(Д* + 25)1 < е (19) к=1

гле (рю(0),.. • 0); 5ю(0),... ,5лго(0)) - искомый оптимальный вектор начальных координат-характеристик исходной задачи (5)-(8); •г'м(^) ~ из решения вспомогательной задачи (15), (6), (7), (18).

Предлагаемый метод, как и исходные методы §§ 1.2 и 1.3, применим ко всему классу задач с непрерывными моделями взаимодействия.

В § 1.5 описаны две модификации исходной демонстрационной модели взаимодействия (5). Эти модели позволяют просто учесть управляемость направленных воздействий подвижных объектов и возможность разделения соответствующего ресурса данного объекта между подвижными объектами конкурента.

В Модели 1 в исходной системе дифференциальных уравнений (5) с каждым из управляемых объектов связывается управляемая "точка при-целипания'" с координатой Zi(t), 1 ... г... N. При этом функция ^-'о- зависящая лишь от расстояния г = — а^{¿) | между /-й ''точкой прицеливания" и к-и объектом конкурента, описывает рассеяние воздействия г-го управляемого объекта в направлении ■£,(/) —> «¿(О- Функция У'ц(г) зада-

ется таким образом, что совмещение траектории Z-t{1) с <n(i) концентрирует воздействие г-го управляемого объекта на к-м объекте конкурента.

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

Формализованы соответствующие задачи оптимального управления.

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

Задача 1 (Простейший случай). Задан временной интервал [0, £/]. траектория цели â(i), 0 < t < tj, в евклидовом пространстве Е'\ начальная координата объекта-преследователя ¿(0), пространственные и динамические ограничения на его возможные траектории £(•), выражающиеся в системе неравенств, связывающих функцию x(t) и ее производные до второй включительно.

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

Решение. Введем первую вспомогательную функцию F(s(t)), s(t) = |.r(i) — a(i)|, удовлетворяющую следующим условиям:

1. F(s) дифференцируема и F's(s) > 0. | 0 < F (s) < ei при 0 < s < éTi [ 1 - £2 < F (s) < 1 при S > + E%

3. Значения ei и е? регулируются параметрами функции F(s) независимо (в смысле неравенств 0 < £2 < и 0 < < гДе £з ~ заданное число).

Конкретный вид F (s), удовлетворяющей условиям 1. 3., вполне произволен.

Введем далее вторую вспомогательную функцию F(s(-),f) с начальным условием F(s(-).0) = 1 и следующими свойствами:

F "достаточно быстро" убывает по t при F < F, F "достаточно

медленно" возрастает по * при Р > Р. При этом поведение Г регулируется параметрами Р и Г таким образом, что для любого интервала (О, ¿) С (0, ¿/) функция Р(я(-), £) сколь угодно точно приближает значения функции

Простейшая удовлетворяющая этим требованиям функция является решением дифференциального уравнения

• р_^

—, (20)

где о- - регулируемый положительный параметр.

Используя преобразование —» -+ молено записать

решение задачи 1 в виде

Ч

! (21)

о

Решая теперь (20) с начальным условием .Р(з(-),0) = 1, получим Р(з(-)Л) =

Подставляя (22) в (21), получим классическую задачу вариационного исчисления.

Далее в § 1.6 формализуется с помощью введенных вспомогательных функций Р и Р задача 2 - вариант общего случая задачи оптимального преследования.

(В § 1.6 мы ограничились рассмотрением задачи планирования, но предлагаемый подход распространим и на случай дифференциальной игры).

В Главе 2 (§§ 2.1-2.4) решены некоторые задачи оптимального поиска стационарных целей. Исходные данные рассматриваемых задач следующие.

Односвязной области О С Е2 достоверно принадлежат К неподвижных целей с известными функциями плотностей распределения вероятностей Л-(ж), 1 < к < Л", .г = (:Г1,.г'2) 6 [6'], где [С] - замыкание области

(22)

О. В замыкании [С] произвольным образом расположены в начальный момент времени Лг поисковых единиц (ПЕ). При движении каждая ПЕ является центром окружности радиуса а, заметающей в области С полосу шириной 2а - ''полосу захвата"; попавшая в полосу цель считается обнаруженной.

Отдельно рассмотрена задача коммивояжера.

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

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

Ниже представлена схема формализации общего случая задачи планирования поиска.

Метод упругих функций. Дополним исходные данные следующими обозначениями:

Дх) = £ /*(*);

к=1

£,•(£) = (£!(£),£2(0) — траектория г — ой ПЕ;

и = < < < 1 < г < /V} — стратегия поиска,

где •- время поиска.

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

Свяжем с каждой ПЕ колоколообрашую дифференцируемую функцию

Fi(x,^(f)) ■ "трафаретную" функцию, сколь угодно точно (регулировкой параметров F,) приближающую значения:

/ 1, если mt) - r| < а, .

\ 0. если — > а. ' '

Конкретный вид F{, удовлетворяющей этому условию, вполне произволен.

Зададим далее функцию sup (sup F,(x,£,(t))) - объединение шлей-

l<t<N 0<т<1

фов трафаретных функций F;(.x, £j(t)), 1 < i < N, над областью G за время t.

Доказывается, что в качестве искомого приближения объединения шлейфов может использоваться "упругая" функция F(r, tt, t), являющаяся решением уравнения

3F ^ F р

■ж=а£т=ъ (24)

где а - регулируемый положительный параметр, F(x,u, 0) — 0. Используя (24). молено теперь привести исходную задачу к виду

J (и) = J f(x)F(x.u, tj)ds —> max. (25)

G

т.е. получить функционал J (и) с дифференцируемым интегрантом, учитывающим возможное наложение полос захвата поисковых единиц.

(Допустим следующий наглядный комментарий: к моменту окончания поиска tf функция F создает над G дифференцируемую "галерею", повторяющую траектории поисковых единиц. При этом высота и ширина галереи с заданной точностью, регулируемой параметрами F и F;. равны 1 и 2а соответственно, в том числе и на интервалах пересечений и самопересечений полос захвата).

В § 2.2 результат § 2.1 расширяется на управления поиском неподвижных целей в реальном масштабе времени, когда известны реальные состояния поиска, то есть моменты обнаружения п координаты обнаруженных целой:

1) даны правила корректировки исходной плотности распределения /(.г) в моменты обнаружения целей:

2) показано, что оптимальные траектории поиска, управляемого в реальном масштабе времени, на интервале между двумя последовательными обнаружениями совпадают с траекториями оптимального плана (§ 2.1), рассчитываемого в момент последнего обнаружения (т.е. в момент обнаружения, открывающего данный временной интервал):

3) первый результат § 1.2 (метод возврата) распространен на задачу оптимального планирования поиска и оптимального управления поиском (§§ 2.1 и 2.2). для которых описан соответствующий метод оптимизации начальных координат поисковых единиц.

В § 2.3 исследуется расширение формализованной в § 2.1 задачи оптимального поиска на случай, когда на области поиска задана плотность вероятности гибели поисковой единицы, т.е. когда результат поиска зависит не только от просмотренной к данному моменту области, но и от последовательности ее просмотра.

Двухкритериальная задача слепого поиска формализована для случая одной цели, одной ПЕ и одной регистрирующей единицы (РЕ), а именно:

Дополнительно в области О находится регистрирующая единица (РЕ ) с соответствующей функцией плотности распределения вероятности ;■(-»") ■ .г 6 й. Если РЕ попадает в полосу захвата ПЕ, то ПЕ и РЕ удаляются из задачи. - При следующей таблице возможных исходов:

Объекты Исходы

Цель 1 0 1 0

ПЕ 1 1 0 0

РЕ 1 1 0 0

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

Модель 1 частный случай модели §1.1 связывает с каждой из .V точек задачи убывающую функцию "веса1" и функцию, зависящую от

дистанции между данной точкой и коммивояжером. Решение соответствующей задачи обеспечивает € - близкий обход всех точек.

Модель 2 - частный случай модели оптимального преследования в Ь 1 .(3 и модели оптимального поиска § 2.1. Решение соответствующей задачи обеспечивает не только £ - близость обхода всех точек, но и его оптимальность.

В Главе 3 (§ § 3.1- 3.3) предложены и исследованы некоторые достаточно общие модели поиска подвижных целей для систем автоматизированного отображения и анализа реальной физической обстановки. Соответствующие задачи порождаются необходимостью эффективного выборочного просмотра больших двумерных массивов текущей информации.

Исходные данные решаемых в Главе 3 задач следующие.

Реальная обстановка отображается на квадратной мозаике, состоящей из № активных элементов (./V »1). В площади мозаики находятся подвижные цели. Если координаты дели лежат в площади данного элемента мозаики, он находится в состоянии 1, если нет - 0. Управляемый процессором поисковый маркер идентифицирует цели по состоянию просматриваемых элементов мозаики.

В § 3.1 выделены II исследованы три основных варианта исходной задачи.

Вариант 1. Цель, достигшая границы мозаики, "отражается" границей внутрь мозаики. Количество целей в площади мозаики постоянно.

Вариант 2. Мозаика лежит в плоскости с известной средней плотностью целей. Границы мозаики "прозрачны" для целей, находящихся внутри и вне площади мозаики.

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

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

построить адекватную конкретной задаче и конкретной схеме поиска

целевую функцию:

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

прогнозировать и оценивать в реальном масштабе времени «тгтуашио поиска:

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

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

Отдельно рассмотрен случай одной цели.

В § 3.3 предложена модель поиска, расширяющая класс задач, исследованных в § § 3.1 и 3.2, где существенно использовались следующие допущения:

поиск состоит в циклическом просмотре некоторой фиксированной замкнутой кривой на мозаике;

время обнаружения половины целей много больше времени одного цикла просмотра;

в каждый момент времени обнаруженные и необнаруженные цели распределены по мозаике равномерно.

Модель § 3.3 снимает указанные ограничения, так как, во-первых, допускает подвижный фронт поиска достаточно произвольной геометрии и, во-вторых, учитывает релаксацию, т.е. немгновенное перемешивание захваченных целей с незахваченными.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

СПИСОК ОПУБЛИКОВАННЫХ РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Потапов В.И., Братцев С.Г., Нартов Б.К. О задачах оптимального управления конкурирующими подвижными объектами. Деп. рук.. ВНИНТИ, № 1465-В87, 1987. - 24 с.

2. Братцев С.Г., Нартов Б.К., Потапов В.И. Оптимальное сегментирование вычислительного ресурса ЭВМ // Тезисы конференции "Информатика и вычислительная техника в учебном процессе и управлении'". ОГПИ. - Омск: ОмПИ, 1988. - С.167-168.

3. Нартоп Б.К., Братцев С.Г. Модель оптимального преследования .. Стохастические п детерминированные модели сложных систем. ВЦ СО АН СССР. - Новосибирск, 1988. - С.86-92.

4. Братцев С.Г.. Мурзин Ф.А.. Нартов Б.К. Исследования по обраом ке динамических пзображешш // Тезисы международ, конф. "Обрабо i k.i изображений и дистанционные преследования", СО АН СССР. Новосибирск. 1990. С.41-43.

5. Нартов Б.К., Братцев С.Г. Модель поиска целей // Интеллектуальные системы управления летательных аппаратов. - М.: Изд-во МАИ. 1991.- С.46-50.

6. Bratsev S.G.. Murzin F.A., Nartov В.К. The Optimum Search of Targe*, and the Processing of Dynamical Images // Thes. if Intern. Symp. on Visual Analysis and Interface. - Novosibirsk, 1991. - p. 17-18.

7. Kriuclikov V.X., Nartov B.K., Frolov S.D. Addressing in Small Groups // Constructive Psychology, Transactions "Scientific Siberian", B. AMSE Press. Vol. 1, 1992. - P. 89-100.

8. Murzin F.A.. Bratsev S.G., Nartov B.K. A Parallel Automatic System for Image Processing, in Computer Algebra and Its Applications to Mechanics. Nova Science Publishers, Commack, NY 11725, 1992, 210 p.

9. Murzin F.A., Bratsev S.G., Nartov B.K. Optimum Target Search and Dynamic linage Processing // Advances in Modelling & Analysis. B. AMSE Press. Vol. 26. № 4, 1993. - P. 1-11.

10. Nartov B.K. Conflict of Moving Systems. - AMSE Press. France. 1994. 87 p.

11. Нартов Б.К. и др. Конфликт сложных систем. Модели и управление. М.: Изд-во МАИ, 1995. 120 с.

12. Крючков В.Н.. Мурзин Ф.А.. Нартов Б.К. Исследование связей в коллективах и сетях ЭВМ на основе анализа предпочтений // Проблемы конструирования эффективных и надежных программ. Институт пи том информатики им. А.П. Ершова СО РАН. Новосибирск, 1995. С. 130 141.

Подписано в печать 19.11.98

Формат бумаги 60x84 1/16.

Усл. печ. л. 1,2. Тираж 100 экз. Заказ 134.

Отпечатано на ризографе ИВМ СО РАН.

660036, Красноярск, Академгородок.

• ) 1

/

КРАСНОЯРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ

НАРТОВ Борис Кимович

МОДЕЛИРОВАНИЕ КОНФЛИКТОВ УПРАВЛЯЕМЫХ СЛОЖНЫХ СИСТЕМ

05.13.16 - применение вычислительной техники, ма-

диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель: доктор физико-математических

наук, профессор А.Н. Горбань

тематического моделирования и математических методов в научных исследованиях (в механике)

Красноярск - 1998

Содержание

Введение 1

Глава 1. Конкуренция подвижных объектов 5

§ 1.1. Модели взаимодействия 5

§ 1.2. Метод возврата. Оптимизация начальных координат 13

§ 1.3. Метод фиктивных потоков. Оптимизация начальных характеристик 21

§ 1.4. Комплексная задача размещения группы подвижных

объектов 23

§ 1.5. Управление направленными воздействиями 24

§ 1.6. Задачи оптимального преследования 26

Глава 2. Поиск стационарных целей 41

§ 2.1. Планирование слепого поиска. Метод упругих функций 41

§ 2.2. Оптимальное управление поиском 49

§ 2.3. Двухкритериальная задача 53

§ 2.4. К задаче коммивояжера 55

Глава 3. Поиск подвижных целей 65

§ 3.1. Постановка задачи и общие модели поиска. Разделение вычислительного ресурса. 65

§ 3.2. Схемы поиска и функционалы качества 74

§ 3.3. Нестационарный поиск и релаксация целей 79

Библиография 91

ВВЕДЕНИЕ

Данную работу объединяет тема конфликта сложных систем, включающих, в общем случае, множества управляемых подвижных объектов с характеристиками, зависящими как от времени, так и от управления [5365]. Основное внимание уделено при этом трем, выделенным в главы, группам задач:

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

2. Поиск стационарных целей. Предлагаемые модели позволяют свести некоторые известные задачи планирования поиска к задачам оптимального управления. Формализована задача управления поиском в реальном масштабе времени. Отдельно рассмотрена задача коммивояжера.

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

Таким образом, большая часть работы посвящена моделям и методам управления и оптимизации, сопровождаемым в необходимых случаях схе-

мами решений. Соответствующие же разрешающие алгоритмы специально не рассматривались, но реализуемы в большинстве случаев стандартными средствами.

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

В § 1.1 предложена и обоснована простейшая состоятельная модель вза-имодеиствия групп противодействующих объектов, связывающая характеристики объектов с характеристиками объектов противника, управлением и временем [53]. На примере этой модели демонстрируются далее предлагаемые в Главе 1, достаточно универсальные формализмы и методы.

В § 1.2 описывается метод быстрой направленной оптимизации начальных координат управляемых траекторий группы подвижных объектов. Идея метода состоит в построении сходящегося итеративного процесса, в шагах которого чередуются исходная задача "исчерпывания" и вспомогательная задача "восстановления" ("метод возврата"). Существенно, что предлагаемый метод применим ко всем задачам с непрерывными по времени функционалами качества. Приводится реализующий алгоритм. Описывается также метод оптимизации начальных координат, основанный на решении вспомогательной задачи конкуренции со специальным образом модифицированными динамическими ограничениями [63].

В § 1.3 предлагается метод расчета оптимального - в смысле минимизации избранного функционала качества - размещения данного ресурса подвижных объектов на заданных исходных позициях. Предлагаемый метод основан на дополнении исходной модели взаимодействия "коммутатором фиктивных потоков", позволяющим за время, малое по сравнению с временем управления, перераспределить данный ресурс объектов между исходными позициями ("метод фиктивных потоков", [63]).

В § 1.4 доказывается, что для дифференцируемых уравнений взаимодействия предложенные в §§ 1.2 и 1.3 метод модификации динамических ограничений и метод фиктивных потоков совместимы. Таким образом, формулируется и формализуется до метода комплексная задача оптимального начального размещения группы объектов, то есть задача параллельной оптимизации начальных координат и характеристик объектов [63].

В § 1.5 описаны две модификации модели взаимодействия, исследованной в § 1.1. Эти модели позволяют просто учесть управляемость направленных воздействий подвижных объектов и возможность разделения соответствующего ресурса данного объекта между подвижными объектами конкурента [54].

В § 1.6 рассмотрен новый подход к решению классических задач оптимального преследования. Предлагаемая модель [55] позволяет избавиться от дифференциальных уравнений траекторий объектов и формализовать общий случай задачи оптимального преследования в виде задачи вариационного исчисления или оптимального управления.

В Главе 2 решены некоторые задачи оптимального поиска стационарных целей, интерес к которым стимулировала монография Хеллмана [48].

В § 2.1 исследуется задача планирования поиска неподвижных целей с известными функциями плотностей распределения вероятностей. Долгое время не удавалось свести эту задачу к классическим задачам условной оптимизации. Непереборные решения существовали лишь для частных случаев или получались при физически необоснованных ограничениях. Основным препятствием была при этом невозможность аналитического учета пересечений и самопересечений полос поиска. Предлагаемый подход [62] позволяет формализовать общий случай задачи планирования поиска в виде задачи оптимального управления ("метод упругих функций").

В § 2.2 формализована задача управления поиском неподвижных целей в реальном масштабе времени. Даны правила перенормировки плотно-

стей вероятностей координат целей в моменты обнаружений. Показано, что оптимальная траектория поиска, управляемого в реальном масштабе времени, на интервале между двумя последовательными обнаружениями совпадает с траекторией оптимального плана (§ 2.1), рассчитываемого в момент последнего обнаружения [64].

В § 2.3 исследуется расширение формализованной в § 2.1 задачи оптимального поиска на случай, когда на области поиска задана плотность вероятности гибели поисковой единицы, т.е. когда результат поиска зависит не только от просмотренной к данному моменту области, но и от последовательности ее просмотра.

Порождаемая этим дополнительным условием двухкритериальная задача также сведена к задаче оптимального управления [64].

В заключающем Главу 2 параграфе 2.4 приводятся две простые, основанные на результатах Глав 1 и 2, математические модели, позволяющие записать задачу коммивояжера как задачу оптимального управления [64].

В Главе 3 (§ § 3.1-3.3) предложены некоторые достаточно общие модели поиска подвижных целей для систем автоматизированного отображения и анализа реальной физической обстановки. Соответствующие задачи (см., например [37] и [56]) порождаются необходимостью эффективного выборочного просмотра больших двумерных массивов текущей информации.

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

ГЛАВА 1

Конкуренция подвижных объектов

§ 1.1. Модели взаимодействия

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

Термин "характеристики" должен быть, конечно, определен. В самом деле, можно указать по крайней мере три типичных разнородных характеристики подвижного объекта (ПО): характеристика динамических параметров объекта, характеристика доставляемого ПО "полезного груза" и, наконец, характеристика подсистемы ПО, отвечающей за воздействие на противостоящий объект. Каждая из характеристик данного ПО в результате конкуренции, по определению, ухудшается по своему закону (ввиду разной надежности и защищенности элементов подсистем ПО; при этом надежность уменьшается как из-за воздействия противостоящих ПО, так и из-за воздействия изменяющихся пространственных факторов: физико-географических особенностей, радиационной обстановки и так далее). Кроме того, соответствующие подсистемы ПО зачастую взаимозависимы. Общая модель, рассматривающая ПО как систему, катастрофически усложняется - необходимы разумные упрощения.

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

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

Общий вид системы дифференциальных уравнений, описывающих принятую модель, будет таков:

где р, д - характеристики ПО; х^) - траектории соответствующих

объектов, причем по условию р < 0, д < 0.

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

Поскольку решаемые в настоящей работе задачи предполагают наличие двух игроков, управляющих произвольными количествами ПО, следует переписать уравнения (1.1) для общего случая:

где N и М - число ПО, управляемых игроками 1 и 2 соответственно; р = (РъР2, • • • 0ъ 02, • ■ ■ , 0м); ^(0 = ¿12(0» • ■ • > Ьагхш(г)У, ж2(0 =

(¿21(0, ¿22(0? • • • ?£2м(0)> ^2&(0 ~ траектории ПО, управляемых 1-

м и 2-м игроками. Аналогично (1.1) здесь для всех соответствующих к имеем рк <0, дк < 0.

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

Р = 1(0» Я2(0)>

д = Ф(р,д, Ж1(0,ж2(0),

(1.1)

р* = П(р,Х1(0»^(0)» 1 < к < дк = Фк(р, хи (0, ж2(0), 1 < к < М,

(1.2)

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

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

Рассмотрим два контрастных игровых сюжета и обоснуем для каждого цель конкуренции. Сюжет 1.

Игроки 1 и 2 располагают N и М подвижными объектами, для которых принята модель взаимодействия (1.2) (см. рис. 1.1). Игрок 1 дополнительно располагает М защищаемыми стационарными объектами. За время tf ПО игрока 2, двигаясь по заданным, известным игроку 1 траекториям, достигают защищаемых объектов (каждый - своей цели). При этом каждому защищаемому объекту наносится урон в размере Ckqk(tf), 1 < к < М, где Ck - заданные коэффициенты. Игрок 1 в течение времени tf противодействует игроку 2, ухудшая при этом характеристики своих ПО (начальные значения координат и характеристик ПО игрока 1 заданы).

Очевидно, цель игрока 1 состоит в том, чтобы минимизировать суммарный урон, наносимый игроком 2 защищаемым объектам, учитывая одновременно ухудшение характеристик своих ПО, то есть

М N

Z ckqk{tf) ~ Е Pk{tf) min. (1.3)

к=1 к=1

Сюжет 2.

Игроки 1 и 2 располагают N и М подвижными объектами, для которых

принята модель взаимодействия (1.2). Заданные траектории игрока 2 известны игроку 1 на любом интервале времени. За заданное время игрок 1 стремится провести свои ПО из заданной начальной точки А в заданную конечную точку В с минимальными суммарными потерями. При этом ПО игрока 1, достигающие конечной точки, считаются защищенными, то есть их характеристики стабилизируются (рис. 1.2).

Цель игры уже сформулирована:

N

тт. (1.4)

к=1

Таким образом, хотя модели взаимодействия совпадают, цели конкуренции (1.3) и (1.4), задаваемые сюжетами 1 и 2 соответственно, существенно разные. В рамках же одного сюжета цель конкуренции не зависит от того, какой вариант - задачу оптимизации или дифференциальную игру -мы рассматриваем. Сделаем одно необходимое замечание об исследуемых моделях конкуренции. В этой главе формализована задача оптимизации траекторий ПО игрока при вероятностно заданных траекториях ПО его конкурента. На погрешность, морфологически присущую любой модели, накладывается в этом случае неустранимая неопределенность, содержащаяся в самой постановке задачи. Неопределенность такого рода назовем "внутренними оценками модели".

Рассмотрим снова два взаимодействующих в трехмерном евклидовом пространстве объекта, характеристики которых р и д изменяются во времени в результате взаимодействия. В общем случае р ид связаны системой уравнений (1.1). Если взаимодействие объектов удовлетворяет принципу суперпозиции, то есть если функции ^иФ полилинейны пори д, то в (1.1) можно разделить переменные - характеристики и координаты - и уточнить вид уравнений:

где не оговорен знак ср\ и (р2.

Естественно полагать функцию , V = 1,2, симметричной, зависящей только от расстояния между подвижными объектами, то есть (р„(х 1; ¿2) = (ри(х2, Жх) = фи(\х1 — 1)- Обозначим Р = \Х1 — ¿2!, а функцию <р„(р) в дальнейшем будем считать монотонно убывающей по р.

Определение 1.1. Пусть х^) - траектории двух подвижных в

пространстве Е3 объектов, р = \х\ — Х2\~ расстояние между ними. Любая положительная, монотонно убывающая функция <р(р) называется функцией взаимодействия объектов.

Таким образом, приняв в задачах конкуренции производные р < 0, д < О, получим следующие уравнения взаимодействия:

р =-рд(р1(хъх2) ^ ^

Я = ~Р<1¥ 2(^1,^2).

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

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

Хотя модель (1.6) вполне обоснована физически, приведем один из возможных, описываемых ею реальных примеров взаимодействия.

Пусть два источника излучения, состоящие из большого количества однотипных излучателей р ид, создают в пространстве Е3 сферически симметричные поля р(р\(1) и д</?2(0> гДе ^ ~ расстояние от источника. Под влиянием взаимного облучения источники "распадаются" по закону ра-

диоактивного распада:

Р = Ч =

где к\ — цщ(р)„ к2 = №\{р) р ~ расстояние между источниками излучения. Таким образом, функция взаимодействия источников излучения, определяющая правые части уравнений (1.5), принимает вид (1.6). Если выполняется принцип суперпозиции источников излучения, то (р\(р) = <р2(р)- Однако, при учете в функции (р разной экранировки источников от облучения или, например, разной экранировки самих излучателей, обосновывается и случай ф\(р) ф (р2{р)-

Рассмотрим теперь следующую задачу. Игроки 1 и 2 располагают N и М управляемыми подвижными объектами соответственно, которые в начале игры при t = 0 находятся в точках 0), 1 < к < N и а^(0), 1 < к < М. Траектории объектов, управляемых игроком 2, известны и не изменяются за время игры; обозначим их через а&(£). Обозначим далее через траектории объектов, управляемых игроком 1. Уравнения взаимодействия объектов, учитывая (1.6), принимают вид

(1.7)

м