Лекции - Системы искусственного интеллекта
Подождите немного. Документ загружается.
Типы сред определяются посредством восприятия и реакции
агента. Восприятия агента позволяют ему получать сведения о
среде, реакции - воздействовать на среду. В то же время
среда существует независимо от агентов и одним из важнейших
понятий, связанных со средой, является её состояние.
Полагая, что среда состоит из множества объектов, каждый из
которых в принципе, может принимать бесконечное число
микросостояний (свойств, значений), состоянием среды
назовем любой набор всех этих микросостояний. Восприятие
агента содержит информацию (полную или неполную) о
состоянии среды. Понятие состояния среды будет далее широко
использоваться и уточняться.
Нельзя не отметить, что понятие состояния физической
системы, физического процесса не поддается общему
определению, так как для каждого конкретного процесса или
системы оно различно, а общие определения сводятся к
синонимам [2].
Агент состоит из знаний и решателя, который работает с
этими знаниями. Агент также способен воспринимать
информацию из внешней среды, в том числе и новые знания. Он
способен порождать внутри себя новые знания, используя уже
ему известные. Агент способен реагировать (воздействовать)
на внешнюю среду в результате рассуждений на основе всех
этих знаний. Мы будем рассматривать предмет искусственного
интеллекта в последующем как науку о создании агентов, а
под системами искусственного интеллекта будем понимать
сообщество агентов, способных решать интеллектуальные
задачи в средах.
Таким образом, наша главная цель - создание требуемого
агента. Спрашивается, с чего начинать процесс создания и
кто это будет делать? Кто будет формировать необходимые
каждому агенту правила? В принципе, поскольку эта задача
относится к интеллектуальным, таким существом может быть
другой агент. Получается, что это уже какой-то суперагент
или метаагент. А кто научит метаагента? Какой-то вдвойне
метаагент? А кто научит его? Если идти этим путем, то
перечень таких вопросов бесконечен. Чтобы выйти из этой
кажущейся неразрешимой ситуации, предполагается, что
создание агента любого типа осуществляется человеком, и он
всегда способен решать задачи суперагента любого уровня.
Процесс создания агента сам по себе неформален. Здесь
весьма важным представляется качество описания, которое
выражается в степени адекватности поведения получаемого
агента задуманному. Оно, качество описание, зависит от
учета создателем всех необходимых аспектов его будущего
11
поведения. Иначе говоря, создатель агента должен включить в
его описание все правила, необходимые для задуманного
поведения. Совокупность всех таких правил называют иногда
базой знаний агента.
В действительности эту базу знаний можно представить в
некотором формальном языке, в частности, языке логики
(понятие формального языка будет введено позднее). Пока мы
будем полагать, что таким языком является некоторое
подмножество естественного русского языка. В ответ на свое
восприятие агент с помощью логических рассуждений на основе
знаний, которые хранятся в базе знаний, способен
вырабатывать реакции. Механизм рассуждений зависит от типа
агента и от языка представления базы знаний. В случае
комбинационного агента эти рассуждения простые, для других
- более сложные, но в любом случае в основе рассуждения с
использованием базы знаний лежит логика. Именно поэтому
уделяется большое внимание логикам, специальным языкам или
исчислениям, создаваемых на их основе, и процедурам
рассуждениям.
12
4.ЛОГИЧЕСКИЕ РАССУЖДЕНИЯ
Рассуждением или умозаключением обычно называют ряд
мыслей, изложенных в логически последовательной форме.
Ранее было введено понятие состояния среды. Далее мы будем
изучать возможности агента находить интересующие его
состояния среды (целевые состояния), если он что-либо знает
о других её состояниях. Определение целевых состояний
осуществляется с помощью поиска или рассуждения в
пространстве состояний. Покажем, как рассуждения подобного
рода можно формализовать в языке логики высказываний и
затем её формально решить, пользуясь аппаратом логики
высказываний. Рассмотрим также, что такое стратегия решения
или поиска.
Рассуждения в пространстве состояний среды. В
коммунальной квартире две старушки занимают по комнате.
Комнаты находятся в общем коридоре, который имеет выход на
лестничную клетку. Одна из комнат расположена слева (левая
комната) от выхода, а другая - справа (правая комната). В
коридоре живет кот, которого обе старушки одинаково любят и
балуют, оставляя ему кусочки сыра. Каждая старушка кладет
кусочек сыра у двери своей комнаты. Кот отдыхает либо у
левой комнаты (слева), либо у правой (справа). Множество
всех состояний этой среды (среды кота) можно представить
таблицей, в столбцах которой для каждого состояния среды
указаны местонахождения кота (слева или справа), наличие
или отсутствие кусочка сыра (да или нет) у соответствующей
комнаты.
Состояние
1
b
означает, что кот находится около левой
комнаты и около обеих комнат лежит по кусочку сыра,
состояние
2
b
кот находится около правой комнаты и около
обеих комнат снова лежит по кусочку сыра и т. д. Кот может
совершать в один и тот же момент времени только одно из
следующих действий: переходить к дверям левой комнаты,
переходить к дверям правой комнаты и съедать кусочек сыра
около той комнаты, где он находится. Эти действия
обозначим:
1
с
Идти налево;
2
с
Идти направо;
3
с
Съесть сыр.
Если среда находится в одном из состояний,
перечисленных в таблице, и кот совершает какое-либо из
действий, то нетрудно определить, в какое состояние после
выполнения действия перейдет среда.
Таблица
Состояние Местонахождени
е
кота
Наличие сыра
Слева Справа
1
b
Слева Да Да
2
b
Справа Да Да
3
b
Слева Да Нет
4
b
Справа Да Нет
5
b
Слева Нет Да
6
b
Справа Нет Да
7
b
Слева Нет Нет
8
b
Справа Нет Нет
Будем полагать, что нам известно состояние, называемое
начальным, с которого могут начаться изменения среды при
действиях кота. Пусть, например, это будет состояние
1
b
.
Будем изображать состояние кружочками с обозначением
состояния внутри кружочка. Переход из одного состояния в
другое, которое происходит в результате действия, будем
изображать стрелкой, которая ведет в это другое состояние.
На рис. 1 изображены все переходы из состояния
1
b
в
результате действий
.,,
321
ccс
На рис. 2 показано дерево всех
дальнейших переходов, которое является продолжением
элементарного дерева на рис. 1. Построение каждой ветви
дерева прекращено на том состоянии, которое встречается
повторно на пути, ведущем в него из начального состояния.
Постановка задачи. Цель кота - не оставить ни одного
кусочка сыра, где бы он не находился. В терминах состояний
среды целью кота является перевод её с помощью своих
действий (реакций) в одно из состояний
7
b
и
.
8
b
Состояния,
в которые с помощью набора допустимых действий необходимо
перевести среду, называются целевыми. Процесс определения
этих состояний называют формулировкой цели. Будем полагать
в рамках нашего примера, что каждое восприятие совпадает с
одним из состояний. Задачей агента является нахождение
последовательности действий или восприятие-действие,
ведущих на дереве переходов из начального состояния в
целевые. Процесс нахождения этих последовательностей
называют поиском, выводом или рассуждением. Постановкой
задачи называют задание всех состояний и действий, которые
можно использовать для решения задачи, начального состояния
и целевых состояний, а также всех допустимых переходов
между состояниями при выполнении действий. Для среды кота
постановка задачи уже осуществлена. Все состояния, которые
могут быть использованы при решении задачи, перечислены в
14
b
1
b
2
b
1
b
5
Рис. 1.
с
1
с
2
с
3
таблице. Целевыми состояниями
являются состояния
.,
87
bb
Все
допустимые переходы между
состояниями показаны на рис. 2.
Из рисунка ясно, что решениями
задачи является
последовательность
,,,,
3
3
1
4
3
2
2
1
c
b
c
b
c
b
c
b
в
результате выполнения которой
агент (кот) переведет среду из
состояния
,
7
b
и
последовательность
,,,
3
6
2
5
3
1
c
b
c
b
c
b
в
результате выполнения которой среда окажется в состоянии
.
8
b
b
1
b
1
b
5
b
2
c
2
c
1
c
3
b
1
b
2
b
4
b
5
b
6
b
5
b
3
b
4
b
4
b
5
b
8
b
3
b
4
b
7
с
1
с
2
с
3
с
1
с
2
с
3
с
1
с
2
с
3
с
1
с
2
с
3
с
1
с
2
с
3
b
6
Рис. 2
Поиск решения. Решение задачи для среды кота
практически очевидно, когда построено дерево переходов
состояний среды, по которому легко проследить пути, ведущие
в целевые состояния из начального. В реальных задачах это
дерево может быть очень большим, вследствие чего
нецелесообразно использовать стратегию поиска, согласно
которой необходимо сначала получать дерево целиком. Вместо
15
этого используются другие более эффективные стратегии
поиска, которые будут изложены ниже. Однако, какая бы из
этих стратегий не применялась, элементарным шагом поиска
является переход из одного состояния среды в другое и
анализ состояния среды, в которое переход был осуществлен,
на принадлежность к числу целевых. Каждый допустимый
переход из состояния
i
b
после совершения действия
j
c
в
состояние
k
b
можно задавать с помощью правила перехода:
"Если среда находится в состоянии
i
b
и совершается действие
,
j
c
то она должна перейти в состояние
".
k
b
Совокупность правил подобного типа используется в
процессе поиска. Одной из очевидных, но чрезвычайно
неэкономных стратегий поиска, позволяющей найти все решения
для среды кота, может быть следующая.
1. Образовать множество
},{
1
bB
которое состоит из
одного начального состояния
.
1
b
2. Для каждого состояния множества
B
и каждого
действия
j
c
найти, согласно соответствующим правилам
перехода, все состояния
,
k
b
в которые переходит среда.
Совокупность всех таких состояний, за исключением тех,
которые уже встречались в ранее образованных множествах
,B
принять за новое множество
B
.
3. Проверить, нет ли среди элементов этого множества
целевых состояний. Если целевых состояний нет, то перейти к
п. 2. Если целевые состояния есть, то выписать в порядке
использования правил все последовательности действий,
которые привели к целевым состояниям, удалить эти состояния
из множества
B
и перейти к выполнению следующего пункта.
4. Проверить, все ли целевые состояния найдены. Если
найдены все, то прекратить поиск. Если не все, то перейти к
п. 2.
Проиллюстрируем на примере среды кота применение этой
стратегии. Правила перехода выписывать не будем, так как в
нашем распоряжении уже есть дерево переходов.
Итак, вначале
}.{
1
bB
После выполнения п. 2 имеем
совокупность состояний
.,,
521
bbb
В этой совокупности нет ни
одного целевого состояния, а состояние
1
b
уже встречалось.
Поэтому, согласно п. 3, принимаем
},{
52
bbB
и переходим к
выполнению п. 2. В результате получаем совокупность
состояний
,,,,,
65421
bbbbb
среди которых опять же нет целевых, а
521
,, bbb
уже встречались. Поэтому
},{
64
bbB
и снова
возвращаемся к п. 2. После очередного выполнения это пункта
имеем совокупность состояний
.,,,
6543
bbbb
Среди этих состояний
654
,, bbb
уже встречались. Поэтому
},{
53
bbB
и снова
возвращаемся к п. 2. После очередного выполнения этого
16
пункта имеем совокупность состояний
.,,,,
86543
bbbbb
Среди этих
состояний
654
,, bbb
уже встречались, а состояние
8
b
является
целевым. В это состояние ведет единственная
последовательность действий
.,,
323
ссс
Однако еще не все
целевые состояния найдены, а именно не найдено
.
7
b
Поэтому
в соответствии с п. 4 продолжим поиск, вновь переходя к п.2
с множеством
}.{
3
bB
В результате получим совокупность
состояний
,,,
743
bbb
среди которых
43
,bb
уже встречались, а
7
b
- целевое. Последовательностью действий, ведущих в
состояние
7
b
является
.,,,
3132
cссс
Итак, все целевые состояния
найдены, решение задачи в виде последовательности действий,
ведущих в эти состояния, получено. Поиск на этом
прекращается.
17
5.ЛОГИКА ВЫСКАЗЫВАНИЙ
Выше показано, что рассуждение агента (поиск решения
задачи) сводится к определению правил перехода в
соответствии с выбранной стратегией. Каждый шаг состоит в
проверке агентом истинности левой части правила (факта
нахождения среды в состоянии
i
b
и допустимости действия
j
c
) и, в случае её истинности, признания факта перехода из
состояния
i
b
в состояние
k
b
в результате действия
j
c
.
Естественно, нам хотелось бы иметь математический аппарат,
на основе которого можно осуществлять постановку и поиск
решения задачи формально, используя наилучшую стратегию
поиска. Логика высказывания - это первый шаг к созданию
такого аппарата.
Осуществить постановку задачи формально - значит, имея
некий формальный язык, выразить на нём все знания о среде,
необходимые для решения задачи. Формальный язык в
соответствии с современными представлениями требует
рассмотрения двух его неотъемлемых частей: синтаксиса и
семантики.
Синтаксис языка описывает допустимые в языке
предложения, состоящие из цепочек (последовательностей)
символов, принадлежащих определенному множеству,
называемому алфавитом. Синтаксис языка позволяет отличать
предложения, принадлежащие языку, от предложений, ему не
принадлежащих. Семантика языка определяет смысл этих
предложений, сопоставляя символы языка с объектами
реального мира, а предложения - отношения между объектами.
Без семантики предложения языка являются ничего не
значащими для агента цепочками символами. Семантика логики
высказываний позволяет подразделять все множества
допустимых предложений на истинные и ложные. Истинные - это
те предложения, которые соответствуют имеющим место фактам
или отношениям, а ложные - не имеющим. Решать задачу
формально - это значит иметь множество правил и стратегию
их использования, которые позволяют осуществить вывод одних
синтаксически правильных истинных предложений из других
синтаксически правильных истинных или предполагаемых
истинными.
Синтаксис логики высказываний. Синтаксис логики
высказывания прост и имеет прямые синтаксические и
семантические аналоги в естественных языках, что
чрезвычайно облегчает нам понимание логики высказываний.
Символами языка логики высказываний, составляющими её
алфавит, являются логические константы ИСТИНА и ЛОЖЬ,
сокращенно обозначаемые буквами И и Л, логические
переменные
,,,, zyx
обозначаемые строчными буквами
латинского алфавита, логические связки
(И),
(ИЛИ),
(НЕ),
(ЭКВИВАЛЕНТНО),
(ВЛЕЧЕТ) и круглые скобки.
Значениями логических переменных являются логические
константы. Предложения языка логики высказываний,
называемые также формулами или высказываниями, составляют в
соответствии со следующими правилами:
логические константы являются простыми предложениями;
логические переменные также простые предложения;
сложные предложения формулируются из простых с помощью
связок
(И),
(ИЛИ),
(НЕ),
(ЭКВИВАЛЕНТНО),
(ВЛЕЧЕТ);
простые и сложные предложения, заключенные или не
заключенные в скобки, являются предложениями языка логики
высказываний;
из предложений с помощью связок и скобок можно
образовать новые предложения языка логики высказываний;
связки имеют следующий порядок старшинства
,,,,,
т.е. связка
самая старшая, а связка
- самая младшая.
Формулы логики высказываний, составленные по этим
правилам, называют правильно построенными формулами или
сокращенно формулами.
Семантика логики высказываний. Семантику логики
высказываний можно пояснить смысловой интерпретацией её
предложений или формул, под которой обычно понимают процесс
установления соответствия между логическими переменными и
изменяющимися свойствами объектов среды и между значениями
переменных (константами) и конкретными значениями свойств
объектов. В примере со средой кота - это соответствие между
логической переменной
k
x
и свойствами кота находиться
слева или справа и значениями логической переменной
k
x
И и
k
x
Л, следовательно, одним из местонахождений кота (слева
или справа) и далее между отношениями свойств объектов и
формулами, истинное значение которых определяет наличие
отношения, а ложное - его отсутствие.
Иначе говоря, интерпретация определяет семантику формул
(предложений, высказываний) путем сопоставления переменных
в формулах со свойствами объектов среды, а отношений между
этими свойствами - с формулами. Это позволяет по значению
формул после подстановки вместо переменных конкретных
значений свойств судить о наличии или отсутствии у среды
тех или иных совокупных свойств или отношений. Если дана
какая-либо формула, то подстановка в формулу констант
19
вместо её переменных называется конкретизацией. Таким
образом конкретизация является результатом интерпретации.
Замечательным свойством логики высказываний является то,
что семантика её простейших формул, т. е. истинностные
значения (И или Л) близки к соответствующим высказываниям
на естественном языке при любой интерпретации.
Так, например, если формула включает только одну
связку, то её семантика очень близка к соответствующим
высказываниям в русском языке. Так семантика формул
,,, xyxyx
в которых встречаются соответственно связки
,,,
практически совпадает с отношениями, определяемыми
соответственно смыслом слов "И", "ИЛИ", "НЕ", употребляемых
в русском языке для выражения отношений между свойствами
объектов, обозначаемых переменными
,, yx
хотя некоторые
различия имеются. Например, формула
yx
имеет истинное
значение, если хотя бы одна переменная истинна, но она
истинна и при истинности обеих переменных. Говоря на
русском языке "
x
или
y
", обычно предполагаем, что это
предложение истинно, если истинна только одна переменная,
т.е. это предложение русского языка по смыслу ближе к
формуле логики высказываний
.yxyx
Еще больше различий между семантикой формулы
yx
в
логике высказываний и похожему на неё высказыванию на
русском языке "
x
влечет
y
". Первое различие состоит в
том, что в русском языке мы показываем, что предложение "
x
влечет
y
" истинно, если истинны
x
и
y
, т.е. предложение
русского языка по смыслу совпадает с формулой
,yx
в то
время как формула
yx
может быть истинной не только
тогда, когда истинны обе переменные
x
и
y
, но и когда обе
ложны или когда
x
ложна, а
y
истинна. Кроме того,
семантика формулы
yx
вообще не предполагает какой-либо
связи между переменными
x
и
y
. Чтобы не обсуждать в
дальнейшем подобные несоответствия, впредь будем полагать,
что, употребляя формулу
yx
, мы вкладываем в нее смысл,
вытекающий из следующего предложения: "Мы заявляем, что
истинность высказывания "
x
влечет
y
" означает, что
истинность
x
влечет истинность
y
, а больше мы ничего не
заявляем".
Истинность значения любой формулы, т.е. её семантику,
всегда можно задать таблицей, состоящей из двух частей: в
левой части таблицы перечислены все наборы значений
аргументов, а в правой соответствующие наборам значения
формулы. Задание таких таблиц для связок облегчается тем,
что значениями аргументов и формул являются только две
20