Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 35
Текст из файла (страница 35)
Общий алгоритм поиска в графе. Множество с1овео может быть реализовано с помощью хэш-таблипы для обеспечения эффективной проверки повторяющихся состояний. В этом алгоритме предполагается, чтв первый найденный путь к состоянию в является наименее дорогостоящим (см. текст) Еппсе1оп Отар)з-Беато)з(ргоЫем, Ег1пде) геепгпв решение или индикатор неудачи Еа11иге с1овес[ ь- пустое множество егепде < — 1пвегс(махе-иоде(1пьсьа1-Бсасе[ргоыет]), егбпде) 1оор оо 1Е Еюреут(Егхпде) етзеп гевпгп индикатор неудачи Еаз1иге пог(е ь- кеточе-еьгвс(Егдпде) Ее ооа1-тевс[ргоыет] (Благе [поде] ) е)зеп геепгп Бо1псьоп(пог[е) 1Е Беасе[поде) ие находится в множестве с1овеб еЬеп добавить Благе[пса(е] к множеству с1овеМ егбпде г — 1пвеге-д11(ехрапб(поде, ргоыет), егЕпде) Между прочим, использование закрытого списка с1опес] означает, что поиск в глубину и поиск с итеративным углублением больше не имеют линейных требований к пространству.
Поскольку в алгоритме Огар)з-Беагс]т каждый узел хранится в памяти, некоторые методы поиска становятся неосуществимыми из-за недостаточного объема памяти. 3.6. ПОИСК С ЧАСТИЧНОЙ ИНФОРМАЦИЕЙ В разделе 3.3 было выдвинуто предположение, что среда является полностью наблюдаемой и детерминированной и что агент имеет информацию о том, каковы последствия каждого действия. Поэтому агент может точно вычислить, какое состояние становится результатом любой последовательности действий, и всегда знает, в каком состоянии он находится. Его восприятия не предоставляют новой информации после выполнения каждого действия. Но что произойдет, если знания о состояниях или действиях являются неполными? Авторы обнаружили, что разные типы неполноты приводят к трем перечисленным ниже типам проблем.
1. Проблемы отсутствия датчиков (называемые также проблемами совместимости). Если агент вообще не имеет датчиков, то (насколько ему известно) может находиться в одном из нескольких возможных начальных состояний и поэтому каж- Глава 3. Решение проблем посредством поиска 141 ными, но фактически он может сделать это вполне успешно. Поскольку агент знает, к чему приводят его действия, то может, например, вычислить, что действие пад)зс вызовет переход его в одно из состояний (2,4,6,8), а последовательность действий (дздШ, Био)с) всегда оканчивается в одном из состояний (4, 8).
Наконец, последовательность действий (Кзд)зс, Бис)с, деГс, Бис)с] гарантирует достижение целевого состояния 7, независимо от того, каковым является начальное состояние. Мы утверждаем, что агент может Ж принудительно перевести мир в состояние 7, даже если ему не известно, с какого состояния он начинает. Подведем итог. если мир не является полностью наблюдаемым, то агент должен рассуждать о том, в какое множество состояний (а не в единственное состояние) он может попасть. Мы называем каждое такое множество состояний ск доверительным состоянием, поскольку оно показывает, в каких возможных физических состояниях агент может считать себя находящимся в данный момент со всей уверенностью. (В полностью наблюдаемой среде каждое доверительное состояние содержит одно физическое состояние.) Для решения проблемы отсутствия датчиков необходимо выполнять поиск в пространстве доверительных, а не физических состояний.
Первоначальное состояние является доверительным состоянием, а каждое действие становится отображением из одного доверительного состояния в другое. Результат применения некоторого действия к некоторому доверительному состоянию определяется путем объединения результатов применения этого действия к каждому физическому состоянию из этого доверительного состояния. Теперь любой путь объединяет несколько доверительных состояний, а решением является путь, который ведет к такому доверительному состоянию, все члены которого представляют собой целевые состояния. На рис. 3.13 показано пространство достижимых доверительных состояний для детерминированного мира пылесоса без датчиков.
Существует только 12 достижимых доверительных состояний, но все пространство доверительных состояний включает каждое возможное множество физических состояний, т.е. 2з=256 доверительных состояний. Вообще говоря, если пространство физических состояний имеет Я состояний, то пространство доверительных состояний имеет 2' доверительных состояний.
В приведенном выше описании проблем отсутствия датчиков предполагалось, что действия являются детерминированными, но этот анализ, по сути, остается неизменным, если среда — недетерминированная, т.е. если действия могут иметь несколько возможных результатов. Причина этого состоит в том, что в отсутствие датчиков агент не способен определить, какой результат достигнут фактически, поэтому различные возможные результаты становятся просто дополнительными физическими состояниями в доверительном состоянии-преемнике. Например, предположим, что среда подчиняется закону Мэрфи (или закону "подлости"): так называемое действие Бис)с иногда оставляет мусор на полу, но только если на нем еще не было мусора'.
В таком случае, если действие Бис)с применяется в физическом состоянии 4 (см. рис. 3.12), то существуют два возможных результата: состояния 2 и 4. Теперь применение действия Бис)г в начальном доверительном состоянии, (1, 2, 3, 4, 5, 6, 7, 8), приводит к доверительному состоянию, представляю- а Мы предполагаем, что большинство читателей стазкиваются с аналогичными проблемами и поэтому выражают сочувствие нашему агенту. Авторы приносят свои извинения владельцам современных, эффективных бытовых приборов, которые не смогут извлечь урок из этого педагогического упражнения.
Глава 3. Решение проблем посредством поиска 143 ется с 'а. проблемой непредвиденных ситуаций. Решение проблемы непредвиденных ситуаций часто принимает форму дерева, в котором каждая ветвь может быть выбрана в зависимости от результатов восприятий, полученных вплоть до этой позиции в дереве. Например, предположим, что агент находится в мире закона Мэрфи и имеет датчик положения и локальный датчик мусора, но не имеет датчика, способного обнаружить мусор в других квадратах. Таким образом, восприятие «ь, пйксу] означает, что агент находится в одном из состояний [1, 3). Агент может сформулировать последовательность действий [яис]с, лацис, яис]с]. Всасывание должно было бы перевести текущее состояние в одно из состояний [5, 71, и тогда передвижение вправо перевело бы данное состояние в одно из состояний [б, 8).
Выполнение заключительного действия 8ис)с в состоянии б переводит агента в состояние 8, целевое, но выполнение его в состоянии 8 способно снова перевести агента в состояние б (согласно закону Мэрфи), и в этом случае данный план оканчивается неудачей. Исследуя пространство доверительных состояний для этой версии задачи, можно легко определить, что ни одна фиксированная последовательность действий не гарантирует решение данной задачи. Однако решение существует, при условии, что мы не будем настаивать на фиксированной последовательности действий: [ Яиск, яхдлс, хя [я, Рзх Еу] Еззеп Ясак Тем самым дополняется пространство решений для включения возможности выбора действий с учетом непредвиденных ситуаций, возникающих во время выполнения.
Многие задачи в реальном, физическом мире усложняются из-за наличия проблемы непредвиденных ситуаций, поскольку точные предсказания в них невозможны. По этой причине многие люди соблюдают предельную осторожность во время пеших прогулок или вождения автомобиля. Иногда проблемы непредвиденных ситуаций допускают чисто последовательные решения. Например, рассмотрим полностью наблюдаемый мир закона Мэрфи. Непредвиденные ситуации возникают, если агент выполняет действие Бис]с в чистом квадрате, поскольку при этом в данном квадрате может произойти или не произойти отложение мусора.
При том условии, что агент никогда не будет очищать чистые квадраты, не будут возникать какие-либо непредвиденные ситуации и поэтому из любого начального состояния можно будет найти последовательное решение (упр. 3.18). Алгоритмы для решения проблем непредвиденных ситуаций являются более сложными по сравнению с алгоритмами стандартного поиска, приведенными в этой главе; они рассматриваются в главе 12. Кроме того, проблемы непредвиденных ситуаций требуют применения немного иного проекта агента, в котором агент может действовать до того, как найдет гарантированный план. Это полезно, поскольку вместо предварительного обдумывания каждой возможной непредвиденной ситуации, которая могла бы возникнуть во время выполнения, часто бывает лучше приступить к действию и узнать, какие непредвиденные ситуации действительно возникают. После этого агент может продолжать решать свою задачу, принимая в расчет эту дополнительную информацию.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
