О СВОЙСТВАХ МУЛЬТИАГЕНТНЫХ СИСТЕМ С ВЕРОЯТНОСТНЫМИ КАНАЛАМИ СВЯЗИ[1]

Валиев М.К., к.ф.-м.н.

Институт прикладной математики им. М.В.Келдыша РАН

(495)250-79-38, valiev@keldysh.ru

Дехтярь М.И., к.ф.-м.н., доцент

Тверской государственный университет

(482-2)365410, Michael.Dekhtyar@tversu.ru

Диковский А.Я., д.ф.-м.н.

Институт прикладной математики им. М.В.Келдыша РАН

(495)250-79-38, dikovsky@keldysh.ru

1. Введение

Системы взаимодействующих интеллектуальных агентов представляют одно из самых активно развивающихся направлений в области искусственного интеллекта и прикладного программирования (см., например, [5,7]). Агенты используются в качестве автономных компонент при построении систем искусственного интеллекта, работы в Интернете и т.д. В таких системах агенты могут работать и взаимодействовать по весьма сложным правилам, что делает поведение системы во времени очень сложным. Это приводит к необходимости верификации динамических свойств таких систем.

Определение понятия агента, используемое в настоящей работе, в основном (с некоторыми упрощениями) следует архитектуре IMPACT из работы [5]. В работах [3, 4, 6] мы изучали проблему верификации динамических свойств мультиагентных систем (МАС) с синхронной и асинхронной системами передачи сообщений. В данной работе нас интересует случай, когда каналы связи между агентами являются вероятностными.

2. МАС с вероятностными каналами связи

Мультиагентная система (МАС) A = {A₁,...,A_n} состоит из конечного множества {A₁,...,A_n} взаимодействующих интеллектуальных агентов A_i. У интеллектуального агента A имеется внутренняя база данных (БД) I_A, содержащая конечное множество базисных атомов (т.е. выражений вида p(c₁,…, c_k), где p-предикатный символ, c₁,…, c_k - константы, причем множество используемых данной системой констант ограничено), и почтовый ящик MsgBox_A. Текущие содержимые внутренней БД и почтового ящика агента A составляют его текущее локальное состояние IM_A=<I_A,MsgBox_A>.

Агенты из A общаются между собой посредством передачи сообщений вида msg(Sender, Receiver, Msg), где Sender и Receiver – имена агентов (источника и адресата), a Msg - (передаваемый) базисный атом.

Для каждой пары агентов A, B из A имеется канал связи CH_AB, в который попадают сообщения, посылаемые агентом A агенту B. Затем из этого канала они попадают в почтовый ящик MsgBox_B. Время пребывания каждого сообщения «в пути» мы будем рассматривать как случайную величину, задаваемую конечным дискретным распределением вероятностей. Через p_AB(t) обозначим вероятность того, что B получит сообщение, посланное ему агентом A, ровно через t ≥ 1 шагов (тактов) после его отсылки.

Для разных сообщений соответствующие случайные величины будем считать независимыми. Мы будем предполагать, что ∑_t=1^∞ p_AB(t) £ 1 . Тогда разность 1 - ∑_t=1^∞ p_AB(t) определяет вероятность того, что сообщение никогда не достигнет адресата, т.е. будет утеряно в канале. Например, p_AB(1) = 1 означает, что каждое сообщение, посланное агентом A агенту B, будет получено адресатом на следующем шаге после его посылки. Именно такой вариант рассматривался в работах [3, 4, 6]. Если p_AB(1)=0.5, p_AB(2)=0.4 и p_AB(t)=0 при t >2 , то половина всех сообщений A агенту B будет получена на следующем шаге после их отсылки, еще 4/10 будут находиться в пути 2 такта, и в среднем десятая часть таких сообщений будет утеряна.

Текущее состояние канала CH_AB будет включать все сообщения, посланные агентом A агенту B, которые еще не дошли до B, с указанием времени их нахождения в канале. Мы будем обозначать текущее состояние канала так же как и сам канал, т.е. CH_AB ={(Msg, t) | сообщение Msg от агента A агенту b находится в канале t тактов}. Мы будем также использовать сокращения CH_ij и p_ij для CH_AiAj и p_AiAj, соответственно.

