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

В настоящем разделе рассматривается метод планирования, основанный на иерархических се задач, или сетях HTN (Hierarchical Task Network). В принятом нами подходе объединены идеи из области планирования с частичным упорядочением (раздел 11.3) и из области, известной под названием "планирование в иерархических сетях задач", или планирование HTN. В планировании HTN первоначальный план, который описывает задачу, рассматривается как описание на очень высоком уровне того, что должно быть сделано, например строительство дома. Планы уточняются путем применения декомпозиций действий. В каждой декомпозиции действия одно действие высокого уровня сводится к частично упорядоченному множеству действий низкого уровня. Поэтому в декомпозициях действий воплощены знания о том, как осуществляются действия. Например, строительство дома может быть сведено к получению разрешения, найму подрядчика, осуществлению строительства и оплате работы подрядчика (такая декомпозиция показана на рис. 12.3). Этот процесс продолжается до тех пор, пока в плане не остаются только примитивные действия. Как правило, примитивными считаются такие действия, которые могут быть выполнены агентом автоматически. Например, для генерального подрядчика такое действие, как "оформление ландшафтной архитектуры", может оказаться примитивным, поскольку оно сводится к привлечению подрядчика по ландшафтной архитектуре, а для подрядчика по ландшафтной архитектуре могут рассматриваться как примитивные действия, подобные "посадке на этом участке рододендронов".

Рис. 12.3. Одна из возможных декомпозиций для действия BuildHouse