Лінійні ігрові задачі керування рухомими об’єктами

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Лінійні ігрові задачі керування рухомими об'єктами

Автореферат

дисертації на здобуття наукового ступеня кандидата фізико-математичних наук

Загальна характеристика роботи

Актуальність теми. Задачі взаємодії рухомих об'єктів, які функціонують в умовах конфлікту, виникають в різних областях економіки, військової та ракетної техніки, при побудові систем автоматичного керування. Серед цих задач можна виділити такі класи як ігри з конфліктом двох учасників, ігри переслідування групою гравців одного втікача, ігри взаємодії двох груп гравців. Розвиток методів розв'язання перелічених класів задач керування, що розширює можливості їх практичного застосування, є важливою й актуальною темою теорії конфліктно-керованих процесів. Зокрема, задачі конфлікту двох учасників важливі для моделювання системи літак - ракета. Для наведення ракети на ціль використовуються методи кривої погоні, паралельного переслідування, постійного кута упередження, пропорційної навігації. Останній є найбільш важливим з точки зору практичного застосування. Для систем з простим рухом метод пропорційної навігації займає проміжне положення між двома класичними методами - паралельного переслідування, з одного боку, та кривої погоні - з іншого. Метод паралельного зближення є частковим випадком відомого в теорії диференціальних ігор методу розв'язуючих функцій для зазначених систем, а метод кривої погоні випливає з правила екстремального прицілювання М.М. Красовського. Слід зазначити, що метод розв'язуючих функцій ідейно близький до першого прямого методу Л.С. Понтрягіна, який є універсальним методом розв'язання ігрових задач зближення. Аналіз стану проблеми виявив, що задачі обґрунтування правила пропорційного зближення з використанням методів теорії динамічних ігор є актуальним напрямком сьогоденних досліджень.

Складнішим випадком конфліктно-керованого процесу є задача переслідування одного втікача групою гравців. Уперше така задача у випадку простих рухів у класі контркерувань була розглянута в роботі Б.М. Пшеничного. Її розв'язок ілюструється простою геометричною побудовою: якщо початкове геометричне положення втікача належить внутрішності опуклої оболонки початкових положень переслідувачів, то зустріч гарантується за будь-яких рухів втікача. Якщо ж переслідувачі користуються лише позиційною інформацією, то проблема залишається відкритою. Подальший розвиток теорії групового переслідування пов'язаний з іменами А.О. Чикрія, Й.С. Раппопорта, М.Л. Григоренка, М.М. Петрова та С.Й. Тарлінського.

Природне узагальнення проблеми групового переслідування складає клас задач конфліктної взаємодії груп переслідувачів та втікачів. Мета переслідувачів - переловити всіх втікачів, мета втікачів - хоча б одному уникнути зустрічі. Одна з найбільш відомих задач даного класу - лінійна задача ухилення одного гравця від іншого. Вона була поставлена Л.С. Понтрягіним та Є. Ф. Міщенком. Проблеми диференціальних ігор за участю групи переслідувачів вивчались у роботах П.Б. Гусятнікова, М.С. Нікольского, В.В. Остапенка, М.Ю. Сатімова та А.О. Чикрія. В роботах останнього була висловлена гіпотеза про те, що якщо гра відбувається в n - вимірному евклідовому просторі з простими рухами гравців за рівних динамічних можливостей, то у випадку 2n переслідувачів і двох втікачів хоча б один із втікачів уникне зустрічі для будь-якого натурального n > 1. У випадку n = 2 цей результат був отриманий у 1987 р. А.О. Чикрієм та П.В. Прокоповичем. Актуальним залишалося доведення зазначеної гіпотези для n і 3. Дана робота присвячена розв'язанню виділених проблем.

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана у відповідності до плану наукових досліджень відділу оптимізації керованих процесів Інституту кібернетики імені В.М. Глушкова НАН України:

ВФК 165.05 «Оптимізація траєкторних задач керування рухомими об'єктами для прийняття рішень в екстремальних ситуаціях»;

