Проблема со стрельбой в Йельском университете - Yale shooting problem

В Проблема со стрельбой в Йельском университете головоломка или сценарий в формальной ситуационной логика на каких ранних логических решениях проблема с рамой провал. Название этой проблемы происходит от ее изобретателей, Стив Хэнкс и Дрю Макдермотт, работая в Йельский университет когда они это предложили. В этом сценарии Фред (позже идентифицированный как индюк ) изначально жив, а ружье изначально разряжено. Ожидается, что заряжание пистолета, ожидание и затем выстрел в Фреда убьет Фреда. Однако если инерция формализуется в логике путем минимизации изменений в этой ситуации, то нельзя однозначно доказать, что Фред мертв после загрузки, ожидания и стрельбы. В одном случае Фред действительно умирает; в другом (тоже логически правильном) решении, пистолет загадочным образом разряжается, и Фред выживает.

Технически этот сценарий описывается двумя беглый (свободное владение - это состояние, которое может изменить значение истины через некоторое время): ${ displaystyle live}$ и ${ displaystyle loaded}$ . Изначально первое условие верно, а второе - ложно. Потом ружье заряжается, проходит некоторое время, и ружье стреляет. Такие проблемы можно формализовать логически, рассмотрев четыре момента времени. ${ displaystyle 0}$ , ${ displaystyle 1}$ , ${ displaystyle 2}$ , и ${ displaystyle 3}$ , и поворачивая каждый беглый язык, например ${ displaystyle live}$ в предикат ${ Displaystyle в живых (т)}$ в зависимости от времени. Непосредственная формализация постановки задачи Йельской стрельбы в логике следующая:

{ displaystyle live (0)}

{ displaystyle neg loaded (0)}

{ displaystyle true rightarrow loaded (1)}

{ displaystyle loaded (2) rightarrow neg alive (3)}

Первые две формулы представляют начальное состояние. Третья формула формализует эффект заряжания пистолета по времени ${ displaystyle 0}$ . Четвертая формула формализует эффект стрельбы по Фреду в момент ${ displaystyle 2}$ . Это упрощенная формализация, в которой имена действий не учитываются, а эффекты действий прямо указываются для моментов времени, в которые эти действия выполняются. Увидеть ситуационное исчисление для подробностей.

Приведенных выше формул, будучи прямой формализацией известных фактов, недостаточно для правильной характеристики области. Действительно, ${ displaystyle neg alive (1)}$ согласуется со всеми этими формулами, хотя нет оснований полагать, что Фред умирает до того, как выстрелит из пистолета. Проблема в том, что приведенные выше формулы включают только эффекты действий, но не указывают, что все флюенты, не измененные действиями, остаются прежними. Другими словами, формула ${ Displaystyle живой (0) Equiv alive (1)}$ необходимо добавить, чтобы формализовать неявное предположение, что заряжание оружия только меняет значение ${ displaystyle loaded}$ а не ценность ${ displaystyle live}$ . Необходимость большого количества формул, устанавливающих очевидный факт, что условия не меняются, если их не изменяет действие, известна как проблема с рамой.

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

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

${ displaystyle live (0)}$	${ displaystyle live (1)}$	${ displaystyle live (2)}$	${ displaystyle neg alive (3)}$
${ displaystyle neg loaded (0)}$	${ displaystyle loaded (1)}$	${ displaystyle loaded (2)}$	${ displaystyle loaded (3)}$

Это ожидаемое решение. Он содержит два плавных изменения: ${ displaystyle loaded}$ становится истинным в момент времени 1 и ${ displaystyle live}$ становится ложным в момент 3. Следующая оценка также удовлетворяет всем приведенным выше формулам.

${ displaystyle live (0)}$	${ displaystyle live (1)}$	${ displaystyle live (2)}$	${ displaystyle live (3)}$
${ displaystyle neg loaded (0)}$	${ displaystyle loaded (1)}$	${ displaystyle neg loaded (2)}$	${ displaystyle neg loaded (3)}$

В этой оценке остались только два изменения: ${ displaystyle loaded}$ становится истинным во время 1 и ложным во время 2. В результате эта оценка считается действительным описанием эволюции состояния, хотя нет веских причин для объяснения ${ displaystyle loaded}$ ложно во время 2. Тот факт, что минимизация изменений приводит к неправильному решению, является мотивацией для введения проблемы стрельбы Йельского университета.

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

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

Сценарий стрельбы в Йельском университете также правильно оформлен Reiter версия ситуационное исчисление, то свободный расчет, а языки описания действий.

В 2005 году статья 1985 года, в которой впервые был описан сценарий стрельбы в Йельском университете, получила оценку Премия AAAI Classic Paper. Несмотря на то, что проблема решена, этот пример все еще иногда упоминается в недавних исследовательских работах, где он используется в качестве иллюстративного примера (например, для объяснения синтаксиса новой логики для рассуждения о действиях), а не представляется как проблема.

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

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

М. Гельфонд и В. Лифшиц (1993). Представление действий и изменений с помощью логических программ. Журнал логического программирования, 17:301–322.
С. Хэнкс и Д. Макдермотт (1987). Немонотонная логика и временная проекция. Искусственный интеллект, 33(3):379–412.
Дж. Маккарти (1986). Применение ограничения к формализации здравого смысла. Искусственный интеллект, 28:89–116.
Т. Митчелл и Х. Левеск (2006). Награды AAAI Classic Paper 2005 года. «AI Magazine», 26 (4): 98–99.
Р. Рейтер (1991). Проблема фрейма в ситуационном исчислении: простое решение (иногда) и результат полноты для регрессии цели. Во Владимире Лифшице, редакторе, Искусственный интеллект и математическая теория вычислений: статьи в честь Джона Маккарти, страницы 359–380. Academic Press, Нью-Йорк.
Э. Сандеволл (1994). Функции и флюенты. Издательство Оксфордского университета.