Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 144
Текст из файла (страница 144)
Ограничения упорядочения должны описывать правильный вариант частичного упорядочения. Любой цикл (такой как А с В и В к А) представляет противоречие, поэтому ни одно ограничение упорядочения не может быть добавлено в план, если оно создает цикл. быть применены, и не залумываться над тем, каким образом алгоритм осуществляет исследование пространства поиска.
В действительности после формулировки задачи поиска может быть применен широкий перечень неинформированных или эвристи- ческих методов поиска. 530 Часть 1Ч. Планирование ° Множество ск причинных связей. Причинная связь между двумя действиями л и В в плане записывается как А.— я->В и читается как "л ъ. достигает р для В". Например, в следуюшей причинной связи: К>дпвзоск>кокто-ово Яхд)>СБ)>се утверждается, что кед)> сяос)сОп (надет правый носок) представляет собой результат деиствия Кдд)>едос)с и предусловие действия кдд)>сЯ)>се. В ней также содержится утверждение, что предусловие кхд)>ЕЯос)гоп должно оставаться истинным со времени действия куд)>сяос)с до времени действия КудйСЯпое.
Другнмн СЛОвами, пЛан не может быть дополнен путем добавления какого-либо нового действия с, которое 'ш. конфликтует с причинной связью. Действие С конфликтует со связью А — а-~В, если С имеет результат — р и если С может (в соответствии с ограничениями упорядочения) происходить после л и перед в. Некоторые авторы называют причинные связи интервалами защиты, поскольку связь л.— в->В зашишает предусловие р от его отрицания в интервале отлдо в.
° Множество 'ж открытых предусловий. Предусловие является открытым, если оно не достигнуто с помошью какого-то действия в плане. Планировщики действуют по принципу сокрашения множества открытых предусловий до пустого множества без внесения противоречия. Например, окончательный план, показанный на рис. 11.2, имеет следуюшие компоненты (не показаны ограничения упорядочения, которые распространяются на каждое действие после действия ясаке и перед действием купу вй): действия: (яздйсяоск, Кхдйгвйое, ЬеЕСьос)о, ЬеЕСВ)>се, Беате, Кзпдя)>) упорядочения> 1яедйгдоск и кед)>сд)>ее, ьеесяос)о и ьеесялое) Связи: 1 Кхдйгвосн к оьоо — ко'"Кзд)>С")>се, ДеЕСБос)с"е>ов око г.еЕСс)>се, кедлсдьое к'о-'"-~и"'~"Вепев)>, йеесдпое" -т — "~ "Вепея)>) Открытые препусповия: () мы определяем 'а.согласованный план (сопямеп) р)ап) как план, в котором не имеется циклов в ограничениях упорядочения и нет конфликтов с причинными связями.
Согласованный план без открытых предусловий представляет собой решение. Даже краткие размышления должны убедить читателя в справедливости следующего утверждения: озе каждая лш>еаризания решения с частичным упорядочением представляет гобой решение с полным упорядочением, выполнение которого из начального сотпояния позволяет достичь Иелевого состояния.
Это означает, что можно распространить понятие "выполнения плана" с планов с полным упорядочением на планы с частичным упорядочением. План с частичным упорядочением выполняется путем повторного выбора любого из возможных следующих действий. Как будет показано в главе 12, такая гибкость, предоставляемая агенту в ходе выполнения плана, может быть очень полезной в тех обстоятельствах, когда мир к нему не благосклонен. Гибкое упорядочение позволяет также упростить комбинирование меньших планов в более крупные, поскольку каждый из меньших планов допускает переупорядочение его действий для предотврашения конфликтов с другими планами.
Теперь мы готовы сформулировать задачу поиска, которую решает алгоритм рОр, как показано ниже. Начнем с формулировки, подходяшей для задач планирования в пропозициональной логике, оставляя на будушее осложнения, связанные с исполь- Глава 11. Основы планирования 531 зованием логики первого порядка. Как обычно, это определение включает началь- ное состояние, действия и проверку цели.
° Начальный план содержит действия ясаке и гзпза)ь ограничение упорядочения яса гс -~ Гзпзао, не включает ни одной причинной связи и имеет все предусловия в действии Рзпуай в качестве открытых предусловий. ° Функция определения преемника произвольным образом выбирает одно открытое предусловие р действия в и вырабатывает план-преемник лля каждого возможного согласованного способа выбора действия д, которое достигает р. Согласованность обеспечивается принудительно следующим образом. 1.
Причинная связь л — в-~н и ограничение упорядочения д ~ в добавляются к плану. Действие л может быть существующим действием в плане или новым действием. Если оно является новым, добавить его к плану, а также добавить ясагс -~ А и А -~ Рупа ай, 2. Разрешаются конфликты между новой причинной связью и всеми существующими действиями, а также между действием А (если оно является новым) и всеми существующими причинными связями. Конфликт между А — а — >в и С разрешается путем обеспечения того, чтобы лействие С происходило в какое-то время за пределами интервала зашиты, либо за счет добавления ограничения в -~ С, либо путем добавления ограничения С -с д. Для одного из них или обоих добавляются состояния-преемники, если они приводят к созданию согласованных планов.
° В ходе проверки цели осуществляется проверка того, является ли текущий план решением первоначальной задачи планирования. Поскольку вырабатываются только согласованные планы, в проверке цели достаточно только проконтролировать, есть ли еше открытые предусловия. Еше раз напомним, что действия, рассматриваемые в алгоритмах поиска при такой формулировке, представляют собой этапы уточнения плана, а не реальные лействия из самой проблемной области. Поэтому, строго говоря, стоимость пути не имеет значения, поскольку важна только суммарная стоимость реальных действий в плане, к которому ведет этот путь.
Тем не менее сугцествует возможность определить функцию стоимости пути, которая отражает стоимости реальных планов; для этого можно назначать цену 1 за каждое реальное действие, добавленное к плану, и 0 — за все остальные этапы уточнения. В таком случае значение функции ц(п), где ив некоторый план, будет равно количеству реальных действий в плане. Может также исгюльзоваться эвристическая оценка )з (и ) . На первый взгляд может показаться, что функция определения преемника должна вырабатывать преемников для каждого открытого предусловия р, а не только для одного из них. Но такой подход был бы избыточным и неэффективным по той же причине, по которой алгоритмы удовлетворения ограничений не включают преемников для каждой возможной переменной, поскольку порядок, в котором рассматриваются открытые предусловия (как и порядок, в котором рассматриваются переменные СЯР), является коммугативным (см.
с. 214). Таким образом, мы можем выбирать произвольное упорядочение и все еше иметь полный алгоритм. Выбор правильного упорядочения может привести к более быстрому поиску, но все упорядочения оканчиваются одним и тем же множеством решений-кандидатов. 532 Часть 1Ч. Планирование Пример планирования с частичным упорядочением Теперь рассмотрим, как можно с помощью алгоритма РОР решить задачу с запасным колесом, описанную в разделе 11.1. Описание этой задачи повторно приведено в листинге 11.4.
Листинг 11.4. Описание простой задачи замены колеса со стертой покрышкой тп 'С (Лс(Р1аС,Я 1е) л ЛС(Браге, т пн) ) Ооа1(АС(Браге,Ах1е)) АССхоп(нетоие(Брате, Тгипн), Ртесспсн АС(Бра~в, Тгипк) ЕСьесС: - Ас(Браге, Тгип)г) л Ас( Брате, Огоипс))) Лсгтоп(летсие(51аС,Лх1е), Ртесопси лс(Р1ас,лх1е) Еттесе; АС(взаС, Ах1е) л АС (Р1аС, СгоипЯ ) АсСхоп(Рисоп(Брате, Ах1е), Ртесопш АС( Брате, Огоипе)) л АС(Р1ас, Лх1е) ЕССесте АС(Брате, ОгоипЯ л Ас(Брате,Ах1е)) Ассе оп (Ьеачеочетп1БПС, Ртесопс)г Естест г Ас( Браге, ОтоипЯ л Ас(Браге, Ах1е) л АС ( рате, Тгипк) л АС(Р1ас, Отоипг)) л †,АС(Р1ае,лх1е)) Поиск решения начинается с начального плана, содержащего действие Бсагс с результатом Ас (Браге, тгип)г) л Ас (Р1ас, Ах1е) и действие Рйпйа)з с единственным предусловием Ас (Браге, Ах1е) .
Затем вырабатываются преемники путем взятия открытого предусловия для его проработки (не допускающей отмены) и выбора среди возможных действий для его лостижения. На данный момент мы не будем задумываться над тем, что нужно воспользоваться какой-то эвристической функцией, которая могла бы помочь в выработке этих решений, и станем выбирать варианты, которые внешне кажутся произвольными. Последовательность событий описана ниже.
1. Взять единственное открытое иредусловие, АС (Браге, Лх1 е), действия Рйпйа)з. Выбрать единственное применимое действие, Ри С Оп ( Браге, Ах1 е) . 2. Взять предусловие Ас (Браге, ~гоипс)) действия Ри СОп ( Браге, Ах1е) . Выбрать единственное применимое действие, нешоие(Браге, Тгип)с), чтобы достичь его. Результирующий план показан на рис. 11.3. Аг(5реш,Тшег) М(5ре ш, Тшег) ~::Л Б(яи АГ(нееЛ Ь) АГ(5~ашлшееа) Ритон(Браге,лх)ь) Аг(злеш 4х/е) ~~~~ай АГ(нее,4х)е) Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
