Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 160
Текст из файла (страница 160)
12.6. Первые два уровня дерева поиска для мира пылесоса с "двойньал законом Мэрфи ". Узлами состояния являюп~ся узлы ОЯ, в которых должно быть вьы брало неколюрое действие. Узлы жеребьевки, показанные в виде кружков, являются узлами АФП, для которых требуется упитывать все результаты, как показывает кривая линия, соединяющая исходящие ветви. Рещение показано жирными линиями Для получения точных решений в играх используется алгоритм минимакса (см. листинг б.1), а для условного планирования обычно применяются две его модификации. Во-первых, узлы МАХ и М1Х могут быть преобразованы в узлы ОК и АХР. Интуитивно кажется очевидным, что в плане требуется предпринимать некоторые действия в каждом достигнутом в нем состоянии, но должны учитываться все результаты предпринятого действия. Во-вторых, алгоритм должен возврашать условный план, а не просто отдельный ход.
В узле ОК план состоит в выборе действия, за которым следует то, что должно произойти. А в узле А)к) Р план представляет собой вложенный ряд этапов "1à — г)теп — е!зе" с определением субпланов для каждого результата; проверки в этих этапах возврашают полные описания состояния'.
Формально говоря, опрелеленное нами пространство поиска представляет собой граф АХР— ОК. В главе 7 графы АХР— ОК рассматривались в контексте пропозиционального вывода на основе хорновских выражений, а в этой главе ветвями являются действия, а не этапы логического вывода, но алгоритм остается тем же самым. В листинге 12.4 приведен рекурсивный алгоритм поиска в глубину, предназначенный для поиска в графе АХР— ОК.
Одной из ключевых особенностей этого алгоритма является тот способ, с помошью которого он справляется с циклами, часто возникаюшими в задачах недетерминированного планирования (например, если какое-то действие иногда не имеет з Такис планы можно также составлять с использованием конструкции саве. Глава ]2. Планирование и осуществление действий в реальном мире 587 результата или если может быть исправлен нежелательный результат). Если текущее состояние идентично одному из состояний в пути от корня, то алгоритм выполняет возврат с индикатором неудачи. Это не означает, что нет решения, достижимого из текущего состояния; просто такая ситуация свидетельствует о том, что если есть не- циклическое решение, оно должно быть достижимым из более раннего воплощения текущего состояния, поэтому его новое воплощение может быть отброшено.
С помощью этой проверки можно гарантировать, что алгоритм завершит свою работу в любом конечном пространстве состояний, поскольку каждый путь должен достигнуть цели, тупика или повторяющегося состояния. Обратите внимание на то, что в алгоритме не осуществляется проверка, не является ли текущее состояние повторением какого-то состояния в каком-то другом пути от корня; этот вопрос исследуется в уп р.
! 2. ! 5. Листинг 12.4. Алгоритм поиска в графах А]чП-ОК, сформированных в условиях недетерминироааниых вариантов среды. Предполагается, что функция Биосвввогв возвращает список действий, каждое из которых связано с множеством возможных результатов. Задача состоит в том, чтобы найти условный план, который достигает целевого состояния во всех обстоятельствах Еипоеаоп Апс(-Ох-Огарн-Яеагон(рхоЬ1ем) геепгпв условный план или индикатор неудачи Еа11ихе Ог-эеахсц(1пьеьа1-ЯСаее[рхоЫет], рхоЬ1ет, []) Еппоезоп Ог-эеагсн(аеаСе, рхоЬ1езп, раСЛ) геепгпв условный план или индикатор неудачи Еа11ихе зЕ Ооа1-Тевг[рхоЫет](аеаее) Сноп гоепгп пустой план аЕ состояние аеаСе входит в состав раСЛ Снеп гееигп Еа11ихе Еог еасн аоС1ол, леаеа аеС зп Биосеавога[рхоЫет](агаге) До р1ап г — Апс(-Беагсн(асасе аес, рхоЪ1ет, [асасе]расл]) Ее р1ап Ф Еа11ихе снеп гесигп [аос1оп]р1ал] геепгп Еа11иге Еппсейоп Алс)-Беагсн(асасе аес, рхоЫет, расЛ) геспгпв условный план или индикатор неудачи Еа11ихе Еог еасн а, Еп аеаге аеС с(о р1ап, г — Ог-Беагсъ(а,, рхоЫет, расЫ ЕЕ р1ал = Еа11ихе Снеп геепгп Еа11ихе геепгп [ЕЕ аг Сиеп р1алз езве зЕ аг Сноп р1ал, езве ЕЕ а г Сцен р1альа езве р1ал,] Планы, возвращаемые алгоритмом Апс]-Ох-ОхарЛ-Яеахс]т, содержат условные шаги, в которых проверяется описание всего состояния для выбора следующей ветви.
Но во многих случаях можно справиться с этой работой с помощью менее исчерпывающих проверок. Например, план решения на рис. [2.6 может быть записан просто как [леЕс, Ее с1еапл с[топ [] е1не Бцс]с]. Это связано стем, чтодостаточно провести единственную проверку, С2еаль, для разделения состояния в узле АХР на два одноэлементных множества, чтобы после проверки агент мог точно определить, в каком состоянии он находится. В действительности проведение ряда проверок по принципу "[Š— (йеп — е!зе" отдельных переменных всегда позволяет разделить множество состояний на одноэлементные множества, при условии, что среда является полностью наблюдаемой. Поэтому можно без потери общности ограничиться проведением проверок отдельных переменных. 588 Часть (У.
Планирование В недетерминированных проблемных областях часто возникает еше одна, последняя сложность: не всегда удается выполнить текущую операцию с первого раза, поэтому приходится предпринимать еше одну попытку. Например, рассмотрим пылесос в мире с "тройным законом Мэрфи", который (кроме ранее указанных его недостатков) иногда отказывается переходить туда, куда требует переданная ему команда, например, действие ьебс может иметь дизъюнктивный результат АСЬ м Аед, КаК В ураВНЕНИИ 12.1. ТЕПЕРЬ ужЕ НЕЛЬЗЯ ГараНтИрОВатЬ, ЧтО ПЛаН (ьебс, йй С2еапь е]зезз (1 е1ве ецс]с] будет работать.
Часть нового графа поиска показана на рис. 12.7; очевидно, что больше нет каких-либо нециклических решений и алгоритм Апс]-Ох-Сгар]з-Яеакс]з выполняет возврат с индикатором неудачи. Тем не менее существует 'в. циклическое решение, которое заключается в том, что нужно продолжать попытки выполнять действие ьебс до тех пор, пока одна из попыток не достигнет успеха. Это решение можно выразить, введя 'в. метку для обозначения некоторой части плана и используя эту метку позднее, вместо повторения самого плана. Таким образом, соответствующее циклическое решение может выглядеть таким образом: (ь,: ьебс, йй Асл Е]зев Ь, е1ве 1й С1еапЬ Еиеп (] е1ве лис]с] Рис.
72.7. Первый уровень графа поиска для мира пылесоса, подчиняющегося бтроиному закону Мэрфи", гд» циклы показаны явно. Все решения для данной задачи предсюавляюш собой циклические планы (Более удобный синтаксис для циклической части этого плана мог бы предусматривать применение конструкции "м]з11е Ае]г сзо ьеГе".) Изменения, необходимые для внесения в алгоритм Апс]-Ок-беар]з-пеагс]з, рассматриваются в упр.
12.1б. Из этого следует основной вывод, что цикл в пространстве состояний, ведущий в состояние Ь, преобразуется в цикл в плане, ведущий в ту точку, где выполнялся субплан для состояния Ь. Теперь мы получили возможность синтезировать сложные планы, которые во многом выглядят как программы, с условными выражениями и циклами. К сожалению, эти циклы, в принципе, могут стать бесконечными.
Например, в представлении действия для мира с "тройным законом Мэрфи" ничего не сказано, что действие ьеГс в конечном итоге закончится успешно. Поэтому циклические планы не столь желательны, как ациклические, но вполне могут рассматриваться как решения, при условии, что каждый листовой узел представляет собой целевое состояние и любой листовой узел достижим из каждой точки в плане. 589 Глава 12. Планирование и осуществление действий в реальном мире Условное планирование в частично наблюдаемых вариантах среды В предыдущем разделе рассматривались полностью наблюдаемые варианты среды, преимущество которых состоит с том, что во время условных проверок можно задавать любые вопросы и быть уверенным в том, что будет получен ответ.
Но в реальном мире гораздо чаше встречается частичная наблюдаемость. В начальном состоянии частично наблюдаемой задачи планирования агент обладает лишь некоторым объемом знаний о действительном состоянии. Простейший способ промоделировать такую ситуацию состоит в том, чтобы принять предположение, что начальное состояние принадлежит к множеству состояний; множество состояний представляет собой способ описания начального доверительного состояния агента'. Предположим следующее: агенту в мире пылесоса известно, что он находится в правом квадрате и что этот квадрат чист, но он не может определить с помощью датчиков наличие или отсутствие мусора в других квадратах.
В таком случае, насколько известно агенту, он может находиться в одном из двух состоянии: левый квадрат может быть либо чистым, либо грязным. Это доверительное состояние обозначено на рис. 12.8 буквой л. На этом рисунке показана часть графа А)ч(Р— ОК для мира пылесоса с "альтернативным двойным законом Мэрфи", в котором мусор может иногда оставаться сзади, после того как агент покидает чистый квадрат'. Если бы этот мир был полностью наблюдаемым, то агент имел бы возможность сформировать циклическое решение в такой форме: "Продолжать двигаться влево и вправо, всасывая мусор везде, гле он появляется, ло тех пор, пока оба квадрата не станут чистыми, а я не буду находиться в левом квадрате" (см, упр. 12.!6). К сожалению, при использовании лишь локального датчика грязи этот план является невыполнимым, поскольку невозможно определить истинностное значение проверки "оба квадрата стали чистыми".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
