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

Для базового ознакомления достаточно посетить разделы Level 0 и MPC+DL, для желающих посмотреть под капот есть разделы Level 1 и Прикладное.

Level 0: Для самых маленьких

Давайте начнём с простого анализа тайтла и поймём, какую задачу мы решаем.

Предположим, что у нас есть какая-то система, которой мы хотим управлять. Этой системой может быть что угодно: от машин, роботов, до, в теории, государства. Под управлением понимают генерацию последовательности управляющих сигналов (они же controls, actions, управления и экшены), которые приводят к решению какой-либо поставленной задачи. В случае машины или робота этими сигналами могут быть, например, скорости или ускорения, которые привезут нас в целевую точку; в случае государства — придумайте сами (ребята, записываем домашнее задание).

Слово Model в MPC предполагает наличие (математической) модели нашей системы. Эта модель позволяет просчитать поведение системы в будущем — отсюда и слово predictive.

Хорошо, предсказывать мы умеем, как найти-то управления? За это отвечает компонент, которого хоть и нет в тайтле, несмотря на ключевую роль — это функция стоимости (cost function, cost, кост). Стоимость говорит нам о том, насколько состояние системы (и в общем случае управляющий сигнал), плохи в контексте поставленной задачи. Тут RL-щики должны напрячься и словить флешбеки от понятия награды (reward): в общем случае cost и reward — понятия довольно взаимозаменяемые, просто reward говорит нам, насколько состояние, наоборот, хорошее (но заранее скажу, что между MPC и RL идейно очень большая разница, хоть и с первого взгляда может показаться обратное).

Миленький примерчик

Давно нашёл эту картинку на сайте одной лабы из Колорадо (кста, челики вроде прикольный рисерч делают, мне зашло). В общем, у зайца-гонщика из команды MPC поставлена задача: достичь финиша как можно быстрее. У него в голове есть какая-то интуитивная модель динамики мотоцикла: он понимает, как будет вести себя мотоцикл в зависимости от того, как жать на педали и поворачивать руль (ого, получается в этом случае модель — это биологическая нейронная сеть!!!). Эта модель позволяет ему примерно спроецировать будущую траекторию на трек — что и изображено в облачке.

Далее, посмотрим на жёлтую и зелёную траекторию. Жёлтая траектория в целом,решает поставленную задачу, но не является оптимальной, т.к. слишком длинная. Поэтому и её стоимость выше. Зелёная же решает задачу и является более короткой, поэтому её стоимость ниже, можно сказать, минимальная из всех возможных — она является оптимальным решением в контексте поставленной задачи.

Также одно из важных преимуществ MPC, не упомянутых выше — возможность введения ограничений, т. е. определения множества состояний, в которых система не должна находиться ни при каких условиях. Посмотрим на красные траектории у зайчика. Они нарушают ограничения — ими в нашем случае являются границы трека — а значит, никак не могут быть решениями поставленной задачи, даже если бы они приводили меньшей стоимости. Иначе зайчика в лучшем случае ждёт дисквалификация, а в худшем — GGWP 😥.

С Level 0 всё, дальше пойдёт уже полноценный рассказ для взрослых с математикой. Кому хочется ещё интуитивных объяснений — могу порекомендовать серию видосов от доброй тётеньки из Matlab.

Level 1: Для подростков с матешей

Теперь давайте рассмотрим уже более строгую математическую постановку задачи.

В дискретном случае нашу задачу можно записать в следующем общем виде (для непрерывного случая, по классике, сумма заменяется на интеграл, а модель динамики определяет производную состояния):

Решив данную оптимизационную задачу, мы получим последовательность управлений на наш горизонт. На практике, обычно на вход системе подают только первое управление из последовательности, а на следующем шаге решают задачу заново. Зачем так, почему бы тогда не решать задачу только для одного шага? Ну, тут у нас, можно сказать, классическая проблема жадных алгоритмов vs. динамическое программирование. Решая задачу на горизонт, мы можем получить более оптимальное решение для будущего. Конечно, в идеале тогда горизонт должен быть бесконечным, что невозможно на практике, поэтому ограничиваемся H шагами. А перепланирование после первого шага нужно для быстрой реакции на изменения в наблюдаемой среде (например, на резкие манёвры машин и людей). Хотя никто не запрещает использовать все управления или часть из них.

Для лучшего понимания всех ингредиентов давайте сразу рассмотрим простую прикладную задачу. Предположим, что у нас есть робот, представляемый кругом, для которого можно задавать вектор скорости в произвольном направлении. Наша цель — переместить робота из точки A в точку B, минуя круговые препятствия.

Интуитивно, имеем слеудующую обстановку:

