Например, Бобцов

ПРОГРАММНЫЙ КОМПЛЕКС ДЛЯ АНАЛИЗА ЭФФЕКТИВНОСТИ АЛГОРИТМОВ РЕШЕНИЯ НЕЛИНЕЙНЫХ ЗАДАЧ ОБРАБОТКИ НАВИГАЦИОННОЙ ИНФОРМАЦИИ

ПРОГРАММНЫЙ КОМПЛЕКС ДЛЯ АНАЛИЗА ЭФФЕКТИВНОСТИ АЛГОРИТМОВ...

УДК 621.391.172
ПРОГРАММНЫЙ КОМПЛЕКС ДЛЯ АНАЛИЗА ЭФФЕКТИВНОСТИ АЛГОРИТМОВ РЕШЕНИЯ НЕЛИНЕЙНЫХ ЗАДАЧ ОБРАБОТКИ НАВИГАЦИОННОЙ ИНФОРМАЦИИ
А.Б. Торопов, В.А. Васильев

Описывается программный комплекс, позволяющий проводить анализ эффективности алгоритмов решения нелинейных задач при проектировании современных навигационных систем. Ключевые слова: алгоритмы калмановского типа, фильтрация, навигация.

Введение

До недавнего времени необходимость решения нелинейных задач фильтрации, связанных с навигационной тематикой, возникала лишь при построении систем для традиционных объектов, таких как морские суда, летательные и космические аппараты. В последнее время число объектов, для которых требуется решать такого рода задачи, существенно возрастает. Это обусловлено широким внедрением средств навигации в наземный, и, в первую очередь, в автомобильный транспорт [1]. Кроме того, навигационные системы востребованы и самим человеком, а также активно используются у различного вида роботов [2]. Важно отметить, что допущения, справедливые при решении традиционных навигационных задач, для таких объектов не всегда выполняются.
Для анализа эффективности линейных алгоритмов для навигационных систем широко используются различного рода универсальные программы, облегчающие процесс их создания. Существующие пакеты для нелинейного случая [3, 4] в основном ориентированы на проверку работоспособности алгоритмов, в то время как вопросам анализа точности не уделяется должного внимания. Кроме того, такие программы, по мнению авторов, не обладают удобным интерфейсом.
В работе приводится описание программного комплекса для анализа эффективности решения нелинейных навигационных задач. В частности, рассматривается постановка задачи фильтрации, решаемой в программном комплексе, описываются алгоритмы калмановского типа для решения нелинейных задач фильтрации, используемые в программном комплексе, и предлагается методика оценки их эффективности.

Постановка задачи фильтрации, решаемой в программном комплексе

Задана n-мерная случайная последовательность

xi  ixi1  iwi , и имеются m-мерные измерения

(1)

yi  si (xi )  vi,

(2)

где wi – вектор порождающих шумов; vi – вектор ошибок измерения, i , i – известные матрицы;

si (xi )  [si1(xi ),..., sim (xi )]Т  известная нелинейная функция. Последовательности wi и vi представляют собой дискретные, центрированные белые шумы с известными законами распределения. Предполага-

ется известным закон распределения вектора x0 . Векторы x0 , wi и vi считаются некоррелированными

между собой.

Требуется, располагая накопленными к текущему моменту времени i измерениями

Yi  [y1T , yT2 ,..., yTi ]T , найти рекуррентный алгоритм вычисления оптимальных в среднеквадратическом

смысле оценок xi (Yi ) последовательности (1), минимизирующих критерий

48 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 5 (69)

А.Б. Торопов, В.А. Васильев

 Ji  M xi  xi (Yi )T xi  xi (Yi )

(3)

и алгоритм вычисления характеристик точности в виде матриц ковариаций ошибок оценивания. В выражении (3) М – знак математического ожидания.
Как известно, решение поставленной задачи сводится к отысканию условного среднего с привлечением численных процедур, требующих большого объема вычислений [5]. Задача может быть существенно упрощена, если ввести ограничение на класс используемых оценок при минимизации (3). В рас-
сматриваемых ниже алгоритмах калмановского типа (КТ) предполагается нахождение оценки xi (Yi ) в
классе линейных оптимальных несмещенных оценок.

Алгоритмы калмановского типа, используемые в программном комплексе

Поясним, что понимается под алгоритмами КТ. Предположим, что имеется составной вектор
 zT  xT , yT , y  s(x) , для которого определены математические ожидания x , y , матрицы ковариаций

Pxx , Pyy и взаимная матрица ковариаций Pxy . Под линейной оптимальной несмещенной оценкой будем

понимать оценку следующего вида x(y)  x  K (y  ylin ) ,

(4)

где K и ylin выбираются такими, чтобы обеспечить минимальное значение критерия

 J  M x  xˆ (y)T x  xˆ (y) . Алгоритмы, в которых оценка вычисляется в виде (4) будем называть ал-

горитмами КТ. Известно [5], что при фиксированном известном значении вектора y линейная оптимальная не-

смещенная оценка вектора x и соответствующая ей матрица ковариаций P определяются с помощью

