Главная arrow Знания и рассуждения arrow Агенты пропозициональной логике
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Агенты пропозициональной логике Печать

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

 

Поиск ям и вампусов с помощью логического вывода

Начнем с описания агента, который рассуждает логически о том, где находятся ямы, вампусы и безопасные квадраты. Агент начинает свою работу с базы знаний, в которой описаны "законы" мира вампуса. Он знает, что квадрат [1,1] не содержит яму или вампуса; это означает, что ¬P1,1 и ¬W1,1. Для каждого квадрата [х, у] агенту известно высказывание с указанием того, как возникает ветерок:

Bx,y <=> (Px, y+1 v Px, y-1 v Px+1, y v Px-1,y)

Для каждого квадрата [х, у] агенту известно высказывание с указанием того, как возникает неприятный запах:

Sx,y <=> (Wx, y+1 v Wx, y-1 v Wx-1, y)

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

W1,1 v W1,2 v v W4,3 v W4,4

Затем необходимо указать, что существует самое большее один вампус. Один из способов формулировки этого утверждения состоит в том, что при наличии любых двух квадратов один из них обязательно должен быть свободным от вампуса. При наличии n квадратов мы получаем n(n-1) /2 таких высказываний, которые подобны по форме высказыванию ¬W1,1 v ¬W1,2 Таким образом, для мира с размерами 4x4 описание начинается с общего количества 155 высказываний, содержащих 64 различных символа.

Программа агента, приведенная в листинге, сообщает в свою базу знаний с помощью операции Tell о каждом новом восприятии ветерка и неприятного запаха. (Она также обновляет некоторые обычные программные переменные для слежения за тем, где находится агент и где он побывал; дополнительная информация об этом приведена ниже.) Затем программа выбирает среди периферийных квадратов (т.е. квадратов, являющихся соседними по отношению к тем, которые уже посетил агент) такой квадрат, который должен быть проверен в следующую очередь. Агент может доказать, что периферийный квадрат [I,j] безопасен, если из базы знаний следует высказывание (¬Pi,j ^ ¬Wi,j). На втором месте по своей привлекательности находится квадрат, который, возможно, является безопасным; таковым является квадрат, применительно к которому агент не может доказать, что в нем имеется яма или вампус, т.е квадрат, для которого из базы знаний не следует высказывание (Pi,j v Wi,j).

Агент для мира вампуса, использующий пропозициональную логику для определения ям, вампусов и безопасных квадратов. Процедура Route-Problem формирует задачу поиска, решением которой является последовательность действий, ведущих от [x, y] до [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, -iS>c,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, (—iPifj л -iWij)) имеет значение true or

  для некоторого периферийного квадрата [i,j] результат

  Ask(KB, (Pi,j v ^i,j)) имеет значение false then do

  plan <— A*-Graph-Search (Route-Problem( [x,y] , orientation,

  [i,j], visited))

  action <— Pop(plan)

  else action <— случайно выбранный шаг

return action

 

Вычисление логического следствия в процедуре Ask может быть реализовано с использованием любого из методов, описанных выше в этой главе. Очевидно, что алгоритм TT-Entails? является практически не применимым, поскольку в нем приходится выполнять перебор 264 строк. Алгоритм DPLL осуществляет требуемый логический вывод за несколько миллисекунд в основном благодаря использованию эвристики с распространением единичных выражений. Может также использоваться алгоритм Walks AT с учетом обычных предостережений о его неполноте. В рассматриваемых экземплярах мира вампуса неудачи в поиске модели при использовании 10 000 инверсий неизменно соответствуют невыполнимости, поэтому вероятность ошибок, вызванных неполнотой этого алгоритма, весьма мала.

В малом мире вампуса алгоритм PL-Wumpus-Agent действует весьма неплохо. Тем не менее некоторые особенности базы знаний агента остаются крайне неудовлетворительными. База знаний KB содержит "буквальные" высказывания в общей форме, для каждого отдельного квадрата. Чем больше среда, тем крупнее должна быть такая начальная база знаний. Было бы гораздо лучше иметь только два высказывания, которые сообщают, из-за чего возникают ветерки и неприятные запахи в любых квадратах. Но такие выразительные возможности выходят за рамки пропозициональной логики. В следующей главе будет показан более выразительный логический язык, в котором можно легко представить подобные высказывания.

 

Слежение за местонахождением и ориентацией

Программа агента, приведенная в листинге, немного "жульничает", поскольку в ней слежение за местонахождением осуществляется за пределами базы знаний, тогда как вместо этого следует использовать логические рассуждения13. Для выполнения этих функций "должным образом" потребуются высказывания, касающиеся местонахождения. Одна из первых попыток решения этой задачи может состоять в использовании некоторого символа наподобие L1,1 для обозначения того, что агент находится в квадрате [1,1]. В таком случае начальная база знаний могла бы включать высказывания, подобные следующим:

L1,1 ^ FacingRight ^ Forward => L2,1

Однако сразу же обнаруживается, что такой способ является неприменимым. Если агент начинает движение с квадрата [1,1], глядя вправо, и передвигается вперед, то из базы знаний будут следовать высказывания и L1,1 (о его первоначальном местонахождении), и L1,2 (о его новом местонахождении). Тем не менее эти высказывания не могут одновременно быть истинными! Проблема состоит в том, что эти два высказывания, касающиеся местонахождения, должны ссылаться на два различных промежутка времени. Нам требуется ввести обозначение наподобие L1,1 которое означало бы, что агент находился в квадрате [1,1] в момент времени 1, L2,1 — для обозначения того, что агент находился в квадрате [2,1] в момент времени 2, и т.д. Высказывания, касающиеся ориентации и действий, также должны зависеть от времени. Поэтому правильными высказываниями являются следующие:

L+ ^ FacingRight1 ^ Forward1 => L2,1

FacingRight ^ TurnLeft1 => FacingUp2

и тому подобные высказывания. Как оказалось, задача создания полной и правильной базы знаний, которая позволяла бы следить за всем, что происходит в мире вампуса, является весьма сложной. А в данном разделе достаточно лишь подчеркнуть такую мысль, что начальная база знаний должна содержать высказывания, подобные приведенным в двух предыдущих примерах, для каждого момента времени t, а также для каждого местонахождения. Это означает, что для каждого момента времени t и местонахождения [x, y] база знаний содержит некоторое высказывание примерно в такой форме:

Lt x,y ^ FacingRightt ^ Forwardt => Lt+1 x+1, y

Но даже если мы установим верхний предел количества допустимых интервалов времени (допустим, 100), в конечном итоге база знаний заполнится десятками тысяч высказываний. Та же самая проблема возникает, если для каждого нового интервала времени добавление высказываний происходит "по мере необходимости". Из-за такого стремительного увеличения количества высказываний база знаний становится неудобной для чтения людьми, но быстрые пропозициональные алгоритмы — решатели задач все еще способны легко справляться с задачами в мире вампуса с размерами 4x4 (они достигают предела своих возможностей в мире, размеры которого составляют приблизительно 100x100). Агенты, основанные на логических схемах, которые описаны в следующем подразделе, предоставляют частичное решение этой проблемы стремительного увеличения количества высказываний.