2. ЛОГИЧЕСКИЕ РАССУЖДЕНИЯ

В этой главе рассмотрена задача создания целенаправленного агента, имеющего дело с дискретной средой, ее постановка и решете. Введены основные понятия логики высказываний. Описан процесс рассуждений в этой логике, позволяющий целенаправленному агенту достигать целей.

Рассуждением или умозаключением обычно называют ряд мыслей, изложенных в логически последовательной форме. В предыдущей главе были введены понятия состояний среды. Настоящая глава посвящена изучению возможности агента находить интересующие его состояния среды (целевые состояния), если он что-либо знает о других ее состояниях. Определение целевых состояний осуществляется с помощью поиска или рассуждений в пространстве состояний. Обсудим, как рассуждения подобного рода можно формализовать в языке логики высказываний, т.е. как формально поставить задачу на языке логики высказываний и затем ее формально решить, пользуясь аппаратом логики высказываний. Рассмотрим также, предваряя главу 6, что такое стратегия решения или поиска. Там, где это возможно, введение необходимых понятий будем иллюстрировать простыми примерами. В конце главы остановимся на трудностях, которые возникают при решении задач с помощью только логики высказываний.

2.1. Рассуждения в пространстве состояний среды

В коммунальной квартире две старушки занимают по комнате. Комнаты находятся в общем коридоре, который имеет выход на лестничную клетку. Одна из комнат расположена слева (левая комната) от выхода, а другая — справа (правая комната). В коридоре живет кот, которого обе старушки одинаково любят и балуют, оставляя ему кусочки сыра. Каждая старушка кладет кусочек сыра у двери своей комнаты. Кот отдыхает либо у левой комнаты (слева), либо у правой (справа). Множество всех состояний этой среды (среды кота) можно представить табл. 2.1, в столбцах которой для каждого состояния среды указаны местонахождение кота (слева или справа), наличие или отсутствие кусочка сыра (да или нет) у соответствующей комнаты.

Состояние означает, что кот находится около левой комнаты и около обеих комнат лежит по кусочку сыра, состояние — кот находится около

Таблица 2.1 (см. скан)

правой комнаты и около обеих комнат снова лежит по кусочку сыра и т.д. Кот может совершать в один и тот же момент времени только одно из следующих действий: переходить к дверям левой комнаты, переходить к дверям правой комнаты и съедать кусочек сыра около той комнаты, где он находится. Эти действия обозначим Идти налево, Идти направо и Съесть соответственно. Если среда находится в одном из состояний, перечисленных в табл. 2.1, и кот совершает какое-либо из действий, то нетрудно определить, в какое состояние после выполнения действия перейдет среда.

Будем полагать, что нам известно состояние, называемое начальным, с которого могут начаться изменения среды при действиях кота. Пусть, например, это будет состояние Будем изображать состояния кружочками с обозначением состояния внутри кружочка. Переход из одного состояний в другое,

Рис. 2.1. Допустимые переходы из начального состояния

Рис. 2.2. Дерево переходов

происходящий в результате действия, будем изображать стрелкой, ведущей в это другое состояние и помеченной соответствующим действием. Так, на рис. 2.1 изображены все переходы из состояния в результате действий На рис. 2.2 показано дерево всех дальнейших переходов, являющееся продолжением элементарного дерева на рис. 2.1. Построение каждой ветви дерева прекращено на том состоянии, которое встречается повторно на пути, ведущем в него из начального состояния.

2.1.1. Постановка задачи

Цель кота — не оставить ни одного кусочка сыра, где бы он изначально ни находился. В терминах состояний среды целью кота является перевод ее с помощью своих действий (реакций) в одно из состояний или Состояния, в которые с помощью набора допустимых действий необходимо перевести среду, называются целевыми. Процесс определения этих состояний называют формулировкой цели. Будем полагать в рамках нашего примера, что каждое восприятие совпадает с одним из состояний. Задачей агента (см. гл. 1) является

нахождение последовательности действий или пар восприятие—действие, ведущих на дереве переходов из начального состояния в целевые. Процесс нахождения этих последовательностей называют поиском, выводом или рассуждением. Постановкой задачи называют задание всех состояний и действий, которые можно использовать для решения задачи, начального состояния и целевых состояний, а также всех допустимых переходов между состояниями при выполнении действий. Для среды кота постановка задачи уже осуществлена. Все состояния, которые могут использоваться при решении задачи, перечислены в табл. 2.1. Целевыми состояниями являются состояния Все допустимые переходы между состояниями показаны на рис. 2.2. Из рисунка ясно, что решениями задачи является последовательность в результате выполнения которой агент (кот) переведет среду в состояние и последовательность в результате выполнения которой среда окажется в состоянии

2.1.2. Поиск решения

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

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

1. Образовать множество состоящее из одного начального состояния

2. Для каждого состояния множества В и каждого действия с. найти, согласно соответствующим правилам перехода, все состояния в которые переходит среда. Совокупность всех таких состояний, за исключением тех, которые уже встречались в ранее образованных множествах В, принять за новое множество В.

3. Проверить, нет ли среди элементов этого множества целевых состояний. Если целевых состояний нет, то перейти к п. 2. Если целевые состояния есть, то выписать в порядке использования правил все последовательности действий, которые привели к целевым состояниям, удалить эти состояния из множества В и перейти к выполнению следующего пункта.

4. Проверить, все ли целевые состояния найдены. Если найдены все, то прекратить поиск. Если найдены не все, то перейти к

Проиллюстрируем на примере среды кота применение этой стратегии. Правила перехода выписывать не будем, поскольку в нашем распоряжении уже есть дерево переходов (см. рис. 2.2).

Итак, вначале После выполнения имеем совокупность состояний В этой совокупности нет ни одного целевого состояния, а состояние уже встречалось. Поэтому, согласно п. 3, принимаем и переходим к выполнению п. 2. В результате получаем совокупность состояний среди которых опять нет целевых, уже встречались. Поэтому и снова возвращаемся к п. 2. После очередного выполнения этого пункта имеем совокупность состояний Среди этих состояний уже встречались, а состояние является целевым. В это состояние ведет единственная последовательность действий Однако еще не все целевые состояния найдены, а именно не найдено состояние Поэтому в соответствии с п. 4 продолжим поиск, вновь переходя к п. 2 с множеством . В результате получим совокупность состояний среди которых уже встречались, а целевое. Последовательностью действий, ведущих в состояние является Итак, все целевые состояния найдены, решение задачи в виде последовательности действий, ведущих в эти состояния, получено. Поиск на этом прекращается.