ПЛАНИРОВАНИЕ И ОСУЩЕСТВЛЕНИЕ ДЕЙСТВИЙ В НЕДЕТЕРМИНИРОВАННЫХ ПРОБЛЕМНЫХ ОБЛАСТЯХ
До сих пор в этой главе рассматривались только проблемные области классического планирования, которые являются полностью наблюдаемыми, статическими и детерминированными. Кроме того, предполагалось, что описания действий являются правильными и полными. В таких обстоятельствах любой агент получает возможность вначале составлять план, а затем выполнять этот план буквально "с закрытыми глазами". С другой стороны, в неопределенной среде агент должен использовать результаты своих восприятий для обнаружения того, что происходит в процессе выполнения плана, а также, возможно, модифицировать или заменять этот план, если случается что-то непредвиденное.
Агентам приходится также иметь дело и с неполной, и с неправильной информацией. Неполнота возникает из-за того, что мир является частично наблюдаемым, или недетерминированным, или обладающим и тем и другим свойством. Например, дверца шкафа с канцелярскими принадлежностями может быть либо закрыта, либо не закрыта на замок; один из моих ключей может открыть или не открыть дверцу, если она на замке, а я могу знать или не знать, в чем имеющаяся у меня информация об этой ситуации является неполной. Поэтому моя модель мира является слабой, но правильной. С другой стороны, неправильность часто возникает, поскольку мир не всегда соответствует моей модели мира; например, я могу быть уверенным в том, что мой ключ откроет шкаф с канцелярскими принадлежностями, но окажусь неправ, если в нем сменили замок. Не обладая способностью справляться с неправильной информацией, агент становится таким же неинтеллектуальным, как и навозный жук (с. 81), который пытается заткнуть свою норку несуществующим шариком навоза даже после того, как шарик вынули из его лапок.
Возможность получения полной или правильной информации зависит от того, какой степенью недетерминированности характеризуется мир. При ограниченной недетерминированности действия могут иметь непредсказуемые результаты, но все возможные результаты можно перечислить в аксиомах описания действия. Например, при подбрасывании монеты вполне резонно считать, что результатом будет Heads (Орел) или Tails (Решка). Агент получает способность справляться с ограниченной недетерминированностью, составляя планы, применимые во всех возможных обстоятельствах. При неограниченной недетерминированности, с другой стороны, множество возможных предусловий или результатов либо неизвестно, либо слишком велико для того, чтобы в нем можно было выполнить полный поиск. Такие ситуации могут возникать в случае очень сложных или динамичных проблемных областей, таких как вождение автомобиля, экономическое планирование и разработка военной стратегии. Агенту удастся справиться с неограниченной недетерминированностью, только если он способен пересматривать свои планы и/или свою базу знаний. Неограниченная недетерминированность тесно связана с проблемой спецификации (qualification problem), описанной в главе 10, — с проблемой, определяемой невозможностью перечислить все предусловия, требуемые для того, чтобы какое-то действие в реальном мире имело свой намеченный результат.
Существуют четыре описанных ниже метода планирования для осуществления действий в условиях недетерминированности. Первые два из них применимы для ограниченной недетерминированности, а последние два — для неограниченной недетерминированности.
• Планирование без использования датчиков. Этот метод, называемый также совместимым планированием, предусматривает создание стандартных, последовательных планов, которые должны выполняться без учета результатов восприятия. Алгоритм планирования без использования датчиков должен обеспечивать, чтобы цель достигалась в плане при всех возможных обстоятельствах, независимо от истинного начального состояния и фактических результатов действий. Планирование без использования датчиков основано на идее принуждения, согласно которой мир может быть принудительно переведен в данное конкретное состояние, даже если агент обладает лишь частичной информацией о текущем состоянии. Принуждение не всегда возможно, поэтому планирование без использования датчиков часто является неприменимым. Методы решения задач без использования датчиков, предусматривающие поиск в пространстве доверительных состояний, были описаны в главе 3.
• Условное планирование. В этом подходе, называемом также планированием с учетом непредвиденных ситуаций, действия в условиях ограниченной недетерминированности осуществляются путем создания условного плана с различными ответвлениями для самых разных непредвиденных ситуаций, какие только могут возникнуть. Так же как и в классическом планировании, агент вначале составляет план, а затем выполняет подготовленный план. Агент определяет, какая часть плана должна быть выполнена, включив в план действия по восприятию для проверки соответствующих условий. Например, в проблемной области воздушных перевозок могут быть предусмотрены планы, в которых указано "проверить, работает ли аэропорт SFO (Сан-Франциско); в случае положительного ответа полететь в этот аэропорт, в противном случае полететь в Окленд". Условное планирование рассматривается в разделе 12.4.
• Контроль выполнения и перепланирование. При этом подходе агент может использовать любой из описанных выше методов планирования (классический, без использования датчиков или условный) для формирования плана, но использует также контроль выполнения для оценки того, предусмотрена ли в плане фактически сложившаяся текущая ситуация, или план должен быть пересмотрен. Перепланирование осуществляется, если что-то происходит не так, как надо. Благодаря этому агент приобретает способность справляться с неограниченной недетерминированностью. Например, даже если агент, способный к перепланированию, не предвидел возможность закрытия аэропорта SFO, то может обнаружить эту ситуацию после ее возникновения и снова вызвать планировщик для поиска нового пути к цели. Перепланирующие агенты рассматриваются в разделе 12.5.
• Непрерывное планирование. Все планировщики, рассматривавшиеся до сих пор, спроектированы так, что они достигают цели, а затем останавливаются, а непрерывный планировщик предназначен для того, чтобы заниматься планированием в течение всего срока своего существования. Он способен справляться с непредвиденными ситуациями в своей среде, даже если они возникают в ходе того, как агент занимается составлением плана. Он способен также обеспечить отказ от целей и создание дополнительных целей с помощью формулировки цели. Непрерывное планирование описано в разделе 12.6.
Рассмотрим один пример, позволяющий выяснить различия между агентами разных типов. Задача состоит в следующем: дано начальное состояние, в котором имеются стул, стол и несколько банок с краской, притом что все они имеют неизвестный цвет; достичь состояния, в котором стул и стол имеют одинаковый цвет.
Классический планирующий агент не может справиться с этой задачей, поскольку начальное состояние задано не полностью, — мы не знаем, какой цвет имеет мебель.
Агент, осуществляющий планирование без использования датчиков, должен найти план, который работает, не требуя применения каких-либо датчиков во время его выполнения. Решение состоит в том, чтобы открыть любую банку с краской и нанести эту краску и на стул, и на стол, тем самым принудительно переведя их в такое состояние, в котором они имеют одинаковый цвет (даже несмотря на то, что агент так и не узнает, каким стал этот цвет). Принуждение является наиболее приемлемым, если обработка высказываний требует больших затрат или не существует возможности обеспечить восприятие. Например, врачи часто предписывают антибиотик с широким спектром действия, а не используют условный план, согласно которому нужно выполнить анализ крови, затем дождаться получения результатов и только после этого выписать более специализированный антибиотик. Они принимают такое решение потому, что задержки и затраты, связанные с выполнением анализа крови, обычно слишком велики.
Агент, занимающийся условным планированием, может создать лучший план. Он вначале определяет цвет стола и стула; если этот цвет является одинаковым, то план выполнен. В противном случае агент просматривает надписи на банках с краской; если имеется банка с краской такого же цвета, как и у одного из предметов мебели, то агент наносит эту краску и на другой предмет. Если же оба эти предположения оказываются недействительными, агент окрашивает и стол, и стул произвольно выбранной краской.
Перепланирующий агент может выработать тот же план, что и условный планировщик, или вначале предусмотреть меньше ответвлений и по мере необходимости заполнять остальные фрагменты плана в ходе его выполнения. Он также способен справляться с неточностями в описании его действий. Например, предположим, что действие Paint (obj, color) рассматривается как имеющее детерминированный результат Color{obj, color). Условный планировщик будет просто считать, что желаемый результат достигнут непосредственно после выполнения действия, а перепланирующий агент способен проверить результат, и если он не был истинным (возможно, потому, что агент допустил небрежность и не прокрасил полностью какой-то участок), то имеет возможность затем перепланировать свои действия, чтобы снова покрасить дефектный участок. Мы вернемся к данному примеру на с. 596.
Непрерывно планирующий агент, кроме учета непредвиденных событий, способен пересматривать свои планы должным образом, если, допустим, мы внесем дополнительную цель, чтобы сегодняшний обед прошел еще за этим столом, поэтому нужно будет отложить выполнение плана окрашивания.
В реальном мире в агентах применяется сочетание нескольких подходов. Производители автомобилей продают запасные колеса и надувные подушки безопасности, которые представляют собой физические воплощения ответвлений условного плана, позволяющих справляться с такими ситуациями, как проколы колес или аварии; с другой стороны, большинство водителей автомобилей никогда не учитывают такие возможности, поэтому отвечают на проколы и аварии как перепланирующие агенты. Как правило, агенты создают условные планы только для таких непредвиденных ситуаций, которые имеют важные последствия, а шансами на то, что дела пойдут не лучшим образом, нельзя пренебречь. Таким образом, водителю автомобиля, предпринимающему поездку через пустыню Сахара, придется явно учесть возможность поломок в пути, тогда как поездка в соседний супермаркет требует гораздо меньшего заблаговременного планирования.
Агенты, описанные в этой главе, предназначены для осуществления действий в условиях недетерминированности, но не обладают способностью учитывать ком
промиссы между вероятностью успеха и стоимостью составления плана. В главе 16 рассматриваются дополнительные инструментальные средства, позволяющие справляться с этими проблемами.