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

Исчисление событие является логическим языком для представления и рассуждения о событиях и их влияние первого представленных Роберт Ковальский и Марек Sergot в 1986 году был продлен Мюррей Shanahan и Роб Миллер в 1990 - е годы. Подобно другим языкам для рассуждений об изменениях, исчисление событий представляет влияние действий на беглых . Однако события также могут быть внешними по отношению к системе. В исчислении событий можно указать значение текучести в некоторые заданные моменты времени, события, которые происходят в заданные моменты времени, и их эффекты.

Fluents и события

В исчислении событий флюэнт являются овеществлёнными . Это означает, что они формализованы не с помощью предикатов, а с помощью функций . Отдельный предикат $HoldsAt$ используется для определения того, какие флюэнты удерживаются в данный момент времени. Например, это означает, что коробка находится на столе в момент времени $t$ ; в этой формуле $HoldsAt$ - это предикат, а $on$ - функция. ${\ displaystyle {\ mathit {HoldsAt}} (на (поле, таблица), t)}$

События также представлены в виде терминов. Эффекты событий задаются с помощью предикатов $Initiates$ и $Terminates$ . В частности, это означает, что если событие, представленное термином $e$ , выполняется в момент времени $t$ , то беглый $f$ будет истинным после $t$ . $Завершает$ предикат имеет сходное значение, с той лишь разницей, что $е$ будет ложным после $т$ . ${\ Displaystyle {\ mathit {Посвященные}} (е, е, т)}$

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

Как и другие языки для представления действий, исчисление событий формализует правильную эволюцию беглого языка с помощью формул, сообщающих значение каждого беглого языка после того, как произвольное действие было выполнено. Исчисление событие решает проблему кадров таким образом , что это похоже на правопреемником государственных аксиом в ситуации исчисления : свободно владеет истинно в момент времени $т$ тогда и только тогда , когда это было сделано верно в прошлом , и не было сделано ЛОЖЬ в тем временем.

{\ displaystyle {\ mathit {HoldsAt}} (f, t) \ leftarrow [{\ mathit {Happens}} (e, t_ {1}) \ wedge {\ mathit {Initiates}} (e, f, t_ {1 }) \ wedge (t_ {1} <t) \ wedge \ neg {\ mathit {Clipped}} (t_ {1}, f, t)]}

Эта формула означает, что значение fluent, представленное термином $f$ , истинно в момент $t,$ если:

событие $е$ имеет место: ; ${\ displaystyle {\ mathit {Happens}} (е, t_ {1})}$
это имело место в прошлом :; ${\ displaystyle {\ mathit {t}} _ {1} <t}$
это событие имеет свободно $п$ как эффект: ; ${\ Displaystyle {\ mathit {Посвященные}} (е, f, t_ {1})}$
тем временем беглый язык не был сделан ложным: ${\ displaystyle {\ mathit {Clipped}} (t_ {1}, f, t)}$

Подобная формула используется для формализации противоположного случая, когда беглое слово неверно в данный момент. Другие формулы также необходимы для правильной формализации беглых языков до того, как они станут следствием какого-либо события. Эти формулы аналогичны приведенным выше, но заменены на . ${\ displaystyle {\ mathit {Happens}} (е, t_ {1}) \ клин {\ mathit {Initiates}} (e, f, t_ {1})}$ ${\ Displaystyle {\ mathit {HoldsAt}} (е, т_ {1})}$

$Обрезанные$ сказуемое, заявив , что свободно было сделана ЛОЖЬ в течение интервала, может быть аксиоматизировано, или просто принимать как условное обозначение, следующим образом :

{\ Displaystyle {\ mathit {Clipped}} (т_ {1}, е, т_ {2}) \ эквив \ существует е, т [{\ mathit {Happens}} (е, т) \ клин (т_ {1} \ leq t <t_ {2}) \ wedge {\ mathit {Завершает}} (e, f, t)]}

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

