Нейро-Динамическое Программирование Автономных Агентов Как обучаемые агенты решают задачи оптимизации Сергей Терехов Лаборатория Искусственных Нейронных Сетей ALIFE г. Троицк, Московской обл.

План Введение: Cистемы с динамически-оптимальным управлением Классическая задача оптимизации с ограничениями Управляемая оптимальная динамика Программное управление Прогностическое управление на основе нейросетевой модели системы Нейро-динамическое программирование Марковский процесс принятия решения Уравнение Беллмана Игровая стратегия и оценка позиции Нейросетевая аппроксимация функции ценности Алгоритм SARSA и Q-обучение Примеры прикладных разработок Динамическое управление портфелем финансовых активов Динамическое резервирование каналов сети сотовой связи.

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

Многоэтапные задачи - 1 Менеджмент проекта. Real options. Управление оптовыми закупками в торговых сетях с учетом будущих потребностей. Управление динамикой инвестиционного портфеля. Управляющие воздействия состоят в покупке и продаже некоторых активов портфеля с целью достижения выбранного критерия эффективности.

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

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

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

Найти, такое, что где - множество допустимых управлений, определяемое ограничениями Классическая задача оптимизации с ограничениями Постановка задачи:

Линейная Оптимизация Леонид Витальевич КанторовичЭкономический расчет наилучшего использования ресурсов (1939) George Dantzig – симплекс-метод (1963)

Динамическая Оптимизация Функция ценности меняется во времени Функция ценности доступна не для всех значений аргументов Функция ценности зависит от принятых решений Цель – найти оптимальную последовательность решений

Найти, такое, что где - множество допустимых управлений, определяемое ограничениями на всей траектории Программное управление Постановка задачи:

Прогностическое управление на основе (нейросетевой) модели динамики системы прошлое будущее целевая траектория прогнозируемая траектория динамики состояния управляемая траектория управление в замкнутом контуре Управление в открытом контуре горизонт управления горизонт прогноза t Model Predictive Control (MPC)

Логика алгоритмов MPC - 1 Нейронная сеть обучается на исторических данных и данных, полученных в результате испытаний управляемой системы в условиях программного управления. После обучения, нейронная сеть может использоваться для предсказания динамики системы при заданном законе управления на N последовательных шагов по времени (горизонт прогнозирования). На каждом шаге управления новое состояние системы измеряется в петле обратной связи.

Логика алгоритмов MPC - 2 Управляющие воздействия на последующих M шагах рассматриваются как неизвестные переменные. Набор этих переменных вместе с нейросетевой моделью отклика системы синтезируют теоретическую траекторию изменения состояния системы. Оптимальные значения управляющих переменных далее определяются итерационно путем минимизацией стоимости прогнозируемой траектории. Только первое управляющее действие (из N последовательных значений управления) фактически применяется к управляемой системе. Далее алгоритм тогда повторяется для следующего шага.

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

Методологические проблемы MPC Необходимость наличия адекватной математической модели управляемого объекта. В некоторых важных приложениях математической модели системы может и не быть, либо ее использование требует неприемлемых вычислительных ресурсов. Поиск многошагового оптимального управления путем прямой оптимизации возможен лишь в задачах с небольшим числом переменных и временных шагов. (Р. Беллман: проклятие размерности) В общем случае объект управления демонстрирует вероятностное поведение, которое может быть вызвано как неполнотой описания сложной системы, так и объективными характером процессов.

Марковский Процесс Принятия Оптимального Решения Изменение состояния окружения Агента Наблюдаемая функция Подкрепление на временном шаге Изменение состояния Агента Политика (действие) Агента Цель Агента

Динамическое взаимодействие агента и окружения Марковский Процесс Принятия Оптимального Решения

Почему Агенты? Агент изменяет свои решения с целью получение максимального подкрепления (reinforcement) При этом он решает требуемую задачу оптимизации! Жизненный цикл Агента включает: Наблюдение окружения (sense) и реакцию на него Выбор поведения (reasoning, adaptation) Активное действие

Сложность Задачи Агента Агент, наблюдая локальные состояния системы и получая локальные подкрепления, должен найти такую способ принятия решений (стратегическую политику), которая бы обеспечивала максимальные подкрепления в будущем. С этой целью Агент должен уметь вырабатывать и помнить внутреннюю сравнительную оценку различный состояний окружения.

Принцип Оптимальности Оптимальное поведение обладает тем свойством, что каковы бы ни были первоначальное состояние и решение в начальный момент, последующие решения должны составлять оптимальное поведение относительно состояния, получившегося в результате первого решения (Ричард Беллман) прошлоебудущее Оптимальная траектория A Предыдущие решения Траектория B t

