7.6. ИСПОЛЬЗОВАНИЕ ИСЧИСЛЕНИЯ ПРЕДИКАТОВ ПРИ РЕШЕНИИ ЗАДАЧ В ПРОСТРАНСТВЕ СОСТОЯНИЙ

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

бы использовать методы доказательства теорем в исчислении предикате для проверки выполнения условий достижения цели и условий применимости операторов.

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

Описание 50 начального состояния может состоять из четырех п.п. формул:

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

У нас, как и прежде, есть четыре оператора: «подойти «передвинуть «взобраться» и «схватить». Два первых — операторные схемы; конкретное их значение зависит от величины схемной переменной. При определении каждого оператора основными являются следующие элементы:

правильно построенная формула применимости, описывающая условия, при которых этот оператор применим;

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

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

(см. скан)

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

(см. скан)

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

Теперь поиск целевого состояния может протекать на основе стандартного процесса применения применимых операторов

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

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

Следующий шаг в простейшем процессе перебора в пространстве состояний — выяснение, какой из операторов применим. Здесь опять можно использовать методы доказательства теорем на основе резольвенции. Для каждого оператора можно было бы попытаться доказать, что его п. п. формула применимости следует из 50. Тогда мы быстро обнаружили бы, что оператор «схватить» неприменим. Правильно построенные формулы применимости для операторов «взобраться» и «передвинуть» совпадают. Отрицание этой общей п. п. формулы применимости (в форме предложения) имеет вид Попытка вывести его противоречие с S здесь также окончится неудачей, так что операторы «взобраться» и «передвинуть» также неприменимы к S.

Наконец, нам удастся доказать, что оператор подойти применим к S. Используя правило преобразования для оператора «подойти приходим к следующей схеме описания состояний:

Теперь процесс повторяется. Сначала мы выясняем, существует ли частный случай схемы из которого следует целевая п. п. формула Очевидно, что нет. Далее мы находим операторы, которые можно применить к частным случаям схемы Например, при проверке применимости оператора «передвинуть мы хотим узнать, существует ли частный случай схемы из которого следует п. п. формула Мы видим, что подстановка в S вместо и величины дает частный случай, к которому оператор «передвинуть» применим. Обозначим этот частный

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

Поскольку к применим оператор «передвинуть», к применим также и оператор «взобраться», но оператор «схватить» неприменим ни к одному частному случаю схемы

К любому частному случаю схемы применим, конечно, также и оператор «подойти», но его применение не изменяет схему описания состояния.

Теперь, если применить оператор «передвинуть то получится схема описания состояния

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

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