Лекции - Системы искусственного интеллекта
Подождите немного. Документ загружается.
находится(Зловоние,
ji ,1
);
*
).( 1810
находится (Зловоние,
ji,
)
находится (Чудовище,
ji,
)
находится (Чудовище,
1ji,
)
находится (Чудовище,
1ji,
)
находится (Чудовище,
ji ,1
)
находится(Чудовище,
ji ,1
);
*
).( 1910
находится (Сквозняк,
ji,
)
находится (Яма,
ji,
) находится (Яма,
1ji,
)
находится (Яма,
1ji,
) находится (Яма,
ji ,1
)
находится(Яма,
ji ,1
);
С помощью преобразования
)()(
)(
,
удаления квантора существования и правила исключения
конъюнкта получаем следующие формулы:
*
).( 2010
находится (Агент,
ji,
) ориентация
),( 1ji
находится (Чудовище,
1ji,
)
находится (Яма,
1ji,
) перейти
),( 1ji
;
находится (Агент,
ji,
) ориентация
),( 1ji
находится (Чудовище,
1ji,
)
находится (Яма,
1ji,
)
находится (Агент,
1ji,
);
находится (Агент,
ji,
) ориентация
),( 1ji
находится (Чудовище,
1ji,
)
находится (Яма,
1ji,
)
81
ориентация (
2ji,
).
Число подформул в системе формул
*
).( 2010
совпадает с
числом литералов вследствие импликативной формулы
).( 2010
и
различаются они только последним литералом. Поэтому для
остальных формул
*
).( 2110
-
*
).( 2310
выпишем только первую
подформулу
*
).( 2110
находится (Агент,
ji,
) ориентация
),( 1ji
находится (Чудовище,
1ji,
)
находится (Яма,
1ji,
) перейти
),( 1ji
;
*
).( 2210
находится (Агент,
ji,
) ориентация
),( ji 1
находится (Чудовище,
),( ji 1
)
находится (Яма,
),( ji 1
) перейти
),( ji 1
;
*
).( 2310
находится (Агент,
ji,
) ориентация
),( ji 1
находится (Чудовище,
ji ,1
)
находится (Яма,
ji ,1
) перейти
),( ji 1
;
*
).( 2410
находится (Агент,
ji,
)
находится (Блеск,
ji,
)
взять
),( ji
.
Подформулы системы формул
*
).( 2510
-
*
).( 3210
получаются
аналогично, но их ещё больше. Выпишем, как и в предыдущем
случае, только по одной (первой) подформуле:
*
).( 2510
находится (Агент,
ji,
) ориентация
),( 1ji
находится (Чудовище,
1ji,
)
повернуться_направо
),( ji
;
*
).( 2610
находится (Агент,
ji,
) ориентация
),( ji 1
находится (Чудовище,
ji ,1
)
повернуться_направо
),( ji
;
*
).( 2710
находится (Агент,
ji,
) ориентация
),( 1ji
находится (Чудовище,
1ji,
)
повернуться_направо
),( ji
;
*
).( 2810
находится (Агент,
ji,
) ориентация
),( ji 1
находится (Чудовище,
ji ,1
)
82
повернуться_направо
),( ji
;
*
).( 2910
находится (Агент,
ji,
) ориентация
),( 1ji
находится (Чудовище,
1ji,
)
повернуться_налево
),( ji
;
*
).( 3010
находится (Агент,
ji,
) ориентация
),( ji 1
находится (Чудовище,
ji ,1
)
повернуться_налево
),( ji
;
*
).( 3110
находится (Агент,
ji,
) ориентация
),( 1ji
находится (Чудовище,
1ji,
)
повернуться_налево
),( ji
;
*
).( 3210
находится (Агент,
ji,
) ориентация
),( 1ji
находится (Чудовище,
1ji,
)
повернуться_налево
),( ji
.
Применение обобщенного правила модус поненс вследствие
того, что в нём используются не отдельные атомы, а их
конъюнкции, делает вывод боле эффективным. Это объясняется
тем, что подставнока одних и тех же констант осуществляется
сразу для совокупности атомов, входящих в конъюнцию левой
части импликации и, если необходимо, то правой.
83
11.ПРЯМОЙ И ОБРАТНЫЙ ВЫВОД
Наиболее распространенными являются два типа: прямой и
обратный. До сих пор как ранее, так в примерах со средой
чудовища использовался прямой вывод. Будем полагать, что
все формулы, входящие в постановку задачи, образуют
некоторую начальную базу знаний.
Идея прямого вывода основа на следующих шагах. На
первом шаге подбирается правило вывода, условие которого
можно образовать из формул начальной базы знаний с
использованием, если это необходимо, унификации. Обычно
начинается всё с формул, которые представляют знания о
начальном состоянии среды. По правилу вывода получаются
новые истинные формулы, которые являются его
унифицированным следствием. Эти формулы помещаются в
начальную базу знаний, в результате чего она превращается в
другую базу знаний, из неё извлекаются новые формулы, и всё
повторяется сначала до тех пор, пока на очередном шаге
унифицированное следствие не совпадёт с целевой функцией.
Таким образом, в процессе прямого вывода на каждом его шаге
база знаний пополняется выведенными истинными формулами.
В обратном выводе всё делается наоборот. На первом шаге
обратного вывода подбирается правило вывода, следствием
которого является целевая формула, а условие может быть
образовано из формул начальной базы знаний, с
использованием, если это необходимо, унификации.
Унифицированные формулы, которые входят в условие,
принимаются за новые целевые формулы (обычно называемые
подцелевыми формулами) и всё повторяется сначала, но уже
для каждой из них. И так до тех пор, пока все
унифицированные подцелевые формулы не окажутся аксиомами,
входящими в начальную базу знаний. При выводе на основе
использования обобщенного правила модус поненс, унификации
и хорновских формул используется только один тип правила,
поэтому нет необходимости осуществлять выбор подходящего
правила вывода. Это типизирует процедуру прямого и
обратного вывода, превращая их в итеративную процедуру
выполнения однотипных шагов. Рассмотрим прямой и обратный
вывод на простых примерах из среды кубиков.
Постановка задачи в среде кубиков. Представим формулы,
которые определяют начальные знания агента. Имеем среду,
которая из стола и кубиков на нём. Каждый из кубиков может
лежать либо непосредственно на столе, либо на одном из
других кубиков, образуя с кубиками, лежащими под ним,
столбик. Столбики могут быть любой высоты. Пусть начальное
состояние среды кубиков следующее: кубики
С
и
B
лежат на
столе, кубик
A
лежит на кубике
C
, кубик
D
на кубике
B
(рис. 11.1).
Рис. 11.1. Начальное и целевое состояния среды кубиков
Начальное состояние среды кубиков можно описать
следующими атомами:
).( 111
на
),( CA
,
).( 211
на
,(C
Стол),
).( 311
на
),( BD
,
).( 411
на
,(B
Стол),
).( 511
свободен
)(A
,
).( 611
свободен
)(D
.
Атомы на
),( CA
, на
,(C
Стол), на
),( BD
, на
,(B
Стол)
описывают положение кубиков относительно друг друга, а
атомы свободен
)(A
, свободен
)(D
указывают, что на кубиках
)(A
и
)(B
ничего не лежит.
Формулы, которые определяют условия выполнения
действий. Действия, которые можно совершить в среде кубиков
– это перемещать один кубик, на котором ничего не лежит, на
стол или другой кубик, если он свободен от кубиков сверху.
Для обозначения этих действий введём атомы переместить
),( yx
и переместить
x(
, Стол
)
. Тогда для нашего примера
достаточно двух формул, определяющих условия выполнения
действий:
A
C
D
B
A
C
D
B
85
).( 711
на
),( yx
свободен
)(x
переместить
x(
, Стол
)
,
).( 811
на
x(
, Стол
)
свободен
)(x
свободен
)(z
переместить
),( zx
.
Формулы, определяющие условия перехода состояний среды:
).( 911
на
),( yx
свободен
)(x
переместить
x(
,Стол
)
на
x(
, Стол
)
,
).( 1011
на
),( yx
свободен
)(x
переместить
x(
,Стол
)
свободен
)(y
,
).( 1111
на
),( yx
свободен
)(x
свободен
)(z
переместить
),( zx
на
),( zx
,
).( 1211
на
),( yx
свободен
)(x
свободен
)(z
переместить
),( zx
свободен
)(y
.
Целевая формула. В соответствии с рис. 11.2 целевой
будет следующая формула:
).( 1311
на
),( BA
на
B(
, Стол) на
C(
, Стол)
на
D(
, Стол).
Прямой вывод. Начнем с формулы (11.7), унифицируя
которую получим следующие формулы:
).( 1411
на
),( CA
свободен
)(A
переместить
A(
, Стол
)
).( 1511
на
),( BD
свободен
)(D
переместить
D(
, Стол
)
.
На основании обобщенного правила модус поненс и формул
(11.1), (11.5), (11.3), (11.6), (11.14), (11.15) делаем
заключение о возможности выполнения действия по перемещению
кубиков
A
и
D
на стол: истинны атомы переместить
A(
,
Стол
)
, переместить
D(
, Стол
)
. Эти атомы помещаются в
исходную базу знаний. Далее можно воспользоваться формулами
(11.9), (11.10), унифицируя которые получим формулы
).( 1611
на
),( CA
свободен
)(A
переместить
A(
, Стол
)
на
A(
, Стол
)
,
).( 1711
на
),( CA
свободен
)(A
переместить
A(
, Стол
)
свободен
)(С
,
).( 1811
на
),( BD
свободен
)(D
переместить
D(
, Стол
)
на
D(
, Стол
)
,
).( 1911
на
),( BD
свободен
)(D
переместить
D(
,Стол
)
свободен
)(D
.
86
Рис. 11.2. Граф прямого вывода в среде кубиков
В результате кубики
A
и
D
оказались на столе. Кубики
C
и
B
никуда не перемещались и, согласно начальному
состоянию, остались на столе. Используя формулу (11.8)
получим унифицированную формулу
).( 2011
на
A(
, Стол
)
свободен
)(A
свободен
)(B
переместить
),( BA
.
Наконец, воспользовавшись формулой (11.9), получим
унифицированную формулу
на (A,B) на (B,Стол) (C,Стол)
(D,Стол)
на
(A,B)
на (B,Стол)
на (С,Стол)
на (D,Стол)
на (D,B) свободен (D) переместить (D,Стол)
свободен (A)
на (A,С)
свободен (D)
на (D,B)
на (A,B) свободен (A) свободен (B) переместить (A,B)
на (A,С) свободен (A)
на (A,Стол) свободен (A) свободен (B)
свободен (B)
свободен (C)
на (A,Стол)
на (A,С) свободен (A) переместить (A,
Стол)
переместить (A, Стол)
переместить (D, Стол)
переместить (D, Стол)
на (D,B) свободен (D)
переместить (A,B)
(D,Стол)
87
).( 2111
на
A(
, Стол
)
свободен
)(A
свободен
)(B
переместить
),( BA
на
),( BA
.
Таким образом, имеем истинные атомы на
),( BA
, на
B(
,
Стол), на
C(
, Стол), на
D(
, Стол). Согласно правилу
введения конъюнкции, делаем заключение об истинности
целевой формулы на
),( BA
B(
, Стол) на
C(
, Стол) на
D(
, Стол). На этом прямой вывод завершён. На рис. 11.2
показан граф вывода указанной целевой формулы. В процессе
прямого вывода база знаний разрастается, в неё заносятся
вновь выводимые формулы. Некоторые из них могут оказаться
ненужными для вывода целевой формулы. Таких "лишних" формул
может быть достаточно много. Например, на рис. 11.2
ненужной является формула свободен
)(С
.
Обратный вывод. Обратный вывод начинается с целевой
формулы на
),( BA
B(
, Стол) на
C(
, Стол) на
D(
,
Стол). Для нашего примера его можно проследить по тому же
графу на рис. 11.2. Только в отличие от прямого вывода,
который осуществлялся в направлении стрелок, обратный вывод
осуществляется против направления стрелок. Кроме того,
ненужных формул не выводится, что делает его в ряде случаев
более эффективным, особенно, если для вывода целевых формул
достаточно незначительной части базы знаний.
Здесь рассмотрены только принципы прямого и обратного
вывода. Во всех случаях исходной для вывода является
некоторая начальная база знаний. Для того чтобы иметь
возможность решения реальных задач на основе использования
исчисления, необходимо иметь ответ на ряд очень важных
вопросов.
Первая группа вопросов связана с понятием полноты
исчисления. Если все общезначимые формулы выводятся в
данном исчислении и только они, то его называют полным. В
противном случае исчисление называют неполным. Если в нашем
распоряжении (распоряжении агента) имеется некоторое
исчисление, то как определить, является ли оно полным?
Если исчисление является полным, то какая стратегия
вывода обеспечивает вывод любой общезначимой формулы этого
исчисления? Стратегию, которая обеспечивает вывод всех
общезначимых формул данного исчисления и только их,
называют полной. Если полная стратегия вывода существует и
она нам известна, но данная формула не выводима из
начальной базы знаний, то можно ли узнать это без вывода?
Другой класс вопросов, важных для практического
использования исчислений, связан с понятиями их
противоречивости и непротиворечивости. Исчисление называют
непротиворечивым, если не существует формулы, выводимой в
88
этом исчислении вместе со своим отрицанием. В противном
случае исчисление называют противоречивым. Из практических
соображений нас интересуют непротиворечивые исчисления.
Исчисление нам необходимо для того, чтобы осуществлять
вывод для достижения определенной цели. Если же для одного
и того исчисления существует некий вывод, который позволяет
достичь цели, и ВТО же самое время для этого же исчисления
существует вывод, который свидетельствует о том, что цель
не достижима (достижимо её опровержение), то такое
исчисление скорее всего неадекватно отражает свойства
среды, в которой оно интерпретируется. Главный вопрос,
который связан с непротиворечивостью исчислений звучит так:
если данное исчисление противоречиво вследствие того, что в
нём выводится некоторая формула и отрицание этой формулы,
то можно ли обнаружить этот факт без вывода этих двух
формул?
Прежде, чем переходить к ответу на перечисленные выше
вопросы, ответим на более простой. Если формула выводима в
каком-либо исчислении (не обязательно полном), то выводима
ли она при использовании той же системы аксиом и
единственного правила вывода – обобщенного правила модус
поненс? Вернемся к примеру со средой кубика.
Предположим, что в начальной базе знаний имеются
аксиомы
свободен
)(B
,
свободен
)(B
переместить
B(
, Стол
)
,
переместить
B(
, Стол
)
на
B(
, Стол
)
.
Пусть целевой формулой является формула на
B(
, Стол
)
.
С помощью обобщенного правила модус поненс сначала можно
вывести формулу переместить
),( BA
, а затем формулу на
B(
,
Стол
)
.
Если базе данных имеются аксиомы
свободен
)(B
,
свободен
)(B
освободить_и_переместить
B(
, Стол
)
,
освободить_и_переместить
B(
, Стол
)
на
B(
, Стол
)
,
то формулу на
B(
, Стол
)
, несмотря на то, что она выводима
с использованием обычного правила модус поненс, нельзя
вывести с помощью обобщенного правила модус поненс,
поскольку формулу свободен
)(B
освободить_и_переместить
B(
, Стол
)
невозможно
преобразовать в хорновскую формулу. Таким образом,
существуют исчисления, для которых не все общезначимые
89
формулы можно вывести с помощью только обобщенного правила
модус поненс. Перейдём к ответу на остальные вопросы.
90