ВФК 165.07 «Розробити методи аналізу та синтезу керування для еволюційних процесів, що функціонують в умовах невизначеності».

Мета і задачі дослідження. Мета роботи - застосування теорії динамічних ігор до розв'язання спеціальних задач керування в умовах конфліктної взаємодії. Предмет дослідження - ігрові задачі взаємодії: задача зближення для системи за участю двох гравців, задача групового переслідування одного втікача, задача ухилення групи від групи. Методи для побудови розв'язку вказаних задач базуються на ідеях теорії динамічних ігор.

Наукова новизна отриманих результатів:

для ігрової задачі зближення зі спеціальною динамікою проведено формалізацію та обґрунтування методу пропорційної навігації; встановлено зв'язок з методами розв'язуючих функцій та правилом екстремального прицілювання М.М. Красовського;

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

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

Практичне значення одержаних результатів полягає в тому, що запропоновані автором методи можуть бути використані для моделювання описаних задач ігрової взаємодії керованих об'єктів.

Особистий внесок здобувача. Основні результати, викладені в дисертації, отримані автором самостійно. У публікаціях, виконаних в співавторстві, А.О. Чикрію належить постановка задач та рекомендації щодо методів їх розв'язання. Особистий внесок здобувача полягає у формулюванні тверджень, проведенні доведень та ілюстрації теоретичних результатів на модельних прикладах.

Апробація результатів дисертації. Основні результати дисертаційної роботи доповідались на наступних конференціях:

перша національна науково-практична конференція студентів та аспірантів «Системний аналіз та інформаційні технології» (28 - 30 червня 1999 р., м. Київ);

друга національна науково-практична конференція студентів, аспірантів та молодих вчених «Системний аналіз та інформаційні технології» (28 - 30 червня 2000 р., м. Київ);

третя міжнародна науково-практична конференція студентів, аспірантів та молодих вчених «Системний аналіз та інформаційні технології» (1 - 3 липня 2001 р., м. Київ);

міжнародна конференція з прикладної математики, присвячена 65-річчю від дня народження Б.М. Пшеничного (25 - 28 червня 2002 р., м. Київ);

десята міжнародна конференція по автоматичному управлінню «Автоматика-2003» (15 - 19 вересня 2003 р., м. Севастополь);

