Автоматика и телемеханика, № 2, 2021

Робастное, адаптивное и сетевое

управление

(Институт проблем управления им. В.А. Трапезникова РАН, Москва)

АСИНХРОННЫЕ МНОГОАГЕНТНЫЕ МНОГОСОРТНЫЕ СИСТЕМЫ¹

Асинхронная многоагентная многосортная система (АММС) - это сеть

из пороговых элементов (агентов), функционирующая в непрерывном

времени. Агенты находятся либо в активном, либо в пассивном состоя-

нии. В активном состоянии агент генерирует сигнал определенного сорта

(цвета). Сигнал воспринимается всеми агентами, имеющими входы то-

го же цвета. Агент обладает потенциалом, изменяющимся под возбуж-

дающим или тормозящим действием сигналов; он активен, только если

его потенциал превышает порог. Изменения активности агентов являют-

ся событиями, разбивающими временную шкалу на такты - временные

интервалы, внутри которых состояние системы не меняется. Последова-

тельность состояний системы называется ее поведением. Исследуется за-

висимость автономного поведения сети от значений ее параметров.

Ключевые слова: асинхронная система, пороговый элемент, многосортные

сигналы, автономное поведение, события.

DOI: 10.31857/S0005231021020082

1. Введение

Модель, описываемая в данной статье, возникла по двум причинам. Во-

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

ми [1]. В предлагаемой модели опущены биологические сущности; в резуль-

тате вместо сети нейронов, обменивающихся химическими сигналами (нейро-

трансмиттерами), появляется сеть из абстрактных агентов, которые обмени-

ваются сигналами разных сортов, циркулирующими в едином пространстве

сигналов и в едином асинхронном времени. Многосортность сигналов озна-

чает, что каждый агент воспринимает только сигналы определенных сортов

и “не слышит” остальные сигналы.

Во-вторых, правомерно рассматривать эту модель как многоагентную си-

стему (МАС), хотя, возможно, это не согласуется с существующей традици-

ей теории МАС. Дело в том, что уже многие годы в этой теории домини-

рует парадигма BDI-архитектуры [2], в которой агенты обладают убежде-

ниями, желаниями и намерениями. Однако, как отмечено в обзоре [3], этот

¹ Работа выполнена при частичной финансовой поддержке Российского фонда фунда-

ментальных исследований (проекты №№ 17-29-07029, 20-07-00190).

132

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

ных и вычислительно неэффективных логических средств. В резюме это-

го обзора отмечается, что “в новой парадигме формализации МАС раци-

онально строить как множество простых агентов с богатой компонентой

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

эволюции, присущих живым системам”. Предлагаемая модель удовлетворя-

ет, по крайней мере, требованиям простоты агентов и разнообразию типов

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

Асинхронность - еще одна важная особенность предлагаемой модели.

Асинхронные дискретные модели появились в 50-х гг. ХХ в. в логической схе-

мотехнике [4]. Их главная особенность - зависимость поведения от временных

параметров элементов логических схем. Одной из важных задач проектиро-

вания асинхронных схем всегда являлось преодоление этой зависимости с

целью обеспечения детерминированного поведения схемы [5, 6]. В данной ра-

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

симость от временных параметров оказывается достоинством: она порожда-

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

изменении параметров. Сеть, в которой зафиксированы все основные пара-

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

Краткое изложение первых трех разделов настоящей статьи (без доказа-

тельств теорем 2 и 3) опубликовано в [7].

2. Формальная модель - основные определения

Асинхронная многоагентная многосортная система (АММС) S опреде-

ляется как S = < N, C, H, T >, где N = {N₁, . . . , N_n} - множество агентов,

C = {c₁,...,c_m} - множество абстрактных цветов (сортов), H - множество

параметров системы, T - непрерывное время, в котором происходят собы-

тия. Агенты могут находиться в одном из двух состояний - активном и пас-

сивном. Событиями являются моменты изменения состояния любого агента.

Переход агента из пассивного состояния в активное иногда будем называть

включением, а переход из активного состояния в пассивное - выключением.

События разбивают непрерывную шкалу времени на отрезки - такты.

Границы тактов (точки на этой шкале, т.е. моменты наступления событий)

нумеруются натуральными числами и называются дискретными моментами

времени. Такт t - это интервал между моментами t и t + 1, т.е. между дву-

мя соседними событиями. Такты имеют разную длительность; длительность

такта t обозначается τ(t). Текущее состояние активности агента N_i задает-

ся величиной y_i(t) ∈ {0, 1}; y_i(t) = 1 означает, что на такте t агент активен;

y_i(t) = 0 означает, что на такте t агент пассивен.

Выходы, входы и сигналы. В активном состоянии агент N_i генерирует сиг-

нал, характеризуемый цветом c_j и мощностью d_ij . Мощность задается мат-

рицей D = ∥d_ij ∥_n×m, в которой строки соответствуют агентам, а столбцы -

цветам. Агент N_i обладает входами, каждый из которых имеет цвет из мно-

жества C. Разные входы имеют разные цвета; вход цвета c_j имеет вес w_ij ∈ R.

Вес w_ij = 0 означает, что у агента N_i нет входов цвета c_j ; w_ij > 0 означает,

что сигнал, пришедший на вход цвета c_j, оказывает на агента возбуждаю-

133

щее воздействие, w_ij < 0 означает тормозное воздействие. Множество весов

также удобно задавать матрицей W = ∥w_ij ∥_n×m.

По характеру активности агенты делятся на два типа: инициативный и

реактивный. Инициативный агент переходит в пассивное состояние только

при достаточно сильных тормозящих воздействиях; в остальное время он

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

