Обучение в ходе поиска в оперативном режиме
То, что агенты, выполняющие поиск в оперативном режиме, на первых порах находятся в полном неведении, открывает некоторые возможности для обучения. Во-первых, агенты изучают "карту" своей среды (а точнее, результаты каждого действия в каждом состоянии), регистрируя результаты каждого из своих опытов. (Обратите внимание на то, что из предположения о детерминированности среды следует, что для изучения любого действия достаточно проведения одного эксперимента.) Во-вторых, агенты, выполняющие локальный поиск, получают все более точные оценки значения каждого состояния, используя локальные правила обновления, как в алгоритме LRTA*. В главе 21 будет показано, что в конечном итоге такие обновления сходятся к точным значениям для каждого состояния, при условии, что агент исследует пространство состояний правильным способом. А после того как станут известными точные значения, оптимальные решения могут быть приняты путем перемещения к преемнику с наивысшим значением, т.е. в таком случае оптимальной стратегией становится метод поиска с восхождением к вершине в чистом виде.
В данной главе рассматривалось применение эвристических функций для уменьшения стоимости поиска. В ней исследовался целый ряд алгоритмов, в которых используются эвристические функции, и было установлено, что даже при использовании хороших эвристических функций достижение оптимальности связано с увеличением стоимости поиска.
• Поиск по первому наилучшему совпадению сводится просто к применению алгоритма Graph-Search, в котором для развертывания выбираются неразвернутые узлы с минимальной стоимостью (в соответствии с некоторым критерием). В алгоритмах поиска по первому наилучшему совпадению обычно используется эвристическая функция п(п), которая оценивает стоимость достижения решения из узла п.
• При жадном поиске по первому наилучшему совпадению развертываются узлы с минимальным значением п(п). Этот поиск не оптимален, но часто является эффективным.
• При поиске А* развертываются узлы с минимальным значением f(n) =g(n) +h(n). Алгоритм А* является полным и оптимальным, при условии, что гарантирована допустимость (для алгоритма Tree-Search) или преемственность (для алгоритма Graph-Search) функции п(п). Пространственная сложность алгоритма А* все еще остается слишком высокой.
• Производительность алгоритмов эвристического поиска зависит от качества эвристической функции. Иногда хорошие эвристические функции можно составить путем ослабления определения задачи, предварительного вычисления стоимости решения подзадач и сохранения этой информации в базе данных шаблонов или обучения на основе опыта решения данного класса задач.
Если читатель выполнил нашу рекомендацию провести трассировку поведения алгоритма Online-DFS-Agent в среде, показанной на рис. 4.12, то должен был заметить, что этот агент не слишком умен. Например, после того как агент обнаружил, что действие Up ведет из пункта (1,1) в пункт (1, 2), он еще не знает, что действие Down возвратит его назад в пункт (1,1) или что следующее действие Up приведет его из пункта (2,1) в пункт (2 , 2), из пункта (2,2) в пункт (2,3) и т.д. Вообще говоря, было бы желательно, чтобы агент освоил в результате обучения, что действие Up приводит к увеличению координаты у, если на этом пути нет стены, и что действие Down приводит к уменьшению этой координаты, и т.д. Для того чтобы это произошло, требуются две составляющие. Во-первых, необходимо формальное и явно манипулируемое представление общих правил такого рода; до сих пор мы скрывали эту информацию внутри "черного ящика", называемого функцией определения преемника. Данному вопросу посвящена часть III. Во-вторых, нужны алгоритмы, позволяющие формировать подходящие общие правила из конкретных наблюдений, сделанных агентом. Эта тема рассматривается в главе 18.
• Алгоритмы RBFS и SMA* представляют собой надежные, оптимальные алгоритмы поиска, в которых используются ограниченные объемы памяти; при наличии достаточного количества времени эти алгоритмы могут решать такие задачи, которые не позволяет решать алгоритм А*, поскольку исчерпывает доступную память.
• Такие методы локального поиска, как поиск с восхождением к вершине, действуют на основе формулировок полного состояния и предусматривают хранение в памяти лишь небольшого количества узлов. Было разработано также несколько стохастических алгоритмов, включая поиск с эмуляцией отжига, которые возвращают оптимальные решения при наличии подходящего графика "охлаждения" (т.е. графика постепенного уменьшения величины случайного разброса). Кроме того, многие методы локального поиска могут использоваться для решения задач в непрерывных пространствах.
• Генетический алгоритм представляет собой стохастический поиск с восхождением к вершине, в котором сопровождается большая популяция состояний. Новые состояния формируются с помощью мутации и скрещивания; в последней операции комбинируются пары состояний, взятых из этой популяции.
• Проблемы исследования возникают, если агент не имеет никакого представления о том, каковы состояния и действия в его среде. Для безопасно исследуемых вариантов среды агенты, выполняющие поиск в оперативном режиме, могут составить карту и найти цель, если она существует. Эффективным методом выхода из локальных минимумов является обновление эвристических оценок на основе опыта.
Пример использования эвристической информации при решении задач впервые появился в одной из ранних статей Саймона и Ньюэлла [1419], но само выражение "эвристический поиск" и обоснование применения эвристических функций, которые оценивают расстояние до цели, появились немного позже [932], [1126]. Доран и Мичи [404] осуществили обширные экспериментальные исследования в области применения эвристического поиска к решению ряда задач, в частности задач игры в восемь и игры в пятнадцать. Хотя Доран и Мичи провели теоретический анализ длины пути и "проникновения" (penetrance) (отношения длины пути к общему количеству узлов, исследованных к данному моменту) в процессе эвристического поиска, они, по-видимому, игнорировали ту информацию, которую может предоставить текущая длина пути. Алгоритм А*, предусматривающий использование в эвристическом поиске текущего значения длины пути, был разработан Хартом, Нильссоном и Рафаэлем [623], с некоторыми дальнейшими поправками [624]. Дек-стер и Перл [371] продемонстрировали оптимальную эффективность алгоритма А*.
В указанной выше оригинальной статье, посвященной алгоритму А*, было впервые представлено условие преемственности (consistency condition), которому должны удовлетворять эвристические функции. В качестве более простой замены этого условия Полом [1223] было предложено условие монотонности, но Перл [1188] показал, что эти два условия эквивалентны. Аналоги открытых и закрытых списков использовались