Программирование на языке Пролог для искусственного интеллекта

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

Одна из важных проблем при программировании состоит в выборе (адекватного) представления решаемой задачи в терминах понятий используемого языка программирования. В нашем случае мы можем считать, что "обезьяний мир" всегда находится в некотором состоянии, и оно может изменяться со временем. Текущее состояние определяется взаиморасположением объектов. Например, исходное состояние мира определяется так:

(1) Обезьяна у двери.

(2) Обезьяна на полу.

(3) Ящик у окна.

(4) Обезьяна не имеет банана.

Удобно объединить все эти четыре информационных фрагмента в один структурный объект. Давайте в качестве такого объединяющего функтора выберем слово "состояние". На рис. 2.12 в виде структурного объекта изображено исходное состояние.

Нашу задачу можно рассматривать как игру для одного игрока. Давайте, формализуем правила этой игры. Первое, целью игры является ситуация, в которой обезьяна имеет банан, т.е. любое состояние, у которого в качестве четвертой компоненты стоит "имеет":

состояние( _, _, _, имеет)

Второе, каковы разрешенные ходы, переводящие мир из одного состояния в другое? Существуют четыре типа ходов:

(1) схватить банан,

(2) залезть на ящик,

(3) подвинуть ящик,

(4) перейти в другое место.

Рис. 2.12. Исходное состояние обезьяньего мира, представленное в виде структурного объекта. Его четыре компоненты суть горизонтальная позиция обезьяны, вертикальная позиция обезьяны, позиция ящика, наличие или отсутствие у обезьяны банана.

Не всякий ход допустим при всех возможных состояниях мира. Например, ход "схватить" допустим, только если обезьяна стоит на ящике прямо под бананом (т.е. в середине комнаты) и еще не имеет банана. Эти правила можно формализовать в Прологе в виде трехместного отношения ход:

ход( Состояние1, М, Состояние2)

Три аргумента этого отношения определяют ход, следующим образом:

Состояние1 --------> Состояние2

                М

Состояние1 это состояние до хода, М — выполняемый ход, и Состояние2 — состояние после хода.

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

ход( состояние( середина, наящике, середина, неимеет),

           % Перед ходом

 схватить, % Ход

 состояние( середина, наящике, середина, имеет) ).

           % После хода

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

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

ход( состояние( P1, наполу, В, H),

 перейти( P1, Р2), % Перейти из P1 в Р2

 состояние( Р2, наполу, В, H) ).

Заметим, что в этом предложении делается много утверждений и, в частности:

• выполненный ход состоял в том, чтобы "перейти из некоторой позиции P1 в некоторую позицию Р2";

• обезьяна находится на полу, как до, так и после хода;

• ящик находится в некоторой точке В, которая осталась неизменной после хода;

• состояние "имеет банан" остается неизменным после хода.

Рис. 2.13. Рекурсивная формулировка отношения можетзавладеть.

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

Два других типа ходов: "подвинуть" и "залезть" — легко определить аналогичным способом.

Главный вопрос, на который должна ответить наша программа, это вопрос: "Может ли обезьяна, находясь в некотором начальном состоянии S, завладеть бананом?" Его можно сформулировать в виде предиката

можетзавладеть( S)

где аргумент S — состояние обезьяньего мира. Программа для можетзавладеть может основываться на двух наблюдениях: