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

В исчисление событий это логичный язык для представления и рассуждения о событиях и их последствиях, впервые представленных Роберт Ковальски и Марек Сергот в 1986 г.^[1] Он был продлен Мюррей Шанахан и Роб Миллер в 1990-е гг.^[2] Подобно другим языкам для рассуждений об изменениях, исчисление событий представляет эффекты действия на беглый. Тем не мение, События также может быть внешним по отношению к системе. В исчислении событий можно указать значение текучести в некоторые заданные моменты времени, события, которые происходят в заданные моменты времени, и их эффекты.

Fluents и события

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

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

Независимые от предметной области аксиомы

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

{ displaystyle { mathit {HoldsAt}} (f, t) leftarrow [{ mathit {Happens}} (e, t_ {1}) wedge { mathit {Initiates}} (e, f, t_ {1 }) wedge (t_ {1}

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

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

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

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

{ Displaystyle { mathit {Clipped}} (т_ {1}, е, т_ {2}) эквив существует е, т [{ mathit {Happens}} (е, т) клин (т_ {1} leq t

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

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

{ Displaystyle { mathit {Посвященные}} (е, е, т) эквив [е = открытый клин f = isopen клин { mathit {HoldsAt}} (haskey, t)] vee cdots}

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

Приведенная выше формула определяет значение истины из ${ 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)}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Другие известные расширения исчисления событий включают: вероятностный диалекты. Например, Artikis et al. представила Марковские логические сети на основе^[6] и вероятностный^[7] варианты ЭК.

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

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

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

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

Брандано, С. (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. Дои:10.1007 / BF03037383. ISSN 1882-7055. S2CID 7584513.

[2] Миллер, Роб; Шанахан, Мюррей (2002), Какас, Антонис С.; Садри, Фариба (ред.), «Некоторые альтернативные формулировки исчисления событий», Computational Logic: Logic Programming and Beyond: Essays in Honor of Robert A. Kowalski Part II, Lecture Notes in Computer Science, Berlin, Heidelberg: Springer, pp. 452–490, стр. Дои:10.1007/3-540-45632-5_17, ISBN 978-3-540-45632-2, получено 2020-10-05

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

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

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

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]