Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 223
Текст из файла (страница 223)
6) Вычислите ожидаемую чистую прибыль от покупки автомобиля с„если не проводится проверка. в) Проверки можно описать с помощью оценки вероятности того, пройдет ли автомобиль или не пройдет данную конкретную проверку, позволяющую определить, находится ли автомобиль в хорошем или плохом состоянии. Имеется следующая информация: Р(раяя(с1, Е1) )с'(с~) ) = 0.8 Р(раяя(с1, Е1) ~ И (с1) ) = О. 35 Примените теорему Байеса для вычисления вероятности успешного прохождения (или не прохождения) автомобилем проверки и следовательно, вероятности того, что он находится в хорошем (или плохом) состоянии, с учетом каждого возможного результата проверки. 814 Часть Ч.
Неопределенные знания и рассуждения в условиях неопределенности г) Рассчитайте оптимальные решения при условии прохождения или не прохождения проверки, а также их ожидаемые полезности. д) Рассчитайте стоимость информации о проверке и разработайте оптимальный условный план для покупателя.
16.!2.Докажите, что стоимость информации является неотрицательной и независимой от последовательности восприятий, как утверждалось в разделе 16.6. Объясните, как может случиться, что после получения информации будет принято худшее решение, чем было бы до ее получения. !6.13. ~Й Модифицируйте и дополните программы байесовской сети, приведенные в репозитарии кода, чтобы обеспечить создание и оценку сетей принятия решений, а также вычисление стоимости информации. Ответы к упр.
16. 3: ° первый ряд вопросов: 3 000000, 1 600 000, 1541, 41000000, 4768, 221, 649 000 000, 295 000 000, 132, 25 546; ° второй ряд вопросов: 1917, 155 000 000, 4 500 000, 11 000 000, 120 000, 1 100 000, 1 636, 19 340, 1 595, 41 710. В данной главе рассматриваются методы принятия решении о том, что следует делать в настоящее время, при условии, что в дальнейшем может быть принято другое решение. В этой главе описано, какие расчеты связаны с принятием решений. В главе 16 речь шла о задачах принятия единоразовых нлн эпизодических решений, в которых полезность результата каждого действия была вполне известна, а в настоящей главе рассматриваются Ж задачи последовательного принятия решений, в которых полезность действий агента зависит от последовательности решений.
Задачи последовательного принятия решений, в которых рассматриваются полезности, степени неопределенности и результаты восприятия, являются обобщением задач поиска и планирования, описанных в частях !1 и !Ъ'. В разделе 17,! описано, как должны быть определены задачи последовательного принятия решений, а в разделах 17.2 и 17.3 показано, как их следует решать, чтобы выработать оптимальные правила поведения, в которых уравновешиваются риски и вознаграждения, связанные с осуществлением действий в неопределенной среде. В разделе 17.4 эти илеи распространяются на случай частично наблюдаемых вариантов среды, а в разделе 17.5 разрабатывается полный проект для агентов, действующих на основе теории принятия решений в частично наблюдаемых вариантах среды; в этом проекте объединяются динамические байесовские сети, описанные в главе 15, и сети принятия решений, описанные в главе 16.
Во второй части данной главы рассматриваются варианты среды с многочисленными агентами. В таких вариантах среды понятие оптимального поведения становится гораздо более сложным из-за взаимодействия агентов. В разделе 17.6 представлены основные идеи теории игр, включая ту идею, что рациональным агентам может потребоваться вести себя случайным образом. В разделе 17.7 показано, как следует проектировать мультиагентные системы для того, чтобы несколько агентов могли достичь общей цели. 817 Глава 17.
Принятие сложных решений О. 8'=О. 32768. Существует также небольшой шанс случайно достичь цели, обойдя барьер с другой стороны с вероятностью 0. 1'хО. 8, поэтому суммарная вероятность достижения цели равна О. 3277 8 (см. также упр. 17.1). Спецификацию вероятностей результатов каждого действия в каждом возможном состоянии принято называть ок моделью перехода (или просто "моделью", если не может возникнуть путаница).
Для обозначения вероятности достижения состояния э ', если в состоянии л было выполнено действие а, будет применяться запись т( в, а, в ' ) . Предполагается, что эти переходы являются марковскими в том смысле, какой указан в главе 15, т,е. что вероятность достижения состояния э ' из л зависит только от э, а не от истории пребывания в предыдуших состояниях. На данный момент запись т(л, а, в ' ) может рассматриваться как большая трехмерная таблица, содержащая вероятности. В дальнейшем, в разделе 17.5, будет показано, что модель перехода может быть представлена как динамическая байесовская сеть, точно так же, как и в главе 15.
В завершение этого определения среды задачи необходимо сформулировать функцию полезности для агента. Поскольку эта задача принятия решений является последовательной, функция полезности должна зависеть от послеловательности состояний (от истории пребывания в среде), а не от отдельного состояния. Ниже в этом разделе будет приведено описание того, как такие функции полезности могут быть определены в целбм, а на данный момент просто примем предположение, что в каждом состоянии л агент получает 'гж вознаграждение )((э), которое может быть положительным или отрицательным, но должно быть ограниченным.
В данном конкретном примере вознаграждение равно -О. 04 во всех состояниях, кроме конечных (с которыми связаны вознаграждения +1 и -1). Полезность, связанная с историей пребывания в среде (на данный момент), рассматривается как сумма полученных вознаграждений. Например, если агент достиг состояния ь1 после !О шагов, суммарная полезность его действий будет равна О. б. Отрицательное вознаграждение -О. 04 побуждает агента быстрее достичь квадрата (4, 3), поэтому данная среда представляет собой стохастическое обобщение вариантов среды, которые рассматривались в задачах поиска в главе 3.
Еще один способ описать эту игровую ситуацию состоит в том, что агенту "не нравится" находиться в этой среде, поэтому он стремится выйти из игры как можно быстрее. Такая спецификация задачи последовательного принятия решений для полностью наблюдаемой среды с марковской моделью перехода и дополнительными вознаграждениями называется спецификацией оь марковского процесса принятия решений, или сокращенно МРР (Магйоч Е)ес!з)оп Ргосезз).
Любая задача М)3Р определяется тремя перечисленными ниже компонентами. ° Начальное состояние — 8е. ° Модель перехода — т( в, а, э ' ) . ° Функция вознаграждения' — д ( л) . ' В некоторых определениях задач МРР допускается, чтобы вознагражление зависело также от лействия и результата, поэтому функция вознаграждения принимает вид а (в, а, в ' ) . Такой подход позволяет упростить описание некоторых вариантов среды, но не приводит к какому-либо фундаментальному изменению самой задачи. 818 Часть Ч.
Неопределенные знания и рассуждения в условиях неопределенности Следующий вопрос состоит в том, как должно выглядеть решение этой задачи. Выше в данной главе было показано, что какая-либо фиксированная последовательность действий не может служить решением этой задачи, поскольку в конечном итоге после ее выполнения агент может оказаться в состоянии, отличном от целевого. Поэтому в решении должно быть указано, что следует делать агенту в любом состоянии, которого он может достичь.
Решение такого рода — это так называемая ж стратегия. Для обозначения стратегии обычно принято использовать и; а я ( э)— это действие, рекомендованное в соответствии со стратегией я лля состояния э. Если агент имеет полное описание стратегии, то всегда знает, что делать дальше, независимо от результата любого действия. Каждый раз, когда осуществляется данная конкретная стратегия, начиная с начального состояния, стохастический характер среды приводит к формированию лругой истории пребывания в среде. Поэтому качество определения стратегии измеряется по ожидаемой полезности возможных историй пребывания в среде, создаваемых с помощью этой стратегии.
',ъ. Оптимальной стратегией называется такая стратегия, которая позволяет достичь максимальной ожидаемой полезности. Для обозначения оптимальной стратегии принято использовать запись я*. Если агенту указана стратегия л*, он принимает решение, что делать, проверяя свои текущие результаты восприятия, которые сообщают ему, что он находится в текущем состоянии э, а затем выполняя действие я* ( э) .
В любой стратегии функция агента представлена явно, поэтому стратегия является описанием простого рефлексного агента, сформированным с учетом информации, которая используется агентом, действующим на основе полезности. Оптимальная стратегия для мира, приведенного на рис.
17.1, показана на рис. 17.2, а. Обратите внимание на то, что стоимость выполнения одного шага довольно мала по сравнению со штрафом, который связан со случайным попаданием в квалрат (4, 2), поэтому оптимальная стратегия для состояния (3, 1) является предельно осторожной. Этот стратегия рекомендует, что нужно совершить дальний обход препятствия, а не пытаться пройти по короткому пути и тем самым подвергнуться риску попасть в квадрат (4, 2 ) . Равновесие между риском и вознаграждением изменяется в зависимости от значения функции л(э) для нетерминальных состояний.
На рис. 17.2, бпоказаны оптимальные стратегии для четырех различных диапазонов изменения значения д(э) . Если л(э) <-1. 6284, жизнь настолько мучительна, что агент направляется прямо к ближайшему выходу, даже если стоимость этого выхода равна -1. Если -0.4278<8(э)<-0.0850, жизнь ловольно дискомфортна; агент выбирает кратчайший маршрут к состоянию +1 и стремится избежать риска случайного попадания в состояние -1. В частности, агент выбирает короткий путь из квадрата (3, 1) .
А если жизнь не так уж неприятна (-О. 0221<Я(э) <О), оптимальная стратегия состоит в том, чтобы избегать вообще какого-либо риска. В квадратах (4, 1) и (3, 2) агент направляется буквально прочь от состояния -1, чтобы случайно не попасть туда ни при каких обстоятсльствах, даже несмотря на то, что из-за этого ему приходится несколько раз удариться головой о стену.
Наконец, если л ( э) >О, то жизнь агента становится весьма приятной и он избегает обоих выходов. При условии, что используются действия, показанные в квадратах (4, 1), (3, 2) и (3, 3), любая стратегия является оптимальной и агент получает бесконечно боль- 819 Глава 17. Принятие сложных решений шое суммарное вознаграждение, поскольку он никогда не попадает в терминальное состояние. Как это ни удивительно, но оказывается, что существуют шесть других оптимальных стратегий для различных диапазонов значений )7)э); в упр. 17 7 предлагается найти эти стратегии. -0,4270 < й(з) <-0,0850 Я(г) < — 1,6204 1 2 3 4 й1Ц >0 -0,0221 < й(д < 0 а) б) )асс. 7 7 2.
Примеры оптимальных стритегий: оптимальная стратегия для стохастической среды со значениями Я)з) = -О. 04 е нетерминальных состояниях (а); оптимальные стратегии для четырех различных диапизоное значений В 7а ) (бд Тщательное уравновешивание риска и вознаграждения является характерной особенностью задач МГ)Р, которая не возникает в летермннированных задачах поиска; более того, такое уравновешивание характерно для многих реальных задач принятия решений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
