Решение задачи морской навигации в условиях неполноты и неопределенности исходной информации

Дешнер А. И.

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

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

Введение

Надежное навигационное обеспечение судов имеет важное значение для безопасности плавания, эффективной эксплуатации и предотвращения экологических бедствий. Особую значимость вопросы надежного, высокоточного контроля за положением судна приобретают при плавании в прибрежной зоне, на подходных путях, в узкостях, каналах и на акваториях портов. Для удовлетворения современных требований к навигационному обеспечению судоходства внедряются качественно новые средства навигации, в том числе спутниковые навигационные системы (СНС).

В настоящее время наиболее полно удовлетворяют требованиям к навигационному обеспечению судоходства СНС GPS и Глонасс. Основными достоинствами этих систем при использовании сигналов стандартной точности в штатном режиме работы являются глобальность рабочей зоны, высокие доступность, точность и надежность при непрерывности навигационных определений, а в дифференциальном режиме -возможность повышения точности и надежности навигационных определений в рабочей зоне дифференциальной подсистемы.

Вместе с тем, при использовании СНС в качестве основной навигационной системы возникает ряд проблем, в первую очередь, связанных с надежностью работы СНС в целом. При одобрении систем Глонасс и GPS в качестве компонентов Всемирной радионавигационной системы в 1996 г. Международная Морская Организация (ИМО) отметила неспособность каждой из них обеспечить в штатном режиме точность, необходимую для безопасной навигации судов на подходах к портам и в других водах, в которых свобода маневрирования ограничена. Другой отмеченный недостаток этих систем связан с их неспособностью в данное время обеспечивать оперативное оповещение потребителей о нарушениях в работе систем или их элементов, которые происходят пока довольно часто.

Одним из путей решения данной проблемы является использование резервных навигационных систем, работающих в автономном режиме без привлечения внешних средств.

Весьма перспективным для решения навигационных задач в настоящее время является использование геофизических полей Мирового океана - магнитного, гравитационного и поля глубин. При этом системы данного типа могут быть полностью автономными, а также использоваться для коррекции показаний базовой автономной навигационной системы - инерциально-навигационной или доплеровского лага.

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

Минимаксная фильтрация

Пусть движение объекта описывается линейным разностным уравнением

zi + 1=Aizi + е1, 1 = 1, Ы, = е0

при линейных измерениях

yi = Hizi + 1 = 1, Ы,

где Н^ - известные матрицы соответствующей размерности, е^ si, -неопределенные векторы

размерности т и п соответственно. Априорная неопределенность в системе и условиях ее функционирования заключена в наборе ю=со1(е^ sN), где е^со1(е0, ..., еЭД, sN=col(s1, ..., sN). Про вектор ю неизвестных параметров известно лишь, что он стеснен ограничением N . N

21К - “IБ +21К - * £ * ^,

1=0 /=1

где В^ ^ - положительно определенные матрицы, г - заданная постоянная, т^ qi - известные вектора. Множество

Г N N ]

Ег = ю: 211е - “ Ц +21 К-- * 1Ц *г г

I /=0 1=1 J

является множеством возможных значений неопределенного вектора ю.

Поставим задачу поиска оптимальной в некотором смысле оценки вектора I по данным измерений

у . При этом конкретный смысл критерия оптимальности получаемой оценки, а также точная формализация характеристик возмущений ei и ошибок измерений si определяют способ построения алгоритма оценивания. Классическим подходом является гипотеза о случайном характере ошибок измерений и возмущений с нормальной плотностью распределения и задания среднеквадратического критерия качества. При этом для систем вида (1), (2) удается получить в явном виде решение задачи оценивания вектора

состояния системы. Однако в общем случае не удается гарантировать выполнение требуемых условий, в частности, возмущения в модели (1) могут иметь неслучайную природу, а вероятностные характеристи-

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

предельные (доверительные множества). При этом оптимальная стратегия оценивания определяется как

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

