Разработка вероятностной модели поведения многоагентной системы в трехмерном пространстве

Н.И. Левонович

doi:10.17759/mda.2025150209

Введение

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

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

Описание поведения системы

Агенты

L_{m} (m = 0, \dots, M - 1)

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

T_{n} (n = 0, \dots, N - 1)

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

(i, j, k)

, где

i -

индекс долготы

(i = (0, \dots, I - 1))

,

j -

индекс широты

(j = (0, \dots, J - 1))

,

k -

индекс высоты

(k = (0, \dots, K - 1))

(рисунок 1). Вероятность того, что агент

L_{m}

находится в ячейке

(i, j, k)

в момент времени

t

определяется функцией

p_{m, ijk} (t)

.

Рис. 1. Структура отношений между состояниями случайного марковского процесса, представляющая движение агентов по ячейкам игрового поля

Fig. 1. Structure of relationship between states of random Markov process representing agent movement through game field cells

В дискретные моменты времени, разделенные интервалами дискретизации

∆ t

, агент

L_{m}

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

p_{t}

и коллективного

p_{tn}

воздействия на цель, максимальная разрешенная вероятность успешного воздействия цели на агента

p_{B}

, максимальная скорость агента

v_{\max}

. Число агентов, одновременно терпящих воздействие одной цели (не регулируется, один агента).

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

Изменение положения агентов и целей на игровом поле, а также вероятностей взаимных поражений происходит за фиксированный интервал времени

∆ t

называется тактом игры.

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

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

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

Число переходов между смежными состояниями

X

, происходящий за любой интервал времени

τ

, начиная со времени

t

подчиняются закону Пуассона:

P_{t, τ} (X = m) = \frac{a {(t, τ)}^{m}}{m!} e^{- a (t, τ)},

где

P_{t, τ} (X = m)

– вероятность

m

переходов за этот интервал,

a (t, τ)

среднее количество переходов, совершаемых за интервал

τ

с момента времени

t

. В дальнейшем рассматриваются только стационарные потоки

a (t, τ) = ητ

и

η = const

Гипотеза о пуассоновском распределении переходов является стандартной для рассматриваемой области, так как это распределение часто встречается на практике, так как следует из предельных теорем для потоков событий.

Поведение каждого агента в части перемещения определяется автономно. Динамика вероятностей пребывания

m

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

\frac{d p_{m} (t)}{dt} = M_{m} (λ_{m}) p_{m} (t)

где

p_{m} (t)

– вероятности пребывания m-того агента в n-том состоянии процесса,

λ_{m}

– вектор интенсивностей перехода между смежными состояниями для m-того агента.

M_{m}

– матрица

n

-того порядка интенсивностей перехода между смежными состояниями m-того агента. Начальные условия

p_{m, i_{0} j_{0} k_{0}} (0) = 1, {p_{m, ijk} (0) = 0}_{i \neq i_{0}, j \neq j_{0}, k \neq k_{0}}

, где

(i_{0}, j_{0}, k_{0})

– индекс ячейки в который m-тый агент находился в

t_{0} = 0

.

Введём следующее обозначения для элементов вектора

λ_{m}

(рисунок 2)

Интенсивность переходов m-того агента в состоянии $(i, j, k)$ в сторону увеличения первой координаты $λ_{m, i, j, k, \to}$ ;
Интенсивность переходов m-того агента в состоянии $(i, j, k)$ в сторону уменьшения первой координаты $λ_{m, i, j, k, \leftarrow}$ ;
Интенсивность переходов m-того агента в состоянии $(i, j, k)$ в сторону увеличения второй координаты $λ_{m, i, j, k, ⊙}$ ;
Интенсивность переходов m-того агента в состоянии $(i, j, k)$ в сторону уменьшения второй координаты $λ_{m, i, j, k, ⨂}$ ;
Интенсивность переходов m-того агента в состоянии $(i, j, k)$ в сторону увеличения третий координаты $λ_{m, i, j, k, ↑}$ ;
Интенсивность переходов m-того агента в состоянии $(i, j, k)$ в сторону уменьшения третий координаты $λ_{m, i, j, k, ↓}$ ;