• Мы хотим минимизировать расстояние между роботом и целью;
• При этом робот не должен столкнуться с препятствиями (это и есть наши ограничения) — для наших простых репрезентаций это означает, что расстояние до препятствия должно превышать сумму радиусов препятствия и робота;
• Движение робота в нашем случае можно описать простой кинематикой.

Исходя из этого, можно предложить следующую постановку задачи для MPC:

Здесь мы предполагаем, что наша система — дискретная, и шаг дискретизации равен \Delta t. Состояние робота — декартовы координаты в 2D. В стоимости на этапе, равно как и в финальной, мы напрямую минимизируем расстояние между роботом и целью. На практике в стоимость на этапе также добавляют штрафы на большие величины управлений, поскольку в реальных системах это может привести к нестабильности. Поскольку ограничения у нас заданы в виде неравенств со знаком >=, то и функция записывается по принципу расстояния минус суммарный радиус.

Для реальных систем, конечно, постановка задачи может быть намного сложнее: динамику могут задавать в виде системы диффуров, а ограничений может быть в разы больше.

Ок, с постановкой задачи мы разобрались, а как её решать-то?

Ха-ха. Вопрос не простой и заслуживает отдельного поста, если наша организация, конечно, более глубоко разберётся в сабже. Но если дать хоть какой-то ответ, то можно выделить следующие методы. В первую очередь, это выпуклая оптимизация, или лучше даже сказать, выпуклое программирование (линейное программирование сюда же, вполне его юзают для MPC, если получается нормально линеаризовать проблему). Даже у легенды Stephen P. Boyd Rice (кто не слышал, чекайте его книгу Convex Optimization и пакеты CVX/CVXPY) есть много работ про решение задачи MPC. Из методов, которые точно юзаются для MPC, хочется отметить Quadratically Constrained Quadratic Program (QCQP) и Second-Order Cone Programming (SOCP) — их точно можно найти в разных солверах и прикладных публикациях.

В общем случае для нелинейных задач применимы любые методы из нелинейного программирования. Выпуклое программирование, в общем-то, является частным случаем. Из всего этого разнообразия, особенно в контексте невыпуклых задач, важно отметить Interior-point Methods, в частности, солвер IPOPT, и Sequential Quadratic Programming (SQP). Из исследователей в области нелинейного программирования, помимо упомянутого выше Бойда, хочется выделить господина Dimitri Bertsekas (RL-щикам, знакомым с понятием approximate dynamic programming, он может быть уже знаком) — у него есть целая книжка по нелинейному программированию.

В целом, конечно, ограничений на методы нет, можно выбрать абсолютно любой метод оптимизации, который сможете прикрутить сюда. Далее вопрос только в качестве и скорости работы.

Honorable mentions: DDP/iLQR и MPPI

Из альтернативных методов решения задачи MPC важно упомянуть две группы: DDP/iLQG и MPPI.

Differential Dynamic Programming (DDP, не путать с Distributed Data Parallel!) и очень близкий к нему Iterative Linear-Quadratic Gaussian (iLQG) основаны на использовании принципа оптимальности Беллмана и аппроксимации value-функции (да, здесь понятие value такое же, как в RL-е, только замените reward на cost) второго порядка. Очень хороший обзор с выводами можно найти в этой статье. Такие трюк позволяют нам получить решение на нашей проблемы в явном виде. Главный недостаток здесь — это отсутствие поддержки ограничений. Расширения DDP, поддерживающие ограничения, конечно, есть, но в их случаях уже редко можно получить решения в явном виде, насколько нам известно. Тем не менее, методы довольно широко используются, например, в свое время их любили использовать для походки робо-собак и робо-гуманоидов.

А вот про Model Predictive Path Integral (MPPI) у нас точно будет отдельный пост. Во-первых, нам он видится как один из самых перспективных алгоритмов будущего, во-вторых, это просто очень красивая математическая идея. MPPI относится к sampling-based подходам — он позволяет решить задачу оптимизации вообще без градиентов, только за счёт хитрых манипуляций над рандомными сэмплами управлений!!!! И нет, это даже не простой перебор рандомных сэмплов!!! Главное преимущество здесь в том, что теперь у нас нет ограничений на форму динамики и стоимости (хоть фидбек из онлайн API чатгпт используй как стоимость), а также эта штука, по крайней мере, в исходном виде, позволяет эффективно использовать многопоточные вычисления. Один из самых более-менее доступных выводов MPPI можно найти в этой статье, но опять же, ждём отдельного поста на эту тему.

Прикладное: фреймворки и пакеты

Захотелось потрогать MPC? Чел харош! А слабо потрогать траву? Тогда вот подборка библиотек и фреймворков, с которых можно начать. По факту, их, конечно, больше, но здесь мы укажем только то, с чем работали или имеем хоть какое-то представление.

