Исчисление событий

Исчисление событий описывает состояние мира в каждый момент времени как множество всех фактов (называемых флуентами), которые справедливы в этот момент. События инициируют и завершают флуенты.

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

Исходная версия исчисления событий, предложенная Робертом Ковальски и Мареком Серготом в 1986 году^[1], была сформулирована как программа на языке логического программирования и разрабатывалась для представления нарративов и обновлений баз данных^[2]. Каве Эшги показал, как использовать исчисление событий для планирования^[3], применяя абдуктивное логическое программирование для генерации гипотетических действий, направленных на достижение желаемого состояния.

В 1990-х годах Мюррей Шэнахан и Роб Миллер расширили исчисление событий и переформулировали его в терминах предикатной логики с ограничением^[4]. Эти и последующие расширения позволили формализовать недетерминированные действия, параллельные действия, действия с отложенными и постепенными эффектами, а также действия с длительностью, непрерывными изменениями и неинертными флуентами.

Михил ван Ламбалген и Хамм показали, что формулировка исчисления событий как программы с логическими ограничениями может обеспечить алгоритмическую семантику времени и аспекта для естественного языка^[5].

В исчислении событий флуенты подвергаются реификации, то есть представляются с помощью термов. Например, выражение ${\displaystyle {\mathit {holdsAt}}(on(green\_block,table),1)}$ говорит о том, что зелёный блок находится на столе в момент времени 1. Здесь ${\displaystyle {\mathit {holdsAt}}}$ — это предикат, а ${\displaystyle {\mathit {on(green\_block,table)}}}$ — терм. В общем виде атомарная формула ${\displaystyle {\mathit {holdsAt}}(fluent,time)}$ выражает, что флуент справедлив в указанный момент времени.

События также реифицируются и представляются термами. Например, ${\displaystyle {\mathit {happensAt}}(move(green\_block,red\_block),3)}$ выражает, что зелёный блок был перемещён на красный блок в момент времени 3. В общем виде ${\displaystyle {\mathit {happensAt}}(event,time)}$ означает, что событие произошло в заданный момент.

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

${\displaystyle {\mathit {initiates}}(event,fluent,time)}$ — если событие происходит в момент времени, то флуент становится справедливым после этого момента.

${\displaystyle {\mathit {terminates}}(event,fluent,time)}$ — если событие происходит в момент времени, то флуент перестаёт быть справедливым после этого момента.

Исчисление событий было частично разработано как альтернатива исчислению ситуаций^[6][7] — как решение известной проблемы фреймов при представлении и рассуждении об изменениях состояния мира под действием событий.

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

${\displaystyle {\mathit {holdsAt}}(F,T2)\leftarrow }$