Рис. 2. Обозначение интенсивности переходов m-того агента в данном состоянии

Fig. 2. Designation of the intensity of transitions of the m-th agent in a given state

Расчет вероятностей

p_{m} (t)

для всех агентов происходит синхронно в дискретные моменты времени с шагом

Δ t

. Некоторые агенты могут оставаться в тех же ячейках.

Обозначим текущий момент времени как

t_{}

, обозначим введем следующие обозначения для событий:

 $A_{n}$ – n-тая цель успешно помечена в результате воздействия;
 $B_{mn}$ – m-тый агент помечена в результате n-той цели;
 $D_{mn}$ – воздействие m-тым агентом на n-тую цель;
 $H_{i_{m} j_{m} k_{m} m}$ – m-тый агент находится в ячейке $(i_{m}, j_{m}, k_{m})$
 ${\tilde{H}}_{i_{m} j_{m} k_{m} m}$ – в момент времени $t_{} + ∆ t$ m-тый агент находится в ячейке $(i_{m}, j_{m}, k_{m})$ , которая смежна с ячейкой, в которой агент находился в момент времени $t_{}$ .
 $C_{m}$ – переход m-того агента из ячейки, в которой он был в момент времени $t_{}$ в одну из смежных ячеек.
 $H_{i_{n} j_{n} k_{n} n}$ – n-тая цель находится в ячейке $(i_{n}, j_{n}, k_{n})$

Вероятность успешной пометки n-той цели в результате воздействия m-тым агентом вычисляется согласно формуле полной вероятности:

p (A_{n} | D_{mn}) = \sum_{i, j, k} p (A_{n} | H_{i_{m} j_{m} k_{m} m} \cap H_{i_{n} j_{n} k_{n} n}) p (H_{i_{m} j_{m} k_{m} m}) p (H_{i_{n} j_{n} k_{n} n})

Вероятность успешной пометки n-той цели, находящейся в ячейке

(i_{n}, j_{n}, k_{n})

m-тым агентом в результате воздействия из ячейки

(i_{m}, j_{m}, k_{m})

в момент времени

t_{}

задается относительной «картой осуществимости»

f_{a}

:

p (A_{n} | H_{i_{m} j_{m} k_{m} m} \cap H_{i_{n} j_{n} k_{n} n}) = f_{a} (i_{m}, j_{m}, k_{m}, i_{n}, j_{n}, k_{n}, t_{})

Вероятности

p (H_{i_{m} j_{m} k_{m} m})

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

Вероятность успешной пометки m-того агента, находящегося ячейке

(i_{m}, j_{m}, k_{m})

, n-той целью находящейся в ячейке

(i_{n}, j_{n}, k_{n})

в результате воздействия в момент времени

t_{}

задается относительной «картой уязвимости»

f_{b}

:

p (A_{n} │ H_{i_{m} j_{m} k_{m} m} \cap H_{i_{n} j_{n} k_{n} n}) = f_{b} (i_{n}, j_{n}, k_{n}, i_{m}, j_{m}, k_{m}, t_{})

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

f_{a} (i_{m}, j_{m}, k_{m}, i_{n}, j_{n}, k_{n}, t_{}) = c_{a} (\frac{e^{r_{a, d} d (i_{m}, j_{m}, k_{m}, i_{n}, j_{n}, k_{n}) + q_{a, d}}}{1 + e^{r_{a, d} d (i_{m}, j_{m}, k_{m}, i_{n}, j_{n}, k_{n}) + q_{a, d}}})

f_{b} (i_{m}, j_{m}, k_{m}, i_{n}, j_{n}, k_{n}, t_{}) = c_{b} (\frac{e^{r_{b, d} d (i_{m}, j_{m}, k_{m}, i_{n}, j_{n}, k_{n}) + q_{b, d}}}{1 + e^{r_{b, d} d (i_{m}, j_{m}, k_{m}, i_{n}, j_{n}, k_{n}) + q_{b, d}}})

