КОНТРОЛЬ ВЫПОЛНЕНИЯ И ПЕРЕПЛАНИРОВАНИЕ

Агент, контролирующий выполнение, проверяет свои восприятия для определения того, все ли идет в соответствии с планом. Закон Мэрфи говорит нам о том, что даже самые тщательно продуманные планы, которые составляют мыши, люди и агенты, занимающиеся условным планированием, часто оканчиваются неудачей. Проблема заключается в неограниченной недетерминированности — всегда могут возникнуть непредвиденные обстоятельства, для которых описания действий, подготовленные агентом, будут неправильными. Поэтому в реальных вариантах среды всегда требуется контроль выполнения. Мы будем рассматривать два способа организации контроля выполнения: простую, но слабую форму, называемую контролем действий, в которой агент проверяет среду для определения того, что следующее действие окажется применимым, и более сложную, но и более эффективную форму, называемую контролем плана, в которой агент проверяет весь оставшийся план.
Перепланирующий агент знает, что делать, когда происходит что-то непредвиденное: снова вызвать планировщик, чтобы он предложил ему новый план достижения цели. Для предотвращения использования слишком больших затрат времени на планирование такая операция обычно осуществляется в виде попытки исправить старый план — найти способ перехода из текущего непредвиденного состояния обратно в одно из тех состояний, которые были предусмотрены в плане.
В качестве примера еще раз рассмотрим мир пылесоса с "двойным законом Мэрфи", показанный на рис. 12.6. В этом мире перемещение в чистый квадрат иногда приводит к тому, что в этом квадрате откладывается мусор, но что если агент не будет знать или задумываться об этом? Такой подход позволяет предложить очень простое решение: [Left]. Если мусор не был оставлен после прибытия агента в квадрат во время фактического выполнения плана, то агент обнаружит, что цель достигнута. В противном случае, поскольку предусловие CleanL неявного шага Finish не выполнено, агент выработает новый план: [Suck]. Выполнение этого плана всегда приводит к успеху.
Контроль выполнения и перепланирование, вместе взятые, образуют общую стратегию, которая может применяться и в полностью наблюдаемых, и в частично наблюдаемых вариантах среды, а также может распространяться на самые различные представления, применяемые в планировании, включая планы в пространстве состояний, планы с частичным упорядочением и условные планы. Один из простых подходов к планированию в пространстве состояний показан в листинге 12.5. Планирующий агент начинает с цели и создает начальный план ее достижения. Затем агент приступает к последовательному выполнению действий. А перепланируюший агент, в отличие от других рассматриваемых нами планирующих агентов, следит за выполнением как оставшегося невыполненного сегмента плана plan, так и полного первоначального плана whole__plan. В нем используется контроль действий: прежде чем выполнить следующее действие плана plan, агент проверяет свои результаты восприятия для определения того, не оказались ли вдруг невыполненными какие-либо предусловия плана. Если они действительно являются таковыми, то агент пытается снова попасть в колею, перепланируя последовательность действий, которые должны помочь ему вернуться в некоторый пункт плана whole_plan.
Листинг 12.5. Алгоритм агента, который занимается контролем действий и перепланированием. В нем в качестве процедуры используется полный алгоритм планирования в пространстве состояний, называемый Planner. Если предусловия следующего действия не выполняются, агент проходит по циклу через возможные пункты р в плане whole_plan, пытаясь найти такой из них, путь к которому может быть запланирован с помощью алгоритма Planner. Этот путь называется repair (поправка). Если в алгоритме Planner удается найти такую поправку repair, агент соединяет repair и остаток плана после пункта р, чтобы создать новый план. Затем агент возвращается к первому этапу нового плана
function Replanning-Agent{percept) returns действие action static: KB, база знаний (включает описания действий)
plan, план, первоначально представленный пустым списком [] whole__plan, общий план, первоначально представленный пустым списком []
goal, цель
Tell(KB, Make-Percept-Sentence(percept, t) ) current <— State-Description(KB, t) if plan = [] then
whole_plan <— plan <— Planner(current, goal, KB) if предусловия Preconditions(First{plan)) не имеют в настоящее время значения true in KB then
candidates <— Sort{whole_plan, упорядоченный по расстояниям
до текущего состояния current) find состояние s среди возможных кандидатов candidates,
такое, что failure Ф repair <— Planner (current, s, KB) continuation <— хвост общего плана whole_jolan, начинающийся с s whole_plan <— plan <— Append(repair, continuation) return Pop{plan)
Схематически этот процесс приведен на рис. 12.9. Перепланирующий агент обнаруживает, что в текущем состоянии не выполнены предусловия первого действия в плане plan. Поэтому он вызывает алгоритм планирования, чтобы получить новый субплан repair, позволяющий перейти из текущего состояния в некоторое состояние s плана whole_plan. В данном примере оказалось, что состояние s находится на один шаг назад от текущего, оставшегося плана plan (это удалось определить благодаря тому, что осуществляется контроль за выполнением всего плана, а не только оставшегося). Вообще говоря, следует выбирать состояние s так, чтобы оно было как можно ближе к текущему состоянию. Соединение плана repair и части плана whole_plan от s и дальше, которую мы называем continuation, позволяет получить новый план plan, и агент становится готовым возобновить выполнение плана.
Теперь вернемся к примеру задачи, в которой нужно было добиться, чтобы цвет стула и стола совпадал, но на этот раз применим перепланирование. Предполагается наличие полностью наблюдаемой среды. В начальном состоянии стул окрашен синей краской, стол — зеленой, и имеются банка с синей краской и банка с красной краской. Таким образом, может быть сформулировано следующее определение задачи:
Init(Color{Chair, Blue) л Color(Table, Green)
A ContainsColor(BC, Blue) л PaintCan(ВС))
A ContainsColor(RC, Red) л PaintCan(RC) Goal(Color(Chair, x) л Color(Table, x))
Action(Paint(object, color),
Precond: HavePaint(color) ,
Effect: Color(object, color)) Action(Open(can),
Precond: PaintCan(can) л ContainsColor(can, color),
Effect: HavePaint(color))
Алгоритм Planner агента должен предложить такой план: [Start; Open(ВС); Paint(Table, Blue); Finish]
Теперь агент готов выполнить этот план. Предположим, что все шло хорошо, поскольку агент успешно открыл банку с синей краской и нанес эту краску на стол. В этот момент агенты, описанные в предыдущих разделах, объявили бы о победе, поскольку они завершили все этапы в плане. Но агент, контролирующий выполнение, должен вначале проверить предусловие этапа Finish, в котором сказано, что эти два предмета мебели должны иметь одинаковый цвет. Предположим, агент обнаружил, что стол и стул не имеют одинакового цвета, поскольку он не закрасил часть стола и осталось зеленое пятно. Теперь агент должен определить, в какую позицию плана whole_р>1ап он должен перейти и какая последовательность корректирующих действий позволяет в нее попасть. Агент обнаруживает, что текущее состояние идентично предусловию перед выполнением действия Paint, поэтому агент выбирает пустую последовательность для repair и принимает, что его план plan должен быть таким же, как и только что выполненная последовательность [Paint, Finish]. После принятия этого нового плана контроль выполнения возобновляется и предпринимается попытка выполнить действие Paint. Такое поведение повторяется в цикле до тех пор, пока результаты восприятия не будут указывать, что стол полностью перекрашен. Но заслуживает внимания то, что этот цикл создается процессом "запланировать—выполнить—перепланировать", а не явным циклом в плане.
Контроль действий — это очень простой метод контроля выполнения, но он может иногда приводить к поведению, которое нельзя назвать интеллектуальным. Например, предположим, что агент формирует план решения задачи по перекраске, предусмотрев окрашивание стула и стола в красный цвет. Затем он открывает банку с красной краской и обнаруживает, что краски достаточно только для стула. При контроле действий неудача не была бы обнаружена до тех пор, пока не будет окрашен стул, поскольку в этот момент предусловие HavePaint (Red) становится ложным. А фактически требуется обнаруживать неудачное завершение каждый раз, когда состояние является таковым, что оставшийся план больше не будет работать. В методе контроля плана эта цель достигается путем проверки предусловий успеха всего оставшегося плана, т.е. предусловий каждого этапе в плане, за исключением