${\displaystyle [{\mathit {happensAt}}(E1,T1)\wedge {\mathit {initiates}}(E1,F,T1)\wedge (T1<T2)\wedge }$

${\displaystyle \neg \exists E2,T[{\mathit {happensAt}}(E2,T)\wedge {\mathit {terminates}}(E2,F,T)\wedge (T1\leq T<T2)]}$

Эта аксиома утверждает, что

флуент ${\displaystyle F}$ справедлив в момент ${\displaystyle T2}$, если

событие ${\displaystyle E1}$ произошло в момент ${\displaystyle T1}$ и

${\displaystyle E1}$ инициирует ${\displaystyle F}$ в ${\displaystyle T1}$ и

${\displaystyle T1}$ предшествует ${\displaystyle T2}$ и

не существует такого события ${\displaystyle E2}$ и момента ${\displaystyle T}$, чтобы

${\displaystyle E2}$ произошло в ${\displaystyle T}$ и

${\displaystyle E2}$ завершает ${\displaystyle F}$ в ${\displaystyle T}$ и

${\displaystyle T1\leq T<T2}$.

Решение проблемы фреймов в исчислении событий достигается благодаря интерпретации этой аксиомы в рамках немонотонной логики, например, в предикатной логике с ограничениями (circumscription)^[8] либо как программы на логике Хорна с отрицанием как неудачей^[1]. На самом деле, circumscription является одним из вариантов семантики для отрицания как неудачи^[9], и тесно связано с семантикой полноты программ на логике Хорна^[10] (где если трактуется как если и только если).

Ключевая аксиома исчисления событий определяет предикат ${\displaystyle holdsAt}$ через предикаты ${\displaystyle happensAt}$, ${\displaystyle initiates}$, ${\displaystyle terminates}$, ${\displaystyle <}$ и ${\displaystyle \leq }$. Для применения исчисления событий к конкретной задаче необходимо также определить эти вспомогательные предикаты.

Исчисление событий допускает различные определения временных предикатов ${\displaystyle <}$ и ${\displaystyle \leq }$. На практике время чаще всего представляется дискретно (натуральными числами) или непрерывно (неотрицательные вещественные числа). Однако время может быть и частично упорядочено.

Для применения исчисления событий в конкретной предметной области требуется определить, какие события инициируют или завершают какие флуенты. Например, в предметной области «мир блоков» событие перемещения объекта на новое место ${\displaystyle move(Object,Place)}$ инициирует флуент ${\displaystyle on(Object,Place)}$, то есть объект находится на новом месте, и завершает флуент ${\displaystyle on(Object,Place1)}$ для предыдущего положения:

${\displaystyle {\mathit {initiates}}(move(Object,Place),on(Object,Place),Time).}$

${\displaystyle {\mathit {terminates}}(move(Object,Place),on(Object,Place1),Time)\leftarrow different(Place1,Place).}$

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

${\displaystyle {\mathit {initiates}}(initialise(Fluent),Fluent,Time).}$

Для использования исчисления событий после определения предикатов ${\displaystyle holdsAt}$, ${\displaystyle initiates}$, ${\displaystyle terminates}$, ${\displaystyle <}$, ${\displaystyle \leq }$ необходимо задать предикаты ${\displaystyle happensAt}$, которые описывают конкретный контекст задачи.

Например, в мире блоков можно описать начальное состояние двух блоков (красный блок лежит на зелёном, а зелёный — на столе), а затем последовательность событий: перемещение красного блока на стол в момент 1 и перемещение зелёного блока на красный в момент 3 — итоговое «переворачивание» башни:

${\displaystyle {\mathit {happensAt}}(initialise(on(red\_block,green\_block),0)}$

${\displaystyle {\mathit {happensAt}}(initialise(on(green\_block,table),0)}$

${\displaystyle {\mathit {happensAt}}(move(red\_block,table),1)}$

${\displaystyle {\mathit {happensAt}}(move(green\_block,red\_block),3)}$

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

holdsAt(Fluent, Time2) :- 
    before(Time1, Time2),
    happensAt(Event, Time1),
    initiates(Event, Fluent, Time1),
    not(clipped(Fluent, Time1, Time2)).

clipped(Fluent, Time1, Time2) :-
    terminates(Event, Fluent, Time),
    happensAt(Event, Time), 
    before(Time1, Time),
    before(Time, Time2).

initiates(initialise(Fluent), Fluent, Time).
initiates(move(Object, Place), on(Object, Place), Time).
terminates(move(Object, Place), on(Object, Place1), Time).

happensAt(initialise(on(green_block, table)), 0).
happensAt(initialise(on(red_block, green_block)), 0).
happensAt(move(red_block, table), 1).
happensAt(move(green_block, red_block), 3).

Данная программа на Прологе отличается от предыдущей формализации следующими моментами:

• Ядро аксиомы переписано с использованием дополнительного предиката clipped(Fact, Time1, Time2)., что позволяет устранить экзистенциальные кванторы, чтобы все переменные были неявно универсально квантифицированы (как принято в Прологе).
• Изменён порядок условий, чтобы ответы на запросы формировались в хронологическом порядке.
• Из условия ${\displaystyle T1\leq T}$ исключено равенство, то есть before(Time1, Time). предполагает, что события не могут одновременно инициировать и завершать один и тот же флуент. Это упрощает определение ${\displaystyle terminates}$ за счёт исключения условия ${\displaystyle different(Place1,Place)}$.

Пример подходящего определения:

before(Time1, Time2) :-
   timeline(Eternity), 
   append(Before, [Time2 | After], Eternity), 
   member(Time1, Before).

timeline([0, 1, 2, 3, 4, 5]).

</ref> предиката before(Time1, Time2) позволяет получить ответы на запрос «что справедливо когда» по временной шкале:

?- holdsAt(Fluent, Time).
Fluent = on(green_block,table),     Time = 1.
Fluent = on(red_block,green_block), Time = 1.
Fluent = on(green_block,table),     Time = 2.
Fluent = on(red_block,table),       Time = 2.
Fluent = on(green_block,table),     Time = 3.
Fluent = on(red_block,table),       Time = 3.
Fluent = on(red_block,table),       Time = 4.
Fluent = on(green_block,red_block), Time = 4.
Fluent = on(red_block,table),       Time = 5.
Fluent = on(green_block,red_block), Time = 5.

Программа также позволяет строить отрицательные запросы: «какие флуенты в какие моменты НЕ справедливы». Для корректной работы необходимо предварительно определить все переменные в отрицательных условиях, например:

timePoint(1).
timePoint(2).
timePoint(3).
timePoint(4).
timePoint(5).

fluent(on(red_block, green_block)).
fluent(on(green_block, red_block)).
fluent(on(red_block, table)).
fluent(on(green_block, table)).

?- timePoint(T), fluent(F), not(holdsAt(F, T)).
F = on(green_block,red_block),  T = 1.
F = on(red_block,table),        T = 1.
F = on(red_block,green_block),  T = 2.
F = on(green_block,red_block),  T = 2.
F = on(red_block,green_block),  T = 3.
F = on(green_block,red_block),  T = 3.
F = on(red_block,green_block),  T = 4.
F = on(green_block,table),      T = 4.
F = on(red_block,green_block),  T = 5.
F = on(green_block,table),      T = 5.

Помимо Пролога и его диалектов, существуют и другие инструменты для рассуждения на основе исчисления событий:

• Abductive Event Calculus Planners
• Discrete Event Calculus Reasoner
• Event Calculus Answer Set Programming
• Reactive Event Calculus
• Run-Time Event Calculus (RTEC)
• Epistemic Probabilistic Event Calculus (EPEC)^[11]

Среди известных расширений исчисления событий выделяются варианты, использующие марковские логические сети^[12], вероятностный подход^[13], эпистемический подход^[14] и разные их комбинации^[15].