где

d (i_{m}, j_{m}, k_{m}, i_{n}, j_{n}, k_{n})

расстояние между ячейками

(i_{m}, j_{m}, k_{m})

и

(i_{n}, j_{n}, k_{n})

; параметры

c_{a}, c_{b}, r_{a, d}, q_{a, d} r_{b, d}, q_{b, d}

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

Найдем закон распределения для

τ_{} > 0

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

P_{τ} (X = 0) = e^{- ητ}

. Это значение эквивалентно вероятности события

τ_{} > τ

:

P (τ_{} > τ) = e^{- ητ}

. Следовательно,

P (τ_{} \leq τ) = 1 - P (τ_{} > τ) = 1 - e^{- ητ}

, где

F (τ, η) = P (τ_{} \leq τ)

– функция распределения случайной величины

τ_{} .

Это распределение имеет плотность

ρ (τ) = η e^{- ητ}

и математическое ожидание

E = \int_{0}^{\infty} tη e^{- ητ} dt = \frac{1}{η}

Вероятность успешной пометки n-той цели в ходе групповой атаки оценивается согласно формуле сумме вероятностей, в случае воздействия на него всеми агентами одновременно:

p (A_{n} | D_{1 n} + \dots + A_{n} | D_{mn}) = p (A_{n} | D_{1 n}) + \dots + p (A_{n} | D_{mn}) - p (A_{n} | D_{1 n} * A_{n} | D_{2 n}) - p (A_{n} | D_{1 n} * A_{n} | D_{3 n}) - \dots + p (A_{n} | D_{1 n} * A_{n} | D_{2 n} * A_{n} | D_{3 n}) + \dots \pm p (A_{n} | D_{1 n} * A_{n} | D_{2 n} * \dots * A_{n} \lor D_{mn})

События

A_{n} \lor D_{}

и

A_{n} \lor D_{jn}

полагаются независимыми если

i \neq j

.

Построение пар атак

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

d_{mn} = (l_{m}, t_{n})

,

D

– множество воздействий, функционал

f_{a}^{+ (d_{mn}, t_{}) = f_{a} (i_{m}, j_{m}, k_{m}, i_{n}, j_{n}, k_{n}, t_{})}

назовем значением воздействия.

Матрица значений воздействия

C

, образуется из значений воздействий, которые стоят на пересечении строки (относящейся к агенту) и столбца (относящейся к цели).

C (t_{}) =

Построим граф

G = (W, E); W = L_{m} \cup D

;

E = {(l_{m}, d_{mn}) : l_{m} \in L_{m}; l_{m} \in d_{mn}}

. Для ребер существует функционал разметки

g : E \to R

,

g (e) =^{f_{a}^{+ (d_{mn}, t_{})} - f_{a}^{+ (d_{mn}, t_{}) + ϵ}}

, где

d_{mn} \in e

.

Для полученного графа с помощью венгерского алгоритма [Венгерский алгоритм решения; Задача о назначениях] решается задача о назначениях получается распределение воздействий.

Определения:

Паросочетанием M называется набор попарно несмежных рёбер графа (иными словами, любой вершине графа должно быть инцидентно не более одного ребра из множества M). Мощностью паросочетания назовём количество рёбер в нём. Наибольшим (или максимальным) паросочетанием назовём паросочетание, мощность которого максимальна среди всех возможных паросочетаний в данном графе. Все те вершины, у которых есть смежное ребро из паросочетания (т.е. которые имеют степень ровно один в подграфе, образованном M), назовём насыщенными этим паросочетанием.
Полное паросочетание – паросочетание, в которое входят все вершины.
Цепью длины k назовём некоторый простой путь (т.е. не содержащий повторяющихся вершин или рёбер), содержащий k рёбер.
Чередующейся цепью (в двудольном графе, относительно некоторого паросочетания) назовём цепь, в которой рёбра поочередно принадлежат/не принадлежат паросочетанию.
Увеличивающей цепью (в двудольном графе, относительно некоторого паросочетания) назовём чередующуюся цепь, у которой начальная и конечная вершины не принадлежат паросочетанию.

