УДК 004.896

Алгоритм роевого управления динамическими объектами на основе мультиагентных систем

Н.Н. Юрьев^1, О.И. Федяев^2

^*1 магистрант, Донецкий национальный технический университет, mikitayuriev@gmail.com

^*2 к.т.н, доцент, Донецкий национальный технический университет, fedyaev@donntu.org, OrcID: 0000-0001-6822-7306, SPIN-код: 7777-3791

Юрьев Н.Н., Федяев О.И. Алгоритм роевого управления динамическими объектами на основе мультиагентных систем. В работе рассматривается возможность применения технологий мультиагентных систем к задаче управления роем. Приводится описание ключевых особенностей роевого управления и акта локального согласия, с помощью которого строится стратегия адаптивного управления в условиях неопределенностей, а также представлен алгоритм управления роем на основе согласия.

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

Введение

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

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

Выделяют такие виды роевого управления, как самоорганизующиеся системы, так называемые природные агенты [3]. Они обладают следующими признаками: отсутствие индивидуального сознания у особи, правила поведения заложены в генетику особи, разумная деятельность направлена на сохранение роя, рой состоит из представителей одного вида. Следующий вид предполагает наличие управления. Для агентов, которые перемещаются по поверхности, действуют следующие параметры: расчёт расстояния от начальной точки, выстраивание в группу, образование заданной плотности роя, локализация. Если агенты перемещаются в пространстве, то они должны: держать дистанцию от объектов, стремиться к центру группы ближайших объектов, двигаться в направлении ближайшего объекта, держать связь с главным агентом. Роевые системы способны двигаться и взаимодействовать с окружающей средой без централизованного управления. В таком случае управлять можно дистанционно с выделением базовой станции, лидер роя назначается из центрального узла. Также можно определить лидера роя на основе алгоритма и не быть зависимым от центральной управляющей станции [4].

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

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

Имеется множество K агентов kⁱ (i = 1, ..., n), ориентированное на решение ряда задач D = d₁,...,d_m, которое будем называть моделью роя. При этом вводим следующие предположения:

Все агенты kⁱ (i = 1,...,n) имеют одинаковую структуру.
Агент kⁱ ∈ K может осуществлять обмен сообщениями с подмножеством агентов Kⁱ < K, которые находятся в пределах видимости R, где R -- радиус области видимости агента kⁱ. Благодаря такой связи агенту kⁱ может быть доступна информация о состоянии всех соседних агентов из подмножества Kⁱ.
Во избежания столкновения, агент kⁱ не может приближаться к своим соседним агентам на расстояние меньше, чем r.
Для решения задачи d_i ∈ D оператор задаёт каждому агенту kⁱ перспективу движения. Предположим, что агенты движутся в условиях отсутствия преград. По мере движения у каждого агента формируется собственная картина мира (среды).
Движение каждого агента kⁱ определяется направлением xⁱ и значением потенциала (степень целесообразности) выбранного пути zⁱ.
Об окружающем мире (среде движения) в каждом агенте заложена база знаний, которую он пополняет по пути своего движения.
После того, как агент определится с направлением движения, он должен проложить маршрут с избеганием столкновения при наличии препятствий и определить своё новое состояние параметрами xⁱ и zⁱ.

Математическое описание перехода агентов в новое состояние

Акт локального соглашения нужен для согласия между агентами [5]. При управлении каждый агент kⁱ ∈ K в момент времени t = 0, 1, 2,... имеет зашумленную информацию о своем собственном направлении движения, увеличенную на текущий потенциал своего маршрута:

y_t^i,i = g_tⁱ + m_t^i,i, g_tⁱ = z_tⁱx_tⁱ, (1)

и, если K_tⁱ ≠ ∅ , то под его контролем имеются также зашумленные наблюдения о направлениях движения соседей, которые также домноженные на потенциалы маршрутов соседей:

y_t^i,j = g_t^j - p_t^i,j + m_t^i,j, j ∈ K_tⁱ (2)

