Статья: Непрямые действия агентов и авторитетные отношения в STIT и PDL

Непрямые действия агентов и авторитетные отношения в STIT и PDL

Г.В. Карпов

Аннотация

Рассматривается понятие авторитетных отношений между агентами с точки зрения логики действий и с точки зрения пропозициональной динамической логики (PDL).

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

Ключевые слова: логика действий, STIT, NEXT-семантика, PDL, авторитетные отношения.

Abstract

The article investigates the notion of an authority relation between agents from two perspectives. Its first part argues that the existence of an authority relation between agents, with respect to some state of affairs, means that an agent who is in authority has an ability to command to act in order to see to it that such state of affairs is true. A command of that kind is modelled in NEXT-semantics. Here an impact of one agent on another is pictured as a composition of accessibility relations between the worlds. A case of an embedded authority relation and a case of presupposed conditions are investigated.

The second part of the article argues that an authority relation between agents, with respect to some state of affairs, exists due to a personal and immediate ability of an agent, who is in authority, to make that state of affairs true. Here an authority relation is interpreted on process graphs as a transitive move to the third world from the first one (where an agent who is in authority acts) via the second world (where an agent who is under authority acts) or as an ability of one agent to use others as a proxy for his or her actions. Such an ability is modelled for three agents by means of a special relation that can distinguish equivalent classes on process graphs. Finally, the article introduces some semantic ideas which are to make further synthesis of the logic of action and PDL fruitful.

Keywords: logic of actions; STIT; NEXT-semantics; PDL; authority relations.

1. Авторитетные отношения в логике действий на базе NEXT-семантики

1.1 Язык, модельная структура, модель

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

ц := p | ¬ц | ц ЃИш | Xц | ?ц | [б]ц | _ц,

где p ? Ф и б ? Г.

Модельная структура F для L_aut есть упорядоченная шестерка элементов (М, H, R_X, R^, Ro, Ra). Множество М = {m₁, m₂, ...} есть бесконечное множество моментов времени. Множество H = { h₁, h₂, ...} есть бесконечное множество историй, такое, что каждая история h представляет собой множество упорядоченных элементов из М. Множество пар {(m/h), (m'/h')}?МхH обозначает множество миров, относительно которых осуществляется означивание формул.

Отношение R_X есть отношение на множестве миров М х H такое, что если (m/h) R_X (m'/h'), то h = h'. Другими словами, для каждого момента времени М отношение R_X определяет последующий, более поздний, момент т', принадлежащий той же истории, что и т. R_X антирефлексивно, транзитивно и антисимметрично.

Отношение R^ есть отношение на М х H такое, что если {m/h)R? {т'/h'), то М = т'. Так отношение R^ для каждой истории h указывает такую историю h', которая проходит через тот же момент времени, что и история h. R^ рефлексивно, транзитивно и симметрично.