возбуждающих воздействиях; в остальное время он пассивен.

Совокупность цветов, присвоенных входам и выходу агента N_i, а также

знаки весов его входов будем называть разметкой агента. Разметки агентов

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

агента N_k к агенту N_l существует, если N_l имеет вход, цвет которого совпа-

дает с цветом выхода N_k. Будем считать, что эта связь имеет тот же цвет.

Тем самым разметка всех агентов однозначно порождает раскрашенный ори-

ентированный граф системы S, который будем называть размеченной сетью

(или просто сетью) Σ_S системы S.

Из приведенных определений следует, что сигнал цвета c_j будет воспринят

только теми агентами, которые имеют входы цвета c_j . Иначе говоря, сигналы

в системе являются, с одной стороны, широковещательными, а с другой - из-

бирательными. Заметим также, что в АММС возможны “скрытые” входы и

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

ды или только выходы. В автономной (не имеющей внешних входов) системе

такой цвет не будет влиять на ее функционирование.

Внешним (наблюдаемым) состоянием системы в момент t называется век-

тор состояний активности всех агентов системы, т.е. вектор Y (t) = (y₁(t),

...,y_n(t)).

Пространство сигналов описывается вектором X(t) = (x₁(t), . . . , x_m(t)),

где x_j (t) - суммарная мощность сигналов цвета c_j, генерируемых на протя-

жении такта t и распространяемых по связям этого цвета. Она вычисляется

по формуле

∑

(1)

x_j(t) =

d_ijy_i

(t) .

i=1

В матричном виде эта формула принимает вид

(1а)

X(t) = Y (t) × D,

где X(t) - вектор-строка пространства сигналов, Y(t) - вектор-строка актив-

ности нейронов.

Потенциалы агентов. Агент N_i имеет потенциал U_i(t) - непрерывную ве-

личину, которая может изменяться в интервале U_i0 ≤ U_i(t) ≤ U_imax. Агент

активен, если величина U_i(t) не меньше порогового значения P_i, которое так-

же находится в интервале U_i0 < P_i < U_imax:

