ГРАФЫ ПЛАНИРОВАНИЯ
Все предложенные выше эвристики для планирования с полным упорядочением и частичным упорядочением могут допускать неточности. В данном разделе показано, как можно воспользоваться специальной структурой данных, называемой графом планирования, для получения лучших эвристических оценок. Такие эвристики могут применяться в любом из методов поиска, рассмотренных нами до сих пор. Еще один вариант состоит в том, что решение может быть извлечено непосредственно из графа планирования с использованием специализированного алгоритма, например такого, который получил название Graphplan.
Граф планирования состоит из последовательности уровней, которые соответствуют временнб/м этапам в плане, где уровень 0 представляет собой начальное состояние. Каждый уровень содержит множество литералов и множество действий. Грубо говоря, литералы представляют собой то, что может быть истинным на каждом временном этапе в зависимости от действий, выполненных на предыдущих вре-меннб/х этапах. Также грубо говоря, действиями являются все те действия, которые могут иметь все свои предусловия выполненными на данном временном этапе в зависимости от того, какие из литералов фактически являются истинными. В этих двух определениях применяется выражение "грубо говоря", поскольку в графе планирования регистрируется только ограниченное подмножество возможных отрицательных взаимодействий между действиями; поэтому граф может давать оптимистическую оценку минимального количества временнб/х этапов, требуемых для того, чтобы некоторый литерал стал истинным. Тем не менее такое количество этапов в графе планирования предоставляет хорошую оценку того, насколько трудно достичь указанного литерала из начального состояния. Еще важнее то, что граф планирования определен таким образом, что может быть сформирован очень эффективно.
Графы планирования могут применяться только для решения задач планирования в пропозициональной логике, т.е. тех задач, в которых отсутствуют переменные. Как упоминалось в разделе 11.1, в пропозициональную форму могут быть преобразованы и представления Strips, и представления ADL. Если в задаче имеется большое количество объектов, это может привести к весьма существенному возрастанию количества возможных схем действий. Несмотря на это, было показано, что графы планирования представляют собой эффективное инструментальное средство решения трудных задач планирования.
Проиллюстрируем применение графов планирования на простом примере. (Использование более сложных примеров привело бы к созданию графов, которые не поместились бы на одной странице книги.) В листинге 11.5 приведена задача, а на рис. 11.6 показан ее граф планирования. Начнем с уровня состояния S0, который представляет начальное состояние задачи. Затем перейдем на уровень действия А0 и поместим на него все действия, предусловия которых были выполнены на предыдущем уровне. Каждое действие соединено с его предусловиями в состоянии S0 и его результатами в состоянии Sl9 а это в данном случае влечет за собой введение в s1 новых литералов, которых не было в s0.
Листинг 11.5. Задача "получить кекс, а также съесть кекс"
Init{Have{Саке))
Goal(Have(Cake) A Eaten(Cake))
Action(Eat(Cake)
Precond: Have(Cake)
Effect: -Have(Cake) A Eaten(Cake))
Action(Bake(Cake)
Precond: —\Have(Cake) Effect: Have(Cake)
Должны быть предусмотрены способы представлять на графе планирования не только действие, но и бездействие. Это означает, что необходимо иметь своего рода эквивалент аксиом окружения ситуационного исчисления, которые позволяют литералу оставаться истинным от одной ситуации к другой, если его не изменяет ни одно действие. В графе планирования это осуществляется с помощью множества сохраняющих действий (persistence action). Для каждого положительного или отрицательного литерала С в задачу вводится сохраняющее действие с предусловием С и результатом С. На рис. 11.6 в состоянии А0 показано одно "реальное" действие,
Eat {Саке) (съесть кекс), наряду с двумя сохраняющими действиями, обозначенными с помощью небольших квадратов.
Уровень А0 содержит все действия, которые могут произойти в состоянии S0, но столь же важно то, что он показывает конфликты между действиями, способные воспрепятствовать тому, чтобы эти действия выполнялись вместе. Серыми линиями на рис. 11.6 показаны взаимно исключающие связи (или связи, характеризующиеся взаимным исключением — mutual exclusive, mutex). Например, действие Еа t (Саке) является взаимно исключающим с действием, обеспечивающим сохранение состояния, вызванного действием Have (Саке) или -.Eatел (Саке). Вскоре будет показано, как происходит вычисление взаимно исключающих связей.
На уровне sx находятся все литералы, которые могут стать результатом принятия к исполнению любого подмножества действий уровня А0. На этом уровне показаны также взаимно исключающие связи (серые линии), обозначающие литералы, которые не могут появляться вместе, независимо от выбора действий. Например, взаимно исключающими являются литералы Have {Саке) и Eaten {Саке): в зависимости от выбора действий на уровне А0 результатом может стать один из них или другой, но не оба. Иными словами, на уровне Si представлено несколько состояний, точно так же, как и при регрессивном поиске в пространстве состояний, а взаимно исключающие связи представляют собой ограничения, которые определяют множество возможных состояний.
Построение плана продолжается таким же образом, с чередованием между уровнями состояния Si и уровнями действия Лх, до тех пор, пока не будет достигнут уровень, на котором два последовательных уровня становятся идентичными. После достижения такой точки граф называется выровненным (leveled off). Каждый последующий уровень будет оставаться неизменным, поэтому дальнейшее развертывание не имеет смысла.
В конечном итоге образуется структура, в которой каждый уровень А± содержит все действия, применимые на уровне Si? наряду с ограничениями, указывающими, какие пары действий не могут выполняться одновременно. Каждый уровень Si содержит все литералы, которые могут стать результатом любого возможного выбора действий на уровне Ai_l5 наряду с ограничениями, указывающими, какие пары литералов недопустимы. Важно отметить, что процесс построения графа планирования не требует выбора среди действий, который потребовал бы комбинаторного поиска. Вместо этого в графе просто регистрируется невозможность осуществления некоторых выборов с использованием взаимно исключающих связей. Сложность формирования графа планирования оценивается полиномиальной зависимостью низкого порядка от количества действий и литералов, тогда как размеры пространства состояний определяются экспоненциальной зависимостью от количества литералов.
Теперь определим взаимно исключающие связи как для действий, так и для литералов. Между двумя действиями на данном конкретном уровне имеет место взаимно исключающее отношение, если соблюдается любое из трех перечисленных ниже условий.
• Несогласованные результаты. Одно действие отрицает результат другого. Например, действие Eat {Саке) и сохраняющее действие Have {Саке) имеют несогласованные результаты, поскольку они не согласуются в результате Have (Саке) (съедение кекса приводит к его исчезновению).
• Вмешательство. Один из результатов одного действия является отрицанием предусловия другого действия. Например, действие Eat (Саке) мешает осуществлению сохраняющего действия Have (Саке), поскольку отрицает его предусловие (если кекса больше нет, то нечего и хранить).
• Конкурирующие потребности. Одно из предусловий одного действия является взаимно исключающим по отношению к предусловию другого. Например, литералы Баке (Саке) (Испечь кекс) и Eat (Саке) (Съесть кекс) являются взаимно исключающими, поскольку конкурируют за значение предусловия Have (Саке) (в одном литерале кекс создается, а в другом — уничтожается).
Взаимно исключающее отношение имеет место между двумя литералами на одном и том же уровне, если один из них является отрицанием другого или если каждая возможная пара действий, которые позволяют достичь двух литералов, является взаимно исключающей. Такое условие называется несогласованной поддержкой. Например, на уровне S1 литералы Have(Cake) и Eaten (Cake) являются взаимно исключающими, поскольку единственный способ достичь литерала Have (Cake) (применения сохраняющего действия) является взаимно исключающим с единственным способом достижения литерала Eaten (Cake), а именно Eat (Cake). На уровне S2 эти два литерала не являются взаимно исключающими, поскольку существуют новые способы их достижения, такие как действие Bake (Cake) и сохраняющее действие Eaten (Cake), которые не являются взаимно исключающими.