Ситуационный расчет

Ситуационное исчисление — это логический формализм, предназначенный для представления и рассуждений о динамических областях. Впервые он был представлен Джоном Маккарти в 1963 году. ^[1] Основная версия ситуационного исчисления, представленная в этой статье, основана на версии, представленной Рэем Рейтером в 1991 году. За ней следуют разделы, посвященные версии Маккарти 1986 года и формулировке логического программирования .

Обзор [ править ]

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

Действия, которые можно совершать в мире
, Свободно говорящие которые описывают состояние мира
Ситуации

Домен формализуется рядом формул, а именно:

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

В качестве рабочего примера будет смоделирован простой мир роботов. В этом мире есть один робот и несколько неодушевленных предметов. Мир построен по сетке, поэтому локации можно указать с точки зрения $(x,y)$ координатные точки. Робот может перемещаться по миру, поднимать и бросать предметы. Некоторые предметы могут быть слишком тяжелыми, чтобы их мог поднять робот, или хрупкими, поэтому они могут сломаться при падении. Робот также имеет возможность ремонтировать любые сломанные предметы, которые он держит.

Элементы [ править ]

Основными элементами ситуационного исчисления являются действия, флюанты и ситуации. В описании мира также обычно участвует ряд объектов. Исчисление ситуаций основано на отсортированной области трех видов: действия, ситуации и объекты, где объекты включают все, что не является действием или ситуацией. Можно использовать переменные любого типа. Хотя действия, ситуации и объекты являются элементами предметной области, флюенты моделируются либо как предикаты, либо как функции.

Действия [ править ]

Действия образуют своего рода домен. Можно использовать переменные действия сортировки, а также функции, результатом которых является действие сортировки. Действия можно измерить количественно. В примере мира роботов возможные условия действия будут такими: $move(x,y)$ смоделировать перемещение робота в новое место $(x,y)$ , и $pickup(o)$ смоделировать робота, подбирающего предмет $o$ . Специальный предикат $Poss$ используется для указания того, когда действие может быть выполнено.

Ситуации [ править ]

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

Ситуация – это конечная последовательность действий. Период. Это не состояние, это не снимок, это история . ^[2]

Ситуация до того, как были выполнены какие-либо действия, обычно обозначается $S_{0}$ и назвал начальную ситуацию. Новая ситуация, возникающая в результате выполнения действия, обозначается функциональным символом $do$ (Некоторые другие ссылки ^[3] также используйте $результат$ ). Этот функциональный символ имеет в качестве аргументов ситуацию и действие, а также ситуацию как результат, причем последняя представляет собой ситуацию, возникающую в результате выполнения данного действия в данной ситуации.

Тот факт, что ситуации представляют собой последовательности действий, а не состояния, подтверждается аксиомой, утверждающей, что $do(a,s)$ равно $do(a',s')$ тогда и только тогда, когда $a=a'$ и $s=s'$ . Это условие не имеет смысла, если ситуации являются состояниями, поскольку два разных действия, выполненные в двух разных состояниях, могут привести к одному и тому же состоянию.

В примере мира роботов, если первым действием робота является перемещение в нужное место $(2,3)$ , первое действие $move(2,3)$ и в результате ситуация $do(move(2,3),S_{0})$ . Если его следующим действием будет взятие мяча, результирующая ситуация будет такой: $do(pickup(Ball),do(move(2,3),S_{0}))$ . Условия таких ситуаций, как $do(move(2,3),S_{0})$ и $do(pickup(Ball),do(move(2,3),S_{0}))$ обозначают последовательность выполняемых действий, а не описание состояния, возникающего в результате выполнения.

Свободно владею [ править ]

Утверждения, истинностное значение которых может измениться, моделируются реляционными флюентами , предикатами, которые принимают ситуацию в качестве своего окончательного аргумента. Также возможны функциональные флюенты — функции, которые принимают ситуацию в качестве последнего аргумента и возвращают зависящее от ситуации значение. Свободно говорящих можно рассматривать как «свойства мира».

В примере беглый ${\textit {isCarrying}}(o,s)$ может использоваться для обозначения того, что робот несет определенный объект в конкретной ситуации. Если изначально робот ничего не несет, ${\textit {isCarrying}}(Ball,S_{0})$ является ложным, пока ${\textit {isCarrying}}(Ball,do(pickup(Ball),S_{0}))$ это правда. Местоположение робота можно смоделировать с помощью функционального флюэнта. $location(s)$ который возвращает местоположение $(x,y)$ робота в конкретной ситуации.

Формулы [ править ]

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

Предварительные условия действия [ править ]