Алгоритм решает следующую задачу пусть дан взвешенный полный двудольный граф c целыми весами ребер

K_{n, n}

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

Функцию

ϕ

назовём потенциалом, если для любых вершин

i

и

j

выполняется условие:

ϕ (i) + ϕ (j) \leq g ((i, j))

где

g ((i, j))

— стоимость ребра между

i

и

j

. Значением потенциала называется сумма потенциалов всех вершин.

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

Алгоритм работает с жёсткими рёбрами — теми, для которых выполняется равенство:

ϕ (i) + ϕ (j) = c (i, j)

Если обозначить подграф из таких рёбер как

G_{ϕ}

, то стоимость любого совершенного паросочетания в

G_{ϕ}

(при его существовании) в точности равна значению потенциала

ϕ

.

Алгоритм работает с матрицей весов графа.

Вспомогательный алгоритм (алгоритм Куна)

Алгоритм

1.Берем пустое паросочетание;
2.Пока в графе удается найти увеличивающую цепь, выполняется чередование паросочетание вдоль этой цепи, и повторять процесс поиска увеличивающей цепи.
1. a.Как только не удалось найти увеличивающую цепь, процесс поиска останавливается, текущее паросочетание максимально.

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

Алгоритм последовательно обрабатывает все вершины

v

первой доли

(v = 1, \dots, n_{1})

:

Если вершина $v$ уже насыщена текущим паросочетанием (т. е. уже соединена с какой-то вершиной второй доли), то она пропускается.
В противном случае алгоритм пытается насытить $v$ путём поиска увеличивающей цепи, начинающейся в этой вершине.

Для поиска используется обход в глубину (DFS) (реже — в ширину, BFS):

1.Начинаем из ненасыщенной вершины $v$ первой доли.
2.Перебираем все рёбра, исходящие из $v$ . Пусть текущее ребро ведёт в вершину второй доли.
- oЕсли ненасыщенна, то цепь найдена — это просто ребро $(v,)$ .
  - Действие: добавляем $(v,)$ в паросочетание и завершаем поиск.
- oЕсли уже насыщена ребром $(p,)$ , то продолжаем поиск из $p$ .
  - Таким образом, мы пытаемся построить чередующуюся цепь вида $(v,), (, p), \dots$ .
3.Обход продолжается, пока либо не будет найдена увеличивающая цепь, либо не станет ясно, что такой цепи не существует.

Результат обхода

Если цепь найдена, то вершина $v$ становится насыщенной, и мощность паросочетания увеличивается на 1.
Если цепь не найдена, то вершина $v$ остаётся ненасыщенной (и в текущем паросочетании её уже нельзя покрыть).

Завершение работы алгоритма

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

Алгоритм для равных долей

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

ϕ

(в виде массивов

u

и

v

) и ориентацию (направление) каждого жёсткого ребра. Эта ориентация обладает ключевым свойством: рёбра, направленные от

T

к

S

, формируют паросочетание, обозначаемое

M

. Ориентированный граф, состоящий из жёстких рёбер с заданной ориентацией, обозначается как

\vec{G_{ϕ}}

.

Шаг 1. В начале алгоритма потенциал полагается равным нулю и паросочетание

M

полагается пустым.

Цикл. На каждом шаге алгоритм пытается увеличить мощность текущего паросочетания

M

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

G_{ϕ}

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

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

1.Определим множества $Z_{1}$ и $Z_{2}$ и величину Δ

 $Z ₁$ — посещённые вершины первой доли при обходе (поиске увеличивающей цепи).
 $Z ₂$ — посещённые вершины второй доли.
Δ вычисляется как:

∆ = \min_{\begin{matrix} i \in Z_{1} \\ j \notin Z_{2} \end{matrix}} {c_{ij} - u_{i} - v_{j}}

