Разработка быстрых численных реле для высокоразмерных задач оптимального управления

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

Проклятие размерности

Проклятие размерности, термин, введенный Ричардом Беллманом в 1950-х годах, относится к экспоненциальному увеличению объема, связанному с добавлением дополнительных измерений в математическое пространство. В контексте оптимального управления это означает, что количество образцов, необходимых для покрытия государственного пространства, растет экспоненциально с измерением. Даже с мощными компьютерами невозможно хранить плотную сетку для 10-мерной задачи — считать сетку со 100 точками на измерение приводит к 10010 = 1020 точкам, намного превышающим любую доступную память.

Это проклятие не просто практическое неудобство; оно фундаментально ограничивает применимость классического динамического программирования. Для его преодоления исследователи разработали методы, которые используют структуру (например, приближения низкого ранга, сепарабельность, редкость) или отменяют точность для масштабируемости (например, выборка Монте-Карло, модель предиктивного контроля). Задача состоит в том, чтобы поддерживать строгие гарантии оптимальности или стабильности при резком снижении вычислительной сложности.

Основные задачи в развитии численного растворителя

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

Вычислительная сложность

Основным препятствием является явная вычислительная нагрузка. Даже если функция значений может быть представлена компактно, оценка оператора Bellman или решение уравнения HJB требует интеграции по пространствам состояния и управления, что может быть дорогостоящим. Например, многие алгоритмы полагаются на передние задние промахи или градиентный спуск во времени, каждый из которых требует множественных оценок динамики и функций стоимости. В высоких измерениях сами эти оценки могут стать узкими местами, если динамика сложна или моделирование дорого.

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

Численность и точность

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

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

Масштабируемость для приложений в реальном времени

Многие высокоразмерные проблемы оптимального управления возникают в контекстах, где решения должны приниматься в миллисекундах. Например, квадротор, перемещающийся по загроможденной среде, должен пересчитывать свою траекторию по мере появления новых препятствий. Традиционные решатели не могут соответствовать этим временным ограничениям. Следовательно, разработка быстрых решателей часто включает в себя автономные вычисления (например, обучение политике нейронной сети) и онлайн-исполнение (например, предварительная оценка политики). Это разделение проблем является центральным для успеха современных моделей предиктивного управления (MPC) и подходов к обучению подкреплению.

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

Стратегии разработки быстрых растворителей

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

Методы снижения размерности

Если система демонстрирует низкомерную структуру, то эффективная размерность может быть намного ниже номинальной размерности состояния. Снижение размерности идентифицирует и использует эту структуру.

Правильное ортогональное разложение

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

Декомпозиции тензора

Тензорные разложения обобщают матричные факторизации с массивами более высокого порядка. Функция значения в оптимальном управлении может быть представлена в виде тензора низкого ранга, резко сокращающего хранение и вычисления. каноническое полиадическое (CP) разложение и Разложение Такера являются общим выбором. В высокоразмерных уравнениях HJB тензорные решатели показали перспективность для задач с размером до 10-20 измерений. Алгоритмы, такие как чередующиеся наименьшие квадраты (ALS), могут эффективно вычислять разложение. работа Колды и Бадера остается основополагающей ссылкой для тензорных методов.

Методы Sparse Grid

Спарзовые сетки, введенные Сергеем Смоляком, предлагают способ разорвать проклятие размерности для гладких функций. Вместо полной тензорной сетки продукта с разреженными сетками используется тщательный подбор точек на основе иерархических функций. Для функций с ограниченными смешанными производными число точек растет только полиномиально с размерностью, а не экспоненциально. Для решения уравнений HJB для задач с размерами до 10-15 применены методы с разреженной сеткой для задач с точностью до доли точек сетки. Сочетание разреженных сеток с адаптивностью еще больше повышает эффективность.

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

Машинное обучение и нейронные сети

Быстрый прогресс в глубоком обучении открыл новые возможности для оптимального управления. Нейронные сети могут аппроксимировать функцию значений или политику управления непосредственно из данных, минуя необходимость представлений на основе сетки. Наиболее заметным подходом является использование глубоких нейронных сетей для решения уравнений HJB с помощью неконтролируемого обучения — так называемого «метода глубокого Галеркина» или «физически информированных нейронных сетей» (PINNs). В этих методах остаток уравнения HJB минимизируется по точкам коллокации, что позволяет сети изучать функцию значений в высоких измерениях без сетки.

Другое семейство алгоритмов происходит от обучения подкреплению, где критики (функции ценности) и акторы (политики) представлены нейронными сетями. Методы, такие как Deep Deterministic Policy Gradient (DDPG) и Soft Actor-Critic (SAC), могут обрабатывать непрерывные пространства состояний и действий с сотнями измерений. Однако эти методы могут потребовать больших объемов данных и тщательной настройки гиперпараметров. Теоретический анализ приближений нейронных сетей для оптимального управления является активной областью; см., например, , этот документ NeurIPS о приближении мощности нейронных сетей для уравнений HJB .

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

Параллельные и распределенные вычисления

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

Например, итерация значений с разреженными сетками может быть параллелизирована путем назначения различных точек сетки различным процессорам. Аналогично, в методах на основе нейронных сетей, мини-пакетное обучение естественным образом использует параллелизм GPU. Более продвинутые методы, такие как асинхронные параллельные акторно-критические алгоритмы, продемонстрировали значительные ускорения для задач управления высокой размерностью. Ключ заключается в разработке алгоритмов, которые поддерживают свойства конвергенции при параллелизме, поскольку наивная параллелизация может вводить устаревшие градиенты или блокировку.

Последние достижения и новые технологии

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

Интеграция глубинного обучения с численными методами

Вместо того чтобы рассматривать глубокое обучение как самостоятельный подход, исследователи объединяют его с традиционными численными методами. Например, метод «Deep BSDE» использует формулу обратного стохастического дифференциального уравнения для решения параболических ПДЭ высокой размерности, включая уравнения HJB. Этот метод использует нейронные сети для представления градиента функции ценности и обучает их с помощью выборки Монте-Карло. Он достиг впечатляющих результатов для задач до 100 измерений, таких как оптимальные инвестиции в финансы.

Другой гибридный подход — «Многоуровневая итерация Пикарда», использующая приближение Монте-Карло интегрального представления уравнения HJB. Этот метод имеет теоретические гарантии сходимости даже в очень высоких измерениях, хотя его практическая эффективность зависит от конкретной структуры задачи.Объединение таких методов с ускорением нейронной сети — активное направление исследований.

Гибридные модели и подходы, основанные на данных

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

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

Будущие направления и открытые вызовы

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

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

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

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