2.4. Рассуждения в терминах интервалов

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

Рассмотрим простой пример среды такого типа, называемой средой чудовища. Среда имеет число ячеек, равное расположенных по вертикали и горизонтали. Каждая внутренняя ячейка имеет четыре соседних, крайние ячейки могут не иметь соседних ячеек с одной или двух сторон. Агент, выступающий в роли единственного играющего, может переходить в одну из соседних ячеек. В одной из ячеек находится чудовище. Чудовище издает зловоние, которое распространяется на соседние ему ячейки. В одной из ячеек лежит золото, которое блестит. Кроме того, в ячейках могут быть бездонные ямы. В ячейках, соседних ячейкам с ямами, ощущается сквозняк. Задача агецта, стартуя в ячейке , добраться до ячейки с золотом, взять его и благополучно вернуться назад.

Исходное состояние среды чудовища соответствует рис. 2.3, где буквы в ячейках обозначают следующее: Ч — чудовище, 3 — зловоние, С — сквозняк, Б — блеск, Я — яма, агент. Сопоставим каждую ячейку среды с шестью логическими переменными Будем полагать, что значение этих переменных истинно, если

Рис. 2.3. Исходное состояние среды чудовиша

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

— отсутствие ориентации.

Естественно, такая интерпретация переменных означает, что только одна из них может быть истинна. Понятно, что суммарное число переменных равно и набор значений всех переменных целиком задает состояние среды чудовища. Так, например, начальное состояние среды, показанное на рис. 2.3, определяется набором значений этих переменных, в котором 17 переменных истинны: , а остальные ложны. Число таких наборов, обычно называемых полными наборами значений, или полными состояниями среды, астрономически велико и равно . Конечно, далеко не во всех полных состояниях может находиться среда вследствие ограничений на значения каких-либо переменных в зависимости от значения других. Например, как уже отмечалось, никакая переменная из с одним и тем же индексом никогда не может быть истинной, если истинна какая-либо другая из этого множества. А значит, и среда не может находиться в состояниях, где хотя бы две из них одновременно истинны. Тем не менее, если рассуждать в терминах состояний среды, то это число может быть слишком велико даже с учетом указанных ограничений, а таблицу истинности практически невозможно построить.

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

В ячейке, где находится чудовище, и в соседних ей ячейках агент ощущает зловоние чудовища.

В ячейках, соседних ячейке, в которой находится яма, агент ощущает сквозняк.

В ячейке, где находится золото, агент видит яркий блеск.

Агент всегда стоит лицом к одной из соседних ячеек и может совершать одно из следующих действий:

а) поворот к ячейке, в которой нет ни чудовища, ни ямы. Сопоставим это действие с переменной которая истинна, если действие поворота совершается, и ложна в противном случае;

б) переход в соседнюю ячейку, к которой агент стоит лицом. Сопоставим это действие с логической переменной которая истинна, если действие перехода совершается, и ложна в противном случае.

в) изъятие золота, если агент достиг ячейки, где оно находится. Это действие сопоставим с логической переменной

Теперь мы имеем достаточно полное представление о среде чудовища и цели агента и можем перейти к формальной постановке задачи.

2.4.1. Интервальная постановка задачи

В начальном состоянии, показанном на рис. 2.3, агент находится в ячейке и стоит лицом к ячейке (лицом на север). Это означает истинность формулы . Правило для принятия агентом решения о возможности совершения действия перехода в ячейку из ячейки можно представить импликацией (2. 1)

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

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

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

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

Постановка задачи теперь состоит из следующих шагов.

Задание интервальных форм, определяющих, начальные интервалы среды.

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

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

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

Задание интервальных форм, определяющих целевые интервалы.

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

Формулы, определяющие начальные интервалы. В нашем случае начальное состояние можно представить следующей конституентой, содержащей все 160 переменных и определяющей тем самым одно начальное состояние:

(см. скан)

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

Формулы, определяющие условия местонахождения объектов среды. Если в какой-либо ячейке не ощущается зловония, то в соседних ей ячейках чудовища нет. Точно так же, если в какой-либо ячейке нет сквозняка, то в соседних ячейках нет ям. Импликации, с помощью которых можно выразить эти знания, в общем случае имеют следующий вид.

