Проблема с рамой - Википедия - Frame problem

В искусственный интеллект, то проблема с рамой описывает проблему с использованием логика первого порядка (FOL), чтобы выразить факты о роботе в мире. Представление состояния робота с помощью традиционного FOL требует использования многих аксиом, которые просто подразумевают, что вещи в окружающей среде не изменяются произвольно. Например, Хейс описывает "блокировать мир "с правилами наложения блоков вместе. В системе ВОЛС дополнительные аксиомы необходимы для того, чтобы делать выводы об окружающей среде (например, что блок не может изменить положение, если он физически не перемещен). Проблема фрейма - это проблема поиска адекватных наборов аксиом для жизнеспособного описания среды робота.^[1]

Джон Маккарти и Патрик Дж. Хейс определили эту проблему в своей статье 1969 года, Некоторые философские проблемы с точки зрения искусственного интеллекта. В этой статье и во многих последующих, формальная математическая проблема была отправной точкой для более общих обсуждений сложности представления знаний для искусственного интеллекта. Такие вопросы, как предоставление рациональных допущений по умолчанию и что люди считают здравым смыслом в виртуальной среде.^[2] Позже термин приобрел более широкое значение в философия, где она сформулирована как проблема ограничения убеждений, которые должны обновляться в ответ на действия. В логическом контексте действия обычно определяются тем, что они изменяют, с неявным предположением, что все остальное (фрейм) остается неизменным.

Описание

Проблема с фреймами возникает даже в очень простых областях. Сценарий с дверью, которая может быть открытой или закрытой, и светом, который может быть включен или выключен, статически представлен двумя предложения ${ displaystyle mathrm {open}}$ и ${ displaystyle mathrm {on}}$ . Если эти условия могут измениться, их лучше представить двумя предикаты ${ Displaystyle mathrm {open} (т)}$ и ${ Displaystyle mathrm {on} (т)}$ которые зависят от времени; такие предикаты называются беглый. Область, в которой дверь закрыта и свет выключен в момент времени 0, а дверь открыта в момент времени 1, может быть непосредственно представлена в логике.^{[требуется разъяснение ]} по следующим формулам:

{ displaystyle neg mathrm {open} (0)}

{ displaystyle neg mathrm {on} (0)}

{ displaystyle mathrm {open} (1)}

Первые две формулы представляют исходную ситуацию; третья формула представляет результат выполнения действия по открытию двери в момент времени 1. Если бы такое действие имело предварительные условия, такие как отпирание двери, оно было бы представлено следующим образом: ${ displaystyle neg mathrm {заблокировано} (0) подразумевает mathrm {open} (1)}$ . На практике можно было бы иметь предикат ${ Displaystyle mathrm {executeopen} (т)}$ для указания времени выполнения действия и правила ${ displaystyle forall t. mathrm {executeopen} (t) подразумевает mathrm {open} (t + 1)}$ для уточнения результатов действий. Статья о ситуационное исчисление дает более подробную информацию.

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

${ displaystyle neg mathrm {open} (0)}$	${ displaystyle mathrm {open} (1)}$
${ displaystyle neg mathrm {on} (0)}$	${ displaystyle neg mathrm {on} (1)}$

В самом деле, еще один набор условий, который согласуется с тремя приведенными выше формулами:

${ displaystyle neg mathrm {open} (0)}$	${ displaystyle mathrm {open} (1)}$
${ displaystyle neg mathrm {on} (0)}$	${ displaystyle mathrm {on} (1)}$

Проблема фрейма заключается в том, что указание только того, какие условия изменяются действиями, не влечет за собой, что все другие условия не изменяются. Эта проблема может быть решена путем добавления так называемых «аксиом фрейма», которые явно указывают, что все условия, на которые не влияют действия, не изменяются во время выполнения этого действия. Например, поскольку действие, выполняемое в момент времени 0, - это действие открытия двери, аксиома рамы будет утверждать, что состояние света не меняется с момента 0 на время 1:

