Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 29
Текст из файла (страница 29)
Этот процесс будет описан более подробно немного позднее. А на данный момент предположим, что агент будет рассматривать действия на уровне автомобильной поездки из одного крупного города в другой. Таким образом, состояния, рассматриваемые агентом, соответствуют его пребыванию в конкретном городе'. Итак, наш агент поставил перед собой цель доехать на автомобиле до Бухареста и определяет, куда отправиться для этого из Арада. Из этого города ведут три дороги: в Сибиу, Тимишоару и Зеринд. Прибытие в какой-либо из этих городов не представляет собой достижение намеченной цели, поэтому агент, не очень знакомый с географией Румынии, не будет знать, по какой дороге он должен следовать'.
Иными словами, агент не знает, какое из его возможных действий является наилучшим, поскольку не обладает достаточными знаниями о состоянии, возникающем в результа- ' Обратите внимание на то, что каждое из этих "состояний** фактически соответствует большому множеству состояний мира, поскольку в состоянии реального мира должен быль определен каждый аспект действительности.
Важно всегда учитывать различие между состояниями, которые рассматриваются в проблемной области решения задач, и состояниями реального мира. з Авторы предполагают, что большинство читателей окажутся в таком же положении и вполне могут представить себя такими же беспомощными, как и наш агент. Приносим свои извинения румынским читателям, которые не смогут воспользоваться преимушествами использованного здесь педагогического приема. Часть П. Решение проблем 112 те выполнения каждого действия.
Если агент не получит дополнительных знаний, то окажется в тупике. Самое лучшее, что он может сделать, — это выбрать одно из указанных действий случайным образом. Но предположим, что у агента есть карта Румынии, либо на бумаге, либо в его памяти. Карта способна обеспечить агента информацией о состояниях, в которых он может оказаться, и о действиях, которые он способен предпринять. Агент имеет возможность воспользоваться этой информацией для определения последовательных этапов гипотетического путешествия через каждый из этих трех городов в попытке найти такой путь, который в конечном итоге приведет его в Бухарест. Найля на карте путь от Арада до Бухареста, агент может достичь своей цели, осуществляя действия по вождению автомобиля, которые соответствуют этапам этого путешествия.
Вообще говоря, ср агент, имеюи(ий несколько непосредственных вариантов выбора с неизвестной стоимостью, может решить, что делать, исследуя вначале различные возможные последовательности действий, которые ведут к состояниям с известной стоимостью, а затем выбирая из них наилучшую последовательность. Описанный процесс определения такой последовательности называется 'ъ. поиском. Любой алгоритм поиска принимает в качестве входных данных некоторую задачу и возврашает ',ъ решение в форме последовательности действий. После того как решение найдено, могут быть осуществлены действия, рекомендованные этим алгоритмом.
Такое осуществление происходит на стадии 1в. выполнения. Итак, для рассматриваемого агента можно применить простой проект, позволяющий применить принцип "сформулировать, найти, выполнить", как показано в листинге 3.1. После формулировки цели и решаемой задачи агент вызывает процедуру поиска для решения этой задачи. Затем он использует полученное решение для руководства своими действиями, выполняя в качестве следующего предпринимаемого мероприятия все, что рекомендовано в решении (как правило, таковым является первое действие последовательности), а затем удаляет этот этап из последовательности. Сразу после выполнения этого решения агент формулирует новую цель. Листинг 3.1.
Прпегпй агент, решающий задачу. Вначале ои формулирует цель и задачу, затем ищет последовательность действий, позволяющую решить зту задачу, и, пакопев, осущесгачяет действия одно за другим. Закончив свою работу, агент формулирует другую цель и начинает сначала. Обратите внимание ип тп, что при выполнении очередной последовательности действий агент ипюрирует данные своих актов восприятия, поскольку прелполшает, что найденное им решение всегда выполнимо гчпсМоп яьтр1е-РгоЫет-яо1чьпд-лдепг(регсерс) геечгпп действие всЫоп ьпрпгп: регсерс, результат восприятия пгаг1с: яед, последовательность действий, первоначально пустая вгаге, некоторое описание текущего состояния мира доа1, пель, первоначально неопределенная ргоЫет, формулировка задачи яснее ч- прг)асе-ясасе(яснее, регсерс) ае последовательность вод пуста гпеп 6о доа1 ч- Рогтч1аге-ооа1 (яснее) ргоЫот ч- Рогтч1аге-ргоЬ1ет(всасе, доа1) яед ч- Яеагсп(ргоЫет) асгдоп ч- Р1гвг(яеч) вод +- веяг(яед) гвечгп асейоп 113 Глава 3.
Решение проблем посредством поиска Вначале опишем процесс составления формулировки задачи, а затем посвятим основную часть данной главы рассмотрению различных алгоритмов для функции Яеагс)т. В этой главе осуществление функций ()рс)псе-Ясасе и роггпц1асе-Соа1 дополнительно не рассматривается.
Прежде чем перейти к подробному описанию, сделаем краткую паузу, чтобы определить, в чем агенты, решающие задачи, соответствуют описанию агентов и вариантов среды, приведенному в главе 2. В проекте агента, показанном в листинге 3.1, предполагается, что данная среда является статической, поскольку этапы формулировки и решения задачи осуществляются без учета каких-либо изменений, которые могут произойти в данной среде. Кроме того, в этом проекте агента допускается, что начальное состояние известно; получить такие сведения проще всего, если среда является наблюдаемой. К тому же в самой идее перечисления "альтернативных стратегий" заключается предположение, что среда может рассматриваться как дискретная.
Последней и наиболее важной особенностью является следующее; в проекте агента предполагается, что среда является детерминированной. Решения задач представляют собой единственные последовательности действий, поэтому в них не могут учитываться какие-либо неожиданные события; более того, решения выполняются без учета результатов каких-либо актов восприятия! Агент, выполняющий свои планы, образно говоря, с закрытыми глазами, должен быть вполне уверенным в том, что он делает. (В теории управления подобный проект именуется системой ск с разомкнутой обратной связью, поскольку игнорирование результатов восприятия приводит к нарушению обратной связи между агентом и средой.) Все эти предположения означают, что мы имеем дело с простейшими разновидностями среды, и в этом состоит одна из причин, по которой настоящая глава помещена в самом начале данной книги.
В разделе 3.6 дано краткое описание того, что произойдет, если будут исключены допущения о наблюдаемости и детерминированности, а в главах 12 и 17 приведено гораздо более подробное изложение соответствующей темы. Хорошо структурированные задачи и решения Ъ. Задача может быть формально определена с помощью четырех компонентов, описанных ниже. ° ск Начальное состояние, в котором агент приступает к работе. Например, начальное состояние для нашего агента в Румынии может быть описано как пребывание в Араде, 1п (Ахас() . ° Описание возможных действий, доступных агенту.
В наиболее общей формулировке' используется Ъ. функция определения преемника. Если задано конкретное состояние х, то функция Яиссеппок-Рп (х) возвращает множество упорядоченных пар <аоезоп, писссппок>, где каждое действие аоезоп представляет собой одно из допустимых действий в состоянии х, а каждый преемник ацссеппок представляет собой состояние, которое может быть достигнуто из х путем применения этого действия. Например, из состояния ' В альтернативной формулировке нсполыустся множество операторов, которые могут быть применены к некоторому состоянию лая выработки преемников.
Часть П. Решение проблем 114 1п(Апас)) функция определения преемника для данной задачи проезда по Румынии возвратит следующее: (чоо(Я1Ьгп), 1п(51Ып) >, <Со(тгмгеоаса), 1п(тдт1еоага) >, <Со(ке дпс)), 1п(Еегзпд) >) Начальное состояние и функция определения преемника, вместе взятые, неявно задают Ъ. пространство состояний данной задачи — множество всех состояний, достижимых из начального состояния. Пространство состояний образует граф, узлами которого являются состояния, а дугами между узлами — действия. (Карта Румынии, показанная на рис.
3.1, может интерпретироваться как граф пространства состояний, если каждая дорога рассматривается как обозначающая два действия проезда на автомобиле, по одному в каждом направлении.) 'па Путем в пространстве состояний является последовательность состояний, соединенных последовательностью действий. Огаг(еа Агаа (Араа) ))8 а) пе Эферие) района (дагуряхгу) Рис. 3.1. Унрои(синая дорожная карта части Румынии ° 'оа Проверка цели, позволяющая определить, является ли данное конкретное состояние целевым состоянием. Иногда имеется явно заданное множество возможных целевых состояний, и эта проверка сводится просто к определению того, является ли данное состояние одним из них.
Пель рассматриваемого агента в Румынии прелставляет собой одноэлементное множество ( 1п (впс)гапее г) ) . Иногда цель задается в виде абстрактного свойства, а не явно перечисленного множества состояний. Например, в шахматах цель состоит в достижении состояния, назыиаемого "матом", в котором король противника атакован и не может уклониться от удара. ° Функция ',ъ стоимости пути, которая назначает числовое значение стоимости каждому пути. Агент, решающий задачу, выбирает функцию стоимости, кото- Глава 3. Решение проблем посредством поиска 115 рая соответствует его собственным показателям производительности. Для данного агента, пытающегося попасть в Бухарест, важнее всего время, поэтому стоимость пути может измеряться длиной в километрах. В настоящей главе предполагается, что стоимость пути может быть описана как сумма стоимостей отдельных действий, выполняемых вдоль этого пути. Ъ.
Стоимость этапа, связанного с выполнением действия а для перехода из состояния х в состояние у, обозначается как с(зс, а, у) . Стоимости этапов для Румынии показаны на рис. 3.1 в виде дорожных расстояний. Предполагается, что стоимости этапов являются неотрицательными4. Описанные выше элементы определяют задачу и могут быть собраны вместе в единую структуру данных, которая передается в качестве входных данных в алгоритм решения задачи. Решением задачи является путь от начального состояния до целевого состояния.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
