Сведение вероятностной многоагентной системы к цепи маркова

Для верификации ВМАС необходимо получить её представление в виде цепи Маркова. В работе построен алгоритм TranslateMarkovChain, который по данным, задающим ВМАС A, строит эквивалентную цепь Маркова M_A. Мы приведем содержательное описание этого алгоритма. Входными данными алгоритма TranslateMarkovChain являются: описание ВМАС, включающее параметры, сообщения и программы всех агентов системы и вероятностные распределения для каналов связи, набор возможных начальных состояний S₁, …, S_s с распределением вероятностей на них: p₀₁,…, p_0s. Результатом работы алгоритма TranslateMarkovChain является цепь Маркова, состояния которой соответствуют состояниям входной ВМАС, и для каждого состояния цепи указан список исходящих дуг с вероятностями переходов по ним.

Алгоритм использует следующие внутренние структуры данных:

Q — очередь для хранения расширенных состояний, для которых ещё не находились переходы в другие состояния.

GlobalStates — упорядоченный список всех найденных состояний.

q.probability — вероятность перехода в состояние q из текущего.

OldStates, NewStates — упорядоченные списки, хранящие состояния, получающиеся за один шаг из текущего.

Алгоритм TranslateMarkovChain

1) Заполняем начальное распределение цепи Маркова:

P0 = {p01,…, p0s}.

• 2) Добавляем начальные состояния в очередь Q.
• 3) Пока очередь Q не пуста, выполняем шаги 4−11:
• 4) Выбираем текущее состояние C0 из очереди Q, помещаем его в список текущих состояний NewStates и помечаем его вероятность С. probability := 1.
• 5) Опустошаем почтовые ящики для C: m_i := 0 для всех i=1,…, q.
• 6) Увеличиваем время хранения сообщений в каналах связи CHij={t, msg} на единицу для С: CH_ij:= {t+1,msg} для всех i, j.
• 7) Получение сообщений агентами с вероятностью: для каждого текущего состояния C из NewStates и для каждого агента вычисляются два состояния C1 и С2: C1 — если сообщение будет доставлено, C2 — если сообщение не будет доставлено, и вычисляется вероятность этих состояний: C1. probability := C. probability * pCH[i, j](t), C2. probability := C1. probability * (1-pCH[I, j](t)). После чего C1 и C2 помещаются в отсортированный список NewStates вместо C.
• 8) Выполнение программы с вероятностью: для каждого текущего состояния C из NewStates, для каждого агента и для каждой группы событий G вычисляются состояния C1,…, Ck, где Ci — состояние, полученное из C путём выполнения процедуры Proci из группы событий G, и вычисляется вероятность каждого такого состояния: Сi. probability := C. probability * Probi, где Probi — вероятность входа в процедуру Proci. После этого C1,…, Ck помещаются в NewStates вместо C.
• 9) Если в список NewStates попали два одинаковых состояния, то оставляем одно из них, а вероятность обоих складываем.
• 10) Для каждого состояния C, находящегося в NewStates, добавляем переход в цепь Маркова с вероятностью P (С0, С) = С.probability. Если состояние С ещё не встречалось в списке GlobalStates, то добавляем его в этот список и в очередь Q, а также в список состояний марковской цепи.
• 11) Продолжаем цикл, переходя к шагу 3.

Пусть с — число констант, используемых в описании системы, p максимальное число параметров у агента, m — число различных сообщений и n — число агентов системы. Тогда прямой подсчет показывает, что число всех глобальных состояний системы |S|(c^p2^m)ⁿ.

Теорема 2. Алгоритм TranslateMarkovChain по ВМАС A строит эквивалентную цепь Маркова M_A за время O (|S|²log |S|), где S — множество всех глобальных состояний A.