АГЕНТЫ, ОСНОВАННЫЕ НА ПРОПОЗИЦИОНАЛЬНОЙ ЛОГИКЕ
В данном разделе соберем воедино все, что было описано до сих пор, для того, чтобы приступить к созданию агентов, действующих с использованием пропозициональной логики. Здесь будут рассматриваться два вида агентов: во-первых, агенты, в которых применяются алгоритмы логического вывода и база знаний, подобные показанному в листинге 7.1 универсальному агенту, основанному на знаниях, и, во-вторых, агенты, которые вычисляют значения логических высказываний непосредственно с помощью логических схем. В этом разделе будет также продемонстрировано функционирование агентов обоих типов в мире вампуса, а также показано, что оба они страдают от серьезных недостатков.
Поиск ям и вампусов с помощью логического вывода
Начнем с описания агента, который рассуждает логически о том, где находятся
ямы, вампусы и безопасные квадраты. Агент начинает свою работу с базы знаний,
в которой описаны "законы" мира вампуса. Он знает, что квадрат [1,1] не содер-
жит яму или вампуса; это означает, что -лР1Л и Для каждого квадрата [х,у]
агенту известно высказывание с указанием того, как возникает ветерок:
Вх<у <=> (Рх,у+1 V Рх,у_1 V Рх+1,у V Рх-1,у) (7.1)
Для каждого квадрата [х, у] агенту известно высказывание с указанием того, как возникает неприятный запах:
Sx,y <=> (Wx.y+i v Wx,y-i v Wx+1,y v Wx-i,y) (7.2)
Наконец, он знает, что в мире вампуса существует точно один вампус. Соответствующее высказывание состоит из двух частей. Прежде всего необходимо указать, что имеется самое меньшее один вампус:
Wifi v Wit2 v ... v 3 v 4,4
Затем необходимо указать, что существует самое большее один вампус. Один из способов формулировки этого утверждения состоит в том, что при наличии любых двух квадратов один из них обязательно должен быть свободным от вампуса. При наличии п квадратов мы получаем п (л-1) /2 таких высказываний, которые подобны по форме высказыванию -iWltl v —iWli2. Таким образом, для мира с размерами 4x4 описание начинается с общего количества 155 высказываний, содержащих 64 различных символа.
Программа агента, приведенная в листинге 7.9, сообщает в свою базу знаний с
помощью операции Tell о каждом новом восприятии ветерка и неприятного запа-
ха. (Она также обновляет некоторые обычные программные переменные для слеже-
ния за тем, где находится агент и где он побывал; дополнительная информация об
этом приведена ниже.) Затем программа выбирает среди периферийных квадратов
(т.е. квадратов, являющихся соседними по отношению к тем, которые уже посетил
агент) такой квадрат, который должен быть проверен в следующую очередь. Агент
может доказать, что периферийный квадрат [i, j] безопасен, если из базы знаний
следует высказывание (-iPif j л ). На втором месте по своей привлекательно-
сти находится квадрат, который, возможно, является безопасным; таковым является квадрат, применительно к которому агент не может доказать, что в нем имеется яма или вампус, т.е квадрат, для которого из базы знаний не следует высказывание (Pi,j v Witj).
Листинг 7.9. Агент для мира вампуса, использующий пропозициональную логику для определения ям, вампусов и безопасных квадратов. Процедура Rout е-Problem формирует задачу поиска, решением которой является последовательность действий, ведущих от [х#у] до [i# j] и проходящих только через ранее посещенные квадраты
function PL-Wumpus-Agent(percept) returns действие action inputs: percept, список результатов восприятия в форме
[Stench,Breeze,Glitter] (["Неприятный запах", "Ветерок","Блеск"]) static: KB, база знаний, первоначально содержащая лишь определения "законов функционирования" мира вампуса х, у, orientation, позиция агента (первоначально 1,1) и его ориентация (первоначально Right - смотрит вправо)
visited, массив, показывающий, какие квадраты были посещены,
первоначально содержащий значения false action, последнее по времени действие агента, первоначально не определено
plan, намеченная последовательность действий, первоначально пустая
обновить значения х, у, orientation, visited
с учетом действия action if stench then Tell (KB, S.y) else Tell (KB, -iSx,y) if breeze then Tell (KB, B*,y) else TelKJCB, -тДс.у)
if glitter then action <— grab
else if plan не пуст then action <— Pop (plan)
else if для некоторого периферийного квадрата [i,j]
результат Ask (KB, (~iPi,j л —IL, j) ) имеет значение true or для некоторого периферийного квадрата [i,j] результат Ask(KB, (Pi.j v i,j)) имеет значение false then do plan
action <— Pop(plan) else action <— случайно выбранный шаг return action
Вычисление логического следствия в процедуре Ask может быть реализовано с использованием любого из методов, описанных выше в этой главе. Очевидно, что алгоритм TT-Entails? (см. листинг7.3) является практически не применимым, поскольку в нем приходится выполнять перебор 264 строк. Алгоритм DPLL (см. листинг 7.7) осуществляет требуемый логический вывод за несколько миллисекунд в основном благодаря использованию эвристики с распространением единичных выражений. Может также использоваться алгоритм WalkSAT с учетом обычных предостережений о его неполноте. В рассматриваемых экземплярах мира вампуса неудачи в поиске модели при использовании 10 ООО инверсий неизменно соответствуют невыполнимости, поэтому вероятность ошибок, вызванных неполнотой этого алгоритма, весьма мала.
В малом мире вампуса алгоритм PL-Wumpus-Agent действует весьма неплохо. Тем не менее некоторые особенности базы знаний агента остаются крайне неудовлетворительными. База знаний KB содержит "буквальные" высказывания в общей форме, приведенной в уравнениях 7.1 и 7.2, для каждого отдельного квадрата. Чем больше среда, тем крупнее должна быть такая начальная база знаний. Было бы гораздо лучше иметь только два высказывания, которые сообщают, из-за чего возникают ветерки и неприятные запахи в любых квадратах. Но такие выразительные возможности выходят за рамки пропозициональной логики. В следующей главе будет показан более выразительный логический язык, в котором можно легко представить подобные высказывания.