Введение
Обобщение процесса принятия решений Маркова
A partially observable Markov decision process (POMDP) is a generalization of a Markov decision process (MDP). A POMDP models an agent decision process in which it is assumed that the system dynamics are determined by an MDP, but the agent cannot directly observe the underlying state. Instead, it must maintain a sensor model (the probability distribution of different observations given the underlying state) and the underlying MDP. Unlike the policy function in MDP which maps the underlying states to the actions, POMDP's policy is a mapping from the history of observations (or belief states) to the actions. The POMDP framework is general enough to model a variety of real world sequential decision processes. Applications include robot navigation problems, machine maintenance, and planning under uncertainty in general. The general framework of Markov decision processes with imperfect information was described by Karl Johan Åström in 1965 in the case of a discrete state space, and it was further studied in the operations research community where the acronym POMDP was coined. It was later adapted for problems in artificial intelligence and automated planning by Leslie P. Kaelbling and Michael L. Littman. An exact solution to a POMDP yields the optimal action for each possible belief over the world states. The optimal action maximizes the expected reward (or minimizes the cost) of the agent over a possibly infinite horizon. The sequence of optimal actions is known as the optimal policy of the agent for interacting with its environment.
Частично наблюдаемый процесс принятия решений Маркова (POMDP) является обобщением процесса принятия решений Маркова (MDP). POMDP моделирует процесс принятия решений агентом, в котором предполагается, что динамика системы определяется MDP, но агент не может непосредственно наблюдать истинное состояние. Вместо этого агент должен поддерживать сенсорную модель (вероятностное распределение различных наблюдений, учитывая истинное состояние) и базовый MDP. В отличие от функции политики в MDP, которая сопоставляет истинные состояния с действиями, политика POMDP – это сопоставление истории наблюдений (или состояний убеждений) с действиями. Фреймворк POMDP достаточно универсален для моделирования широкого спектра последовательных процессов принятия решений в реальном мире. Области применения включают задачи навигации роботов, техническое обслуживание оборудования и планирование в условиях неопределенности в целом. Общая структура процессов принятия решений Маркова с неполной информацией была описана Карлом Йоханом Астромом в 1965 году для дискретного пространства состояний и впоследствии была более подробно изучена в сообществе исследователей операций, где и был введен акроним POMDP. Позже Лесли П. Каэлблинг и Майкл Л. Литтман адаптировали его для решения задач в области искусственного интеллекта и автоматизированного планирования. Точное решение POMDP определяет оптимальное действие для каждого возможного состояния убеждения относительно состояний мира. Оптимальное действие максимизирует ожидаемую награду (или минимизирует стоимость) агента на, возможно, бесконечном горизонте. Последовательность оптимальных действий известна как оптимальная политика агента для взаимодействия с окружающей средой.
A partially observable Markov decision process (POMDP) is a generalization of a Markov decision process (MDP). A POMDP models an agent decision process in which it is assumed that the system dynamics are determined by an MDP, but the agent cannot directly observe the underlying state. Instead, it must maintain a sensor model (the probability distribution of different observations given the underlying state) and the underlying MDP. Unlike the policy function in MDP which maps the underlying states to the actions, POMDP's policy is a mapping from the history of observations (or belief states) to the actions. The POMDP framework is general enough to model a variety of real world sequential decision processes. Applications include robot navigation problems, machine maintenance, and planning under uncertainty in general. The general framework of Markov decision processes with imperfect information was described by Karl Johan Åström in 1965 in the case of a discrete state space, and it was further studied in the operations research community where the acronym POMDP was coined. It was later adapted for problems in artificial intelligence and automated planning by Leslie P. Kaelbling and Michael L. Littman. An exact solution to a POMDP yields the optimal action for each possible belief over the world states. The optimal action maximizes the expected reward (or minimizes the cost) of the agent over a possibly infinite horizon. The sequence of optimal actions is known as the optimal policy of the agent for interacting with its environment.
Обсуждение
Поскольку агент не наблюдает состояние среды напрямую, ему приходится принимать решения в условиях неопределенности относительно истинного состояния среды. Однако, взаимодействуя со средой и получая наблюдения, агент может уточнять свои представления об истинном состоянии, обновляя распределение вероятностей текущего состояния. Следствием этого является то, что оптимальное поведение часто включает в себя действия (сбора информации), предпринимаемые исключительно для улучшения оценки текущего состояния, что позволяет агенту принимать более обоснованные решения в будущем. Полезно сравнить данное определение с определением марковского процесса принятия решений. В марковском процессе принятия решений отсутствует набор наблюдений, поскольку агент всегда точно знает текущее состояние среды. Альтернативно, марковский процесс принятия решений можно переформулировать как POMDP, приравняв набор наблюдений к набору состояний и определив условные вероятности наблюдений таким образом, чтобы они детерминированно выбирали наблюдение, соответствующее истинному состоянию.
Обновление убеждений
После совершения действия и получения наблюдения, агенту необходимо обновить свое представление о возможном (или невозможном) состоянии окружающей среды. Поскольку состояние является марковским (по предположению), поддержание представления о состояниях требует только знания предыдущего представления о состоянии, совершенного действия и текущего наблюдения. Эта операция обозначается Ниже мы опишем, как вычисляется это обновление представления. После достижения состояния , агент наблюдает с вероятностью Пусть будет вероятностным распределением по пространству состояний, где обозначает вероятность нахождения среды в состоянии . При заданном , после совершения действия и получения наблюдения ,
где – нормализующая константа, такая что .
Вера МДП
Марковское состояние убеждений позволяет сформулировать ПОМДП как процесс принятия решений Маркова, где каждое убеждение является состоянием. Полученный MDP убеждений, таким образом, будет определен на непрерывном пространстве состояний (даже если "исходный" POMDP имеет конечное число состояний: существует бесконечное количество состояний убеждений (в), поскольку существует бесконечное число распределений вероятностей по состояниям (из)). Он может быть представлен в виде конечного набора векторов. В формулировке с бесконечным горизонтом конечный набор векторов может приближать его произвольно точно, сохраняя при этом выпуклую форму. Итерация значений применяет обновление динамического программирования для постепенного улучшения значения до сходимости к оптимальной функции значения, сохраняя её кусочно-линейность и выпуклость. Улучшение значения влечет за собой улучшение политики. Другая техника динамического программирования, называемая итерацией политики, явно представляет и улучшает политику.
Приблизительные решения POMDP
На практике, частично наблюдаемые марковские процессы принятия решений (ПОМДП) часто вычислительно сложно решить точно. Эта сложность часто обусловлена проклятием размерности или проклятием истории (тем фактом, что оптимальная политика может зависеть от всей истории действий и наблюдений). Для решения этих проблем, специалисты в области компьютерных наук разработали методы, которые аппроксимируют решения для ПОМДП. Эти решения обычно стремятся аппроксимировать задачу или решение с помощью ограниченного числа параметров, планировать только на небольшой части пространства убеждений в режиме реального времени, или компактно суммировать историю действий и наблюдений. Алгоритмы, основанные на сетках, представляют собой один из методов приближенного решения. В этом подходе, функция ценности вычисляется для набора точек в пространстве убеждений, а интерполяция используется для определения оптимального действия для других состояний убеждений, которые встречаются и не входят в набор точек сетки. Более поздние работы используют методы выборки, методы обобщения и использование структуры задачи, а также расширили возможности решения ПОМДП для больших областей с миллионами состояний. Например, адаптивные сетки и методы, основанные на точках, выбирают случайные достижимые точки убеждений, чтобы ограничить планирование соответствующими областями в пространстве убеждений. Также было исследовано снижение размерности с использованием метода главных компонент (ПКА). Алгоритмы онлайн-планирования решают большие ПОМДП, строя новую политику для текущего убеждения каждый раз, когда поступает новое наблюдение. Такая политика должна учитывать только будущие убеждения, достижимые из текущего убеждения, которые часто являются лишь небольшой частью всего пространства убеждений. Это семейство включает варианты поиска по деревьям Монте-Карло и эвристического поиска. Подобно марковским процессам принятия решений (МПП), можно построить онлайн-алгоритмы, которые находят произвольно близкие к оптимальным политики и не имеют прямой зависимости вычислительной сложности от размера пространства состояний и наблюдений. Другое направление методов приближенного решения для ПОМДП основано на использовании (подмножества) истории предыдущих наблюдений, действий и вознаграждений до текущего момента времени в качестве псевдосостояния. Затем можно использовать обычные методы решения МПП, основанные на этих псевдосостояниях (например, Q-обучение). В идеале, псевдосостояния должны содержать наиболее важную информацию из всей истории (для уменьшения смещения), будучи при этом максимально сжатыми (для уменьшения переобучения).