{ Displaystyle mathrm {on} (0) iff mathrm {on} (1)}

Проблема фрейма состоит в том, что одна такая аксиома фрейма необходима для каждой пары действия и условия, так что действие не влияет на условие.^{[требуется разъяснение ]} Другими словами, проблема состоит в том, чтобы формализовать динамическую область без явного указания аксиом фрейма.

Решение, предложенное Маккарти для решения этой проблемы, предполагает предположение, что произошло минимальное количество изменений условий; это решение формализовано в рамках ограничение. В Проблема со стрельбой в Йельском университете Однако показывает, что это решение не всегда верно. Затем были предложены альтернативные решения, включая завершение предикатов, плавную окклюзию, аксиомы государства-преемника, так далее.; они объяснены ниже. К концу 1980-х годов проблема фрейма, определенная Маккарти и Хейсом, была решена.^{[требуется разъяснение ]}. Однако даже после этого термин «проблема фрейма» все еще использовался, отчасти для обозначения той же проблемы, но в других условиях (например, одновременных действий), а отчасти для обозначения общей проблемы представления и рассуждения с динамическими домены.

Решения

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

Жидкий раствор для окклюзии

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

Обоснование этого решения состоит в том, чтобы представить не только значение условий во времени, но и то, может ли на них повлиять последнее выполненное действие. Последнее представлено другим состоянием, называемым окклюзией. Условие называется окклюзия в заданный момент времени, если только что было выполнено действие, в результате которого условие становится истинным или ложным. Окклюзию можно рассматривать как «разрешение на изменение»: если условие закрыто, оно освобождается от подчинения ограничению инерции.

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

{ displaystyle neg mathrm {open} (0)}

{ displaystyle neg mathrm {on} (0)}

{ displaystyle mathrm {open} (1) wedge mathrm {occludeopen} (1)}

{ Displaystyle forall т. neg mathrm {occludeopen} (т) подразумевает ( mathrm {open} (t-1) iff mathrm {open} (t))}

{ displaystyle forall t. neg mathrm {occludeon} (t) подразумевает ( mathrm {on} (t-1) iff mathrm {on} (t))}

В общем, каждое действие, делающее условие истинным или ложным, также делает истинным соответствующий предикат окклюзии. В этом случае, ${ Displaystyle mathrm {occludeopen} (1)}$ верно, что делает антецедент четвертой формулы выше ложным для ${ displaystyle t = 1}$ ; следовательно, ограничение, которое ${ Displaystyle mathrm {open} (т-1) iff mathrm {open} (т)}$ не подходит для ${ displaystyle t = 1}$ . Следовательно, ${ displaystyle mathrm {open}}$ может изменять значение, что также обеспечивается третьей формулой.

Чтобы это условие работало, предикаты окклюзии должны быть истинными только тогда, когда они становятся истинными в результате действия. Этого можно достичь либо ограничение или по завершению предиката. Стоит отметить, что окклюзия не обязательно подразумевает изменение: например, выполнение действия открытия двери, когда она уже была открыта (в формализации выше), делает предикат ${ displaystyle mathrm {occludeopen}}$ правда и делает ${ displaystyle mathrm {open}}$ истинный; тем не мение, ${ displaystyle mathrm {open}}$ не изменил значение, как это уже было верно.

Решение для завершения предиката

Это кодирование похоже на решение для плавной окклюзии, но дополнительные предикаты обозначают изменение, а не разрешение на изменение. Например, ${ Displaystyle mathrm {changeopen} (т)}$ представляет тот факт, что предикат ${ displaystyle mathrm {open}}$ со временем изменится ${ displaystyle t}$ к ${ displaystyle t + 1}$ . В результате предикат изменяется тогда и только тогда, когда соответствующий предикат изменения истинен. Действие приводит к изменению тогда и только тогда, когда оно делает истинным условие, которое ранее было ложным, или наоборот.

