Частично наблюдаемый марковский процесс принятия решений

Частично наблюдаемый марковский процесс принятия решения ( POMDP ) представляет собой обобщение решения марковского процесса (MDP). POMDP моделирует процесс принятия решения агентом, в котором предполагается, что динамика системы определяется MDP, но агент не может напрямую наблюдать за базовым состоянием. Вместо этого он должен поддерживать распределение вероятностей по набору возможных состояний на основе набора наблюдений и вероятностей наблюдений, а также лежащего в основе MDP.

Структура POMDP достаточно универсальна, чтобы моделировать множество реальных последовательных процессов принятия решений. Приложения включают проблемы навигации роботов, техническое обслуживание машин и планирование в условиях неопределенности в целом. Общая структура марковских процессов принятия решений с несовершенной информацией была описана Карлом Йоханом Остромом в 1965 году ^[1] в случае дискретного пространства состояний и в дальнейшем изучена в сообществе исследователей операций, где была придумана аббревиатура POMDP. Позднее он был адаптирован для задач искусственного интеллекта и автоматизированного планирования по Лесли P Каелблинг и Майкл Л. Литтмана . ^[2]

Точное решение POMDP дает оптимальное действие для каждого возможного убеждения по состояниям мира. Оптимальное действие максимизирует (или минимизирует) ожидаемое вознаграждение (или стоимость) агента на возможно бесконечном горизонте. Последовательность оптимальных действий известна как оптимальная политика агента для взаимодействия со своим окружением.

Определение [ править ]

Формальное определение [ править ]

POMDP с дискретным временем моделирует отношения между агентом и его средой. Формально POMDP представляет собой набор из 7 элементов , где${\ displaystyle (S, A, T, R, \ Omega, O, \ gamma)}$

• ${\ displaystyle S}$ это набор состояний,
• ${\ displaystyle A}$ это набор действий,
• ${\ displaystyle T}$ - набор условных вероятностей перехода между состояниями,
• ${\ Displaystyle R: S \ times A \ to \ mathbb {R}}$ это функция вознаграждения.
• ${\ displaystyle \ Omega}$ это набор наблюдений,
• ${\displaystyle O}$ - набор условных вероятностей наблюдения, а
• ${\displaystyle \gamma \in [0,1]}$ коэффициент дисконтирования.

В каждый период времени окружающая среда находится в каком-то состоянии . Агент выполняет действие , в результате которого среда с вероятностью переходит в состояние . В то же время агент получает наблюдение, которое с вероятностью зависит от нового состояния окружающей среды , и от только что предпринятого действия . Наконец, агент получает вознаграждение в размере . Затем процесс повторяется. Цель состоит в том, чтобы агент выбирал действия на каждом временном шаге, которые максимизируют его ожидаемое будущее дисконтированное вознаграждение:, где - вознаграждение, заработанное в данный момент . Фактор скидки определяет, насколько немедленное вознаграждение предпочтительнее более отдаленного вознаграждения. Когда${\displaystyle s\in S}$${\displaystyle a\in A}$${\displaystyle s'}$${\displaystyle T(s'\mid s,a)}$${\displaystyle o\in \Omega }$${\displaystyle s'}$${\displaystyle a}$${\displaystyle O(o\mid s',a)}$${\displaystyle r}$${\displaystyle R(s,a)}$${\displaystyle E\left[\sum _{t=0}^{\infty }\gamma ^{t}r_{t}\right]}$${\displaystyle r_{t}}$${\displaystyle t}$${\displaystyle \gamma }$${\displaystyle \gamma =0}$агент заботится только о том, какое действие принесет наибольшую ожидаемую немедленную награду; когда агент заботится о максимальном увеличении ожидаемой суммы будущих вознаграждений.${\displaystyle \gamma =1}$

Обсуждение [ править ]

Поскольку агент не наблюдает напрямую за состоянием окружающей среды, агент должен принимать решения в условиях неопределенности истинного состояния окружающей среды. Однако, взаимодействуя с окружающей средой и получая наблюдения, агент может обновить свое мнение об истинном состоянии, обновив распределение вероятностей текущего состояния. Следствием этого свойства является то, что оптимальное поведение часто может включать в себя действия (сбор информации), которые предпринимаются исключительно потому, что они улучшают оценку агентом текущего состояния, тем самым позволяя ему принимать более обоснованные решения в будущем.

Поучительно сравнить приведенное выше определение с определением марковского процесса принятия решений . MDP не включает набор наблюдений, потому что агент всегда точно знает текущее состояние среды. В качестве альтернативы, MDP можно переформулировать как POMDP, установив набор наблюдений равным набору состояний и определив условные вероятности наблюдения для детерминированного выбора наблюдения, которое соответствует истинному состоянию.

Обновление убеждений [ править ]

