МАРКОВСКИЕ ПРОЦЕССЫ ПРИНЯТИЯ РЕШЕНИЙ В ЧАСТИЧНО НАБЛЮДАЕМЫХ ВАРИАНТАХ СРЕДЫ
Чтобы найти подход к решению задач POMDP, необходимо вначале определить их должным образом. Любая задача POMDP состоит из таких же компонентов, как и задача MDP (модель перехода T(s, a, s1 ) и функция вознаграждения R{s)), но имеет также модель наблюдения 0(s, о), которая задает вероятность получения
В качестве примера еще раз рассмотрим мир с размерами 4x3 (см. рис. 17.1), но на этот раз предположим, что агент вообще не имеет датчиков, а также не представляет себе, где находится. Точнее, допустим, что начальным состоянием агента с равной вероятностью может быть любое из девяти нетерминальных состояний (рис. 17.6, а). Очевидно, что если бы агент знал, что он находится в квадрате (3,3), то отправился бы направо, выполнив движение Right, а если бы знал, что он — в квадрате (1,1), то направился бы вверх с помощью движения Up, но поскольку агент может находиться в любом квадрате, то что ему делать? Один из возможных ответов состоит в том, что агенту необходимо вначале действовать так, чтобы уменьшить неопределенность своего положения и только после этого отправиться к выходу +1. Например, если агент выполнит движение Left пять раз, то с наибольшей вероятностью окажется у левой стены (см. рис. 17.6, б), а если он после этого пять раз выполнит движение Up, то, вполне вероятно, будет находиться вверху, возможно даже, в левом верхнем углу (см. рис. 17.6, в). Наконец, если он пять раз выполнит движение Right, то получит хорошие шансы (около 77,5%) достижения выхода + 1 (см. рис. 17.6, г). Продолжение после этого движения вправо повышает его шансы до 81,8%. Поэтому такая стратегия является удивительно безопасной, но при ее использовании агенту потребуется довольно много времени для достижения желаемого выхода, а ожидаемая полезность будет составлять лишь около 0.08. Оптимальная стратегия, который вскоре будет описана, позволяет достичь намного лучших результатов.
результатов наблюдения о в состоянии3 s. Например, рассматриваемый в данном случае агент без датчиков имеет только одно возможное наблюдение (пустое наблюдение), и такое наблюдение возникает с вероятностью 1 в любом состоянии.
В главах 3 и 12 рассматривались задачи планирования в недетерминированных и частично наблюдаемых вариантах среды и было определено доверительное состояние (множество фактических состояний, в которых может находиться агент) как ключевая концепция для описания и вычисления решений. В задачах POMDP это понятие требует определенного уточнения. Теперь доверительным состоянием Ъ становится распределение вероятностей по всем возможным состояниям. Например, начальное доверительное состояние в ситуации, показанной на рис. 17.6, а, может быть записано как
<9'9'9'9'9'9'9,9'9,0'0>-
Мы будем обозначать через b(s) вероятность, присвоенную фактическому состоянию s доверительным состоянием Ь. Агент может вычислить свое текущее доверительное состояние как распределение условных вероятностей по фактическим состояниям, если дана последовательность происшедших до сих пор наблюдений и действий. Такая задача по сути сводится к задаче фильтрации (см. главу 15). Основное рекурсивное уравнение фильтрации (см. уравнение 15.3) показывает, как вычислить новое доверительное состояние из предыдущего доверительного состояния и нового наблюдения. Для решения задач POMDP необходимо также учитывать определенное действие и использовать немного другую систему обозначений, но результат остается по сути тем же самым. Если предыдущим доверительным состоянием было b(s), а агент выполнил действие а и получил результаты наблюдения о, то новое доверительное состояние определяется следующим соотношением:
где а — нормализующая константа, при использовании которой сумма вероятностей доверительных состояний становится равной 1. Это уравнение можно сокращенно записать какЬ' =Forward(b, а, о).
Основная идея, необходимая для понимания сути задач POMDP, состоит в следующем: оптимальное действие зависит только от текущего доверительного состояния агента. Это означает, что оптимальную стратегию можно описать, отобразив стратегию я* (Ь) с доверительных состояний на действия. Она не зависит от фактического состояния, в котором находится агент. Это — очень благоприятная особенность, поскольку агент не знает своего фактического состояния; все, что он знает, — это лишь его доверительное состояние. Поэтому цикл принятия решений агентом POMDP состоит в следующем.
1. С учетом текущего доверительного состояния Ь выполнить действие
2. Получить результаты наблюдения о.
3. Установить текущее доверительное состояние равным Forward (Ь, а, о) и повторить ту же процедуру.
Теперь мы можем рассматривать задачи POMDP как требующие поиска в пространстве доверительных состояний, во многом аналогично тем методам, которые применялись для решения задач в отсутствие датчиков и задач в условиях непредвиденных ситуаций, описанных в главе 3. Основное различие состоит в том, что пространство доверительных состояний POMDP является непрерывным, поскольку доверительное состояние POMDP — это распределение вероятностей. Например, доверительное состояние для мира 4x3 представляет собой точку в 11-мерном непрерывном пространстве. Любое действие изменяет не только физическое состояние, но и доверительное состояние, поэтому оценивается согласно информации, полученной агентом в качестве результата. Таким образом, задачи POMDP должны включать стоимость информации в качестве одного из компонентов задачи принятия решений (см. раздел 16.6).
Рассмотрим более внимательно результаты действий. В частности, рассчитаем вероятность того, что агент, находящийся в доверительном состоянии Ь, достигнет доверительного состояния Ь' после выполнения действия а. Итак, если известно действие и последующее наблюдение, то уравнение 17.11 должно обеспечить получение детерминированного обновления доверительного состояния, иными словами, Ь' Forward(Ь, а, о). Безусловно, результаты последующего наблюдения еще не известны, поэтому агент может перейти в одно из нескольких возможных доверительных состояний Ь', в зависимости от того наблюдения, которое последует за данным действием. Вероятность получения результатов наблюдения о, при условии, что действие а было выполнено в доверительном состоянии Ь, определяется путем суммирования по всем фактическим состояниям s1, которых может достичь агент:
Уравнение 17.12 можно рассматривать как определение модели перехода для пространства доверительных состояний. Мы можем также определить функцию вознаграждения для доверительных состояний (т.е. ожидаемое вознаграждение, относящееся к фактическим состояниям, в которых может находиться агент) следующим образом:
Итак, создается впечатление, что т(Ь, а, Ь' ) и р (Ь) совместно определяют наблюдаемую задачу MDP в пространстве доверительных состояний. Кроме того, можно показать, что оптимальная стратегия для этой задачи MDP, п* (Ь), является также оптимальной стратегией для оригинальной задачи POMDP. Другими словами,
решение любой задачи POMDP в пространстве физических состояний можно свести к решению задачи MDP в соответствующем пространстве доверительных состояний. Этот факт, возможно, станет менее удивительным, если мы вспомним, что доверительное состояние по определению всегда является наблюдаемым для агента.
Но необходимо отметить следующее: хотя мы свели задачу POMDP к задаче MDP, полученная задача MDP имеет непрерывное (а иногда многомерное, с большим количеством размерностей) пространство состояний. Для решения подобных задач MDP нельзя непосредственно применить ни один из алгоритмов MDP, описанных в разделах 17.2 и 17.3. Но, как оказалось, существует возможность разработать версии алгоритмов итерации по значениям и итерации по стратегиям, которые могут применяться для решения задач MDP с непрерывными состояниями. Основная идея состоит в том, что стратегия п (Ь) может быть представлена как множество областей пространства доверительных состояний, каждая из которых связана с конкретным оптимальным действием4. Функция стоимости связывает с каждой из областей отдельную линейную функцию от Ь. На каждом этапе итерации по значениям или по стратегиям уточняются границы областей и могут вводиться новые области.
Подробное описание соответствующих алгоритмов выходит за рамки данной книги, но мы сообщаем решение для мира 4x3 без датчиков. Оптимальная стратегия состоит в следующем:
[Left, Up, Up,Right, Up, Up,Right, Up, Up,Right, Up,Right, Up,Right, Up, ...]
Этот стратегия представляет собой последовательность, поскольку рассматриваемая задача в пространстве доверительных состояний является детерминированной — в ней нет наблюдений. Воплощенный в этой стратегии "секрет" состоит в том, что нужно предусмотреть для агента однократное движение Left для проверки того, что он не находится в квадрате (4,1), с тем чтобы в дальнейшем было достаточно безопасно продолжать движения Up и Right для достижения выхода +1. Агент достигает выхода +1 в 86,6% попыток и добивается этого гораздо быстрее по сравнению со стратегией, приведенной выше в данном разделе, поэтому его ожидаемая полезность повышается до 0 . 38, что гораздо больше по сравнению с 0 . 08.
Для более сложных задач POMDP с непустыми результатами наблюдений приближенный поиск оптимальных стратегий является очень сложным (фактически такие задачи являются PSPACE-трудными, т.е. действительно чрезвычайно трудными). Задачи с несколькими десятками состояний часто оказываются неразрешимыми. В следующем разделе описан другой, приближенный метод решения задач POMDP, основанный на опережающем поиске.
В этом разделе будет описан исчерпывающий подход к проектированию агентов для частично наблюдаемых, стохастических вариантов среды. Как показано ниже, основные элементы этого проекта должны быть уже знакомы читателю.
• Модели перехода и наблюдения представлены в виде динамических байесовских сетей (см. главу 15).
• Динамическая байесовская сеть дополняется узлами принятия решений и узлами полезности, по аналогии с теми, которые использовались в сетях принятия решений в главе 16. Результирующая модель называется динамической сетью принятия решений (Dynamic Decision Network — DDN).
• Для учета данных о каждом новом восприятии и действии и для обновления представления доверительного состояния используется алгоритм фильтрации.
• Решения принимаются путем проектирования в прямом направлении возможных последовательностей действий и выбора наилучших из этих последовательностей.
Основное преимущество использования динамической байесовской сети для представления модели перехода и модели восприятия состоит в том, что такая сеть позволяет применять декомпозицию описания состояния на множество случайных переменных во многом аналогично тому, как в алгоритмах планирования используются логические представления для декомпозиции пространства состояний, применяемого в алгоритмах поиска. Поэтому проект агента представляет собой практическую реализацию агента, действующего с учетом полезности, который был кратко описан в главе 2.
Поскольку в этом разделе будут использоваться динамические байесовские сети, вернемся к системе обозначений главы 15, где символом xt обозначается множество переменных состояния во время t, a Et — переменные свидетельства. Таким образом, там, где до сих пор в этой главе использовалось обозначение st (состояние во время t), теперь будет применяться обозначение xt. Для обозначения действия во время t будет использоваться запись At, поэтому модель перехода T(s, a, s1 ) представляет собой не что иное, как Р (xt+11xt, At), а модель наблюдения 0(s, о) — то же, что и Р (Et |xt). Для обозначения вознаграждения, полученного во время t, будет применяться запись Rt, а для обозначения полезности состояния во время t — запись ut. При использовании такой системы обозначений динамическая сеть принятия решений принимает вид, подобный показанному на рис. 17.7.