{

1, если U_i(t) ≥ P_i;

(2)

y_i(t) =

иначе.

134

Значения U_i0, U_imax и P_i специфичны для каждого агента.

Потенциал агента N_i внутри такта меняется, но не создает событий; важны

только его значения U_i(t) и U_i(t + 1). Внутри такта потенциал изменяется

линейно, т.е. с постоянной в пределах такта суммарной скоростью v_i(t):

(3)

v_i (t) = s_i (t) + v^αien

(t),

где s_i(t) - экзогенная скорость, пропорциональная силе внешних воздействий:

∑

(4)

s_i (t) = h

w_ijx_j

(t),

j=1

v^αien - эндогенная скорость, т.е. собственная скорость агента, не зависящая от

внешних воздействий; в дальнейшем полагаем h = 1. Перепишем (4) в мат-

ричном виде:

(4а)

S(t) = X(t) × W^T,

где S(t) - вектор-строка экзогенных скоростей (сил внешних воздействий),

X(t) - вектор-строка пространства сигналов, W^T - транспонированная мат-

рица весов.

Каждый агент имеет два значения эндогенной скорости:

{ v^0ien, если U_i (t) < P_i,

(5)

v^αien(t) =

v^1ien, если U_i (t) ≥ P_i,

причем для инициативного агента обе скорости положительны, для реактив-

ного агента обе скорости отрицательны и для обоих типов агентов v^0ien < v^1ien.

Параметры системы. Параметры, определяющие систему S (формулы

(1)-(5)), разбиваются на два класса: статические (не меняющиеся в процес-

се функционирования) и динамические параметры. Статические параметры

(количество входов, их веса, величина порога и др.) образуют множество H,

описываемое табл. 1. Динамические параметры (y_i(t), U_i(t), v_i(t) и др.) меня-

ются со временем.

Будем считать, что асинхронная система S = < N, C, H, T > состоит из

двух компонентов: размеченной сети Σ_S и ее параметров. Cеть Σ_S системы S

определяется множествами N, C и разметками агентов; множество парамет-

ров H задается табл. 1.

Таблица 1. Статические параметры системы

P_i U^maxi U⁰ⁱ v^0ien v^1ien d_i1 ... d_1m w_i1 ... w_im

N₁

P₁

U^max1

U⁰¹

v^01en v^11en d₁₁ ... d_1m w₁₁ ... w_1m

N_i

U⁰ⁱ

N_n P_n U^maxn U⁰ⁿ v^0nen v^1nen d_n1 ... d_nm w_n1 ... w_nm

135

Такое разделение позволяет говорить об изменениях параметров без из-

менения сети. Две АММС, имеющие одну и ту же сеть Σ, но отличающиеся

наборами значений параметров H_k и H_l, будем называть конфигурациями

сети Σ и обозначать как Σ(H_k) и Σ(H_l).

3. Динамика системы и ее вычисление

3.1. Динамические параметры системы

Последовательность состояний Y (0), Y (1),. . . , порождаемую системой, бу-

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

ное поведение системы, т.е. поведение при отсутствии внешних воздействий.

Алгоритм, вычисляющий ее поведение, должен по заданному состоянию си-

стемы в момент t вычислить ее состояние в момент t + 1. Однако в асинхрон-

ной системе вычислению состояния в момент t + 1 предшествует вычисле-

ние самого момента t + 1, т.е. длительности τ(t) такта [t, t + 1) и положения

момента t + 1 на шкале непрерывного времени. Это вычисление связано с

пересчетом на каждом такте динамических параметров системы.

К уже введенным ранее динамическим параметрам y_i(t), x_j(t), U_i(t), s_i(t),

v_i(t) добавим несколько новых динамических параметров.

Остаточным потенциалом ΔU_i(t) в момент t назовем величину, равную

“расстоянию” до наступления ближайшего события, связанного с агентом N_i.

Ближайшее событие для агента N_i определяется таблицей переходов, одина-

ковой для обоих типов агентов; ее вид приведен в табл. 2. Знак ∞ означает,

что значение потенциала агента N_i в такте t не достигнет порога и ближай-

шее событие не связано с агентом N_i. Если v_i(t) = 0, то ΔU_i(t) = ΔU_i(t - 1),

поэтому этого случая в таблице нет.

Таблица 2. Таблица переходов для агентов

U_i(t)

Знак v_i(t)

Ближайшее событие

ΔU_i(t)

U_i(t) ≥ P_i

Движение вверх, активность не меняется,

∞

события нет

U_i(t) ≥ P_i

y_i = 0

U_i(t) - P_i

U_i(t) < P_i

y_i = 1

P_i - U_i(t)

U_i(t) < P_i

Движение вниз, активность не меняется,

∞

события нет

Остаточное время τ_ri(t) агента N_i - это время до достижения ближайшего

события при текущем потенциале U_i(t) и скорости v_i(t). Знак ∞ означает,

что это время не влияет на вычисление следующего события.



U_i(t)



если v_i = 0 и ΔU_i (t) = ∞,

(6)

τ_ri(t) =

⌈v_i(t)⌉



∞ в остальных случаях.

136

3.2. Алгоритм функционирования автономной АММС

и его вычислительная сложность

Теорема 1. Поведение автономной АММС однозначно определяется

вектором U(0) = (U₁(0), . . . , U_n(0)) и множеством ее статических пара-

метров H.

Доказательством служит алгоритм, который по заданным U(t) и H вы-

числяет Y (t) и U(t + 1) для любого t.

Этот алгоритм выглядит так:

1. Вектор Y (t) вычисляется по формуле (2).

2. Вектор X(t) вычисляется по формуле (1а).

3. Силы воздействия s₁(t), . . . , s_n(t) вычисляются по формуле (4а).

4. Суммарные скорости v₁(t), . . . , v_n(t) вычисляются по формулам (3), (5).

5. Остаточные потенциалы вычисляются по табл. 2.

6. Остаточные времена вычисляются по формуле (6).

7. Ищется минимальное остаточное время τ_min(t). Если τ_min(t) = τ_i(t), то:

- длина такта t τ(t) = τ_i(t);

- событием является изменение активности агента N_i;

- состояние Y (t + 1) отличается от Y (t) значением y_i(t + 1).

8. Потенциалы для момента t + 1 пересчитываются по формуле





U_imax, если U_i(t) + τ(t)v_i(t) ≥ U_imax,

(7)

U_i(t + 1) =

U_i0,

если U_i(t) + τ(t)v_i(t) ≤ U_i0,



U_i (t) + τ (t) v_i (t) в остальных случаях.

9. Перейти к п. 1 для t + 1.

Оценим вычислительную сложность шага этого алгоритма, воспользовав-

шись матричным представлением формул (1a) и (4a). Известно, что слож-

ность произведения матриц A_∥l×k∥ × B_∥k×p∥ имеет порядок O(lkp). В форму-

ле (1а) имеем l = 1, k = n, p = m. Поэтому сложность вычисления (1а) рав-

на O(mn). Аналогично получаем, что сложность вычисления формулы (4а)

также равна O(mn). Остальные шаги имеют сложность, не превосходящую

O(n). Поэтому сложность вычисления одного такта имеет порядок O(mn).

Важно отметить, что эта сложность линейна относительно числа агентов n,

поскольку естественно считать, что число сортов сигналов m растет гораздо

медленнее, чем число агентов.

Теорема 1 дает основание называть вектор U(t) внутренним состоянием

АММС.

3.3. Примеры

Пример 1. На рисунке показана размеченная сеть Σ₁, где N₁ и N₃ -

инициативные агенты, N₂ - реактивный агент. Приведем расчет динамиче-

ских параметров для конфигурации Σ₁(H₁) и начального состояния U(0) =

= (0,9; 0; 0,9). Набор статических параметров H₁ задан табл. 3.

137

Сеть примера 1.

Момент t = 0:

Начальное состояние (текущие потенциалы): U(0) = (0,9; 0; 0,9).

1. Начальное внешнее состояние Y (0) = (1; 0,1).

2. X(0) = (0,5; 0,3).

3. Силы воздействия:

s₁(0) = w₁₂x₂(0) = -0,3;

s₂(0) = w₂₁x₁(0) = 1;

s₃(0) = w₃₁x₁(0) + w₃₂x₂(0) = -0,15 - 0,3 = -0,45.

4. Суммарные скорости:

v₁(0) = s₁(0) + v^11en = -0,3 + 0,8 = 0,5,

v₂(0) = s₂(0) + v^02en = 1 - 0,8 = 0,2,

v₃(0) = s₃(0) + v^13en = -0,45 + 0,8 = 0,35.

5. Остаточные потенциалы:

ΔU₁(0) = ∞ (строка 1 табл. 2),

ΔU₂(0) = P₂ - U₂(0) = 0,6,

ΔU₃(0) = ∞ (строка 1 табл. 2).

6. Остаточные времена:

τ_r1(0) = ∞;

τ_r2(0) = ΔU₂(0)/ | v₂(0) |= 0,6/0,2 = 3;

τ_r3(0) = ∞.

7. Минимальное остаточное время τ_min(0) = τ₂(0) = 3.

Соответственно, длина такта [0, 1] будет τ(0) = 3.

Событие, произошедшее в момент 1, - включение нейрона N₂.

8. Потенциалы для момента t = 1:

U (1) = (0,9; 0,6; 0,9).

Таким образом, к моменту t = 1 получаем внешнее состояние Y (1) =

= (1, 1, 1), внутреннее состояние U(1) = (0,9; 0,6; 0,9) и начальный отрезок по-

ведения 101, 111. Это дает возможность начать расчет для момента t = 1.

138

Таблица 3

P_i

U_imax

U_i0

v^0ien

v^1ien

d_i1

d_i2

w_i1

w_i2

N₁

0,6

0,9

0,5

0,8

0,5

-1

N₂

0,6

0,9

-0,8

-0,5

1,0

N₃

0,6

0,9

0,5

0,8

0,3

-0,5

-1

Таблица 4

№t

Y (t)

101

111

110

010

000

100

101

111

U₁(t)

0,9

0,7

0,6

0,3

0,6

0,9

U₂(t)

0,6

0,8

0,9

0,6

0,12

0,36

0,6

U₃(t)

0,9

0,6

0,225

0,3

0,6

0,9

x₁

0,5

x₂

0,3

1,3

0,3

1,3

τ (t)

0,4

0,5

0,6

1,2

0,4

v₁

0,5

-0,5

-0,2

-0,5

0,5

0,8

0,5

-0,5

v₂

0,2

0,5

-0,5

-0,8

0,2

0,5

v₃

0,25

-0,75

-0,5

0,5

0,25

-0,75

Полный протокол вычисления поведения (вместе с изменениями динами-

ческих параметров) конфигурации Σ₁(H₁) приведен в табл. 4.

Видно, что внутренние состояния в тактах 1 и 7 повторяются. Из теоремы 1

следует, что в дальнейшем отрезок протокола, образованный столбцами 1-6,

будет повторяться в дальнейшем.

Пример 2. Рассмотрим теперь поведение конфигурации Σ₁(H₂), в кото-

рой набор параметров H₂ получен из H₁ заменой значения d₁₁ = 0,5 на d₁₁ =

= 0,3. Для этого достаточно изменить некоторые величины в приведенном

выше расчете. Получим: X(0) = (0,3; 0,3); s₂(0) = w₂₁ · x₁(0) = 0,6; отсюда

v₂(0) = s₂(0) + v^02en = 0,6 - 0,8 = -0,2, т.е. суммарная скорость роста потен-

циала N₂ становится отрицательной и потенциал N₂ не растет. Формально

это означает, что для ΔU₂(0) выполняются условия строки 4 таблицы 2, т.е.

ΔU₂(0) = ∞. В результате все остаточные потенциалы получают значение ∞,

а это означает, что процесс остановился в самом начале, и поведение конфи-

гурации Σ₁(H₂) состоит из одного начального внешнего состояния 101.

Эти два примера показывают, что одна и та же сеть при разных парамет-

рах может генерировать различное поведение. Множество всех ее возможных

поведений будем называть репертуаром поведений сети. Ниже будут рассмот-

рены некоторые задачи анализа репертуара поведений автономной сети.

4. Анализ репертуара поведений автономной пороговой сети

Напомним ряд известных понятий. Бесконечная последовательность

a₀,a₁,... ,a_k-1,a_k,... ,a_l-1,... называется периодической, если некоторый ее

отрезок a_k, . . . , a_l-1 повторяется бесконечное число раз. Этот отрезок назы-

вается периодом, а отрезок a₀, a₁, . . . , a_k-1 - предпериодом. Такая последо-

139

вательность записывается как a₀, a₁, . . . , a_k-1, (a_k, . . . , a_l-1). Длиной предпе-

риода является целое число k ≥ 0, а длиной периода - целое число l - k ≥ 1.

В поведении АММС два вектора Y (t), Y (t + 1) всегда отличаются хотя

бы в одном разряде, потому что в момент t + 1 изменилось состояние, по

крайней мере, одного агента. Поэтому для АММС случай l - k = 1 соответ-

ствует тому, что начиная с момента k, событий не происходит: потенциалы

всех агентов соответствуют строкам 1 или 4 табл. 2 и последовательность

Y (0), . . . , Y (k - 1), Y (k) становится конечной. Такое поведение будем назы-

вать стационарным; его заключительное состояние Y (k) также стационарно.

Поведение конфигурации Σ₁(H₂) (пример 2) - это пример стационарного по-

ведения длины 1; его начальное состояние является одновременно заключи-

тельным и, следовательно, стационарным.

При l - k > 1 бесконечное поведение Y (0), . . . , Y (k - 1), (Y (k), . . . , Y (l - 1))

будем называть периодическим поведением. Поведение конфигурации Σ₁(H₁)

(пример 1) - это пример периодического поведения, в котором длина периода

равна 6, а длина предпериода равна 1.

Теорема 1 показывает, что автономную АММС можно интерпретировать

как автономный автомат, в котором состояниями являются векторы U(t). Из

теории конечных автоматов [8] известно, что автономный конечный автомат

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

периода, так и предпериода не превосходит число M состояний. Это объясня-

ется тем, что благодаря конечности числа состояний не позднее, чем через M

тактов, появится состояние Y (t), t ≤ M, которое совпадет с одним из преды-

дущих состояний Y (t^′), t^′ < t и возникнет периодическая последовательность

c периодом (Y (t^′), . . . , Y (t-1)), длина которого меньше M. Однако в автоном-

ной АММС это рассуждение не проходит, поскольку множество возможных

значений потенциалов бесконечно, и вопрос о том, всегда ли автономная АС

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

тым. Здесь ограничимся некоторыми простыми утверждениями.

Начальное состояние сети U (0) будем называть естественным, если для

любого инициативного агента N_i выполняется U_i(0) > P_i, а для любого реак-

тивного агента N_j выполняется U_j (0) < P_j .

Теорема 2. Для любой автономной асинхронной сети Σ и любого ее

естественного состояния U(0) существует такой набор параметров H,

при котором в конфигурации Σ(H)U(0) является стационарным.

Доказательство. Пусть U(0) - естественное начальное состояние. Из

табл. 2 видно, что оно будет стационарным, если суммарные скорости для

всех инициативных агентов положительны, а для всех реактивных агентов

отрицательны. Поэтому из (3), (4) получаем, что искомый набор параметров

должен удовлетворять следующим условиям:

∑

w_ijx_j (0) + v^1ien > 0, если N_i - инициативный агент;

j=1

(8)

∑

w_ijx_j (0) + v^0ien < 0, если N_i - реактивный агент.

j=1

140

Конкретный набор значений, удовлетворяющий условиям (8), можно по-

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

∑_m

w_ij и d_ij; при этом для всех агентов сформируются суммы

w_ijx_j (t).

j=1

Найдем среди них максимальную и минимальную суммы. Затем назначаем

эндогенные скорости v^αien(t), удовлетворяющие (8):

1) для инициативных агентов:

∑

если max

w_ijx_j (t) > 0, то v^1ien - любое положительное число;

j=1



∑



∑



если max

w_ijx_j (t) ≤ 0, то v^1ien >

max

w_ijx_j (t);



j=1



j=1



2) для реактивных агентов:

