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

Исчисление событий — это логическая теория представления и рассуждения о событиях и о том, как они меняют состояние некоторого реального или искусственного мира. Он имеет дело как с событиями-действиями, которые выполняются агентами, так и с внешними событиями, которые находятся вне контроля любого агента.

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

Свободно держит одновременно
если беглый инициируется событием, которое произошло раньше
и беглость не прерывается никаким событием, происходящим в это время. ^{[ нужна ссылка ]}

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

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

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

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

Свободное владение языком и события [ править ]

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

{\mathit {holdsAt}}(fluent,time)

выражает то, что

{\mathit {fluent}}

держится на

{\mathit {time.}}

События также овеществлены и представлены терминами. Например, ${\mathit {happensAt}}(move(green\_block,red\_block),3)$ выражает то, что ${\mathit {green\_block}}$ перемещается на ${\mathit {red\_block)}}$ во время $3$ . В общем:

{\mathit {happensAt}}(event,time)

выражает то, что

{\mathit {event}}

происходит в

{\mathit {time.}}

Отношения между событиями и потоками, которые они инициируют и завершают, также представлены атомарными формулами:

{\mathit {initiates}}(event,fluent,time)

выражает то, что если

{\mathit {event}}

происходит в

{\mathit {time}}

тогда

{\mathit {fluent}}

становится истинным после того, как

{\mathit {time}}

.

{\mathit {terminates}}(event,fluent,time)

выражает то, что если

{\mathit {event}}

происходит в

{\mathit {time}}

тогда

{\mathit {fluent}}

перестает быть правдой после того, как

{\mathit {time}}

.

Независимая от предметной области аксиома [ править ]

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

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

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

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

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

Аксиома гласит, что

беглый

F

держится за раз

T2

если

событие

E1

происходит одновременно

T1

и

E1

инициирует

F

в

T1

и

T1

это раньше

T2

и

это не тот случай, когда существует событие

E2

и время

T

такой, что

E2

происходит в

T

и

E2

прекращается

F

в

T

и

T1

находится до или в то же время, что и

T

и

T

это раньше

T2

.

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

Основная аксиома исчисления событий определяет $holdsAt$ предикат с точки зрения $happensAt$ , $initiates$ , $terminates$ , $<$ и $\leq$ предикаты. Чтобы применить исчисление событий к конкретной проблеме, необходимо определить и другие предикаты.

Исчисление событий совместимо с различными определениями темпоральных предикатов. $<$ и $\leq$ . В большинстве приложений время представляется дискретно натуральными числами или непрерывно неотрицательными действительными числами. Однако время также можно заказать частично.

Аксиомы, зависящие от предметной области [ править ]

Чтобы применить исчисление событий в конкретной проблемной области, необходимо определить $initiates$ и $terminates$ предикаты для этого домена. Например, в мире блоков событие $move(Object,Place)$ Перемещение объекта на место инициирует беглую речь $on(Object,Place)$ , что означает, что объект находится на месте, и прекращает плавное $on(Object,Place1)$ , что означает, что объект находится в другом месте:

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

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

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

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

Аксиомы, зависящие от проблемы [ править ]

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

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

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

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

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

{\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). Такое переписывание позволяет исключить кванторы существования в соответствии с соглашением Пролога, согласно которому все переменные имеют универсальную кванторию.
Порядок условий в основной части основных аксиом был изменен, чтобы ответы на запросы генерировались во временном порядке.
Равенство в условии $T1\leq T$ был удален из соответствующего состояния before(Time1, Time). Это основано на упрощающем предположении, что события не одновременно инициируют и завершают один и тот же поток. Как следствие, определение $terminates$ предикат был упрощен за счет исключения условия, согласно которому $different(Place1,Place)$ .

Учитывая подходящее определение ^{[примечание 1]} предиката 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.

Инструменты рассуждения [ править ]

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

Расширения [ править ]

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

См. также [ править ]

Ссылки [ править ]

