Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 48
Текст из файла (страница 48)
Каноническим примером применения поиска в оперативном режиме может служить робот, который помещен в новое здание и должен его исследовать, чтобы составигь карту, которую может затем использовать для перехода из точки л в точку и. Примерами алгоритмов поиска в оперативном режиме являются также методы выхода из лабиринтов (как известно, такие знания всегда были нужны вдохновляющим нас на подвиги героям древности). Однако исследование пространства — это не единственная форма познания окружающего мира.
Рассмотрим поведение новорожденного ребенка: в его распоряжении есть много возможных действий, но он не знает, к чему приведет выполнение какого-либо из них, а эксперименты проводит лишь в немногих возможных состояниях, которых он может достичь. Постепенное изучение ребенком того, как устроен мир, отчасти представляет собой процесс поиска в оперативном режиме. Задачи поиска в оперативном режиме Любая задача поиска в оперативном режиме может быть ре1пена только агентом, выполняющим и вычисления, и действия, а не осуществляющим лишь вычислительные процессы. Предполагается, что агент обладает только описанными ниже знаниями. ° Функция Ассзопв (л), которая возвращает список действий, допустимых в состоянии в.
° Функция стоимости этапа с(в, а, л ' ); следует отметить, что она не может использоваться до тех пор, пока агент не знает, что результатом является состояние я'. ° Функция эоа1-тев с ( я) . Следует, в частности, отметить, что агент не может получить доступ к преемникам какого-либо состояния, иначе чем путем фактического опробования всех действий в этом состоянии. Например, в задаче с лабиринтом, показанной на рис. 4.!2, Глава 4. Информированный поиск и исследование пространства состояний 193 фактически оно остается истинным также и для обратимого случая (см. рис. 4.13, б).
По этой причине обычно принято описывать производительность алгоритмов поиска в оперативном режиме с учетом размеров всего пространства состояний, а не только глубины самой поверхностной цели. Агенты, выполняющие поиск в оперативном режиме После каждого действия агент, выполняющий поиск в оперативном режиме, получает результаты акта восприятия, с помощью которых может узнать, какого состояния он достиг; на основании этой информации агент может дополнить карту своей среды.
Текущая карта используется для принятия решения о том, куда двигаться дальше. Такое чередование планирования и выполнения действий означает, что алгоритмы поиска в оперативном режиме весьма значительно отличаются от алгоритмов поиска в автономном режиме, которые рассматривались выше. Например, алгоритмы поиска в автономном режиме, такие как А*, обладают способностью развертывать узел в одной части пространства, а затем немедленно развертывать узел в другой части пространства, поскольку для развертывания узла требуются моделируемые, а не реальные действия.
С другой стороны, любой алгоритм поиска в оперативном режиме позволяет агенту развертывать только тот узел, который он физически занимает. Для предотвращения необходимости путешествовать через все дерево, чтобы развернуть следующий узел, представляется более удобным развертывание узлов в локальном порядке. Именно таким свойством обладает поиск в глубину, поскольку (за исключением операции возврата) следующий развертываемый узел является дочерним узлом ранее развернутого узла. Алгоритм агента, выполняющего поиск в глубину в оперативном режиме, приведен в листинге 4.5.
Агент хранит составленную им карту в таблице гево2 с [а, и!, в которой регистрируются состояния, явившиеся следствием выполнения действия а в состоянии и. Этот агент предпринимает попытку выполнения из текущего состояния любого действия, которое еще не было исследовано в этом состоянии.
Сложности возникают после того, как агент опробовал все действия в некотором состоянии. При поиске в глубину в автономном режиме это состояние удаляется из очереди, а при поиске в оперативном режиме агент должен выполнить возврат физически. При поиске в глубину это равносильно возврату в последнее по времени состояние, из которого агент перешел в текущее состояние. Соответствующая организация работы обеспечивается за счет ведения такой таблицы, где для каждого состояния перечисляются состояния-предшественники, к которым агент еше не выполнял возврат. Если агент исчерпал список состояний, к которым может выполнить возврат, это означает, что проведенный агентом поиск является полным.
Лпсгпнг 4.5. Агент, выполняющий попок в оперативном режиме, который проводит исследование с использованием поиска в глубину. Этот агент может применяться только в пространствах двунаправленного поиска гппог1оп Оп11пе-ВРЯ-йдепп(а') гегпгпя дейотвие аседоп 1прцсп: в', восприятие, позволяющее идентифицировать текумее состояние ясагао: геяи1Е, таблица, индексированная по действиям и состояниям, первоначально пустая Часть П.
Решение проблем 194 цпехр1огес), таблица, в которой для каждого посещенного состояния перечислены еще не опробованные действия ипЬасхегас)ген, таблица, в которой для каждого посещенного состояния перечислены еще не опробованные возвраты в, а, предыдущие состояние и действие, первоначально неопределенные ЬЕ Ооа1-тево(в') с[тел хевплп веор ЬЕ в' представляет собой новое состояние Спел цпехр1огеб[в'! е- Асоьопв[а') Ья в не является неопределенным епеп бо гевц1с[а, в! ь- в' добавить в в начало таблицы ильасхегас)гес([в'] Ья элемент ипехр1огеЯв'! пуст Епеп ЬЕ элемент ипьас)сегасхеЯв'! пуст Епеп тесцхп ееор е1ве а ь- действие Ь, такое что геяи1С[Ь, в'! = Рор(ипЬас)гедас)гед[е'!) е1ве а ь- Рор(илехр1огео[в'!) в < — в' леепхп а Рекомендуем читателю провести трассировку хода выполнения процедуры Оп11пе-Ррв-Адепб применительно к лабиринту, показанному на рис. 4 12.
Можно довольно легко убедиться в том, что в наихудшем случае агент в конечном итоге пройдет по каждой связи в данном пространстве состояний точно два раза. При решении задачи обследования такая организация работы является оптимальной; а при решении задачи поиска целей, с другой стороны, коэффициент конкурентоспособности может оказаться сколь угодно неэффективным, если агент будет отправляться в длительные экскурсии, притом что целевое состояние находится непосредственно рядом с начальным состоянием.
Такая проблема решается с использованием варианта метода итеративного углубления для работы в оперативном режиме; в среде, представляюшей собой однородное дерево, коэффициент конкурентоспособности подобного агента равен небольшой константе. В связи с тем что в алгоритме Оп11пе-РРЯ-Адепс используется метод с возвратами, он может применяться только в таких пространствах состояний, где действия являются обратимыми.
Сушествуют также немного более сложные алгоритмы, применимые в пространствах состояний общего вида, но ни один из подобных алгоритмов не характеризуется ограниченным коэффициентом конкурентоспособности. Локальный поиск в оперативном режиме Как и поиск в глубину, поиск с восхождением к вершине обладает свойством локализации применительно к операциям развертывания в нем узлов. В действительности сам поиск с восхождением к вершине уже можно считать алгоритмом поиска в оперативном режиме, поскольку предусматривает хранение в памяти только одного текушего состояния! К сожалению, в своей простейшей форме этот алгоритм не очень полезен, так как оставляет агента в таком положении, что последний не может покинуть локальный максимум и отправиться куда-то еШе.
Более того, в этом алго- Глава 4. Информированный поиск и исследование пространства состояний 195 ритме не может использоваться перезапуск случайным образом, поскольку агент не способен перенести самого себя в новое состояние. Вместо перезапуска случайным образом для исследования среды может быть предусмотрено использование ~ случайного блуждания (гапг[ош хна[[с).
В методе случайного блуждания просто выбирается случайным образом одно нз действий, доступных из текущего состояния; предпочтение отдается действиям, которые еше не были опробованы. Легко доказать, что метод случайного блуждания позволяет агенту в конечном итоге найти цель или выполнить свою задачу исследования, при условии, что пространство является конечным". С другой стороны, этот процесс может оказаться очень продолжительным. На рис.
4.14 показана среда, в которой для поиска цели с помощью метода случайного блуждания может потребоваться количество этапов„измеряемое экспоненциальной зависимостью, поскольку на каждом этапе вероятность шага назад вдвое превышает вероятность шага вперед. Безусловно, что этот пример является надуманным, но существует много реальных пространств состояний, топология которых способствует возникновению "ловушек" такого рода при случайном блуждании. Рис.
4. 14. Среда, в которой применение метода случайнага блуждания длл поиска цели требует выполнения такого количества этапов, которое апределяетгя экгпаненциильнай зависимостью Как оказалось, более эффективным подходом является дополнение метода поиска с восхождением к вершине способностью запоминать, а не способностью выбирать следующее действие случайным образом. Основная идея состоит в том, что необходимо хранить в памяти "текущую наилучшую оценку" н(и) стоимости постижения цели из каждого состояния, которое уже было посешено. На первых порах н( я) представляет собой только эвристическую оценку )з ( в) и обновляется по мере того, как агент приобретает опыт в исследовании пространства состояний. На рис. 4.15 показан простой пример одномерного пространства состояний. На рис.
4.15, а показано, что агент, по-видимому, зашел в тупик, попав в плоский локальный минимум, соответствующий затененному состоянию. Вместо того чтобы оставаться там, где находится, агент должен последовать по тому пути, который может рассматриваться как наилучший путь к цели согласно текущим оценкам стоимостей для соседних состояний.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