∑

если min

w_ijx_j (t) < 0, то v^0ien - любое отрицательное число;

j=1



∑



∑



если min

w_ijx_j (t) ≥ 0, то v^0ien < -min

w_ijx_j (t).



j=1



j=1



Теорема доказана.

Если U (0) не является естественным, теорема может стать неверной: ко-

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

скорость положительна и через некоторое время он станет активным. Ана-

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

суммарная скорость отрицательна и через некоторое время он станет пассив-

ным.

Теорема 3. Существуют сети, все поведения которых стационарны.

Покажем, что такими сетями являются все ациклические сети. Пусть Σ -

ациклическая сеть. Тогда 1) у нее есть агенты-источники, у которых нет вход-

ных связей, и агенты-стоки, у которых нет выходных связей; 2) для любого

агента N_i остальные агенты делятся на три группы: а) предки N_i - агенты,

из которых есть пути к N_i; б) потомки N_i - агенты, к которым есть пути

из N_i; в) остальные агенты.

Ацикличность сети позволяет провести ранжирование всех агентов по са-

мому длинному пути из источника: агент N_i получает ранг j, если самый

длинный путь из источников в N_i имеет длину j. Заметим, что при такой

ранжировке а) агент ранга j обязательно имеет входящее ребро от некото-

рого агента ранга j - 1; б) все предки агента ранга j имеют строго меньшие