{ displaystyle neg mathrm {open} (0)}

{ displaystyle neg mathrm {on} (0)}

{ displaystyle neg mathrm {open} (0) подразумевает mathrm {changeopen} (0)}

{ Displaystyle forall т. mathrm {changeopen} (т) iff ( neg mathrm {open} (t) iff mathrm {open} (t + 1))}

{ Displaystyle forall т. mathrm {changeon} (т) iff ( neg mathrm {on} (t) iff mathrm {on} (t + 1))}

Третья формула - это другой способ сказать, что открытие двери приводит к открытию двери. Точнее, в нем говорится, что открытие двери изменяет состояние двери, если она была закрыта ранее. Последние два условия говорят о том, что условие меняет значение во времени. ${ displaystyle t}$ тогда и только тогда, когда соответствующий предикат изменения истинен во время ${ displaystyle t}$ . Чтобы завершить решение, моменты времени, в которые предикаты изменения верны, должны быть как можно меньше, и это можно сделать, применив завершение предиката к правилам, определяющим эффекты действий.

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

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

действие делает условие истинным; или же
условие ранее было истинным, и действие не делает его ложным.

А аксиома государства-преемника является формализацией в логике этих двух фактов. Например, если ${ Displaystyle mathrm {opendoor} (т)}$ и ${ Displaystyle mathrm {closedoor} (т)}$ два условия используются для обозначения того, что действие выполняется во время ${ displaystyle t}$ Чтобы открыть или закрыть дверь, соответственно, рабочий пример кодируется следующим образом.

{ displaystyle neg mathrm {open} (0)}

{ displaystyle neg mathrm {on} (0)}

{ Displaystyle mathrm {opendoor} (0)}

{ Displaystyle forall т. mathrm {open} (т + 1) iff mathrm {opendoor} (т) vee ( mathrm {open} (т) клин neg mathrm {closedoor} (т) )}

Это решение сосредоточено на ценности условий, а не на эффектах действий. Другими словами, для каждого условия есть аксиома, а не формула для каждого действия. Предпосылки к действиям (которых нет в данном примере) формализованы другими формулами. Следующие аксиомы состояний используются в варианте ситуационное исчисление предложеноРэй Рейтер.

Беглое решение для исчисления

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

Разница между предикатом и термином в логике первого порядка состоит в том, что термин является представлением объекта (возможно, сложного объекта, состоящего из других объектов), в то время как предикат представляет условие, которое может быть истинным или ложным при оценке по данный набор условий.

В беглом исчислении каждое возможное состояние представлено термином, полученным путем композиции других терминов, каждый из которых представляет условия, которые истинны в состоянии. Например, состояние, в котором дверь открыта и горит свет, обозначается термином ${ displaystyle mathrm {open} circ mathrm {on}}$ . Важно отметить, что термин не является истинным или ложным сам по себе, поскольку это объект, а не условие. Другими словами, термин ${ displaystyle mathrm {open} circ mathrm {on}}$ представляют возможное состояние и само по себе не означает, что это текущее состояние. Можно указать отдельное условие, чтобы указать, что это действительно состояние в данный момент времени, например, ${ Displaystyle mathrm {состояние} ( mathrm {open} circ mathrm {on}, 10)}$ означает, что это состояние во время ${ displaystyle 10}$ .

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

{ Displaystyle mathrm {состояние} (s circ mathrm {open}, 1) iff mathrm {состояние} (s, 0)}

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

{ Displaystyle mathrm {состояние} (s, 1) iff mathrm {состояние} (s circ mathrm {open}, 0)}

Эта формула работает при условии, что приведены подходящие аксиомы о ${ displaystyle mathrm {состояние}}$ и ${ displaystyle circ}$ , например, термин, содержащий одно и то же условие дважды, не является допустимым состоянием (например, ${ Displaystyle mathrm {состояние} ( mathrm {open} circ s circ mathrm {open}, т)}$ всегда ложно для каждого ${ displaystyle s}$ и ${ displaystyle t}$ ).