следующих соотношений:

xˆ (y)



x



Pxy

P 1 yy

(y



y)

,

P  Pxx  PxyPyy1Pyx .

(5)

По своей сути алгоритмы КТ различаются процедурами вычисления коэффициента усиления K и

первых двух моментов составного вектора z , включающего оцениваемый вектор и вектор измерений.

В предлагаемом программном комплексе реализованы следующие алгоритмы КТ:

 обобщенный и итерационный фильтры Калмана [5, 6];

 линейный оптимальный алгоритм [5];

 Unscented Kalman Filter [7]. Обобщенный и итерационный фильтры Калмана являются одними из самых простых и удобных

для реализации на практике алгоритмов. Они основаны на разложении нелинейной функции в ряд Тей-

лора с последующим использованием только первых двух членов ряда. Другими словами, такие алго-

 ритмы используют локальную линеаризацию, т.е. при вычислении моментов вектора

zTi



xTi

,

y

T i

пред-

полагается допустимость линеаризованного представления функции si (xi ) .

При получении линейного оптимального алгоритма предполагается, что решается задача отыска-

ния линейных оптимальных несмещенных оценок последовательности (1) по измерениям

Yi  Si (Xi )  Vi , где Si Xi   [s1T x1,sT2 x2 ,...,sTi xi ]T , Xi  [x1T , xT2 ,..., xTi ]T , Vi  [v1T , vT2 ,..., vTi ]T – век-

тор шумов измерений с матрицей ковариаций PVi . В этом случае задача сводится к отысканию первых
 двух моментов вектора zTi  XTi , YiT и последующему применению формул типа (5).
Идея построения алгоритмов типа Unscented Kalman Filter заключается в реализации линейного оптимального алгоритма по рекуррентной схеме, т.е. на каждом шаге отыскиваются моменты вектора
 zi  xTi ,yTi T с использованием информации об оценке и матрице ковариаций с предыдущего шага. При
этом необходимо располагать аппроксимацией плотности прогноза, которая в общем случае неизвестна. В целях упрощения вместо нее используется гауссовская аппроксимация с параметрами, вычисленными на предыдущем шаге. Для снижения объема вычислений при реализации алгоритмов, построенных по

такой структуре, в работе [7] предлагается для вычисления моментов вектора yi и взаимной ковариации
Pxiyi использовать приближенную численную процедуру, названную Unscented Transformation.
При исследовании возможностей алгоритмов КТ для решения различных прикладных задач возникает потребность оценки их эффективности. В нелинейных навигационных задачах основными показателями эффективности алгоритмов являются уровень достигаемой точности и необходимый объем вычис-

Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 5(69)

49

ПРОГРАММНЫЙ КОМПЛЕКС ДЛЯ АНАЛИЗА ЭФФЕКТИВНОСТИ АЛГОРИТМОВ...
лений, причем если объем вычислений можно оценить путем сопоставления затраченного времени на моделирование, то вопросы анализа эффективности с точки зрения точности требуют специального рассмотрения.
Методика оценки эффективности алгоритмов КТ
При исследовании точности рассматриваемых алгоритмов КТ необходимо учитывать два обстоятельства. Во-первых, при построении этих алгоритмов решение отыскивается в классе линейных оценок вида (4), поэтому «эталоном» точности для исследуемых алгоритмов является точность байесовского оптимального алгоритма, обеспечивающего нахождение оценки, минимизирующей (3) без введения каких-либо ограничений [5]. Во-вторых, матрица ковариаций ошибок оценивания, рассчитываемая в алгоритмах КТ (называемая расчетной матрицей ковариаций), может отличаться от своего истинного значения – действительной матрицы ковариаций.
Заметим, что для реализации байесовского оптимального алгоритма необходимо выполнять большой объем моделирования. Эта процедура может быть значительно упрощена, если воспользоваться неравенством Рао–Крамера, которое позволяет найти нижнюю границу для матрицы ковариаций ошибок оптимального оценивания [5].
Таким образом, предлагаемая методика оценки эффективности предполагает:  вычисление характеристики точности, соответствующей байесовскому алгоритму (под характери-
стикой точности понимается зависимость квадратных корней из диагональных элементов матрицы ковариаций от времени);  вычисление расчетной и действительной характеристик точности, соответствующих алгоритмам КТ;  вычисление характеристики точности, соответствующей нижней границе точности;  сопоставление действительной характеристики точности, соответствующей алгоритмам КТ с характеристикой точности, соответствующей оптимальному алгоритму или нижней границе точности;  сопоставление действительных и расчетных характеристик точности, соответствующих алгоритмам КТ.
Программный комплекс
Общая структурная схема программного комплекса представлена на рис. 1.
Ввод априорной информации

Нижняя граница по Рао-Крамеру

Байесовский оптимальный
алгоритм

Моделирование реализаций
вектора состояния
и измерений

Алгоритмы КТ

Оценка и матрица ковариаций, время моделирования
Вычисление действительных и расчетных матриц ковариаций ошибок оценивания

