Контрпример Витсенхаузена , показанный на рисунке ниже, представляет собой обманчиво простую игрушечную задачу в децентрализованном стохастическом управлении . Он был сформулирован Гансом Витсенхаузеном в 1968 году. [1] Это контрпример к естественной гипотезе о том, что можно обобщить ключевой результат централизованного линейно-квадратично-гауссовского управления.системы - что в системе с линейной динамикой, гауссовским возмущением и квадратичной стоимостью аффинные (линейные) законы управления оптимальны - для децентрализованных систем. Витсенхаузен построил двухэтапную линейно-квадратичную гауссовскую систему, в которой два решения принимаются лицами, принимающими решения с децентрализованной информацией, и показал, что для этой системы существуют нелинейные законы управления, которые превосходят все линейные законы. Проблема нахождения оптимального закона управления остается нерешенной. [2]
Формулировка контрпримера
Формулировка контрпримера проста: два контроллера пытаются управлять системой, пытаясь приблизить состояние к нулю ровно за два временных шага. Первый контроллер наблюдает за начальным состоянием На входе указана стоимость первого контроллера, а затраты на государство после ввода второго контроллера. Вход второго контроллера бесплатен, но основан на зашумленных наблюдениях государства после первого входа контроллера. Второй контроллер не может взаимодействовать с первым контроллером и, следовательно, не может наблюдать исходное состояние. или вход первого контроллера. Таким образом, динамика системы
с уравнением наблюдения второго регулятора
Цель состоит в том, чтобы минимизировать функцию ожидаемых затрат ,
где ожидание берется из случайности в начальном состоянии и шум наблюдения , которые распространяются независимо . Шум наблюденияпредполагается распределенным по Гауссу , а распределение значения начального состояния отличается в зависимости от конкретной версии проблемы.
Проблема в том, чтобы найти управляющие функции
которые дают, по крайней мере, такое же хорошее значение целевой функции, как и любая другая пара функций управления. Витсенхаузен показал, что оптимальные функции а также не может быть линейным.
Конкретные результаты Витсенхаузена
Витсенхаузен получил следующие результаты:
- Оптимум существует (теорема 1).
- Оптимальный закон управления первого регулятора таков, что (Лемма 9).
- Дается точное решение для случая, когда оба регулятора должны быть линейными (лемма 11).
- Если имеет гауссовское распределение, и если хотя бы один из контроллеров ограничен как линейный, то оптимально, чтобы оба контроллера были линейными (лемма 13).
- Приведены точные нелинейные законы управления для случая, когда имеет двухточечное симметричное распределение (лемма 15).
- Если имеет гауссово распределение, при некоторых значениях параметра предпочтения дается неоптимальное нелинейное решение для законов управления, которое дает более низкое значение для ожидаемой функции затрат, чем лучшая линейная пара законов управления (теорема 2).
Значимость проблемы
Контрпример лежит на пересечении теории управления и теории информации . Из-за своей сложности проблема поиска оптимального закона управления также привлекла внимание теоретиков информатики . Важность проблемы была отражена на 47-й конференции IEEE по решениям и контролю (CDC) 2008, Канкун, Мексика, [2], где целая сессия была посвящена пониманию контрпримера через 40 лет после его первой формулировки.
Проблема имеет концептуальное значение в децентрализованном управлении, потому что она показывает, что для контроллеров важно неявно взаимодействовать [3] друг с другом, чтобы минимизировать затраты. Это предполагает, что управляющие действия в децентрализованном управлении могут иметь двойную роль: управляющие и коммуникационные.
Сложность проблемы
Сложность проблемы объясняется тем, что информация второго контроллера зависит от решений первого контроллера. [4] Варианты, рассмотренные Тамером Басаром [5], показывают, что жесткость также зависит от структуры индекса производительности и связи различных переменных решения. Также было показано, что проблемы в духе контрпримера Витсенхаузена упрощаются, если задержка передачи по внешнему каналу, который соединяет контроллеры, меньше, чем задержка распространения в задаче. Однако этот результат требует, чтобы каналы были идеальными и мгновенными, [6] и, следовательно, имеет ограниченную применимость. В практических ситуациях канал всегда несовершенен, и поэтому нельзя предполагать, что проблемы децентрализованного управления просты при наличии внешних каналов.
Обоснование неудачи попыток дискретизации проблемы было найдено в литературе по информатике: Христос Пападимитриу и Джон Цициклис показали, что дискретная версия контрпримера является NP-полной . [7]
Попытки получить решение
Для решения контрпримера было предпринято несколько численных попыток. Ориентация на конкретный выбор параметров задачи, исследователи получили стратегии путем дискретизации и использования нейронных сетей . [8] Дальнейшие исследования ( в частности, работа Ю-Чи Хо , [9] и работа Li, Мардена и Shamma [10] ) имеет несколько улучшенные , полученные затраты на том же выборе параметров. Наиболее известные численные результаты для множества параметров, включая упомянутый ранее, получены с помощью алгоритма локального поиска, предложенного С.-Х. Ценг и А. Тан в 2017 г. [11] Первые доказуемо приблизительно оптимальные стратегии появились в 2010 г. (Гровер, Парк, Сахай) [12], где теория информации используется для понимания коммуникации в контрпримере. Оптимальное решение контрпримера остается открытой проблемой.
Рекомендации
- ^ Витсенхаузен, Ганс. «Контрпример в стохастическом оптимальном управлении». SIAM J. Control , том 6, выпуск 1, стр. 131–147 (февраль 1968 г.)
- ^ a b Хо, Ю-Чи, "Обзор проблемы Витсенхаузена". Материалы 47-й конференции IEEE по принятию решений и контролю (CDC) , стр. 1611–1613, 2008 г.
- ^ Миттеран и Сахай. «Информация и контроль: еще раз о Витсенхаузене». Обучение, управление и гибридные системы , 1999, Springer.
- ^ Хо, Ю-Чи. «Теория командных решений и информационные структуры». Труды IEEE , Vol. 68, No 6, июнь 1980 г.
- ^ Басар, Укротитель. «Вариации на тему контрпримера Витценхаузена». 47-я конференция IEEE по решениям и контролю, Канкун , Мексика, 9–11 декабря 2008 г.
- ^ Rotkowitz, M .; Cogill, R .; Lall, S .; , «Простое условие выпуклости оптимального управления сетями с задержками», Decision and Control , 2005 и 2005 European Control Conference. CDC-ECC '05. 44-я конференция IEEE , стр. 6686–6691, 12–15 декабря 2005 г.
- ^ Христос Пападимитриу и Джон Цициклис . «Сложные проблемы теории управления». 24-я конференция IEEE по вопросам принятия решений и контроля , 1985 г.
- ^ Baglietto, Parisini и Zoppoli. «Численное решение контрпримера Витсенхаузена с помощью аппроксимирующих сетей». IEEE Transactions по автоматическому контролю . 2001 г.
- ↑ Ли, Лау и Хо. «Контрпример Витсенхаузена: иерархический поиск для невыпуклых задач оптимизации». IEEE Transactions по автоматическому контролю , 2001 г.
- ↑ Ли, Марден и Шамма. «Изучение подходов к контрпримеру Витсенхаузена с точки зрения потенциальных игр». Конференция IEEE по решениям и контролю , 2009 г.
- ^ Ценг и Тан. «Алгоритм локального поиска для контрпримера Витсенхаузена». Конференция IEEE по решениям и контролю , 2017.
- ^ Гровер, Сахай и Парк. «Конечномерный контрпример Витсенхаузена». IEEE WiOpt 2010, семинар ConCom , Сеул, Корея.