где величины ω_t^i,j, ω_t^i,i - шумы, а p_t^i,j - целочисленная временная задержка, т. е. шаг модельного времени (0 ≤ p_t^i,j ≤ p , p - максимально возможная задержка). Положим ω_t^i,j = 0 и p^i,j = 0 для всех остальных пар (i, j), для которых они не были определены. Так как система начинает работу при t = 0, то неявное требование к множеству соседей j ∈ K_tⁱ следующее: t -- p_t^i,j > 0.

Согласованное мультиагентное управление задается следующим соотношением:

u_tⁱ = α Σ b_t^i,j(y_t^i,j - y_t^i,i), (3)

j∈K_tⁱ

где α -- величина шага протокола управления (0< α<1), b_t^i,j -- веса, т. е. ограниченные случайные величины. Условимся b_t^i,j = 0 для других пар (i, j).

Изменение направления будет описываться разностным уравнением:

x_t+1ⁱ = x_tⁱ + f(u_tⁱ, x_tⁱ) (4)

с управлением u_tⁱ ∈ R, воздействие которого на изменение направления xⁱ определяется некоторой функцией f(·,·):R×R→R , формирующей окончательное управление в соответствии с процедурой избежания столкновений.

В качестве примера рассмотрим следующую задачу: перемещение роя агентов из точки A в точку B в условиях неопределенности (рис. 1).

Рисунок 1 — Перемещение роя из точки A в точку B по акту локального голосования

При изменении потенциала движения роя, объектам роя необходимо поменять свое направление в сторону повышения вероятности выполнения задачи [6]. Рассмотренный выше акт локального соглашения действует подобно природному поведению роя муравьев. Схематично процесс расчёта изменения траектории агентом k₃ при движении роя без препятствий из точки A в точку B показан на рис. 2. Такой подход даёт возможность применения принципов самоорганизации для моделирования управления группой роботизированных устройств с помощью программных агентов.

Рисунок 2 — Схема изменения траектории агента k₃ с учётом соседних агентов

Алгоритм управления роем

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

Все агенты в составе роя получают из пункта управления поставленную задачу.
Установка акта голосования, установка связей между соседями, начало обмена сообщениями.
Каждый агент kⁱ ∈ K получает информацию о текущем направлении движения объектов роя, находящихся в зоне его видимости, и числовую характеристику потенциала их движения.
На основании собственных y_tⁱⁱ и полученных y_t^ij данных, определяемых формулами (1) и (2), формируется управление u_tⁱ по формуле (3) рассматриваемого агента.
Изменение движения агента x_t+1ⁱ по формуле (4) с применением функции f() избегания столкновений с препятствием.
Пересчёт потенциала движения z_t+1ⁱ на основе информации агента и дополнительных сведений, получаемых при анализе мира и от соседей.

Заключение

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

Литература

Y. Shi, R. Eberhart, «A modified particle swarm optimizer» // The 1998 IEEE International Conference on Evolutionary Computation Proceedings, 1998.
R. C. Eberhart, J. Kennedy, «A new optimizer using particle swarm theory» // Proceedings of the Sixth International Symposium on Micro Machine and Human Science MHS'95, 1995.
Tanner H.G., Jadbabaie A., Pappas G. J. Flocking in fixed and switching networks // IEEE Trans. Autom. Contr. 2007. Vol. 52. No. 5. P. 863--868.
R. Mendes, J. Kennedy, J. Neves, «The fully informed particle swarm: Simpler, maybe better» // IEEE Transactions on Evolutionary Computation, №8, 2004.
Beni G., Wang J. Swarm Intelligence in Cellular Robotic Systems, Proceed. NATO Advanced Workshop on Robots and Biological Systems, Tuscany, Italy, 1989.
Huang M. Stochastic approximation for consensus: a new approach via ergodic backward products. IEEE Transactions on Automatic Control: 2994 - 3008, 2012.

Yuriev N.N., Fedyaev O.I. Algorithm for swarm control of dynamic objects based on multi-agent systems. The paper considers the possibility of applying the technologies of multi-agent systems to the problem of swarm control. A description of the key features of swarm control and the act of local consent is given, with the help of which an adaptive control strategy is constructed in conditions of uncertainty, and an algorithm for control of a swarm based on consent is presented.

Keywords: multi-agent technologies, swarm control, swarm intelligence, self-organization, multi-agent systems.