Представление декомпозиций действий
Общие описания методов декомпозиции действий хранятся в библиотеке планов, из которой они извлекаются и конкретизируются для обеспечения потребностей формирования текущего плана. Каждый метод представляет собой выражение в форме Decompose (а, с?). Это выражение указывает, что может быть выполнена декомпозиция действия а на план с?, представленный в виде плана с частичным упорядочением, как описано в разделе 11.3.
Строительство дома — это прекрасный, конкретный пример, поэтому мы будем использовать его для иллюстрации концепций декомпозиции действия. На рис. 12.3 показана одна возможная декомпозиция действия BuildHouse на четыре действия низкого уровня, а в листинге 12.3 приведены некоторые из описаний действий для данной проблемной области, а также декомпозиция действия BuildHouse в том виде, в каком она могла бы присутствовать в библиотеке планов. В этой библиотеке могут находиться также другие возможные декомпозиции.
Листинг 12.3. Декомпозиции действий для задачи построения дома и подробная декомпозиция для действия BuildHouse. В этих декомпозициях приняты упрощенное представление о деньгах, а также оптимистическое представление строителей в отношении перспектив оплаты
Act ion {BuyLand, Precond: Money, Effect: Land A -nMoney)
Action[GetLoan, Precond: GoodCredit, Effect: Money A Mortgage)
Action{BuildHouse, Precond: Land, Effect: House)
Action{GetPermit, Precond: Land, Effect: Permit)
Action(HireBuilder, Effect: Contract)
Action(Construction, Precond: Permit A Contract,
Effect: HouseBuilt A -Permit) Action(PayBuilder, Precond: Money A HouseBuilt,
Effect: -лМопеу A House A -Contract)
Decompose(BuildHouse,
Plan(Steps: {Sn GetPermit, S2: HireBuilder,
S3: Construction, Si: PayBuilder) Orderings: {Start ?< Si ?< S3 -< ?4 -< Finish, Start ?< S2 ?< S3}, Links: { Start-Slt StartS*.
g Permit Contry t HouseBiy.lt
S*Finish, S*-?Finish) )
В действии Start этой декомпозиции должны быть предусмотрены все те предусловия действий в плане, которые не предусмотрены в других действиях. Такие предусловия принято называть внешними предусловиями. В данном примере внешними предусловиями декомпозиции являются Land (Земельный участок) и Money (Деньги). Аналогичным образом, все внешние результаты, являющиеся предусловиями действия Finish, представляют собой такие результаты действий в плане, которые не отрицаются другими действиями. В рассматриваемом примере внешними результатами действия BuildHouse являются House (Дом) и -тМопеу (Отсутствие денег). В некоторых планировщиках HTN проводится также различие между первичными результатами, такими как House, и вторичными результатами, такими как -iMoney. Для достижения целей могут использоваться только первичные результаты, тогда как оба рода результатов могут вызывать конфликты с другими действиями; они позволяют в значительной степени сократить пространство поиска2.
Декомпозиция должна представлять собой правильный способ осуществления действия. План d является правильным способом осуществления действия, если d — полный и согласованный план с частичным упорядочением для задачи достижения результатов действия а при наличии предусловий действия а. Очевидно, что декомпозиция будет правильной, если она стала результатом применения непротиворечивого планировщика с частичным упорядочением.
Библиотека планов может содержать несколько декомпозиций для любого конкретного действия высокого уровня; например, может существовать еще одна декомпозиция для действия BuildHouse, которая описывает такой процесс, что агент возводит дом-самостройку из камней и торфа голыми руками. Каждая декомпозиция должна представлять собой правильный план, но может иметь дополнительные предусловия и результаты, кроме тех, что указаны в описании действия высокого уровня. Например, декомпозиция для действия BuildHouse, показанная на рис. 12.3, кроме земельного участка (Land), требует денег (Money), и имеет такой результат, как -.Молеу. С другой стороны, вариант с самостройкой не требует денег, но требует большого запаса камней (Rocks) и торфа (Turf), а также может привести к результату BadBack (Больная спина).
Учитывая то, что действия высокого уровня, такие как BuildHouse, могут иметь несколько возможных декомпозиций, нельзя избежать такой ситуации, что их описания действий Strips будут скрывать некоторые из предусловий и результатов декомпозиций этих действий. Предусловия действия высокого уровня должны представлять собой пересечение внешних предусловий возможных декомпозиций этого действия, а результаты — пересечение внешних результатов его декомпозиций. Иначе говоря, необходимо обеспечить, чтобы предусловия и результаты высокого уровня представляли собой подмножества истинных предусловий и результатов каждой примитивной реализации действия высокого уровня.
Следует также отметить две другие формы сокрытия информации. Во-первых, в описании высокого уровня полностью игнорируются все внутренние результаты декомпозиций. Например, в декомпозиции действия BuildHouse имеются временнь/е внутренние результаты Permit (Наличие разрешения) и Contract (Заключение контракта)3. Во-вторых, в описании высокого уровня не указаны интервалы "внутри" действия, в течение которых должны иметь место предусловия и результаты высокого уровня. Например, предусловие Land должно оставаться истинным (в нашей очень упрощенной модели) только до выполнения действия GetPermit (Получение разрешения), а результат House становится истинным только после выполнения действия PayBuilder (Оплата работы подрядчика).
Сокрытие информации такого рода становится очень важным, если иерархическое планирование применяется для уменьшения сложности; мы должны иметь возможность рассуждать о действиях высокого уровня, не заботясь о бесчисленных подробностях реализации. Однако за такую возможность приходится платить. Например, могут существовать конфликты между внутренними условиями одного действия высокого уровня и внутренними действиями другого, но способа обнаружить эту ситуацию с помощью высокоуровневых описаний не существует. Такая проблема оказала значительно влияние на алгоритмы планирования HTN. По сути, примитивные действия могут рассматриваться в алгоритме планирования как точечные события, а действия высокого уровня имеют временную протяженность, в пределах которой могут происходить другие всевозможные события.