Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 227
Текст из файла (страница 227)
Для п состояний имеется п линейных уравнений с п неизвестными, которые Глава 17. Принятие сложных решений 83! могут быть решены точно за время о(п') с помощью стандартных методов линейной алгебры. Для небольших пространств состояний оценка стратегии с использованием точных методов решения часто является наиболее эффективным подходом, а для больших пространств состояний затраты времени 0(п') могут оказаться чрезмерно большими.
К счастью, точная оценка стратегии не требуется. Вместо этого можно выполнить некоторое количество упрощенных этапов итерации по значениям (они являются упрощенными, поскольку стратегия зафиксирована) для получения достаточно хорошей аппроксимации полезности. Упрощенное обновление Беллмана для этого процесса определяется таким соотношением: и определяемая в нем операция подстановки повторяется )с раз для получения следующей оценки полезности. Результирующий алгоритм называется ',з. модифипироваииой итерацией по стратегиям.
Он часто оказывается намного более эффективным, чем стандартная итерация по стратегиям или итерация по значениям. Алгоритмы, описанные до сих пор в данной главе, требуют одновременного обновления полезности или стратегии для всех состояний. Как оказалось, применение такой организации работы не является строго необходимым. В действительности в каждой итерации можно выбирать любое подмножество состояний и применять к этому подмножеству либо тот, либо другой вид обновления (усовершенствование стратегии или упрощенную итерацию по значениям). Такой наиболее общий алгоритм называется Ж асинхронной итерацией по стратегиям. При соблюдении определенных условий выбора исходной стратегии и функции полезности гарантируется сходимость асинхронной итерации по стратегиям к определенной оптимальной стратегии. А то, что мы вправе выбирать для работы с ними любые состояния, означает, что могут быть разработаны гораздо более эффективные эвристические алгоритмы, например, алгоритмы, которые сосредоточиваются на обновлении значений состояний, которые с наибольшей вероятностью будут постигнуты при осуществлении качественной стратегии.
Такой подход имеет гораздо больше смысла в реальной жизни — если человек не намеревается попасть на прибрежную полосу, спрыгнув с высокой скалы, то для него нет смысла заниматься точной оценкой стоимости связанных с этим результирующих состояний. 17.4. МАРКОВСКИЕ ПРОЦЕССЪ| ПРИНЯТИЯ РЕШЕНИЙ В ЧАСТИЧНО НАБЛЮДАЕМЫХ ВАРИАНТАХ СРЕДЫ В описании марковских процессов принятия решений, приведенном в разделе 17.1, предполагалось, что среда является полностью наблюдаемой.
При использовании этого предположения агент всегда знает, в каком состоянии он находится. Это предположение, в сочетании с предположением о марковости модели перехода, означает, что оптимальная стратегия зависит только от текущего состояния. А если среда является только частично наблюдаемой, то вполне очевидно, что ситуация становится горазло менее ясной. Агент не всегда точно знает, в каком состоянии находится, поэтому не 833 Глава 17. Принятие сложных решений результатов наблюдения о в состоянии' в. Например, рассматриваемый в данном случае агент без датчиков имеет только одно возможное наблюдение (пустое наблюдение), и такое наблюдение возникает с вероятностью 1 в любом состоянии.
В главах 3 и 12 рассматривались задачи планирования в недетерминированных и частично наблюдаемых вариантах среды и было определено доверительное состояние (множество фактических состояний, в которых может находиться агент) как ключевая концепция для описания и вычисления решений. В задачах РОМРР это понятие требует определенного уточнения. Теперь доверительным состоянием Ь становится распределение вероятностей по всем возможным состояниям.
Например, начальное доверительное состояние в ситуации, показанной на рис. ! 7.6, а, может быть записано как 111111111 †, †, †, †, †, †, †, †, †,о,о>. 9'9'9'9'9'9'9'9'9' Мы будем обозначать через Ь( в) вероятность, присвоенную фактическому состоянию а доверительным состоянием Ь. Агент может вычислить свое текущее доверительное состояние как распределение условных вероятностей по фактическим состояниям, если дана последовательность происшедших до сих пор наблюдений и действий.
Такая задача по сути сводится к задаче фильтрации (см. главу 15). Основное рекурсивное уравнение фильтрации (см. уравнение 15.3) показывает, как вычислить новое доверительное состояние из предыдущего доверительного состояния и нового наблюдения. Для решения задач РОМ()Р необходимо также учитывать определенное действие и использовать немного лругую систему обозначений, но результат остается по сути тем же самым. Если предыдущим доверительным состоянием было Ь(в), а агент выполнил действие а и получил результаты наблюдения о, то новое доверительное состояние определяется следующим соотношением: Ь'(в ) = й 0(в',о) ) Т(в,а,в') Ь(в) (17.11) где а — нормализуюшая константа, прн использовании которой сумма вероятностей доверительных состояний становится равной 1.
Это уравнение можно сокращенно записать как Ь ' = Рог нагс1 ( Ь, а, о ) . Основная идея, необходимая для понимания сути задач РОМРР, состоит в следуюгцем: с(у оптимальное действие зависит талька ат текущего доверительного состояния агента. Это означает, что оптимальную стратегию можно описать, отобразив стратегию я* (Ь) с доверительных состояний на действия.
Она не зависит от фактического состояния, в котором находится агент. Это — очень благоприятная особенность, поскольку агент не знает своего фактического состояния; все, что он знает, — это лишь его доверительное состояние. Поэтому цикл принятия решений агентом РОМ(3Р состоит в следующем. 1. С учетом текущего доверительного состояния Ь выполнить действие а=я*(Ь). з Модель наблюдения по суси идентична модели восприятия для временных процессов, как было описано в главе 15. Как и функция вознаграждения для задач М(ЗР, модель наблюдения также может зависеть от действия и результирующего состояния, ио связанное с этим изменение ис является фундаментальным.
834 Часть Ч. Неопределенные знания и рассуждения в условиях неопределенности 3. Получить результаты наблюдения о. 3. Установить текушее доверительное состояние равным Рох иахс) (Ь, а, 0) и повторить ту же процедуру. Теперь мы можем рассматривать задачи РОМРР как требуюшие поиска в пространстве доверительных состояний, во многом аналогично тем методам, которые применялись для решения задач в отсутствие латчиков и задач в условиях непредвиденных ситуаций, описанных в главе 3.
Основное различие состоит в том, что пространство доверительных состояний РОМ РР является непрерывным, поскольку доверительное состояние РОМЕ)Р— это распределение вероятностей. Например, доверительное состояние для мира 4х3 представляет собой точку в 11-мерном непрерывном пространстве. Любое действие изменяет не только физическое состояние, но и доверительное состояние, поэтому оценивается согласно информации, полученной агентом в качестве результата. Таким образом, задачи РОМОР должны включать стоимость информации в качестве одного из компонентов задачи принятия решений (см, раздел 16.6). Рассмотрим более внимательно результаты действий.
В частности, рассчитаем вероятность того, что агент, находящийся в доверительном состоянии Ь, достигнет доверительного состояния Ь' после выполнения действия а. Итак, если известно действие и последующее наблюдение, то уравнение 17.11 должно обеспечить получение детерминированного обновления доверительного состояния, иными словами, Ь' =Рогыахс)(Ь, а, 0). Безусловно, результаты последуюшего наблюдения еше не известны, поэтому агент может перейти в одно из нескольких возможных доверительных состояний Ь', в зависимости от того наблюдения, которое последует за данным действием.
Вероятность получения результатов наблюдения о, при условии, что действие а было выполнено в доверительном состоянии Ь, определяется путем суммирования по всем фактическим состояниям я ', которых может достичь агент: Р( о(а, Ь) = ~ Р( о) а, я ', Ь) Р(я ' )а, и) 0(я ',о] Р(я ' (а, Ь) ~~> 0(я',о) ~ Т(я,а,я') Ь(я) Обозначим вероятность достижения состояния Ь' из Ь, если дано действие а, как т ( Ь, а, Ь ' ) . В таком случае справедливо следующее соотношение: т(ь, а,ь') = Р(ь' (а,ь) = ~~) Р(ь')о,а, ь) Р(о) а, ь) о Р(Ь' ) о, а, Ь) ) 0(я', о) ,) Т(я, а, я' ) Ь(я) (17.12) я' где Р(Ь' ~ 0, а, Ь) равно 1, если Ь'=Рот яагс((Ь,а, о), и Π— в противном случае.
835 Глава 17. Принятие сложных решений Уравнение 17.12 можно рассматривать как определение модели перехода для пространства доверительных состояний. Мы можем также определить функцию вознаграждения для доверительных состояний (т.е. ожидаемое вознаграждение, относящееся к фактическим состояниям, в которых может находиться агент) следующим образом: р(Ы =,) )з(в)д(в) Итак, создается впечатление, что т()з,а,)з') и р()з) совместно определяют наблюдаемую задачу МРР в пространстве доверительных состояний. Кроме того, можно показать, что оптимальная стратегия для этой задачи МРР, и* (Ы, является также оптимальной стратегией для оригинальной задачи РОМРР.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
