Содержание к диссертации
Введение
Глава 1. Алгоритмы определения координат многих целей 11
1.1 Выбор оптимального фильтра в задаче множественной фильтрации 11
1.1.1 Модель наблюдений 12
1.1.2 Сценарий моделирования 17
1.1.3 Результаты моделирования 18
1.2 Список обозначений в задаче множественной фильтрации 22
1.3 Основные понятия и классификация алгоритмов 23
1.3.1 Алгоритмы с поддержкой таблицы треков 24
1.3.2 Алгоритмы байесовской фильтрации 26
1.4 Метод многих гипотез 28
1.4.1 Алгоритм Рида 28
1.4.2 Алгоритм K-Best 32
1.5 Алгоритмы вероятностной ассоциации данных 34
1.5.1 Случай одной цели 35
1.5.2 Модель наблюдаемости для случая с одной целью 37
1.5.3 Случай многих целей 38
1.5.4 Модель наблюдаемости для случая многих целей 41
1.6 Приближенное решение уравнений общей байесовской фильтрации – PHD фильтр 41
1.6.1 Реализация алгоритма PHD методом Монте-Карло (SMC-PHD) 43
1.6.2 Реализация алгоритма PHD в приближении гауссовых смесей (GM-PHD) 46
1.7 Исследование алгоритмов определения координат многих целей 48
1.8 Выводы 51
Глава 2. Построение траектории полета беспилотного аппарата, выполняющего угловые наблюдения
2.1 Постановка задачи оптимального наблюдения за неманеврирующей целью 55
2.1.1 Фазовые переменные и их динамика 55
2.1.2 Формализация задачи 58
2.1.3 Принцип максимума Л. С. Понтрягина 60
2.1.4 Сопряженная система дифференциальных уравнений 61
2.1.5 Двухточечная задача 63
2.1.6 Численное решение задачи 64
2.1.7 Альтернативный подход к решению задачи 65
2.2 Программные траектории полета БПЛА в 3D при наблюдении углов азимута и возвышения 65
2.3 Способ решения задачи на борту БПЛА 73
2.4 Сценарий с двумя БПЛА и только азимутальными наблюдениями 80
2.4.1 Постановка задачи 80
2.4.2 Результаты численного решения задачи оптимального управления 82
2.5 Заключение 85
Глава 3. Использование карты местности в задаче траекторного управления БПЛА 86
3.1 Описание задачи 86
3.2 Движение цели вдоль дороги. Постановка задачи 87
3.3 Движение цели вдоль дороги. Решение задачи 89
3.4 Движение вдоль поверхности Земли. Постановка и решение задачи 90
3.5 Примеры траекторий полета 92
3.5.1 Движение цели вдоль дороги 92
3.5.2 Движение цели вдоль поверхности Земли 93
3.6 Выводы 96
Глава 4. Построение траекторий БПЛА при слежении за наземной целью в радиодиапазоне с помощью антенной решетки 98
4.1 Введение 98
4.2 Постановка задачи 99
4.3 Траектории полета БПЛА 103
4.4 Выводы 109
Заключение 111
Список сокращений и условных обозначений 112
Список литературы
- Список обозначений в задаче множественной фильтрации
- Формализация задачи
- Сценарий с двумя БПЛА и только азимутальными наблюдениями
- Движение вдоль поверхности Земли. Постановка и решение задачи
Список обозначений в задаче множественной фильтрации
Фильтрация угловых наблюдений сопряжена с рядом трудностей, несмотря на протяженную историю развития данной темы [21] и многочисленным, посвящаемым ей, работам [22—24]. Основная сложность связана с нелинейностью функции наблюдения (для декартовых координат) или динамики системы (для полярных координат) может привести к расходимости фильтра.
В настоящем разделе проводится сравнение нескольких рекуррентных алгоритмов получения оценок координат РЛС [25]. Следует отметить, что в работе [26] проведено сравнение алгоритма псевдоизмерений с Байесовским фильтром, использующим метод Монте-Карло. Как продемонстрировано в этой работе, точность определения координат РЛС с помощью байесовского фильтра не хуже точности оценки, получаемой с помощью метода псевдоизмерений. Если же сравнивать эти фильтры с алгоритмом, в котором плотность распределения моделируется с помощью системы взвешенных частиц, то его вычислительная сложность существенно выше любого из упомянутых алгоритмов и потому он исключен из рассмотрения [26]. Кроме того, приведены результаты численных экспериментов [25] по оценке качества работы расширенного фильтра Калмана в декартовых координатах, метода псевдоизмерений, а также фильтра Калмана в модифицированных полярных координатах, для которого динамика системы вычисляется с помощью неспецифического преобразования – Unscented Transform, UT.
Предполагается, что на борту БПЛА установлен пассивный детектор радиоизлучения, который позволяет периодически, с периодом At, определять направление (пеленг) на источник радиоизлучения, если этот источник является активным в текущий момент времени tk = к At Є [0,Т]. Для случая неподвижной цели на плоскости, координаты цели задаются двумерным вектором р = (хе,уе) в некоторой фиксированной системе координат XOY. Считается, что собственные координаты БПЛА (хк,Ук) известны точно в любой момент времени tk. В дальнейшем предполагается, что источник радиоизлучения активен и доступен для наблюдения всегда. В этом случае последовательность наблюдений фк (углов между осью ОХ и направлением на источник излучения) состоит из последовательности точных значений углов в момент tk с некоторой аддитивной помехой Єк Vе —Ук фк = arctan + єк, (1.1) Xе — Хк где є к ЛГ (О, т2) - последовательность независимых гауссовых случайных величин с нулевым средним и дисперсией а2. Метод псевдоизмерений
Идея метода псевдоизмерений основана на другом представлении получаемых данных, при котором связь между измеренным сигналом и оцениваемыми параметрами является линейной. Этот фильтр обладает наименьшей сложностью реализации среди всех вышеперечисленных, но вносит нежелательные искажения, которые характеризуются смещением оценки [27]. Для вывода уравнений фильтрации перепишем формулу (1.1) в следующем виде, считая угол фк и координаты БПЛА наблюдаемыми величинами. (уе — Ук) cos фк — (хе — Хк)sinфк = Єк(хе — Хк) cos фк = Єк- (1.2) Далее, выделим в уравнении (1.2) наблюдаемые и ненаблюдаемые величины, обозначив zk = Хк sin фк — у к cos фк Тогда модель наблюдений примет вид zk = хеsinфк —yecos(f)k + Sk{xe — Xk)cos(f)k. (1.3)
Уравнение (1.3) линейно по ненаблюдаемым компонентам. В предположении о независимости ошибок измерения угла и точно известном положении БП-ЛА, ik имеют нулевое среднее (Её = 0) и матрицу ковариаций, зависящую от текущих оценок ЭДЦ (ж, уек) в момент времени к At. При этом матрица ковариации Pк ошибки оценивания ЭДЦ размера 2 х 2 в момент времени к At имеет вид
Неизвестные координаты источника излучения удовлетворяют системе линейных уравнений со случайной правой частью. Эта система может быть решена с помощью рекуррентного метода наименьших квадратов (фильтрации), который позволяет производить пересчет оценок неизвестных (ХІ,УІ) при поступлении новой информации и кроме того, дает значение среднеквадратической ошибки определения этих неизвестных (см.[28], Гл. 14, 5). Для решения этой задачи мы полагаем, что в модели измерений нам доступы величины хк = (уе — ук) cos фк — (хе — Xk) sin + ek, которые, при подстановке в уравнения фильтрации предполагаются нулевыми (по этой причине их и называют «псевдоизмерениями»). Далее, опуская временной индекс к, отметим символом «» оценку z величины z и оценку ЭДЦ (хе,уе). Тогда Zk = (у — у) cos ф — (хек — х) sin ф. Воспользуемся теперь фильтром Калмана, для чего необходимо вычисление следующих переменных. zx = E[(z — z) (хе — Xе)} = рху cos ф — рхх sin ф, zy = E[(z — z) (уе — уе)} = Руу cos ф — рху sinф, zkz = Е (z — zf = Е [{уе — уе) cos ф — (хе — хе) sin ф + є (хе — х) sin ф]2 . Принимая во внимание равенство хе — х = хе — хе + хе — х, получаем Izz = Рхх sin2 ф + руу cos2 ф - 2рху sin ф cos ф + а2 \рхх + (хе - х)2] sin2 ф. В матричном представлении эти формулы имеют вид Ъх =P sinф 7-гу cos 0 zx - sin P -sin cos cos r)zz= P + СГ2 [Рхж + (ЖЄ - Х) 2] sin 2 0. Здесь и в последующем штрихом обозначается транспонирование. Далее, согласно калмановской схеме для наилучшей линейной оценки ЭДЦ при известных в момент : - оценках (xek,yl), - матрице ковариации P , - функций наблюдения пеленга (sin фк, cos фк), - координат подвижного наблюдателя (хк,ук), с учетом псевдоизмерения zk = О, имеют место следующие формулы для рекуррентного пересчета оценок. {ігг)-1%к , (1.4) т т о/ х zx = У1 У1 Izy fc+1 fc ч т - sin 01. sin jfecos jfe Pjfe+i = Pjfe - (7 )- Pjfe о Pjfe. (1.5) sin cos - cos"1 Оценки, полученные по формулам (1.4), (1.5), являются несмещенными и дают «наилучшие» линейное приближение. Они сохраняются постоянными до следующего измерения пеленга в момент времени tk+\.
При применении расширенного фильтра Калмана в декартовых координатах для получения оценки координат неподвижного источника радиоизлучения можно использовать, как показано выше, модель псевдоизмерений (1.3), которая не является линейной. Для того, чтобы функция наблюдений стала линейной, удобно получать оценку координат РЛС в модифицированных полярных координатах [29]. При использовании модифицированных полярных координат состоя /1 л ние неподвижного источника описывается вектором -, р , где г - относительное расстояние между БПЛА и РЛС, а – угол между осью OX и направлением на РЛС. Начало координат O в данном случае находится в точке расположения БП-ЛА, ось OX направлена на восток, а ось OY – на север. Несмотря на то, что модель наблюдений становится линейной, источник перестает быть неподвижным в силу того, что новое состояние источника описывается в координатной системе, связанной с БПЛА. При этом уравнения динамики РЛС нелинейны.
Основная сложность при нелинейной динамике системы состоит в осуществлении нелинейных преобразований над матрицей ковариации ошибки оценивания ЭДЦ. Линеаризация в окрестности текущей оценки является наиболее распространенным решением, аналогичным с линеаризацией функции наблюдений при использовании расширенного фильтра Калмана в декартовых координатах. Линеаризация необходима для того, чтобы на каждом шаге работы фильтр Калмана оперировал с гауссовым распределением, то есть с оценкой ЭДЦ и матрицей ковариации ошибок оценивания ЭДЦ. Однако существует более простой и эффективный способ: осуществить нелинейное преобразование над плотностью распределения, а затем получить гауссову аппроксимацию полученного распределения. Такой способ реализуем с помощью так называемого «неспецифического преобразования» – Unscented Transform (UT) [30].
Формализация задачи
Опишем далее процедуру численного решения задачи поиска максимума гамильтониана. В ходе численного решения управление хранится в массиве данных в виде последовательности значений, отвечающих различным моментам времени с интервалом At Т. Поскольку применялся метод решения дифференциальных уравнений с переменным шагом, то для получения управления в произвольный (промежуточный) момент времени используется интерполяция.
Для получения оптимальной траектории применялся итеративный алгоритм, на каждом шаге которого значение функционала (2.8) строго убывает. Каждая итерация состоит из следующих шагов. Сначала решается система дифференциальных уравнений (2.4) и (2.11) для фазовых переменных с известными начальными условиями (2.12) для прямого времени «слева-направо» и с выбранным некоторым образом начальным управлением. Затем по известным значениям фазовых переменных строится решение системы сопряженных уравнений (2.15) и (2.16) «справа-налево» с граничными условиями (2.13) в момент t = Т [81].
Для перехода к следующей итерации необходимо обновить управление. Для этого существует две альтернативы. Первая альтернатива использует управление и к+1, которое доставляет в каждой точке траектории на данном итерационном шаге к +1 глобальный максимум гамильтониану. Обновленное управление в каждой ячейке упомянутого выше массива данных записывается следующим образом. Uk+i = auk +(I — а) и 1+1, (2.17) где щ - управление вычисленное на предыдущей итерации, а и к+1 - оптимальное управление, полученное из условия глобального максимума гамильтониана по управлению при известных фазовых и сопряженных переменных в каждой точке траектории. Параметр а є (0; 1) выбран для сглаживания [81]. Вторая альтернатива использует градиентный спуск ик+і = Uk + а—. (2.18)
В качестве альтернативного подхода к построению программных траекторий полета возможно использование эволюции матрицы информации Фишера вместо матрицы ковариации. Такой подход обладает как достоинствами, так и недостатками. В работе [12] исследована задача оптимального маневрирования наблюдателя, выполняющего угловые наблюдения за целью. В [82] показано, что уравнение динамики матрицы информации Фишера при экстраполяции имеют точнотакой жевид, что идля матрицы ковариации.Вэтом случае сопряженная система дифференциальных уравнений имеет достаточно простой вид, и часть этой системы интегрируется аналитически [12]. Такое свойство является преимуществом, которое реализуется только при оптимизации детерминанта матрицы Фишера.
Недостаток такого функционала состоит в том, что он характеризует площадь зоны неопределенности положения цели. Для линейной оценки размеров этой области целесообразно использовать след матрицы ковариации (арифметический кореньизкоторого как раз характеризует линейные размеры этой области). С помощью вычислительных экспериментов проведено сравнение двух методов – предложенного выше и [12]. Оказалось, что оба метода дают примерно одинаковые результаты, что указывает на отсутствие ошибок в реализации численных процедур. Оба метода имеют примерно одинаковую вычислительную сложность.
В этом разделе под наблюдателем подразумевается БПЛА, который для траекторного управления наблюдениями в рамках имеющихся ограничений может осуществлять пространственное маневрирование, управляя углами тангажа и рысканья. Пусть цель движется на плоскости равномерно и прямолинейно. Наблюдению (с помехой) доступны ее углы азимута и возвышения. Рассматривается задача оценки ЭДЦ. Определим декартову систему координат OXY Z (Рисунок 2.1), оси OX, OY и OZ, которой направлены на восток, север и вертикально БПЛА
Геометрия задачи. Слева: управление - углы тангажа /3(t) и рысканья j(t). Справа: наблюдаемые углы азимута фл и возвышения фЕ. вверх соответственно. Поверхность Земли будем считать локально плоской и задавать ее уравнением Z = 0. Предположим, что на этой плоскости цель движется равномерно и прямолинейно со скоростью v. Рассмотрим относительную систему отсчета oxyz с осями параллельными системе OXYZ, связанную с центром масс БПЛА. Начальные координаты цели (в момент t = 0) в этой системе равны (хо,уо, %о), причем ZQ - начальная высота полета БПЛА, взятая с обратным знаком. Пусть vxиvy- компоненты вектора скорости цели. Поскольку z-координата цели всегда известна, ЭДЦ (см. уравнение (2.2)) задаются вектором p(t) = (x(t),y(t),vx,vy). Уравнения движения системы БПЛА-цель имеют вид (см. уравнение (2.4), где Xi = х, Х2 = У, X-i = z) (2.19) x(t) = vx -V cos /3(t) cos 7() y(t) = vy -V cos /3(t) sin 7(t) где (3 = (3 (t) и 7 = 7 (t) суть управления БПЛА по углам тангажа и рысканья соответственно, а V = const - заданная скорость полета БПЛА. В системе отсчета, связанной с центром масс БПЛА, высота его полета имеет отрицательную величину. Динамика высоты полета БПЛА в этой системе отсчета задается следующим уравнением. і = -V sin/3 (t) Сопоставляя с результатами раздела 2.1, получаем, что уравнение (2.19) задает в явном виде уравнения (2.4), а управление u(t) = (ft (t),7 (О) Предполагается, что в начальный момент времени t0 = 0 имеется априорная оценка ро ЭДЦ и задана матрица ковариации ошибок оценивания Pо размера 4x4. БПЛА имеет возможность наблюдать (с помехой) вектор-столбец (см. уравнение (2.5))
Здесь ФА и ФЕ - углы азимута и возвышения, измеряемые с помощью средства пассивной пеленгации в радио [16] или инфракрасном диапазоне (Рисунок 2.1). Подобная схема наблюдений представлена, например, в патенте [83]. Здесь и далее введены обозначения rf = \/х2 + у2, rs = х2 + у1 + z2. Пусть в каждый момент времени собственные координаты БПЛА, линия горизонта и направление на север известны точно, а детектирующее устройство не меняет своей ориентации при маневрах БПЛА, т.е. систематические погрешности в наблюдениях отсутствуют. В этих предположениях матрица ковариации наблюдений диагональная и имеет вид / 2 А \ R= „ . аЕ При численных расчетах примем а А 26 мрад аЕ 78 мрад.
Будем искать управление (/3(t) , (t)) БПЛА в классе условно-программных (см. ра дел 2.3) с терминальным критерием оптимальности (платежным функционалом) вида (2.8). В силу более высокой чувствительности критерия (2.8) к точности оценки компонентов скорости при вычислении следа матрицы P(Т) в качестве единицы длины используется километр, а в качестве единицы скорости - метр в секунду. Альтернативой функционалу (2.8) может служить детерминант матрицы информации Фишера [84]. Выбор в пользу следа ковариационной матрицы объясняется его простой физической интерпретируемостью, поскольку корень из следа матрицы ковариации характеризует линейные размеры сг-доверительной области получаемой оценки ЭДЦ.
Сценарий с двумя БПЛА и только азимутальными наблюдениями
В данном разделе рассмотрен случай слежения за целью в радиодиапазоне с помощью линейной антенной решетки, расположенной вдоль фюзеляжа БП-ЛА [91]. Применение такого рода сенсора существенно изменяет вид программных траекторий БПЛА. Это связано с тем, что антенной решетке присущи сектора, в которых определить направление угла (AoA – Angle of Arrival) прихода сигнала невозможно. Антенные решетки как сенсоры, определяющие AoA, приобрели широкое распространение, в том числе и в телекоммуникациях [88]. Некоторые алгоритмы определения AoA опираются на законы Фурье-оптики [92] и основаны на построении псевдо-спектральной плотности, например, алгоритмы Бартлетта [93], Capon [94] и MUSIC [95], которые описаны в [17]. Поскольку эти алгоритмы базируются на построении спектральной плотности, они требуют существенных вычислительных затрат.
Альтернативный подход связан с использованием алгоритма ESPRIT – Estimation of Signal Parameters via Rotational Invariants [18]. Такой алгоритм не требует сканирования всех возможных значений AoA, оценки которого выводятся непосредственно из корреляционной матрицы сигнала. Алгоритм основан на том, что исходная линейная антенная решетка может быть логически разделена на две идентичных антенных решетки, причем одна из другой получается параллельным переносом. Примером является антенная решетка с четным числом элементов и разбиением на массивы четных и нечетных элементов. В качестве алгоритма оценки AoA в рассматриваемой задаче выбран ESPRIT. В данном разделе предположим, что: – принимаемый сигнал является узкополосным (малая протяженность импульсной характеристики по сравнению с обратной шириной спектра принимаемого сигнала); – помеха представляет собой аддитивный белый шум. Оба эти условия можно считать выполненными, если БПЛА осуществляет полет на большой по сравнению с элементами ландшафта высоте, что устраняет эффект многолучевого распространения сигнала [87]. В противном случае необходимо использовать методы фильтрации ложных срабатываний сенсора, описанные в Главе 1.
Рассмотрим БПЛА, выполняющий полет на фиксированной высоте с постоянной по модулю скоростью V. С борта БПЛА осуществляется наблюдение за целью, движущейся равномерно и прямолинейно со скоростью V вдоль плоской поверхности Земли. Управление БПЛА задается углом рысканья 7 = 7 W - гладкой функцией времени. Введем прямоугольную систему координат с началом отсчета в центре масс БПЛА и выберем координатные оси так, чтобы относительные координаты цели (х,у) = (х (t) ,у (t)) (см. уравнение 2.4) задавались системой дифференциальных уравнений х = -V cos 7 + vT (4.1) у = -Vsin y + Vy с некоторыми начальными условиями (хо,уо). Здесь vx и vy - неизвестные, но постоянные значения компонент вектора скорости цели с фазовым вектором p=(x,y,vx,vy) . (4.2) Функция наблюдения в (2.5) - азимутальное направление на цель Л V(t) в (t)= arctan (4.3) x(t) Дисперсия распределения ошибок является функцией направления (4.3) на цель и ориентации антенной решетки, определяемой направлением движения БПЛА или углом рысканья 7 = 1 (t). Будем искать такое управление БПЛА, которое доставляет минимум функционалу (2.8).
При решении задачи необходимо сначала определить зависимость точности определения AoA от взаимного расположения антенной решетки и цели, после чего появляется возможность включить эту зависимость в явном виде в уравнение (2.7). Рассмотрим угол а (Рисунок 4.1) между точным направлением на цель Нормаль к антенной решетке Антенная решетка Направление на цель
Параметры вычислительного эксперимента по определению точности определения угла прихода сигнала с помощью линейной антенной решетки и алгоритма ESPRIT. Параметр Значение Тип детектируемого сигнала Узкополосный, амплитуднаямодуляция Количество отсчетов при оценке матрицы ковариации сигнала 500 Количество элементов антенной решетки M 40 Расстояние между элементами антенной решетки 0.25Л Параметры многолучевого распространения сигнала Многолучевое распространениесигнала отсутствует, использованамодель AWGN канала Среднее отношение сигнал-шум 0dB Объем выборки при построении оценки 104 независимых экспериментов и нормалью к линии фюзеляжа, вдоль которой установлены антенные элементы. Линия фюзеляжа задается единичным вектором (sin, cos). Нормаль к ней представляет собой единичный вектор (cos, - sin), где – угол рысканья БПЛА. Точность определения AoA оценим с помощью вычислительного эксперимента с параметрами, перечисленными в таблице 14. В результате получена зависимость дисперсии ошибки от значения , изображенная на Рисунок 4.2.
Результаты моделирования точности определения азимутального направления в зависимости от направления на источник сигнала в. Из результатов вычислительного эксперимента видно, что точность определения AoA достаточно хорошо аппроксимируется зависимостью Поскольку для каждого значения было выполнено 104 независимых реплик, то можно с высокой степенью достоверности утверждать, что распределение ошибки определения AoA является нормальным с нулевым средним для значений вплоть до 60.
Большие значения могут быть охарактеризованы как «слепые» зоны, поскольку точность определения угла прихода сигнала становится слишком низкой.
Запишем зависимость (4.4) как функцию x, y, . Для этого найдем величину cos с помощью скалярного произведения вектора относительных координат цели и единичного вектора нормали к линии антенной решетки
Движение вдоль поверхности Земли. Постановка и решение задачи
Алгоритм нахождения решения задачи о К лучших назначениях был впервые предложен в [49]. Пусть имеется задача о назначениях, заданная множеством достижимых назначений А. Для удобства перенумеруем все достижимые назначения так, чтобы они были упорядочены в порядке возрастания (возможно, не строгого) их веса: а\,а2,...,аи: Vj — х,- Є А Д V(a\) V(a2) У{аи) (Б.5)
В основе алгоритма лежит процедура нахождения x,+i при известном х,, или, что то же самое, нахождения наилучшего назначения среди А \ {а\, «2, OLJ} при известных {«і, «2,..., CXJ}. Это достигается путем разбиения задачи о назначениях на подзадачи. А именно, пусть назначение а размера п есть решение задачи Р с множеством достижимых назначений А. Разбиением задачи Р называется набор задач {P I}=Q с соответствующими им множествами достижимых назначений А\, для которого выполнены следующие условия: ИД = Л\ а (Б.6) г=0 Vi J = 0,n : і ф j; = Л І П Aj = 0 (Б.7) Если разбиение для задачи Р известно, тогда наилучшее из решений задач Р[ есть назначение минимального веса среди А\ а . Таким образом, суть алгоритма Мурти состоит в нахождении разбиения задачи о назначениях при известном оптимальном решении.
На каждом шаге алгоритма требуется нахождение решения некоторого числа задач о назначениях. Данные решения могут быть получены с помощью Венгерского алгоритма [96] или алгоритма Джонкера-Волгенанта [53].
Опишем процедуру отыскания разбиения произвольной задачи Р. Для каждой пары индексов из (kjt) Є а строится задача Р[ путем удаления (kjt) из всех допустимых назначений задачи Р. Это означает, что а не может быть решением задачи Р[. Далее, перед построением задач Р/+1,..., Р п, из Р удаляются все пары индексов (it,к): к Ф jtи (ljt) 1 ф it, кроме (kjt). Это означает, что любое возможное решение всех последующих задач Р{+1,... ,Р п содержит (itjt), а значит, множества данных решений не пересекаются с множеством решения задачи Р[.
После разбиения исходной задачи P, все подзадачи из разбиения помещаются в очередь с приоритетом, где в качестве ключа используется вес оптимального решения задачи. Очередь инициализируется исходной задачей P0 и ее наилучшим решением 0. На каждом шаге алгоритма из очереди извлекается задача с наилучшим решением, для нее производится процедура разбиения, после чего полученные подзадачи помещаются в очередь. Процесс продолжается до тех пор, пока не будут найдены K наилучших решений (или пока очередь не станет пустой).
Для каждого из K лучших решений производится процедура разбиения, которая в худшем случае создает O(N) новых подзадач, т.е. на каждом шаге требуется решение в худшем случае O(KN) задач о назначении. Решение одной задачи о назначении имеет сложность O(N3) для Венгерского алгоритма и O(N2 logN) для алгоритма Джонкера-Волгенанта.
Приложение В Неравенство Крамера-Рао Неравенство Крамера-Рао определяет нижнюю границу дисперсии любой несмещенной оценки детерминированного параметра. Пусть X = {Xi}J=1 - последовательность независимых одинаково распределенных случайных величин с абсолютно непрерывным распределением, обладающих плотностью распределения f(x; в), зависящей от неизвестного параметра в. Логарифмическая функция правдоподобия определяется соотношением
Предположим, что логарифмическая функция правдоподобия L(X;в) удовлетворяет условию регулярности: Г дL(X\0) 1 дв дL(X:в) Еv = О (В.3) дв Далее, пусть в(X) - несмещенная оценка параметра в. Тогда дисперсия данной оценки ограничена снизу обратной информацией Фишера: var(0(X)) 1{в) 1 (В.4) Данное неравенство задает границу Крамера-Рао. У ОКБ СИМОНОВА Открытое акционерное общество Научно-производственное объединение "Опытно-конструкторское бюро имени М.П. Симонова" Адрес: ул. Академика Павлова, д. 2а, г. Казань, Россия, 420036 Телефон: +7 (843) 571-44-38, факс: +7 (843) 571-44-69 e-mail: info@okbsimonova.ru www.okbsimonova.ru От № На № От Г 1 АКТ внедрения результатов диссертационной работы Андреева К.В. «Траекторное управление наблюдениями с борта беспилотного летательного аппарата». Настоящий акт подтверждает, что результаты диссертационной работы Андреева К. В. «Траекторное управление наблюдениями с борта беспилотного летательного аппарата», представленной на соискание ученой степени кандидата технических наук, использованы в практической деятельности АО НПО «ОКБ им. М.П. Симонова» при разработке полетных заданий и траекторий полета беспилотных летательных аппаратов (БЛА) с функциями радиотехнического мониторинга.
В АО НПО «ОКБ им. М.П. Симонова» использованы и внедрены следующие результаты диссертационной работы Андреева К.В.: етод локализации многих объектов интереса по угловым наблюдениям с БЛА; способ построения траектории полета БЛА, выполняющего угловые наблюдения, при котором достигается наилучшая оценка элементов движения цели за время ведения мониторинга; оптимизация траектории полета БЛА с аппаратурой пеленгации бокового обзора.
Примененные результаты диссертационной работы позволили автоматизировать процедуру планирования полетного задания БЛА радиотехнического мониторинга, а также повысить кщеетай.оценок координат объекта интереса в ходе выполнения задач радиот ше. -Ео. иторинга.
Настоящий акт подтверждает, что результаты диссертационной работы Андреева К. В. «Траекторное управление наблюдениями с борта беспилотного летательного аппарата», представленной на соискание ученой степени кандидата технических наук, использованы в практической деятельности ЗАО «Телум» при разработке программного обеспечения по моделированию алгоритмов планирования миссий беспилотных летательных аппаратов (БПЛА) радиотехнической разведки.