^ Jump up to: ^а ^б Ковальски, Роберт; Серго, Марек (1 марта 1986 г.). «Логическое исчисление событий» . Компьютеры нового поколения . 4 (1): 67–95. дои : 10.1007/BF03037383 . ISSN 1882-7055 . S2CID 7584513 .
^ Ковальски, Роберт (1 января 1992 г.). «Обновление базы данных в исчислении событий» . Журнал логического программирования . 12 (1): 121–146. дои : 10.1016/0743-1066(92)90041-Z . ISSN 0743-1066 .
^ Эшги, Каве (1988). «Абдуктивное планирование с исчислением событий» . Iclp/SLP : 562–579.
^ Миллер, Роб; Шанахан, Мюррей (2002), Какас, Антонис К.; Садри, Фариба (ред.), «Некоторые альтернативные формулировки исчисления событий» , Вычислительная логика: логическое программирование и не только: эссе в честь Роберта А. Ковальски, часть II , Конспекты лекций по информатике, Берлин, Гейдельберг: Springer, стр. . 452–490, номер домена : 10.1007/3-540-45632-5_17 , ISBN. 978-3-540-45632-2 , получено 5 октября 2020 г.
^ Ламбальген, Хамм (2005). Правильная трактовка событий . Молден, Массачусетс: Паб Blackwell. ISBN 978-0-470-75925-7 . OCLC 212129657 .
^ Дж. Маккарти и П. Хейс (1969). Некоторые философские проблемы с точки зрения искусственного интеллекта . В Б. Мельцере и Д. Мичи, редакторах, Machine Intelligence , 4:463–502. Издательство Эдинбургского университета, 1969.
^ Р. Рейтер (1991). Проблема фрейма в ситуационном исчислении: простое решение (иногда) и результат полноты целевой регрессии. Владимир Лифшиц, редактор журнала « Искусственный интеллект и математическая теория вычислений: статьи в честь Джона Маккарти» , страницы 359–380, Сан-Диего, Калифорния, США. Academic Press Professional, Inc., 1991.
^ Шанахан, М. (1997) Решение проблемы каркаса: математическое исследование здравого закона инерции . МТИ Пресс.
^ Гельфонд, М.; Пржимусинска, Х.; Пшимусински, Т. (1989). «О соотношении ограничения и отрицания как неудачи». Искусственный интеллект . 38 (1): 75–94. дои : 10.1016/0004-3702(89)90068-4 .
^ Кларк, КЛ (1977). «Отрицание как неудача». Логика и базы данных . Бостон, Массачусетс: Springer US. стр. 293–322. дои : 10.1007/978-1-4684-3384-5_11 . ISBN 978-1-4684-3386-9 .
^ Скарлатидис, Анастасиос; Палиурас, Георгиос; Артикис, Александр; Вурос, Джордж А. (17 февраля 2015 г.). «Вероятностное исчисление событий для распознавания событий» . Транзакции ACM в вычислительной логике . 16 (2): 11:1–11:37. arXiv : 1207.3270 . дои : 10.1145/2699916 . ISSN 1529-3785 . S2CID 6389629 .
^ Скарлатидис, Анастасиос; Артикис, Александр; Филиппу, Джейсон; Палиурас, Георгиос (март 2015 г.). «Вероятностно-логическое программирование событий» . Теория и практика логического программирования . 15 (2): 213–245. arXiv : 1204.1851 . дои : 10.1017/S1471068413000690 . ISSN 1471-0684 . S2CID 5701272 .
^ Ма, Цзефей; Миллер, Роб; Моргенштерн, Леора; Паткос, Теодор (28 июля 2014 г.). «Эпистемическое исчисление событий для основанных на ASP рассуждений о знании прошлого, настоящего и будущего» . Серия EPiC по информатике . 26 . EasyChair: 75–87. дои : 10.29007/zswj .
^ Д'Асаро, Фабио Аурелио; Бикакис, Антонис; Диккенс, Люк; Миллер, Роб (01 октября 2020 г.). «Вероятностные рассуждения об эпистемических нарративах действия» . Искусственный интеллект . 287 : 103352. doi : 10.1016/j.artint.2020.103352 . ISSN 0004-3702 . S2CID 221521535 .

Дальнейшее чтение [ править ]

Брандано, С. (2001) « Оценка исчисления событий », Симпозиум IEEE TIME : 7-12.
Р. Ковальски и Ф. Садри (1995) « Варианты исчисления событий », ICLP : 67-81.
Мюллер, Эрик Т. (2015). Рассуждения здравого смысла: подход, основанный на исчислении событий (2-е изд.) . Уолтем, Массачусетс: Морган Кауфманн/Эльзевир. ISBN 978-0128014165 . (Руководство по использованию исчисления событий)
Шанахан, М. (1997) Решение проблемы каркаса: математическое исследование здравого закона инерции . МТИ Пресс.
Шанахан, М. (1999) « Объяснение исчисления событий » Springer Verlag, LNAI (1600): 409–30.

Примечания [ править ]

^ Например:

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

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