Некоторые действия могут быть невыполнимы в конкретной ситуации. Например, невозможно положить предмет, если вы на самом деле не несете его. Ограничения на выполнение действий моделируются литералами вида ${\textit {Poss}}(a,s)$ , где $a$ — действие, $s$ — ситуация, а $Poss$ — специальный бинарный предикат, обозначающий выполнимость действий. В этом примере условие, при котором падение объекта возможно только при его переноске, моделируется следующим образом:

{\textit {Poss}}(drop(o),s)\leftrightarrow {\textit {isCarrying}}(o,s)

В качестве более сложного примера можно привести следующие модели: робот может переносить только один объект за раз и что некоторые объекты слишком тяжелы, чтобы робот мог их поднять (обозначается предикатом $Heavy$ ):

{\textit {Poss}}(pickup(o),s)\leftrightarrow (\forall z\ \neg {\textit {isCarrying}}(z,s))\wedge \neg heavy(o)

Эффекты действий [ править ]

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

Poss(pickup(o),s)\rightarrow {\textit {isCarrying}}(o,do(pickup(o),s))

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

Poss(drop(o),s)\wedge fragile(o)\rightarrow broken(o,do(drop(o),s))

Хотя эта формула правильно описывает эффект действий, ее недостаточно для правильного логического описания действия из-за проблемы фрейма .

Проблема с рамкой [ править ]

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

Poss(pickup(o),s)\wedge location(s)=(x,y)\rightarrow location(do(pickup(o),s))=(x,y)

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

Аксиомы преемника - государства

Аксиомы последующих состояний «решают» проблему фрейма в ситуационном исчислении. Согласно этому решению, разработчик должен перечислить в качестве аксиом эффекта все способы, которыми можно изменить ценность конкретного флюента. Аксиомы эффекта, влияющие на ценность свободного владения языком $F({\overrightarrow {x}},s)$ можно записать в обобщенной форме как аксиому положительного и отрицательного эффекта:

Poss(a,s)\wedge \gamma _{F}^{+}({\overrightarrow {x}},a,s)\rightarrow F({\overrightarrow {x}},do(a,s))

Poss(a,s)\wedge \gamma _{F}^{-}({\overrightarrow {x}},a,s)\rightarrow \neg F({\overrightarrow {x}},do(a,s))

Формула $\gamma _{F}^{+}$ описывает условия, при которых действие $a$ в ситуации $s$ приводит к тому, что беглое $F$ становится истинным в последующей ситуации. $do(a,s)$ . Так же, $\gamma _{F}^{-}$ описывает условия, при которых выполнение действия $a$ в ситуации $s$ делает беглое $F$ ложным в последующей ситуации.

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

Poss(a,s)\rightarrow \left[F({\overrightarrow {x}},do(a,s))\leftrightarrow \gamma _{F}^{+}({\overrightarrow {x}},a,s)\vee \left(F({\overrightarrow {x}},s)\wedge \neg \gamma _{F}^{-}({\overrightarrow {x}},a,s)\right)\right]

возможно выполнить действие $a$ На словах эта формула гласит: «при условии, что в ситуации $s$ , беглое $F$ будет истинным в результирующей ситуации». $do(a,s)$ тогда и только тогда, когда выполнение $делает$ in $s$ это истинным или оно истинно в ситуации $,$ выполнение $in$ s $а$ не делает его ложным».

Например, значение беглого $нарушения,$ введенного выше, определяется следующей аксиомой состояния-преемника:

Poss(a,s)\rightarrow \left[broken(o,do(a,s))\leftrightarrow a=drop(o)\wedge fragile(o)\vee broken(o,s)\wedge a\neq repair(o)\right]

Штаты [ править ]

Свойства исходной или любой другой ситуации можно задать, просто формулируя их в виде формул. Например, факт об начальном состоянии формализуется путем утверждения утверждений о $S_{0}$ (что является не состоянием, а ситуацией ). Следующая модель утверждений, согласно которой изначально робот ничего не несет, находится на уровнерасположение $(0,0)$ , и нет сломанных объектов:

\forall z\,\neg {\textit {isCarrying}}(z,S_{0})

location(S_{0})=(0,0)\,

\forall o\,\neg broken(o,S_{0})

Основополагающие аксиомы [ править ]

Фундаментальные аксиомы ситуационного исчисления формализуют идею о том, что ситуации являются историями, поскольку $do(a,s)=do(a',s')\iff a=a'\land s=s'$ . Они также включают в себя другие свойства, такие как индукция второго порядка по ситуациям.

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

