The results of computer modelling of algorithm for positioning of vessels across the depths

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

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

В поисковых корреляционно-экстремальных системах навигации(КЭСН) для каждой проверяемой гипотезы на основе измерений поля и имеющейся карты этого поля рассчитываются значения функционала, являющегося мерой схожести измеряемых и эталонных значений ^{[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.

Рисунок 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))` — расстояние между точками a_i ЦКГ и центрами c_k кластеров C_k.

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

Критерий качества кластеризации формируется на основе внутрикластерной оценки качества F₀ – и оценки межкластерного качества F₁ ^[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 — центр масс всей выборки, – мера различия между центрами c_k кластеров C_{k ,} вычисляемая по формуле (2).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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