Проблемы отсутствия датчиков
Предположим, что агенту-пылесосу известны все последствия его действий, но он не имеет датчиков. В таком случае агент знает только, что его начальным состоянием является одно состояние из множества {1#2#3,4#5,6,7#8}. На первый взгляд можно предположить, что попытки агента предсказать будущую ситуацию окажутся бесполезными, но фактически он может сделать это вполне успешно. Поскольку агент знает, к чему приводят его действия, то может, например, вычислить, что действие Right вызовет переход его в одно из состояний {2,4,6,8}, а последовательность действий [Right, Suck] всегда оканчивается в одном из состояний {4,8}. Наконец, последовательность действий [Right, Suck, Left, Suck] гарантирует достижение целевого состояния 7, независимо от того, каковым является начальное состояние. Мы утверждаем, что агент может принудительно перевести мир в состояние 7, даже если ему не известно, с какого состояния он начинает. Подведем итог: если мир не является полностью наблюдаемым, то агент должен рассуждать о том, в какое множество состояний (а не в единственное состояние) он может попасть. Мы называем каждое такое множество состояний доверительным состоянием, поскольку оно показывает, в каких возможных физических состояниях агент может считать себя находящимся в данный момент со всей уверенностью. (В полностью наблюдаемой среде каждое доверительное состояние содержит одно физическое состояние.)
Для решения проблемы отсутствия датчиков необходимо выполнять поиск в пространстве доверительных, а не физических состояний. Первоначальное состояние является доверительным состоянием, а каждое действие становится отображением из одного доверительного состояния в другое. Результат применения некоторого действия к некоторому доверительному состоянию определяется путем объединения результатов применения этого действия к каждому физическому состоянию из этого доверительного состояния. Теперь любой путь объединяет несколько доверительных состояний, а решением является путь, который ведет к такому доверительному состоянию, все члены которого представляют собой целевые состояния. На рис. 3.13 показано пространство достижимых доверительных состояний для детерминированного мира пылесоса без датчиков. Существует только 12 достижимых доверительных состояний, но все пространство доверительных состояний включает каждое возможное множество физических состояний, т.е. 28=256 доверительных состояний. Вообще говоря, если пространство физических состояний имеет S состояний, то пространство доверительных состояний имеет 2s доверительных состояний.
В приведенном выше описании проблем отсутствия датчиков предполагалось, что действия являются детерминированными, но этот анализ, по сути, остается неизменным, если среда — недетерминированная, т.е. если действия могут иметь несколько возможных результатов. Причина этого состоит в том, что в отсутствие датчиков агент не способен определить, какой результат достигнут фактически, поэтому различные возможные результаты становятся просто дополнительными физическими состояниями в доверительном состоянии-преемнике. Например, предположим, что среда подчиняется закону Мэрфи (или закону "подлости"): так называемое действие Suck иногда оставляет мусор на полу, но только если на нем еще не было мусора6. В таком случае, если действие Suck применяется в физическом состоянии 4 (см. рис. 3.12), то существуют два возможных результата: состояния 2 и 4. Теперь применение действия Suck в начальном доверительном состоянии, {1#2,3,4#5#6#7,8}, приводит к доверительному состоянию, представляюшему собой объединение множеств результатов для этих восьми физических состояний. Проведя эти вычисления, можно обнаружить, что новым доверительным состоянием снова становится {1,2,3,4,5,6,7,8}. Таким образом, для агента без датчиков в мире закона Мэрфи действие Suck оставляет доверительное состояние неизменным! Это означает, что фактически данная задача неразрешима (см. упр. 3.18). Интуитивно можно понять, что причина этого состоит в том, что агент не может определить, является ли текущий квадрат грязным и поэтому не способен установить, приведет ли действие Suck к его очистке или оставит еще больше мусора.