Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 164
Текст из файла (страница 164)
С этого момента перепланировщик должен автоматически выработать альтернативный план, который состоит в получении нового ключа. Такого рода обучение рассматривается в главе 21. Даже несмотря на все эти потенциальные усовершенствования, перепланируюший агент все еше обладает несколькими недостатками. Он не может действовать в тех вариантах среды, где все происходит в реальном времени, и не сушествует пределов количества времени, которое он может затратить на перепланирование, ги поэтому нет пределов времени, в течение которого он решится на выполнение какогото действия. Кроме того, данный агент не способен формулировать новые цели самостоятельно или принимать к исполнению новые цели, дополнительно к его текущим целям, поэтому такой агент не сможет долго сушествовать в сложной среле.
Указанные недостатки будут устранены в следуюшем разделе. и Бессмысленное повторение одного н того же способа исправления плана полностью повторяет поведение. которое демонстрирует осв-сфскс (см с 81). 600 Часть 1Ч. Планирование 12.6. НЕПРЕРЫВНОЕ ПЛАНИРОВАНИЕ В этом разделе рассматривается проект агента, способного существовать в некоторой среде неопределенно долго. Поэтому он не является "решателем задач", который получает единственную цель, а затем составляет план и действует до тех пор, пока эта цель не будет достигнута; скорее, данный агент сугцествует, проходя через целые ряды этапов формулировки постоянно меняющихся целей, планирования и осушествлення действий. Вместо трактовки процессов планирования и контроля выполнения как отдельных процессов, один из которых передает свои результаты другому, их можно рассматривать как единый процесс, осуществляемый 'ж непрерывно планирующим агентом (сопгшцоцз р1апп)пя айеп1). Такого агента можно рассматривать как находяшегося постоянно в ситуации осушествления плана — грандиозного плана прожития его жизни.
Его деятельность включает выполнение некоторых этапов плана, готовых к выполнению, уточнение плана для удовлетворения открытых предусловий или разрешения конфликтов, а также модификацию плана в свете дополнительной информации, полученной во время его выполнения. Очевидно, что агент, впервые приступая к формулировке новой цели, не будет иметь в своем распоряжений действий, готовых для выполнения, поэтому он потратит некоторое время на выработку частичного плана. Однако вполне возможно, что агент начнет выполнение плана еше до того, как разработка плана будет полностью закончена, особенно если в нем имеются независимые подцели, которых требуется достичь уже сейчас. Непрерывно планирующий агент постоянно контролирует состояние мира, обновляя свою модель мира по новым результатам восприятия, даже если его размышления над планом еще продолжаются.
Вначале рассмотрим один пример, а затем опишем программу агента, которая полу пила название Сопсьпиоцэ-РОР-Адепс, поскольку в ней для представления намеченной деятельности используются планы с частичным упорядочением. Чтобы упростить это представление, мы будем предполагать наличие полностью наблюдаемой среды. Те же самые методы могут быть распространены и на частично наблюдаемый случай. В качестве примера рассматривается задача из проблемной области мира блоков (раздел 11.1).
Начальное состояние показано на рис. 12.10, а. Нам потребуется действие мот е (х, у), в котором блок х перемешается на блок у, при условии, что обе их верхние поверхности являются свободными. Схема этого действия состоит в следующем: лоедоп(моъе(х,у), Вгеооп(): Сзеаг(х) л Сзеаг(у) л Оп(х,а), дгдесс: оп (х,у) л С1еаг(а) л Оп (х,а) л — С1еаг(у) ) Агенту вначале необходимо сформулировать для себя цель. Здесь мы не будем обсуждать процесс формулировки цели, а вместо этого предположим, что агенту было дано заданиедостичь цели Оп(С, Р) л Г)п((з, В) (или он принял это решение самостоятельно).
Агент начинает планировать действие по достижению данной цели. В отличие от всех других описанных в этой книге агентов, которые отключают все свои восприятия до тех пор, пока планировщик не вернет полное решение данной задачи, непрерывно планируюший агент формирует свой план поэтапно, затрачивая на каждый этап ограниченное количество времени. После каждого этапа планирования агент возвращает в качестве своего действия пустую операцию )(ГоОр и снова 602 Часть!У.
Планирование Омане(Л ап(вСй — с',ь) Оп(С,() анап ап(в',в) с(нм (л) Оеае(С) Оеае(ц) с( (ь) а(срв([, „, ) Рис. 12. 12. После того как некта пастараннии перемещает блок и на блок в, ненаддерзкиваемые связи, создающие предуславия санах (в) и оп (р, о), уничтожаются, в результате чего созда- ется наказанный здесь еыан Теперь агент может воспользоваться преимушеством этого "полезного" вмешательства, обнаружив, что причинная связь )чоче ()з, л) ал ю ч' Рзпз в)з может быть заменена прямой связью от состояния Бсасс к состоянию Рзпзн)з. Этот процесс называется гас продлением (ех(епвйоп) причинной связи и осуществляется каждый раз, когда некоторое условие может быть взято из более раннего, а не более позднего этапа без создания нового конфликта.
После удаления старой причинной связи от моче(гз, В) к Рзпзв)з действие моче(п, в) больше не поддерживает вообще какие-либо причинные связи. Теперь оно становится 'ах избыточным этапом (ге()цпе)апг мер). Все избыточные этапы и все поддерживающие их связи удаляются из плана. В результате создается план, показанный на рнс. ) 2. ) 3. о иьыл ап(В е) Е:Л ', оп(Сг) З(ап оп(п',в) Оеайл( с((юцО с(еацрз с(папа) ап(срв( Г ... „) Рис. 12.13. Связь, поддерживаемая действием моче (о, в), теперь заменена связью, проходящей ат состояния всасс, а зпеап моче (и, в), ставший избытачным, удален После этого стал готовым к выполнению этап моче(С, (З), поскольку все его предусловия выполнены на этапе Бсахс, перед ним не требуется проходить какие- либо другие этапы и он не конфликтует с какой-либо другой связью в плане.
Данный этап удаляется из плана и выполняется. К сожалению, агент допустил оплошность и уронил блок с на блок л, вместо того чтобы поставить его на гз, поэтому было получено состояние, показанное на рис. ) 2.)0, в. Новое состояние плана приведено на рис. ) 2.! 4. Обратите внимание на то, что в плане нет новых действий, но все еще остается открытое условие для этапа Рзпз в)х Оаеаые АЗ ап(в е~ Е:Л '',, ап(с',л З(ап ап(а',в) Оеад ) Саы (с) Оеапрз Оаю (с) ап(с ив) ~ Рис.
12.14. После того как действие моче (с, и) выпалнена и удалено из плана, результаты зпеа- па в сакс отражают тат факт, чта в конечном итоге блок с оказался на блике рч а не на блоке и, для устанавки на котором ан предназначался. Предуславие цели оп (С, и) все еще открыто 603 Глава 12. Планирование и осуществление действий в реальном мире ОмаЫегл Оа(В, В) ЕЛ Оа(С.'Л) тае( Оа(О,В) Сгеа,' 1 с~еачсс Оеае(Ю Сгеае(ьз О (цт Оа(О,В) кнезь Рис. !2.
15. Открытое предусловие удовлетворяется за счет повторного введения в план действия номе (с, п). Обратите внимание на то, что для предусловии применяются новые связывания Действие втоОЕ ( С, И) снова готово к выполнению. На этот раз оно завершается успешно и достигается целевое состояние, показанное на рис. 12.10,г.
После удаления данного этапа из плана целевое условие Оп (С, Р) снова становится открытым. Но поскольку этап ясаке обновлен и в нем отражено новое состояние мира, целевое условие может быть немедленно выполнено с помощью связи от этапа бсакс. Таковььм является обычный ход событий, когда какое-то действие оказывается успешным. Конечное состояние данного плана показано на рис. 12.16. Поскольку все целевые условия удовлетворяются этапом 8сакс и больше нет оставшихся действий, агент теперь вправе удалить все подцепи из состояния Ипз О)з и сформулировать новую цель. ОаеаЫе(А) оа(в ц Е:Л„в,," о (с',О) о.(двр О.(ст О (О,лг Ввйь Рис.
12.1б. После того как действие номе (с, п) вьяолняется и удаеяется из плана, остившссся открытое условие оп (с, и) может быть разрешено путем добавления причиннои связи от нового этапа Бепсе. Теперь выполнение плана закончено Из этого примера ясно, что непрерывное планирование весьма напоминает гшанирование с частичным упорядочением. В каждой итерации алгоритм находит чтото, касающееся плана, что требует исправления (так называемые аь дефекты плана — р1ап йазн), и исправляет это положение. Сам алгоритм РОР также может рассматриваться как алгоритм устранения дефектов, в котором учитываются два лсфекта: открытые предусловия и конфликты причинных связей.
Непрерывно планирующий агент, с другой стороны, справляется с гораздо более широким перечнем дефектов, которые описаны ниже. ° Недостающие цели. Агент может принять решение по добавлению в состояние Рзпзэ)З НОВой целИ или целей. (При непрерывном планировании было бы больше смысла применять вместо названия Рзпзэ)з название 2ОЕзпьс)г, а вместо о Саке — Сцссеп С, но авторы будуг придерживаться установившейся традиции.) ° Открытые предусловия. Агент добавляет причинную связь к открытому предусловию, выбирая либо новое, либо существующее действие (как в алгоритме РОР).
Агент решает составить план для этого открытого условия. Опять-таки целевое условие будет выполнено с помощью действия втоз е( с, гз) . Его предусловия удовлетворяются за счет новых причинных связей от этапа осаке. Новый план приведен парис. 12.\5. 604 Часть 1Ч. Планирование ° Конфликты причинных связей. При наличии причинной связи А — д-эв и действия С с результатом — р агент для разрешения этого конфликта выбирает ограничение упорядочения или ограничение переменной (как в алгоритме РОР). ° Неподдерживаемые связи. Если есть причинная связь Ясаке — в-эл, где предикат р больше не является истинным в состоянии осагс, агент удаляет эту связь (что позволяет предотвратить выполнения действия, предусловия которого являются ложными.) ° Избыточные действия.
Если какое-то действие А не обеспечивает выполнения ни одной причинной связи, агент удаляет и это действие, и его связи (что позволяет ему воспользоваться преиму)деством удачно сложившихся обстоятельств.) ° невыполненные действия. если некоторое действие л (отличное от рйпза)з) имеет все выполненные прсдусловия в состоянии ясагс, не связано с упорядоченными перед ним другими действиями (кроме ясаке) и не конфликтует ни с одной причинной связью, агент удаляет из плана действие А вместе с сто причинными связями и возвращает его как действие, которое должно быть выполнено. ° Ненужные, существовавшие в прошлом цели.
Если в плане нет открытых предусловий и нет действий (поэтому все причинные связи проходят непосредственно от состояния Ясагс к состоянию рулйз)з), то текущее множество целей достигнуто. Агент удаляет эти цели и связи, ведущие к ним, чтобы освободить место для новых целей. Алгоритм Сопсзпцопз-РОР-Адепп приведен в листинге 12.6. В нем имеется цикл "принять результаты восприятия, удалить дефекты, выполнить действие".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
