Проекционные операторы квадратичного программирования для координированного движения беспилотных автомобилей

«ИССЛЕДОВАНИЕ ОПЕРАЦИЙ» ЛЕКЦИЯ-4 22.04.2020 3 КУРС на тему ПРОЕКЦИОННЫЕ ОПЕРАТОРЫ КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ ДЛЯ КООРДИНИРОВАННОГО ДВИЖЕНИЯ БЕСПИЛОТНЫХ АВТОМОБИЛЕЙ 1. Аналитические методы оптимизации для синтеза управлений движущимися беспилотными автомобилями 1.1. Квазианалитические операторы квадратичной оптимизации для стабилизации группы автомобилей Операторы условной минимизации функционалов, заданных квадратом евклидовой нормы, представлены обобщенными проекторами на выпуклое пересечение линейного многообразия и шара. Эти операторы конечномерной оптимизации (ОКО) также отображают параметры экстремальных задач в оптимальные решения. Операторы для неклассических задач, формируемые на основе «принципа двух экстремумов», обобщают операторы допустимых решений, заданных на основе решений классических задач минимизации и максимизации нормы на пересечении линейного многообразия и сферы [25, 29, 33, 35]. Исследованы эквивалентные формы, инварианты и параметры оптимальности ОКО, применяемые для управления энергосистемами с регулярной или хаотической динамикой [34, 36], передачей нефтепродуктов [20], теплофизическими процессами и др. 1. Постановки задач и принципы формулировки квазианалитических операторов для минимизации квадратичных функционалов. Оператор минимизации будут сформулированы для решения конечномерной неклассической экстремальной задачи 1: вычислить где целевой вектор квадрат евклидовой нормы, а допустимое множество определено непустым пересечением линейного многообразия и шара, аппроксимирующего параллелепипеда [29]. Основные принципы для решения задач типа (1) не используют традиционные необходимые и достаточные условия Куна-Таккера теории выпуклого программирования, формулируемые в терминах знаковой определенности множителей Лагранжа для ограничений-неравенств. В данной работе квадрат нормы в задаче (1) минимизируется операторами конечномерной минимизации (ОКМ) на непустом компактном множестве в (1), которые определяются конечными квазианалитическими соотношениями в два этапа. На первом этапе решения формируются операторы допустимых решений на основе «принципа граничных экстремумов» классических задач, следующих из (1). Классические граничные экстремальные решения задач типа (1) вычисляются как классические лагранжевы решения для задач: вычислить экстремальные векторы где допустимое множество как пересечение линейного многообразия и сферы имеет следующий вид На основе операторов для задач (2.а) и (2.б) определены операторы для вычисления граничных (лагранжевых) векторов, которые позволяют минимизировать квадрат нормы на пересечении многообразия и сферы в (2.а), (2.б). Далее формируется однопараметрическое множество допустимых решений, определяемое множителями Лагранжа как выпуклая линейная комбинация граничных элементов, имеющая вид определяет выпуклое однопараметрическое сужение параметра допустимой области и оператор допустимых решений для (2.а), (2.б), отображающий вектор в отрезок с граничными векторами в (2.а) и в (2.б) на указанное выпуклое сужение. На втором этапе вычисляется оптимальный параметр как решение задачи условной одномерной минимизации по параметру . Интервальное ограничение реализуется кусочно-линейным липшицевым проектором на указанный интервал, что позволяет получить решение в квазианалитической форме. Конечномерные операторы оптимизации допускают обобщение на более широкие классы задач, в частности, на задачи минимизации нормы на пересечении линейного многообразия и параллелепипеда, который аппроксимируется эллипсоидом или шаром. Аппроксимация параллелепипеда эллипсоидом или шаром приводит к задаче с одним множителем Лагранжа, что существенно сокращает вычисления, сохраняя качественные свойства ограничений. Минимизирующий скалярный множитель Лагранжа в задаче 1, как параметр оптимальности в задаче на минимум, является положительным в силу непосредственно вычисляемых знаковых ограничений без использования теоремы Куна-Таккера. Форма задания оптимальных решений является конструктивной для анализа систем управления, поскольку явно определяет обратные связи линейного и нелинейного типа, которые по структуре соответствуют законам управления, формируемым в функции координат состояний или выходных координат. Это позволяет выполнить качественный анализ устойчивости замкнутых систем с ограниченными ресурсами для локально или интервально оптимальных систем с ограничениями на управления и координаты без трудоемкой операции решения классического матричного квадратичного уравнения Риккати. 2. Операторы оптимизации для классических задач. Определение операторов можно представить в форме. Определение 1. ОКО – это проекционный квазианалитический оператор конечномерной минимизации (или максимизации) для задачи: вычислить вектор отображающий вектор функционала в оптимальное решение или с учетом параметров задачи оптимизации. Свойства операторов для классических задач минимизации с ограничениями-неравенствами рассмотрены в лемме. Лемма 1 [15, 29]. Ортогональный проекционный оператор на линейное подпространство и матрица которые определяют для вектора функционала проекцию на линейное многообразие обладают свойствами (леммы 1, 2 в п. 2.1): 4)  Эквивалентные формы операторов конечномерной оптимизации, следующие из необходимых условий для задач (2.а) и (2.б), даны ниже. Утверждение 1. Операторы оптимизации, параметризованные множителем Лагранжа, имеют три эквивалентные формы где векторы и определены в лемме 1, а инвариантами для трех форм операторов являются квадратное уравнение для множителей Лагранжа и его корни как параметры оптимальности. Доказательство. Эквивалентные формы ОКО, следующие из необходимых условий для (2.а), (2.б) и функции Лагранжа формируются из условий, представленных системой уравнений Метод исключения для системы (4) с учетом второго уравнения этой системы позволяет вычислить из первого уравнения вектор множителей Лагранжа, преобразовав первое уравнение (4) к виду Тогда с учетом второго уравнения (3) вектор множителей Подстановка (5) в первое уравнение (4) определяет для вектора параметризованное уравнение откуда для следует линейное алгебраическое уравнение Первая форма оператора минимизации как однопараметрическое семейство множителя Лагранжа определяет из (6) вектор Вторая форма оператора оптимизации также параметризованная множителями Лагранжа, вытекающая из (7.а), имеет вид т. к. справедливы равенства как результат преобразования (7.а) в (7.б) Третья форма оператора, следующая из (7.б) и зависящая от множителя Лагранжа , определена равенствами Эквивалентные формы проекционных операторов оптимизации, с множителями Лагранжа как параметра, даны в табл. 2.1. Таблица 2.1 Эквивалентные формы проекционных операторов оптимизации с параметром в виде множителя Лагранжа 1 2 3 Третья форма оператора оптимизации Эквивалентность операторов будет доказана «по цепочке»: Первый переход определен соотношениями В результате определена структура второй формы операторов, поскольку приведенные преобразования определяют однопараметрическое семейство соотношений для эквивалентного задания третьей формы ОКО: Продолжая доказательство эквивалентности, можно иллюстрировать переход 3) приведенными далее соотношениями Таким образом, эквивалентность форм операторов оптимизации доказана на основе трех аксиом эквивалентности: рефлексивности симметрии и транзитивности Проекционные операторы (7.а), (7.б), (7.в) определены «целевыми векторами», параметрами задач (2.а), (2.б) и множителями Лагранжа. Утверждение 2 об операторах для классических задач с параметрами. Пусть выполнено утверждение 1 и ортогональные проекционные операторы оптимизации приведены в табл. 2.1. Тогда для оптимальности решения классической задачи: вычислить вещественные векторы необходимо и достаточно, чтобы выполнялись условия: 1. Векторы условных экстремумов и для функционалов типа евклидовой нормы в классических задачах на компактном множестве в виде пересечения линейного многообразия и сферы (2.а), (2.б) определены операторами, данными в утверждении 1, с параметрами такими, что Квадратное алгебраическое уравнение для оптимальных параметров операторов имеет вид где коэффициенты определяют корни, равные двум значениям множителей Лагранжа 3. При этом уравнение (9.а) и его корни (9.б) являются инвариантами трех форм операторов оптимизации (8.а), (8.б) и (8.в). Условие совместности ограничений экстремальных задач (2.а) и (2.б) (условие существования непустого пересечения линейного многообразия и сферы или шара) задано неравенством Операторы оптимизации в формах типа (8.а), (8.б), (8.в) задают операторы минимизации и максимизации нормы с параметрами оптимальности в виде корней инвариантного квадратного уравнения и соответственно, для задач (2.а) и (2.б) (табл. 2.2), имеющих содержательный смысл для различных классов приложений. Доказательство необходимости. П. 1) и 2) об инвариантности квадратных уравнений и их корней как параметров эквивалентных форм операторов доказывается прямыми вычислениями. Параметры первой формы оператора вычисляются подстановкой (7.а) в третье уравнение (4). Тогда для вычисления знакоопределенных множителей Лагранжа можно получить равенство где в силу леммы 1, п. 1. Преобразование этого равенства в силу свойств операторов проектирования (лемма 1) уравнение Из преобразований этого уравнения следует квадратное уравнение относительно параметров оптимальности совпадающее с (9.в). Тогда первая форма оператора (7.а) примет вид (10.а) Из (10.а) следует условие вещественности корней для совместности ограничений задач 1 и 2, доказывающее п. 2 утверждения. Уравнение (9.а) и корни совпадают для трех форм операторов в силу эквивалентности форм. Третья форма оператора примет вид Подстановка третьей формы оператора (7.в) в третье уравнение системы условий (4) определяет нелинейное уравнение для вычисления множителей Лагранжа, которое примет вид Тогда с учетом свойств матриц (лемма 1) можно получить равенство Из последних соотношений и леммы 1 следует равенство которое определяет инвариантное квадратное уравнение для трех форм операторов оптимизации, данных в табл. 2.2. Вторая форма оператора (7.б), данная в табл. 2.2, имеет вид Таблица 2.2 Эквивалентные формы операторов минимизации и максимизации квадрата нормы на пересечении линейного многообразия и сферы с параметрами оптимальности как корнями квадратного уравнения 1 2 3 Третья форма операторов Равенство (11) определяет структуру и параметры оператора, откуда следует эквивалентность второй и третьей форм операторов Третья форма оператора (7.в) имеет представление поскольку справедливы равенства где параметры как корни квадратного уравнения, равные а функция 3). П. 3 следует из вещественности корней (9.б) для (9.а). 4). В п. 4 надо показать, что положительный корень определяет минимум нормы, а отрицательный – максимум нормы на сфере, что соответствует утверждению теоремы Куна-Таккера. 3. Метод синтеза операторов минимизации нормы на основе «принципа граничных экстремумов и одномерной оптимизации». Синтезированные операторы условной оптимизации для задачи (1.а) сформулированы в утверждениях. Утверждение 3. Пусть справедливы утверждения 1 и 2. Тогда для задачи (1) оператор допустимых решений имеет вид где по утверждению 2 «граничные лагранжевы векторы», определяющие минимум и максимум нормы на пересечении линейного многообразия и сферы (как границы шара) имеют вид Доказательство (15) следует из выпуклости допустимого множества в (1), допустимости (12) и их выпуклой комбинации. Утверждение 4 о квазианалитическом проекционном операторе оптимизации для неклассической задачи. Пусть (1) – корректная задача и справедливы утверждения 1 – 3. Тогда для того, чтобы решение неклассической задачи в силу «принципа граничных лагранжевых экстремумов» представлял регуляризованный оператор минимизации с граничными экстремальными векторами на сфере необходимо и достаточно, чтобы в операторе (16) параметр Доказательство необходимости. Оператор минимизации, как обобщенный проектор, определяется равенством (16), если его параметры задают точки минимума нормы на границе или внутри «сужения» допустимого множества. Этому условию удовлетворяет проектор (16), следующий из оператора (15) при оптимальном выборе параметра на классе допустимых решений. Оператор (16) в форме с параметрами, данными в табл. 2.2, с учетом соотношений определяет семейство допустимых решений параметра решений на основе классических «лагранжевых векторов» В силу сказанного, оператор конечномерной оптимизации с оптимальным параметром должен доставлять минимум квадрата нормы на отрезке одномерного многообразия в пространстве определенном векторами и задающими классические лагранжевы решения задачи 2. Тогда минимизирующий параметр будет совпадать с проекцией на интервал для числового параметра который является точкой безусловного минимума нормы на прямой, включающей лагранжевы векторы и Оператор (16) с оптимальным параметром определяет решение задачи (1), которое является допустимым как выпуклая комбинация «граничных лагранжевых элементов». Внутренняя часть области соответствует параметрам в (16). Параметр вычисляется как точка минимума на «выпуклом сужении» при исходного допустимого множества, параметризованного параметром определяющим уравнения прямой и условия минимума квадрата нормы на прямой (17) по указанному па раметру. Необходимые условия минимума функционала по параметру, преобразованного с учетом (16), имеют вид Параметр, минимизирующий квадратичный функционал типа евклидовой нормы на прямой линии, содержащей точку классического минимума, равен В результате параметр «безусловного минимума на прямой» примет следующий вид где параметр «условного минимума на прямой» для принадлеж- ности решения многообразию и шару в (1) задает проекцию на замкнутый на интервал вычисляемая с помощью скалярного проектора [16]: Равенство (19) определяет допустимый и оптимальный параметр в соотношении (16) как проекцию (18) на отрезок [0, 1] прямой с указанными границами. Таким образом, оператор минимизации (16) для задачи (1) в виде обобщенного проектора на пересечение линейного многообразия и шара на основе «принципа граничных экстремумов», представлен данными табл. 2.3. Таблица 2.3 Оператор типа для минимизации нормы для неклассической задачи (1) с параметрами оптимизации 1 Структура оператора неклассической минимизации нормы 2 Параметры оптимального оператора Оператор минимизации в табл. 2.3 задан суперпозицией двух операторов. Первая составляющая оператора формирует ортогональную проекцию начала координат на линейное многообразие в задаче (1), а вторая (нелинейная) часть оператора задает проекцию вектора на линейное многообразие с параметром, определенным в (19). Обобщенный проектор (16), (19) определен на основе точек минимума и максимума нормы на пересечении многообразия и сферы как границы шара, что определяет необходимые условия для решений без неравенств седловой точки функции Лагранжа. При этом не требуется анализ свойств нормалей разделяющей плоскости в теореме Куна-Таккера. Пример. Пусть задача условной конечномерной минимизации квадратичного функционала имеет вид: вычислить числовой вектор на множестве – пересечении линейного многообразия и шара в двумерном евклидовом пространстве векторов где вектор минимизируемого функционала Решение. Решение на основе (16) имеет вид Шаг 1. Вычисление по табл. 2.3 проектора и квадратичной формы Шаг 2. Вычисление параметров оператора оптимизации: Шаг 3. Вычисление вектора и оптимального решения Квадратичное ограничение-неравенство данной задачи, имещее вид также выполнено для вектора условного оптимального решения. Оптимальный вектор и геометрическая иллюстрация отображения вектора оператором оптимизации в оптимальное решение в задаче условной квадратичной оптимизации приведены на рис. 2.4, где указаны все параметры и линии равного значения функционала для сформулированной задачи условной минимизации. Рис. 2.4. Решение задачи неклассической минимизации нормы как образа проекционного оператора на элементе двумерного евклидова пространства. В результате оператор оптимизации (20) из табл. 2.3 имеет геометрическую иллюстрацию на основе факторизации евклидова конечномерного пространства на линейное многообразие и ортогональное дополнение к нему. Сужение области позволяет свести исходную задачу к одномерной минимизации. Первая составляющая оператора (20) выполняет проектирование нулевого элемента на линейное многообразие в (1). Вторая составляющая оператора (16) есть проекция центра шара на линейное многообразие с весом, который определяет положение точки условного минимума на пересечение многообразия и шара. Таким образом, синтезированные квазианалитические проекционные операторы условной оптимизации, обеспечивающие экстремум функционала в виде нормы при ограничениях типа линейных равенств и квадратичных неравенств. Эти операторы образуют математическую программируемую среду, позволяющую «погружать» в нее широкий класс задач управления с универсальными разрешающими операторами. Домашнее задание. Составить задачу оптимизации в двумерном пространстве и решить ее с помощью примера из лекции. Передать решение преподавателю. 2. ПРИМЕРЫ СИНТЕЗА ПРОГРАММНЫХ ДВИЖЕНИЙ ДЛЯ ВЫПОЛНЕНИЯ ОПЕРАЦИЙ БЕСПИЛОТНЫМИ АВТОМОБИЛЯМИ Этапы синтеза формируются на основе формулировки задачи рассмотренной выше и определяются: - формулировкой задачи, которая может иметь различный вид - структурой проекционного оператора оптимизации. 1. Формулировка задач математического программирования траекторий группы автомобилей на основе заданных движений ведущего автомобиля, которые определены требованиями: - дублирование траектории ведущего автомобиля: - стабилизация относительных положений автомобилей-участников движения; - другие требования к траекториям ведомых автомобилей. Пример. Оператор централизованной автономной (несвязанной) оптимизации движения объектов имеет вид Параметры оптимального оператора заданы равенствами Вариант 1 организации движения БПАМ по единому координирующему сигналу. Программное движение ведущего автомобиля (АМ) можно задать вектором С для случая плоского перемещения автомобилей. Далее можно координировать движение ведомых БПАМ путем передачи этого вектора всем или части ведомых БПАМ. Тогда задача управления будет состоять в обеспечении движения всех АМ по заданному маршруту с сохранением дистанций между ними. Вариант 2 организации движения группы БПАМ по траектории предыдущего автомобиля. Другими словами, этот вариант стабилизации БПАМ на основе применения в качестве программного вектора С в алгоритме траекторий предыдущих автомобилей. Эти две простые задачи могут иметь некоторое решение на основе проекционного оператора. При этом возникает вопрос; каким образом выполнить программирование движений и обеспечить движения всех участников свойством устойчивости. Последнее свойство требует применения такого метода и алгоритма, которые гарантируют устойчивость программных движений. Анализ проекционного метода и алгоритма показывает, что для описания программного и относительного движений можно использовать линейное многообразие, в которое можно «погружать» математические модели участников – БПАМ. Рассмотрим возможности описания динамики с помощью матрицы А, размеры которой по строкам и столбцам могут быть выбраны достаточно большими в соответствии с требованиями задач управления. Тогда в эту матрицу можно «погрузить» модели динамики различных объектов, в том числе и модели всех БПАМ. Пусть эта «МАТРИЦА ОПЕРАЦИИ» имеет ИСХОДНЫЙ ВИД, данный ниже Диагональные блоки «МАТРИЦЫ ОПЕРАЦИИ» содержат не связанные модели БПАМ в виде разностных уравнений отдельных машин. Требуется вычислить: 1 Оптимальные управления для программирований движений группы автомобилей по заданной программе в виде вектора С. Можно видеть, что в данной матрице содержатся математические модели движения трех БПАМ, представленные эквивалентными разностными уравнениями в двух формах Эта система может быть дополнена функционалом качества, который задан квадратом евклидовой нормы Тогда классическая задача конечномерной оптимизации примет стандартный вид. Однако можно эту задачу обобщить за счет введения дополнительного ограничения-неравенства, которое можно использовать для учета ограничений на управления и прогнозируемые координаты. Тогда можно сформулировать общую задачу оптимизации. Кроме этого, можно ввести дополнительные связи между прогнозами координат и управлений, если это имеет смысл и не противоречит требованию реализуемости. Таким образом, классическая задача конечномерной оптимизации примет стандартный вид, на основе которого можно вычислять автономные управления для каждого БПАМ Однако часто по условиям безопасного движения часть требуется эту задачу обобщить за счет введения дополнительных ограничений-неравенств, которые можно использовать для учета ограничений на управления и прогнозируемые координаты. Тогда можно сформулировать обобщенную задачу оптимального управления. Кроме этого, можно реализовать эти дополнительные требования к прогнозам координат и управлений, если это имеет смысл и не противоречит требованию реализуемости. 1. Обобщенная задача оптимального управления. Цели управления движением можно обобщить, дополнив строки или столбцы матрицы «требованиями нестолкновения» отдельных автомобилей группы БПАМ. Это можно сделать, например, введением дополнительных ограничений. Ограничения могут быть заданы дополнительными «условиями различия положений», например, дополнив исходную модель (1) «дополнительными условиями отличия положений». Эти условия могут быть реализованы математическим программированием сдвигами от исходного положений БПАМ на заданные величины по продольным и боковым положениям БПАМ. Для этого можно математически запрограммировать «СДВИГИ ПОЛОЖЕНИЙ БПАМ». «Идея сдвига» реализуется введением «операций вычитания» (или добавления) некоторых «векторов сдвига» для «ЗАДАНИЯ СДВИГОВ» по продольным или боковым координатам всех БПАМ. Эта операция иллюстрируется преобразованием «МАТРИЦЫ ОПЕРАЦИЙ» (1) так, что она примет обобщенный вид. Для этого требуется сформировать расширенную матрицу операции, в которой будут представлены модели (1), дополненные, например, условиями-уравнениями «нестолкновения». Тогда новая матрица операции примет вид где введены управляющие воздействия, обеспечивающие сдвиг за счет корректировки управления для БПАМ. Функционал задачи имеет вид Таким образом, можно обобщить цели управления другим способом за счет корректировки программного движения. Цели управления движением можно также обобщить, дополнив строки или столбцы матрицы «требованиями нестолкновения» отдельных автомобилей группы БПАМ. Это можно сделать, например, введением дополнительных ограничений. Ограничения могут быть заданы дополнительными «условиями различия положений», например, дополнив исходную модель (1) «дополнительными условиями отличия положений». Эти условия могут быть реализованы математическим программированием «сдвигов», предусмотрев их путем корректировки программного движения БПАМ по продольным и боковым положениям БПАМ. Для этого можно математически программировать «СДВИГИ ПОЛОЖЕНИЙ БПАМ». «Идея сдвига» реализуется введением «операций вычитания» (или добавления) некоторых «векторов сдвига» для «ЗАДАНИЯ ПОЛОЖЕНИЙ» по продольным или боковым координатам всех БПАМ. Эта операция иллюстрируется преобразованием «МАТРИЦЫ ОПЕРАЦИЙ» (1) так, что она примет обобщенный вид в части корректировки программных векторов. Для этого требуется сформировать элементы обобщенной «МАТРИЦЫ ОПЕРАЦИЙ», в которой будут представлены модели (1), кдополненные, например, условиями-уравнениями «нестолкновения» на основе корректировки программных векторов для каждого объекта.. ДОМАШНИЕ ЗАДАНИЯ: 1). Составить задачу оптимизации и решить ее с помощью проекционного оператора, действующего в двумерном пространстве и привести геометрическую иллюстрацию решения задачи. 2). Предложите свой вариант корректировки программ движения для обеспечения «нестолкновений». Подготовить персональный ответ для дальнейшей пересылке преподавателю. 3). Какие другие типы «МАТРИЦ ОПЕРАЦИИ» можно предложить для решения задачи управления группой БПЛА. Решения и ответы персональные. Подготовить персональный ответ для дальнейшей пересылке преподавателю.