Проблемы непредвиденных ситуаций
Если среда является таковой, что агент после выполнения действия может получить от своих датчиков в том же состоянии новую информацию, то агент сталкивается с проблемой непредвиденных ситуаций. Решение проблемы непредвиденных ситуаций часто принимает форму дерева, в котором каждая ветвь может быть выбрана в зависимости от результатов восприятий, полученных вплоть до этой позиции в дереве. Например, предположим, что агент находится в мире закона Мэрфи и имеет датчик положения и локальный датчик мусора, но не имеет датчика, способного обнаружить мусор в других квадратах. Таким образом, восприятие [L, Dirty] означает, что агент находится в одном из состояний {1,3}. Агент может сформулировать последовательность действий [Suck, Right, Suck]. Всасывание должно было бы перевести текущее состояние в одно из состояний {5,7}, и тогда передвижение вправо перевело бы данное состояние в одно из состояний {6,8}. Выполнение заключительного действия Suck в состоянии 6 переводит агента в состояние 8, целевое, но выполнение его в состоянии 8 способно снова перевести агента в состояние 6 (согласно закону Мэрфи), и в этом случае данный план оканчивается неудачей.
Исследуя пространство доверительных состояний для этой версии задачи, можно легко определить, что ни одна фиксированная последовательность действий не гарантирует решение данной задачи. Однако решение существует, при условии, что мы не будем настаивать на фиксированной последовательности действий:
[ Suck, Right, if [R, Dirty] then Suck ]
Тем самым дополняется пространство решений для включения возможности выбора действий с учетом непредвиденных ситуаций, возникающих во время выполнения. Многие задачи в реальном, физическом мире усложняются из-за наличия проблемы непредвиденных ситуаций, поскольку точные предсказания в них невозможны. По этой причине многие люди соблюдают предельную осторожность во время пеших прогулок или вождения автомобиля.
Иногда проблемы непредвиденных ситуаций допускают чисто последовательные решения. Например, рассмотрим полностью наблюдаемый мир закона Мэрфи. Непредвиденные ситуации возникают, если агент выполняет действие Suck в чистом квадрате, поскольку при этом в данном квадрате может произойти или не произойти отложение мусора. При том условии, что агент никогда не будет очищать чистые квадраты, не будут возникать какие-либо непредвиденные ситуации и поэтому из любого начального состояния можно будет найти последовательное решение (упр. 3.18).
Алгоритмы для решения проблем непредвиденных ситуаций являются более сложными по сравнению с алгоритмами стандартного поиска, приведенными в этой главе; они рассматриваются в главе 12. Кроме того, проблемы непредвиденных ситуаций требуют применения немного иного проекта агента, в котором агент может действовать до того, как найдет гарантированный план. Это полезно, поскольку вместо предварительного обдумывания каждой возможной непредвиденной ситуации, которая могла бы возникнуть во время выполнения, часто бывает лучше приступить к действию и узнать, какие непредвиденные ситуации действительно возникают. После этого агент может продолжать решать свою задачу, принимая в расчет эту дополнительную информацию. Такой тип чередования поиска и выполнения является также полезным при решении проблем исследования (см. раздел 4.5) и при ведении игр (см. главу 6).
В настоящей главе представлены методы, которые могут использоваться агентом для выбора действий в таких вариантах среды, которые являются детерминированными, наблюдаемыми, статическими и полностью известными. В таких случаях агент может формировать последовательности из действий, позволяющих ему достичь своих целей; такой процесс называется поиском.
• Прежде чем агент сможет приступить к поиску решений, он должен сформулировать цель, а затем использовать эту цель для формулировки задачи.
• Задача состоит из четырех частей: начальное состояние, множество действий, функция проверки цели и функция стоимости пути. Среда задачи представлена пространством состояний, а путь через пространство состояний от начального состояния до целевого состояния представляет собой решение.
• Для решения любой задачи может использоваться единый, общий алгоритм Tree-Search; конкретные варианты этого алгоритма воплощают различные стратегии.
• Алгоритмы поиска оцениваются на основе полноты, оптимальности, временной и пространственной сложности. Сложность зависит от коэффициент ветвления в пространстве состояний, Ь, и глубины самого поверхностного решения, d.
• При поиске в ширину для развертывания выбирается самый поверхностный неразвернутый узел в дереве поиска. Этот поиск является полным, оптимальным при единичных стоимостях этапов и характеризуется временной и пространственной сложностью 0(bd). В связи с такой пространственной сложностью в большинстве случаев он становится практически не применимым. Поиск по критерию стоимости аналогичен поиску в ширину, но предусматривает развертывание узла с самой низкой стоимостью пути, д(п). Он является полным и оптимальным, если стоимость каждого шага превышает некоторое положительное предельное значение 8.
• При поиске в глубину для развертывания выбирается самый глубокий неразвернутый узел в дереве поиска. Этот поиск не является ни полным, ни оптимальным, и характеризуется временной сложностью О (if1) и пространственной сложностью О(Ьт), где т — максимальная глубина любого пути в пространстве состояний.
• При поиске с ограничением глубины на поиск в глубину налагается установленный предел глубины.
• При поиске с итеративным углублением вызывается поиск с ограничением глубины и каждый раз устанавливаются увеличивающиеся пределы, до тех пор, пока цель не будет найдена. Этот поиск является полным и оптимальным при единичных стоимостях этапов и характеризуется временной сложностью О (bd) и пространственной сложностью О (bd).
• Двунаправленный поиск способен чрезвычайно уменьшить временную сложность, но он не всегда применим и может потребовать слишком много пространства.
• Если пространство состояний представляет собой граф, а не дерево, то может оказаться целесообразной проверка повторяющихся состояний в дереве поиска. Алгоритм Graph-Search устраняет все дублирующие состояния.
• Если среда является частично наблюдаемой, то агент может применить алгоритмы поиска в пространстве доверительных состояний, или множестве возможных состояний, в которых может находиться агент. В некоторых случаях может быть сформирована единственная последовательность решения; в других случаях агенту требуется план действий в непредвиденных ситуациях, чтобы иметь возможность справиться со всеми неизвестными обстоятельствами, которые могут возникнуть.