Граф Марковского процесса решений Состояния Управляющие решения

Оценка позиции Суммарное поощрение, который получит Агент, если в состоянии s он примет решение a и будет оптимально действовать в дальнейшем Исходная цель Агента Оптимальная политика Оценка Как получить оценку позиции Q?

Уравнение Беллмана Формализация принципа оптимальности Проблема проклятия размерности – требуется вычислять Q как функцию большого числа состояний и действий Аргументы Q не являются независимыми, а принадлежат допустимым траекториям, которые, в свою очередь, не определены, пока не определены оптимальные действия Агента

Итерационный Алгоритм SARSA Пошаговое уточнение оценки Алгоритм SARSA Инициализировать Q произвольно Цикл (по траекториям) Установить s в начальное состояние Агента Выбрать a(s), используя текущую оценку Q Цикл (по шагам текущей траектории) Применить действие a, получить r и состояние s Выбрать a(s), используя текущую оценку Q Обновить Q по формуле ( s,a -> r -> s,a) Присвоить s = s, a = a

Исследовательское Поведение Адаптивного Агента При выборе решений a только на основе текущей оценки позиции Q, и оценивании Q только на наблюдаемых последствиях решения a, алгоритм останавливается в локальном экстремуме J Для поиска глобального оптимума Агент должен про- активно принимать поисковые решения, противоречащие текущему здравому смыслу оценки Q

Социальные Агенты Интерфейс Человек- Машина Взаимодействие агентов при решении общей задачи Согласование значений функции оценки позиции Параллельное тестирование многих сценариев поведения Tryllian ADK Bonzi

Аппроксимация Функции Оценки Искусственной Нейронной Сетью Нейронная сеть – универсальный аппроксиматор сложных функций Нейронная сеть выполняет эффективное сжатие информации, уменьшая бремя проклятия размерности Для оценивания нейросети при ее обучении используется изменение функции Q на шаге траектории SARSA-алгоритма s,as,a Q

Нейросетевой Комплекс AFINA Программный комплекс AFINA (Algorithms For Intelligent Neural Applications) предоставляет собой единую технологию решения широкого круга практических задач информационного моделирования В рамках комплекса реализованы новейшие нейросетевые и статистические методы. Комплекс AFINA позволяет создавать, обучать и сохранять нейросетевые решения в виде, удобном для дальнейшего использования. Athena

Применения: План Инвестиций - 1 Инвестиционный портфель с фиксированным бюджетом 100 нейро включает 8 проектов. Возможный объем инвестиций в каждый проект нейро. Неинвестированные деньги приносят фиксированный годовой доход 5%. Доходность проектов приведена в таблице. Возврат инвестиций (в нейро) Размер инвестиций Проект Что делать??

Применения: План Инвестиций - 2 Целевая функция Агента k – время, s: (A k, a k ) – состояние (A k – инвестированная величина в проекты k+1..8, a k – инвестиции в к-й проект) Результат: Оптимальный план с годовой доходностью 22.3 нейро Оптимальный план инвестиций проект объем

Применения: Планирование Поставок - 1 Пусть s(t) – количество товара в магазине, a(t) – объем заказа, w(t) – прогнозируемое потребление Функция оценки и алгоритм поведения Агента (оптимальные заказы u рассчитываются одновременно с Q) Цель: Минимизировать затраты на поставку (c – стоимость перевозки единицы товара), при издержках за недопоставку/хранение

Применения: Динамическое Распределение Каналов в Сотовой Сети Диапазон радиочастот Сети разделен на каналы Пользователи входят в зону действия соты и покидают ее Каждый канал может использоваться несколькими сотами, если они достаточно разнесены географически (нет интерференции) При запросе сервиса пользователь получает свободный канал, если он имеется Необходимо резервирование каналов для обеспечения непрерывности сервиса при переходе от соты к соте, ценой возможной блокировки новых пользователей Цель – минимум блокировок пользователей

Итоги Нейро-динамическое программирование – мощный инструмент решения многошаговых задач динамической оптимизации Разработаны алгоритмы оценки позиции на основе обучения с подкреплением В задачах с высокой размерностью вектора состояния для аппроксимации оценки используются нейронные сети Впереди: оптимальная динамическая адаптация в задачах со несколькими участниками – теория игр

Ссылки и Контакт - Ресурсы по обучению машин и интеллектуальному анализу данных - Американская ассоциация искусственного интеллекта - Исследование Операций и Менеджмент сегодня - Reinforcement Learning Repository, University of Massachusetts, Amherst Сергей Терехов, к.ф-м.н, Зав. лабораторией искусственных нейронных сетей г. Троицк Московской обл. Web (лекции и публикации):