Методы распределения целей между роботами группы в условиях противодействия

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

Методы распределения целей между роботами группы в условиях противодействия

В.С.Лазарев, И.В. Черногоров

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

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

Введение

Проблема распределения целей обычно возникает в ходе выполнения многоцелевого задания группой роботов. Начало исследованиям в этой области было положено еще в 50-60-х годах прошлого века [1], [2]. В монографии [3] приведен подробный обзор современных методов целераспределения. В результате обзора подчеркивается, что даже для задач сравнительно небольшого масштаба не существует общего алгоритма решения. Таким образом, каждый конкретный случай требует отдельного рассмотрения.

Постановка задачи

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

В область L2 в произвольные моменты времени влетают нападающие Ti, задача которых попасть в область L1. Задача защитников Rj - перехватить нападающих Ti. В каждый момент времени защитники Rj знают расположение нападающих Ti. В нашем случае, i=j=5. Критерий: уничтожение всех нападающих минимальным числом защитников. Чтобы повысить эффективность защиты области от атакующих ставится задача рассмотреть три метода целераспределения: на базе системы приоритетов, на базе генетического алгоритма и метода роящихся частиц.

Целераспределение на основе системы приоритетов

В работе [4] описан алгоритм динамического распределения целей в зависимости от расстояния между целью и роботом. Этот алгоритм неплохо работает при случае, когда цели неподвижны, однако в условиях противодействия необходимо вводить систему приоритетов. Эта система должна оперативно оценивать уровень опасности, исходящий от цели (атакующего робота). Как считают Лазарев В.С. и Агаджанов Д.Э [5], при назначении приоритета для цели должно быть учтено несколько факторов (рис. 1).

Система приоритета учитывает:

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

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

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

Рис. 1. - Факторы системы приоритета

- активное преследование - преследуется ли потенциальная цель каким-либо роботом защитником, если да, оценивает, каково расстояние между роботами в погоне. Если расстояние между первой парой (робот и цель) минимум на 30% больше чем расстояние между второй парой преследование передается новому роботу. Если расстояние от бывшего преследователя до его потенциальной цели на 0,5 от l1 больше чем l1, цели не меняются. Итоговая формула выглядит следующим образом(1):

 (1)

где:

l1 - расстояние между первой парой; l2- расстояние между второй парой.

l3 - расстояние от бывшего преследователя до его потенциальной цели.

Целераспределение на основе модификации МРЧ

Базовая ММ МРЧ [6, 7] направлена на поиск множества экстремальных значений. Для применения МРЧ для поставленной задачи целераспределения из базовой математической модели МРЧ был исключён ряд уравнений (например, ускорение не может участвовать в задаче целераспределения). В итоге модель МРЧ переработана в уравнение силы притяжения (2) (защитники начинают «притягиваться» к атакующим):

(2)

где: G- притяжение защитника к самому опасному атакующему;Li - притяжение защитников к остальным атакующим; gQ - субоптимизационный параметр, необходимый для корректной настройки сил притяжения в задачах с различными радиусами действий и скоростями роботов, miQ- изначально прототип массы гравитационного центра, однако в данной модели это «степень опасности» атакующего; riQ- расстояние между положением защитником и диффузным положением целевой точки притяжения - атакующего;еQ - естественный ограничитель, который исключит ошибочные вычисления в моделировании.

а б

Рис. 2. - Иллюстрация параметров модели: а) демонстрация изменения сил притяжения; б) демонстрация изменения степени опасности

На рис. 2-а видно, что при движении защитника его сила притяжения к выбранному атакующему растёт, а к двум другим уменьшается, пропорционально расстоянию между роботами.

На рис. 2-б видно, что показатель опасности роботов вне области радара равняется 0, а внутри области растёт с каждой итерацией. Если атакующий располагается на границе базы, то его miQ максимален.

Генно-хромосомная модель целераспределения

Сущность одного из вариантов решения задачи целераспределения заключается в её приведении к генно-хромосомному виду [8-10] и последующему решению данной задачи посредством ЭГА. При этом в качестве хромосомы выступит набор защитников (рис. 3). Количество генов, входящих в состав хромосом неизменно и равно защитников.