Решение для исчисления событий

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

Логическое решение по умолчанию

Проблему фрейма можно рассматривать как проблему формализации принципа, согласно которому по умолчанию «предполагается, что все остается в том состоянии, в котором оно находится» (Лейбниц, "Введение в секретную энциклопедию", c. 1679). Это значение по умолчанию, иногда называемое здравый смысл закон инерции, был выражен Раймонд Рейтер в логика по умолчанию:

{ Displaystyle { гидроразрыва {R (x, s) ;: R (x, mathrm {do} (a, s))} {R (x, mathrm {do} (a, s))} }}

(если ${ Displaystyle R (х)}$ верно в ситуации ${ displaystyle s}$ , и можно предположить^[3] который ${ Displaystyle R (х)}$ остается верным после выполнения действия ${ displaystyle a}$ , то можно заключить, что ${ Displaystyle R (х)}$ остается верным).

Стив Хэнкс и Дрю Макдермотт утверждали, что на основании их Йельская стрельба Например, это решение проблемы фрейма неудовлетворительно. Однако Хадсон Тернер показал, что он работает правильно при наличии соответствующих дополнительных постулатов.

Решение для программирования набора ответов

Аналог логического решения по умолчанию на языке программирование набора ответов это правило с сильное отрицание:

{ Displaystyle г (Х, Т + 1) leftarrow г (Х, Т), { hbox {not}} sim г (Х, Т + 1)}

(если ${ Displaystyle г (Х)}$ верно во время ${ displaystyle T}$ , и можно считать, что ${ Displaystyle г (Х)}$ остается верным во время ${ displaystyle T + 1}$ , то можно заключить, что ${ Displaystyle г (Х)}$ остается верным).

Логическое решение разделения

Логика разделения это формализм для рассуждений о компьютерных программах с использованием до / после спецификаций формы ${ Displaystyle {предварительное условие } код {постусловие }}$ . Логика разделения является продолжением Логика Хоара ориентирована на рассуждения об изменяемых структурах данных в памяти компьютера и других динамических ресурсах, и имеет специальную связку *, произносимую «и отдельно», чтобы поддерживать независимые рассуждения о непересекающихся областях памяти.^[4]^[5]

Логика разделения использует в обтяжку интерпретация пред / пост спецификаций, которые говорят, что код может Только доступ к ячейкам памяти, существование которых гарантировано предварительным условием.^[6] Это приводит к обоснованности самого важного правила вывода логики, фрейм правило

${ displaystyle { frac { {precondition } code {postcondition }} { {precondition ast frame } code {postcondition ast frame }}}}$

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

${ displaystyle { frac { {list (x) } code {sortedlist (x) }} { {list (x) ast sortedlist (y) } code {sortedlist (x ) ast sortedlist (y) }}}}$

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

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

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

Языки описания действий

Языки описания действий избегайте проблемы с рамкой, а не решайте ее. Язык описания действий - это формальный язык с синтаксисом, специфичным для описания ситуаций и действий. Например, действие ${ Displaystyle mathrm {opendoor}}$ открывает дверь, если она не заперта, выражается в:

{ Displaystyle mathrm {opendoor}}

причины

{ displaystyle mathrm {open}}

если

{ displaystyle neg mathrm {заблокировано}}

Семантика языка описания действий зависит от того, что язык может выражать (одновременные действия, отложенные эффекты и т. Д.), И обычно основывается на переходные системы.

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

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

Примечания

