Главная arrow книги arrow Копия Глава 12. arrow Обсуждение вопроса
Обсуждение вопроса

Вначале необходимо отметить определенные сложности: чистая задача планирования HTN неразрешима (если единственным допустимым способом уточнения плана является декомпозиция), даже если соответствующее пространство состояний конечно! На первый взгляд такая ситуация может показаться весьма бесперспективной, поскольку основной смысл планирования HTN состоит в обеспечении высокой эффективности составления планов. Указанные сложности возникают потому, что декомпозиции действий могут оказаться рекурсивными (например, если выход на прогулку рассматривается как выполнение одного шага с последующим выходом на прогулку), поэтому планы HTN могут приобретать произвольную длину. В частности, даже кратчайшее решение HTN может оказаться неопределенно длинным, так что становится невозможным нахождение способа завершения поиска за какое-то постоянное время. Тем не менее существуют по меньшей мере три описанных ниже способа исправления указанного положения.

1.    Исключить рекурсию, поскольку она действительно требуется лишь в очень немногих проблемных областях. В таком случае все планы HTN приобретают конечную длину и могут быть успешно исследованы.

2.    Ограничить длину решений, которые нас интересуют. Поскольку пространство состояний является конечным, план, включающий больше этапов, чем имеется состояний в пространстве состояний, обязательно должен включать цикл, в котором неоднократно посещается одно и то же состояние. Мы ничего не потеряем, исключив решения HTN такого рода, поэтому следует контролировать длину поиска.

3.    Принять гибридный подход, в котором сочетается планирование POP и HTN. Для определения того, существует ли план, достаточно применить планирование с частичным упорядочением, отдельно взятое, поэтому, безусловно, задача планирования с помощью гибридного подхода является разрешимой.

При использовании третьего метода необходимо соблюдать определенную осторожность. В планировании POP примитивные действия могут соединяться в цепочки произвольными способами, поэтому иногда приходится сталкиваться с такими решениями, которые очень трудно понять и которые не имеют такой аккуратной иерархической организации, как планы HTN. Приемлемым компромиссом является управление гибридным поиском таким образом, чтобы операции декомпозиции действий стали предпочтительными по сравнению с операциями добавления новых действий, хотя и не до такой степени, чтобы вырабатывались планы HTN произвольной длины, прежде чем появится возможность добавления каких-либо примитивных действий. Один из способов осуществления такого управления состоит в использовании функции стоимости, которая предоставляет благоприятные условия действиям, введенным путем декомпозиции; чем более благоприятными являются эти условия, тем больше поиск будет напоминать чистое планирование HTN и тем более иерархическим будет решение. Иерархические планы обычно намного проще для выполнения в реальных условиях, поэтому их легче исправить, если что-то при их осуществлении нарушается.