ранги; в) между агентами одного ранга связей нет.

Рассмотрим множество агентов-источников, т.е. агентов ранга 0. Так как

они не имеют воздействий от других агентов сети, то наступит момент t₀, ко-

гда все они перейдут в стационарное естественное состояние: инициативные

агенты станут стационарно активными, а реактивные агенты - стационарно

пассивными. С этого момента все сигналы, идущие к агентам ранга 1, стано-

вятся стационарными и, следовательно, суммарные скорости агентов ранга 1

141

перестанут изменяться. Поэтому наступит момент t₁, когда все агенты ран-

га 1 перейдут в стационарное состояние. Рассуждая индуктивно, допустим,

что существует момент t_j, в котором все агенты ранга j перешли в стационар-

ное состояние. С этого момента все сигналы, идущие к агентам ранга j + 1,

становятся стационарными и, следовательно, суммарные скорости агентов

ранга j + 1 перестанут изменяться. Поэтому наступит момент t_j+1, когда все

агенты ранга j + 1 перейдут в стационарное состояние. Отсюда следует, что

наступит момент t_max, когда агенты с максимальным рангом перейдут в ста-

ционарное состояние, что и доказывает теорему.

5. Анализ устойчивости поведения автономной сети

к изменениям ее параметров

5.1. Постановка задачи и пример

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

является вопрос об устойчивости конкретного поведения сети к изменениям

параметров ее элементов. Точная постановка задачи такова. Задана сеть Σ,

конкретная конфигурация Σ(H) и ее начальное состояние. Каковы области

изменения параметров сети, при которых это поведение не изменяется?

Здесь ограничимся случаем, когда изменяется один параметр. Для этого

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

ведение сети Σ на множестве конфигураций Σ(H_p) таких, что в любых двух

конфигурациях Σ(H_pi) и Σ(H_pj) из этого множества наборы H_pi и H_pj отлича-

ются только значениями параметра p. Задача заключается в том, чтобы для

любого начального состояния Y (0) найти множество положительных чисел

h₁,h₂,..., разбивающих полуось значений параметра p на такие интерва-

лы [0, h₁), [h₁, h₂), . . . , [h_k-1, h_k), . . . , что поведения конфигураций Σ(H_pi) и

Σ(H_pj) одинаковы, если p_i и p_j находятся внутри одного интервала, и различ-

ны, если p_i и p_j находятся в разных интервалах. Такие интервалы назовем

интервалами устойчивости поведения сети относительно параметра p.

Пример 3. Сначала в качестве примера проведем поиск начального ин-