^ Хейс, Патрик. «Проблема фрейма и связанные с ней проблемы в искусственном интеллекте» (PDF). Эдинбургский университет.
^ Маккарти, Дж; П.Дж. Хейс (1969). «Некоторые философские проблемы с точки зрения искусственного интеллекта». Машинный интеллект. 4: 463–502. CiteSeerX 10.1.1.85.5082.
^ т.е. противоречивой информации нет
^ Рейнольдс, Дж. К. (2002). «Логика разделения: логика для общих изменяемых структур данных». Материалы 17-го ежегодного симпозиума IEEE по логике в компьютерных науках. Копенгаген, Дания: IEEE Comput. Soc: 55–74. CiteSeerX 10.1.1.110.7749. Дои:10.1109 / LICS.2002.1029817. ISBN 978-0-7695-1483-3. S2CID 6271346.
^ О'Хирн, Питер (28 января 2019 г.). «Логика разделения». Коммуникации ACM. 62 (2): 86–95. Дои:10.1145/3211968. ISSN 0001-0782.
^ О'Хирн, Питер; Рейнольдс, Джон; Ян, Хонгсок (2001). Фрибург, Лоран (ред.). «Местные рассуждения о программах, изменяющих структуры данных». Логика информатики. Конспект лекций по информатике. Берлин, Гейдельберг: Springer. 2142: 1–19. Дои:10.1007/3-540-44802-0_1. ISBN 978-3-540-44802-0.
^ Кальканьо Криштиану; Дино Дистефано; Питер О'Хирн; Хонсок Ян (01.12.2011). «Анализ формы композиции с помощью двойного отведения». Журнал ACM. 58 (6): 1–66. Дои:10.1145/2049697.2049700. S2CID 52808268.
^ Дистефано, Дино; Фендрих, Мануэль; Логоццо, Франческо; О'Хирн, Питер (24.07.2019). «Масштабирование статического анализа в Facebook». Коммуникации ACM. 62 (8): 62–70. Дои:10.1145/3338112.

внешняя ссылка

Залта, Эдуард Н. (ред.). "Проблема фрейма". Стэнфордская энциклопедия философии.
Некоторые философские проблемы с точки зрения искусственного интеллекта; оригинальная статья Маккарти и Хейса, в которой была предложена проблема.

[1] Хейс, Патрик. «Проблема фрейма и связанные с ней проблемы в искусственном интеллекте» (PDF). Эдинбургский университет.

[2] Маккарти, Дж; П.Дж. Хейс (1969). «Некоторые философские проблемы с точки зрения искусственного интеллекта». Машинный интеллект. 4: 463–502. CiteSeerX 10.1.1.85.5082.

[3] т.е. противоречивой информации нет

[4] Рейнольдс, Дж. К. (2002). «Логика разделения: логика для общих изменяемых структур данных». Материалы 17-го ежегодного симпозиума IEEE по логике в компьютерных науках. Копенгаген, Дания: IEEE Comput. Soc: 55–74. CiteSeerX 10.1.1.110.7749. Дои:10.1109 / LICS.2002.1029817. ISBN 978-0-7695-1483-3. S2CID 6271346.

[5] О'Хирн, Питер (28 января 2019 г.). «Логика разделения». Коммуникации ACM. 62 (2): 86–95. Дои:10.1145/3211968. ISSN 0001-0782.

[6] О'Хирн, Питер; Рейнольдс, Джон; Ян, Хонгсок (2001). Фрибург, Лоран (ред.). «Местные рассуждения о программах, изменяющих структуры данных». Логика информатики. Конспект лекций по информатике. Берлин, Гейдельберг: Springer. 2142: 1–19. Дои:10.1007/3-540-44802-0_1. ISBN 978-3-540-44802-0.

[7] Кальканьо Криштиану; Дино Дистефано; Питер О'Хирн; Хонсок Ян (01.12.2011). «Анализ формы композиции с помощью двойного отведения». Журнал ACM. 58 (6): 1–66. Дои:10.1145/2049697.2049700. S2CID 52808268.

[8] Дистефано, Дино; Фендрих, Мануэль; Логоццо, Франческо; О'Хирн, Питер (24.07.2019). «Масштабирование статического анализа в Facebook». Коммуникации ACM. 62 (8): 62–70. Дои:10.1145/3338112.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]