Для крайних ячеек вследствие отсутствия части соседних правая часть подобных формул может не содержать каких-либо конъюнкций. Так, для эта формула примет вид

Для ячеек и имеем формулы

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

При формула (2.5) примет вид

Число таких формул равно 16.

Формулы, определяющие условия выполнения агентом действий. Для того чтобы достичь цели, агент должен совершать действия, которые бы привели его к этой цели. В случае среды кота, рассмотренной ранее, предполагалось, что кот может совершать одно из действий в любом состоянии и в любом порядке. Такое поведение агента в среде чудовища неприемлемо, поскольку среда небезопасна, и необходимо знать, в зависимости от обстановки, когда и какие действия можно совершать. Для среды чудовища были введены три действия: действие перехода в одну из соседних ячеек, действие по изъятию золота и действие поворота к ячейке, в которой нет ни чудовища, ни ямы. Агент может перейти в соседнюю ячейку,

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

Одна из конкретных импликаций этого типа для перехода была введена ранее (см. (2.1)). Число формул вида (2.6) равно 64. Соответственно, возможные изменения интервалов (состояний среды), осуществляемые в результате действия, связанного с переходом, задаются формулами

Формулы, определяющие условия выполнения действий по изъятию золота, имеют вид

и их число равно 16.

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

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

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

Если действие поворота выполняется в соответствии с формулой (2.10), то импликация, определяющая местоположение и ориентацию агента, будет следующая:

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

Агент может совершать действие поворота и против хода часовой стрелки в соответствии, например, с формулами типа

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

Формулы целевых интервалов. Ограничим решение задачи нахождением золота. Агент не знает, в какой ячейке находится золото. Только попав в нее, он по блеску может определить, что оно в ней находится. Поэтому стратегией агента является обследование всех ячеек, в которые он может попасть и не погибнуть. Если ему удастся, блуждая таким образом, добраться до ячейки , то он увидит блеск и обнаружит там золото. Будем полагать в настоящем примере, что целью агента является совершение действия по взятию золота, т.е. его цель есть а решением задачи должно быть нахождение последовательности действий (правил), в результате выполнения которых цель будет достигнута.

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

Например,

Правило, задающее условие совершения действия описывается следующей формулой:

2.4.2. Решение задачи

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

Начальный интервал задается формулой (2.3). Используя правило исключения конъюнкта, по этой формуле агент может заключить, что истинны формулы т.е.

Теперь агент может воспользоваться формулами (2.4) и правилом модус поненс:

заключая, что истинны формулы

Затем агент может вновь воспользоваться правилом исключения конъюнкта, получая в результате истинные формулы

которые означают, что чудовища и ям нет в ячейках, соседних ячейке .

Далее агент может воспользоваться первой формулой из числа формул (2.6) и правилом модус поненс:

заключая, что формула истинна и, следовательно, он может совершить действие перехода в ячейку . Воспользовавшись этим фактом, правилом модус поненс и первой формулой из (2.7), которая принимает следующий вид:

Очутившись в ячейке (2,1), агент ощущает сквозняк и отсутствие зловония на основании правил типа (2.14)

Так как зловония в ячейке нет истинна), агент, используя формулу типа (2.4)

и правила модус поненс и исключения конъюнкта, заключает, что чудовища нет в ячейке ( истинна). Агент ощущает сквозняк в ячейке ( истинна), поэтому, используя формулу типа (2.5)

правило модус поненс и простую резолюцию, заключает, что в ячейке , к которой он стоит лицом, имеется яма истинна). Отсюда на основании правил типа (2.11)

а затем правил (2.6), (2.7)

агент сначала совершает поворот в сторону ячейки , а затем и переходит в нее. В ячейке на основании формул (2.14)

он обнаруживает, что в ней нет ни зловония, ни сквозняка (истинны формулы -

Далее по формулам (2.4), правилам модус поненс и исключения конъюнкта он устанавливает, что чудовища и ямы в ячейке также нет (истинны формулы

После этого агент может воспользоваться одной из формул типа (2.6), одной из формул типа (2.7) и правилом модус поненс для перехода в ячейку :

В результате агент оказывается в ячейке (истинна и видит блеск золота (истинна на основании правила Используя формулу (2.8) и правило модус поненс, агент может сделать заключение о возможности совершения действия по изъятию золота из ячейки (2,3):

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