Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 49
Текст из файла (страница 49)
Оценка стоимости достижения цели через соседнее состояние в ' равна оценке стоимости достижения а ', которая складывается с оценкой стоимости достижения цели из в', т.е. равна с(в, а, я' ) +у((н' ) . В данном примере имеются два действия, с оценками стоимости 1+9 и 1+2, поэтому, по всей видимости, лучше всего двигаться вправо.
После этого становится очевидно, что оценка стоимости для н Этот вариант бесконечного пространства фактически является гораздо более сложным. Методы случайного блуждания являются полными в бесконечных одно- и двухмерных решетках, но не в трехмерных! В последнем случае вероятность того, что блуждающий агент а конечном итоге возвратится а начальную точку, составляет лишь около 0,3405 (для ознакомления с общим введением в эту тему см.
[7031). Часть И. Решение проблем !9б этого затененного состояния, равная 2, была слишком оптимистической. Поскольку стоимость наилучшего хода равна 1 и он ведет в состояние, которое находится по меньшей мере на расстоянии 2 шагов от цели, то затененное состояние должно находиться по меньшей мере на расстоянии 2 шагов от цели, поэтому его оценка и должна быть обновлена соответствующим образом, как показано на рис. 4.15, б. Продолжая этот процесс, агент перейдет вперед и назад еше дважды, каждый раз обновляя оценку и н "сглаживая' локальный минимум до тех пор, пока не вырвется из него вправо. 8 9 2 2 4 3 б) 8 9 С3) 2 4 3 в) 8 9 3 Д4 4 3 г) 8 9 Д5 4 4 3 ) 8 9 5 О5 4 3 Рис.
4.!5. Пять итераций алгоритма 1 яТА ч в одномерном нространстве состояний. Каждое состояние обозначено значением н (в ), текущей оценкои стоимости достижения цели, а каждая дуга обозначена соответствующей ей стоимостью этапа. Затененное состояние показывает местонахождение агента, а значения, обновлеииьсе после казкдой итерации, обозначаются двойным кружком Алгоритм агента, в котором реализована эта схема. получивший название поиска А* в реальном времени с обучением (1 еагп!пя йеа1-Т!ше А" — га ЖАКТА*), показан в листинге 4.6. Каки в алгоритме оп15пе-прб-Адепт, в данном алгоритме составляется карта среды с использованием таблицы . есц2с.
Этот алгоритм обновляет оценку стоимости для состояния, которое он только что оставил, а затем выбирает ход, "который представляется наилучшим" в соответствии с его текушими оценками стоимости. Следует отметить одну важную деталь, что действия, которые еше не были опробованы в состоянии а, всегда рассматриваются как ведущие непосредственно к цели с наименьшей возможной стоимостью, а именно )з ( в ) . Такой Ъ. оптимизм в отношении неопределенности побуждает агента исследовать новые пути, которые могут действительно оказаться перспективными.
Листинг 4.б. Функция ьвтк -Адепс выбирает действие в соответствии со значениями соседних состояний, которые обновляются по мере тонг, как агент передвигается в пространстве состояний бппсеьоп (.атА*-Ацепс(в') кеспкпв действие а Ьпрпсв: в', восприятие, позволяющее идентифицировать текущее состояние Глава 4. Информированный поиск и исследование пространства состояний 197 веаеьс". геяи1С, таблица, индексированная по действиям и состояниям, первоначально пустая Н, таблица оценок стоимостей, индексированная по состояниям, первоначально пустая я, а, предыдущие состояние и действие, первоначально неопределенные ЕЕ Соа1-Теяе(я') Свес гееигп ягор ЕЕ я' является одним из новых состояний (отсутствующим в Н) сцеп н(я'1 ь- Ь(я') ип1евв я является неопределенным геяи1с[а, я] ь- я' Н[я) ь- вип АПТА*-Сове(я, Ь, геяи1С[Ь, я], Н) ЬОАоеьопя(в) а ь- одно из действий Ь среди действий Асеьопв(я'), которое минимизирует значение ьнТА*-Сояс(я', Ь, геяи1с[Ь, я'1, Н) я ь — я' гесигп а ЕипссЕоп ЬНТА*-Сове(я, а, я', Н) гееигпв оценка стоимости ЕЕ я' является неопределенным слеп гесигп Ь(я) е1ве геспгп с(я,а,я') + Н[я'! Гарантируется, что агент 1.КТА* найдет цель в любой конечной, безопасно исследуемой среде.
Однако, в отличие от А', в бесконечных пространствах состояний применяемый в этом агенте алгоритм становится неполным, поскольку в некоторых случаях этот алгоритм может вовлечь агента в бесконечные блуждания. В наихудшем случае данный алгоритм позволяет исследовать среду с и состояниями за О(и'] этапов, но чаше всего действует намного лучше. Агент 1.КТА* представляет собой лишь один пример из большого семейства агентов, выполняющих поиск в оперативном режиме, которые могут быть определены путем задания правила выбора действия и правила обновления различными способами.
Это семейство агентов, которое было первоначально разработано для стохастических вариантов среды, рассматривается в главе 21. Обучение в ходе поиска в оперативном режиме То, что агенты, выполняющие поиск в оперативном режиме, на первых порах находятся в полном неведении, открывает некоторые возможности для обучения.
Во-первых, агенты изучают '"карту" своей среды (а точнее, результаты каждого действия в каждом состоянии), регистрируя результаты каждого из своих опытов. (Обратите внимание на то, что из предположения о детерминированности среды следует, что для изучения любого действия достаточно проведения одного эксперимента.) Во-вторых, агенты, выполняющие локальный поиск, получают все более точные оценки значения каждого состояния, используя локальные правила обновления, как в алгоритме 1.КТА*. В главе 21 будет показано, что в конечном итоге такие обновления сходятся к точным значениям для кам(лого состояния, при условии, что агент исследует пространство состояний правильным способом.
А после того как станут известными точные значения, оптимальные решения могут быть приняты путем перемещения к преемнику с наи- 198 Часть П. Решение проблем высшим значением, т.е. в таком случае оптимальной стратегией становится метод поиска с восхождением к вершине в чистом виде. Если читатель выполнил нашу рекомендацию провести трассировку поведения алгоритма Оп11пе-Г)РБ-лиепе в среде, пОказанной на рис. 4.12, то должен был заметить, что этот агент не слишком умен.
Например, после того как агент обнаружил, что действие (гр ведет из пункта (1, 1) в пункт (1, 2), он еще не знает, что действие роигп возвратит его назад в пункт (1, 1) или что следующее действие ур приведет его из пункта (2, 1) в пункт (2, 2 ), из пункта (2, 2) в пункт (2, 3 ) и т д. Вообще говоря, было бы желательно, чтобы агент освоил в результате обучения, что действие (гр приводит к увеличению координаты у, если на этом пути нет стены, и что действие г)оигп приводит к уменьшению этой координаты, и т.д. Для того чтобы это произошло, требуются две составляющие.
Во-первых, необходимо формальное и явно манипулируемое представление общих правил такого рода; до сих пор мы скрывали эту информацию внутри "черного ящика", называемого (буикиией определения преемника. Данному вопросу посвящена часть П!. Во-вторых, нужны алгоритмы, позволяющие формировать подходящие общие правила из конкретных наблюдений, сделанных агентом. Эта тема рассматривается в главе 18.
РЕЗЮМЕ В данной главе рассматривалось применение эвристических функций для уменьшения стоимости поиска. В ней исследовался целый ряд алгоритмов, в которых используются эвристические функции, и было установлено, что даже при использовании хороших эвристических функций достижение оптимальности связано с увеличением стоимости поиска. ° Поиск по первому наилучшему совпадению сводится просто к применению алгоритма ~кар)т-Яеахс)т, в котором для развертывания выбираются неразвернутые узлы с минимальной стоимостью (в соответствии с некоторым критерием).
В алгоритмах поиска по первому наилучшему совпадению обычно используется эвристическая функция й(п), которая оценивает стоимость достижения решения из узла п. ° При жадном поиске по первому наилучшему совпадению развертываются узлы с минимальным значением И (и) . Этот поиск не оптимален, но часто является эффективным. ° При поиске А' развертываются узлы с минимальным значением й(п) =д(п) +й(п) . Алгоритм А* является полным и оптимальным, при условии, что гарантирована допустимость (для алгоритма тгее-яеагс)т) или преемственность (для алгоритма агар)т-Яеагс)т) функции й(п). Пространственная сложность алгоритма А" все еще остается слишком высокой. ° Производительность алгоритмов эвристического поиска зависит от качества эвристической функции.
Иногда хорошие эвристические функции можно составить путем ослабления определения задачи, предварительного вычисления стоимости решения подзадач и сохранения этой информации в базе данных шаблонов или обучения на основе опыта решения данного класса задач. Глава 4. Информированный поиск и исследование пространства состояний 199 ° Алгоритмы КВРЯ и ЯМА"' представляют собой надежные, оптимальные алгоритмы поиска, в которых используются ограниченные обьемы памяти; при наличии достаточного количества времени эти алгоритмы могут решать такие задачи, которые не позволяет решать алгоритм А*, поскольку исчерпывает доступную память. ° Такие методы локального поиска, как поиск с восхождением к вершине, действуют на основе формулировок полного состояния и предусматривают хранение в памяти лишь небольшого количества узлов.
Было разработано также несколько стохастических алгоритмов, включая поиск с эмуляцией отжита, которые возвращают оптимальные решения при наличии подходящего графика "охлаждения" (т.е. графика постепенного уменьшения величины случайного разброса). Кроме того, многие методы локального поиска могут использоваться для решения задач в непрерывных пространствах. ° Генетический алгоритм представляет собой стохастнческий поиск с восхождением к вершине, в котором сопровождается большая популяция состояний. Новые состояния формируются с помощью мутации и скрещивания; в последней операции комбинируются пары состояний, взятых из этой популяции. ° Проблемы исследования возникают, если агент не имеет никакого представления о том, каковы состояния и действия в его среде.
Для безопасно исследуемых вариантов среды агенты, выполняющие поиск в оперативном режиме, могут составить карту и найти цель, если она существует. Эффективным методом выхода из локальных минимумов является обновление эвристических оценок на основе опыта. БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕТКИ Пример использования эвристической информации при решении задач впервые появился в одной из ранних статей Саймона и Ньюэлла [1419], но само выражение "эвристический поиск" и обоснование применения эвристических функций, которые оценивают расстояние до цели, появились немного позже [932], [! 126].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
