Главная arrow книги arrow Копия Глава 11. Основы планирования arrow Прямой поиск в пространстве состояний
Прямой поиск в пространстве состояний

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

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

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

•    В ходе проверки цели осуществляется проверка того, удовлетворяет ли данное состояние цели условиям задачи планирования.

•    Стоимость этапа для каждого действия обычно равна 1. Хотя было бы неслож-. но предусмотреть использование различных стоимостей для разных действий, такая возможность в планировщиках Strips применяется редко.