12. ПЛАНИРОВАНИЕ ДЕЙСТВИЙ

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

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

12.1. Задачи планирования

Пусть сосуды для воды А и В имеют различную емкость — 3 и 4 галлона соответственно (рис. 12.1). Каждый сосуд наполняется из своего крана и имеет свой сливной кран. Кроме того, каждый сосуд имеет трубу с краном для перелива воды в другой сосуд. Допускается выполнение трех действий над каждым сосудом: опустошение сосуда, наполнение сосуда и перелив из одного сосуда в другой.

Введем две функции содержимое (сосуд). Если сосуд то областью значений функции является множество а если сосуд то областью значений функции является множество Введем также предикат состояние

Рис. 12.1. Задача о поиске плана наполнения сосудов

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

Аксиомами ситуационного исчисления для нашей задачи будут следующие.

12.1.1. Аксиомы начальной ситуации

12.1.2. Аксиомы допустимых действий

Аксиомы опустошения сосудов:

Аксиомы наполнения сосудов:

Аксиомы переливания из сосуда в сосуд:

12.1.3. Аксиомы перехода в следующие ситуации

Запишем эти аксиомы в виде

Наша цель в данном случае — нахождение плана (последовательности действий), в результате которых сосуды окажутся в ситуации 5, в которой состояние сосудов будет определяться формулой

12.1.4. Процедура поиска плана

Стратегии поиска плана могут быть самыми различными. Часть из них безотносительно к какому-либо языку описания поведения среды фактически рассмотрена в главе 6. В настоящей главе используем процедуру обратного поиска, основанную на резолюции (см. гл. 4). Эта процедура состоит в следующем: опровержение цели, которая должна быть достигнута; преобразование аксиом в клаузальную форму;

до тех пор, пока есть разрешимые клаузы, выполнение следующих шагов:

нахождение пары разрешимых клауз, начиная с опровержения цели, и разрешение их;

добавление результата разрешения (резольвенты) к списку клауз, если достигнута пустая клауза то прекращение процедуры и констатация факта нахождения плана;

выписывание плана в явном виде и оценка возможности его выполнения;

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

12.1.5. Клаузы

Для нашего примера отрицание цели будет следующим:

Начальные клаузы имеют вид

Клауза опустошения сосудов следует из аксиомы опустошения:

Клауза наполнения сосуда А вытекает из аксиомы наполнения сосуда А:

Клауза наполнения сосуда В получается из аксиомы наполнения сосуда В:

Клаузы переливания из сосуда в сосуд можно получить, используя соответствующие аксиомы переливания:

Клаузы перехода в следующие ситуации:

(см. скан)

12.1.6. Обратный вывод

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

(см. скан)

12.1.7. Построение плана

Суть построения плана достаточно проста. Рассмотрим участок процесса вывода (12.22) — (12.27). Преобразуем клаузы (12.22), (12.24), (12.27) этого участка в эквивалентные формулы:

Используя эти формулы и обобщенные правила модус поненс, можем осуществить следующий прямой вывод:

На основании этого вывода приходим к заключению об истинности формулы

интерпретация которой означает, что сосуд В переводится в состояние, когда его содержимое равно 2, в результате действия Убавить осуществленного в ситуации Точно так же можно установить истинность формулы

интерпретация которой означает, что сосуд А переводится в состояние, когда его содержимое равно 2, в результате действия Добавить осуществленного в ситуации 50. Таким образом, план достижения цели определяется формулой

Этот план не является единственным. Аналогично можно найти другие планы достижения той же цели.