Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 156
Текст из файла (страница 156)
Планирование и осуществление действий в реальном мире 573 В действии Ясаке этой декомпозиции должны быть предусмотрены все те предусловия действий в плане, которые не предусмотрены в других действиях. Такие предусловия принято называть оа внешними предусловиями. В данном примере внешними предусловиями декомпозиции являются Вапс) (Земельный участок) и Нопеу(Деньги).
Аналогичным образом, все 'ъ внешние результаты, являющиеся предусловиями действия В1п1я)з, представляют собой такие результаты действий в плане, которые не отрицаются другими действиями. В рассматриваемом примере внешними результатами действия Вц11с)ноцяе являются ноияе (Дом) и мопеу(Отсутствие денег). В некоторых планировщиках НТ)х) проводится также различие между сж первичными результатами, такими как Ноияе, и Пх вторичнЫМИ рЕЗУльтатами, такими как Иопеу. Для достижения целей могут использоваться только первичные результаты, тогда как оба рода результатов могут вызывать конфликты с другими действиями; они позволяют в значительной степени сократить пространство поиска'. Декомпозиция должна представлять собой правильный способ осуществления действия.
План с) является правильным способом осуществления действия, если сз— полный и согласованный план с частичным упорядочением для задачи достижения результатов действия а при наличии предусловий действия еь Очевидно, что декомпозиция будет правильной, если она стала результатом применения непротиворечивого планировщика с частичным упорядочением. Библиотека планов может содержать несколько декомпозиций для любого конкретного действия высокого уровня; например, может существовать еше одна декомпозиция для действия Ви11с)нонне, которая описывает такой процесс, что агент возводит дом-самостройку из камней и торфа голыми руками. Каждая декомпозиция должна представлять собой правильный план, но может иметь дополнительные предусловия и результаты, кроме тех, что указаны в описании действия высокого уровня.
Например, декомпозиция для действия Ви11с)Ноияе, показанная на рис. 12.3, кроме земельного участка (Вапс)), требует денег (нопеу), и имеет такой результат, как Нопеу. С другой стороны, вариант с самостройкой не требует денег, но требует большого запаса камней (Носйя) и торфа (Тид1), а также может привести к результату Вас)Вас)с (Больная спина). Учитывая то, что действия высокого уровня, такие как Ви11с)ноияе, могут иметь несколько возможных декомпозиций, нельзя избежать такой ситуации, что их описания действий Бгг1рз будут скрывать некоторые из предусловий и результатов декомпозиций этих действий. Прсдусловия действия высокого уровня должны представлять собой пересечение внешних предусловий возможных декомпозиций этого действия, а результаты — пересечение внешних результатов его декомпозиций.
Иначе говоря, необходимо обеспечить, чтобы предусловия и результаты высокого уровня представляли собой подмножества истинных предусловий и результатов каждой примитивной реализации действия высокого уровня. Следует также отметить две другие формы сокрытия информации. Во-первых, в описании высокого уровня полностью игнорируются все Ъ. внутренние результаты декомпозиций. Например, в декомпозиции действия Ви11с)Ноияе имеются времен- з Это позволяет также предотвратить обнаружение неочевидных планов Например, некоторое лицо, которому грозит процедура банкротства, может избавиться от всех ликвидных активов (т.с.
достичь цели мопеу), купив или построив дом. Этот план полезен, поскольку современные законы запрещают отчуждать в пользу кредиторов основное жилье. 574 Часть 1У. Планирование ные внутренние результаты Рекли' с (наличие разрешения) и акоп спасе (Заключение контракта)'. Во-вторых, в описании высокого уровня не указаны интервалы "внутри" действия, в течение которых должны иметь место предусловия и результаты высокого уровня. Например, предусловие бапс) должно оставаться истинным (в нашей очень упрощенной модели) только до выполнения действия Оесрехзп1с (Получение разрешения), а результат ггоиве становится истинным только после выполнения действия Раупи11с)ег (Оплата работы подрядчика).
Сокрытие информации такого рода становится очень важным, если иерархическое планирование применяется для уменьшения сложности; мы должны иметь возможность рассуждать о действиях высокого уровня, не заботясь о бесчисленных подробностях реализации. Однако за такую возможность приходится платить. Например, могут существовать конфликты между внутренними условиями одного действия высокого уровня и внутренними действиями другого, но способа обнаружить эту ситуацию с помощью высокоуровневых описаний не существует.
Такая проблема оказана значительно влияние на алгоритмы планирования НТ)х). По сути, примитивные действия могут рассматриваться в алгоритме планирования как точечные события, а действия высокого уровня имеют временную протяженность, в пределах которой могут происходить другие всевозможные события. Модификация планировщика для его использования я сочетании с декомпозициями В этом разделе описано, как модифицировать алгоритм РОР для его применения в планировании НТ)х). Для этого мы модифицируем функцию определения преемника РОР (с. 530), чтобы иметь возможность применять методы декомпозиции к текущему частичному плану Р. Новые планы определения преемника формируются так, что вначале выбирается некоторое непримитивное действие а ' в плане Р, а затем для любого лгетода )зесотрояе (а, с)) из библиотеки планов, такого, что а и а ' унифицируются с помощью подстановки О, действие а ' заменяется лекомпозицией с)'=ЯпЬвс(б,с1).
Один из примеров применения такого метода показан на рис. 12.4. В верхней части приведен план Р возведения дома. Для декомпозиции выбирается действие высокого уровня а ' =ви11с)ггоияе. В качестве декомпозиции с) берется план, приведенный на рис. 12.3, и действие пи11г)номаде заменяется этой декомпозицией. Затем вводится дополнительный этап бесбоап (Получение ссуды) для разрешения нового открытого условия )чопеу, которое создается на данном этапе декомпозиции.
Замена действия его декомпозицией немного напоминает пересадку органов в хирургии: мы должны вынуть новый субплан из его упаковки (этапов ясаке и РупуяЛ), вставить его в нужное место и правильно связать сосуды, ткани и нервы. Для решения такой задачи может применяться несколько методов. Точнее, для каждой возможной декомпозиции с) ' должны быть выполнены описанные ниже этапы. Лействие с впвсхиссхоп отрицает результат Регт1 с, поскольку в противном случае одно и то же разрешение можно было бы использовать дпя строительства нескольких домов.
Но, к сожалению, действие сопасхиссгоп нс завершает действие сод Еда се, пОСкОЛьку внаЧаЛе непбходимо расстаться с деньгами и совершить действие раувпхзпек. 576 Часть !хг. Планирование сти, чтобы в расширенном плане покупка земли ВиуЬапс) осуществлялась перед наймом подрядчика нйкевиз1с)ек. Наложив слишком строгое упорядочение, мы можем исключить возможность обнаружения некоторых решений. Поэтому лучший подход состоит в том, чтобы в каждом ограничении упорядочения записывались причины введения этого ограничения; в таком случае при развертывании действия высокого уровня можно будет применять настолько более ослабленные новые ограничения упорядочения, насколько это возможно, в полном соответствии с причиной введения первоначального ограничения.
Точно такие же соображения могут применяться при замене ограничений в форме а ' ы С 3. Конечный этап состоит в увязке причинных связей. Если одной из причинных связей в первоначальном плане была  — д — за', она заменяется множеством причинных связей от В ко всем этапам декомпозиции с)' с предусловиями р, которые выполнены на этапе Ясакс декомпозиции с) (т.е. ко всем этапам декомпозиции с1', для которых р является внешним предусловием). Вланном примере причинная связь ВиузапсИМВиз1г?Воине заменяется связью Виуз апйшзн Рекш?г.
(Предусловие мапеу для действия Раупи?1с)ек в этой декомпозиции становится открытым условием, поскольку ни в одном из действий в первоначальном плане не выполнено действие по получению денег нопеу для строительства дома Низ?с)Ноинск) Аналогичным образом, для каждой причинной связи а' — л-зС в плане необходимо предусмотреть ее замену множеством причинных связей к С от каждого этапа декомпозиции с1', в котором выполняется предусловие р для этапа Рзпйнй в декомпозиции с) (т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
