Рус Eng Cn Перевести страницу на:  
Please select your language to translate the article


You can just close the window to don't translate
Библиотека
ваш профиль

Вернуться к содержанию

Транспортный вестник
Правильная ссылка на статью:

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

Клюева Светлана Федоровна

кандидат технических наук

Московская академия водного транспорта

115580, Россия, Московская область, г. Москва, ул. Кустанайская, 2 корп 1, кв. 7

KlIUEVA Svetlana Fedorovna

PhD in Technical Science

Educator, Moscow State Academy of Water Transport

115580, Russia, Moskovskaya oblast', g. Moscow, ul. Kustanaiskaya, 2 korp 1, kv. 7

klsvetlkl@gmail.com
Завьялов Виктор Валентинович

доктор технических наук

профессор, кафедра технических средств судовождения, Морской государственный университет им. адмирала Г.И. Невельского

690059, Россия, Приморский край, г. Владивосток, ул. Верхнепортовая, 50а

Zav'yalov Viktor Valentinovich

Doctor of Technical Science

Professor, the department of Technical Means of Ship Navigation, G.I. Nevelskoy Maritime State University

690059, Russia, Primorsky Krai, Vladivostok, Verkhneportovaya Street 50a

zavyalov@msun.ru

DOI:

10.7256/2453-8906.2017.1.21390

Дата направления статьи в редакцию:

12-12-2016


Дата публикации:

12-02-2017


Аннотация: Целью настоящей работы является исследование результатов работы алгоритма уточнения координат места судна по полю глубин морского дна на основе кластеризации исходной цифровой карты глубин. Классические методы уточнения координат в системах навигации по полю глубин основанны на сопоставлении карты заданных глубин и измеренных глубин с помощью установленных на борту дачиков глубин. Предлагаемый алгоритм в отличие от классических поисковых алгоритмов использует кластеры глубин в качестве карты заданных глубин и реализует поиск наиболее вероятных точек места судна на основе кластеризации данных. Методами исследования являются классическая теория корреляционно-экстремальных систем, и современная теория кластерного анализа. Исходные данные получены в результате натурных экспериментов. Программная модель позволяет визуально отображать результаты работы алгоритма. Графическая информация в совокупности с численными параметрами работы позволяет выполнить анализ результатов, оценить эффективность разработанных алгоритмов визуально и аналитически. Работа включает подробные рисунки представления графической информации, кластеризации исходных данных и поэтапный процесс уточнения координат места судна. Результаты работы являются новым вкладом в теорию алгоритмов систем навигации по геофизическим полям. Проведенные исследования и результаты вычислений показали эффективность применения кластерного анализа в системах навигации по глубинам морского дна.


Ключевые слова:

кластеризация, системы навигации, метрика, критерий, батиметрия, корреляционно-экстремальные системы, поле глубин, морское дно, точность, цифровая модель рельефа

УДК:

629.12.001.2

Abstract: The goal of this research is the examination of results of the work of algorithm for positioning of vessels across the depths of the seabed based on the clusterization of the initial digital seabed map. The classical methods of positioning in the marine navigation systems are based on comparison of the map of the depths and measurements using onboard depth sensors. Unlike the classical search algorithms the proposed algorithm uses depth clusters as the map, and executes the search of the most likely points of vessel location based on clusterization of data. The methods of this research is the classical theory of correlation-extreme systems alongside the modern theory of cluster analysis. The initial data were acquired in the result of pilot experiments. The computer model allows visually displaying the results of the work of algorithm. Graphic information in combination with the numerical parameters of the work allows carrying out the analysis of results, as well as visually and analytically assess the efficiency of the developed algorithm. The work contains the detailed images of graphic information, clusterization of the initial data, and stage process of clarification of coordinates of the vessel. The results of this research represent the new contribution into the theory of algorithms of the navigation systems across geophysical fields. The conducted research along with the results of calculation demonstrated the efficiency of application of the cluster analysis in navigation systems across the depths of the seabed.


Keywords:

clustering, navigation systems, metrics, criterion function, bathymetry, correlation-extreme systems, depth , seabed, accuracy , digital terrain model

Поисковые алгоритмы систем навигации по полю глубин

В поисковых корреляционно-экстремальных системах навигации(КЭСН) для каждой проверяемой гипотезы на основе измерений поля и имеющейся карты этого поля рассчитываются значения функционала, являющегося мерой схожести измеряемых и эталонных значений [1 - 6].

`R_(xy)=lim(1)/(2T) int_-T^T dotx(t)doty(t+tau)d tau , `

где `dotx(t), doty(t)` – центрированные значения случайной функции, T – время усреднения (интегрирования).