Таким образом Δ > 0, иначе существовало бы "жёсткое" ребро

(i, j)

, ведущее к противоречию с определением

Z_{1}

и

Z_{2}

.

2.Корректировка потенциалов
- Для всех $i \in Z_{1}$ : $u_{i} = u_{i} + ∆$
- Для всех $i \in Z_{2}$ : $v_{j} = v_{j} - ∆$

Корректность потенциала сохраняется: для рёбер

(i, j)

, где

i \in Z_{1}

и

j \notin Z_{2}

:

u_{i} + v_{j} \leq c_{ij}

(по выбору Δ). Для остальных комбинаций

i, j

неравенство

u_{i} + v_{j} \leq c_{ij}

либо не изменилось, либо усилилось.

Жёсткие рёбра паросочетания остаются: ребра

(i, j)

паросочетания могли измениться только если

i \notin Z_{1}

и

j \in Z_{2}

, но такие рёбра не входят в

M

(так как

i

не была посещена).

3.Рост достижимого множества

После пересчёта все ранее достижимые вершины остаются достижимыми. Появится хотя бы одно новое жёсткое ребро

(i, j)

(где

i \in Z_{1}

,

j \notin Z_{2}

), делающее вершину

j

достижимой. Таким образом,

∣ Z 1 ∣ + ∣ Z_{2} ∣

строго увеличивается.

4.Конечность алгоритма

Поскольку размер

∣ Z_{1} ∣ + ∣ Z_{2} ∣

не может превысить

n_{1} + n_{2}

, число пересчётов потенциалов ограничено (

O (n)

). После каждого пересчёта либо находится увеличивающая цепь, либо прогресс гарантирован.

Завершение алгоритма. Алгоритм продолжает итеративно выполнять следующие шаги:

1.Поиск увеличивающей цепи для текущего паросочетания $M$ .
2.Если цепь найдена — увеличение $M$ на единицу.
3.Если цепь не найдена — пересчёт потенциалов, расширяющий множество достижимых вершин.

Рано или поздно будет достигнут потенциал, при котором существует совершенное паросочетание

M

(если исходный граф его допускает). Это паросочетание и будет решением задачи.

Если говорить об асимптотике алгоритма, то она составляет

O (n^{4})

, поскольку всего должно произойти

n

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

n

пересчётов потенциала, каждый из которых выполняется за время

O (n^{2})

.

3.2. Модификация алгоритма для неравных долей с асимптотикой $O (n^{3})$

Ключевая идея – вместо одновременного рассмотрения всей матрицы, алгоритм последовательно добавляет строки, на каждом шаге поддерживая максимальное паросочетание для уже обработанной части. Это позволяет:

1.Локализовать пересчёты потенциалов только для новых данных.
2.Сделать алгоритм пригодным для неравных долей.
3.Снизить асимптотику до $O (n^{3})$ (или $O (n^{2} m)$ для прямоугольных матриц).

Оптимизации для асимптотики

O (n^{3})

:

Поддержка массива $minv$ , для каждого столбца $j$ хранится минимальное значение $c_{ij} - u_{i} - v_{j}$ по всем посещённым строкам $Z_{1}$ . Обновляется за $O (n)$ при добавлении новой строки в $Z_{1}$ .
Быстрый поиск $Δ$ – $Δ = \min_{j \notin Z_{2}} {\min v_{j}}$ вычисляется за $O (n)$ .
Итеративный обход Куна – после пересчёта потенциала обход продолжается с новыми жёсткими рёбрами, не перезапускаясь с нуля.

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

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

Поведение

m

-того агента

(m = 0, \dots, M - 1)

определяется следующим алгоритмом.

Шаг 1. Указать начальные условия, которые определяются:

