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

Обобщение марковского процесса принятия решений

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

Структура POMDP достаточно общая для моделирования множества реальных последовательных процессов принятия решений. Приложения включают проблемы навигации роботов, обслуживания машин и планирования в условиях неопределенности в целом. Общая структура марковских процессов принятия решений с несовершенной информацией была описана Карлом Йоханом Острёмом в 1965 году ^[1] в случае дискретного пространства состояний, и она была дополнительно изучена в сообществе исследователей операций , где была придумана аббревиатура POMDP. Позднее она была адаптирована для задач искусственного интеллекта и автоматизированного планирования Лесли П. Кэлблингом и Майклом Л. Литтманом . ^[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 O(o\mid s')}$ ${\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 \rightarrow 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)}$

Вера МДП

Марковское состояние убеждения позволяет сформулировать POMDP как марковский процесс принятия решений , где каждое убеждение является состоянием. Результирующее убеждение MDP будет, таким образом, определено в непрерывном пространстве состояний (даже если «исходный» POMDP имеет конечное число состояний: существует бесконечное число состояний убеждения (в ), поскольку существует бесконечное число распределений вероятностей по состояниям (из )). ^[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 часто вычислительно неразрешимы для точного решения. Эта неразрешимость часто обусловлена ​​проклятием размерности или проклятием истории (тот факт, что оптимальная политика может зависеть от всей истории действий и наблюдений). Чтобы решить эти проблемы, специалисты по информатике разработали методы, которые аппроксимируют решения для POMDP. Эти решения обычно пытаются аппроксимировать проблему или решение с ограниченным числом параметров, ^[7] планируют только небольшую часть пространства убеждений онлайн или компактно суммируют историю действий-наблюдений.

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

Онлайн-алгоритмы планирования подходят к большим POMDP, конструируя новую политику для текущего убеждения каждый раз, когда получено новое наблюдение. Такая политика должна учитывать только будущие убеждения, достижимые из текущего убеждения, которое часто является лишь очень небольшой частью полного пространства убеждений. Это семейство включает варианты поиска по дереву Монте-Карло ^[14] и эвристического поиска. ^[15] Подобно MDP, можно конструировать онлайн-алгоритмы, которые находят произвольно близкие к оптимальным политики и не имеют прямой зависимости вычислительной сложности от размера пространств состояний и наблюдений. ^[16]

Другая линия методов приближенного решения для решения POMDPs основана на использовании (подмножества) истории предыдущих наблюдений, действий и вознаграждений вплоть до текущего временного шага в качестве псевдосостояния. Затем можно использовать обычные методы решения MDPs, основанные на этих псевдосостояниях (например, Q-learning ). В идеале псевдосостояния должны содержать самую важную информацию из всей истории (для уменьшения смещения), будучи при этом максимально сжатыми (для уменьшения переобучения). ^[17]

теория ПОМДП

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

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

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

Приложения

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

Одним из примеров является обучающий случай, проблема плачущего ребенка, когда родителю необходимо последовательно решить, кормить ли ребенка, основываясь на наблюдении за тем, плачет ребенок или нет, что является несовершенным представлением фактического состояния голода ребенка. ^{[22] [23]}

Ссылки

1. Åström, KJ (1965). «Оптимальное управление марковскими процессами с неполной информацией о состоянии». Журнал математического анализа и приложений . 10 : 174–205. doi : 10.1016/0022-247X(65)90154-X .
2. Kaelbling, LP, Littman, ML, Cassandra, AR (1998). «Планирование и действие в частично наблюдаемых стохастических областях». Искусственный интеллект . 101 (1–2): 99–134. doi :10.1016/S0004-3702(98)00023-X.{{cite journal}}: CS1 maint: multiple names: authors list (link)
3. Sondik, EJ (1971). Оптимальное управление частично наблюдаемыми марковскими процессами (диссертация). Стэнфордский университет. Архивировано из оригинала 17 октября 2019 г.
4. Smallwood, RD, Sondik, EJ (1973). «Оптимальное управление частично наблюдаемыми марковскими процессами принятия решений на конечном горизонте». Operations Research . 21 (5): 1071–88. doi :10.1287/opre.21.5.1071.{{cite journal}}: CS1 maint: multiple names: authors list (link)
5. Sondik, EJ (1978). «Оптимальное управление частично наблюдаемыми марковскими процессами на бесконечном горизонте: дисконтированная стоимость». Operations Research . 26 (2): 282–304. doi :10.1287/opre.26.2.282.
6. Хансен, Э. (1998). «Решение POMDP путем поиска в пространстве политики». Труды Четырнадцатой международной конференции по неопределенности в искусственном интеллекте (UAI-98) . arXiv : 1301.7380 .
7. Хаускрехт, М. (2000). «Приближения функции ценности для частично наблюдаемых марковских процессов принятия решений». Журнал исследований искусственного интеллекта . 13 : 33–94. arXiv : 1106.0234 . doi : 10.1613/jair.678 .
8. Лавджой, В. (1991). «Вычислительно допустимые границы для частично наблюдаемых марковских процессов принятия решений». Исследование операций . 39 : 162–175. doi :10.1287/opre.39.1.162.
9. Джесси Хои; Аксель фон Бертольди; Паскаль Пупарт; Алекс Михайлидис (2007). «Помощь лицам с деменцией во время мытья рук с использованием частично наблюдаемого марковского процесса принятия решений». Труды Международной конференции по системам компьютерного зрения . doi :10.2390/biecoll-icvs2007-89.
10. Джесси Хоуи; Паскаль Пупарт; Аксель фон Бертольди; Тэмми Крейг; Крейг Бутилье; Алекс Михайлидис. (2010). «Автоматизированная помощь в мытье рук для лиц с деменцией с использованием видео и частично наблюдаемого марковского процесса принятия решений». Компьютерное зрение и понимание изображений . 114 (5): 503–519. CiteSeerX 10.1.1.160.8351 . doi :10.1016/j.cviu.2009.06.008. 
11. Пино, Дж., Гордон, Г., Трун, С. (август 2003 г.). «Итерация значений на основе точек: алгоритм любого времени для POMDP» (PDF) . Международная совместная конференция по искусственному интеллекту (IJCAI). Акапулько, Мексика . стр. 1025–32.{{cite conference}}: CS1 maint: multiple names: authors list (link)
12. Хаускрехт, М. (1997). «Инкрементальные методы вычисления границ в частично наблюдаемых марковских процессах принятия решений». Труды 14-й Национальной конференции по искусственному интеллекту (AAAI). Провиденс, Род-Айленд . С. 734–739. CiteSeerX 10.1.1.85.8303 . 
13. Рой, Николас ; Гордон, Джеффри (2003). "Экспоненциальный семейный PCA для сжатия убеждений в POMDP" (PDF) . Достижения в области нейронных систем обработки информации .
14. Дэвид Сильвер и Джоэл Венесс (2010). Планирование Монте-Карло в больших POMDP . Достижения в нейронных системах обработки информации.
15. Нан Йе, Адхирадж Сомани, Дэвид Хсу и Ви Сан Ли (2017). «DESPOT: Онлайн-планирование POMDP с регуляризацией». Журнал исследований искусственного интеллекта . 58 : 231–266. arXiv : 1609.03250 . doi : 10.1613/jair.5328 .{{cite journal}}: CS1 maint: multiple names: authors list (link)
16. Майкл Х. Лим, Тайлер Дж. Беккер, Майкель Дж. Кочендерфер, Клэр Дж. Томлин и Захари Н. Санберг (2023). «Гарантии оптимальности для аппроксимации убеждений частиц POMDP». Журнал исследований искусственного интеллекта . 77 : 1591–1636. arXiv : 2210.05015 . doi : 10.1613/jair.1.14525 .{{cite journal}}: CS1 maint: multiple names: authors list (link)
17. Франсуа-Лаве, В., Рабюссо, Г., Пино, Ж., Эрнст, Д., Фонтено, Р. (2019). О переобучении и асимптотическом смещении в пакетном обучении с подкреплением с частичной наблюдаемостью. Журнал исследований искусственного интеллекта (JAIR) . Том 65. С. 1–30. arXiv : 1709.07796 .{{cite conference}}: CS1 maint: multiple names: authors list (link)
18. Чаттерджи, Кришненду; Чмелик, Мартин; Траколь, Матье (2016-08-01). «Что разрешимо в частично наблюдаемых марковских процессах принятия решений с ω-регулярными целями». Журнал компьютерных и системных наук . 82 (5): 878–911. doi : 10.1016/j.jcss.2016.02.009 . ISSN  0022-0000.
19. Хаускрехт, М., Фрейзер, Х. (2000). «Планирование лечения ишемической болезни сердца с частично наблюдаемыми марковскими процессами принятия решений». Искусственный интеллект в медицине . 18 (3): 221–244. doi :10.1016/S0933-3657(99)00042-1. PMID  10675716.{{cite journal}}: CS1 maint: multiple names: authors list (link)
20. Chadès, I., McDonald-Madden, E., McCarthy, MA, Wintle, B., Linkie, M., Possingham, HP (16 сентября 2008 г.). «Когда прекращать управление или обследование криптических видов, находящихся под угрозой исчезновения». Proc. Natl. Acad. Sci. USA . 105 (37): 13936–40. Bibcode : 2008PNAS..10513936C. doi : 10.1073/pnas.0805265105 . PMC 2544557. PMID  18779594 . {{cite journal}}: CS1 maint: multiple names: authors list (link)
21. Кочендерфер, Майкель Дж. (2015). «Оптимизированное предотвращение столкновений в воздухе». Принятие решений в условиях неопределенности . Издательство MIT.
22. Кочендерфер, Майкель Дж.; Уилер, Тим А.; Рэй, Кайл Х. (2022). Алгоритмы принятия решений. Кембридж, Массачусетс; Лондон, Англия: MIT Press. стр. 678. ISBN 9780262047012.
23. Мосс, Роберт Дж. (24 сентября 2021 г.). "СМОТРЕТЬ: POMDPs: Принятие решений в условиях неопределенности POMDPs.jl. Проблема плачущего ребенка" (видео) . youtube.com . Язык программирования Julia .

Внешние ссылки

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