Methods of simulation of behavior of agents in multi-agent system “Navigation”

The problem of pursuit on a plane from the point of view multi-agent approach is researched. Setting up of the task of pursuit is carried out and simulation methods of behaviour of the agents, realized in multi-agent system “Navigation” are stated, which intended for modelling of processes of pursui...

Full description

Saved in:

Bibliographic Details
Date:	2025
Main Author:	Yalovets, A.L.
Format:	Article
Language:	rus
Published:	Інститут програмних систем НАН України 2025
Subjects:	UDC 004.942+623.465
Online Access:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/714
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Problems in programming

Institution

Problems in programming

id	pp_isofts_kiev_ua-article-714
record_format	ojs
resource_txt_mv	ppisoftskievua/d6/124adafd259bed863ddbd4d93302f9d6.pdf
spelling	pp_isofts_kiev_ua-article-7142025-04-09T22:22:32Z Methods of simulation of behavior of agents in multi-agent system “Navigation” Методы моделирования поведения агентов в мультиагентной системе "Навигация" Yalovets, A.L. UDC 004.942+623.465 УДК 004.942+623.465 The problem of pursuit on a plane from the point of view multi-agent approach is researched. Setting up of the task of pursuit is carried out and simulation methods of behaviour of the agents, realized in multi-agent system “Navigation” are stated, which intended for modelling of processes of pursuit on the sea of the ships-infringers by the ships of a coast guard.Prombles in programming 2014; 2-3: 212-220 Исследуется проблема преследования на плоскости с точки зрения мультиагентного подхода. Выполняется постановка задачи преследования и излагаются методы моделирования поведения агентов, реализованные в мультиагентной системе «Навигация», предназначенной для моделирования процессов преследования на море кораблей-нарушителей кораблями береговой охраны.Prombles in programming 2014; 2-3: 212-220 Інститут програмних систем НАН України 2025-04-09 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/714 PROBLEMS IN PROGRAMMING; No 2-3 (2014); 212-220 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2-3 (2014); 212-220 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2-3 (2014); 212-220 1727-4907 rus https://pp.isofts.kiev.ua/index.php/ojs1/article/view/714/766 Copyright (c) 2025 PROBLEMS IN PROGRAMMING
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2025-04-09T22:22:32Z
collection	OJS
language	rus
topic	UDC 004.942+623.465
spellingShingle	UDC 004.942+623.465 Yalovets, A.L. Methods of simulation of behavior of agents in multi-agent system “Navigation”
topic_facet	UDC 004.942+623.465 УДК 004.942+623.465
format	Article
author	Yalovets, A.L.
author_facet	Yalovets, A.L.
author_sort	Yalovets, A.L.
title	Methods of simulation of behavior of agents in multi-agent system “Navigation”
title_short	Methods of simulation of behavior of agents in multi-agent system “Navigation”
title_full	Methods of simulation of behavior of agents in multi-agent system “Navigation”
title_fullStr	Methods of simulation of behavior of agents in multi-agent system “Navigation”
title_full_unstemmed	Methods of simulation of behavior of agents in multi-agent system “Navigation”
title_sort	methods of simulation of behavior of agents in multi-agent system “navigation”
title_alt	Методы моделирования поведения агентов в мультиагентной системе "Навигация"
description	The problem of pursuit on a plane from the point of view multi-agent approach is researched. Setting up of the task of pursuit is carried out and simulation methods of behaviour of the agents, realized in multi-agent system “Navigation” are stated, which intended for modelling of processes of pursuit on the sea of the ships-infringers by the ships of a coast guard.Prombles in programming 2014; 2-3: 212-220
publisher	Інститут програмних систем НАН України
publishDate	2025
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/714
work_keys_str_mv	AT yalovetsal methodsofsimulationofbehaviorofagentsinmultiagentsystemnavigation AT yalovetsal metodymodelirovaniâpovedeniâagentovvmulʹtiagentnojsistemenavigaciâ
first_indexed	2025-07-17T09:58:19Z
last_indexed	2025-07-17T09:58:19Z
_version_	1838410110484873216
fulltext	Інтелектуальні інформаційні технології © А.Л. Яловец, 2014 212 ISSN 1727-4907. Проблеми програмування. 2014. № 2–3. Спеціальний випуск УДК 004.942+623.465 МЕТОДЫ МОДЕЛИРОВАНИЯ ПОВЕДЕНИЯ АГЕНТОВ В МУЛЬТИАГЕНТНОЙ СИСТЕМЕ «НАВИГАЦИЯ» А.Л. Яловец Институт программных систем НАН Украины Украина, 03680, Киев, проспект Академика Глушкова, 40, тел. (044) 526 15 38, E-mail: yal@isofts.kiev.ua Исследуется проблема преследования на плоскости с точки зрения мультиагентного подхода. Выполняется постановка задачи пре- следования и излагаются методы моделирования поведения агентов, реализованные в мультиагентной системе «Навигация», пред- назначенной для моделирования процессов преследования на море кораблей-нарушителей кораблями береговой охраны. The problem of pursuit on a plane from the point of view multi-agent approach is researched. Setting up of the task of pursuit is carried out and simulation methods of behaviour of the agents, realized in multi-agent system “Navigation” are stated, which intended for modelling of processes of pursuit on the sea of the ships-infringers by the ships of a coast guard. Введение Задача преследования на плоскости является известной и достаточно глубоко изученной (см., например, [1, 2]), причем в основном ее исследования выполняются в рамках теории дифференциальных игр [3, 4]. Вместе с тем, данная задача может успешно решаться и с помощью методов и моделей, разрабатываемых в рамках мультиагентного подхода. При этом, окружающая среда рассматривается как динамическая система, а убегаю- щие и преследователи – как агенты, действующие в такой системе. Цель данной статьи – это постановка задачи преследования на плоскости с точки зрения мультиагентного подхода и изложение методов моделирования по- ведения агентов, реализованных в мультиагентной системе «Навигация», предназначенной для моделирования процессов преследования на море кораблей-нарушителей кораблями береговой охраны. 1. Постановка задачи преследования на плоскости с точки зрения мультиагентного подхода Опираясь на традиционную постановку задачи преследования на плоскости, рассматриваемую в рамках теории дифференциальных игр и изложенную, например, в [2], приведем ее уточнения, позволяющие, с одной стороны, сформулировать ее в терминах мультиагентного подхода, с другой, – определить перечень математи- ческих методов, требующих разработки. Пусть на плоскости задано выпуклое множество S , соответствующее динамической среде, в пределах которой действуют агенты. Содержательно множество S можно интерпретировать как морской участок, в пре- делах которого действуют корабли различного назначения (интерпретируемые как агенты). В общем случае можно выделить три категории агентов: 1) агенты-убегающие, формирующие множество },,,{ 21 nEEEE  ; 2) агенты-преследователи, формирующие множество },,,{ 21 mPPPP  ; 3) прочие агенты, формирующие множество A , не являющиеся ни убегающими, ни преследователями, но также находящиеся в S . Далее нас будут интересовать только агенты первых двух категорий, хотя в некоторых компонентах за- дачи преследования влияние агентов множества A будет учитываться (например, в задачах маневрирования). Подчеркнем, что влияние агентов множества A содержательно означает учет природы, геометрии и поведения объектов, которым такие агенты соответствуют. В частности, такие объекты могут быть как движущимися, так и неподвижными, как точечными (например, корабли), так и площадными (например, острова). В отличие от традиционной постановки задачи [2], в нашем случае рассматривается не один, а множе- ство убегающих E , где 1)(card E . Это обусловливает необходимость рассмотрения разных групп kGr пре- следователей iP (где PPi  , )(card)(card EP  ), каждая из которых является прототипом наряда (из традици- онной постановки) и преследует вполне определенного убегающего )( EEE jj  . Введем множество групп },,,{ 21 nGrGrGrGr  , где каждая kGr содержит некоторое количество )( PPP ii  и одного )( EEE jj  , т. е. для любой группы kGr выполняется условие, что 2)(card kGr . Для любых двух групп справедливо, что }{1  kk GrGr . Ясно, что EPGrGrGr n  21 , где )(card)(card EGrn  . Каждый агент ji EP , начинает движение в момент времени 0t , имеет текущие координаты в ортого- нальной системе координат и перемещается в S , находясь в состоянии простого движения в любой момент времени 0t , предшествующий его возможной остановке (вследствие захвата либо иных причин). Параметры, Інтелектуальні інформаційні технології 213 характеризующие состояние і-го агента множеств EP, в момент времени 0t , однозначно описываются кор- тежем  iiiiiiiii vvyxBnClGmid },,{},,{,,,, max , где iid – уникальный идентификатор і-го агента; iGm – размер объекта, соответствующего і-му агенту (домен допустимых значений: «большой», «средний», «малый»), iCl – класс объекта, соответствующего і-му агенту (домен допустимых значений: «военный», «гражданский»), iBn – принадлежность объекта, соответствующего і-тому агенту (домен допустимых значений: «свой», «чужой», «не- распознанный», «береговая охрана»), },{ ii yx – текущие координаты і-го агента; },{ max ii vv – текущая и макси- мально возможная скорость движения і-го агента; i – текущий угол движения і-го агента в ортогональной системе координат. Таким образом, в качестве параметров движения і-го агента рассматривается не линейная скорость, а скорость iv и угол движения i , поскольку в произвольный момент времени 0t любая траекто- рия движения может быть аппроксимирована ломаной с конечным числом вершин, где любой фрагмент этой ломаной, являющийся прямой, может быть однозначно описан с помощью именно этих двух параметров, зна- чения которых в данный момент времени являются постоянными. Будем говорить, что преследователи, принадлежащие отдельной группе kGr , догнали убегающего jE ( kj GrE  ), если хотя бы один из преследователей ki GrP  оказался в зоне захвата убегающего jE , а сам jE при этом считается захваченным. Отметим, что мы не используем словосочетания «осуществил встречу», применяемого в традиционной постановке [2], поскольку под ним понимается совпадение положений iP и jE , а используем понятие «догнал». Мы, рассматривая агентов iP и jE , учитываем физические свойства объектов, соответствующих таким агентам. Очевидно, что ситуация совпадения положений фактически соот- ветствует столкновению объектов, в качестве которых выступают агенты. Как следствие, мы рассматриваем зону захвата, под которой понимается квадрат, сторона которого зависит от геометрических размеров (зада- ваемых параметром jGm ) объекта, соответствующего jE , а центр квадрата задается текущими координата- ми },{ jj yx агента jE , что в целом обеспечивает предотвращение столкновению объектов, соответствующих агентам iP и jE . Будем говорить, что в каждый момент времени 0t убегающему kj GrE  известно свое положение, но он знает положение только тех преследователей PPi  и других убегающих, принадлежащих множеству E , которые находятся в его зоне наблюдения. Под зоной наблюдения убегающего jE понимается квадрат, сторона которого равняется некоторому положительному числу и содержательно интерпретируется как удвоенное зна- чение пространства видимости в одну сторону, а центр квадрата задается текущими координатами },{ jj yx убе- гающего jE . Посредством зоны наблюдения моделируется общая видимость вследствие влияния погодных условий, времени суток и т. п. В отличие от традиционной постановки [2], в нашем случае убегающий kj GrE  не знает своих пресле- дователей. Как следствие, убегающий kj GrE  анализирует всех возможных преследователей PPi  , находя- щихся в его зоне наблюдения, но реагирует только на тех из них, кто гипотетически может выступать в каче- стве его преследователей, т. е. может входить в состав группы kGr , а с прочими агентами только избегает столкновения. Для выявления, кто именно является его преследователями, агент-убегающий динамически фор- мирует предположения, которые в каждый момент времени 0t уточняются в зависимости от поведения его возможных преследователей. Каждый агент PPi  и EE j  избегает столкновения с прочими агентами, попавшими в его зону столкновения, за исключением ситуации, когда iP и jE принадлежат одной и той же группе kGr . Зона столк- новения геометрически совпадает с зоной захвата (см. выше). Для избегания столкновений агенты используют специальные методы маневрирования. В случае, если iP и jE принадлежат одной и той же группе kGr , зона столкновения рассматривается как зона захвата, что соответствует ситуации, когда iP догнал jE . Так же, как и в традиционной постановке [2], каждый агент-преследователь ki GrP  в момент времени 0t знает положение всех преследователей, принадлежащих множеству P , включая себя, положение kj GrE  , скорость и направление его движения, а также положение, скорость и направление движения прочих убегающих, принадлежащих множеству E , в тот же момент времени t , но ему неизвестны будущие маневры таких агентов-убегающих. Каждый агент-преследователь ki GrP  в момент времени 0t также анализирует состояние убегающих }){\( kn GrGRE  . Обозначим расчетное время захвата преследователем iP убегающего kj GrE  как j i E P t . То- гда будем говорить, что состоялся взаимный переход агентов-преследователей в другие группы, если для двух Інтелектуальні інформаційні технології 214 агентов ki GrP  и sm GrP  , которые соответственно преследуют агентов-убегающих kj GrE  и sr GrE  , од- новременно выполняются соотношения r i j i E P E P tt  и j m r m E P E P tt  . При этом агент iP переходит из группы kGr в группу sGr , а агент mP – из группы sGr в группу kGr . Ограничением возможных переходов является условие, что constGrk )(card и constGrs )(card . Для выполнения таких взаимных переходов агенты-преследователи вступают в переговоры. По аналогии с традиционной постановкой [2], преследователи ki GrP  нацелены догнать убегающего kj GrE  за минимальное время, а убегающий jE – отсрочить момент захвата либо избежать его, если возможно. Обобщая вышеизложенное, можно сделать несколько выводов. Во-первых, можно утверждать, что в предлагаемой постановке знать закон движения произвольного агента EE j  (и, как следствие, агентов PPi  ) практически невозможно, поскольку на изменение характера их движе- ния влияет достаточно много факторов. В частности, на характер движения агента-убегающего влияют:  подвижные и неподвижные агенты, принадлежащие множествам P , E , A и находящиеся в границах множества S , для избегания столкновений с которыми агенту-убегающему необходимо маневрировать;  ограничения на действия агента-убегающего, накладываемые зоной наблюдения;  неопределенность состава его агентов-преследователей;  возможность динамического изменения состава его агентов-преследователей. Во-вторых, можно назвать основные различия между предложенной постановкой задачи преследования на плоскости и традиционной постановкой [2] (см. таблицу). Таблица. Основные различия между постановками задачи преследования на плоскости с точки зрения мультиагентного подхода и теории дифференциальных игр Мультиагентный подход Теория дифференциальных игр Закон движения агента неизвестен Закон движения точки известен Рассматривается n (n ≥ 1) убегающих и m (m ≥ 1) преследователей, где m ≥ n Рассматривается один убегающий и несколько пре- следователей Существует задача оптимального формирования ко- алиций (групп) Задача оптимального формирования нарядов (групп) не формулируется В каждый момент времени убегающему известно свое положение, но он знает положение только тех преследователей и прочих убегающих, которые находятся в его зоне наблюдения В каждый момент времени убегающему известно как свое положение, так и положение всех его преследо- вателей Убегающий не знает своих преследователей Убегающий знает своих преследователей В-третьих, можно определить перечень требуемых методов, на основе которых агенты могли бы прини- мать решения в динамической среде. К таким методам принадлежат:  методы формирования стратегий поведения агентов;  метод распознавания совокупности агентов, преследующих агента-убегающего;  метод перегруппировки агентов-преследователей;  метод генерации оптимальных групп агентов-преследователей;  методы маневрирования агентов для избегания столкновений с прочими агентами. В данной статье мы будем рассматривать три первых группы методов. 2. Методы моделирования поведения агентов 2.1. Метод преследования на плоскости. Известные методы преследования в основном разрабатыва- лись для военного назначения (в рамках исследований по наведению ракет на движущуюся цель [5–7]). К таким методам относятся: метод погони, метод постоянного упреждения, метод пропорционального сближения и ме- тод параллельного сближения. Из названных методов только метод параллельного сближения позволяет полу- чить прямолинейную (а не криволинейную) траекторию полета ракеты до встречи с целью. Кроме того, как по- казано в [2], по своим свойствам данный метод соответствует методу окружности Аполлония. Вместе с тем, у метода параллельного сближения (как и у метода окружности Аполлония) есть опреде- ленный недостаток, не позволяющий нам применить именно эти методы в качестве стратегии преследования: данные методы явно не используют ортогональной системы координат, использование которой, как мы показа- ли выше, необходимо исходя из предложенной постановки задачи преследования на плоскости. Інтелектуальні інформаційні технології 215 Предлагаемый метод преследования основывается на следующей постановке: два объекта (убегающий и преследователь) находятся в состоянии простого движения, при этом задано (см. рис. 1): текущие координаты убегающего (точка Е), текущие координаты преследователя (точка Р), направление движения убегающего (угол E ), скорость движения убегающего ( Ev ) и скорость движения преследователя ( Pv ). При этом интуитивно понятно, что убегающий и преследователь встретятся в некоторой точке С (при условии, что EP vv  ) через некоторое время .constt  P E C φαP αE LE LP K y 1 x1 S M Y Y' X' X D F G φ Рис. 1. Сущность предлагаемого метода преследования на плоскости В качестве неизвестных параметров выступают: искомое направление движения преследователя (угол P ); длина пути убегающего ( EL ); длина пути преследователя ( PL ); время t , необходимое для достижения объектами точки С; координаты точки С. Для решения задачи преследования на плоскости важно вычислить угол P , задающий направление движения преследователя. Зная этот угол, несложно вычислить все прочие неизвестные параметры задачи. Выполним дополнительные геометрические построения (см. рис. 1). Очевидно, что прямые ЕС и РС можно рассматривать как радиусы двух окружностей, пересекающихся в точках С и D. Построим эти окружно- сти и проложим для них оси координат XЕY и X'РY'. Проведем секущую SM через точки С и D. Соединим точ- ки Р и D прямой. Очевидно, что полученный в результате треугольник РDC является равнобедренным. Ясно, что высота треугольника РК пройдет также и через точку Е. При этом высота РК пересечет оси абсцисс Х и Х' под одним и тем же углом  . Очевидно, что 1 1)180(tg x y   и отсюда мы можем вычислить угол  (расстоя- ния 1x и 1y легко вычислить через координаты точек Е и Р). В свою очередь,  PP L)sin(  zLEE  )sin(  , где z – отрезок КС. Преобразовывая это уравнение и, учитывая, что tvL EE  и tvL PP  , получаем: )sin()sin( E P E P v v   . Отсюда можем вычислить требуемый угол P : ))sin(arcsin( E P E P v v   . В работе [8] мы показали, что предложенный метод преследования сводится как к методу параллельного Інтелектуальні інформаційні технології 216 сближения, так и к методу окружности Аполлония. На основе предложенного метода преследования на плоскости можно сформировать целесообразную стратегию поведения преследователя. Как показано в [8], определение целесообразного направления движе- ния преследователя по предложенному методу в точности совпадает с решением, получаемым по методу па- раллельного сближения. Как следствие, стратегия поведения преследователя должна быть ориентирована на постоянный анализ поведения убегающего, определение целесообразного угла направления своего движения в момент изменения поведения убегающего и, вследствие этого, динамическую корректировку своего поведения. Полученные результаты позволяют сделать выводы и о целесообразной стратегии поведения убегающе- го. Очевидно (см. рис. 1), что самый долгий путь преследователь пройдет, если убегающий будет двигаться по лучу EG. Так, если сравнить расстояния РС и PG, то легко заметить, что PG больше РС на отрезок FG. Отсюда вытекает целесообразная стратегия поведения убегающего для данного случая: он должен корректировать направление своего движения таким образом, чтобы оно максимально приближалось к направлению, задавае- мому лучом, идущим от преследователя к убегающему. Обобщая, отметим, что существенным преимуществом предложенного метода преследования на плоско- сти над методами-аналогами является то, что он основывается на использовании ортогональной системы коор- динат, что является крайне важным для моделирования процессов преследования/убегания агентов в мультиа- гентной системе. 2.2. Метод управления стратегиями поведения агентов. В п. 2.1 статьи мы обосновали целесообраз- ные стратегии поведения агента-убегающего и его агентов-преследователей, основанные на разработанном нами методе преследования. Но при этом остался неформализованным процесс управления использованием этих стратегий в рамках решения общей задачи преследования/убегания. Цель данного подраздела статьи – из- ложение метода ближайшей точки, обобщающего процессы использования стратегий поведения агентов для общего случая (m преследователей и n убегающих, где m ≥ n). 2.2.1. Исследование стратегии преследования/убегания для случая «один убегающий – два пресле- дователя». Данная стратегия преследования/убегания для случая «один убегающий – два преследователя», из- ложенная Р. Айзексом в [3, с.189] (для удобства изложения далее эту стратегию будем называть стратегией Р. Айзекса). Как будет показано далее, анализ данной стратегии важен потому, что в общем случае максимум два преследователя (из произвольного их количества) влияют на характер поведения исследуемого убегающего. Цель исследования – оценка целесообразности применения стратегии Р. Айзекса для управления стратегиями поведения агентов. Сущность стратегии Р. Айзекса заключается в нахождении наиболее удаленной точки от убегающего в области, образованной в результате пересечения двух окружностей Аполлония, построенных для каждой из пар убегающий – преследователь, и выполнении простого движения (при условии, что скорости преследователей больше скорости убегающего) к этой точке как убегающим, так и его преследователями. При этом стратегии поведения убегающего и его преследователей будут оптимальными. Для анализа стратегии Р. Айзекса нами разработан специализированный прототип системы, в котором реализована исследуемая стратегия. В ходе исследований установлено, что могут возникать 3 разных случая: 1) когда две окружности Аполлония пересекаются и преследователи расположены по разные стороны относительно линии, проходящей через точку дислокации убегающего и наиболее удаленную точку пересече- ния окружностей Аполлония (см. рис. 2, а). 2) когда две окружности Аполлония пересекаются и преследователи расположены по одну сторону от- носительно линии MN, проходящей через точку дислокации убегающего и наиболее удаленную точку пересе- чения окружностей Аполлония (см. рис. 2, б). 3) когда две окружности Аполлония не пересекаются (одна окружность находится внутри другой – см. рис. 2, в). a б в Рис. 2. Возможные варианты стратегий преследования/убегания агентов Інтелектуальні інформаційні технології 217 Первый случай соответствует ситуации, рассмотренной Р. Айзексом в [3]. В этом случае убегающий E и преследователи 1P и 2P , в соответствии со стратегией Р. Айзекса, должны двигаться к точке 1 (как наиболее удаленной точке области пересечения окружностей Аполлония). При условии, что E , 1P и 2P будут находить- ся при этом в состоянии простого движения, они одновременно достигнут точки 1. Второй и третий случаи соответствуют ситуации, когда убегающий Е будет захвачен только одним пре- следователем ( 1P ) в точке 1, а другой преследователь ( 2P ) будет двигаться в направлении точки 2. Отметим, что во втором и третьем случаях точка 1 соответствует наиболее удаленной от убегающего E точке на окруж- ности Аполлония, построенной от ближайшего преследователя (см. далее). Исходя из этого, в данных случаях оптимальная стратегия убегающего Е заключается в том, что он должен двигаться в направлении, задаваемом лучом, направленным от преследователя 1P к убегающему E , что полностью совпадает с нашими выводами (см. п. 2.1) о целесообразной стратегии поведения агента-убегающего. В свою очередь, преследователи 1P и 2P во всех случаях движутся в соответствии со стратегией параллельного сближения (или стратегии, соответству- ющей методу преследования, изложенному в п. 2.1). Основным недостатком стратегии Р. Айзекса является то, что направление движения убегающего вычис- ляется в результате выполнения соответствующих расчетов, и не изменяется в процессе преследования. В дей- ствительности же направление движения убегающего задается явно в начале процесса преследования, как ис- ходный параметр задачи преследования, и в любой последующий момент времени формируется ситуационно в зависимости от действий его преследователей (ясно, что при этом убегающий должен стремиться сформировать оптимальную стратегию убегания). Очевидно, что метод, на основе которого будет осуществляться управление стратегиями поведения аген- тов, не должен иметь такого недостатка. 2.2.2. Метод ближайшей точки. Данный метод предназначен для формирования оптимального направ- ления движения убегающего в зависимости от текущих направлений движения его преследователей. Как мы показали в п. 2.2.1, возможны два состояния (которые мы будем называть равновесными состояниями) по формированию оптимального направления движения убегающего: Состояние 1. Когда убегающий и два его ближайших преследователя движутся к точке пересечения двух окружностей Аполлония как наиболее удаленной точке области пересечения этих окружностей (см. случай 1 в п. 2.2.1). Состояние 2. Когда убегающий движется в направлении, задаваемом лучом, направленным от ближай- шего преследователя к этому убегающему (см. случаи 2, 3 в п. 2.2.1). Здесь под ближайшим преследователем понимается преследователь, который на данный момент време- ни может скорее всех прочих преследователей догнать убегающего (то есть точка Аполлония, построенная от этого преследователя, будет ближайшей к убегающему). Далее мы будем ссылаться на названные состояния. Сущность метода ближайшей точки заключается в том, что убегающий в процессе преследования в каждый момент времени определяет ближайшую к нему точку Аполлония (из точек, построенных от пресле- дователей, попавших в его зону наблюдения) и, если он не находится в равновесном состоянии, то постепен- но изменяет угол своего движения для достижения равновесного состояния, либо, если он находится в рав- новесном состоянии, а положение этой точки Аполлония выводит его из этого состояния, то постепенно из- меняет угол своего движения для достижения нового равновесного состояния. Отметим, что точка Аполло- ния и целесообразное направление движения преследователей, используемые в методе ближайшей точки, определяются с помощью метода преследования, изложенного в п. 2.1. Отличительной особенностью пред- ложенного метода ближайшей точки является то, что он, в отличие от стратегии Р. Айзекса, вообще не тре- бует построения окружностей Аполлония. Детальное рассмотрение метода ближайшей точки приведено в [9]. Отметим, что данный метод справедлив для произвольного количества преследователей. Действитель- но, в любой момент времени преследования каждый агент-убегающий может оказаться в одном из двух со- стояний (либо в равновесном, либо в неравновесном). Если убегающий находится в неравновесном состоя- нии, то на его поведение в каждый момент времени влияет один и только один ближайший агент- преследователь, находящийся в зоне наблюдения убегающего. Если же агент-убегающий находится в равно- весном состоянии, то в каждый момент времени на его поведение могут влиять максимум два агента- преследователя, относительно которых сформировано равновесное состояние. Так, как мы показали выше, существует два вида равновесных состояний. При этом в состоянии 2, независимо от общего количества пре- следователей, на поведение агента-убегающего влияет один и только один ближайший преследователь, нахо- дящийся в его зоне наблюдения. В состоянии 1 в общем случае на поведение убегающего могут влиять столько агентов-преследователей, сколько из них сформировали ту же самую общую точку Аполлония, сформированную двумя его ближайшими агентами-преследователями в соответствии с условиями возникно- вения состояния 1. То есть агент-убегающий, формируя оптимальную стратегию убегания, обязательно будет двигаться в направлении этой точки Аполлония, что соответствует сущности состояния 1, независимо от то- го, сколько агентов-преследователей сформировали такую точку. Иначе говоря, случай, когда произвольное количество агентов-преследователей формируют общую точку Аполлония, сводится к случаю, соответству- ющему состоянию 1. Інтелектуальні інформаційні технології 218 Таким образом, метод ближайшей точки позволяет:  адаптивно текущим изменениям формировать оптимальную стратегию поведения агента-убегающего;  адаптивно текущим изменениям поддерживать оптимальные стратегии поведения агентов- преследователей;  моделировать процессы преследования/убегания в реальном масштабе времени, учитывая при этом особенности поведения разных по свойствам агентов. В целом можно утверждать, что метод ближайшей точки позволяет моделировать поведение агентов в мультиагентном стиле и является эффективным методом управления стратегиями преследования/убегания для произвольного количества агентов. 2.3. Метод распознавания агентов, преследующих убегающего. В каждый момент времени 0t , предшествующий моменту его захвата, каждый агент-убегающий решает задачу распознавания множества агентов, гипотетически могущих выступать в качестве его преследователей. При этом каждый убегающий EE j  рассматривает множество PM j 1 подвижных агентов PPi  , находящихся в его зоне наблюдения, и выполняет анализ текущих состояний агентов j i MP 1 для формирования предположений для определения своего целесообразного состояния (направления движения и скорости) в следующий момент времени. Данная задача анализа включает в свой состав две подзадачи: 1) формирования подмножества jM 2 ( jj MM 12  ) агентов, которые потенциально могут выступать в ка- честве преследователей агента-убегающего EE j  ; 2) выявление одного преследователя j k MP 2 (см. также замечание в п. 2.3.2), угроза наискорейшего захвата убегающего EE j  которым является наиболее возможной. Очевидно, что решение второй подзадачи (с учетом того, что управление стратегиями преследова- ния/убегания агентов основывается на методе ближайшей точки) позволит агенту-убегающему точно опреде- лить свое целесообразное состояние, в которое он должен перейти в следующий момент времени. 2.3.1. Метод формирования множества jM 2 агентов, которые потенциально могут выступать в каче- стве преследователей агента-убегающего EE j  , основывается на последовательном попарном анализе теку- щих состояний подвижных агента jE и агентов j i MP 1 . При этом анализируются углы направления движения агентов jE и iP относительно линии, проведенной через точки их текущей дислокации (линии дислокации), и определяется признак, по какую сторону относительно линии дислокации агенты будут расположены в следу- ющий момент времени (правее либо левее). Если значения признаков для агентов jE и iP совпадают и сумма углов направлений движений этих агентов, вычисленных относительно линии дислокации, составляет меньше 180°, то агент iP добавляется в состав множества jM 2 . В результате завершения анализа формируется множе- ство jM 2 , включающее всех агентов, которые гипотетически в данный момент времени могут рассматриваться в качестве преследователей агента jE . 2.3.2. Метод выявления агента-преследователя j k MP 2 заключается в определении времени потен- циальной встречи агента jE с каждым из агентов множества jM 2 . В качестве агента-преследователя j k MP 2 выбирается агент, имеющий наименьшее расчетное время. Заметим, что здесь также возможен случай, когда существует два агента j k MP 2 и j k MP 21  , имеющих одинаковое наименьшее расчетное время. Ясно, что в этом случае агент jE находится в состоянии 1 (см. п. 2.2.2), и при этом его направление движения и скорость в следующий момент времени полностью определяются текущими значениями этих параметров. Отметим, что множество jM 2 обязательно содержит всех фактических агентов-преследователей убега- ющего jE , находящихся в его зоне наблюдения. Вместе з тем, убегающие, формируя предположения с помо- щью данных методов, могут ошибаться, поскольку в попутном направлении с каждым из них могут двигаться и отдельные агенты mP ( j m MP 2 ), также влияющие на характер движения убегающего jE . Однако, как следует из результатов компьютерного моделирования, постепенно в ходе процесса преследования/убегания предполо- жения убегающих об их фактических преследователях становятся все более достоверными. 2.4. Метод перегруппировки агентов-преследователей. Данный метод использует отдельные результа- ты, вычисляемые в процессе выполнения метода формирования множества jM 2 (см. п. 2.3.1), касающиеся определения времени перехвата, которое затратил бы каждый агент-преследователь j i MP 2 на преодоление расстояния от его текущей дислокации до точки потенциальной встречи с агентом-убегающим jE (в п. 2.3.1 Інтелектуальні інформаційні технології 219 эти данные формируются для определения времени потенциальной встречи jE и j i MP 2 ). На основе этих данных агент-преследователь ki GrP  в каждый момент времени 0t своего движения анализирует текущее состояние для выявления ситуации, когда время перехвата некоторого агента-убегающего sr GrE  окажется меньше времени перехвата агента-убегающего kj GrE  . Дополнительным признаком такой ситуации является то, что при этом должно выполняться условие rj i MMP 22  , означающее, что для перехода к преследованию агента-убегающего rE агенту iP не нужно изменять своего текущего направления движения. Если такая ситуация выявляется, то агент-преследователь iP вступает в процесс переговоров, генерируя пред- ложение для агентов-преследователей группы sGr о возможном более быстром захвате агента sr GrE  , и предлагая им рассмотреть возможность передачи собственных полномочий по захвату своей цели (агента- убегающего kj GrE  ). В свою очередь, реагируя на это предложение, агенты-преследователи группы sGr та- ким же образом, как и агент iP , анализируют текущую ситуацию. Если находится некоторый агент sm GrP  , для которого такая ситуация отвечает всем вышеуказанным требованиям, то он принимает это предложение и происходит взаимный переход агентов iP и mP соответственно в группы sGr и kGr (отметим, что если претен- дентов на роль агента mP несколько, то выбирается тот, у которого время перехвата агента jE наименьшее). В противном случае предложение отклоняется. Как показывают результаты компьютерного моделирования, описанный метод в ряде случаев позволяет существенно сократить время захвата убегающих (см., например, разд. 3 статьи). 3. Прототип мультиагентной системы «Навигация» На основе разработанных методов создан прототип мультиагентной системы «Навигация» (МАС Нави- гация) [10], реализованный на языке PDC Visual Prolog 5.2. Для обеспечения адекватного отображения особенностей выполнения вышеизложенных методов, в МАС Навигация реализованы соответствующие решения по поддержке автоматического ведения в реальном масшта- бе времени трех типов протоколов: протокола предположений убегающих, протокола действий агентов и про- токола регистрации переговоров преследователей. Каждый из этих протоколов обеспечивает отображение раз- ных аспектов поведения агентов во времени и реализуется средствами соответствующих окон (см. рис. 3), от- крывающихся по желанию пользователя. Рис. 3. Пример функционирования МАС Навигация Інтелектуальні інформаційні технології 220 Приведенный пример наглядно демонстрирует преимущества использования метода перегруппировки агентов в процессе моделирования преследования на плоскости (на рис. 3 перегруппировавшиеся агенты- преследователи обведены кружками): благодаря этому методу время захвата агентов-убегающих сократилось на 33% по сравнению со случаем, когда агенты-преследователи не выполняли перегруппировки. Выводы Проведенные исследования подтверждают эффективность использования мультиагентного подхода для решения задач преследования на плоскости. Как показано в статье, благодаря разработанным методам, реали- зованным в МАС Навигация, ее средствами обеспечивается моделирование процессов поведения агентов для общего случая ( n ( 1n ) убегающих и m ( 1m ) преследователей, где nm  ). Дальнейшие исследования предполагают разработку методов маневрирования агентов для общего случая (с реализацией их в МАС Навигация) и интеграцию МАС Навигация с геоинформационной системой «ДЕКАРТ» [11] (ГИС ДЕКАРТ). ГИС ДЕКАРТ ориентирована на использование картографических БД формата ГИС ArcGIS. Отметим, что создание ГИС ДЕКАРТ основывалось на новой концепции «динамической элек- тронной карты», благодаря которой средствами ГИС ДЕКАРТ обеспечивается представление и обработка в реальном масштабе времени динамических объектов различной природы. 1. Петросян Л.А., Томский Г.В. Геометрия простого преследования. – Новосибирск: Наука, 1983. – 140 с. 2. Петросян Л.А., Рисхиев Б.Б. Преследование на плоскости. – М.: Наука, 1991. – 91 с. 3. Айзекс Р. Дифференциальные игры. – М.: Мир, 1967. – 479 с. 4. Красовский Н.Н., Субботин А.И. Позиционные дифференциальные игры. – М.: Наука, 1974. – 456 с. 5. Куркоткин В.И., Стерлигов В.Л. Самонаведение ракет. – М.: ВоенИздат, 1963. – 89 с. 6. Локк А.С. Управление снарядами. – М.: Гос. изд-во технико-теоретической литературы, 1957. – 775 с. 7. Неупокоев Ф.К. Стрельба зенитными ракетами. – М.: ВоенИздат, 1991. – 343 с. 8. Яловець А.Л. Про один метод переслідування на площині // Проблеми програмування. – 2013. – № 3. – С. 117–124. 9. Яловець А.Л. Про метод найближчої точки як метод управління стратегіями переслідування/ утікання агентів // Проблеми програмування. – 2013. – № 4. – С. 94–99. 10. Яловець А.Л., Кондращенко В.Я., Арістов В.В. Свідоцтво № 46897 про реєстрацію авторського права на твір «Комп’ютерна програма – “Мультиагентна система “Навігація”, версія 2.0”». Державна служба інтелектуальної власності України, 2012. 11. Яловець А.Л., Кондращенко В.Я., Арістов В.В. Свідоцтво № 52935 про реєстрацію авторського права на твір «Комп’ютерна програма – “Геоінформаційна система “ДЕКАРТ”, версія 1.0”». Державна служба інтелектуальної власності України, 2014.

Methods of simulation of behavior of agents in multi-agent system “Navigation”

Institution

Similar Items