ИСПОЛЬЗОВАНИЕ ПОСЛЕДОВАТЕЛЬНЫХ МЕТОДОВ МОНТЕ-КАРЛО В ЗАДАЧЕ КОРРЕЛЯЦИОННО-ЭКСТРЕМАЛЬНОЙ НАВИГАЦИИ
Использование последовательных методов Монте-Карло в навигации
49
УДК 621.391.172
О. А. СТЕПАНОВ, А. Б. ТОРОПОВ
ИСПОЛЬЗОВАНИЕ ПОСЛЕДОВАТЕЛЬНЫХ МЕТОДОВ МОНТЕ-КАРЛО В ЗАДАЧЕ КОРРЕЛЯЦИОННО-ЭКСТРЕМАЛЬНОЙ НАВИГАЦИИ
Исследуется возможность применения последовательных методов МонтеКарло в задаче корреляционно-экстремальной навигации при учете изменчивости оцениваемого вектора. Обсуждаются особенности применения таких методов и предлагается алгоритм, основанный на апостериорной (повторной) существенной выборке.
Ключевые слова: метод Монте-Карло, фильтрация, точность, навигация.
Введение. В последнее время значительное развитие получили рекуррентные алгоритмы решения задач нелинейной фильтрации, основанные на последовательных методах Монте-Карло. К ним, в частности, относятся парциальные фильтры (particle filtres), бутстрэп (bootstrap) фильтры и ряд их модификаций [1—3]. В настоящей работе исследуется возможность применения аналогичных алгоритмов в задаче корреляционно-экстремальной навигации. Особенность этой задачи заключается в ее нелинейном и протяженном во времени характере, что обусловливает необходимость учета изменчивости оцениваемого вектора. Обычно такой учет осуществляется путем сведения исходной нелинейной задачи к некоторому линейному аналогу [4], что при определенных условиях приводит к снижению точности решения. В настоящей работе предлагается учитывать изменчивость в рамках нелинейной постановки задачи при ее решении с использованием последовательных методов Монте-Карло.
Постановка задачи корреляционно-экстремальной навигации. Задача корреляционно-экстремальной навигации может быть сформулирована следующим образом [4]. Пусть известны значения параметров ϕ i , λ i некоторой навигационной системы в i -е моменты времени
ϕ i = ϕi + ∆ϕi , λ i = λi + ∆λi ,
(1)
где ϕi , λi — истинные координаты объекта; ∆ϕi , ∆λi — погрешность определения координат. Предположим, что имеются скалярные измеренные параметры некоторого геофизиче-
ского поля, например, рельефа дна:
yi = ψ(ϕi , λi ) + χ + vi , i =1, m ,
(2)
где ψ(ϕi , λi ) — известная функция, описывающая зависимость рельефа (глубин) дна от координат; χ и vi — систематическая и флуктуационная составляющие ошибок измерений. Введем
функцию ψ(ϕi , λi ) = ψ(ϕ i − ∆ϕi , λ i − ∆λi ) = si (∆ϕi , ∆λi ) и векторы θi =[∆ϕi ∆λi ]T и
xTi = ⎡⎣χ
θTi
⎤ ⎦
.
Тогда,
используя
модель
для
вектора
xi
,
задачу
корреляционно-экстремальной
навигации можно сформулировать как задачу фильтрации вектора
xi = Φi xi−1 + Γi wi
(3)
с использованием результатов измерений
yi = si (θi ) + χ + vi ,
(4)
где wi — вектор шумов; Φi , Γi — известные матрицы. Будем полагать, что wi и vi
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 10
50 О. А. Степанов, А. Б. Торопов
представляют собой центрированные гауссовы, дискретные, белые шумы с матрицей ковариации Q и дисперсией R . Вектор начальных условий x0 также полагаем центрированным гауссовым с известной матрицей ковариаций Px0 .
Суть задачи фильтрации заключается в следующем. Располагая накопленными к текущему моменту времени i результатами измерений Yi =[y1T , yT2 , ..., yTi ]T , необходимо найти алгоритм вычисления оптимальных по среднему квадратическому отклонению (СКО) оценок xˆ i (Yi ) по-
{ }следовательности (3), минимизирующих критерий Ji = M (xi − xˆi (Yi ))T (xi − xˆ i (Yi )) , и соот-
ветствующую матрицу ковариаций их ошибок. Известно, что это может быть сделано с помощью следующих выражений [4]:
∫ ∫xˆiopt (Yi ) = xi f ( Xi / Yi ) dXi , Piopt (Yi ) = (xi − xˆ i (Yi ))(xi − xˆ i (Yi ))T f (Xi / Yi )dXi , (5)
в которых f (Xi / Yi ) — апостериорная функция плотности распределения вероятности для
составного вектора Xi = ⎣⎡x1T , ..., xTi ⎤⎦T . Таким образом, задача корреляционно-экстремальной
навигации в предложенной постановке сводится к вычислению интегралов (5). Для ее реше-
ния разработаны эффективные алгоритмы для случая, когда порождающие шумы отсутству-
ют, а матрица Φi — единичная. Если оцениваемый вектор изменчивый, то для вычисления
интегралов можно использовать последовательные методы Монте-Карло.
В дальнейшем рассматривается простейший случай, когда считается, что матрица Φi
также
единичная,
wi
—
двумерные
векторы,
матрица
ΓTi
=
⎡0 ⎢⎣0
1 0
0⎤ 1⎦⎥
,
т.е.
считается,
что
ошибки θi описываются винеровскими последовательностями.
Простейший последовательный метод Монте-Карло. Запишем выражение для апо-
стериорной плотности распределения вероятности в виде
∫f (Xi / Yi ) =
f (Yi / Xi ) f (Xi ) , f (Yi / Xi ) f (Xi )dXi
где f (Yi / Xi ) — функции правдоподобия, f (Xi ) — априорная плотность распределения ве-
роятности составного вектора.
Предположим, что имеется Xij — выборка случайных векторов, соответствующих
f (Xi ) , тогда оценка и матрица ковариаций (5) могут быть вычислены с помощью метода
Монте-Карло. В результате получим формулы [4]
∑ ∑ ( )( )xˆ i (Yi ) ≈ xˆ iMC (Yi ) = L qij xij , Pi (Yi ) ≈ PiMC (Yi ) = L qij xij − xˆ iMC (Yi ) xij − xˆ iMC (Yi ) T , (6) j=1 j=1
где qij — нормированные веса, определяемые как
∑qij = qij L qij , j =1
(7)
( )qij = f Yi / Xij — ненормированные веса. Формулы (6) и (7) могут быть получены, если по-
лагать, что для функции f (Xi ) используется аппроксимация в виде [5]:
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 10
Использование последовательных методов Монте-Карло в навигации
51
( )∑f
(Xi ) ≈
1 L
L
δ
j =1
Xi − Xij
,
(8)
где δ(•) — многомерная дельта-функция. Соответственно плотность распределения вероят-
ности f (Xi / Yi ) может быть записана как
( )∑f (Xi / Yi ) ≈ L qij δ Xi − Xij . j =1
(9)
Отличительная особенность приведенных выше соотношений заключается в том, что
ненормированные веса могут вычисляться с помощью рекуррентных соотношений
qij = f (yi / xij )qij−1, qij−1 = f (Yi−1 / Xij−1) ,
(10)
поскольку f (Yi / Xij ) = f (yi / Yi−1, Xij ) f (Yi−1 / Xij ) = f (yi / xij ) f (Yi−1 / Xij−1) . Входящая в это
выражение функция f (yi / xij ) легко вычисляется с использованием выражения (4). Для вычисления выражения (9) необходимо промоделировать L выборок случайных
векторов в соответствии с функцией f (Xi ) . Такие выборки могут быть получены рекуррент-
но с использованием
X
j i −1
и соотношений
(3).
Однако анализ выражения (10) показывает, что для вычисления оценки и матрицы ко-
вариаций
(6)
на
каждом
шаге
достаточно
иметь
только
выборки
xj i−1
,
с использованием
кото-
рых формируется выборка Xij , j =1, L . Таким образом, становится очевидным, что на каж-
дом i -м шаге нет необходимости хранить в памяти всю „предысторию“, т.е. выборки Xij−2 . При использовании соотношений (6) наибольший вклад в результат вычислений оказы-
вают выборки, расположенные в областях, где апостериорная плотность существенно отлич-
на от нуля. Поскольку при использовании простейшего последовательного метода выборка
формируется в соответствии с априорной плотностью распределения вероятности f (Xi ) , то
значительное число элементов выборки этому требованию не удовлетворяет. В результате с
течением времени может возникнуть ситуация, когда значения всех весов (6) станут близки-
ми к нулю, что в полной мере проявилось при попытке применения этого метода в рассмат-
риваемой задаче корреляционно-экстремальной навигации. Эта проблема известна как про-
блема „вырождения“ алгоритма [5].
Существуют два основных метода преодоления этой проблемы: метод существенной
функции и метод апостериорной (повторной) существенной выборки [5] — в настоящей ра-
боте используем второй.
Последовательный метод Монте-Карло с апостериорной существенной выборкой.
Поясним идею применения метода апостериорной существенной выборки для решения зада-
чи фильтрации. Запишем выражение для апостериорной плотности распределения вероятно-
сти в виде
∫f (Xi /Yi ) =
f (yi /xi ) f (Xi /Yi−1) , f (yi /xi ) f (Xi /Yi−1)dXi
(11)
где f (Xi/Yi−1) — плотность прогноза. Предположим, то имеется выборка Xij , полученная в
соответствии с этой плотностью, тогда можем записать
( )∑f
( Xi
/
Yi−1 ) ≈
1 L
L
δ
j=1
Xi − Xij
.
(12)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 10
52 О. А. Степанов, А. Б. Торопов
Чтобы сформировать выборку Xij , соответствующую f (Xi/Yi ) , необходимо рассчитать [6]
µij = f (yi /xij )
(13)
[ ]и промоделировать выборку случайных величин ~x1i ... ~xiL в соответствии с дискретным
[ ]законом распределения, задаваемым множеством x1i ... xiL . Каждому элементу этого мно-
жества соответствует вероятность qij , вычисляемая по формуле (7), в которой q~ij = µij . Затем
для вычисления f (Xi+1 / Yi ) = f (xi+1 / xi ) f (Xi / Yi ) необходимо промоделировать выборку в
( )соответствии с плотностью распределения вероятности
L
∑f
xi+1 / ~xij
, которая используется
j =1
[ ]на следующем шаге для формирования ~xi1+1 ... ~xiL+1 . Описанная процедура повторяется на
каждом шаге, благодаря чему обеспечивается рекуррентный характер алгоритма фильтрации.
Эффективность применения описанной процедуры в задаче корреляционно-экстремальной
навигации проиллюстрирована на рис. 1 (а — график апостериорной плотности распределе-
ния вероятности; б — априорная выборка (серый цвет) и апостериорная выборка (черный);
в и г — изолинии апостериорной плотности на фоне априорной и апостериорной выборки
соответственно).
а) Z
б) Y
20 –2000
10 0
0
1000
2000 Y
2000
0
X 2000 2000
в) Y
г) Y
1600
1600
2000
2000
2400
2400
0 –2000 X
2800
2800
3000 2000 1000 0 –1000 X
3000 2000 1000 0 –1000 X
Рис. 1
Из представленного примера видно, что в результате применения описанной процедуры
удается сформировать выборку, соответствующую апостериорной плотности распределения
вероятности, в результате чего удается преодолеть проблему вырождения алгоритма. Бутстрэп-
фильтр (В-фильтр), использующий такую процедуру, был впервые предложен в работе [2].
Результаты моделирования. Для оценки эффективности применения В-фильтра в за-
даче корреляционно-экстремальной навигации было проведено моделирование на участках
поля рельефа с углами наклона в пределах 0—20°. Предполагалось, что информация о поле рельефа представлена в виде его значений в узлах равномерной сетки с расстояниями между
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 10
Использование последовательных методов Монте-Карло в навигации
53
узлами, равными 30 ∆ . Средние квадратические отклонения для ошибок по каждой коорди-
нате принимались равными 30 ∆ . СКО систематической составляющей погрешности выбира-
лось равным 5 ∆ . Общее число используемых измерений, выполняемых с шагом 30 ∆ , при-
нималось равным 35. СКО шума измерений составляло 0,05—2 % от среднего значения глу-
бины на участке движения. СКО порождающих шумов принималось равным 5 ∆ .
При моделировании вычислялись характеристики точности, формируемые с использо-
ванием метода статистических испытаний [7]. Число реализаций метода Монте-Карло для
расчета безусловных СКО принималось равным 1000, число реализаций L при использовании
В-фильтра равнялось 625. Результаты моделирования приведены на рис. 2 (действительные 1 и
расчетные 2 СКО оценок с использованием В-фильтра: а—в — с учетом изменчивости, г — без
учета изменчивости; а, г — ошибка по широте, б — по долготе, в — погрешность карты).
а) ∆, у.е.
а) ∆, у.е.
25
25 11
15 15
52 0
10 20 30 № измерения
40
52 0
10 20 30 № измерения
40
в) ∆, у.е.
г) ∆, у.е.
4 1
3
2
25 1 20 15 10
1 2
5 2
0 10 20 30 40 № измерения
0 10 20 30 40 № измерения
Рис. 2
С целью сопоставления на рис. 2, г приведены действительные и расчетные СКО, соответствующие В-фильтру для одной из компонент вектора состояния, когда изменчивость ошибок навигационной системы в модели не учитывалась, т.е. в условиях, когда для случая винеровских моделей расчетная модель соответствовала неизменному во времени вектору.
Из представленных результатов следует, что применение В-фильтра позволяет решать рассматриваемую задачу фильтрации в условиях изменчивости ошибок навигационной системы. Подтверждением правильности получаемых результатов, в частности, служит совпадение расчетной и действительных характеристик точности.
Выводы. Проведенные исследования подтвердили эффективность применения последовательного метода Монте-Карло, основанного на апостериорной (повторной) существенной выборке, для решения задачи корреляционно-экстремальной навигации. В дальнейшем планируется реализовать эти методы при решении задачи корреляционно-экстремальной навигации в случае, когда используется более сложная модель ошибок навигационной системы.
Работа выполнена при поддержке гранта РФФИ № 09-08-00828а.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 10
54 О. А. Степанов, А. Б. Торопов
СПИСОК ЛИТЕРАТУРЫ
1. Arulampalam S., Maskell S., and Gordon N. A Tutorial on Particle Filters for on-line nonlinear/non-Gaussian Bayesian tracking. DSTO 2001, IEEE 2001.
2. Gordon N. J., Salmond D. J., and Smith A. F. M. Novel approach to nonlinear/non-Gaussian Bayesian state estimate // IEEE Proc. Pt. F. 1993. Vol. 140, N 2. P. 107—113.
3. Doucet A., de Freitas N., and Gordon N. J. Sequential Monte Carlo Methods in Practice. NY: Springer-Verlag, 2001. P. 581.
4. Степанов О. А. Применение теории нелинейной фильтрации в задачах обработки навигационной информации. СПб: ЦНИИ „Электроприбор“, 2003. 369 с.
5. Doucet A. On sequential simulation-based methods for Bayesian filtering // Technical Report CUED/FINFENG/ TR 310. Department of Engineering, Cambridge University, 1998. P. 26.
6. Smith A. F. M. and Gelfand A. E. Bayesian statistics without tears: a sampling-resampling perspective // Amer. Stat. 1992. Vol. 46. P. 84—88.
7. Степанов О. А. Основы теории оценивания с приложениями к задачам обработки навигационной информации. СПб: ЦНИИ „Электроприбор“, 2009. 496 с.
Олег Андреевич Степанов Антон Борисович Торопов
Сведения об авторах — д-р техн. наук; Санкт-Петербургский государственный университет
информационных технологий, механики и оптики, кафедра информационно-навигационных систем; E-mail: ostepanov@eprib.ru — ЦНИИ „Электроприбор“, Санкт-Петербург; научный сотрудник; E-mail: toropov_a@mail.ru
Рекомендована кафедрой информационно-навигационных систем
Поступила в редакцию 07.05.10 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 10
49
УДК 621.391.172
О. А. СТЕПАНОВ, А. Б. ТОРОПОВ
ИСПОЛЬЗОВАНИЕ ПОСЛЕДОВАТЕЛЬНЫХ МЕТОДОВ МОНТЕ-КАРЛО В ЗАДАЧЕ КОРРЕЛЯЦИОННО-ЭКСТРЕМАЛЬНОЙ НАВИГАЦИИ
Исследуется возможность применения последовательных методов МонтеКарло в задаче корреляционно-экстремальной навигации при учете изменчивости оцениваемого вектора. Обсуждаются особенности применения таких методов и предлагается алгоритм, основанный на апостериорной (повторной) существенной выборке.
Ключевые слова: метод Монте-Карло, фильтрация, точность, навигация.
Введение. В последнее время значительное развитие получили рекуррентные алгоритмы решения задач нелинейной фильтрации, основанные на последовательных методах Монте-Карло. К ним, в частности, относятся парциальные фильтры (particle filtres), бутстрэп (bootstrap) фильтры и ряд их модификаций [1—3]. В настоящей работе исследуется возможность применения аналогичных алгоритмов в задаче корреляционно-экстремальной навигации. Особенность этой задачи заключается в ее нелинейном и протяженном во времени характере, что обусловливает необходимость учета изменчивости оцениваемого вектора. Обычно такой учет осуществляется путем сведения исходной нелинейной задачи к некоторому линейному аналогу [4], что при определенных условиях приводит к снижению точности решения. В настоящей работе предлагается учитывать изменчивость в рамках нелинейной постановки задачи при ее решении с использованием последовательных методов Монте-Карло.
Постановка задачи корреляционно-экстремальной навигации. Задача корреляционно-экстремальной навигации может быть сформулирована следующим образом [4]. Пусть известны значения параметров ϕ i , λ i некоторой навигационной системы в i -е моменты времени
ϕ i = ϕi + ∆ϕi , λ i = λi + ∆λi ,
(1)
где ϕi , λi — истинные координаты объекта; ∆ϕi , ∆λi — погрешность определения координат. Предположим, что имеются скалярные измеренные параметры некоторого геофизиче-
ского поля, например, рельефа дна:
yi = ψ(ϕi , λi ) + χ + vi , i =1, m ,
(2)
где ψ(ϕi , λi ) — известная функция, описывающая зависимость рельефа (глубин) дна от координат; χ и vi — систематическая и флуктуационная составляющие ошибок измерений. Введем
функцию ψ(ϕi , λi ) = ψ(ϕ i − ∆ϕi , λ i − ∆λi ) = si (∆ϕi , ∆λi ) и векторы θi =[∆ϕi ∆λi ]T и
xTi = ⎡⎣χ
θTi
⎤ ⎦
.
Тогда,
используя
модель
для
вектора
xi
,
задачу
корреляционно-экстремальной
навигации можно сформулировать как задачу фильтрации вектора
xi = Φi xi−1 + Γi wi
(3)
с использованием результатов измерений
yi = si (θi ) + χ + vi ,
(4)
где wi — вектор шумов; Φi , Γi — известные матрицы. Будем полагать, что wi и vi
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 10
50 О. А. Степанов, А. Б. Торопов
представляют собой центрированные гауссовы, дискретные, белые шумы с матрицей ковариации Q и дисперсией R . Вектор начальных условий x0 также полагаем центрированным гауссовым с известной матрицей ковариаций Px0 .
Суть задачи фильтрации заключается в следующем. Располагая накопленными к текущему моменту времени i результатами измерений Yi =[y1T , yT2 , ..., yTi ]T , необходимо найти алгоритм вычисления оптимальных по среднему квадратическому отклонению (СКО) оценок xˆ i (Yi ) по-
{ }следовательности (3), минимизирующих критерий Ji = M (xi − xˆi (Yi ))T (xi − xˆ i (Yi )) , и соот-
ветствующую матрицу ковариаций их ошибок. Известно, что это может быть сделано с помощью следующих выражений [4]:
∫ ∫xˆiopt (Yi ) = xi f ( Xi / Yi ) dXi , Piopt (Yi ) = (xi − xˆ i (Yi ))(xi − xˆ i (Yi ))T f (Xi / Yi )dXi , (5)
в которых f (Xi / Yi ) — апостериорная функция плотности распределения вероятности для
составного вектора Xi = ⎣⎡x1T , ..., xTi ⎤⎦T . Таким образом, задача корреляционно-экстремальной
навигации в предложенной постановке сводится к вычислению интегралов (5). Для ее реше-
ния разработаны эффективные алгоритмы для случая, когда порождающие шумы отсутству-
ют, а матрица Φi — единичная. Если оцениваемый вектор изменчивый, то для вычисления
интегралов можно использовать последовательные методы Монте-Карло.
В дальнейшем рассматривается простейший случай, когда считается, что матрица Φi
также
единичная,
wi
—
двумерные
векторы,
матрица
ΓTi
=
⎡0 ⎢⎣0
1 0
0⎤ 1⎦⎥
,
т.е.
считается,
что
ошибки θi описываются винеровскими последовательностями.
Простейший последовательный метод Монте-Карло. Запишем выражение для апо-
стериорной плотности распределения вероятности в виде
∫f (Xi / Yi ) =
f (Yi / Xi ) f (Xi ) , f (Yi / Xi ) f (Xi )dXi
где f (Yi / Xi ) — функции правдоподобия, f (Xi ) — априорная плотность распределения ве-
роятности составного вектора.
Предположим, что имеется Xij — выборка случайных векторов, соответствующих
f (Xi ) , тогда оценка и матрица ковариаций (5) могут быть вычислены с помощью метода
Монте-Карло. В результате получим формулы [4]
∑ ∑ ( )( )xˆ i (Yi ) ≈ xˆ iMC (Yi ) = L qij xij , Pi (Yi ) ≈ PiMC (Yi ) = L qij xij − xˆ iMC (Yi ) xij − xˆ iMC (Yi ) T , (6) j=1 j=1
где qij — нормированные веса, определяемые как
∑qij = qij L qij , j =1
(7)
( )qij = f Yi / Xij — ненормированные веса. Формулы (6) и (7) могут быть получены, если по-
лагать, что для функции f (Xi ) используется аппроксимация в виде [5]:
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 10
Использование последовательных методов Монте-Карло в навигации
51
( )∑f
(Xi ) ≈
1 L
L
δ
j =1
Xi − Xij
,
(8)
где δ(•) — многомерная дельта-функция. Соответственно плотность распределения вероят-
ности f (Xi / Yi ) может быть записана как
( )∑f (Xi / Yi ) ≈ L qij δ Xi − Xij . j =1
(9)
Отличительная особенность приведенных выше соотношений заключается в том, что
ненормированные веса могут вычисляться с помощью рекуррентных соотношений
qij = f (yi / xij )qij−1, qij−1 = f (Yi−1 / Xij−1) ,
(10)
поскольку f (Yi / Xij ) = f (yi / Yi−1, Xij ) f (Yi−1 / Xij ) = f (yi / xij ) f (Yi−1 / Xij−1) . Входящая в это
выражение функция f (yi / xij ) легко вычисляется с использованием выражения (4). Для вычисления выражения (9) необходимо промоделировать L выборок случайных
векторов в соответствии с функцией f (Xi ) . Такие выборки могут быть получены рекуррент-
но с использованием
X
j i −1
и соотношений
(3).
Однако анализ выражения (10) показывает, что для вычисления оценки и матрицы ко-
вариаций
(6)
на
каждом
шаге
достаточно
иметь
только
выборки
xj i−1
,
с использованием
кото-
рых формируется выборка Xij , j =1, L . Таким образом, становится очевидным, что на каж-
дом i -м шаге нет необходимости хранить в памяти всю „предысторию“, т.е. выборки Xij−2 . При использовании соотношений (6) наибольший вклад в результат вычислений оказы-
вают выборки, расположенные в областях, где апостериорная плотность существенно отлич-
на от нуля. Поскольку при использовании простейшего последовательного метода выборка
формируется в соответствии с априорной плотностью распределения вероятности f (Xi ) , то
значительное число элементов выборки этому требованию не удовлетворяет. В результате с
течением времени может возникнуть ситуация, когда значения всех весов (6) станут близки-
ми к нулю, что в полной мере проявилось при попытке применения этого метода в рассмат-
риваемой задаче корреляционно-экстремальной навигации. Эта проблема известна как про-
блема „вырождения“ алгоритма [5].
Существуют два основных метода преодоления этой проблемы: метод существенной
функции и метод апостериорной (повторной) существенной выборки [5] — в настоящей ра-
боте используем второй.
Последовательный метод Монте-Карло с апостериорной существенной выборкой.
Поясним идею применения метода апостериорной существенной выборки для решения зада-
чи фильтрации. Запишем выражение для апостериорной плотности распределения вероятно-
сти в виде
∫f (Xi /Yi ) =
f (yi /xi ) f (Xi /Yi−1) , f (yi /xi ) f (Xi /Yi−1)dXi
(11)
где f (Xi/Yi−1) — плотность прогноза. Предположим, то имеется выборка Xij , полученная в
соответствии с этой плотностью, тогда можем записать
( )∑f
( Xi
/
Yi−1 ) ≈
1 L
L
δ
j=1
Xi − Xij
.
(12)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 10
52 О. А. Степанов, А. Б. Торопов
Чтобы сформировать выборку Xij , соответствующую f (Xi/Yi ) , необходимо рассчитать [6]
µij = f (yi /xij )
(13)
[ ]и промоделировать выборку случайных величин ~x1i ... ~xiL в соответствии с дискретным
[ ]законом распределения, задаваемым множеством x1i ... xiL . Каждому элементу этого мно-
жества соответствует вероятность qij , вычисляемая по формуле (7), в которой q~ij = µij . Затем
для вычисления f (Xi+1 / Yi ) = f (xi+1 / xi ) f (Xi / Yi ) необходимо промоделировать выборку в
( )соответствии с плотностью распределения вероятности
L
∑f
xi+1 / ~xij
, которая используется
j =1
[ ]на следующем шаге для формирования ~xi1+1 ... ~xiL+1 . Описанная процедура повторяется на
каждом шаге, благодаря чему обеспечивается рекуррентный характер алгоритма фильтрации.
Эффективность применения описанной процедуры в задаче корреляционно-экстремальной
навигации проиллюстрирована на рис. 1 (а — график апостериорной плотности распределе-
ния вероятности; б — априорная выборка (серый цвет) и апостериорная выборка (черный);
в и г — изолинии апостериорной плотности на фоне априорной и апостериорной выборки
соответственно).
а) Z
б) Y
20 –2000
10 0
0
1000
2000 Y
2000
0
X 2000 2000
в) Y
г) Y
1600
1600
2000
2000
2400
2400
0 –2000 X
2800
2800
3000 2000 1000 0 –1000 X
3000 2000 1000 0 –1000 X
Рис. 1
Из представленного примера видно, что в результате применения описанной процедуры
удается сформировать выборку, соответствующую апостериорной плотности распределения
вероятности, в результате чего удается преодолеть проблему вырождения алгоритма. Бутстрэп-
фильтр (В-фильтр), использующий такую процедуру, был впервые предложен в работе [2].
Результаты моделирования. Для оценки эффективности применения В-фильтра в за-
даче корреляционно-экстремальной навигации было проведено моделирование на участках
поля рельефа с углами наклона в пределах 0—20°. Предполагалось, что информация о поле рельефа представлена в виде его значений в узлах равномерной сетки с расстояниями между
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 10
Использование последовательных методов Монте-Карло в навигации
53
узлами, равными 30 ∆ . Средние квадратические отклонения для ошибок по каждой коорди-
нате принимались равными 30 ∆ . СКО систематической составляющей погрешности выбира-
лось равным 5 ∆ . Общее число используемых измерений, выполняемых с шагом 30 ∆ , при-
нималось равным 35. СКО шума измерений составляло 0,05—2 % от среднего значения глу-
бины на участке движения. СКО порождающих шумов принималось равным 5 ∆ .
При моделировании вычислялись характеристики точности, формируемые с использо-
ванием метода статистических испытаний [7]. Число реализаций метода Монте-Карло для
расчета безусловных СКО принималось равным 1000, число реализаций L при использовании
В-фильтра равнялось 625. Результаты моделирования приведены на рис. 2 (действительные 1 и
расчетные 2 СКО оценок с использованием В-фильтра: а—в — с учетом изменчивости, г — без
учета изменчивости; а, г — ошибка по широте, б — по долготе, в — погрешность карты).
а) ∆, у.е.
а) ∆, у.е.
25
25 11
15 15
52 0
10 20 30 № измерения
40
52 0
10 20 30 № измерения
40
в) ∆, у.е.
г) ∆, у.е.
4 1
3
2
25 1 20 15 10
1 2
5 2
0 10 20 30 40 № измерения
0 10 20 30 40 № измерения
Рис. 2
С целью сопоставления на рис. 2, г приведены действительные и расчетные СКО, соответствующие В-фильтру для одной из компонент вектора состояния, когда изменчивость ошибок навигационной системы в модели не учитывалась, т.е. в условиях, когда для случая винеровских моделей расчетная модель соответствовала неизменному во времени вектору.
Из представленных результатов следует, что применение В-фильтра позволяет решать рассматриваемую задачу фильтрации в условиях изменчивости ошибок навигационной системы. Подтверждением правильности получаемых результатов, в частности, служит совпадение расчетной и действительных характеристик точности.
Выводы. Проведенные исследования подтвердили эффективность применения последовательного метода Монте-Карло, основанного на апостериорной (повторной) существенной выборке, для решения задачи корреляционно-экстремальной навигации. В дальнейшем планируется реализовать эти методы при решении задачи корреляционно-экстремальной навигации в случае, когда используется более сложная модель ошибок навигационной системы.
Работа выполнена при поддержке гранта РФФИ № 09-08-00828а.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 10
54 О. А. Степанов, А. Б. Торопов
СПИСОК ЛИТЕРАТУРЫ
1. Arulampalam S., Maskell S., and Gordon N. A Tutorial on Particle Filters for on-line nonlinear/non-Gaussian Bayesian tracking. DSTO 2001, IEEE 2001.
2. Gordon N. J., Salmond D. J., and Smith A. F. M. Novel approach to nonlinear/non-Gaussian Bayesian state estimate // IEEE Proc. Pt. F. 1993. Vol. 140, N 2. P. 107—113.
3. Doucet A., de Freitas N., and Gordon N. J. Sequential Monte Carlo Methods in Practice. NY: Springer-Verlag, 2001. P. 581.
4. Степанов О. А. Применение теории нелинейной фильтрации в задачах обработки навигационной информации. СПб: ЦНИИ „Электроприбор“, 2003. 369 с.
5. Doucet A. On sequential simulation-based methods for Bayesian filtering // Technical Report CUED/FINFENG/ TR 310. Department of Engineering, Cambridge University, 1998. P. 26.
6. Smith A. F. M. and Gelfand A. E. Bayesian statistics without tears: a sampling-resampling perspective // Amer. Stat. 1992. Vol. 46. P. 84—88.
7. Степанов О. А. Основы теории оценивания с приложениями к задачам обработки навигационной информации. СПб: ЦНИИ „Электроприбор“, 2009. 496 с.
Олег Андреевич Степанов Антон Борисович Торопов
Сведения об авторах — д-р техн. наук; Санкт-Петербургский государственный университет
информационных технологий, механики и оптики, кафедра информационно-навигационных систем; E-mail: ostepanov@eprib.ru — ЦНИИ „Электроприбор“, Санкт-Петербург; научный сотрудник; E-mail: toropov_a@mail.ru
Рекомендована кафедрой информационно-навигационных систем
Поступила в редакцию 07.05.10 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 10