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

Классические марковские процессы принятия решений (MDP) исходят из фундаментального допущения: агент всегда обладает полной и абсолютно достоверной информацией о текущем состоянии внешней среды. Однако в реальных задачах исследования операций — от медицинской диагностики до навигации беспилотных автомобилей и робототехники — датчики всегда зашумлены, а информация критически неполна. Агент видит лишь косвенные признаки, которые могут соответствовать сразу нескольким физическим состояниям. Для математического моделирования таких систем в условиях неопределенности был разработан аппарат Частично наблюдаемых марковских процессов (Partially Observable Markov Decision Processes, POMDP), который объединяет теорию управления с байесовским статистическим выводом.

Архитектура POMDP добавляет к стандартной марковской модели (состояния, действия, переходы и вознаграждения) два новых элемента: конечное множество возможных наблюдений и матрицу вероятностей эмиссий. Матрица эмиссий (Observation Model) описывает условную вероятность получения конкретного наблюдения при условии, что система находится в определенном скрытом состоянии и было совершено определенное действие. Поскольку агент не знает своего истинного состояния, он вынужден оперировать так называемым состоянием веры (Belief State). Состояние веры — это непрерывное распределение вероятностей по всем возможным скрытым состояниям системы. Таким образом, дискретная задача превращается в задачу непрерывного управления, где агенту необходимо обновлять свои вероятностные гипотезы на каждом шаге времени.

Обновление состояния веры происходит строго по формуле Томаса Байеса. Получив новое наблюдение из окружающей среды, агент пересчитывает свой вектор вероятностей, умножая априорную вероятность перехода на вероятность сделанного наблюдения и нормируя результат константой. Гениальность математического аппарата POMDP заключается в том, что задача управления в условиях неполной информации математически точно (экзактно) сводится к классическому (полностью наблюдаемому) MDP, но не в дискретном пространстве физических состояний, а в непрерывном гиперпространстве состояний веры (Belief Space). В этом гиперпространстве симплекс вероятностей выступает новым полем для поиска оптимальной стратегии (политики), максимизирующей ожидаемую ценность Беллмана.

Вычислительная сложность POMDP колоссальна. Если обычный MDP решается за полиномиальное время (P-class), то точное решение POMDP относится к классу PSPACE-полных задач (или даже неразрешимых для бесконечного горизонта). Функция ценности (Value Function) для POMDP является кусочно-линейной и выпуклой (Piecewise Linear and Convex, PWLC) функцией на симплексе вероятностей. Алгоритмы точного решения (такие как алгоритм Сонди или инкрементальное отсечение) пытаются построить эту функцию путем генерации набора гиперплоскостей (альфа-векторов). Каждая гиперплоскость представляет условную ценность определенной стратегии. Однако количество этих векторов растет экспоненциально с каждым шагом планирования, быстро истощая оперативную память компьютеров.

Для преодоления проклятия размерности исследователи операций разработали мощные эвристические алгоритмы аппроксимации. Наиболее успешным подходом стала Итерация ценности на основе точек (Point-Based Value Iteration, PBVI) и алгоритм SARSOP. Вместо того чтобы вычислять альфа-векторы для всего бесконечного непрерывного симплекс-пространства, эти алгоритмы выбирают конечный набор репрезентативных точек (наиболее вероятных состояний веры, достижимых из начальной точки) и обновляют гиперплоскости только в их окрестностях. Это позволило применять POMDP в реальных промышленных системах: от управления радарами противовоздушной обороны, где нужно отличить ложную цель от ракеты по зашумленному сигналу, до создания медицинских чат-ботов, которые шаг за шагом задают уточняющие вопросы, минимизируя энтропию диагноза пациента.

Оценить