науково-методична конференція «Сучасні проблеми математичного моделювання, прогнозування та оптимізації» (23 - 24 вересня 2004 р., м. Кам'янець-Подільський);

одинадцята міжнародна конференція по автоматичному управлінню «Автоматика-2004» (27 - 30 вересня 2004 р., м. Київ).

Публікації. Основні положення дисертації опубліковані у 13 наукових роботах, з яких 6 надруковано у фахових виданнях, що затверджені ВАК України.

Структура та обсяг дисертації. Дисертаційна робота складається із вступу, трьох розділів, висновків, списку використаних джерел з 98 найменувань. Робота містить 21 рисунок. Повний обсяг роботи - 122 сторінки.

Основний зміст роботи

У вступі обґрунтовується актуальність вибраної теми, формулюється мета роботи, зазначається наукова новизна отриманих результатів та висвітлюється їх теоретична і практична цінність.

У першому розділі досліджена ігрова задача зближення для конфліктно-керованого процесу за участю двох гравців за різних припущень щодо динаміки руху. Розділ починається з огляду літератури та загального аналізу проблем, що виникають при розв'язанні ігрових задач. У підрозділі 1.1 наведено постановки задач, які складають об'єкт дослідження. Підрозділи 1.2 та 1.3 присвячені короткому викладенню методів розв'язуючих функцій та екстремального прицілювання М.М. Красовського у частині, необхідній для обґрунтування методу пропорційної навігації.

У підрозділі 1.4 розглянуто задачу точної зустрічі одного гравця іншим в умовах динаміки простого руху.

Керування втікача належить кулі. Керування переслідувача вибирається з кулі радіусом: Множини всіх таких керувань називаються допустимими і позначаються та відповідно. При цьому втікач використовує програмні, а переслідувач - контр-керування.

Наступна лема доводить, що в цьому випадку вздовж траєкторії руху точки розв'язуюча функція може бути виражена через максимум по множині. Показано, що такий максимум існує та єдиний.

Лема 1.3. Нехай для початкового стану процесу (1) виконується. Якщо для керування втікача, керування переслідувача визначається формулою (3), то для точок траєкторії має місце рівність

Наступним етапом роботи є дослідження зв'язку та методу кривої погоні. Для цього введемо функцію, де, і. В лемі 1.4 доведено, що керування кривої погоні, яке для процесу (1) має вигляд, максимізує функцію на траєкторії руху.

Користуючись доведеними властивостями відображення можна описати керування зазначених методів через максимум від по відповідних множинах.

У дисертації показана допустимість та коректність визначення цих функцій. Зазначимо, що у випадку, коли, де, відображення і збігаються. Таким чином, керування методів виражені через, що дозволяє визначити керування методу пропорційної навігації. Наведемо класичне формулювання методу пропорційної навігації7 для системи (1) на площині. Зафіксуємо прямокутну систему координат XOY. Позначимо кут між вектором і віссю OX, - кут між вектором і віссю OX.

При значенні (у цьому випадку краще переписати формулу у вигляді і, вважаючи, що, одержуємо) - це метод паралельного переслідування. Зафіксуємо момент часу, вектори і, тоді будуть визначені керування паралельного переслідування та кривої погоні.

Теорема 1. Нехай для початкового стану процесу (1) виконується. Тоді для будь-якого моменту часу та значень, визначене керування методу пропорційної навігації, де. Якщо переслідувач використовує це керування, то траєкторія може бути приведена з початкового стану на термінальну множину не пізніше, ніж за час за будь-яких допустимих керувань втікача.

Доведення теореми ґрунтується на тому, що траєкторія системи при керуванні методом пропорційної навігації збігається з траєкторією при керуванні методом кривої погоні для деякого руху втікача.

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

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

Теорема 2. Нехай для початкового стану процесу (5) виконується. Тоді для будь-якого моменту часу та значень, визначене керування методу пропорційної навігації, де. Якщо переслідувач використовує це керування, то траєкторія може бути приведена з початкового стану на термінальну множину не пізніше, ніж за час за будь-яких допустимих керувань втікача.

Другий розділ присвячений дослідженню задачі групового переслідування у випадку позиційної інформованості. У підрозділі 2.1 викладається постановка задачі.

Для розв'язання цієї задачі спочатку проведемо допоміжні побудови векторного поля, на основі якого буде визначена стратегія переслідування.

У підрозділі 2.2 визначається багатозначне відображення, яке характеризує геометричний стан гравців. Для фіксованого моменту часу t положення гравців визначається набором векторів та y. Під опуклою оболонкою, натягнутою на точки, будемо розуміти множину точок та позначати її. Геометричні стани гравців, для яких виконується, де множина внутрішніх точок, будемо називати не виродженими.

Стратегія переслідування буде будуватися на основі методу розв'язуючих функцій та з використанням векторного поля. Будемо вважати, що геометричний стан гравців такий, що виконуються співвідношення, тоді за наслідком до леми 2.1 можна вибрати кут достатньо малим, щоб виконувалось. Не обмежуючи загальності можна вважати, що.

Тепер, маючи на увазі, що для кожної точки фазового простору визначений вектор, застосуємо метод розв'язуючих функцій для визначення керування переслідувачів. Розглянемо квадратне рівняння, де. Розв'язком цього рівняння є розв'язуюча функція. Відповідні керування переслідувачів дорівнюють. Якщо визначене керування, то можна оцінити час зустрічі для гри, яка починається з точки.

За умови, що, час зустрічі, в іншому випадку покладемо. Якщо, що відповідає ситуації, коли, і керування втікача буде дорівнювати, то зустріч відбудеться в момент часу. Нехай. У цьому разі перевизначимо керування, щоб зустріч відбувалася одночасно. Це можна зробити «вповільнивши» рух гравця.

Таким чином, кожній парі можна зіставити тетраедр, причому єдиним чином. Цей тетраедр має наступну властивість: площина, де, відділяє одного з переслідувачів, від решти гравців. Якщо проводити аналогію з плоским випадком «4 проти 2», то можна зробити висновок, що вказаний тетраедр грає роль діагоналі плоского чотирикутника, що є опуклою оболонкою двох переслідувачів. Позначимо множину індексів тетраедрів K.

Визначимо класи геометричних станів гравців, які не перетинаються та повністю вичерпують всі можливі розташування, що виникають у ситуації.

Означення 3.1. Назвемо положенням 1 таке розташування гравців, що:

1. Не існує індексу.

2. Існує індекс, такий, що для всіх.

Означення 3.2. Назвемо положенням 2 таке розташування гравців, що:

1. Не існує індексу.

2. Не існує індексу, такого, що для всіх.

3. Існує індекс і єдиний індекс, такі, що.

Означення 3.3. Назвемо положенням 3 таке розташування гравців, що існує і єдиний індекс для якого.

Означення 3.4. Назвемо положенням 4 таке розташування гравців, що існують індекси, такі, що.

Означення 3.5. Назвемо положенням 5 решту можливих розташувань гравців.

У підрозділі 3.3 доводиться ряд допоміжних тверджень. Наведемо стислий опис головних результатів:

1. Існує стратегія втікачів, за якої гравці, знаходячись у положенні 5, переходять в одне з положень 1, 2, 3, 4 незалежно від стратегій переслідувачів за час, не більше. При цьому відстань між втікачами завжди більше позитивного числа. Величини і визначаються тільки початковим геометричним розташуванням гравців. Твердження доведено в лемі 3.2.

2. Показано, що існують керування втікачів, такі, що за якнайгірших, в деякому розумінні, стратегіях переслідувачів відстань між втікачами, принаймі, не зменшиться. Твердження доведено в лемі 3.3. Дане твердження є опорним при доведенні леми 3.5.

3. Твердження, опорне для розв'язання задачі. Визначає та обґрунтовує стратегію втечі для певного класу геометричних станів. Доводиться, що за будь-яких рухів переслідувачів гравці не переходять в положення 5 та при цьому відстань між втікачами не зменшується. Твердження доведено в лемі 3.5.

4. Вказується стратегія для положення 1. При цій стратегії відстань між втікачами не зменшується, вони уникають зустрічі за будь-яких рухів переслідувачів, гравці можуть перейти тільки в одне з положень 2, 3, 4. Твердження доведено в лемі 3.6.

5. Аналогічні п. 4 твердження для положень 2, 3, 4 доводяться в лемах 3.7, 3.8 та 3.9.

У підрозділі 3.4 доводиться теорема, за допомогою якої розв'язується поставлена задача втечі двох гравців від шести переслідувачів з рівняннями руху (13) в тривимірному просторі.

Теорема 4. Нехай заданий конфліктно-керований процес (13). Тоді для початкового стану можна вказати стратегію втікачів таку, що за довільної стратегії переслідувачів для будь-якого моменту часу виконується, для всіх індексів, тобто зустріч неможлива.

Висновки

У дисертації одержано нові науково обґрунтовані результати в галузі динамічних ігор зближення - ухилення для конфліктно-керованих процесів взаємодії груп керованих об'єктів.

Основні результати дисертаційної роботи:

1. Для ігрової задачі зближення зі спеціальною динамікою проведена формалізація методу пропорційної навігації. Показано зв'язок з методами розв'язуючих функцій та екстремального прицілювання М.М. Красовського.

2. Доведено, що використання керування цього методу гарантує закінчення гри не пізніше певного моменту часу за будь-яких протидій втікача.

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

4. Для задачі взаємодії двох груп керованих об'єктів доведено справедливість гіпотези про те, що якщо гра відбувається в тривимірному евклідовому просторі з простими рухами гравців за рівних динамічних можливостей, то у випадку шести переслідувачів і двох втікачів хоча б один з втікачів уникне зустрічі.

Запропоновані методи можуть бути застосовані до дослідження таких задач конфліктного керування рухомими об'єктами як ігри з конфліктом двох учасників, ігри переслідування групою гравців одного втікача, ігри взаємодії двох груп гравців.

Основні положення дисертації опубліковані в таких працях

1. Игнатенко А.П. Решение одного класса задач взаимодействия групп управляемых объектов на плоскости // Кибернетика и вычисл. техника. - 2002. - Вып. 135. - С. 19 - 30.

2. Игнатенко А.П., Чикрий А.А. Задача об убегании двух управляемых объектов от группы преследователей в трехмерном пространстве // Проблемы управления и информатики. - 2002. - №1. - С. 5 - 31.

3. Игнатенко А.П. Об одной задаче позиционного группового преследования // Теория оптимальных решений. - 2004. - №3. - С. 96 - 101.

4. Игнатенко А.П., Чикрий А.А. К обоснованию метода пропорциональной навигации в задаче простого движения // Проблемы управления и информатики. - 2004. - №1. - С. 26 - 36.

5. Игнатенко А.П., Чикрий А.А. Метод пропорциональной навигации в задаче простого преследования // Докл. НАН Украины. - 2004. - №7. - С. 67 - 71.

6. Игнатенко А.П., Чикрий А.А. Метод пропорциональной навигации в одной задаче преследования // Проблемы управления и информатики. - 2004. - №6. - С. 5 - 11.

7. Ігнатенко О.П. Метод розв'язку задачі взаємодії груп керованих об'єктів в // Тези докл. першої нац. наук.-практ. конф. студентів та аспірантів «Систем-ний аналіз та інформаційні технології» (28 - 30 червня 1999 р., м. Київ). - К.: НТУУ «КПІ», 1999. - С. 92.

8. Игнатенко А.П. Решение одной задачи взаимодействия групп управляемых объектов в пространстве // Збірка тез доп. учасників ІІ нац. наук.-практ. конф. студентів, аспірантів та молодих вчених «Системний аналіз та інформаційні технології» (28 - 30 червня 2000 р., м. Київ). - К.: НТУУ «КПІ», 2000. - С. 204.

9. Игнатенко А.П. К вопросу взаимодействия групп управляемых объектов // Збірка тез доп. учасників ІІІ міжнар. наук.-практ. конф. студентів, аспірантів та молодих вчених «Системний аналіз та інформаційні технології» (1 - 3 липня 2001 р., м. Київ). - К.: НТУУ «КПІ», 2001. - Ч. 1. - С. 144.

10. Ignatenko A. Solution of problem of group of controlled objects cooperation in three-dimensional space // Междунар. конф., посвященная 65-летию со дня рождения Б.Н. Пшеничного: Тез. докл. - Киев: Изд-во НТУУ «КПИ», 2002. - С. 114.

11. Чикрий А.А., Игнатенко А.П. О задаче взаимодействия групп управляемых объектов в пространстве // Матеріали 10-ї міжнар. конф. по автоматичному управлінню «Автоматика-2003» (м. Севастополь, 15-19 вересня 2003 р.): В 3 т. - Севастополь: Вид-во СевНТУ, 2003. - Т. 1. - С. 196.

12. Игнатенко А.П., Чикрий А.А. Решение одной задачи позиционного группо-вого преследования // Зб. праць наук.-метод. конф. «Сучасні проблеми математичного моделювання, прогнозування та оптимізації» (м. Кам'янець-Подільський, 23 - 24 вересня 2004 р.). - Кам'янець-Подільський: КПДУ: Інформаційно-видавничий відділ, 2004. - С. 254 - 255.

13. Чикрий А.А., Игнатенко А.П. О методе пропорциональной навигации в задаче простого преследования // Матеріали 11-ї міжнар. конф. по автоматичному управлінню «Автоматика-2004» (м. Київ, 27-30 вересня 2004 р.): В 3 т. - Севастополь: Вид-во СевНТУ, 2004. - Т. 3. - С. 11.

Размещено на Allbest.ru