Ситуационное исчисление - Situation calculus

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

Обзор

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

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

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

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

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

Элементы

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

Действия

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

Ситуации

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

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

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

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

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

Свободно

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

В этом примере беглый ${ displaystyle is _carrying (o, s)}$ может использоваться, чтобы указать, что робот несет определенный объект в конкретной ситуации. Если изначально робот ничего не несет, ${ displaystyle is _carrying (Ball, S_ {0})}$ ложно, пока ${ displaystyle is _carrying (Ball, do (pickup (Ball), S_ {0}))}$ правда. Расположение робота можно смоделировать с помощью функционального бегуна. ${ displaystyle location (s)}$ который возвращает местоположение ${ Displaystyle (х, у)}$ робота в конкретной ситуации.

Формулы

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

Предпосылки действий

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

${ displaystyle Poss (drop (o), s) leftrightarrow is _carrying (o, s)}$

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

${ Displaystyle Посс (пикап (о), s) leftrightarrow ( forall z neg is _carrying (z, s)) клин neg Heavy (o)}$

Эффекты действия

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

${ displaystyle Poss (подобрать (o), s) rightarrow is _carrying (o, do (pickup (o), s))}$

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

${ Displaystyle Посс (капля (о), s) клин хрупкий (о) rightarrow сломанный (о, делать (капля (о), s))}$

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

Проблема с рамой

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

${ displaystyle Poss (подобрать (о), s) место клина (s) = (x, y) положение правой стрелки (do (подобрать (o), s)) = (x, y)}$

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

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

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

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

${ displaystyle Poss (a, s) wedge gamma _ {F} ^ {-} ({ overrightarrow {x}}, a, s) rightarrow neg F ({ overrightarrow {x}}, сделайте ( в качестве))}$

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

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

${ displaystyle 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) верно-верно]}$

На словах эта формула гласит: «при условии, что можно выполнить действие ${ displaystyle a}$ в ситуации ${ displaystyle s}$ , беглый ${ displaystyle F}$ будет правдой в сложившейся ситуации ${ displaystyle do (а, s)}$ если и только если выполнять ${ displaystyle a}$ в ${ displaystyle s}$ сделает это правдой, или это правда в ситуации ${ displaystyle s}$ и выполнение ${ displaystyle a}$ в ${ displaystyle s}$ не сделает это ложным ".

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

${ displaystyle Poss (a, s) rightarrow left [сломанный (o, do (a, s)) leftrightarrow a = drop (o) клин хрупкий (o) vee сломанный (o, s) клин a neq repair (o) right]}$

состояния

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

${ displaystyle forall z , neg - это _carrying (z, S_ {0})}$

${ Displaystyle местоположение (S_ {0}) = (0,0) ,}$

${ displaystyle forall o , neg broken (o, S_ {0})}$

Основополагающие аксиомы

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

Регресс

Регрессия - это механизм доказательства последствий при исчислении ситуации. Он основан на выражении формулы, содержащей ситуацию ${ displaystyle do (а, s)}$ в терминах формулы, содержащей действие ${ displaystyle a}$ и ситуация ${ displaystyle s}$ , но не ситуация ${ displaystyle do (а, s)}$ . Повторяя эту процедуру, можно получить эквивалентную формулу, содержащую только начальную ситуацию ${ displaystyle S_ {0}}$ . Доказательство следствий из этой формулы якобы проще, чем из исходной.

ГОЛОГ

GOLOG - это язык логического программирования, основанный на ситуационном исчислении.^[2]^[3]

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

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

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

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

{ displaystyle neg closed (дверь, s) rightarrow open (дверь, результат (открывается, s))}

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

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

{ displaystyle neg closed (дверь, s) rightarrow neg closed (дверь, результат (открывается, s))}

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

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

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

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

${ displaystyle Удерживает (f, do (a, s)) leftarrow Poss (a, s) клин Посвященные (a, f, s)}$

${ displaystyle Удерживает (f, do (a, s)) leftarrow Poss (a, s) wedge Holds (f, s) wedge neg Завершает (a, f, s)}$

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