Приведенные выше аксиомы связывают значение предикатов $HoldsAt$ , $Initiates$ и $Terminates$ , но не определяют, какие флюэнты известны как истинные, а какие события фактически делают флюенты истинными или ложными. Это делается с помощью набора аксиом, зависящих от предметной области. Известные значения fluents указаны в виде простых литералов . Эффекты событий выражаются формулами, связывающими эффекты событий с их предпосылками. Например, если событие $open$ делает fluent $isopen$ истинным, но только если $haskey$ в настоящее время истинно, соответствующая формула в исчислении событий будет: ${\ Displaystyle {\ mathit {HoldsAt}} (е, т)}$

{\ displaystyle {\ mathit {Initiates}} (e, f, t) \ Equiv [e = open \ wedge f = isopen \ wedge {\ mathit {HoldsAt}} (haskey, t)] \ vee \ cdots}

Правое выражение этой эквивалентности состоит из дизъюнкции: для каждого события и текучести, которая может быть сделана истинной с помощью этого события, есть дизъюнкция, говорящая, что $e$ на самом деле является этим событием, что $f$ на самом деле так плавно и что предварительное условие события выполнено.

Формула выше Задает значение истины о для каждого возможного случая и свободно. В результате все эффекты всех событий должны быть объединены в единую формулу. Это проблема, потому что добавление нового события требует изменения существующей формулы, а не добавления новых. Эта проблема может быть решена путем применения ограничения к набору формул, каждая из которых определяет один эффект одного события: ${\ Displaystyle {\ mathit {Посвященные}} (е, е, т)}$

{\ displaystyle {\ mathit {Initiates}} (open, isopen, t) \ leftarrow {\ mathit {HoldsAt}} (haskey, t)}

{\ displaystyle {\ mathit {Initiates}} (break, isopen, t) \ leftarrow {\ mathit {HoldsAt}} (hashammer, t)}

{\ displaystyle {\ mathit {Initiates}} (перерыв, сломанный, t) \ leftarrow {\ mathit {HoldsAt}} (hashammer, t)}

Эти формулы проще, чем формула выше, потому что каждый эффект каждого события может быть указан отдельно. Единая формула, показывающая, какие события $e$ и fluents $f$ делают истинными, была заменена набором более мелких формул, каждая из которых говорит о влиянии события на fluent. ${\ Displaystyle {\ mathit {Посвященные}} (е, е, т)}$

Однако эти формулы не эквивалентны приведенной выше формуле. На самом деле, они только определяют достаточные условия для того, чтобы быть истинными, которые должны дополняться тем фактом, что $посвященные$ ложны во всех других случаях. Этот факт можно формализовать, просто описав предикат $Initiates$ в приведенной выше формуле. Важно отметить, что это ограничение выполняется только на формулах, определяющих $посвященных,$ а не на аксиомах, не зависящих от предметной области. Предикат $Terminates$ может быть указан так же, как и $Initiates$ . ${\ Displaystyle {\ mathit {Посвященные}} (е, е, т)}$

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

{\ Displaystyle {\ mathit {Happens}} (е, т) \ эквив (е = открытый \ клин т = 0) \ ви (е = выход \ клин т = 1) \ ви \ cdots}

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

{\ displaystyle {\ mathit {Happens}} (открытый, 0)}

{\ displaystyle {\ mathit {Happens}} (выход, 1)}

Ограничивая предикат $Happens$ , этот предикат будет ложным во всех точках, в которых он явно не указан как истинный. Это ограничение должно быть выполнено отдельно от других формул. Другими словами, если $F$ - набор формул такого типа , $G$ - набор формул , а $H$ - аксиомы, не зависящие от области, правильная формулировка области: ${\ Displaystyle {\ mathit {Посвященные}} (е, е, т) \ leftarrow \ cdots}$ ${\ Displaystyle {\ mathit {Happens}} (е, т)}$

{\ displaystyle {\ mathit {Circ}} (F; {\ mathit {Initiates}}, {\ mathit {Terminates}}) \ wedge Circ (G; Happens) \ wedge H}

Исчисление событий как логическая программа

Исчисление событий изначально было сформулировано как набор предложений Хорна, дополненных отрицанием как отказ, и его можно было запускать как программу на Прологе . Фактически, ограничение - это одна из нескольких семантик, которые можно придать отрицанию как отказу, и она тесно связана с семантикой завершения (в которой «если» интерпретируется как «если и только если» - см. Логическое программирование ).

