Лекции - Системы искусственного интеллекта
Подождите немного. Документ загружается.
7.РАССУЖДЕНИЯ В ТЕРМИНАХ ИНТЕРВАЛОВ
Каждый из нас с детства знаком с настольными играми.
Основным их элементом является игральная доска, которая
разбита на ячейки, соединенные тем или иным образом путями.
Играющие кидают кость и из той ячейки, где они находятся, в
зависимости от выпавшего числа очков переходят в ту или
иную ячейку. При этом можно попасть в "хорошую" ячейку,
которая расположена близко от целевой ячейки, но можно и в
"плохую", из которой бросавший кость может быть переведен
назад и окажется от цели дальше, чем был перед бросанием
кости. Добравшись до цели раньше других выигрывает. Спектр
таких игр велик: переходы из ячейки зависят от
встречающихся в ячейках различных препятствий и
противников, которые не только могут отбросить играющего
назад, но и вообще вывести его из игры, противники имеют
возможности сами перемещаться по ячейкам в ответ на ход
бросающего кости и т. д.
Рассмотрим простой пример среды такого типа, называемой
средой чудовища. Среда имеет число ячеек, равное 44,
расположенных по вертикали и горизонтали. Каждая внутренняя
ячейка имеет четыре соседних, крайние ячейки могут не иметь
соседних ячеек с одной или двух сторон. Агент, который
выступает в роли единственного играющего, может переходить
в одну из соседних ячеек. В одной из ячеек находится
чудовище. Чудовище издает зловоние, которое
распространяется на соседние ему ячейки. В одной из ячеек
лежит золото, которое блестит. Кроме того, в ячейках могут
быть бездонные ямы. В ячейках, соседних ячейками с ямами,
ощущается сквозняк. Задача агента, стартуя в ячейке (1,1),
добраться до ячейки с золотом, взять его и благополучно
вернуться назад.
Исходное состояние среды чудовища соответствует
рис...., где буквы в ячейках обозначают следующее: Ч -
чудовище, З - золото, С - сквозняк, Б - блеск, Я - яма, Н -
агент. Сопоставим каждую ячейку
),( ji
среды с шестью
логическими переменными
),,( jix
ч
),,( jix
з
),,( jix
с
),,( jix
б
),,( jix
я
).,( jix
н
Будем полагать, что значения этих переменных
истинно, если чудовище, зловоние, сквозняк, блеск, яма или
агент присутствуют в соответствующей ячейке, и ложно в
противном случае. Введем дополнительные логические
переменные, которые характеризуют ориентацию агента на
север, юг, восток и запад:
),,( jix
n
),,( jix
s
),,( jix
e
).,( jix
w
Истинное значение какого либо из них с индексом
),( ji
означает ориентацию агента, который находится в ячейке
),( ji
соответственно на север, юг, восток и запад; ложное
значение - отсутствие ориентации.
4 З С Я
3 Ч,З З,С,Б Я С
2 З С
1 Н С Я С
1 2 3 4
Естественно, такая интерпретация переменных означает,
что только одна из них может быть истинна. Понятно, что
суммарное число переменных равно 1016=160, и набор
значений всех переменных целиком задает значение среды
чудовища. Так, например, начальное состояние среды, которое
показано на рис...., определяется набором значений этих
переменных, в котором 17 переменных истинны:
),1,1(
н
x
),1,1(
n
x
),1,2(
с
x
),1,3(
я
x
),1,4(
с
x
),2,1(
з
x
),2,3(
с
x
),3,1(
ч
x
),3,1(
з
x
),3,2(
з
x
),3,2(
с
x
),3,2(
б
x
),3,3(
я
x
),3,4(
с
x
),4,1(
з
x
),3,4(
с
x
),4,4(
я
x
а
остальные ложны. Число таких наборов, обычно называемых
полными наборами значений, или полными состояниями среды,
астрономически велико и равно 2
160
. Конечно, далеко не во
всех полных состояниях может находиться среда вследствие
ограничений на значения каких-либо переменных в зависимости
от значений других. Например, как уже отмечалось, никакая
переменная из
),,( jix
n
),,( jix
s
),,( jix
l
),( jix
w
с одним и тем же
индексом
),( ji
никогда не может истинной, если истинна
какая-либо другая из этого множества. А значит, и среда не
может находиться в состоянии, где хотя бы две из них
одновременно истинны. Тем не менее, если рассуждать в
терминах состояний среды, то это число может быть слишком
велико даже с учетом указанных ограничений, а таблицу
истинности практически невозможно построить.
К счастью, в реальных задачах чаще всего, во-первых,
нет необходимости знать значения всех переменных, а во-
вторых, агент, зачастую, и не может их знать. В нашем
примере агент может воспринимать значения только тех
переменных, которые относятся к ячейке, в которой он
находится (т.е. имеет индекс, который совпадает с индексом
ячейки местонахождения агента). При этом восприятие агента
определяются следующими факторами.
В ячейке, где находится чудовище, и в соседних ей
ячейках агент ощущает зловоние чудовища.
В ячейках, соседних ячейке, в которой находится яма,
агент ощущает сквозняк.
32
В ячейке, где находится золото, агент видит яркий
блеск.
Агент всегда стоит лицом к одной из соседних ячеек и
может совершать одно из следующих действий:
а)поворот к ячейке, в которой нет ни чудовища, ни ямы.
Сопоставим это действие с переменной
,
0
z
которая истинна,
если действие поворота совершается, и ложна в противном
случае;
б)переход в соседнюю ячейку, к которой агент стоит
лицом. Сопоставим это действие с логической переменной
,
m
z
которая истинна, если действие перехода совершается, и
ложна в противном случае;
в)изъятие золота, если агент достиг ячейки, где оно
находится. Это действие сопоставим с логической переменной
з
z
.
Теперь мы имеем достаточно полное представление о среде
чудовища и цели агента и можем перейти к формальной
постановке задачи.
Интервальная постановка задачи. В начальном состоянии,
показанном на рис..., агент находится в ячейке (1,1) и
стоит лицом к ячейке (1,2) (лицом на север). Это означает
истинность формулы
).1,1()1,1(
n
xx
н
Правило для принятия
агентом решения о возможности совершения действия перехода
в ячейку (1,2) из ячейки (1,1) можно представить
импликацией
.),(),(),(),().(
mn
zxxxx 11 11 1111 17
сзн
В левую часть этой импликации, которая является в
данном случае конъюнкцией, а в общем случае любой формулой,
включены не все переменные, а только часть из них,
необходимая для принятия решения. В частности, в неё
включены переменная
),1,1(
н
x
которая характеризует
местоположение агента, переменная
),1,1(
n
x
которая
характеризует ориентацию агента,
),1,1(
з
x
которая
характеризует наличие или отсутствие зловония, и переменная
),1,1(
с
x
которая характеризует наличие или отсутствие
сквозняка. Обычно такие переменные называют существенными.
Это правило задает условие допустимости совершения
действия. Действие может быть и не совершенно. Но если оно
совершилось, то среда перейдет в какое-нибудь другое
состояние. Этот переход задается формулой
).,(),(),(),(),(),().( 212111 11 1111 27
нсзн nmn
xxzxxxx
Логически любая элементарная конъюнкция эквивалентна
дизъюнкции всех конституент (совершенной дизъюнктивной
33
нормальной форме), в которой существенные переменные имеют
одно и тоже значение, которое совпадает с их значением в
рассматриваемой конъюнкции, а несущественные переменные
пробегают все наборы значений. Множество всех полных
состояний среды, каждое из которых соответствует одной из
конституент совершенной нормальной формы, полученной по
данной элементарной конъюнкции, называется интервалом.
Используя интервалы, можно перейти от рассуждения в
терминах конституент, представляющих состояния среды, к
рассуждениям в терминах элементарных конъюнкций, которые
представляют интервалы среды. Формулы логики высказываний,
в которых используются элементарные конъюнкции,
представляющие интервалы, будем называть интервальными
формами.
Постановка задачи теперь состоит из следующих шагов.
Задание интервальных форм, которые определяют начальные
интервалы среды.
Задание в интервальной форме множества импликаций
(правил), которые определяют условия местонахождения тех
или иных объектов в ячейках среды в зависимости от
восприятий агента.
Задание в интервальной форме множества импликаций,
которые определяют допустимые переходы между ячейками при
совершении агентом действия перехода в зависимости от
восприятий.
Задание интервальных форм, определяющих целевые
интервалы.
Сформулируем теперь на основании сказанного задачу для
среды чудовища полностью.
Формулы, определяющие начальные интервалы. В нашем
случае начальное состояние можно представить следующей
конституентой, которая содержит все 160 переменных и
определяет тем самым одно начальное состояние:
),(),(),(),(
),(),(),(),(),(),(
11 11 11 11
1111 11 11 11 11
нябсзч
wesn
xxxx
xxxxxx
),(),(),(),(
),(),(),(),(),(),(
12 12 12 12
1212 12 12 12 12
нябсзч
wesn
xxxx
xxxxxx
),(),(),(),(
),(),(),(),(),(),(
13 13 13 13
13 13 13 13 13 13
нябсзч
wesn
xxxx
xxxxxx
),(),(),(),(
),(),(),(),(),(),(
14 14 14 14
14 14 14 14 14 14
нябсзч
wesn
xxxx
xxxxxx
),(),(),(),(
),(),(),(),(),(),(
21 21 21 21
21 21 21 21 21 21
нябсзч
wesn
xxxx
xxxxxx
),(),(),(),(
),(),(),(),(),(),(
22 22 22 22
22 22 22 22 22 22
нябсзч
wesn
xxxx
xxxxxx
),(),(),(),(
),(),(),(),(),(),(
23 23 23 23
23 23 2323 23 23
нябсзч
wesn
xxxx
xxxxxx
34
),(),(),(),(
),(),(),(),(),(),(
24 24 24 24
24 24 24 24 24 24
нябсзч
wesn
xxxx
xxxxxx
),(),(),(),(
),(),(),(),(),(),(
31 31 31 31
31 31 31 31 31 31
нябсзч
wesn
xxxx
xxxxxx
),(),(),(),(
),(),(),(),(),(),(
32 32 32 32
32 32 32 32 32 32
нябсзч
wesn
xxxx
xxxxxx
),(),(),(),(
),(),(),(),(),(),(
33 33 33 33
33 33 33 33 33 33
нябсзч
wesn
xxxx
xxxxxx
),(),(),(),(
),(),(),(),(),(),(
34 34 34 34
34 34 34 34 34 34
нябсзч
wesn
xxxx
xxxxxx
),(),(),(),(
),(),(),(),(),(),(
41 41 41 41
41 41 41 41 41 41
нябсзч
wesn
xxxx
xxxxxx
),(),(),(),(
),(),(),(),(),(),(
42 42 42 42
42 42 42 42 42 42
нябсзч
wesn
xxxx
xxxxxx
),(),(),(),(
),(),(),(),(),(),(
43 43 43 43
43 43 43 43 43 43
нябсзч
wesn
xxxx
xxxxxx
).,(),(),(),(
),(),(),(),(),(),(
44 44 43 44
44 44 44 44 44 44
нябсзч
wesn
xxxx
xxxxxx
Агент не знает всех значений переменных, входящих в эту
конституенту. Согласно его восприятию, он знает, что
находится в ячейке (1,1) и стоит лицом на север, а также не
ощущает в этой ячейке зловония и сквозняка. Таким образом,
начальная совокупность интервалов, определяемая восприятием
агента задается формулой
).,(),(),(),().( 11 11 1111 37
сзн
xxxx
n
Формулы, определяющие местонахождения объектов среды.
Если в какой-либо ячейке
),( ji
не ощущается зловония, то в
соседних ей ячейках чудовища нет. Точно так же, если в
какой-либо ячейке нет сквозняка, то в соседних ячейках нет
ям. Импликации, с помощью которых можно выразить эти знания
в общем случае имеют следующий вид
);,(
),(),(),(),(),().(
1
1 1 1 47
ч
ччччз
jix
jixjixjixjixjix
).1,(
)1,(),1(),1(),(),(
jix
jixjixjixjixjix
я
яяяяc
Для крайних ячеек вследствие отсутствия части соседних
правая часть подобных формул может не содержать каких-либо
конъюнкций. Так, для
1,1 ji
эта формула примет вид
).,(),(),(),( 21 12 11 11
чччз
xxxx
Для ячеек (1,2) и (2,1) имеем формулы
),3,1()1,1()2,2()2,1()2,1(
ччччз
xxxxx
).2,2()1,3()1,1()1,2()1,2(
ччччз
xxxxx
Понятно, что число формул (7.4) равно 32. Полезным
могут оказаться также знания о наличии чудовища или ямы в
ячейках, соседних ячейке
),,( ji
если в ней ощущается
35
зловоние или сквозняк соответственно. Импликации, с помощью
которых можно выразить эти знания, имеют следующий вид
);,(),(),(),(),(),().( 1 1 1 1 57
чччччз
jixjixjixjixjixjix
).1,()1,(),1(),1(),(),( jixjixjixjixjixjix
яяяяяc
При
2,1 ji
формула(7.5) примет вид
).1,2()3,1()1,1()2,2()2,1()2,1(
чччччз
xxxxxx
Число таких формул равно 16.
Формулы, определяющие условия выполнения агентом
действий. Для того чтобы достичь цели, агент должен
совершать действия, которые бы привели его к этой цели. В
случае среды кота, рассмотренной ранее, предполагалось, что
кот может совершать одно из действий в любом состоянии и в
любом порядке. Такое поведение агента в среде чудовища
неприемлемо, поскольку среда небезопасна, и необходимо
знать, в зависимости от обстановки, когда и какие действия
можно совершать. Для среды чудовища были введены три
действия: действие перехода в одну из соседних ячеек,
действие по изъятию золота и действие по повороту к ячейке,
в которой нет ни чудовища, ни ямы. Агент может перейти в
соседнюю ячейку, если там его не подстерегает опасность в
виде чудовища или ямы. Поэтому общий вид импликаций,
определяющих возможность совершения действия по переходу в
соседнюю ячейку, является следующим
,),(),(),(),().(
mn
zjixjixjixjix 1 1 67
ячн
,)1,()1,(),(),(
ms
zjixjixjixjix
ячн
,),1(),1(),(),(
me
zjixjixjixjix
ячн
.),1(),1(),(),(
mw
zjixjixjixjix
ячн
Число таких формул равно 64. Соответственно, возможные
изменения интервалов (состояний среды), которые
осуществляются в результате действия, связанного с
переходом, задаются формулами
),,(),(
),(),(),(),().(
11
1 1 77
н
ячн
jixjix
zjixjixjixjix
n
mn
),1,()1,(
)1,()1,(),(),(
jixjix
zjixjixjixjix
s
ms
н
ячн
),,1(),1(
),1(),1(),(),(
jixjix
zjixjixjixjix
e
me
н
ячн
).,1(),1(
),1(),1(),(),(
jixjix
zjixjixjixjix
w
mw
н
ячн
36
Формулы, которые определяют условия выполнения действий
по изъятию золота, имеют вид
збн
(7.8) zjixjix ),(),(
и их число равно 16.
Формулы, которые определяют условия возможного
выполнения действия поворота агента, введем исходя из
следующих соображений. Если агент стоит лицом к какой-либо
ячейке и в результате своих рассуждений пришел к выводу,
что в этой ячейке может быть чудовище или яма, то он
поворачивается к той ячейке, в которой нет ни ямы, ни
чудовища (предполагается, что такая ячейка существует).
Таким образом формулы, регламентирующие возможность
выполнения действия поворота направо, лицом к ячейке, в
которой нет ни чудовища, ни ямы, если агент перед этим
находился в ячейке
),( ji
и стоял лицом соответственно на
север, восток, юг и запад, и перед ним не находились
чудовища и яма, имеют вид
,),(),(),(),(),().(
on
zjixjixjixjixjix 1 1 1 97
яччн
,),1(),1()1,(),(),(
on
zjixjixjixjixjix
ячян
,)1,()1,(),1(),(),(
oe
zjixjixjixjixjix
ячян
,),1(),1()1,(),(),(
os
zjixjixjixjixjix
яччн
,)1,()1,(),1(),(),(
ow
zjixjixjixjixjix
яччн
,)1,()1,(),1(),(),(
ow
zjixjixjixjixjix
ячян
Если же агент находится в ячейке
),( ji
, а чудовище в
ячейках
)1,( ji
или
),,1( ji
а в ячейке
)1,( ji
нет ни
чудовища, ни ямы, то можно воспользоваться формулой типа
.),(),(
)),(),(),(),(
o
n
zjixjix
jixjixjixjix
11
1 1( (7.10)
яч
ччн
Формулы, определяющие множество допустимых переходов.
Агент может перейти из ячейки
),( ji
в соседние ячейки
),1,( ji
),1,( ji
),,1( ji
),1( ji
в результате выполнения
действия
.
m
z
При повороте он остается в той же ячейке.
Ориентация его при этом меняется. Поэтому импликациями,
определяющими местоположение и ориентацию агента после
выполнения действия поворота в соответствии с формулами
(7.9), будут следующие
),,(),(),(
),(),(),(),(
jixjixzjix
jixjixjixjix
eo
n
ня
ччн
1
1 1 (7.11)
),,(),(),1(
),1()1,(),(),(
jixjixzjix
jixjixjixjix
eo
n
ня
чян
),,(),()1,(
)1,(),1(),(),(
jixjixzjix
jixjixjixjix
so
e
ня
ччн
),,(),()1,(
)1,(),1(),(),(
jixjixzjix
jixjixjixjix
so
e
ня
чzн
37
),,(),(),1(
),1()1,(),(),(
jixjixzjix
jixjixjixjix
wo
s
ня
ччн
),,(),(),1(
),1()1,(),(),(
jixjixzjix
jixjixjixjix
wo
s
ня
чян
),,(),()1,(
)1,(),1(),(),(
jixjixzjix
jixjixjixjix
no
w
ня
ччн
).,(),()1,(
)1,(),1(),(),(
jixjixzjix
jixjixjixjix
no
w
ня
чян
Если действие поворота выполняется в соответствии с
формулой (7.10), то импликация, определяющая местоположение
и ориентацию агента, будет следующая
).,(),(),(),(
)),(),(),(),(
jixjixzjixjix
jixjixjixjix
so
n
няч
ччн
1 1
1 1( (7.12)
Формулы (7.11) и (7.12) предопределяют результат
выполнения действия поворота по ходу часовой стрелки при
наличии чудовища или ямы в ячейке, к которой агент стоит
лицом.
Агент может совершать действие поворота и против
часовой стрелки в соответствии, например, с формулами типа
),,(),(),(
),(),(),(),(
jixjixzjix
jixjixjixjix
eo
s
ня
ччн
1
1 1 (7.13)
).,(),(),1(
),1()1,(),(),(
jixjixzjix
jixjixjixjix
eo
s
ня
чян
В том случае, когда ячейка не имеет какой-либо
соседней, соответствующие условия и результат поворота
модифицируются таким образом, чтобы учесть отсутствие
соседних ячеек.
Формулы целевых интервалов. Ограничим решение задачи
нахождением золота. Агент не знает, в какой ячейке
находится золото. Только попав в неё, он по блеску может
определить, что оно в ней находится. Поэтому стратегией
агента является обследование всех ячеек, в которые он может
попасть и не погибнуть. Если ему удастся, блуждая таким
образом добраться до ячейки (2,3), то он увидит блеск и
обнаружит там золото. Будем полагать в настоящем примере,
что целью агента является совершение действия по взятию
золота, т.е. его цель
,
з
z
а решением задачи должно быть
нахождение последовательности действий (правил) в
результате выполнения которых цель будет достигнута.
С учетом того, что агент способен к восприятию
сквозняка или зловония только в ячейке, в которой он
находится, а среда чудовища является статической
(местоположение чудовища и ям не изменяется), то для
конкретных значений
i
и
j
в соответствии с рис. , по мере
необходимости, будем также использовать формулы вида
),,( jixx
зн
),,( jixx
cн
),,( jixx
зн
).,( jixx
зн
Например,
38
),,(),(),,(),(),,(),().( 1212 21 21 2121 147
снснзн
xxxxxx
),2,1()2,2(),2,1()1,2(
знзн
xxxx
).3,2()3,2(),2,2()2,2(
бнcн
xxxx
Правило, которое задает условие совершения действия
,
з
z
описывается формулой
.),(),().(
ззн
157 zjixjix
Решение задачи. Рассмотрим вывод, который приводит к
решению задачи нахождения агентом золота в среде чудовища.
Начальный интервал задается формулой (7.3). Запишем эту
формулу
).1,1()1,1()1,1()1,1(
сзн
xxxx
n
Используя правило исключения конъюнкта, по этой формуле
агент может заключить, что истинны формулы
н
),1,1(),1,1(
n
xx
,
сз
)1,1(),1,1( xx
т.е.
),1,1()1,1()1,1()1,1()1,1(
нсзн
xxxxx
n
),1,1()1,1()1,1()1,1()1,1(
nn
xxxxx
сзн
),1,1()1,1()1,1()1,1()1,1(
зсзн
xxxxx
n
.)1,1()1,1()1,1()1,1()1,1(
ссзн
xxxxx
n
Теперь агент может воспользоваться формулами (7.4),
которые определяют условия местонахождения объектов среды и
правилом модус поненс. Напомним их
),1,()1,(
),1(),1(),(),(
jixjix
jixjixjixjix
чч
чччз
).1,()1,(
),1(),1(),(),(
jixjix
jixjixjixjix
яя
яяяс
Модус поненс. Из истинности условия импликации и
истинности самой импликации следует истинность следствия
импликации
.,
Результат применения этих выражений
),2,1()1,2()1,1(
)2,1()1,2()1,1()1,1(),1,1(
ччч
чччзз
xxx
xxxxx
),2,1()1,2()1,1(
)2,1()1,2()1,1()1,1(),1,1(
яяя
яяясс
xxx
xxxxx
заключаем, что истинны формулы
),2,1()1,2()1,1(
ччч
xxx
).2,1()1,2()1,1(
яяя
xxx
39
Затем агент может воспользоваться правилом исключения
конъюнкта, получая в результате истинные формулы
),2,1(),1,2(),1,1(
ччч
xxx
),2,1()1,2()1,1(
яяя
xxx
которые означают, что чудовища и ям нет в ячейках, соседних
ячейке (1,1).
Далее агент может воспользоваться первой формулой из
числа (7.6) и правилом модус поненс
),2,1()2,1()1,1()1,1(
ячн
xxxx
n
)2,1()1,1()1,1(
чн
xxx
n
,)2,1(
m
zx
я
заключая, что формула
m
z
истинная и, следовательно, он
может совершить действие перехода в ячейку (1,2).
Воспользовавшись этим фактом, правилом модус поненс и
первой формулой из (7.7), которая принимает следующий вид
),2,1()2,1()2,1()2,1()1,1()1,1(
nmn
xxzxxxx
нячн
агент может установить истинность формулы
),2,1()2,1(
n
xx
н
которая означает, что он после совершения действия перехода
находится в ячейке (1,2) лицом на север к ячейке (1.3).
Теперь процесс исследования соседних ячеек на существующие
там опасности повторяется. В ячейке (1,2) агент ощущает
зловоние (истинна формула
),2,1(
з
x
и не ощущает сквозняка
(истинна формула
)2,1(
с
x
).
Применяя формулы (7.4), правило модус поненс и правило
исключения, агент устанавливает, что в ячейке (2,2) нет ямы
(истинна
)2,2(
я
x
)
).3,1()2,2()1,1()2,1(),2,1(
яяясс
xxxxx
Используя формулы (7.5) и правило модус поненс
)3,1()2,2()1,1()3,1()2,2()1,1()2,1(),2,1(
ччччччзз
xxxxxxxx
агент получает истинную формулу
),3,1()2,2()1,1(
ччч
xxx
которая означает, что чудовище может находиться в одной из
ячеек (1,1), (2,2) или (1,3). Но согласно начальным
условиям задачи, чудовища и ям нет в ячейке (1,1), т.е.
истинны формулы
).1,1(),1,1(
яч
xx
Следовательно, чудовище может находиться в одной из
ячеек (2,2) или (1,3), что формально выводится с
использованием правила простой резолюции
).3,1()2,2()3,1()2,2()1,1(),1,1(
чччччч
xxxxxx
40