Под геном будем подразумевать каждого защитника с его индивидуальными параметрами. Основной из них - бинарный параметр включения или исключения из рассматриваемой генно-хромосомной структуры. “0” - обозначает то, что в настоящий момент времени защитнику (на Рис.3 выделены бледно-голубым цветом), не будет присвоена цель в виде атакующего, “1” - что данному защитнику в обязательно будет присвоена цель (на Рис.3 выделены синим цветом).

Цели выделены красным цветом. Стоит заметить, что на данной стадии описания алгоритма присвоение целей происходит в случайном порядке. Если защитнику не присвоена цель, он не участвует в бою. Если цель защитнику присвоена, происходит инициализация следующих параметров защитника (гена хромосомы):

координаты текущей позиции защитника (xзащ, yзащ, zзащ);

координаты текущей позиции нападающего (xнап, yнап, zнап), который выступает в качестве цели для рассматриваемого защитника;

Рис. 3. - Модель ЭГА

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

На первом этапе предложенного подхода производится инициализация первой популяции, где происходит присвоение статуса каждому защитнику (гену) “0” или “1”, из которых в дальнейшем складывается хромосома. На рис. 3 можно наблюдать пример хромосомы - все гены (защитники) связаны между собой фиолетовой линией. Фиолетовая линия характеризует последовательность генов (защитников, в которой они представлены в формируемых для ЭГА хромосомах). На рис. 3. хромосома имеет вид “111001110”. Стоит заметить, что изменение статусов защитников может происходить только посредством операторов кроссовера или мутации. После инициализации популяции, каждому гену (защитнику), входящему в состав хромосомы со статусом “1” присваивается случайная цель. После производится подсчёт суммарного расстояния, которое будет преодолено всеми защитниками до вступления с нападающим в бой - это главный критерий отбора особи (варианта целераспределения) для ЭГА.

В ходе выполнения ЭГА производится выбор наиболее оптимального варианта хромосомы целераспределения, именно её модель в итоге используется в реальном бою. Стоит заметить, что в связи с тем, что рассматриваемая система является динамической, предложенную выше последовательность действий необходимо производить один раз в определенный промежуток времени.

Сравнение результатов

Для каждого метода целераспределения (на основе системы приоритетов, на основе МРЧ и на основе ЭГА) было проведено 20 экспериментов. 10 из них проводились с неактивной, а 10 с - активной системой целераспределения.

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

Результаты экспериментов представлены в виде диаграмм на рис. 4 и 5. Как можно заметить из результатов на рис. 4, все три метода значительно (более чем на 70%) повышают эффективность защиты области от атакующих роботов противника. Наибольшую эффективность показал метод на базе системы приоритетов, из 10 экспериментов 8 завершились победой защитников.

а) б)

Рис. 4. - Количество побед: а) с неактивной системой целераспределения; б) с активной системой целераспределения.

а) б)

Рис. 5. - Среднее число выживших защитников: а) с неактивной системой целераспределения; б) с активной системой целераспределения.

python групповое управление противодействие

Второй важный параметр - количество выживших защитников в выигранных боях (рис.5). Здесь лучшие результаты также показал метод на основе приоритетов, однако необходимо также отметить метод на основе МРЧ, при котором в проигранных боях оставался в живых только 1 атакующий. Это лучший результат среди трех методов, худший по этому параметру метод на основе приоритетов. Однако по совокупности трех факторов, лучшие результаты показал метод на основе системы приоритетов.

Заключение

В заключении хотелось бы отметить то, что данные моделирования справедливы для случая, когда невелико число роботов защитников и атакующих (по 5-7 с каждой стороны). С увеличением порядка размера защищаемой области, а также числа атакующих роботов и защитников, могут существенно измениться результаты работы методов целераспределения, описанных в данной работе.

В перспективе описанные в работе методы, при условии использования вместо модели кинематики модели реального БПЛА, например гексакоптера [11], могут использоваться для решения реальных задач по защите области от роботов-противников.

Литература

1. Day R. Allocating Weapons to Target Complexes by Means of Nonlinear Programming // Operations Research 14. - 1966. pp. 992-1013.

2. Den G. Broeder, Ellison R., Emerling L. On Optimal Target Assignments // Operations Research 7. 1959. pp. 322-326.

