Главная arrow Поиск arrow Поиск информации
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Поиск с частичной информацией Печать
Было выдвинуто предположение, что среда является полностью наблюдаемой и детерминированной и что агент имеет информацию о том, каковы последствия каждого действия. Поэтому агент может точно вычислить, какое состояние становится результатом любой последовательности действий, и всегда знает, в каком состоянии он находится. Его восприятия не предоставляют новой информации после выполнения каждого действия. Но что произойдет, если знания о состояниях или действиях являются неполными? Авторы обнаружили, что разные типы неполноты приводят к трем перечисленным ниже типам проблем.
  1. Проблемы отсутствия датчиков (называемые также проблемами совместимости). Если агент вообще не имеет датчиков, то (насколько ему известно) может находиться в одном из нескольких возможных начальных состояний и поэтому каждое действие способно перевести его в одно из нескольких возможных состояний-преемников.
  2. Проблемы непредвиденных ситуаций. Если среда наблюдаема лишь частично или действия являются неопределенными, то акты восприятия агента предоставляют новую информацию после выполнения каждого действия. Каждое возможное восприятие определяет непредвиденную ситуацию, к которой необходимо подготовиться с помощью соответствующего плана. Проблема называется обусловленной сторонним воздействием, если неопределенность вызвана действиями другого агента.
  3. Проблемы исследования. Если состояния и действия в среде неизвестны, агент должен действовать так, чтобы их обнаружить. Проблемы исследования могут рассматриваться как крайний случай проблем непредвиденных ситуаций.

В качестве примера мы будем использовать среду мира пылесоса. Напомним, что пространство состояний имеет восемь состояний, как показано на рисунке. Существуют три действия (Left, Right и Suck), и цель состоит в том, чтобы был убран весь мусор (состояния 7 и 8). Если среда наблюдаема, детерминирована и полностью известна, то эта задача решается тривиально с помощью любого из описанных нами алгоритмов.

Например, если начальным является состояние 5, то последовательность действий [Right, Suck] обеспечивает достижение целевого состояния 8. В оставшейся части этого раздела рассматриваются версии данной задачи, в которых отсутствуют датчики и возникают непредвиденные ситуации.


Восемь возможных состояний мира пылесоса


Проблемы отсутствия датчиков

Предположим, что агенту-пылесосу известны все последствия его действий, но он не имеет датчиков. В таком случае агент знает только, что его начальным состоянием является одно состояние из множества {1,2,3,4,5,6,7,8}. На первый взгляд можно предположить, что попытки агента предсказать будущую ситуацию окажутся бесполезными, но фактически он может сделать это вполне успешно. Поскольку агент знает, к чему приводят его действия, то может, например, вычислить, что действие Right вызовет переход его в одно из состояний {2,4,6,8}, а последовательность действий [Right, Suck] всегда оканчивается в одном из состояний {4,8}. Наконец, последовательность действий [Right, Suck, Left, Suck] гарантирует достижение целевого состояния 7, независимо от того, каковым является начальное состояние. Мы утверждаем, что агент может принудительно перевести мир в состояние 7, даже если ему не известно, с какого состояния он начинает.

Подведем итог: если мир не является полностью наблюдаемым, то агент должен рассуждать о том, в какое множество состояний (а не в единственное состояние) он может попасть. Мы называем каждое такое множество состояний доверительным состоянием, поскольку оно показывает, в каких возможных физических состояниях агент может считать себя находящимся в данный момент со всей уверенностью. (В полностью наблюдаемой среде каждое доверительное состояние содержит одно физическое состояние.)

Для решения проблемы отсутствия датчиков необходимо выполнять поиск в пространстве доверительных, а не физических состояний. Первоначальное состояние является доверительным состоянием, а каждое действие становится отображением из одного доверительного состояния в другое. Результат применения некоторого действия к некоторому доверительному состоянию определяется путем объединения результатов применения этого действия к каждому физическому состоянию из этого доверительного состояния. Теперь любой путь объединяет несколько доверительных состояний, а решением является путь, который ведет к такому доверительному состоянию, все члены которого представляют собой целевые состояния. На рисунке показано пространство достижимых доверительных состояний для детерминированного мира пылесоса без датчиков. Существует только 12 достижимых доверительных состояний, но все пространство доверительных состояний включает каждое возможное множество физических состояний, т.е. 28=256 доверительных состояний. Вообще говоря, если пространство физических состояний имеет S состояний, то пространство доверительных состояний имеет 2 s доверительных состояний.