Отношение Ro есть отношение на М х H такое, что если {m/h)R₀{m'/h'), то т = т ' и каждая h ' есть «идеальная» или «деонтически совершенная» история, т.е. такая история, которая наиболее предпочтительна для некоторого агента. R₀ серийно (serial), т.е. для каждого мира {т/h) оно находит хотя бы один мир {т/h'), такой, где h' - «идеальная» история.

Отношение R_A есть отношение на М х H такое, что и , где A - метапеременная для {a, в, ...} ? Г. Мы также будем называть R_a отношением эффективности для агентов A.

Модель М образуется присоединением к F функции означивания v, которая ставит в соответствие атомарным пропозициям языка L_aut множество миров из М х H, где эти пропозиции истинны. Условия истинности формул языка L_aut определяются следующими правилами:

. т.е. существует такой мир , что и ;

. т.е. для каждого мира , такого, что , имеет место ;

. т.е. для всех миров , таких, что , имеет место ;

для каждого мира , такого, что .

1.2 Авторитетное отношение как возможность указывать

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

Условия истинности для определены на модели, представленной ниже (рис. 1), где отражена ситуация наличия авторитетного отношения между агентами a и в по ф, когда в некотором начальном моменте a отдает указание в на выполнение ф, а в последующем моменте в, связанный теперь обязательством, принимает решение о том, исполнять это указание или нет.

Рис. 1. Модель авторитетного отношения б к в по ц

Как видим, наличие авторитетного отношения по ц между б и в в мире порождает обязательство в (перед б) в одном из миров, связанных отношением R_a с данным миром. Действительное побуждение агентом а агента в к выполнению ц дает обязательство для в сделать так, что ц во всех мирах, связанных с данным миром отношением R_a. И в том и в другом случае у в сохраняется возможность уклониться от выполнения ц, выбрав мир (m₅/h₂), где допустимо -- ц. Последнее не снимает в , так как идеальной историей в данной модели назначена история h₁ (она отмечена звездочкой).

На основании изложенного нетрудно дополнить список определений истинности формул языка L_aut следующим производным определением: для некоторого мира , такого, что . Или: , для некоторого мира (m'/h'), такого, что (m/h) R_a⁰R_o (m '/h') (где история h' - «идеальная» история).

Композиция R_a⁰R_o отношений определяет миры для а, в которых действует его авторитет по ц в связи с в. Смоделируем теперь несколько случаев использования агентами авторитетных отношений.

Случай 1: вложенные авторитетные отношения. Пусть а находится в авторитетном отношении по ц к в, когда тот сам связан авторитетным отношением по ц к у; можно ли утверждать в этом случае, что в авторитетном отношении по ц к у находится б? И если да, то относительно какого именно момента это верно?

Формула, отражающая случай вложенных авторитетных отношений, имеет вид: . Модель для этой формулы дана на рис. 2.

Предположим, что а не связан авторитетным отношением по ц с г; т.е. во всех мирах, связанных с миром (mj/hj) отношением R₀, имеет место -- . Такая ситуация не является неприемлемой. Однако авторитетное отношение а к y опосредовано авторитетным отношением а к в и в к y, т.е. возможным действием в, для которого в модели должен найтись подходящий момент. Это действие и момент для него, следовательно, нужно учитывать в формуле, которая выражает отношение а к y. Предположение, что авторитетного отношения по ц между а и y нет, с учетом сказанного лучше всего выражает формула -- (неверно, что у а есть возможность сделать так, что в некотором последующем моменте будет так, что у должен сделать так, что ц). Тогда, -- истинна во всех мирах, достижимых из мира (mj/hj) по отношению R_a. Тогда, в каждом мире, связанном отношением R_X c данными мирами (т.е. в мирах (m₄/hi), (m₄/h₂) и (m₅/h₃)), будет истинна -[у]ф. Это противоречит тому, что мы показали ранее: о[у]ф истинна в (m₄/h\). Мы заключаем отсюда, что если (а)оф)о[у]ф, то (а)Хо[у]ф.

Рис. 2. Вложенные авторитетные отношения

Случай 2: подразумеваемое агентами. Пусть а обладает таким авторитетом, который позволяет ему обязать в сделать так, что при условии ф агент в будет делать так, что ф. Пусть далее а способен сделать так, что у в возникает обязательство по выполнению ф. Означает ли это вместе, что а тем самым как бы обязывает в к выполнению ф? В языке L_aut подобная ситуация может быть воспроизведена, например, с помощью формул

(1)

и уже привычной

(2)

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

(3)

Для этого нам потребуется модельная структура Из-за громоздкости формул мы не будем давать модель полностью и ограничимся лишь ее наброском. Мы предполагаем, что читатель может свободно видеть в древовидных структурах струк-туры NEXr-семантики, и наоборот. Если это не так, то в качестве справочной литературы по этому вопросу мы рекомендуем обратиться к [1] и [2]., аналогичная той, что дана на рис. 3: здесь m₁ - момент выбора агентом а формулы (1); m₂ - момент, в котором виден результат решения, принятого а в m₁, и одновременно момент, когда в принимает решение о выполнении или невыполнении назначенного ему действия. Неагентный переход (т.е. переход без ветвления) от m₄ к m₆ необходим, так как этого требует формула ХЩф, которая получает значение в моменте, связанном с текущим моментом отношением R_X.

Означивание формул (1) и (2) на модели, в основе которой лежит модельная структура, представленная на рис. 3, идет обыкновенным образом - так, что в мирах (m₂/h₁), (m₂/h₂), {m₂/h₃) верно, что °([в](9 ^X[в]y)) и оЩф; в мире (m₂/h₁) (где h₁ - идеальная история) верно, что ВД(ф ^ X Щф) и Щф; в мире (m₄/h₁) верно, что ф ^ X [в]^ и Ф (и, следовательно, X [в]y) (в мире (m₆/h₁) верно, что [в]y); наконец, в мире (m₇ihj) верно, что ф.

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

Модель, описываемая здесь, состоит из пяти временных отрезков, сменяющих друг друга один за другим, каждый из которых представлен набором моментов: {m₁}, {m₂, m₃}, {m₄, m₅}, {m₆} и {m₇, m₈}. Формула (3), истинная в текущем моменте, дает XXo[в]^ в последующем (в m₂) Так как, очевидно, временной отрезок {m₂, m₃} разбивается R_a на два класса эквивалентности, один их которых представлен множеством миров {(m2ih\), (m^hi), (m^)}, или, для краткости, мо-ментом m2 и всеми проходящими через него историями., - Xo[в]^ в m₄; o[в]^ ^{и [}ЙФ ^- в m₆ (точнее, в мире (m₆/h₁), так как h₁, напомним, идеальная история); ф - в m₇ (в мире (m₇ihj)). Напротив, предположение о том, что в m₁ истинна --(a)XXo[в]y влечет в конечном итоге противоречие, так как в (m₇/h₁) оказывается в таком случае истинна --ф.

Промежуточные итоги

1. Агентные формулы допускают суперпозицию, через которую выражается влияние, воздействие агентов друг на друга. Тогда один агент вместе с его возможными действиями в будущем предстает в качестве объекта действия другого агента.

2. Одни агенты обладают авторитетом по отношению к другим агентам в связи с некоторым положением дел: первые могут обязать вторых к выполнению некоторых действий; вторые могут исполнить обязательство или уклониться от него.

3. Синтаксически авторитетное отношение между агентами по ф выражается как возможность отдать указание на выполнение ф - сделать так, что выполнение ф становится обязательным; семантически авторитетное отношение агента a предстает как композиция R_a°R_o, где R_a есть отношение эффективности для a, а R_o - отношение, указывающее для каждого возможного мира, достижимого для a, наилучший.

авторитетный логика бисимуляция семантика

2. Авторитетные отношения, данные средствами PDL

2.1 О сходстве и отличии логики действий и PDL

Если мы дадим себе труд оторваться от текущей работы и оглядеться вокруг, то сразу же увидим те множества связей, которыми окружена логика действий, те нити, что ведут из нашей области в области, смежные с ней. Потянуть за одну из них означает обнаружить на том конце, к примеру, пропозициональную динамическую логику (PDL) и её семантическую основу - систему отмеченных переходов (labled-transitions system, LTS).

Чем обусловлена эта связь? Определенным сходством и определенным различием. Первым - так как и логика действий, и PDL семантически трактуют действия как бинарные отношения на множестве возможных миров. И там и тут совершить действие означает перейти из одного мира, с одним набором истинностных значений для пропозиций, в другой мир с, возможно, другим набором истинностных значений. Вторым - так как логика действий в такого рода переходе делает акцент на результате, на том наборе истинностных значений, с которым агенту придется иметь дело после того, как действие будет совершено. Для PDL, напротив, наиболее существенным оказывается именно процесс, посредством которого осуществляется переход между мирами. Логика действий и PDL здесь различны так же, как различны для нас выполнение рутинных обязанностей (поскорей бы с этим расправиться!) и игра на музыкальном инструменте или танец (которые доставляют удовольствие сами по себе).

Одновременное существование сходств и различий между логикой действий и PDL говорит о том, что они нуждаются друг в друге, так как подходят друг другу как две разные части одной и той же головоломки. Отметим и то, что на многие версии логики действий (в частности, на STIT и XSTIT, NEXT-семантику которой мы использовали для построения логики L_aut) можно смотреть как на сокращенные версии PDL. Это сокращение касается множества возможных действий, которое представлено в них не классическим для пропозициональной динамической логики набором, включающим атомарное действие, тест, последовательность, выбор и повтор, а только первым элементом этого набора. Возможность перемещения акцента в исследовании действия с его результата на его процесс предоставит в наше распоряжение семантический инструмент несколько более компактный и удобный в обращении по сравнению с NEXT-структурами.