Обсуждение вопроса
Вначале необходимо отметить определенные сложности: чистая задача планирования HTN неразрешима (если единственным допустимым способом уточнения плана является декомпозиция), даже если соответствующее пространство состояний конечно! На первый взгляд такая ситуация может показаться весьма бесперспективной, поскольку основной смысл планирования HTN состоит в обеспечении высокой эффективности составления планов. Указанные сложности возникают потому, что декомпозиции действий могут оказаться рекурсивными (например, если выход на прогулку рассматривается как выполнение одного шага с последующим выходом на прогулку), поэтому планы HTN могут приобретать произвольную длину. В частности, даже кратчайшее решение HTN может оказаться неопределенно длинным, так что становится невозможным нахождение способа завершения поиска за какое-то постоянное время. Тем не менее существуют по меньшей мере три описанных ниже способа исправления указанного положения.
1. Исключить рекурсию, поскольку она действительно требуется лишь в очень немногих проблемных областях. В таком случае все планы HTN приобретают конечную длину и могут быть успешно исследованы.
2. Ограничить длину решений, которые нас интересуют. Поскольку пространство состояний является конечным, план, включающий больше этапов, чем имеется состояний в пространстве состояний, обязательно должен включать цикл, в котором неоднократно посещается одно и то же состояние. Мы ничего не потеряем, исключив решения HTN такого рода, поэтому следует контролировать длину поиска.
3. Принять гибридный подход, в котором сочетается планирование POP и HTN. Для определения того, существует ли план, достаточно применить планирование с частичным упорядочением, отдельно взятое, поэтому, безусловно, задача планирования с помощью гибридного подхода является разрешимой.
При использовании третьего метода необходимо соблюдать определенную осторожность. В планировании POP примитивные действия могут соединяться в цепочки произвольными способами, поэтому иногда приходится сталкиваться с такими решениями, которые очень трудно понять и которые не имеют такой аккуратной иерархической организации, как планы HTN. Приемлемым компромиссом является управление гибридным поиском таким образом, чтобы операции декомпозиции действий стали предпочтительными по сравнению с операциями добавления новых действий, хотя и не до такой степени, чтобы вырабатывались планы HTN произвольной длины, прежде чем появится возможность добавления каких-либо примитивных действий. Один из способов осуществления такого управления состоит в использовании функции стоимости, которая предоставляет благоприятные условия действиям, введенным путем декомпозиции; чем более благоприятными являются эти условия, тем больше поиск будет напоминать чистое планирование HTN и тем более иерархическим будет решение. Иерархические планы обычно намного проще для выполнения в реальных условиях, поэтому их легче исправить, если что-то при их осуществлении нарушается.
Еще одной важной характерной особенностью планов HTN является возможность совместного использования подзадач. Напомним, что совместным использованием подзадач называется применение одного и того же действия для реализации двух разных этапов в декомпозиции планов. Если совместное использование подзадач запрещено, то каждая конкретизация декомпозиции d' должна быть выполнена только одним способом, а не многими, что приводит к отсечению значительной части пространства поиска. Обычно такое отсечение обеспечивает некоторую экономию времени и в худшем случае приводит к решению, лишь немного более длинному, чем оптимальное. Но в некоторых случаях возникают более существенные проблемы. Например, рассмотрим цель: "Насладись медовым месяцем и создай большую семью". Библиотека планов может содержать решение "вступи в брак и отправляйся на Гавайи" для первой подцели и "вступи в брак и заведи двух детей" для второй. Без совместного использования подзадач план будет включать два разных действия по вступлению в брак для одного человека, но такой вариант многие считают весьма нежелательным.
Интересным примером анализа затрат и результатов совместного использования подзадач является применение этого метода при оптимизации компиляторов. Рассмотрим задачу компиляции выражения tan (х) -sin (х). В большинстве компиляторов такая задача выполняется путем слияния результатов двух отдельных вызовов процедур тривиальным способом: все этапы процедуры вычисления тангенса tan выполняются перед каким-либо из этапов вычисления синуса sin. Но рассмотрим следующие аппроксимации для sin и tan с помощью рядов Тэйлора:
tan х~х+з + 15 + 315 ; sin х ~ х - 6 + 120 - 5040
Планировщик HTN с совместным использованием подзадач может выработать более эффективное решение, поскольку он способен выбрать вариант реализации многочисленных этапов вычисления sin в сочетании с существующими этапами вычисления tan. В большинстве компиляторов межпроцедурное совместное использование этапов такого рода не осуществляется, поскольку для них потребовалось бы слишком много времени на рассмотрение всех возможных совместно используемых планов. Вместо этого в большинстве компиляторов каждый субплан вырабатывается независимо и только после этого, возможно, происходит модификация результата с помощью локального оптимизатора.
Если учесть все эти дополнительные сложности, вызванные введением декомпозиций действий, можно ли рассчитывать на то, что планирование HTN окажется эффективным? Фактические причины сложностей трудно проанализировать на практике, поэтому рассмотрим идеализированный случай. Предположим, например, что необходимо составить план с п действиями. Для неиерархического планировщика с прямым поиском в пространстве состояний при наличии Ь допустимых действий в каждом состоянии затраты составят O(tP). А применительно к планировщику HTN предположим, что структура декомпозиции является регулярной: каждое непримитивное действие имеет d возможных декомпозиций, каждая из которых сводится к действиям на следующем, более низком уровне. Необходимо определить, сколько разных деревьев декомпозиции существует в этой структуре. Итак, если имеется п действий на примитивном уровне, то количество уровней ниже корня равно 1одкл, поэтому количество внутренних узлов декомпозиции определяется выражением 1 + к+к2 + ... + к1одъп~1= (л-1) / (к-1). Каждый внутренний узел имеет d возможных декомпозиций, поэтому существует d(n'1)/(k~1] возможных регулярных деревьев декомпозиции, которые могут быть сформированы. Исследуя эту формулу, можно определить, что уменьшение значения d и увеличение значения к позволяет получить огромную экономию: по сути затраты измеряются корнем k-й степени от стоимости неиерархического решения, если значения bud являются сопоставимыми. С другой стороны, составление библиотеки планов, которая включает небольшое количество длинных декомпозиций, но тем не менее позволяет решить любую задачу, не всегда возможно. В другой формулировке эту мысль можно выразить так, что длинные декомпозиционные макроподстановки, применимые для решения широкого ряда задач, являются чрезвычайно ценными.
Еще одной и, возможно, более важной причиной, позволяющей убедиться в том, что планирование HTN эффективно, является то, что эти методы хорошо зарекомендовали себя на практике. Почти все планировщики для крупномасштабных приложений являются планировщиками HTN, поскольку планирование HTN позволяет людям-экспертам применять свои крайне важные знания о том, как следует выполнять сложные задания, чтобы можно было формировать большие планы с малыми вычислительными издержками. Например, система 0-Р1ап [93], в которой планирование HTN сочетается с составлением расписаний, использовалась для разработки производственных планов в компании Hitachi. При этом типичная задача охватывала производственную линию с 350 различными изделиями, 35 сборочными агрегатами и с более чем 2000 различных операций. Планировщик О-Plan вырабатывает тридцатисуточные расписания с тремя восьмичасовыми сменами в сутки, включающие миллионы операций.
Таким образом, ключом к планированию HTN является составление библиотеки планов, в которой зашифрованы известные методы осуществления сложных, высокоуровневых действий. Одним из способов составления такой библиотеки является изучение требуемых методов на опыте решения задач. Накопив тяжелым трудом опыт планирования в ходе разработки какого-то плана с нуля, агент может сохранить этот план в библиотеке как метод осуществления высокоуровневого действия, определяемого данным конкретным заданием. Таким образом, агент может становиться со временем все более и более компетентным по мере того, как будет находить новые методы на основе старых. Одной из важных характеристик такого процесса обучения является способность обобщать созданные методы, устраняя детали, характерные для данного экземпляра задачи (например, в задаче строительства дома таковыми являются имя подрядчика или адрес земельного участка), и сохраняя в плане только ключевую информацию. Методы осуществления такого рода обобщения описаны в главе 19. Авторы не могут себе даже представить, что человечество смогло бы достичь современного уровня компетентности без какого-то подобного механизма.