В приведенном выше описании проблем отсутствия датчиков предполагалось, что действия являются детерминированными, но этот анализ, по сути, остается неизменным, если среда — недетерминированная, т.е. если действия могут иметь несколько возможных результатов. Причина этого состоит в том, что в отсутствие датчиков агент не способен определить, какой результат достигнут фактически, поэтому различные возможные результаты становятся просто дополнительными физическими состояниями в доверительном состоянии-преемнике. Например, предположим, что среда подчиняется закону Мэрфи (или закону "подлости"): так называемое действие Suck иногда оставляет мусор на полу, но только если на нем еще не было мусора6. В таком случае, если действие Suck применяется в физическом состоянии 4, то существуют два возможных результата: состояния 2 и 4. Теперь применение действия Suck в начальном доверительном состоянии, {1,2,3,4,5,6,7,8}, приводит к доверительному состоянию, представляю щему собой объединение множеств результатов для этих восьми физических состояний. Проведя эти вычисления, можно обнаружить, что новым доверительным состоянием снова становится {1,2,3,4,5,6,7,8}.

Таким образом, для агента без датчиков в мире закона Мэрфи действие Suck оставляет доверительное состояние неизменным! Это означает, что фактически данная задача неразрешима. Интуитивно можно понять, что причина этого состоит в том, что агент не может определить, является ли текущий квадрат грязным и поэтому не способен установить, приведет ли действие Suck к его очистке или оставит еще больше мусора.


Достижимая часть пространства доверительных состояний для детерминированного мира пылесоса без датчиков. Каждый затененный прямоугольник соответствует одному доверительному состоянию. В любой конкретный момент времени агент находится в одном конкретном доверительном состоянии, но не знает, в каком именно физическом состоянии он находится. Первоначальным доверительным состоянием (с полным незнанием ситуации) является верхний центральный прямоугольник. Действия обозначены дугами с метками, а петли, обозначающие возврат в одно и то же доверительное состояние, опущены для упрощения рисунка

Проблемы непредвиденных ситуаций

Если среда является таковой, что агент после выполнения действия может получить от своих датчиков в том же состоянии новую информацию, то агент сталкивается с проблемой непредвиденных ситуаций. Решение проблемы непредвиденных ситуаций часто принимает форму дерева, в котором каждая ветвь может быть выбрана в зависимости от результатов восприятий, полученных вплоть до этой позиции в дереве. Например, предположим, что агент находится в мире закона Мэрфи и имеет датчик положения и локальный датчик мусора, но не имеет датчика, способного обнаружить мусор в других квадратах. Таким образом, восприятие [L, Dirty] означает, что агент находится в одном из состояний {1,3}. Агент может сформулировать последовательность действий [Suck,Right, Suck]. Всасывание должно было бы перевести текущее состояние в одно из состояний {5,7}, и тогда передвижение вправо перевело бы данное состояние в одно из состояний {6,8}. Выполнение заключительного действия Suck в состоянии 6 переводит агента в состояние 8, целевое, но выполнение его в состоянии 8 способно снова перевести агента в состояние б (согласно закону Мэрфи), и в этом случае данный план оканчивается неудачей.

Исследуя пространство доверительных состояний для этой версии задачи, можно легко определить, что ни одна фиксированная последовательность действий не гарантирует решение данной задачи. Однако решение существует, при условии, что мы не будем настаивать на фиксированной последовательности действий: [ Suck, Right, if [R,Dirty] then Suck ] Тем самым дополняется пространство решений для включения возможности выбора действий с учетом непредвиденных ситуаций, возникающих во время выполнения. Многие задачи в реальном, физическом мире усложняются из-за наличия проблемы непредвиденных ситуаций, поскольку точные предсказания в них невозможны. По этой причине многие люди соблюдают предельную осторожность во время пеших прогулок или вождения автомобиля.

Иногда проблемы непредвиденных ситуаций допускают чисто последовательные решения. Например, рассмотрим полностью наблюдаемый мир закона Мэрфи. Непредвиденные ситуации возникают, если агент выполняет действие Suck в чистом квадрате, поскольку при этом в данном квадрате может произойти или не произойти отложение мусора. При том условии, что агент никогда не будет очищать чистые квадраты, не будут возникать какие-либо непредвиденные ситуации и поэтому из любого начального состояния можно будет найти последовательное решение.

Алгоритмы для решения проблем непредвиденных ситуаций являются более сложными по сравнению с алгоритмами стандартного поиска. Кроме того, проблемы непредвиденных ситуаций требуют применения немного иного проекта агента, в котором агент может действовать до того, как найдет гарантированный план. Это полезно, поскольку вместо предварительного обдумывания каждой возможной непредвиденной ситуации, которая могла бы возникнуть во время выполнения, часто бывает лучше приступить к действию и узнать, какие непредвиденные ситуации действительно возникают. После этого агент может продолжать решать свою задачу, принимая в расчет эту дополнительную информацию.