Регрессия ^[4] представляет собой механизм доказательства следствий в исчислении ситуаций. ^[5] Он основан на выражении формулы, содержащей ситуацию $do(a,s)$ через формулу, содержащую действие $a$ и ситуацию $s$ , но не ситуацию $do(a,s)$ . Повторяя эту процедуру, можно получить эквивалентную формулу, содержащую только начальную ситуацию $S 0$ . Доказывать последствия по этой формуле якобы проще, чем по исходной.

ГОЛЫЕ [ править ]

ГОЛОГ — язык логического программирования, основанный на ситуационном исчислении. ^[6]^[7]

Исходная версия ситуационного исчисления [ править ]

Основное различие между первоначальным исчислением ситуаций Маккарти и Хейса и тем, которое используется сегодня, заключается в интерпретации ситуаций. В современной версии ситуационного исчисления ситуация представляет собой последовательность действий. Первоначально ситуации определялись как «полное состояние Вселенной в определенный момент времени». С самого начала было ясно, что такие ситуации невозможно полностью описать; идея заключалась в том, чтобы просто дать некоторые утверждения о ситуациях и вывести из них последствия. Это также отличается от подхода, используемого в беглом исчислении , где состояние может быть совокупностью известных фактов, то есть, возможно, неполным описанием Вселенной.

