Одна задача оптимального управления и связанная литература

[rincewind112]

Недавно начал интересоваться нелинейным программированием и оптимальным управлением, но литературы по данным вопросам обилие, и неизвестно, как подступиться и с чего начать. В первую очередь интересуют практические аспекты, литература же в основном останавливается на теоретических вопросах. Наткнулся на "Practical Methods for Optimal Control Using Nonlinear Programming" Джона Беттса, - по глубине изложения подходит, но, к сожалению, в этой книге почти ничего не говорится про решение задач о быстродействии, а именно они представляют наибольший интерес.

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

Буду признателен любой помощи. Если нужно что-то уточнить - постараюсь ответить :)

[mserg]

А что такое «Целевое множество» в данной задаче?

[Padawan]

Книжку Понтрянина посмотрите ("Математическая теория оптимальных процессов"), там должно быть.

[mserg]

Спасибо, если Понтрягин – то, стало быть, это множество точек, в одной из которых нужно оказаться в конце движения. Но задача то все равно дохлая. Можно, конечно, разбить траекторию, скажем на 1000 одинаковых по времени интервалов T/1000. Превратить дифференциальное уравнение в разностное, критерий – минимум T. Только вот непересечение траектории (суть множества отрезков) с препятствиями (суть – тоже множествами отрезков) записать в виде «классических» ограничений весьма проблематично. Кажется получается несколько ограничений, соединенных условием ИЛИ – точно навскидку не могу сказать. Если это так, то стандартные пакеты нелинейного программирования работать не будут. Нужны пакеты частично-целочисленного нелинейного программирования. В любом случае, задача будет громоздкой, со множеством локальных оптимумов и со всеми вытекающими отсюда последствиями. По мне так эта задача не для начинающих.

[rincewind112]

Спасибо за ответ, пусть и несколько удручающий :)

Попробую упростить формулировку:
Пусть задача дискретная. Ускорение тела по модулю всегда равно единице, т.е. на каждом шаге можно менять только его направление (направление выбирается из правильного 15-30угольника, вписанного в единичный круг). Более того, отрезки траектории могут попадать в множества-препятствия, - важно только чтобы их концы лежали в допустимой области. А цель та же самая, что и в исходной формулировке.

Таким образом, задача уже разбита на одинаковые по времени интервалы; непересечение траектории с препятствиями сводится к проверке непринадлежности точки выпуклому многоугольнику и нескольким неравенствам на координаты; но как выбирать управление?

Я предполагал, что здесь всё будет опираться на эффективное построение множества достижимости, а уже по нему на следующем шаге траектория будет строиться некоторым известным алгоритмом. Но знаний по этому вопросу нет, и единственное, что нашел - это подробный теоретический разбор задачи Цермело (формулировка тут: http://en.wikipedia.org/wiki/Zermelo#Zermelo.27s_navigation_problem), а вот задач с препятствиями то ли нигде не описывают, то ли я не там ищу. Интересуют любые ресурсы, освещающие подобные задачи. Пусть даже самые простые, - например, оптимизировать ломаную с одним изломом, расположенную внутри квадрата, с единственным препятствием, которое тоже является квадратом.

[mserg]

В математике есть некоторое количество хорошо разработанных классов задач. Когда строится математическая модель, хорошо бы ее «затолкать» в рамки такого класса задач. Тогда с такой моделью можно эффективно работать. Если Вы придумываете свои собственные постановки задач, не входящие в «эффективные» классы задач - сами и будете искать методы их решения. Литература не даст ответа, как эффективно решать задачи в произвольной постановке. Без особого труда можно напридумывать простые постановки задач, у которых нет эффективных методов решения, ну, или они неизвестны. На практике иногда приходится перепробовать десятки моделей, пока не будет найдено нечто приемлемое для реального использования. Это бывает не совсем то, куда завела фантазия заказчика, но нечто реально полезное.

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

Можно попробовать пространство движения представить в виде графа и решить задачу минимального пути.
На арену можно наложить достаточно мелкую сетку, и условиться, что движение возможно только от одного узла сетки к другому. Там, где препятствия, - эти узлы сетки изымаются из рассмотрения. Для каждого узла нужно определить множество точек окрестности, в которые можно попасть. Скажем, окрестность радиусом 5 размеров шага сетки. И соединить их «дорогами» с рассматриваемым узлом. «Дорога», естественно, не может проходить по препятствию. Для окончания движения можно ввести одну точку, и соединить «Целевое множество» с этой терминальной точкой дорогами с длиной 0. Все – получаем граф, в котором нужно найти минимальный путь из исходной точки к терминальной.

Задача будет громоздкой, но с этой моделью хоть как-то можно работать. Можно накладывать неравномерную сетку – вдалеке от препятствий иметь грубую сетку; поблизости – мелкую.

Если есть ограничения на инертность поворота, то это уже динамическое программирование. Не берусь слету сказать, можно ли сделать «дискретной» еще и скорость, и использовать динамическое программирование для подбора оптимального управления. На первый взгляд это возможно. Ну и т.д.

Математика – это не только «методы», это еще и постановка задачи, т.е. подбор эффективных математических моделей. А вот этому у нас толком не учат...

[rincewind112]

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

А про постановку задачи - я её не сам из пальца высосал, а видел реализацию первого описанного мной варианта в университете пару лет назад, поэтому посчитал, что постановка известная и изученная. Только вдобавок в примерах присутствовали движущиеся по прямым и круговым траекториям невыпуклые препятствия. К сожалению, тогда у меня интересы лежали в других сферах, не удосужился подробно поинтересоваться, сейчас жалею :) Наверное, стоит включить режим сыщика и попробовать найти контакты, но это только после января получится.