С каждым агентом A связана его база ACT_A параметризованных действий вида <a(X₁,…,X_m), ADD_a(X₁,…,X_m), DEL_a(X₁,…,X_m), SEND_a(X₁,…,X_m)>, где a(X₁,…,X_m) определяет параметризованное имя действия. ADD_a(X₁,…,X_m) и DEL_a(X₁,…,X_m) – списки атомов вида p(t₁,…,t_k), где p – k-местный предикат из сигнатуры внутренней БД, t₁,…,t_k – либо константы, либо параметры X₁,…,X_m. Эти множества определяют изменения внутренней БД (добавления и удаления фактов) при выполнении соответствующего действия. SEND_a(X₁,…,X_m) определяет аналогичным образом список сообщений вида msg(A,B, p(t₁,…,t_k)), отправляемых другим агентам. Пусть c₁,…,c_m – константы. Обозначим через ADD_a(c₁,…,c_m) множество фактов, получаемых подстановкой c₁,…,c_m вместо X₁,…,X_m в атомы из ADD_a(X₁,…,X_m). Аналогично определяются DEL_a(c₁,…,c_m) и SEND_a(c₁,…,c_m). Базисные атомы вида a(c₁,…, c_l) назовем базисными именами действий.

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

повысить-зарплату(Фамилия, Должность, СтарСум, НовСум):

ADD={(зарплата(Фамилия, Должность, НовСум)},

DEL ={(зарплата(Фамилия, Должность, СтарСум)},

SEND = {(отдел_кадров, зарплата _повышена(Фамилия, НовСум))}

Конкретный выбор действий для выполнения в зависимости от текущего локального состояния агента определяется парой < LP_A , Sel_A>. Здесь LP_A - логическая программа агента, определяющая совместно с фактами из текущего локального состояния агента некоторое множество Perm (= Perm_At) допустимых для выполнения в данный момент t базисных имен действий , а Sel_A выделяет из Perm подмножество Obl (=Obl_At) обязательных для выполнения на данном шаге действий.

После того, как множество Obl определено, выполнение действий из него определяется следующим образом. Все действия из Obl выполняются параллельно и однозначно определяют изменения внутреннего состояния I_A и каналов СH_AB . Пусть ADD_Obl равно объединению всех множеств ADD_a(c₁,…,c_m) таких, что базисное имя a(c₁,…, c_m) из Obl унифицируется с параметризованным именем a(X₁,…, X_m). Аналогично определяются множества DEL_Obl и SEND_Obl. Тогда следующее состояние NEW_DB(I_A, Obl ) внутренней БД агента A получается из текущего состояния удалением элементов из DEL_Obl и добавлением элементов из ADD_Obl.

Одновременно с изменением внутреннего состояния выполнение действий из Obl приводит к изменению состояний каналов, пересылающих сообщения агента A другим агентам. Для каждого агента B ¹ A в канал CH_AB добавляются пары вида (Msg,, 0) для всех экземпляров сообщений Msg, для которых (B, Msg) Î SEND_Obl . Обозначим множество всех таких добавленных в канал CH_AB пар как NEW_CH(Obl,B).

Пусть, например, агент бухгалтер должен выполнить множество действий Obl={ повысить-зарплату(петров, инженер, 3500, 5000),

повысить-зарплату(соколова, программист, 4500, 6000)}. Выполнение Obl приведет к удалению из базы данных фактов

зарплата(петров, инженер, 3500),

зарплата(соколова, программист, 4500)}

и вставке фактов

зарплата(петров, инженер, 5000),

зарплата(соколова, программист, 6000)}.

Кроме того, в канал CH_{бухгалтер отдел_кадров} будут помещены две пары:

NEW_CH(Obl, отдел_кадров)={ (зарплата_повышена(петров,5000),0),

(зарплата_повышена(соколова,6000),0)}.

В качестве программы LP_A мы рассматриваем логическую программу с предложениями вида H :- L₁,...,L_n со следующими свойствами: H –атом действия, т.е. имеет вид a(t₁,…,t_m), где a – имя действия, t₁,…,t_m – либо константы, либо переменные; литералы L_i – либо литералы действия, либо (экстенсиональные) литералы с предикатами из сигнатуры внутренней БД, либо литералы сообщений вида msg(Sender, A, Msg) или not msg(Sender, A, Msg), либо некоторые вычислимые в полиномиальное время встроенные предикаты.

Мы предполагаем, что предложения в программах агентов являются безопасными в том смысле, что все переменные из головы предложения H входят позитивно в тело предложения L₁,...,L_n. Кроме того, мы считаем, что программа LP_A является стратифицированной [1]. Тогда в каждом локальном состоянии state= <I_A, MsgBox_A> программа

LP_A,state = LP_A È I_A È MsgBox_A,

определяющая множество действий, которые в принципе может выполнить агент в текущем состоянии, является стратифицированной. Хорошо известно (см. [1]), что стратифицированные логические программы имеют единственную минимальную модель. Обозначим такую модель программы LP_A,state через M_A,state. Стандартная процедура вычисления неподвижной точки позволяет вычислить эту модель по базисной развертке gr(LP_A,state ) программы LP_A,state. Отметим, что размер gr(LP_A,state) может быть экспонентой от размера LP_A,state. Напомним также, что предположение о замкнутости области, которое мы используем, предполагает вычислимость за полиномиальное время всех встроенных предикатов. Поэтому сохраняется вычислимость неподвижной точки за полиномиальное время.