Распределение агентов по ячейкам $(i, j, k)$ игрового поля;
«Карта осуществимости» представлена функцией $f_{a} (i_{m}, j_{m}, k_{m}, i_{n}, j_{n}, k_{n}, t_{})$
«Карта уязвимости» представлена функцией $f_{b} (i_{m}, j_{m}, k_{m}, i_{n}, j_{n}, k_{n}, t_{})$
Приблизительная оценка интервала семплирования.

Шаг 2. Для текущего распределения агентов и целей на текущий момент

t_{}

:

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

Шаг 3. Если как минимум одно из условий для завершения игры выполнено на момент

t_{}

:

Получение информации о пометке всех агентов.
Получение информации о пометке всех целей.
Тогда перейти к шагу 6, иначе перейти к шагу 4.

Шаг 4. Выполним идентификацию свободных параметров

{λ_{m}}_{m = 0, \dots, M - 1}

марковского процесса, полагая

| v_{k} | \leq v_{\max}

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

{λ_{m}}_{m = 0, \dots, M - 1}

, со средними значениями

{\bar{τ}}_{λ * = \frac{1}{λ_{}}}

,

{\bar{τ}}_{μ * = \frac{1}{μ_{}}}

и

{\bar{τ}}_{ν * = \frac{1}{ν_{}}}

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

t_{} + ∆ t

, принимая в расчет всех агентов.

obj = \sum_{n = 0, \dots, N - 1} p (A_{n} | D_{1 n} + \dots + A_{n} | D_{mn})

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

iobj

, в момент времени

t_{} + ∆ t

(при условии равновероятного выбора цели).

iobj = \sum_{n = 0, \dots, N - 1} \frac{p (A_{n} \lor D_{mn})}{N} (m = 0, \dots, M - 1)

Перейти к шагу 5.

Шаг 5. Для каждого агента выбрать ячейку игрового поля, смежную с ячейкой, в которой он находится в момент времени

t_{}

используя «метод рулетки», с вероятностями выбора пропорциональми предсказанным байесовским оценкам

p ({\tilde{H}}_{i_{m} j_{m} k_{m} m} \lor C_{k}) = \frac{p (C_{k} \lor {\tilde{H}}_{i_{m} j_{m} k_{m} m}) p ({\tilde{H}}_{i_{m} j_{m} k_{m} m})}{p (C_{k})} = \frac{p ({\tilde{H}}_{i_{m} j_{m} k_{m} m})}{p (C_{k})}

и вероятностям

p ({\tilde{H}}_{i_{m} j_{m} k_{m} m})

, рассчитанным для момента времени

t_{} + Δ t

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

$| v_{m} | \leq v_{\max}$
$p (B | H_{ijk}) \leq p_{B}$

Если не выполнено условие 1, установить скорость перемещения

| v_{k} |

равной

v_{\max}

, если не выполнено второе условие, не перемещаться. На текущий такт игры, интервал

Δ t

определяется как максимальное время необходимое для перемещения между центрами соседних ячеек:

Δ t = \max_{m \in {0, \dots, M - 1}} \frac{Δ l_{m}}{| v_{m} |}

, где

Δ l_{m} = \sqrt{{(∆ l_{λ, m})}^{2} + {(∆ l_{μ, m})}^{2} + {(∆ l_{ν, m})}^{2}}

Переходы агентов между состояниями синхронизированы по интервалу

Δ t

который одинаков для всех объектов.

Перейти к следующему по порядку дискретному моменту времени

t_{} + Δ t

, и далее полагать его текущим моментом времени. Перейти к шагу 2.

Шаг 6. Завершить игру.

Задача идентификации решается по методу, предложенному в статье [Kuravsky, 2015].

Выводы

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

Поведение агентов определяется вспомогательным алгоритмом, который включает:

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

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

Разработка вероятностной модели поведения многоагентной системы в трехмерном пространстве

Резюме

Общая информация

Полный текст

Введение

Описание поведения системы

Построение пар атак

Вспомогательный алгоритм (алгоритм Куна)

Алгоритм для равных долей

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

Выводы

Литература

Информация об авторах

Метрики

Просмотров web

Скачиваний PDF

Всего