Вывод в удобной для пользователя форме с целью сопоставления
Рис. 1. Структурная схема программного комплекса
Здесь приведены общие блоки, реализующие алгоритмы КТ и иллюстрирующие последовательность действий при реализации методики оценки эффективности, которая заключается в следующем. На основании априорной информации моделируются реализации оцениваемой последовательности (1) и измерений (2), которые являются входными данными для алгоритмов. Оценки, вырабатываемые в этих алгоритмах, используются для формирования действительных матриц ковариаций. Сопоставление полученных матриц ковариаций, соответствующих алгоритмам КТ, оптимальному алгоритму и нижней границе точности позволяет судить об эффективности алгоритмов КТ.
При работе с комплексом программ вначале пользователю предлагается ввести необходимую априорную информацию (рис. 2 и 3). Здесь могут быть выбраны алгоритмы КТ, для которых будет проводиться моделирование, параметры оцениваемой последовательности (1), а также графики, характеризующие зависимости диагональных элементов матриц ковариаций ошибок оценивания (расчетных и действительных), которые выбрал пользователь, от времени. Вид нелинейной функции si (xi ) может зада-
50 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 5 (69)

А.Б. Торопов, В.А. Васильев ваться либо аналитически, либо в виде отдельной m-функции, название которой предлагается ввести пользователю. Значения матриц ковариаций вектора состояния, шумов измерений и порождающих шумов вводятся в виде таблиц. Все введенные пользователем параметры для моделирования можно сохра-
нить в файл для дальнейшего использования.
После ввода всех необходимых значений и нажатия кнопки «Пуск» начинается процесс моделирования, по завершении которого появляются окна вывода результатов моделирования (рис. 4).
Рис. 2. Окно ввода априорной информации
Рис. 3. Окно ввода параметров моделирования

Рис. 4. Окно вывода результатов моделирования
В окнах приводятся зависимости диагональных элементов матриц ковариаций ошибок оценивания (расчетных и действительных), которые выбрал пользователь, от времени. По полученным данным пользователь может судить об эффективности алгоритмов КТ.
Апробация рассмотренного программного комплекса была проведена на примере задачи определения координат объекта по информации о дальностях до точечных ориентиров. Проведенное моделирование подтвердило правильность построения программного комплекса.

Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 5(69)

51

КОМПЕНСАЦИЯ РАДИАЛЬНЫХ ЭЛЕКТРОМАГНИТНЫХ СИЛ ВЕНТИЛЬНОГО ДВИГАТЕЛЯ...

Заключение

Предложена методика оценки эффективности алгоритмов решения нелинейных навигационных задач, с учетом которой разработан программный комплекс, обладающий удобным интерфейсом и позволяющий:
 моделировать алгоритмы калмановского типа для решения нелинейных навигационных задач;
 анализировать эффективность алгоритмов калмановского типа с точки зрения точности и быстродействия. Предполагается провести доработку комплекса программ с целью расширения его возможностей, в
частности, совершенствования интерфейса пользователя и построения графиков апостериорной плотности. Авторы выражают признательность за помощь в подготовке публикации научному руководителю,
д.т.н. Степанову О.А. Работа проводилась при поддержке гранта РФФИ 09-08-00828-a.

Литература

1. Степанов О.А. Состояние, перспективы развития и применения наземных систем навигации для подвижных объектов // Гироскопия и навигация. – 2005. – № 2. – С. 95–121.
2. Lefebvre T., Bruyninckx H. and J. De Schutter. Nonlinear Kalman Filtering for Force-Controlled Robot Task, Springer, Berlin. – 2005. – 265 p.
3. Hartikainen J. and S. Sarkka. Optimal filtering with Kalman filters and smoothers – a Manual for Matlab toolbox EKF/UKF // Centre of Excellence in Computational Complex Systems Research [Электронный ресурс]. – Режим доступа: http://www.lce.hut.fi/research/mm/ekfukf/, свободный. – Яз. англ. (дата обращения 30.06.2010).
4. Van der Merwe R. and E. Wan. «Recursive bayesian estimation library». Сайт: Machine Learning and Adaptive Signal Processing. – Режим доступа: http://choosh.csee.ogi.edu/rebel, свободный. – Яз. англ. (дата обращения 30.06.2010).
5. Степанов О.А. Основы теории оценивания с приложениями к задачам обработки навигационной информации. – СПб: ГНЦ РФ ЦНИИ «Электроприбор. – 2009. – 496 с.
6. Степанов О.А. Применение теории нелинейной фильтрации в задачах обработки навигационной информации. – СПб: ГНЦ РФ ЦНИИ «Электроприбор». – 1998. – 369 с.
7. Juiler S.J. and J.K. Uhlmann. Unscented Filtering and Nonlinear Estimation // Proc. IEEE. – 2004. – V. 92(3). – Р. 401–422.

Торопов Антон Борисович Васильев Владимир Андреевич

– ОАО «ЦНИИ «Электроприбор», научный сотрудник, toropov_a@mail.ru – Санкт-Петербургский государственный университет, аспирант,
vasiliev_vl.a@mail.ru

52 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 5 (69)