Итак, по измерениям у^со1(у1, ..., уЭД требуется оценить в момент времени N+1 вектор состояния

zN+1 системы. Поиск стратегии оценивания +1 = иЫ (УN) выполняется в классе линейных

/ Ч N

иы (У Ы ) = 2 (УУ, + V,.) , 1=1

где VI - весовые матрицы фильтра, vi - векторы настройки фильтра. Требуется выбрать такие наборы (V, vi) весовых матриц V и векторов vi, I = 1, N, чтобы была минимальна наибольшая погрешность оценивания

Ф

юеБу

т.е.

D,b D,b юеЕг

Таким образом, критерий качества алгоритма оценивания является минимаксным.

Синтез минимаксного фильтра [0] приводит к рекуррентным соотношениям:

V* = vЫ+1, где ^+! = у*к - У* (Нк  Ък + )- Ък;

V* = 0, к = 1, N, Ь+1 = Ь + “, Ъ0 = 0, у = 0, N;

V* = Ук • Кк , где Ук =

+1 = I, к = N1, К к = ЛкРкИтк (с-1 + НкРк • Я[ )-1;

Рк+1 = ЛкРкЛкк + Б--1 - ЛкРкЯккКкк , Р = В-1.

Ф(К ,V ) = гХ , где X - максимальное собственное значение матрицы Рк+1 ;

€-+1

Приведенные соотношения по форме аналогичны соотношениям, определяющим классический фильтр

Калмана. Матрицы Рк в данных соотношениях не являются в общем случае ковариационными матрицами погрешностей оценивания, так как в рассматриваемой модели (1), (2) помехи е^ si являются неопре-

деленными. Оценки y(t)opt являются однозначными, несмещенными и удовлетворяют условию сходимости [0].

Использование геофизических полей

Использование фильтрации Калмана в задачах высокоточной навигации требует определения матрицы Н (в уравнениях (8)), которая может быть получена путем аппроксимации областей цифровых карт аналитическими поверхностями. При этом аппроксимация может касаться только областей неопределенности (областей возможных вариаций модельных ошибок и ошибок наблюдения) измерения у(^, лежащих на траектории движения объекта.

Существующие методы аппроксимации не обеспечивают представления ошибок восстановления исходных поверхностей. Методы, восстанавливающие поверхность непосредственно с использованием дискретного набора данных используют некоторое подмножество исходных данных и, в общем случае, менее устойчивы, и кроме того, их применение требует хранения всего исходного набора данных.

В данной работе предлагается использование интервальных сплайн-поверхностей, с помощью которых

можно не только восстанавливать исходную поверхность, но также учитывать неопределенность, возникающую при наличии ошибок измерений непосредственно геофизических полей с помощью датчиков, ошибок позиционирования при подготовке эталонных карт, а также ошибок, возникающих при преобразовании данных в определенный формат данных ЭВМ. Для представления данных предлагается использование

квадратичных однородных интервальных сплайн-поверхностей на интервале 2*,^ , где и,1 - соот-

ветственно верхняя и нижняя границы данных измерений. При этом использование сплайн-поверхностей дает следующие преимущества. Представление поверхностей с помощью сплайнов является аналитическим, что позволяет эффективное представлять вариаций параметров геофизических полей, при этом восстановление с помощью сплайна производится в любой промежуточной точке сетки без какой-либо дополнительной обработки. При этом также существенно снижаются требования к объему оперативной памяти бортовой ЭВМ, а интервальное представление данных позволяет учесть ошибки картографирования при использовании карт.

Метод использования интервальных сплайн-поверхностей для представления неопределенности аппроксимации геофизических полей был предложен в работе [0].

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

Интервальная В-сплайн-поверхность определяется как В-сплайн с интервальными коэффициентами. Пусть к - множество действительных чисел таких, что

^ , 0 * I < к + 2(М -1) ,

где к - число сплайн-коэффициентов. Тогда действительная функция / () в области | /0, $к+2(м-1)]

называется сплайном порядка М или степени М -1, если многочлен степени М -1 на каждом подынтервале ,//+^ и его первые М -р -1 производных, где р - количество контрольных узлов, непрерывны на всем интервале |/0,^+2(м-1)] . Более того, производные высших порядков /() непрерывны везде, кроме , 0 < У < к + 2(М — 1) . Вектор Т =  -^Аг+2(М-1)} называется вектором контрольных узлов и

значения • *’^г+2(М-1) называются внутренними узлами В-сплайна.

В-сплайн-поверхность определяется прямоугольным множеством контрольных точек ZІJ, 0 * I * ш-1 ,

О * у * п-1 , являющихся вершинами контрольного полиэдра Z , и двумя векторами к и Б , связанными с параметрами и и V . Для интервального В-сплайна каждая контрольная точка заменяется интервалом

ш-1 п-1

ZM, N (и, ^ = [ ZM N (и^\ ZM,N (и, ^)] = 22 ^.Ам (u)Бj,N М .

1=0 ]=0

Аналитическое восстановление карты геофизического поля из некоторого набора дискретных данных заключается в представлении области изменения данных измерений интервальной В-сплайн поверхностью. При этом для построения карты требуется предварительная обработка данных. В первую очередь выполняется сортировка данных на регулярной двумерной сетке.

Для определения вершин билинейной ограничивающей поверхности в пустых ячейках, используется линейная интерполяционная поверхность, которая строится на основе алгоритма триангуляции Делоне на известных вершинах. Общая постановка задачи триангуляции Делоне заключается в следующем. Пусть дано некоторое множество вершин (X- ,Yt) на плоскости. Требуется построить триангуляцию с использованием всех вершин, при этом углы выбираются так, чтобы они имели как можно более близкие значения. В геометрическом смысле триангуляция двойственна к диаграмме Вороного.

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

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

Для построения В-сплайн поверхности требуется задание внутренних узлов. Их количество, в принципе, может быть произвольным, ограничение состоит лишь в том, чтобы количество внутренних узлов превышало порядок поверхности. При этом целесообразно выбрать количество внутренних узлов сплайна таким образом, чтобы обеспечить определенную точность восстановления исходной поверхности. Для выделения в исходном массиве данных сегментов используем деление двумерного массива на прямоугольные области с помощью тернарного дерева. Каждая вершина тернарного дерева имеет не менее 2 и не более 4 потомков, вершина дерева представляет всю исходную прямоугольную область, а ветви дерева получаются делением прямоугольных областей на 4 подобласти. Каждому узлу дерева присваивается значение «истина» или «ложь», либо производится дальнейшее деление до получения какого-либо значения (классификация) либо по достижении заданной глубины дерева.

Общая задача заключается в построении поверхности Z = Z(х,у) , минимизирующей ошибку аппроксимации и имеющей форму согласно заданному вектору контрольных узлов, при этом интервальная В-сплайн-поверхность строится таким образом, чтобы объем, ограниченный В-сплайн-поверхностью и билинейной поверхностью, был минимальным. Определим

Z(u,v) 0 ^Zu (u,v), Zl (u,v)J

как интервальную В-сплайн поверхность, где u = Ах + B , v = Cy + D , A, B, C, D выбираются из условия u,v е [0,1] . Требуется минимизировать

11 ku kv 11 ки kv

F=J J 2 2 ZU

0 0 i=0 j=0 0 0 i=0 j=0

по Z™j , Z\ j , где к11 , kv - число внутренних узлов (количество контрольных узлов минус единица),

необходимых для каждого сегмента в параметрических направлениях u и v .

Интеграл от В-сплайн-поверхности вычисляется с помощью выражения

11 ku kv 1 ku kv

JJZZ j (u)Bj(vdudv=-, ZZ Pi, )(sj +M ) ,

0 0 i=0 j=0 1ViN i=0 j=0

где M =N=3 для двунаправленных квадратических сплайнов, откуда получаем

1 ku kv i ku kv

F=7^ZZZu

i=0 j=0 mN i=0 j=0

Полученная задача минимизации (11) с линейными ограничениями может быть решена с использованием методов линейного программирования.

Пример расчета

В качестве примера был выполнен расчет В-сплайн-поверхности двух участков морского дна, изображенных на рис. 1-2. Оба участка представлены цифровой картой на сетке размером 200х200. Было выполнено построение сплайнов для исходных карт, а также для карт, полученных использованием каждого 2-го, 3-го, 4-го и т.д. узлов исходной карты. Полученные при этом значения среднеквадратической ошибки приближения исходной поверхности G с помощью построенных таким образом сплайн-поверхностей показаны на рис. 1, 2. Из рис. 2 видно, что использование всего лишь 1,56% исходной информации позволяет получать приближение со среднеквадратической ошибкой, не превышающей 2 м.

ЛИТЕРАТУРА

1. Малышев В. В., Кибзун А. И. Анализ и синтез высокоточного управления летательными аппаратами. М.: Машиностроение, 1987. 304 с.

2. Пузырев В. А., Гостонина М. А. Алгоритмы оценивания движения летательных аппаратов // Зарубежная радиоэлектроника, 1981, № 4. С. 3-25.

3. Ржевкин В.А. Автономная навигация по картам местности // Зарубежная радиоэлектроника. 1981. №10. с.3-28.

4. Щербатюк А.Ф. Беспоисковые корреляционно-экстремальные алгоритмы коррекции местоположения объекта по изолинии поля рельефа // Сб. коррекция в навигационных системах и системах ориентации ИСЗ. - М.: Изд. МГУ. 1986. с.40-48.

5. S.T. Tuohy. Geophysical map representation, abstraction and interrogation for autonomous underwater vehicle navigation. Ph. D. thesis, Massachusetts Institute of Technology, Cambridge, Massachusetts, October 1993.