Упомянутое выше множество Perm определяется тогда как множество базисных имен действий, содержащихся в минимальной модели M_A,state . Обозначим через Sem функцию, которая по LP_A,state строит это множество Perm.

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

3. Поведение МАС

Глобальное состояние S системы A включает в себя локальные состояния ее агентов и состояния всех ее (n²-n) каналов:

S = <I₁,…,I_n; CH_1,2, CH_2,1,… , CH_n-1,n, CH_n,n-1>.

Обозначим через S_A множество всех глобальных состояний МАС A.

Тогда одношаговая семантика МАС A задает отношение S Þ_A S’

перехода (за один шаг) на множестве S_A, а вероятности p_i,j(t) индуцируют вероятности таких переходов p(S, S’).

Переход S Þ_A S’ начинается с работы каналов и формирования нового содержимого почтовых ящиков. Сначала каждый канал увеличивает на 1 счетчик времени у всех находящихся в нем сообщений. Затем для каждой пары (Msg, t) Î CH_i,j в почтовый ящик MsgBox_j агента A_j с вероятностью p_i,j(t) помещается факт msg(A_i, A_j ,Msg). После этого каждый агент A_i Î A формирует множество всех допустимых на данном шаге действий Perm_i = Sem(LP_A,state). А затем, используя свой оператор выбора Sel_Ai , определяет множество выполняемых действий Obl_i= Sel_Ai(Perm_i). Почтовые ящики всех агентов МАС A после этого опустошаются, т.е. полученные сообщения “забываются”. Разумеется, это не ограничивает общности, поскольку агент может все нужные ему данные перенести из почтового ящика в свою базу данных. Затем состояние внутренней БД I_i заменяется на NEW_DB(I_i, Obl_i ), а посланные им сообщения помещаются в соответствующие каналы.

Таким образом, переход S Þ_A S’ вычисляется следующим алгоритмом:

A -шаг( Вход: S ; Выход: S’ )

(1) FOR EACH A_i, A_j Î A (i ¹ j) DO

(2) FOR EACH (Msg, t) Î CH_i,j DO

(3) CH_i,j := (CH_i,j \ {(Msg, t)} ) È {(Msg, t+1)} ;

(4) FOR EACH A_i, A_j Î A (i ¹ j) DO

(5 ) FOR EACH (Msg, t) Î CH_i,j DO с вероятностью p_i,j(t)

(6 ) { CH_i,j := (CH_i,j \ {(Msg, t)} ) ;

(7) MsbBox_j := MsbBox_j È{msg(A_i, A_j , Msg)}

(8) };

(9) FOR EACH A_i Î A DO