Расширения и приложения

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

Каве Эшги показал, как исчисление событий можно использовать для планирования, используя абдукцию для генерации гипотетических событий в абдуктивно-логическом программировании . Ван Ламбальген и Хамм показали, как исчисление событий может также использоваться для придания алгоритмической семантики времени и аспекта на естественном языке с использованием программирования логики ограничений .

Другие известные расширения исчисления событий включают вероятностные , эпистемологические варианты и их комбинации на основе логических сетей Маркова .

Инструменты рассуждения

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

Смотрите также

использованная литература

^ Ковальский, Роберт; Серго, Марек (1986-03-01). «Логическое исчисление событий» . Вычислительная техника нового поколения . 4 (1): 67–95. DOI : 10.1007 / BF03037383 . ISSN 1882-7055 . S2CID 7584513 .
^ Миллер, Роб; Шанахан, Мюррей (2002), Какас, Антонис С.; Садри, Фариба (ред.), «Некоторые альтернативные формулировки исчисления событий» , « Вычислительная логика: логическое программирование и не только»: эссе в честь Роберта А. Ковальски, часть II , конспект лекций по информатике, Берлин, Heidelberg: Springer, стр. . 452-490, DOI : 10.1007 / 3-540-45632-5_17 , ISBN 978-3-540-45632-2, получено 2020-10-05
^ Ковальский, Роберт (1992-01-01). «Обновление базы данных в исчислении событий» . Журнал логического программирования . 12 (1): 121–146. DOI : 10.1016 / 0743-1066 (92) 90041-Z . ISSN 0743-1066 .
^ Eshghi, Кава (1988). «Абдуктивное планирование с исчислением событий» . Iclp / SLP : 562–579.
^ Lambalgen, Hamm (2005). Правильная трактовка событий . Молден, Массачусетс: Blackwell Pub. ISBN 978-0-470-75925-7. OCLC 212129657 .
^ Skarlatidis, Анастасий; Палиурас, Георгиос; Артикис, Александр; Вурос, Джордж А. (17 февраля 2015 г.). «Вероятностное исчисление событий для распознавания событий» . ACM-транзакции по вычислительной логике . 16 (2): 11: 1–11: 37. arXiv : 1207,3270 . DOI : 10.1145 / 2699916 . ISSN 1529-3785 . S2CID 6389629 .
^ Skarlatidis, Анастасий; Артикис, Александр; Филиппу, Джейсон; Палиоурас, Георгиос (март 2015 г.). «Вероятностно-логическое программирование событийного исчисления» . Теория и практика логического программирования . 15 (2): 213–245. DOI : 10.1017 / S1471068413000690 . ISSN 1471-0684 . S2CID 5701272 .
^ Ма, Jiefei; Миллер, Роб; Моргенштерн, Леора; Паткос, Теодор (28.07.2014). «Расчет эпистемических событий для рассуждений на основе ASP о знании прошлого, настоящего и будущего» . Серия EPiC в вычислительной технике . Кресло. 26 : 75–87. DOI : 10,29007 / zswj .
^ D'Асаро, Фабио Аурелио; Бикакис, Антонис; Диккенс, Люк; Миллер, Роб (2020-10-01). «Вероятностные рассуждения об эпистемических нарративах действия» . Искусственный интеллект . 287 : 103352. дои : 10.1016 / j.artint.2020.103352 . ISSN 0004-3702 .

дальнейшее чтение

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

[1] Ковальский, Роберт; Серго, Марек (1986-03-01). «Логическое исчисление событий» . Вычислительная техника нового поколения . 4 (1): 67–95. DOI : 10.1007 / BF03037383 . ISSN 1882-7055 . S2CID 7584513 .

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

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

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

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

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

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

[8] Ма, Jiefei; Миллер, Роб; Моргенштерн, Леора; Паткос, Теодор (28.07.2014). «Расчет эпистемических событий для рассуждений на основе ASP о знании прошлого, настоящего и будущего» . Серия EPiC в вычислительной технике . Кресло. 26 : 75–87. DOI : 10,29007 / zswj .

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

Languages

In other projects