do-mpc

Языки: Python

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

Nota bene: do-mpc, и многие другие либы используют фреймворк Casadi -- это такой инструмент для автоматического дифференцирования. По сути, задавая динамики и стоимости в do-mpc, вы создаёте выражения на Casadi, по которым потом явно находятся выражения для градиентов по принципу графа вычислений. Это очень похоже на то, как в своё время работал старый товарищ TensorFlow, с, имхо, главной вытекающей проблемой: фиг получится увидеть какие-либо промежуточные значения для выражений (в отличие от PyTorch). Также Casadi использует column-major репрезентацию для матриц, в отличие от row-major в NumPy, к которому, скорее всего, привыкло большинство читателей. Так что поначалу работать с этой штукой будет больно, но такова жизнь. Мы вообще пришли к юнит-тестам для Casadi-выражений, втупую сравнивая их конечные результаты с более понятными аналогами на NumPy.

ForcesPro

Языки: C++, Python

Коммерческий фреймворк от выходцев из ETH Zurich, хотя студенческие лицензии выдают без проблем, даже в наше непростое время. Позиционируется как решение с фокусом на продакшн, хотя и в рисерческих статях его можно встретить довольно часто. Разработчики утверждают, что их солверы самые быстрые на рынке. Документация есть, но, скажем так, порог вхождения в этой штуке очень высокий. Так что новичкам я бы не рекомендовал ForcesPro. А вот если нужно добиться максимальной производительности или в целом хочется потыкать индустриальные решения — то велком.

ACADO

Языки: C++, Matlab

Довольно старый оптимизационный тулкит, из всего рассмотренного, наверное, лежит ближе к ForcesPro, но с открытым кодом. Не могу особо много что-то про него сказать, видел, что его юзали в статьях от топ лаб из ETH Zurich, но по сайту и документации не понятно, жив он вообще или нет. Но решили на всякий случай добавить его в наш список.

acado

Языки: C, Python, Matlab, Octave

Наследник ACADO, но, в отличие от него, жив и развивается. Есть документация, примеров в репозитории много. Сами с ним не работали, но слышали о нем хорошие отзывы от коллег. В списке кандидатов на потыкать, наверное, на втором месте после do-mpc.

cvxpy

Языки: Python

Известная среди оптимизаторов библиотека от лабы упомянутого выше С. Бойда. Это инструмент для выпуклой оптимизации общего назначения, поэтому к MPC-фреймворкам она относится постольку-поскольку, однако, видел не одно её применение к MPC и управлению в целом, например, здесь.

MPC в эпоху Deep Learning

Прошаренные читатели могли подумать, что динамика в MPC очень похожа на... те самые World Models от Шмидхубера! Ну или правильнее сказать, что world models похожи на динамику.

Действительно, обучаемые модели динамики, да и обучаемые стоимости — идея не новая. Даже в статье про MPPI, о которой я упоминал выше, и, по факту, довольно старой, контрибушн заключался в использовании нейросети в качестве модели динамики. В наши дни эти идеи обрели новую жизнь, в первую очередь благодаря появлению разных foundation-моделей и больших world models (из недавнего, взять те же GAIA-1 и Nvidia Cosmos, хоть и их практическое использование из-за большого размера и ограниченных condition-ов на управления остается под вопросом).

За идею MPC с обучаемой моделью динамики активно топит Ян Лекун. Из его недавних работ по сабжу стоит отметить DINO-WM и Navigation World Models. Из менее известных исследователей в этой области хотелось бы отметить господина Tim Salzmann, в частности, его проект l4casadi, посвящённый женитьбе PyTorch-моделей и солверов на основе упомянутого выше Casadi. Также очень важные работы, на которые стоит обратить внимание — TD-MPC и TD-MPC2 от челиков из UC San Diego. Они предложили подход на основе model-based planning в в стиле MPC для решения онлайн и офлайн RL-ных задач и достигли в них очень крутых метрик.

А мы что?

Мы пришли к MPC, решая задачу социальной навигации робота с учётом неопределённости. Роботу нужно доехать из точки A в точку B в среде, где ходят люди, чьё движение мы можем предсказать и получить оценку неопределённости этого предсказания в виде матрицы ковариации. Рисёрч посвящён дизайну MPC, позволяющему эффективно учесть эту неопределённость. С подробностями можно ознакомиться в нашей публикации. В общем, что-то сделали, что-то получилось.

Сейчас нас сильно интересует свадьба learnable-моделей и sampling-based подходов для MPC, в частности, свзяь диффузионных моделей и MPPI. Работа идёт, так что stay tuned!

А на этом всё. Подписывайтесь, ставьте лайки, пишите комментарии, делайте рисёрч, и до новых встреч!