После выполнения действия и наблюдения агенту необходимо обновить свое мнение о состоянии, в котором может (или нет) находиться окружающая среда. Поскольку состояние является марковским (по предположению), поддержание веры в состояния требует исключительно знания предыдущих состояние убеждений, предпринятые действия и текущее наблюдение. Обозначена операция . Ниже мы описываем, как рассчитывается это обновление убеждений.${\displaystyle a}$${\displaystyle o}$${\displaystyle b'=\tau (b,a,o)}$

Достигнув , агент с вероятностью наблюдает . Позвольте быть вероятностным распределением по пространству состояний . обозначает вероятность того, что окружающая среда находится в состоянии . Учитывая , то после принятия мер и наблюдения ,${\displaystyle s'}$${\displaystyle o\in \Omega }$${\displaystyle O(o\mid s',a)}$${\displaystyle b}$${\displaystyle S}$${\displaystyle b(s)}$${\displaystyle s}$${\displaystyle b(s)}$${\displaystyle a}$${\displaystyle o}$

${\displaystyle b'(s')=\eta O(o\mid s',a)\sum _{s\in S}T(s'\mid s,a)b(s)}$

где - нормирующая постоянная с .${\displaystyle \eta =1/\Pr(o\mid b,a)}$${\displaystyle \Pr(o\mid b,a)=\sum _{s'\in S}O(o\mid s',a)\sum _{s\in S}T(s'\mid s,a)b(s)}$

Вера MDP [ править ]

Марковское состояние убеждений позволяет сформулировать POMDP как марковский процесс принятия решений, в котором каждое убеждение является состоянием. Таким образом, результирующая MDP убеждения будет определена в непрерывном пространстве состояний (даже если «исходный» POMDP имеет конечное число состояний: есть бесконечные состояния доверия (in ), потому что существует бесконечное количество распределений вероятностей по состояниям (of )). ^[2]${\displaystyle B}$${\displaystyle S}$

Формально убеждение MDP определяется как кортеж, в котором${\displaystyle (B,A,\tau ,r,\gamma )}$

• ${\displaystyle B}$ - это набор состояний убеждений по состояниям POMDP,
• ${\displaystyle A}$ - тот же конечный набор действий, что и для исходного POMDP,
• ${\displaystyle \tau }$ функция перехода в состояние доверия,
• ${\displaystyle r:B\times A\to \mathbb {R} }$ - функция вознаграждения по состояниям убеждений,
• ${\displaystyle \gamma }$- коэффициент дисконтирования, равный исходному POMDP.${\displaystyle \gamma }$

Из них и нужно вывести исходный POMDP. является${\displaystyle \tau }$${\displaystyle r}$${\displaystyle \tau }$

${\displaystyle \tau (b,a,b')=\sum _{o\in \Omega }\Pr(b'|b,a,o)\Pr(o|a,b),}$

где - значение, полученное в предыдущем разделе, и${\displaystyle \Pr(o|a,b)}$

${\displaystyle Pr(b'|b,a,o)={\begin{cases}1&{\text{if the belief update with arguments }}b,a,o{\text{ returns }}b'\\0&{\text{otherwise }}\end{cases}}.}$

Функция вознаграждения MDP убеждений ( ) - это ожидаемое вознаграждение от функции вознаграждения POMDP по распределению состояний убеждений:${\displaystyle r}$

${\displaystyle r(b,a)=\sum _{s\in S}b(s)R(s,a)}$.

Убеждение MDP больше не является частично наблюдаемым, поскольку в любой момент времени агент знает свое убеждение и, в более широком смысле, состояние MDP убеждения.

Политика и функция ценностей [ править ]

В отличие от «исходной» POMDP (где каждое действие доступно только из одного состояния), в соответствующей MDP убеждений все состояния убеждений разрешают все действия, поскольку у вас (почти) всегда есть некоторая вероятность полагать, что вы находитесь в любом (исходном) состоянии. Таким образом, определяет действие для любого убеждения .${\displaystyle \pi }$${\displaystyle a=\pi (b)}$${\displaystyle b}$

Здесь предполагается, что цель состоит в том, чтобы максимизировать ожидаемое общее дисконтированное вознаграждение на бесконечном горизонте. Когда определяется стоимость, целью становится минимизация ожидаемой стоимости.${\displaystyle R}$

Ожидаемое вознаграждение за политику, исходящую из убеждений , определяется как${\displaystyle \pi }$${\displaystyle b_{0}}$

${\displaystyle V^{\pi }(b_{0})=\sum _{t=0}^{\infty }\gamma ^{t}r(b_{t},a_{t})=\sum _{t=0}^{\infty }\gamma ^{t}E{\Bigl [}R(s_{t},a_{t})\mid b_{0},\pi {\Bigr ]}}$

где коэффициент дисконтирования. Оптимальная политика достигается за счет оптимизации долгосрочного вознаграждения.${\displaystyle \gamma <1}$${\displaystyle \pi ^{*}}$

${\displaystyle \pi ^{*}={\underset {\pi }{\mbox{argmax}}}\ V^{\pi }(b_{0})}$

где изначальное убеждение.${\displaystyle b_{0}}$

Оптимальная политика, обозначенная как , дает наивысшее ожидаемое значение вознаграждения для каждого состояния убеждений, компактно представленное функцией оптимального значения . Эта функция цены является решением уравнения оптимальности Беллмана :${\displaystyle \pi ^{*}}$${\displaystyle V^{*}}$

${\displaystyle V^{*}(b)=\max _{a\in A}{\Bigl [}r(b,a)+\gamma \sum _{o\in \Omega }\Pr(o\mid b,a)V^{*}(\tau (b,a,o)){\Bigr ]}}$

Для POMDP с конечным горизонтом функция оптимального значения является кусочно-линейной и выпуклой. ^[3] Его можно представить как конечный набор векторов. В формулировке с бесконечным горизонтом можно произвольно аппроксимировать конечный набор векторов , форма которого остается выпуклой. Итерация значений применяет обновление динамического программирования для постепенного улучшения значения до сходимости к функции оптимального значения и сохраняет ее кусочную линейность и выпуклость. ^[4] Повышая ценность, мы неявно улучшаем политику. Другой метод динамического программирования, называемый итерацией политики, вместо этого явно представляет и улучшает политику. ^{[5] [6]}${\displaystyle V^{*}}$${\displaystyle \epsilon }$

Планирование в POMDP [ править ]

Планирование в POMDP вообще неразрешимо . Однако некоторые параметры были определены как разрешимые (см. Таблицу 2 в ^[7], воспроизведенную ниже). Были рассмотрены разные цели. Цели Büchi определяются автоматами Büchi . Достижимость - это пример состояния Бюхи (например, достижение хорошего состояния, в котором все роботы находятся дома). Объективы coBüchi соответствуют трассам, которые не удовлетворяют заданному условию Büchi (например, не достигают плохого состояния, в котором погиб какой-то робот). Цели паритета определяются через паритетные игры ; они позволяют ставить сложные задачи таким образом, чтобы достичь хорошего состояния каждые 10 временных шагов. Цель может быть достигнута:

• почти наверняка, то есть вероятность достижения цели равна 1;
• положительный, то есть вероятность достижения цели строго больше 0;
• количественный, то есть вероятность достижения цели больше заданного порога.

Мы также рассматриваем случай конечной памяти, в котором агент является конечным автоматом, и общий случай, в котором агент имеет бесконечную память.

Примерные решения POMDP [ править ]

На практике POMDP часто трудно решить с помощью вычислений , поэтому специалисты по информатике разработали методы, приближающие решения для POMDP. ^[8]

Сеточные алгоритмы ^[9] содержат один метод приближенного решения. В этом подходе функция ценности вычисляется для набора точек в пространстве убеждений, а интерполяция используется для определения оптимального действия, которое необходимо предпринять для других обнаруженных состояний убеждений, которые не входят в набор точек сетки. В более поздних работах используются методы выборки, методы обобщения и использование структуры проблемы, а решение POMDP распространилось на большие области с миллионами состояний. ^{[10] [11]} Например, адаптивные сетки и точечные методы выбирают случайные достижимые точки доверия, чтобы ограничить планирование соответствующими областями в пространстве убеждений. ^{[12] [13]} Уменьшение размерности с помощью PCAтакже был исследован. ^[14]

Использует [ редактировать ]

POMDP можно использовать для моделирования многих видов реальных проблем. Известные применения включают использование POMDP при лечении пациентов с ишемической болезнью сердца, ^[15] вспомогательные технологии для людей с деменцией, ^{[10] [11]} сохранение находящихся под угрозой исчезновения и трудных для обнаружения суматранских тигров ^[16] и самолетов. избежание столкновения. ^[17]

Ссылки [ править ]

Внешние ссылки [ править ]

• Страницы POMDP Тони Кассандры с учебником, примерами проблем, смоделированных как POMDP, и программным обеспечением для их решения.
• pomdp: Решатель для частично наблюдаемых марковских процессов принятия решений (POMDP) пакет R, обеспечивающий интерфейс для решателя POMDP Тони Кассандры.
• zmdp , решатель POMDP Трея Смита
• APPL , быстрый точечный решатель POMDP
• SPUDD , решатель MDP с факторизованной структурой (PO), использующий алгебраические диаграммы решений (ADD).
• pyPOMDP , набор инструментов (PO) MDP (симулятор, решатель, обучающийся, читатель файлов) для Python от Оливер Столлманн и Бастиан Мигге
• Конечные контроллеры, использующие функцию Branch-and-Bound для точного решения POMDP для политик ограниченного размера
• POMDPs.jl , интерфейс для определения и решения MDP и POMDP в Julia с различными решателями.