Экстремум функционала по всем гипотезам позволяет определить траекторию движения и конечное значение вектора состояния объекта. Применимы различные способы достижения экстремума. Например, «слепой» поиск, когда значение функционала рассчитываются для всех возможных дискретных значений конечного местоположения движущегося объекта [3].

Для поиска экстремума применимы также эвристические алгоритмы. Удачно найденная эвристика позволяет эффективно организовать реализацию поискового алгоритма в области максимума корреляционной функции [3, 6].

В рамках данной работы выполнена программная реализация поискового алгоритма на основе кластеризации исходной цифровой базы глубин морского дна. Алгоритм является синтезом трех алгоритмов: алгоритма оптимального последовательного поиска [4], алгоритма кластеризации исходной базы глубин морского дна [7 -10] и алгоритма уточнения координат места судна на базе кластеров и последовательного поиска.

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

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

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

Алгоритм уточнения координат места судна по полю глубин

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

navig_sist3

Рисунок 1. Основные этапы алгоритма

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

Первый этап расчетов реализует формирование кластеров глубин для исходной цифровой карты глубин — ЦКГ.

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

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

Кластеризация выполнена на базе введенной метрики, [7- 10]:

`mu_(c)=d_(p)*p_(k)(a_(i),c_(k))+d_(h)*|h_(i)-h_(c_(k))|` ,

где `d_(p),d_(h)` — вещественные коэффициенты, учитывающие величину настройки метрики к изменению глубин и расстояниям между точками ЦКГ; `p_(k)(a_(i),c_(k))` — расстояние между точками ai ЦКГ и центрами ck кластеров Ck.

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

Критерий качества кластеризации формируется на основе внутрикластерной оценки качества F0 – и оценки межкластерного качества F1 [9-11]:

`F_(0)=sum_(k)1/|C_(k)|sum_(j) mu^(2)_c(a_(j),c_(k))->min` ,

`F_(1)=1/|C_(k)|sum_(k)mu^2(c_(k),q)->max` ,

где q — центр масс всей выборки, – мера различия между центрами ck кластеров Ck , вычисляемая по формуле (2).

В результате формируются кластеры однородных областей моря. Причём для предварительного анализа больших областей глубин можно использовать «крупные кластеры» со средними величинами глубин более 500 м. Отношение коэффициентов расстояния и глубины dp/dh влияет на величину кластеров. С увеличением отношения dp/dh возрастает число кластеров, и уменьшаются размеры кластеров [7].

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

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

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

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

Далее алгоритм реализует поиск внутри каждого найденного кластера. В результате выполнения формируются возможные координаты местоположения судна для заданного момента времени.

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

`Psi(T(t),T_(0)(t))->min` , ` `

где `T_(0)` — истинная траектория движения.

Результаты программного моделирования

Вычислительный эксперимент выполнен для района «Амурского залива». Цифровая карта глубин и траектория движения судна показаны на рисунке 2.

az1

Рисунок 2. Цифровая карта глубин, траектория движения судна

Для данного района выполнена кластеризация по алгоритму, описанному выше.

Параметры кластеризации: dp=0.45; dh=0.55, число кластеров N = 29. Для расчетов выбраны отметки глубин с дискретностью 100 отсчетов. Результаты кластеризации для нерегулярной базы глубин совместно с траекторией судна приведены на рисунке 3.

az3

Рисунок 3. Кластеризация глубин на основе нерегулярной структуры данных

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

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

az55

Рисунок 4. Регулярная сетка глубин и кластеры глубин района «Амурского залива»

Параметры кластеризации: dp=0.45; dh=0.55, число кластеров N = 80. Результаты моделирования демонстрируют, что практически для каждой контрольной точки (отметки измеренных глубин по ходу движения судна) может быть найден кластер и соответственно точки наиболее вероятного места судна.

Точность вычислений зависит от подробности представления цифровой карты глубин (шага регулярной сети), точности представления координат отметок глубин на карте, масштаба карты и погрешностей измерения глубин [11].

Выводы

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

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

При этом вопросы оценки погрешностей определения координат места судна по полю глубин требует дальнейших исследований.

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

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

