Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 38
Текст из файла (страница 38)
Ниже перечислены предлагаемые задания. а) Реализуйте описанную среду и агента, решающего задачи для этой среды. После каждой телепортации агент должен будет сформулировать новую задачу, которая предусматривает также определение его текущего местоположения. б) Зарегистрируйте данные о производительности предложенного вами агента (для этого предусмотрите выработку агентом соответствующих комментариев по мере его передвижения в среде) и составьте отчет о его производительности по данным, охватывающим больше 100 эпизодов. в) Модифицируйте среду так, чтобы в 30% случаев движение агента заканчивались в не предусмотренном им месте назначения (выбранном случайным образом среди других видимых вершин, если таковые имеются, а в противном случае соответствующем ситуации, в которой вообгде не было выполнено никакого движения).
Это — грубая модель ошибок при выполнении движений реального робота. Доработайте определение агента так, чтобы при обнаружении указанной ошибки он определял, где находится, а затем создавал план возвращения в то место, где он находился прежде, и возобновлял выполнение прежнего плана. Помните, что иногда попытка возвращения в прежнее место также может оканчиваться неудачей! Продемонстрируйте пример агента, который успешно преодолевает две последовательные ошибки движения и все равно достигает цели. г) Опробуйте две различные схемы возобновления работы после ошибки: вопервых, отправиться к ближайшей вершине из первоначально~о маршрута и, во-вторых, перепланировать маршрут к цели от нового местоположения. Сравните производительность всех схем возобновления работы.
Влияет ли на результаты такого сравнения включение затрат на поиск? д) Теперь предположим, что есть такие местоположения, представления среды из которых являются идентичными. (Например, предположим, что мир — это решетка с квадратными препятствиями.) С какой проблемой теперь сталкивается агент? Как должны выглядеть решения? 3.17.
На с. 115 было указано, что мы не будем принимать во внимание задачи с отрицательными значениями стоимости пути. В данном упражнении эта тема рассматривается немного более подробно. а) Предположим, что действия могут иметь произвольно большие отрицательные стоимости; обьясните, почему такая ситуация может вынудить любой оптимальный алгоритм исследовать полное пространство состояний.
б) Удастся ли выйти из этого положения, потребовав, чтобы стоимости этапов были больше или равны некоторой отрицательной константе с? Рассмотрите и деревья, и графы. 152 Часть П. Решение проблем в) Предположим, что имеется множество операторов, образующих цикл, так что выполнение операторов этого множества в определенном порядке не приводит к какому-либо чистому изменению состояния. Если все эти операторы имеют отрицательную стоимость, то какие выводы из этого следуют применительно к оптимальному поведению агента в такой среде? г) Можно легко представить себе, что операторы с высокой отрицательной стоимостью имеются даже в таких проблемных областях, как поиск маршрута. Например, некоторые участки дороги могут оказаться настолько живописными, что стремление ознакомиться с ними намного перевесит обычные здравые рассуждения о стоимости, измеряемой в терминах затрат времени и топлива.
Объясните, применяя точные термины, принятые в контексте поиска в пространстве состояний, почему все же люди не ведут свои автомобили неопределенно долго по живописным циклическим участкам пути, и укажите, каким образом нужно определить пространство состояний и операторы для задачи поиска маршрута, чтобы агенты с искусственным интеллектом также могли избежать попадания в цикл. д) Можете ли вы придумать пример такой реальной проблемной области, в которой стоимости этапов таковы, что могут вызвать возникновение цикла? 3.18. Рассмотрим мир пылесоса без датчиков, с двумя местоположениями, подчиняющийся закону Мэрфи.
Нарисуйте пространство доверительных состояний, достижимых из начального доверительного состояния (1, 2, 3, 4, 5, б, 7, 8), и объясните, почему эта задача неразрешима. Покажите также, что если бы этот мир был полностью наблюдаемым, то существовала бы последовательность решения для каждого возможного начального состояния. 3.19.
Й) Рассмотрим залачу в мире пылесоса, который определен на рис. 2.2. а) Какой из алгоритмов, определенных в этой главе, был бы подходящим для решения этой задачи? Должен ли этот алгоритм проверять наличие повторяющихся состояний? б) Примените выбранный вами алгоритм для вычисления оптимальной последовательности действий в мире с размером 3 хЗ, в начальном состоянии которого в трех верхних квадратах имеется мусор, а агент находится в центре. в) Сконструируйте агента, выполняющего поиск в этом мире пылесоса, и оцените его работу в множестве миров с размером ЗхЗ, характеризухлдемся вероятностью наличия мусора в каждом квадрате, равной О . 2. Включите в состав показателя производительности не только стоимость поиска, но и стоимость пути, используя для них подходящий "курс обмена".
г) Сравните вашего лучшего поискового агента с простым рандомизированным рефлексным агентом, который всасывает мусор, если последний имеется, а в противном случае выполняет случайно выбранные перемещения. д) Рассмотрите, что произошло бы, если ли бы мир расширился до размеров пхп. Как производительность данного поискового агента и рефлексного агента зависит от п? В этой главе показано, как можно с помощью информации о пространстве состояний не дать алгоритмам заблудиться в темноте.
В главе 3 показано, что неинформированные стратегии поиска позволяют находить решения задач пугем систематической выработки новых состояний и их проверки применительно к цели. К сожалению, в большинстве случаев эти стратегии являются чрезвычайно неэффективными.
Как показано в настояшей главе, информированные стратегии поиска (в которых используются знания, относящиеся к конкретной задаче) обеспечивают более эффективный поиск решения. В разделе 4.1 описаны информированные версии алгоритмов главы 3, а в разделе 4.2 показано, как может быть получена необходимая информация, относящаяся к конкретной задаче.
В разделах 4.3 и 4.4 представлены алгоритмы, которые выполняют исключительно локальный поиск в пространстве состояний, оценивая и модифицируя одно или несколько текуШих состояний вместо систематического исследования путей из начального состояния. Эти алгоритмы применимы для решения задач, в которых стоимость пути не представляет интереса и требуется лишь найти состояние, соответствуюшее решению. К этому семейству алгоритмов локального поиска относятся методы, созданные под влиянием исследований в области статистической физики (моделируемый отжиг) и эволюционной биологии (генетические алгоритмы). Наконец, в разделе 4.5 рассматривается поиск в оперативном режиме, в котором агент сталкивается с полностью неизвестным пространством состояний.
154 Часть П. Решение проблем 4.1. СТРАТЕГИИ ИНФОРМИРОВАННОГО (ЭВРИСТИЧЕСКОГО) ПОИСКА В данном разделе показано, как стратегия 'в. информированного поиска (в которой кроме определения самой задачи используются знания, относящиеся к данной конкретной проблемной области) позволяет находить решения более эффективно, чем стратегия неинформированного поиска. Общий рассматриваемый здесь подход называется оь поиском по первому наилучшему совпадению. Поиск по первому наилучшему совпадению представляет собой разновидность общего алгоритма Тгее-Яеа гсЬ или СгарЬ-ЯеагсЬ, в котором узел лля развертывания выбирается на основе Ж функции оценки, Е(п) . По традиции для развертывания выбирается узел с наименьшей оценкой, поскольку такая оценка измеряет расстояние до цели.
Поиск по первому наилучшему совпадению может быть реализован в рамках описанной в данной книге общей инфраструктуры поиска с помощью очереди по приоритету — структуры данных, в которой периферия поиска поддерживается в возрастающем порядке ('-значений. Название "поиск по первому наилучшему совпадению" (Ьез( В(гз( зеагсЬ) узаконено традицией, но неточно.
В конце концов, если бы мы действительно могли развертывать наилучший узел первым, то не было бы и поиска как такового; решение задачи представляло бы собой прямое шествие к цели. Единственное, что мы можем сделать, — это выбрать узел, который представляется наилучшим в соответствии с функцией оценки. Если функция оценки действительно является точной, то выбранный узел в самом деле окажется наилучшим узлом, но фактически функция оценки иногда оказывается малопригодной и способной завести поиск в тупик.
Тем не менее авторы будут придерживаться названия "поиск по первому наилучшему совпадению", поскольку более подходящее название "поиск по первому совпадению, которое можно считать наилучшим" было бы довольно громоздким. Существует целое семейство алгоритмов поиска по первому наилучшему совпадению, пенс-рзгзс-яеагсЬ, с различными функциями оценки'. Ключевым компонентом этих алгоритмов является 'в.
эвристическая функция', обозначаемая как Ь ( и): Л(п) = оценка стоимости наименее дорогостоящего пути от узла и до целевого узла Например, в задаче поиска маршрута в Румынии можно было бы оценивать стоимость наименее дорогостоящего пути от Арада до Бухареста с помощью расстояний по прямой до Бухареста, измеряемых в узловых точках маршрута от Арада до Бухареста. Эвристические функции (или просто эвристики) представляют собой наиболее общую форму, в которой к алгоритму поиска подключаются дополнительные знания о задаче. Эвристики рассматриваются более подробно в разделе 4.2, а на данный момент мы будем определять их как произвольные функции, относящиеся к конкретной проблеме, с одним ограничением: если п — целевой узел, то )з(п) =о.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
