НЕПРЕРЫВНОЕ ПЛАНИРОВАНИЕ

В этом разделе рассматривается проект агента, способного существовать в некоторой среде неопределенно долго. Поэтому он не является "решателем задач", который получает единственную цель, а затем составляет план и действует до тех пор, пока эта цель не будет достигнута; скорее, данный агент существует, проходя через целые ряды этапов формулировки постоянно меняющихся целей, планирования и осуществления действий. Вместо трактовки процессов планирования и контроля выполнения как отдельных процессов, один из которых передает свои результаты другому, их можно рассматривать как единый процесс, осуществляемый непрерывно планирующим агентом (continuous planning agent).
Такого агента можно рассматривать как находящегося постоянно в ситуации осуществления плана — грандиозного плана прожития его жизни. Его деятельность включает выполнение некоторых этапов плана, готовых к выполнению, уточнение плана для удовлетворения открытых предусловий или разрешения конфликтов, а также модификацию плана в свете дополнительной информации, полученной во время его выполнения. Очевидно, что агент, впервые приступая к формулировке новой цели, не будет иметь в своем распоряжений действий, готовых для выполнения, поэтому он потратит некоторое время на выработку частичного плана. Однако вполне возможно, что агент начнет выполнение плана еще до того, как разработка плана будет полностью закончена, особенно если в нем имеются независимые подцели, которых требуется достичь уже сейчас. Непрерывно планирующий агент постоянно контролирует состояние мира, обновляя свою модель мира по новым результатам восприятия, даже если его размышления над планом еще продолжаются.
Вначале рассмотрим один пример, а затем опишем программу агента, которая получила название Continuous-POP-Agent, поскольку в ней для представления намеченной деятельности используются планы с частичным упорядочением. Чтобы упростить это представление, мы будем предполагать наличие полностью наблюдаемой среды. Те же самые методы могут быть распространены и на частично наблюдаемый случай.
В качестве примера рассматривается задача из проблемной области мира блоков (раздел 11.1). Начальное состояние показано на рис. 12.10, а. Нам потребуется действие Move{x, у), в котором блок х перемещается на блок у, при условии, что обе их верхние поверхности являются свободными. Схема этого действия состоит в следующем:
Action {Move {х, у) ,
Precond: Clear(x) л Clear(y) л On(x,z),
Effect: Оп(х,у) л Clear(z) л -.On(x, z) л —iClear(y))
Агенту вначале необходимо сформулировать для себя цель. Здесь мы не будем обсуждать процесс формулировки цели, а вместо этого предположим, что агенту было дано задание достичь цели On (C,D) л Оп{ D, В) (или он принял это решение самостоятельно). Агент начинает планировать действие по достижению данной цели. В отличие от всех других описанных в этой книге агентов, которые отключают все свои восприятия до тех пор, пока планировщик не вернет полное решение данной задачи, непрерывно планирующий агент формирует свой план поэтапно, затрачивая на каждый этап ограниченное количество времени. После каждого этапа планирования агент возвращает в качестве своего действия пустую операцию NoOp и снова проверяет результаты своего восприятия. Предположим, что результаты восприятия не меняются и агент быстро составляет план, показанный на рис. 12.11. Обратите внимание на то, что предусловия обоих действий, Move{D, В) и Move {С, D), выполнены еще в состоянии start, но в соответствии с существующим ограничением упорядочения первое из них вносится в план прежде, чем второе. Это требуется для обеспечения того, чтобы предикат Clear[D) оставался истинным до выполнения действия Move (D, В). На протяжении всего процесса непрерывного планирования в качестве метки для текущего состояния всегда используется Start. Агент обновляет это состояние после каждого действия.
Теперь план готов к выполнению, но прежде чем агент сможет приступить к действию, вмешивается природа. Какой-то внешний агент (возможно, учитель агента, потерявший терпение) перемещает блок D на блок Б, после чего мир переходит в состояние, показанное на рис. 12.10, в. Агент воспринимает информацию об этом состоянии, учитывает, что предикаты Clear (В) и On(D, G) больше не являются истинными в текущем состоянии, и обновляет соответствующим образом модель текущего состояния. Причинные связи, которые создавали предусловия Clear(в) и On (D, G) для действия Move {D, В), становятся недействительными и должны быть удалены из плана. Новый план показан на рис. 12.12. Состояние Start всегда представляет текущее состояние, но оно изменилось, поэтому на данном рисунке состояние Start отличается от соответствующего состояния на предыдущем рисунке. Обратите внимание на то, что теперь план стал неполным: два из предусловий для действия Move(D, В) являются открытыми, а его предусловие On(D,y) теперь неконкретизировано, поскольку больше нет смысла предполагать, что это перемещение будет выполнено из позиции блока G.
Теперь агент может воспользоваться преимуществом этого "полезного" вмешательства, обнаружив, что причинная связь Move(D, В) 0n{D,V Finish может быть заменена прямой связью от состояния Start к состоянию Finish. Этот процесс называется продлением (extension) причинной связи и осуществляется каждый раз, когда некоторое условие может быть взято из более раннего, а не более позднего этапа без создания нового конфликта.
После удаления старой причинной связи от Move(D, В) к Finish действие Move{D, В) больше не поддерживает вообще какие-либо причинные связи. Теперь оно становится избыточным этапом (redundant step). Все избыточные этапы и все поддерживающие их связи удаляются из плана. В результате создается план, показанный на рис. 12.13.
После этого стал готовым к выполнению этап Move{C,D), поскольку все его предусловия выполнены на этапе Start, перед ним не требуется проходить какие-либо другие этапы и он не конфликтует с какой-либо другой связью в плане. Данный этап удаляется из плана и выполняется. К сожалению, агент допустил оплошность и уронил блок С на блок А, вместо того чтобы поставить его на D, поэтому было получено состояние, показанное на рис. 12.10, в. Новое состояние плана приведено на рис. 12.14. Обратите внимание на то, что в плане нет новых действий, но все еще остается открытое условие для этапа Finish.
Агент решает составить план для этого открытого условия. Опять-таки целевое условие будет выполнено с помощью действия Move (С, D). Его предусловия удовлетворяются за счет новых причинных связей от этапа Start. Новый план приведен на рис. 12.15.
Рис. 12.16. После того как действие Move (C,D) выполняется и удаляется из плана, оставшееся открытое условие On (С, D) может быть разрешено путем добавления причинной связи от нового этапа Start. Теперь выполнение плана закончено
Из этого примера ясно, что непрерывное планирование весьма напоминает планирование с частичным упорядочением. В каждой итерации алгоритм находит что-то, касающееся плана, что требует исправления (так называемые дефекты плана— plan flaw), и исправляет это положение. Сам алгоритм POP также может рассматриваться как алгоритм устранения дефектов, в котором учитываются два дефекта: открытые предусловия и конфликты причинных связей. Непрерывно планирующий агент, с другой стороны, справляется с гораздо более широким перечнем дефектов, которые описаны ниже.
• Недостающие цели. Агент может принять решение по добавлению в состояние Finish новой цели или целей. (При непрерывном планировании было бы больше смысла применять вместо названия Finish название Infinity, а вместо Start — Current, но авторы будут придерживаться установившейся традиции.)
• Открытые предусловия. Агент добавляет причинную связь к открытому предусловию, выбирая либо новое, либо существующее действие (как в алгоритме POP).
Действие Move {С, D) снова готово к выполнению. На этот раз оно завершается успешно и достигается целевое состояние, показанное на рис. 12.10, г. После удаления данного этапа из плана целевое условие On (С, D) снова становится открытым. Но поскольку этап Start обновлен и в нем отражено новое состояние мира, целевое условие может быть немедленно выполнено с помощью связи от этапа Start. Таковым является обычный ход событий, когда какое-то действие оказывается успешным. Конечное состояние данного плана показано на рис. 12.16. Поскольку все целевые условия удовлетворяются этапом Start и больше нет оставшихся действий, агент теперь вправе удалить все подцели из состояния Finish и сформулировать новую цель.
• Конфликты причинных связей. При наличии причинной связи А Р >В и действия С с результатом -р агент для разрешения этого конфликта выбирает ограничение упорядочения или ограничение переменной (как в алгоритме POP).
• Неподдерживаемые связи. Если есть причинная связь Start—1В->А, где предикат р больше не является истинным в состоянии Start, агент удаляет эту связь (что позволяет предотвратить выполнения действия, предусловия которого являются ложными.)
• Избыточные действия. Если какое-то действие А не обеспечивает выполнения ни одной причинной связи, агент удаляет и это действие, и его связи (что позволяет ему воспользоваться преимуществом удачно сложившихся обстоятельств.)
• Невыполненные действия. Если некоторое действие А (отличное от Finish) имеет все выполненные предусловия в состоянии Start, не связано с упорядоченными перед ним другими действиями (кроме Start) и не конфликтует ни с одной причинной связью, агент удаляет из плана действие А вместе с его причинными связями и возвращает его как действие, которое должно быть выполнено.
• Ненужные, существовавшие в прошлом цели. Если в плане нет открытых предусловий и нет действий (поэтому все причинные связи проходят непосредственно от состояния Start к состоянию Finish), то текущее множество целей достигнуто. Агент удаляет эти цели и связи, ведущие к ним, чтобы освободить место для новых целей.
Алгоритм Continuous-POP-Agent приведен в листинге 12.6. В нем имеется цикл "принять результаты восприятия, удалить дефекты, выполнить действие". Агент, действующий в соответствии с этим алгоритмом, хранит в своей базе знаний постоянно существующий план и в каждой операции удаляет из этого плана по одному дефекту. Затем он выполняет некоторое действие (хотя таким действием часто бывает пустая операция NoOp) и повторяет цикл. Этот агент способен преодолевать многие проблемы, перечисленные при обсуждении перепланирующего агента на с. 599. В частности, он может действовать в реальном времени, пользуется удачным стечением обстоятельств, способен формулировать цели самостоятельно и справляется с непредвиденными ситуациями, которые влияют на выполнение плана в будущем.
Листинг 12.6. Алгоритм непрерывно планирующего агента с частичным упорядочением Continuous-POP-Agent. После получения очередных результатов восприятия агент удаляет один дефект из своего постоянно обновляемого плана, а затем возвращает действие. Агенту часто приходится выполнять много этапов планирования, связанных с удалением дефектов, в течение которых он возвращает пустую операцию NoOp, пока он не будет готов выполнить какое-то реальное действие
function Continuous-POP-Agent{percept) returns действие action static: plan, план, первоначально содержащий только действия Start и Finish
action Remove-Flaw{plan) // Возможно, выполнение этой операции приведет // к обновлению действия action return action







Материалы

Яндекс.Метрика