Библиография
1. Бочкарев А.М. Корреляционно-экстремальные системы навигации. Зарубежная радиоэлектроника. 1981. № 9. С. 28-53.
2. Красовский А.А., Белоглазов И.Н., Чигин Г.П. Теория корреляционно-экстремальных навигационных систем. М.: Наука, 1979. 448 с.
3. Красовский А.А. Справочник по теории автоматического управления / Под ред. А.А. Красовского. М.: Наука. 1987. 712 с.
4. Клюева С.Ф., Завьялов В.В. Синтез алгоритмов батиметрических систем навигации. Владивосток: Мор. гос. ун-т, 2013. 132 с.
5. Клюева С.Ф. Методы параллельной обработки данных в системе навигации по полю глубин морского дна // Евразийское научное объединение. 2016. Т. 1. № 4(16). С. 4-9.
6. Степанов О.А., Торопов А.Б. Методы нелинейной фильтрации в задаче навигации по геофизическим полям // Гироскопия и навигация. 2015. № 4(90). С. 102-125.
7. Завьялов В.В., Клюева С.Ф. Исследование параметров кластеризации в системах навигации по глубинам морского дна // Морские интеллектуальные технологии. 2016. Т. 1. № 3(33). С. 258-263.
8. Клюева С.Ф. Применение алгоритмов кластеризации в задачах навигации по глубинам морского дна // Евразийское научное объединение. 2016. Т. 1. № 4(16). С. 26-30.
9. Клюева, С.Ф. Алгоритм кластеризации цифровой карты глубин морского дна // Вестник морского государственного университета им. адм. Г.И. Невельского. Серия: Автоматическое управление, математическое моделирование и информационные технологии. Вып. 75/2016. Владивосток: МГУ им. Г.И. Невельского, 2016. С. 14-20.
10. Акмайкин Д.А., Клюева С.Ф., Салюк П.А. Результаты исследования проблемы моделирования графа маршрута судна на основе алгоритмов кластеризации // Вестник Государственного университета морского и речного флота им. адмирала С.О. Макарова. 2015. № 5 (39). C. 28-38.
11. Савиных В.П., Цветков В.Я. Геоинформационный анализ данных дистанционного зондирования. М.: Картгеоцентр-Геодезиздат, 2001. 228 с.
12. Завьялов В.В., Клюева С.Ф., Лабюк Ф.И. Анализ точности построения и использования цифровой модели дна в задачах навигации по полю глубин // Транспортное дело России. 2015. №6 (121). С. 211–214.
References
1. Bochkarev A.M. Korrelyatsionno-ekstremal'nye sistemy navigatsii. Zarubezhnaya radioelektronika. 1981. № 9. S. 28-53.
2. Krasovskii A.A., Beloglazov I.N., Chigin G.P. Teoriya korrelyatsionno-ekstremal'nykh navigatsionnykh sistem. M.: Nauka, 1979. 448 s.
3. Krasovskii A.A. Spravochnik po teorii avtomaticheskogo upravleniya / Pod red. A.A. Krasovskogo. M.: Nauka. 1987. 712 s.
4. Klyueva S.F., Zav'yalov V.V. Sintez algoritmov batimetricheskikh sistem navigatsii. Vladivostok: Mor. gos. un-t, 2013. 132 s.
5. Klyueva S.F. Metody parallel'noi obrabotki dannykh v sisteme navigatsii po polyu glubin morskogo dna // Evraziiskoe nauchnoe ob''edinenie. 2016. T. 1. № 4(16). S. 4-9.
6. Stepanov O.A., Toropov A.B. Metody nelineinoi fil'tratsii v zadache navigatsii po geofizicheskim polyam // Giroskopiya i navigatsiya. 2015. № 4(90). S. 102-125.
7. Zav'yalov V.V., Klyueva S.F. Issledovanie parametrov klasterizatsii v sistemakh navigatsii po glubinam morskogo dna // Morskie intellektual'nye tekhnologii. 2016. T. 1. № 3(33). S. 258-263.
8. Klyueva S.F. Primenenie algoritmov klasterizatsii v zadachakh navigatsii po glubinam morskogo dna // Evraziiskoe nauchnoe ob''edinenie. 2016. T. 1. № 4(16). S. 26-30.
9. Klyueva, S.F. Algoritm klasterizatsii tsifrovoi karty glubin morskogo dna // Vestnik morskogo gosudarstvennogo universiteta im. adm. G.I. Nevel'skogo. Seriya: Avtomaticheskoe upravlenie, matematicheskoe modelirovanie i informatsionnye tekhnologii. Vyp. 75/2016. Vladivostok: MGU im. G.I. Nevel'skogo, 2016. S. 14-20.
10. Akmaikin D.A., Klyueva S.F., Salyuk P.A. Rezul'taty issledovaniya problemy modelirovaniya grafa marshruta sudna na osnove algoritmov klasterizatsii // Vestnik Gosudarstvennogo universiteta morskogo i rechnogo flota im. admirala S.O. Makarova. 2015. № 5 (39). C. 28-38.
11. Savinykh V.P., Tsvetkov V.Ya. Geoinformatsionnyi analiz dannykh distantsionnogo zondirovaniya. M.: Kartgeotsentr-Geodezizdat, 2001. 228 s.
12. Zav'yalov V.V., Klyueva S.F., Labyuk F.I. Analiz tochnosti postroeniya i ispol'zovaniya tsifrovoi modeli dna v zadachakh navigatsii po polyu glubin // Transportnoe delo Rossii. 2015. №6 (121). S. 211–214.