Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 228
Текст из файла (страница 228)
Другими словами, пг решение любой задачи РОМРР в пространстве физических состоянии можно свенпи к решению зада~и М2)Р в соответствующем пространстве доверительных состояний. Этот факт, возможно, станет менее удивительным, если мы вспомним, что доверительное состояние по определению всегда является наблюдаемым для агента. Но необходимо отметить следующее: хотя мы свели задачу РОМРР к задаче МРР, полученная задача МРР имеет непрерывное (а иногда многомерное, с большим количеством размерностей) пространство состояний.
Для решения подобных задач МРР нельзя непосредственно применить ни один из алгоритмов МРР, описанных в разделах !7.2 и !7.3. Но, как оказалось, существует возможность разработать версии алгоритмов итерации по значениям и итерации по стратегиям, которые могут применяться для решения задач МРР с непрерывными состояниями. Основная идея состоит в том, что стратегия и ()з) может быть представлена как множество областей пространства доверительных состояний, каждая из которых связана с конкретным оптимальным действием4.
Функция стоимости связывает с каждой из областей отдельную линейную функцию от.Ь. На каждом этапе итерации по значениям или по стратегиям уточняются границы областей и могут вводиться новые области. Подробное описание соответствующих алгоритмов выходит за рамки данной книги, но мы сообщаем решение для мира 4хЗ без датчиков. Оптимальная стратегия состоит в следующем: (ьеес, пр, пр, дзц)за, пр, пр, кзх т)за, цр, пр, дзд)за, гтр, кзпдс, гр, кзя)зс, цр, 1 Этот стратегия представляет собой последовательность, поскольку рассматриваемая задача в пространстве доверительных состояний является детерминированной — в ней нет наблюдений. Воплощенный в этой стратегии "секрет" состоит в том, что нужно предусмотреть для агента однократное движение деГс для проверки того, что он не находится в квадрате ( й, 1), с тем чтобы в дальнейшем было достаточно безопасно продолжать движения (гр и )(зд)зс для достижения выхода +1.
Агент достигает выхода +1 в 86,6% попыток и добивается этого гораздо быстрее по сравнению со стратегией, приведенной выше в данном разделе, поэтому его ожидаемая полезность повышается до О. 38, что гораздо больше по сравнению с О. 08. 4 Для некоторых задач РОМРР оптимальная стратегия имеет бесконечное количество областей, поэтому простой подход с использованием списка областей ие позволяет добиться успеха, и лля поиска даже приближенного решения нужны более изощренные методы.
836 Часть Ч. Неопределенные знания и рассуждения в условиях неопределенности Для более сложных задач РОМРР с непустыми результатами наблюдений приближенный поиск оптимальных стратегий является очень сложным (фактически такие задачи являются РЗРАСЕ-трудными, т.е. действительно чрезвычайно трудными). Задачи с несколькими десятками состояний часто оказываются неразрешимыми. В следующем разделе описан другой, приближенный метод решения задач РОМРР, основанный на опережающем поиске. 17.5. АГЕНТЫ, ДЕЙСТВУЮЩИЕ НА ОСНОВЕ ТЕОРИИ РЕШЕНИЙ В этом разделе будет описан исчерпывающий подход к проектированию агентов для частично наблюдаемых, стохастических вариантов среды.
Как показано ниже, основные элементы этого проекта должны быть уже знакомы читателю. ° Модели перехода и наблюдения представлены в виде динамических байесовских сетей (см. главу 15). ° Динамическая байесовская сеть дополняется узлами принятия решений и узлами полезности, по аналогии с теми, которые использовались в сетях принятия решений в главе 16. Результирующая модель называется Ъ. динамической сетью принятия решений (Рупатьс Ресвйоп Хе(вог8 — РРХ). ° Для учета данных о каждом новом восприятии и действии и для обновления представления доверительного состояния используется алгоритм фильтрации. ° Решения принимаются путем проектирования в прямом направлении возможных последовательностей действий и выбора наилучших из этих последовательностей.
Основное преимущество использования динамической байесовской сети для представления модели перехода и модели восприятия состоит в том, что такая сеть позволяет применять декомпозицию описания состояния на множество случайных переменных во многом аналогично тому, как в алгоритмах планирования используются логические прелставления для декомпозиции пространства состояний, применяемого в алгоритмах поиска. Поэтому проект агента представляет собой практическую реализацию агента, действующего с учетом полезности, который был кратко описан в главе 2.
Поскольку в этом разделе будут использоваться динамические байесовские сети, вернемся к системе обозначений главы 15, где символом х, обозначается множество переменных состояния во время с, а х„— переменные свидетельства. Таким образом, там, где до сих пор в этой главе использовалось обозначение в, (состояние во время с), теперь будет применяться обозначение х,. Для обозначения действия во время с будет использоваться запись д„поэтому модель перехода т( а, а, в' ) представляет собой не что иное, как р (х„,) х„д,), а модель наблюдения 0( в, о) — то же, что и в (к,) х,) . Для обозначения вознаграждения, полученного во время с, будет применяться запись д,, а для обозначения полезности состояния во время с— запись (),.
При использовании такой системы обозначений динамическая сеть принятия решений принимает вид, подобный показанному на рис. 17.7. Г~ды !7 Пцинн~ие с .он нц~ пе~~книи Глава 17. Принятие сложных решений 839 ванных на исполыовании алгоритмов динамической сети принятия решений, является то, что в них используется прямой поиск, полностью аналогичный тому, который предусмотрен в алгоритмах поиска в пространстве состояний, описанных в части!1. В части 1Ч было показано, что способность рассматривать частично упорядоченные, абстрактные планы с использованием целенаправленного поиска обеспечивает существенное расширение возможностей решения задач, особенно если при этом применяются библиотеки планов.
Кроме того, были предприняты попытки распространить эти методы на вероятностную проблемную область, но до сих пор они оказывались неэффективными. Еще одной связанной с этим проблемой является слишком простой язык динамических сетей принятия решений, который по сути является пропозициональным. Бьшо бы желательно распространить на задачи принятия решений некоторые идеи вероятностных языков первого порядка, описанные в разделе 14.6.
Современные исследования показали, что такое расширение возможно и что оно позволяет получить существенные преимущества, как описано в заметках в конце данной главы. 17.6. ПРИНЯТИЕ РЕШЕНИЙ ПРИ НАЛИЧИИ НЕСКОЛЬКИ)( АГЕНТОВ: ТЕОРИЯ ИГР Данная глава в основном посвящена теме принятия решений в неопределенных вариантах среды.
А как обстоят дела в том случае, если неопределенность связана с наличием других агентов и осуществлением ими решений, которые они принимают? И что будет, если на решения этих агентов, в свою очередь, влияют решения нашего агента? Эти вопросы уже рассматривались в настоящей книге при описании игр в главе 6. Но в этой главе речь в основном шла об играх с полной информацией, в которых игроки делают ходы по очереди: в подобных играх для определения оптимальных ходов может использоваться минимаксный поиск. А в данном разделе рассматриваются некоторые идеи Ж теории игр, которые могут применяться при анализе игр с одновременно выполняемыми ходами. Для упрощения изложения вначале рассмотрим игры, которые продолжаются только в течение одного хода.
На первый взгляд может показаться, что слово "игра" не совсем подходит для обозначения такого упрощения, которое сводится к одному ходу, но в действительности теория игр используется в очень серьезных ситуациях принятия решений, включая ведение дел о банкротстве, организацию аукционов по распределению спектра радиочастот, принятие решений по разработке промышленной продукции и назначению на нее цен, а также национальную оборону. В таких ситуациях речь часто идет о миллиардах долларов и сотнях тысяч человеческих жизней. Теория игр может использоваться по меньшей мере в двух описанных ниже направлениях. 1. Проектирование агента. Теория игр позволяет анализировать решения агента и вычислять ожидаемую полезность для каждого решения (с учетом предположения, что другие агенты действуют оптимальным образом согласно теории игр).
Например, в игре в чет и нечет иа двух пальцах (эту игру на пальцах называют также аогга, от итальянского слова саеогга — группа) два игрока, 0(О~Ы вЂ” нечетный) и к (Ечеп — четный), одновременно показывают один или два пальца.
Допустим, что общее количество показанных пальцев равно Е Если число Г является нечетным, игрок о получает Е долларов от игрока д', 840 Часть Ч, Неопределенные знания и рассуждения в условиях неопределенности а если число Š— четное, игрок Е получает Е долларов от игрока О. Теория игр позволяет определить наилучшую стратегию в игре против рационально действующего игрока и ожидаемый выигрыш для каждого игроказ.
2. Проектирование механизма. Если в среде присутствует много агентов, то может существовать возможность так определить правила действий в этой среде (т.е. правила игры, в которую должны играть агенты), чтобы обгцее благосостояние всех агентов максимизировалось, если каждый агент принимает обоснованное теорией игр решение, максимизирующее его собственную полезность. Например, теория игр позволяет проектировать такие протоколы для коллекции маршрутизаторов трафика )п1егпег, чтобы каждый маршрутизатор стремился действовать в направлении максимизации глобальной пропускной способности.
Проектирование механизма может также использоваться для создания интеллектуальных мультиагентпых систем, которые решают сложные задачи в распределенной форме без необходимости для каждого агента знать о том, какая задача решается в целом. Любая игра в теории игр определяется с помощью описанных ниже компонентов. ° 7ц Игроки, или агенты, которые должны принимать решения. Наибольшее внимание в исследованиях уделялось играм с двумя игроками, хотя достаточно часто рассматриваются также игры с и игроками, где п>2. В этой главе имена игроков записываются с прописной буквы, например л24 се и ео)э или О и е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