[EC-1] Jump up to: ^а ^б Ковальски, Роберт; Серго, Марек (1 марта 1986 г.). «Логическое исчисление событий» . Компьютеры нового поколения . 4 (1): 67–95. дои : 10.1007/BF03037383 . ISSN 1882-7055 . S2CID 7584513 .

[2] Ковальски, Роберт (1 января 1992 г.). «Обновление базы данных в исчислении событий» . Журнал логического программирования . 12 (1): 121–146. дои : 10.1016/0743-1066(92)90041-Z . ISSN 0743-1066 .

[3] Эшги, Каве (1988). «Абдуктивное планирование с исчислением событий» . Iclp/SLP : 562–579.

[4] Миллер, Роб; Шанахан, Мюррей (2002), Какас, Антонис К.; Садри, Фариба (ред.), «Некоторые альтернативные формулировки исчисления событий» , Вычислительная логика: логическое программирование и не только: эссе в честь Роберта А. Ковальски, часть II , Конспекты лекций по информатике, Берлин, Гейдельберг: Springer, стр. . 452–490, номер домена : 10.1007/3-540-45632-5_17 , ISBN. 978-3-540-45632-2 , получено 5 октября 2020 г.

[5] Ламбальген, Хамм (2005). Правильная трактовка событий . Молден, Массачусетс: Паб Blackwell. ISBN 978-0-470-75925-7 . OCLC 212129657 .

[6] Дж. Маккарти и П. Хейс (1969). Некоторые философские проблемы с точки зрения искусственного интеллекта . В Б. Мельцере и Д. Мичи, редакторах, Machine Intelligence , 4:463–502. Издательство Эдинбургского университета, 1969.

[7] Р. Рейтер (1991). Проблема фрейма в ситуационном исчислении: простое решение (иногда) и результат полноты целевой регрессии. Владимир Лифшиц, редактор журнала « Искусственный интеллект и математическая теория вычислений: статьи в честь Джона Маккарти» , страницы 359–380, Сан-Диего, Калифорния, США. Academic Press Professional, Inc., 1991.

[8] Шанахан, М. (1997) Решение проблемы каркаса: математическое исследование здравого закона инерции . МТИ Пресс.

[9] Гельфонд, М.; Пржимусинска, Х.; Пшимусински, Т. (1989). «О соотношении ограничения и отрицания как неудачи». Искусственный интеллект . 38 (1): 75–94. дои : 10.1016/0004-3702(89)90068-4 .

[10] Кларк, КЛ (1977). «Отрицание как неудача». Логика и базы данных . Бостон, Массачусетс: Springer US. стр. 293–322. дои : 10.1007/978-1-4684-3384-5_11 . ISBN 978-1-4684-3386-9 .

[12] Скарлатидис, Анастасиос; Палиурас, Георгиос; Артикис, Александр; Вурос, Джордж А. (17 февраля 2015 г.). «Вероятностное исчисление событий для распознавания событий» . Транзакции ACM в вычислительной логике . 16 (2): 11:1–11:37. arXiv : 1207.3270 . дои : 10.1145/2699916 . ISSN 1529-3785 . S2CID 6389629 .

[13] Скарлатидис, Анастасиос; Артикис, Александр; Филиппу, Джейсон; Палиурас, Георгиос (март 2015 г.). «Вероятностно-логическое программирование событий» . Теория и практика логического программирования . 15 (2): 213–245. arXiv : 1204.1851 . дои : 10.1017/S1471068413000690 . ISSN 1471-0684 . S2CID 5701272 .

[14] Ма, Цзефей; Миллер, Роб; Моргенштерн, Леора; Паткос, Теодор (28 июля 2014 г.). «Эпистемическое исчисление событий для основанных на ASP рассуждений о знании прошлого, настоящего и будущего» . Серия EPiC по информатике . 26 . EasyChair: 75–87. дои : 10.29007/zswj .

[15] Д'Асаро, Фабио Аурелио; Бикакис, Антонис; Диккенс, Люк; Миллер, Роб (01 октября 2020 г.). «Вероятностные рассуждения об эпистемических нарративах действия» . Искусственный интеллект . 287 : 103352. doi : 10.1016/j.artint.2020.103352 . ISSN 0004-3702 . S2CID 221521535 .

[11] Например:
before(Time1, Time2) :- timeline(Eternity), append(Before, [Time2 | After], Eternity), member(Time1, Before). timeline([0, 1, 2, 3, 4, 5]).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[примечание 1]

[11]

[12]

[13]

[14]