2.7. ВЫБОР «ХОРОШИХ» ПРЕДСТАВЛЕНИЙ

Выбор для данной задачи определенного представления в пространстве состояний существенно определяет те поисковые усилия, которые придется приложить для ее решения. Очевидно, что предпочтительны представления с малыми пространствами состояний (т. е. такие, графы которых имеют небольшое число вершин). Существует множество примеров задач, кажущихся трудными, но таких, что при правильной их трактовке соответствующие пространства состояний оказываются очень узкими. Подчас данное пространство состояний «сжимается в точку» после того, как обнаруживается, что некоторые операторы могут быть отброшены за ненадобностью, а другие — объединены в более мощные операторы. И даже если такие простые преобразования неосуществимы, может оказаться, что полная переформулировка задачи, изменяющая само понятие состояния, приведет к меньшему пространству.

Еще слишком слабо поняты те процессы, которые необходимы для первоначального представления задач и для

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

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

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

Как следует строить для этой задачи представления в пространстве состояний? В описании состояния должны непременно появиться следующие элементы: координаты обезьяны в комнате (по горизонтали и по вертикали), координаты ящика в комнате и наличие у обезьяны бананов. Эти элементы удобно представить в виде четырехэлементного списка (w, х, у, z), где

w — координаты обезьяны в горизонтальной плоскости (двумерный вектор),

х — это 1 или 0 в зависимости от того, где обезьяна находится, на ящике или нет,

у — координаты ящика в горизонтальной плоскости (двумерный вектор),

z — это 1 или 0 в зависимости от того, достала обезьяна бананы или нет.

Если бы каждое отдельное значение списка (w, х, у, z) описывало ровно одно состояние, то мы имели бы бесконечное число состояний, поскольку число различных расположений предметов в комнате бесконечно. Мы могли бы сделать

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

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

1) подойти — обезьяна идет к точке и в плоскости пола комнаты (и — переменная),

2) передвинуть — обезьяна передвигает ящик в точку пола комнаты — переменная),

3) взобраться — обезьяна забирается на ящик,

4) схватить — обезьяна хватает бананы.

В связи с наличием переменных в «подойти», «передвинуть» эти операторы на самом деле являются схемами. Условия применимости и действия этих операторов даются следующими правилами переписывания:

где с — координаты точки пола, расположенной непосредственно под бананами (двумерный вектор).

Применение некоторых операторов, например «передвинуть», связано с ограничением значений переменных, представляющих координаты обезьяны и ящика, от которых теперь требуется, чтобы они были одинаковыми. Мы будем считать идентичными две схемы для описания состояний, если они отличаются лишь наименованием переменных.

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

Предположим, что вначале обезьяна находится в точке а пола, а ящик — в Тогда описанием начального состояния будет Единственный оператор, который применим в этом состоянии, - это «подойти», приводящий к схеме Теперь применимы три оператора. Если то обезьяна может либо забраться на ящик, либо передвинуть его. Независимо от величины и обезьяна могла бы переместиться куда-нибудь

еще. Влезание на ящик приводит к состоянию с описанием перемещение ящика в приводит к схеме а переход в другое место, описываемое новой переменной, не изменяет описания.

Продолжая процесс применения всех операторов, мы построим пространство состояний, иллюстрируемое графом на рис. 2.10. Мы видим, что этот граф весьма невелик и на нем легко можно найти путь, решающий нашу задачу (жирные стрелки).

Рис. 2.10. (см. скан) Граф для задачи об обезьяне и бананах.

Подставив вместо переменных их соответствующие частные значения, как это показано на рис. 2.10, мы получаем последовательность операторов: подойти передвинуть взобраться, схватить.

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