тех предусловий, которые достигаются с помощью еще одного этапа в оставшемся плане. В условиях контроля плана выполнение поставленного под сомнение плана прекращается настолько быстро, насколько это возможно, а не продолжается до тех пор, пока фактически не возникнет неудачное завершение13. В некоторых случаях такое поведение позволяет спасти агента от несчастья, когда поставленный под сомнение план завел бы его к тупик, из которого цель будет недостижима.
Модифицировать алгоритм планирования таким образом, чтобы в нем в каждом пункте план сверялся с предусловиями успеха оставшегося плана, относительно несложно. Если же мы расширим контроль плана для проверки того, выполняются ли в текущем состоянии предусловия плана в любом будущем пункте, а не только в текущем пункте, то контроль плана позволит также воспользоваться преимуществом удачи, т.е. случайного успеха. Если кто-то вдруг придет на помощь и покрасит стол в красный цвет одновременно с тем, как агент красит в красный цвет стул, то предусловия завершения плана будут выполнены (поскольку цель достигнута) и агент сможет раньше уйти с работы.
До сих пор методы контроля и перепланирования рассматривались в полностью наблюдаемых вариантах среды. А если среда является частично наблюдаемой, то ситуация может стать гораздо более сложной. Во-первых, обстоятельства могут так измениться в худшую сторону, что агент не сумеет этого обнаружить. Во-вторых, для "проверки предусловий" может потребоваться выполнение действий по получению информации с помощью датчиков, которые должны быть запланированы (либо на этапе планирования, что потребует от нас возврата к условному планированию, либо на этапе выполнения плана). В наихудшем случае для осуществления любого действия по получению информации с помощью датчиков может потребоваться составление сложного плана, который сам требует контроля и поэтому применения дополнительных действий по сбору информации, и т.д. Если агент упорно добивается того, чтобы были проверены все предусловия, то может так и не перейти к фактическому выполнению каких-либо действий. Агент должен предпочесть в такой ситуации проверку лишь переменных, которые имеют важное значение, характеризуются значительной вероятностью того, что их значения окажутся неправильными, и не требуют слишком больших затрат на сбор информации об их значениях. Это позволяет агенту отвечать должным образом на важные опасности, но не тратить время на проверку того, не падает ли небо на голову.
Теперь, после описания одного из методов контроля и перепланирования, мы должны ответить на вопрос: "Будет ли он работать?" Этот вопрос — на удивление сложный. Если под ним подразумевается: "Можем ли мы гарантировать, что агент всегда достигнет цели, даже в условиях неограниченной недетерминированности?", то ответ будет отрицательным, поскольку агент может неожиданно попасть в тупиковую ситуацию, как описано применительно к оперативному поиску в разделе 4.5. Например, агент-пылесос может не знать, что его аккумуляторы способны разрядиться. Но мы исключим из рассмотрения тупиковые ситуации, т.е. предположим, что агент может сформировать план достижения цели из любого состояния в своей среде. Если принять предположение, что среда действительно является недетерминированной, в том смысле, что подобный план всегда имеет какой-то шанс на успех в любой конкретной попытке его выполнения, то агент в конечном итоге достигнет цели. Поэтому перепланирующий агент обладает способностями, аналогичными тем, которыми обладает агент, занимающийся условным планированием. В действительности можно модифицировать условный планировщик таким образом, чтобы он формировал только частичный план решения, который включает этапы в форме "if then planA else replan". С учетом принятых выше предположений такой план может стать правильным решением первоначальной задачи, к тому же его формирование может оказаться намного дешевле по сравнению с созданием полного условного плана.
Неприятности возникают, когда повторные попытки достижения цели агентом становятся бесплодными — когда они блокируются каким-то предусловием или результатом, о котором агент не знает. Например, если агенту выдали неправильную магнитную карточку-ключ от его номера в гостинице, то он не сможет открыть дверь, даже вставляя эту карточку и вынимая бесконечное количество раз14. Одно из решений состоит в том, чтобы выбрать случайным образом один из множества возможных планов исправления ситуации, а не пытаться каждый раз выполнить один и тот же план. В данном случае полезной альтернативной был бы план исправления ситуации, состоящий в том, чтобы снова подойти к администратору гостиницы и получить правильную карточку-ключ от комнаты. Учитывая то, что агент может оказаться неспособным отличать друг от друга действительно недетерминированный случай и случай, в котором все попытки будут напрасными, такой способ организации выполнения плана, в котором предусмотрено использование нескольких вариантов исправления ситуации, в целом становится более целесообразным.
Еще одним решением проблемы неправильных описаний действий является обучение. После нескольких попыток обучающийся агент должен быть способен модифицировать описание действия, в котором указано, что данный ключ открывает дверь. С этого момента перепланировщик должен автоматически выработать альтернативный план, который состоит в получении нового ключа. Такого рода обучение рассматривается в главе 21.
Даже несмотря на все эти потенциальные усовершенствования, перепланирующий агент все еще обладает несколькими недостатками. Он не может действовать в тех вариантах среды, где все происходит в реальном времени, и не существует пределов количества времени, которое он может затратить на перепланирование, и поэтому нет пределов времени, в течение которого он решится на выполнение какого-то действия. Кроме того, данный агент не способен формулировать новые цели самостоятельно или принимать к исполнению новые цели, дополнительно к его текущим целям, поэтому такой агент не сможет долго существовать в сложной среде. Указанные недостатки будут устранены в следующем разделе.







Материалы

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