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

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

% Разрешенные ходы
ход( состояние( середина, на ящике, середина, неимеет),
 схватить, % Схватить банан
состояние( середина, наящике, середина, имеет)).

ход( состояние( P, наполу, P, H),
 залезть, % Залезть на ящик
 состояние( P, наящике, P, H) ).

ход( состояние( P1, наполу, P1, H),
 подвинуть( P1, Р2), % Подвинуть ящик с P1 на Р2
 состояние( Р2, наполу, Р2, H) ).

ход( состояние( P1, наполу, В, H),
 перейти( P1, Р2), % Перейти с P1 на Р2
 состояние( Р2, наполу, В, H) ).

% можетзавладеть(Состояние): обезьяна может завладеть
% бананом, находясь в состоянии Состояние
можетзавладеть( состояние( -, -, -, имеет) ).

% может 1: обезьяна уже его имеет
можетзавладеть( Состояние1) :-
 % может 2: Сделать что-нибудь, чтобы завладеть им
 ход( Состояние1, Ход, Состояние2),
 % сделать что-нибудь
 можетзавладеть( Состояние2).
 % теперь может завладеть

Рис. 2.14. Программа для задачи об обезьяне и банане.

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

Рис. 2.15. Поиск банана обезьяной. Перебор начинается в верхнем узле и распространяется вниз, как показано. Альтернативные ходы перебираются слева направо. Возврат произошел только один раз.

2.6. Порядок предложений и целей

2.6.1. Опасность бесконечного цикла

Рассмотрим следующее предложение:

p :- p.

В нем говорится: "p истинно, если p истинно". С точки зрения декларативного смысла это совершенно корректно, однако в процедурном смысле оно бесполезно. Более того, для пролог-системы такое предложение может породить серьезную проблему. Рассмотрим вопрос:

?- p.

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

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

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

?- можетзавладеть( состояние( удвери, наполу, уокна, неимеет) ).

протекал бы на этот раз так. Первые четыре списка целей (с соответствующим образом переименованными переменными) остались бы такими же, как и раньше:

(1) можетзавладеть( состояние( удвери, наполу, уокна, неимеет) ).

Применение второго предложения из можетзавладеть ("может2") породило бы

(2) ход( состояние( удвери, наполу, уокна, неимеет), М', S2'), 

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

С помощью хода перейти( уокна, Р2') получилось бы

(3) можетзавладеть( состояние( Р2', наполу, уокна, неимеет) )

Повторное использование предложения "может2" превратило бы список целей в

(4) ход( состояние(Р2', наполу, уокна, неимеет), М'', S2''),

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

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

S2'' = состояние( Р2'', наполу, уокна, неимеет).

Поэтому список целей стал бы таким:

(5) можетзавладеть( состояние( Р2'', наполу, уокна, неимеет) )

Применение предложения "может2" дало бы

(6) ход( cocтояниe( P2'', наполу, yoкнa, неимeeт), M''', S2'''),

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

Снова первый было бы попробовано "перейти" и получилось бы

(7) можетзавладеть( состояние( Р2''', наполу, уокна, неимеет) )

Сравним теперь цели (3), (5) и (7). Они похожи и отличаются лишь одной переменной, которая по очереди имела имена Р', Р'' и P'''. Как мы знаем, успешность цели не зависит от конкретных имен переменных в ней. Это означает, что, начиная со списка целей (3), процесс вычислений никуда не продвинулся. Фактически мы замечаем, что по очереди многократно используются одни и те же два предложения: "может2" и "перейти". Обезьяна перемещается, даже не пытаясь воспользоваться ящиком. Поскольку продвижения нет, такая ситуация продолжалась бы (теоретически) бесконечно: пролог-система не сумела бы осознать, что работать в этой направлении нет смысла.