ПЛАНИРОВАНИЕ ИЕРАРХИЧЕСКОЙ СЕТИ ЗАДАЧ
Одной из наиболее привлекательных идей в области решения сложных задач является иерархическая декомпозиция. На основе иерархии процедур или классов объектов создается сложное программное обеспечение; из иерархии боевых подразделений складываются армии; иерархии отделов, филиалов и дочерних организаций лежат в основе правительств и корпораций. Основное преимущество иерархической структуры состоит в том, что на каждом уровне иерархии вычислительная задача, военная операция или административная функция сводится к небольшому количеству действий, выполняемых на более низком уровне, поэтому вычислительная стоимость поиска правильного способа упорядочения этих действий для решения текущей задачи очень невелика. С другой стороны, в неиерархических методах задача сводится к очень большому количеству отдельных действий; при решении крупномасштабных задач такой подход становится полностью неприменимым. Но в наилучшем случае (в котором высокоуровневые решения всегда сводятся к решениям, имеющим удовлетворительные низкоуровневые реализации) иерархические методы могут привести к созданию алгоритмов планирования с линейными, а не экспоненциальными затратами времени.
В настоящем ракеле рассматривается метод планирования, основанный на иерархических сс задач, или сетях HTN (Hierarchical Task Network). В принятом нами подходе объединены идеи из области планирования с частичным упорядочением (раздел 11.3) и из области, известной под названием "планирование в иерархических сетях задач", или планирование HTN. В планировании HTN первоначальный план, который описывает задачу, рассматривается как описание на очень высоком уровне того, что должно быть сделано, например строительство дома. Планы уточняются путем применения декомпозиций действий. В каждой декомпозиции действия одно действие высокого уровня сводится к частично упорядоченному множеству действий низкого уровня. Поэтому в декомпозициях действий воплощены знания о том, как осуществляются действия. Например, строительство дома может быть сведено к получению разрешения, найму подрядчика, осуществлению строительства и оплате работы подрядчика (такая декомпозиция показана на рис. 12.3). Этот процесс продолжается до тех пор, пока в плане не остаются только примитивные действия. Как правило, примитивными считаются такие действия, которые могут быть выполнены агентом автоматически. Например, для генерального подрядчика такое действие, как "оформление ландшафтной архитектуры", может оказаться примитивным, поскольку оно сводится к привлечению подрядчика по ландшафтной архитектуре, а для подрядчика по ландшафтной архитектуре могут рассматриваться как примитивные действия, подобные "посадке на этом участке рододендронов".
В "чистом" планировании HTN планы разрабатываются только путем последовательной декомпозиции действий. Поэтому планирование HTN может рассматриваться как процесс конкретизации описания некоторой деятельности, а не как процесс создания описания деятельности, начиная с пустого действия (как в случае планирования в пространстве состояний и планирования с частичным упорядочением). Как оказалось, каждое описание действия Strips может быть преобразовано в декомпозицию действия (см. упр. 12.6), а планирование с частичным упорядочением может рассматриваться как частный случай чистого планирования HTN. Однако для некоторых задач (особенно для тех, в которых применяется так называемая "новаторская" постановка с конъюнктивными целями) подход с использованием чистого планирования HTN становится не совсем естественным. Поэтому авторы предпочитают применять гибридный подход, в котором декомпозиции действий используются как уточнения плана в планировании с частичным упорядочением, в дополнение к стандартным операциям определения открытых условий и разрешения конфликтов путем введения ограничений упорядочения. (Подход, в котором планирование HTN рассматривается как расширение планирования с частичным упорядочением, имеет дополнительное преимущество в том, что могут использоваться те же соглашения по системе именования вместо введения полностью нового набора обозначений.) Начнем с более подробного описания декомпозиций действий. Затем рассмотрим, как можно модифицировать алгоритм планирования с частичным упорядочением для учета декомпозиций, и, наконец, рассмотрим вопросы полноты, сложности и практической применимости алгоритмов.