3. Белоглазов Д.А., Гайдук А.Р., Косенко Е.Ю., Медведев М.Ю., Пшихопов В.Х., Соловьев В.В., Титов А.Е., Финаев В.И., Шаповалов И.О.Групповое управление подвижными объектами в неопределенных средах. // Москва: Физматлит. 2015. 304 с.

4. Медведев М.Ю., Лазарев В.С. Метод планирования движения группы подвижных объектов с использованием динамических репеллеров и целераспределения // Научный вестник НГТУ, Новосибирск. вып. 1(66). 2017. С. 41-52.

5. Лазарев В.С., Агаджанов Д.Э Использование графоаналитических методов для формирования траектории группы подвижных объектов в двумерной среде // Труды СПИИРАН. 2016. Вып. 45. C. 45-57.

6. Strongin R. G. Algorithms for multi-extremal mathematical programming problems // Journal of Global Optimization, vol. 2. 1992. pp. 357-378.

7. Neydorf R. , Chernogorov I., Polyakh V., Yarakhmedov O., Goncharova J., Neydorf A. Formal Characterization and Optimization of Algorithm for the Modelling of Strongly Nonlinear Dependencies Using the Method "Cut-Glue" Approximation of Experimental Data // SAE Technical Paper, 2016, URL: papers.sae.org/2016-01-2033.

8. Fogel D. B. Evolutionary Computation: The Fossil Record // New York: IEEE Press, 1998, URL: eu.wiley.com/WileyCDA/WileyTitle/productCd-0780334817.html.

9. Barricelli N. A. Numerical testing of evolution theories. Part II. Preliminary tests of performance, symbiogenesis and terrestrial life // ActaBiotheoretica. 1963. pp. 99-126.

10. Пучков Е. В. Сравнительный анализ алгоритмов обучения искусственной нейронной сети // Инженерный вестник Дона, №4, 2013, URL: ivdon.ru/ru/magazine/archive/n4y2013/2135.

11. Кульченко А.Е., Лазарев В.С., Медведев М.Ю. Метод управления движением гексакоптера в трехмерной среде с препятствиями на базе динамических отталкивающих сил // Инженерный вестник Дона, №4, 2016, URL: ivdon.ru/ru/magazine/archive/n4y2016/3828.

1. Day R. Operations Research. 1966. № 14. pp. 992-1013.

2. Den Broeder G., Ellison R., Emerling L. Operations Research 1959. № 7. pp. 322-326.

3. Beloglazov D.A., Guzik V.F., KosenkoE.Yu., Krukhmalev V.A., Medvedev M.Yu., Pereversev V.A., PshikhopovV.Kh., Pyavchenko A.O., Saprykin R.V., Solovjev V.V., Finaev V.I., ChernukhinYu.V., Shapovalov I.O. Gruppovoe upravlenie podvizhnymi objektami v neopredelennyh sredah [Group control of vehicles in undetermined environments]. M.: Fizmatlit, 2015, 304 p.

4. Medvedev M.YU., Lazarev V.S. Science bulletin of NSTU, 2017, №. 1(66). pp. 41-52.

5. Lazarev, V.S., Agadjanov, D.E. SPIIRAS Proceedings, 2016. № 2(45). pp. 45-57.

6. Strongin R. G. Journal of Global Optimization, 1992. vol. 2. pp.357-378.

7. Neydorf R. , Chernogorov I., Polyakh V., Yarakhmedov O., Goncharova J., Neydorf A. SAE Technical Paper, 2016, URL: papers.sae.org/2016-01-2033/.

8. Fogel D. B. Evolutionary Computation: The Fossil Record. New York: IEEE Press, 1998, URL://eu.wiley.com/WileyCDA/WileyTitle/productCd-0780334817.html.

9. Barricelli N. A. Numerical testing of evolution theories. Part II. Preliminary tests of performance, symbiogenesis and terrestrial life. ActaBiotheoretica. 1963. pp. 99-126.

10. Puchkov E. V. Inћenernyj vestnik Dona (Rus), №4, 2013. URL: ivdon.ru/ru/magazine/archive/n4y2013/2135.

11. Kulchenko A.E., Lazarev V.S., Medvedev M.YU. Inћenernyj vestnik Dona (Rus), №4, 2016, URL: ivdon.ru/ru/magazine/archive/n4y2016/3828.

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