В исходной версии ситуационного исчисления беглые слова не материализуются. Другими словами, условия, которые могут меняться, представлены предикатами, а не функциями. На самом деле Маккарти и Хейс определили флюэнт как функцию, которая зависит от ситуации, но затем они всегда использовали предикаты для представления флюентов. Например, тот факт, что в месте $x$ в ситуации $s$ идет дождь , представлен буквалом $raining(x,s)$ . В версии ситуационного исчисления Маккарти 1986 года используются функциональные флюенты. Например, положение объекта $x$ в ситуации $s$ представляется значением $location(x,s)$ , где $местоположение$ является функцией. Утверждения о таких функциях можно дать с помощью равенства: $location(x,s)=location(x,s')$ означает, что местоположение объекта $x$ одинаково в двух ситуациях $s$ и $s'$ .

Выполнение действий представлено функцией $result$ : выполнение действия $a$ в ситуации $s$ – это ситуация ${\textit {result}}(a,s)$ . Эффекты действий выражаются формулами, связывающими беглых в ситуациях $и$ беглых в ситуациях. ${\textit {result}}(a,s)$ . Например, то, что действие открытия двери приводит к тому, что дверь открыта, если она не заперта, представлено следующим образом:

\neg locked(door,s)\rightarrow open(door,{\textit {result}}(opens,s))

Предикаты $locked$ и $open$ представляют условия, при которых дверь заперта и открыта соответственно. Поскольку эти условия могут различаться, они представлены предикатами с аргументом ситуации. Формула гласит, что если дверь не заперта в ситуации, то дверь открывается после выполнения действия открытия, это действие представлено константой $opens$ .

Этих формул недостаточно, чтобы вывести все, что считается правдоподобным. Действительно, беглое владение различными ситуациями связано только в том случае, если они являются предпосылками и последствиями действий; если действие не влияет на беглого, невозможно сделать вывод, что оно не изменилось. Например, из приведенной выше формулы не следует, что $\neg locked(door,{\textit {result}}(opens,s))$ следует из $\neg locked(door,s)$ , чего и следовало ожидать (дверь не запирается при открытии). Чтобы инерция сохранялась, формулы, называемые аксиомами системы координат необходимы . Эти формулы определяют все неэффекты действий:

\neg locked(door,s)\rightarrow \neg locked(door,{\textit {result}}(opens,s))

В исходной формулировке ситуационного исчисления исходная ситуация, позже обозначаемая через $S_{0}$ , явно не идентифицирован. Исходная ситуация не нужна, если ситуации воспринимаются как описания мира. Например, чтобы представить сценарий, в котором дверь была закрыта, но не заперта, и выполняется действие по ее открытию, формализуется путем принятия константы $s$ для обозначения исходной ситуации и формулирования утверждений о ней (например, $\neg locked(door,s)$ ). То, что дверь открыта после изменения, отражается формулой $open(door,{\textit {result}}(opens,s))$ будучи повлечённым за собой. Вместо этого исходная ситуация необходима, если, как и в современном исчислении ситуаций, ситуация рассматривается как история действий, поскольку начальная ситуация представляет собой пустую последовательность действий.

Версия ситуационного исчисления, представленная Маккарти в 1986 году, отличается от исходной тем, что в ней используются функциональные беглые выражения (например, $location(x,s)$ — термин, обозначающий положение $x$ в ситуации $s$ ) и попытку использовать ограничение для замены аксиом системы координат.

Ситуационное исчисление как логическая программа [ править ]

Также возможно (например, Ковальский 1979, Апт и Безем 1990, Шанахан 1997) записать ситуационное исчисление в виде логической программы:

{\textit {Holds}}(f,do(a,s))\leftarrow {\textit {Poss}}(a,s)\wedge {\textit {Initiates}}(a,f,s)

{\textit {Holds}}(f,do(a,s))\leftarrow {\textit {Poss}}(a,s)\wedge {\textit {Holds}}(f,s)\wedge \neg {\textit {Terminates}}(a,f,s)

Здесь $Holds$ — метапредикат, а переменная $f$ варьируется по значениям Fluents. Предикаты $Poss$ , $Initiates$ и $Terminates$ соответствуют предикатам $Poss$ , $\gamma _{F}^{+}({\overrightarrow {x}},a,s)$ , и $\gamma _{F}^{-}({\overrightarrow {x}},a,s)$ соответственно. Левая стрелка ← — это половина эквивалентности ↔. Другая половина подразумевается в завершении программы, в котором отрицание интерпретируется как отрицание как неудача . Аксиомы индукции также неявны и нужны только для доказательства свойств программы. Обратное рассуждение, как и в разрешении SLD , которое является обычным механизмом, используемым для выполнения логических программ, неявно реализует регрессию.

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

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

^ Маккарти, Джон (1963). «Ситуации, действия и причинные законы» (PDF) . Технический отчет Стэнфордского университета . Архивировано из оригинала (PDF) 21 марта 2020 г.
^ «Вклад в дебаты ECSTER» .
^ «Объединяя повествования, Джон Маккарти и др. (1998)» (PDF) .
^ Уолдингер, Ричард. «Достижение нескольких целей одновременно». В «Чтениях по искусственному интеллекту», стр. 250–271. Морган Кауфманн, 1981 год.
^ Райтер, Р., 1991. Проблема фрейма в ситуационном исчислении: простое решение (иногда) и результат полноты для регрессии цели. Искусственная и математическая теория вычислений, 3.
^ Лейкмейер, Герхард. «Исчисление ситуаций и Голог: Учебное пособие» (PDF) . www.hybrid-reasoning.org . Проверено 16 июля 2014 г.
^ «Публикации о ГОЛОГе» . Проверено 16 июля 2014 г.

Дж. Маккарти и П. Хейс (1969). Некоторые философские проблемы с точки зрения искусственного интеллекта . В Б. Мельцере и Д. Мичи, редакторах, Machine Intelligence , 4:463–502. Издательство Эдинбургского университета, 1969.
Р. Ковальский (1979). Логика решения проблем - Elsevier North Holland.
КР Апт и М. Безем (1990). Ациклические программы. В: 7-я Международная конференция по логическому программированию. МТИ Пресс. Иерусалим, Израиль.
Р. Рейтер (1991). Проблема фрейма в ситуационном исчислении: простое решение (иногда) и результат полноты целевой регрессии. Владимир Лифшиц, редактор журнала « Искусственный интеллект и математическая теория вычислений: статьи в честь Джона Маккарти» , страницы 359–380, Сан-Диего, Калифорния, США. Academic Press Professional, Inc., 1991.
М. Шанахан (1997). Решение проблемы рамы: математическое исследование закона инерции здравого смысла. МТИ Пресс.
Х. Левеск, Ф. Пирри и Р. Рейтер (1998). Основы ситуационного расчета . Электронные транзакции по искусственному интеллекту , 2 (3–4): 159–178.
Ф. Пирри и Р. Рейтер (1999). Некоторые вклады в метатеорию ситуационного исчисления. Журнал ACM , 46(3):325–361. дои : 10.1145/316542.316545
Р. Рейтер (2001). Знания в действии: логические основы для определения и реализации динамических систем. Массачусетский технологический институт Пресс.

[1] Маккарти, Джон (1963). «Ситуации, действия и причинные законы» (PDF) . Технический отчет Стэнфордского университета . Архивировано из оригинала (PDF) 21 марта 2020 г.

[2] «Вклад в дебаты ECSTER» .

[3] «Объединяя повествования, Джон Маккарти и др. (1998)» (PDF) .

[4] Уолдингер, Ричард. «Достижение нескольких целей одновременно». В «Чтениях по искусственному интеллекту», стр. 250–271. Морган Кауфманн, 1981 год.

[5] Райтер, Р., 1991. Проблема фрейма в ситуационном исчислении: простое решение (иногда) и результат полноты для регрессии цели. Искусственная и математическая теория вычислений, 3.

[Lakemeyer2013-6] Лейкмейер, Герхард. «Исчисление ситуаций и Голог: Учебное пособие» (PDF) . www.hybrid-reasoning.org . Проверено 16 июля 2014 г.

[7] «Публикации о ГОЛОГе» . Проверено 16 июля 2014 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]