ПЛАНИРОВАНИЕ С ПОМОЩЬЮ ПОИСКА В ПРОСТРАНСТВЕ СОСТОЯНИЙ
Данный раздел посвящен описанию алгоритмов планирования. Наиболее простой подход состоит в использовании поиска в пространстве состояний. Поскольку описания действий в задаче планирования определяют и предусловия, и результаты, существует возможность организовать поиск в обоих направлениях: либо в прямом, от начального состояния, либо в обратном, от цели, как показано на рис. 11.1. Кроме того, явные представления действий и целей могут использоваться для автоматического вывода эффективных эвристик.
Прямой поиск в пространстве состояний
Подход к организации планирования с использованием прямого поиска в пространстве состояний аналогичен подходу к решению задач, описанному в главе 3. Иногда его называют прогрессивным планированием, поскольку оно предусматривает продвижение в прямом направлении. При этом мы начинаем с начального состояния задачи и рассматриваем последовательности действий до тех пор, пока не находим последовательность, позволяющую достичь целевого состояния. Формулировка задач планирования в виде задач поиска в пространстве состояний приведена ниже.
• Начальным состоянием поиска является начальное состояние, взятое из задачи планирования. Вообще говоря, каждое состояние должно представлять собой множество положительных базовых литералов; литералы, не присутствующие в определении задачи, являются ложными.
• Всеми действиями, применимыми в некотором состоянии, являются такие действия, для которых выполнены предусловия. Состояние-преемник, являющееся результатом выполнения действия, вырабатывается путем добавления положительных литералов результата и удаления отрицательных литералов результата. (В случае использования литералов первого порядка к литералам результата необходимо применять унификатор из предусловий.) Обратите внимание на то, что во всех задачах планирования используется единственная функция определения преемника, что является следствием применения явного представления действий.
•
• В ходе проверки цели осуществляется проверка того, удовлетворяет ли данное состояние цели условиям задачи планирования.
• Стоимость этапа для каждого действия обычно равна 1. Хотя было бы неслож-. но предусмотреть использование различных стоимостей для разных действий,
такая возможность в планировщиках Strips применяется редко.
Напомним, что при отсутствии функциональных символов пространство состояний задачи планирования является конечным. Поэтому полным алгоритмом планирования должен быть любой алгоритм поиска в графе, который является полным (например, А*).
Начиная с самых первых дней исследований по планированию (примерно с 1961 года) и до сравнительно недавнего времени (примерно до 1998 года), предполагалось, что прямой поиск в пространстве состояний был бы слишком неэффективен для того, чтобы иметь практическое значение. Причины этого понять совсем несложно — достаточно вернуться в начало раздела 11.1. Во-первых, прямой поиск не решает проблему не относящихся к делу действий — рассматриваются все действия, применимые из каждого состояния. Во-вторых, без хорошей эвристики этот подход быстро приводит к чрезмерному увеличению объема вычислений. Рассмотрим задачу воздушных грузовых перевозок с 10 аэропортами, где в каждом аэропорту имеется 5 самолетов и 20 единиц груза. Цель состоит в том, чтобы переместить все грузы из аэропорта А в аэропорт В. Существует простое решение этой задачи: погрузить 20 единиц груза в один из самолетов в аэропорту А, полететь на этом самолете в аэропорт В и выгрузить груз. Но формальный поиск этого решения может оказаться затруднительным, поскольку средний коэффициент ветвления является огромным: каждый из этих 5x10 = 5 0 самолетов может полететь в 9 других аэропортов, а каждая из 2 0x10=200 единиц груза может быть либо разгружена (если она загружена), либо загружена в любой самолет в аэропорту, где она находится (если она разгружена). Допустим, что в среднем существует около 100 0 возможных действий, поэтому дерево поиска с глубиной, равной глубине очевидного решения, имеет около 10 0О41 узлов. Очевидно, что для обеспечения эффективности такого поиска потребуется очень точная эвристика. Мы рассмотрим некоторые возможные эвристики после описания обратного поиска.