Модификация планировщика для его использования в сочетании с декомпозициями
В этом разделе описано, как модифицировать алгоритм POP для его применения в планировании HTN. Для этого мы модифицируем функцию определения преемника POP (с. 530), чтобы иметь возможность применять методы декомпозиции к текущему частичному плану Р. Новые планы определения преемника формируются так, что вначале выбирается некоторое непримитивное действие а1 в плане Р, а затем для любого метода Decompose (a, d) из библиотеки планов, такого, что а и а' унифицируются с помощью подстановки 0, действие а 1 заменяется декомпозицией d'=Subst (8,d).
Один из примеров применения такого метода показан на рис. 12.4. В верхней части приведен план Р возведения дома. Для декомпозиции выбирается действие высокого уровня а 1 BuildHouse. В качестве декомпозиции d берется план, приведенный на рис. 12.3, и действие BuildHouse заменяется этой декомпозицией. Затем вводится дополнительный этап Get Loan (Получение ссуды) для разрешения нового открытого условия Money, которое создается на данном этапе декомпозиции. Замена действия его декомпозицией немного напоминает пересадку органов в хирургии: мы должны вынуть новый субплан из его упаковки (этапов Start и Finish), вставить его в нужное место и правильно связать сосуды, ткани и нервы. Для решения такой задачи может применяться несколько методов. Точнее, для каждой возможной декомпозиции d" должны быть выполнены описанные ниже этапы.
1. Вначале действие а' удаляется из плана Р. Затем для каждого этапа s в де-
композиции d' необходимо выбрать действие для выполнения соответст-
вующей роли в s и добавить его к плану. Это может быть либо новый экземпляр этапа s, либо существующий этап s' из плана Р, который унифицируется
с этапом s. Например, декомпозиция действия MakeWine (Выращивание ви-
нограда) может потребовать, чтобы мы купили земельный участок, BuyLand;
но, по-видимому, достаточно будет использовать то же действие BuyLand,
которое уже было предусмотрено в плане строительства дома. Такая ситуация
будет называться совместным использованием подзадач.
На рис. 12.4 возможности совместного использования подзадач отсутствуют, поэтому создаются новые экземпляры действий. После выбора действий в них копируются все внутренние ограничения из декомпозиции d1, например, такие, что действие Get Permit должно быть выполнено перед действием Construction и что есть причинная связь между этими двумя этапами, обусловливающая выполнение предусловия Permi t действия Construction. На этом задача замены а' конкретизацией декомпозиции d на основе подстановки 0 завершается.
2. На следующем этапе необходимо связать ограничения упорядочения для а ' в
первоначальном плане с этапами декомпозиции d . Вначале рассмотрим лю-
бое ограничение упорядочения в плане Р, которое задано в форме в -< а'.
Как должно быть упорядочено действие в по отношению к этапам декомпо-
зиции d' ? Наиболее очевидное решение состоит в том, что действие В долж-
но быть завершено перед выполнением любого этапа декомпозиции d',
а этого можно добиться, заменяя каждое ограничение в форме Start -< s
в декомпозиции d' ограничением в -< s. С другой стороны, этот подход мо-
жет оказаться слишком жестким! Например, действие BuyLand должно быть
выполнено перед действием BuildHouse, но нет безусловной необходимости, чтобы в расширенном плане покупка земли BuyLand осуществлялась перед наймом подрядчика HireBuilder. Наложив слишком строгое упорядочение, мы можем исключить возможность обнаружения некоторых решений. Поэтому лучший подход состоит в том, чтобы в каждом ограничении упорядочения записывались причины введения этого ограничения; в таком случае при развертывании действия высокого уровня можно будет применять настолько более ослабленные новые ограничения упорядочения, насколько это возможно, в полном соответствии с причиной введения первоначального ограничения. Точно такие же соображения могут применяться при замене ограничений в форме а' -< С.
3. Конечный этап состоит в увязке причинных связей. Если одной из причинных связей в первоначальном плане была в Р >а1, она заменяется множеством причинных связей от В ко всем этапам декомпозиции d1 с предусловиями р, которые выполнены на этапе Start декомпозиции d (т.е. ко всем этапам декомпозиции d", для которых р является внешним предусловием). В данном примере причинная связь BuyLandhand>BuildHouse заменяется связью BuyLand hand>Permi t. (Предусловие Money для действия PayBuilder в этой декомпозиции становится открытым условием, поскольку ни в одном из действий в первоначальном плане не выполнено действие по получению денег Money для строительства дома BuildHouse.) Аналогичным образом, для каждой причинной связи а' Р >С в плане необходимо предусмотреть ее замену множеством причинных связей к С от каждого этапа декомпозиции d', в котором выполняется предусловие р для этапа Finish в декомпозиции d (т.е. от этапа в декомпозиции d", для которого предусловие р является внешним результатом). В данном примере связь BuildHouscHous<> Finish заменяется связью PayBuilder4Finish.
На этом завершаются4 дополнения, требуемые для формирования декомпозиций в контексте применения планировщика POP.
Необходимость в дополнительных модификациях алгоритма POP связана с тем, что действия высокого уровня скрывают информацию об их конечных примитивных реализациях. В частности, в первоначальном алгоритме POP осуществляется возврат с индикатором неудачи, если текущий план включает неразрешимый конфликт, т.е. если одно из действий конфликтует с причинной связью, но не может быть переупорядочено так, чтобы оно находилось до или после этой связи (подобный пример приведен на рис. 11.4). При использовании действий высокого уровня, с другой стороны, с виду неразрешимые конфликты иногда могут быть разрешены путем декомпозиции конфликтующих действий и чередования их этапов. Соответствующий пример приведен на рис. 12.5. Таким образом, может возникнуть такая ситуация, что путем декомпозиции может быть получен полный и согласованный план из примитивных действий, даже если не существует полного и согласованного плана из действий высокого уровня. Такая возможность означает, что полный планировщик HTN не должен использовать многие варианты отсечения, которые предусмотрены для стандартного планировщика POP. Еще один способ организации работы может состоять в том, чтобы отсечение применялось в любом случае, в надежде на то, что ни одно решение не будет упущено.