тервала устойчивости [0, h₁) поведения сети на рисунке относительно пара-

метра d₁₁. Как и в предыдущих примерах, начальным внутренним состоянием

является U(0) = (0,9; 0; 0,9).

Как видно из примера 2, при d₁₁ = 0,3 поведение является стационарным.

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

Область устойчивости этого поведения, как следует из табл. 2 (строка 1 для

N₁ и N₃, строка 4 для N₂), определяется следующими неравенствами:

(9)

v₁(0) ≥ 0, v₂(0) ≤ 0, v₃

(0) ≥ 0.

Раскрывая суммарные скорости, получим:

s₁(0) + v^11en ≥ 0, т.е. s₁(0) ≥ -0,8,

(10)

s₂(0) + v^02en < 0, т.е. s₂(0) < 0,8,

s₃(0) + v^13en ≥ 0, т.е. s₃(0) ≥ -0,8.

142

Подставим вместо s_i(0) их выражения из шага 3 алгоритма:

(11)

w₁₂x₂(0) ≥ -0,8, или w₁₂d₃₂

≥ -0,8,

(12)

0,8 ≥ w₂₁x₁(0), или

0,8 ≥ w₂₁d₁₁,

(13)

w₃₁x₁(0) + w₃₂x₂(0) ≥ -0,8, или w₃₁d₁₁ + w₃₂d₃₂

≥ -0,8.

Если в эти формулы подставить значения весов w_ij из табл. 4, то получим:

(14)

-d₃₂ ≥ -0,8 т.е. d₃₂

≤ 0,8,

(15)

0,8 ≥ 2d₁₁, т.е. d₁₁

≤ 0,4,

(16)

−0,5d₁₁ - d₃₂ ≥ -0,8, т.е. 0,5d₁₁ + d₃₂

≤ 0,8,

причем неравенство (16) слабее, чем (15), и является лишним.

Видно, что при значениях d₁₁ ≤ 0,4 поведение сети не изменится, посколь-

ку суммарная скорость v₂(0) останется отрицательной. Поэтому 1) стацио-

нарное поведение сети рисунке, описанное в примере 2, остается неизмен-

ным, если d₁₁ находится в интервале (0, 0,4], а остальные параметры сети не

меняются; 2) при d₁₁ > 0,4 поведение сети должно измениться.

Для поиска верхней границы этого поведения воспользуемся описываемым

ниже методом.

Пусть для заданного начального состояния Y (0) вычислены границы по-

луинтервала [h_k-1, h_k) устойчивости относительно p. Будем искать верхнюю

границу интервала [h_k, h_k+1), а также вычислять поведение сети в этом ин-

тервале.

5.2. Метод определения границ областей устойчивости

для одного параметра p

Идея метода заключается в том, чтобы провести вычисления алгоритма

п. 3.2 со значением параметра p = h_k + ε, где ε - неизвестное положительное

число. В ходе этих вычислений будут возникать выражения, содержащие ε.

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

выше при получении неравенств (9)-(16)), будем их решать относительно ε и

среди решений вида ε < q, где q > 0, выбирать решение с наименьшим q. Ре-

шения вида ε > q выбираться не будут, поскольку они не относятся к окрест-

ности h_k. Если поведение периодично или стационарно, получим конечное

число решений вида ε < q. Тогда h_k+1 - это наименьшее из всех полученных

значений q.

Шаги базового алгоритма п. 3.2, которые будут использоваться в описании

метода, будем обозначать как А1, А2, . . . , а шаги самого метода - как М1,

М2,

Обозначим набор параметров, в котором p = h_k, через H_pk, а набор, в

котором p = h_k + ε, через H_pkε. Метод определим индуктивно: считаем, что

для первых t - 1 тактов уже вычислено поведение конфигурации Σ(H_pkε) и

найдена минимальная оценка ε < q(t - 1). Опишем шаги метода для текущего

такта t.

143

М1. Вычисляются первые 4 шага алгоритма п. 3.2 для начального сос-

тояния Y (t) и конфигурации Σ(H_pkε). При этом выражения для некоторых

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

М2. Для всех i = 1, . . . , n проверяются условия переключения агента N_i:

(17)

если y_i = 0, то v_i

> 0,

(18)

если y_i = 1, то v_i

< 0.

Для любого агента N_i, у которого ни одно из неравенств (17), (18) не

выполняется, ΔU_i(t) = ∞. Эти агенты в дальнейших вычислениях не участ-

вуют. Если ΔU_i(t) = ∞ для всех i, то процесс вычисления останавливается;

состояние Y (t) стационарно.

М3. Для остальных агентов возникнут неравенства, некоторые из которых

содержат ε. После решения этих неравенств из решений вида ε < q, q > 0,

выбирается решение q₀(t), минимальное среди всех q. Текущей оценкой для ε

полагается q₁(t) = min(q₀(t), q(t - 1)).

М4. Вычисляются шаги А5 и А6. На шаге А6 получаются равенства вида

τ_ri(t) = α_ri, где α_ri - либо положительные числа, либо выражения, содержа-

щие ε.

М5. - Если все остаточные времена равны ∞, то процесс вычисления оста-

навливается; состояние Y (t) стационарно; h_k+1 = q₁(t);

- если только для одного i τ_ri(t) = ∞, то в такте t переключается агент N_i

и состояние Y (t + 1) отличается от Y (t) состоянием агента N_i; длина такта

τ (t) = τ_ri(t); q(t) = q₁(t);

- в противном случае формируется множество A = {α^∗r}, в которое вклю-

чаются все α_ri, содержащие ε, а также наименьшее из α_ri, являющихся чис-