(10) { Perm_i := Sem(LP_A,state );

(11) Obl_i= Sel_Ai (Perm_i);

(12) MsgBox_i := Æ;

(13) I_i := NEW_DB_i(Obl_i, I_i);

(14) FOR EACH (i ¹ j) DO

(15) CH_i,j := (CH_i,j È NEW_CH(Obl_i , A_j)

(16) }

(17) RETURN S’.

В соответствии с вышеприведенным определением семантики с МАС A можно связать Марковскую цепь с множеством состояний S_A и вероятностями переходов p(S, S’) между ними. Поведение A в начальном глобальном состоянии S⁰ описывается деревом T_A(S⁰) возможных траекторий этой цепи, начинающихся с S⁰. Узлы этого дерева помечены глобальными состояниями системы, причем каждый узел, находящийся на (t+1)-ом уровне и помеченный состоянием S’, связан с узлом на t-ом уровне, из пометки которого S возможен переход S Þ_A S’ c вероятностью p(S, S’) >0.

4. Верификация динамических свойств

Динамические свойства (поведения) МАС описываются формулами пропозициональной логики линейного времени PLTL, интерпретируемыми на траекториях [ 2 ].

Проблема верификации динамических свойств мультиагентных систем (которую мы называем MA-BEHAVIOR) формулируется следующим образом. Пусть даны МАС A, ее начальное глобальное состояние S⁰ и формула F, выражающая некоторое свойство траекторий, нужно вычислить меру (вероятность) P_A(S⁰ , F) множества траекторий дерева T_A(S⁰), на которых выполнена F.

Отметим, что единственным источником неопределенности в программе A-шаг являются операторы в строках 5-8, в результате выполнения которых сообщения попадают в почтовые ящики агентов с учетом вероятностей времен их пересылки. Поэтому результат S’ этой программы однозначно определяется ее начальным состоянием S и содержимым почтовых ящиков агентов MsbBox_j, полученным ими в вероятностном цикле в строках 5-8. Обозначим для любой пары A_i, A_j Î A (i ¹ j) через Msgs_i,j множество сообщений, полученных агентом A_j от агента A_i на текущем шаге. Тогда для каждого A_j имеем MsgBox_j = È{Msgs_i,j| 1 £ i £ n, j ¹ i }.

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

S = <I₁,…,I_n; CH_1,2, CH_2,1,… , CH_n-1,n, CH_n,n-1> перешло в состояние

S’ = <I’₁,…,I’_n; CH’_1,2, CH’_2,1,… , CH’_n-1,n, CH’_n,n-1>.

Тогда для всех i=1, … , n новое состояние БД агента A_j получается в строке 13 как I’_i= NEW_DB_i(Obl_i, I_i) и для всех i,j =1, … , n, (i ¹ j) новое состояние канала сообщений от A_i к A_j определяется равенством CH_i,j = (CH_i,j \ Msgs_i,j ) È NEW_CH(Obl_i , A_j) .

Это позволяет предложить эффективную процедуру вычисления вероятности p(S, S’) перехода S Þ_A S’

Алгоритм Prob(S, S’)

(1) FOR EACH A_i, A_j Î A (i ¹ j) DO

(2) { M[i,j] := {(m, t) | ((m, t) Î CH_i,j) & ((m,t+1) Ï CH’_i,j )};

(3) p_i,j := Õ { p_i,j(t) | ((m, t) Î M[i,j]}

(4) };

(5) FOR EACH A_j Î A DO

(6) { MsgBox_j := Æ;

(7) FOR EACH A_i Î A (i ¹ j) DO

(8) MsgBox_j := MsgBox_j È {msg( A_i, A_{j ,}m) | $t ( (m,t) ÎM[i,j] )}

(9) };

(10) FOR EACH A_j Î A DO

(10) { Perm_i := Sem(LP_A,state );

(11) Obl_i := Sel_Ai (Perm_i);

(12) IF I’_i ¹ NEW_DB_i(Obl_i, I_i)

(13) THEN RETURN 0;

(14) FOR EACH (j ¹ i ) DO

(15) IF {(m,0) | (m,0) Î CH_i,j) } ¹ NEW_CH(Obl_i , A_j)

(16) THEN RETURN 0

(17) };

(18) RETURN p(S, S’) = Õ { p_i,j | 1 £ i, j £ n, j ¹ i }

Теорема 1. Алгоритм Prob(S, S’) вычисляет вероятность p(S, S’) перехода S Þ_A S’ за время, полиномиальное от суммы размеров МАС A и размеров исходного и результирующего состояний S и S’: |A| + |S| +|S’| (в размер |A| МАС A входят размеры всех сигнатур, множества констант, и описаний агентов, включающих их базы действий и базисные развертки программ агентов).

Эта теорема вместе с результатами о верификации вероятностных программ из работы [2] позволяют получить алгоритм решения проблемы MA-BEHAVIOR для МАС с вероятностными каналами связи.

Теорема 2. Существует алгоритм, который по базисной МАС A, начальному состоянию S⁰ и формуле F из PLTL вычисляет вероятность P_A(S⁰ , F) за время, экспоненциальное от размера входа.

Список литературы

1.Apt K. R., Logic LPogramming. In: J. van Leeuwen (Ed.), Handbook of Theoretical Computer Science. Volume B. Formal Models and Semantics, Chapter 10, Elsevier Science Publishers B.V. 1990, 493-574.

2. Courcoubetis C., Yannakakis M., The complexity of probabilistic verification. J. ACM, v. 42, 4, 1995, 857-907.

3. Dekhtyar M., Dikovsky A., and Valiev M., On Feasible Cases of Checking Multi-Agent Systems Behavior. Theoretical Computer Science, Elsievier Science, 2003, vol. 303, no. 1, 63-81.

4. Dekhtyar M.I., Dikovsky A.Ja., Valiev M.K., On complexity of verification of interacting agents’ behavior. Annals of Pure and Applied Logic, 141, 2006, 336 – 362.

5. Subrahmanian V. S., Bonatti P., Dix J., et al., Heterogeneous Agent Systems, MIT LPess, 2000.

6. Валиев М.К., Дехтярь М.И., Диковский А.Я, Китаев Е. Л., Скороходов А.П. Верификация динамических свойств многоагентных систем. Труды III-го Межд. научно-практического семинара "Интегрированные модели и мягкие вычисления в искусственном интеллекте", М.; Физматлит, Коломна, 2005.

7. Тарасов В.Б. От многоагентных систем к интеллектуальным организациям. Эдиториал УРСС, М., 2002.

---

[1] Эта работа выполнена при поддержке РФФИ (гранты 07-01-00637-а и 05-01-01006-а).