лами.

М6. Для каждой пары (α^∗ri, α^∗rj ) формируются два неравенства α^∗ri < α^∗rj,

α^∗ri > α^∗rj и решаются относительно ε. Верными считаются неравенство, ко-

торое дает решение вида ε < q, и соответствующее неравенство τ_ri < τ_rj или

τ_ri > τ_rj.

М7. Из верных неравенств, полученных на предыдущем шаге, находим

τ_min(t) и выполняем шаг А7, т.е. определяем следующее состояние и длину

такта.

М8. Среди правых частей неравенств вида ε < q, полученных на ша-

ге М6, находится минимальное q. Обозначим его как q₂(t). Полагаем

q(t) = min(q₂(t), q(t - 1)). Таким образом, поведение сети на первых t + 1 ша-

гах сохраняется в интервале h_k < p < h_k + q(t).

М9. Выполняется шаг А8 базового алгоритма - пересчет потенциалов.

В выражениях, полученных на этом шаге, по-прежнему возможно появле-

ние ε.

М10. Перейти к М1 для t + 1.

Пример 4. Приведем пример, поясняющий шаги М4-М7.

Пусть для сети из 3 агентов на шаге М4 получены равенства τ_r1 = 2ε,

τ_r2 = 0,5 - 0,3ε, τ_r3 = 0,4.

144

Множество А (шаг М5) состоит из правых частей этих равенств.

М6. Для каждой пары из А составляем два неравенства:

для α_r1, α_r2: 2ε < 0,5 - 0,3ε, откуда ε < 5/23 ≈ 0,21; противоположное

неравенство неверно; поэтому τ_r1 < τ_r2;

для α_r1, α_r3: 2ε < 0,4 и ε < 0,2; поэтому τ_r1 < τ_r3;

для α_r2, α_r3: 0,4 < 0,5 - 0,3ε и ε < 1/3; поэтому τ_r3 < τ_r2.

М7. Из полученных неравенств заключаем, что τ_min(t) = τ_r1.

М8. q(t) = 0,2, т.е. ε < 0,2.

Пример 5. В примере 3 было показано, что верхняя граница для интер-

вала [0, h₁) поведения сети на рисунке относительно параметра d₁₁ равна 0,4.

Применим теперь описанный выше метод для поиска верхней границы сле-

дующего интервала устойчивости [0,4, h₂). Вычисления приводятся в сокра-

щенном виде: показаны только те их места, где возникают новые оценки ε.

Момент t = 0:

Начальное состояние (текущие потенциалы): U(0) = (0,9; 0; 0,9).

1. Начальное внешнее состояние Y (0) = (1; 0,1).

2. X(0) = (0,4 + ε; 0,3).

3. Силы воздействия:

s₁(0) = w₁₂x₂(0) = -0,3;

s₂(0) = w₂₁x₁(0) = 0,8 + 2ε;

s₃(0) = w₃₁x₁(0) + w₃₂x₂(0) = -0,2 - 0,3 - 0,5ε = -0,5 - 0,5ε.

4. Суммарные скорости:

v₁(0) = s₁(0) + v^11en = -0,3 + 0,8 = 0,5,

v₂(0) = s₂(0) + v^02en = 0,8 + 2ε - 0,8 = 2ε,

v₃(0) = s₃(0) + v^13en = -0,5 - 0,5ε + 0,8 = 0,3 - 0,5ε.

5. Остаточные потенциалы:

ΔU₁(0) = ∞,

ΔU₂(0) = P₂ - U₂(0) = 0,6,

ΔU₃(0) = ∞.

Последнее равенство верно при условии, что v₃(0) = 0,3 - 0,5ε ≥ 0, откуда

ε ≤ 0,6 (Шаг М2).

6. Остаточные времена:

τ_r1(0) = ∞,

τ_r2(0) = ΔU₂(0)/ | v₂(0) |= 0,6/2ε,

τ_r3(0) = ∞.

7. Минимальное остаточное время τ_min(0) = τ₂(0) = 0,6/2ε.

Соответственно, длина такта [0, 1) τ(0) = 0,6/2ε.

Событие, произошедшее в момент 1, - включение агента N₂.

145

8. Потенциалы для момента t = 1:

U (1) = (0,9; 0,6; 0,9).

Таким образом, как и следовало ожидать, при d₁₁ > 0,4 начальное состоя-

ние Y (0) уже не стационарно и сеть генерирует новое поведение. Обозначим

его через B_04ε.

Вычисления для тактов 1, 2, 3 ничего не добавляют к оценке ε. На 4-м

такте ε исчезает из значений параметров, потому что выключился его носи-

тель N₁. На 5-м такте ε снова появляется. К этому моменту

U₁(5) = 0,6,

U₂(5) = U₂(4) + τ(4)v₂(4) = 0,6 - 0,6 · 0,8 = 0,12,

U₃(5) = 0 + 0,6 · 0,5 = 0,3.

Вычисления на такте 5 дают следующие результаты.

Момент t = 5:

1. Внешнее состояние Y (5) = (1, 0, 0).

Вычисленное поведение: 101, 111, 110, 010, 000, 100.

2. X(5) = (0,4 + ε; 0).

3. Силы воздействия:

s₁(5) = w₁₂ · x₂(5) = 0;

s₂(5) = w₂₁ · x₁(5) = 2 · (0,4 + ε) = 0,8 + 2ε;

s₃(5) = w₃₁ · x₁(5) + w₃₂ · x₂(5) = -0,5(0,4 + ε) = -0,2 - 0,5ε.

4. Суммарные скорости:

v₁(5) = s₁(5) + v^11en = 0,8,

v₂(5) = s₂(5) + v^02en = 0,8 + 2ε - 0,8 = 2ε,

v₃(5) = s₃(5) + v^03en = -0,2 - 0,5ε + 0,5 = 0,3 - 0,5ε.

5. Остаточные потенциалы:

ΔU₁(5) = ∞,

ΔU₂(5) = P₂ - U₂(5) = 0,6 - 0,12 = 0,48,

Δ₃(5) = 0,6 - 0,3 = 0,3.

6. Остаточные времена:

τ_r1(5) = ∞,

τ_r2(5) = ΔU₂(5)/ | v₂(5) = 0,48/2ε = 0,24/ε,

τ_r3(5) = 0,3/(0,3 - 0,5ε) = 0,6/(0,6 - ε).

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

0,6/(0,6 - ε) < 0,24/ε. После преобразований

получаем ε < 0,4(0,6 - ε), откуда ε < 0,1714 и 0,4 + ε < 0,5714. Поэтому

τ_r3(5) < τ_r2(5). В результате событием, произошедшим в момент 6, являет-

ся включение нейрона N₃, а верхняя граница поведения B_04ε до 5-го такта

равна 0,5714.

146

Вычисления до такта 7 ничего не добавляют к оценке ε. К моменту 7

получаем значения потенциалов, совпадающие с их значениями на такте 1:

U (7) = U(1) = (0,9; 0,6; 0,9). Таким образом, на этом такте система входит в

цикл: B₀₄ = 101, (111, 110, 010, 000, 100, 101). Поэтому новых оценок ε уже не

будет, оценка ε < 0,1714 - окончательная, верхняя граница интервала значе-

ний d₁₁, в котором сеть генерирует поведение B₀₄, равна 0,5714.

Вычисления показывают, что при d₁₁ = 0,58 поведение сети действительно

отличается от B₀₄. Протокол B₀₄ для d₁₁ = 0,5 приведен в табл. 4.

6. Заключение

Как уже было отмечено, предложенная модель интерпретируется как био-

логическая нейронная сеть с химическими взаимодействиями [1]. Кроме то-

го, ее можно интерпретировать как социальную сеть с разными типами ин-

формационных обменов. Заметим, что социальные сети с разными типами

активности уже рассматривались в [9, 10]. В нейробиологической интерпре-

тации цветные сигналы - это трансмиттеры, пространство сигналов - это

внеклеточное пространство, потенциал - это мембранный потенциал нейро-

на. В социальной сети цветные сигналы - это специальные каналы связи,

доступные только определенному виду агентов, пространство сигналов - это

общая доска объявлений, на которой каждый агент видит только сообщения

определенного цвета; потенциал вместе с эндогенной скоростью - это харак-

теристика инертности агента, уровня его готовности к переключению.

Предложенный метод структурирования поведения формально пригоден

для любых статических параметров, однако наибольший интерес представ-

ляет структурирование по параметрам d_ij . Дело в том, что эти параметры

(цветные сигналы) могут изменять пространство сигналов в результате внеш-

них воздействий, тогда как остальные параметры (веса, пороги, эндогенные

скорости) являются внутренними характеристиками агентов, изменение ко-

торых гораздо более затруднено. В частности, метод структурирования пове-

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

биологических экспериментов.

СПИСОК ЛИТЕРАТУРЫ

1. Кузнецов О.П., Базенков Н.И., Болдышев Б.А. и др. Асинхронная дискретная

модель химических взаимодействий в простых нейронных системах // Искус-

ственный интеллект и принятие решений. 2018. № 2. С. 3-20.

2. Rao A.S., Georgeff M.P. BDI-agents: From Theory to Practice // Proc. First Int.

Conf. Multiagent Syst. (ICMAS’95) (ed. V. Lesser). AAAI Press / The MIT Press.

1995. P. 312-319.

3. Городецкий В.И., Бухвалов О.Л., Скобелев П.О., Майоров И.В. Современное

состояние и перспективы индустриальных применений многоагентных систем //

Управление большими системами. 2017. Вып. 66. С. 93-157.

4. Muller D.E., Bartky W.S. A theory of asynchronous circuits // Int. Sympos. Switch-

ing Theory in Harvard University. 1959. P. 204-243.

147

5. Варшавский В.И., Кишиневский М.А, Мараховский В.Б. и др. Автоматное

управление асинхронными процессами в ЭВМ и дискретных системах. М.: Нау-

ка, 1986.

6. Brzozowski J.A. Topics in asynchronous circuit theory //Recent Advances Formal

Languages Appl. 2006. V. 25. P. 11-42.

7. Кузнецов О.П. Асинхронные сети с многосортными сигналами // ДАН. 2019.

Т. 487. № 1. С. 10-13.

8. Минский М. Вычисления и автоматы. М.: Мир, 1971.

9. Zhilyakova L.Yu., Gubanov D.A. Double-threshold Model of the Activity Spread-

ing in a Social Network. The Case of Two Types of Opposite Activities // Proc.

11th IEEE Int. Conf. Application of Information and Communication Technologies

AICT2017. 2017. V. 2. P. 267-270.

10. Zhilyakova L.Yu. Modeling the Structure of MIMO-Agents and Their Interactions /

Kuznetsov S., Panov A. (eds.) Artificial Intelligence. RCAI 2019. Communications

in Computer and Information Science, vol. 1093. Cham: Springer, 2019. P. 3-16.

Статья представлена к публикации членом редколлегии В.И. Васильевым.

Поступила в редакцию 02.03.2020

После доработки 11.06.20

Принята к публикации 09.07.2020

148