„Който знае за приближаваща се опасност, той я е избегнал.“

Автоматизираните системи за управление на подводни и надводни апарати изискват специфични информационни ресурси за решаване на техните проблеми. По-специално, необходима е информация за заобикалящи ги навигационни опасности, за да се осигури безопасно маневриране. Очевидно в традиционната картографска форма той е адаптиран към човешкото възприятие и не може да се използва директно от компютърно управлявана система. Тук са необходими други форми на представяне на картографската информация, които могат да бъдат адаптирани за включване в цифров анализ от компютърни системи.

За безопасното маневриране на автоматизирано подводно превозно средство е необходима информация за заобикалящите го навигационни опасности. Цифровите карти на дъното на акваторията не са ефективен източник на данни за навигационните опасности за автоматизираните системи за управление. Първо, стойностите на дълбочината не са свързани дори с близостта на бреговата линия, например във водни зони с „дълбоко крайбрежие“, и второ, има други видове навигационни опасности, които не са свързани с формата на топографията на дъното, например потънали кораби, наводняване на зони, експлозиви и т.н. За да се определят безопасни навигационни курсове, автоматизираната система за управление изисква един източник на данни за съвкупността от навигационни опасности в района на навигация.

За решаването на този проблем се предлага да се използва една информационна структура, която да съхранява данни за най-близката навигационна опасност за всяка точка от акваторията. Прототипът на такава структура е концепцията за „изолиния на разстояние“ или „изостадия“, традиционно използвана в навигацията, която дефинира геометричното място на точките, еднакво отдалечени от точката A на разстояние D. На картата такива точки лежат на окръжност с радиусDс център в точка A (рис. 1а). Такъв кръг се нарича изостадий. В навигацията изостадиите се използват при изготвянето на карти за полагане на ветроходни курсове. В района на навигация се разграничават опасни брегове, носове и др., като спрямо тях се изграждат стадиометрични решетки или изостадиини решетки, които представляват окръжности, начертани с различни радиуси, центрирани в точките на опасност (рис. 1б).

Рис. 1. Описание на разстоянието до опасността при навигация: a – изостадиен кръг, б – стадиаметрична мрежа за наблюдения на разстоянието

Концепцията за изостадия е частен случай на концепцията за навигационен параметър. Навигационният параметър U е стойността, измерена за определяне на координатите на кораба и е функция на тези координати. По този начин навигационните параметри се измерват от плавателния съд (за да се определи местоположението му), хоризонталните ъгли между земните ориентири, пеленгите на ориентирите, разстоянията до ориентирите. Навигационният параметър образува скаларно поле на този параметър на земната повърхност и тъй като координатите на навигационните ориентири са известни, наборът от стойности на навигационния параметър определя навигационната функция:

т. е. зависимостта на навигационния параметър от φ – географската ширина и λ – дължината на местоположението на кораба.
В стереографската (локална правоъгълна) координатна система (x, y) изразът (1) има формата:

Ако фиксираме навигационния параметър U , тогава получаваме уравнението на навигационния контур:

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

Навигационният параметър се променя най-бързо в посока, която е перпендикулярна на допирателната към навигационния контур в дадена точка. С други думи, градиентът е насочен по нормата към навигационния контур. Посоката на градиента е условно взета в посока на увеличаване на навигационния параметър.
За да се изчисли максималната скорост на промяна на навигационния параметър, т.е. модулът на градиентния вектор, е необходимо да се изчисли нормалната производна на навигационната функция ????:

Тук трябва да се отбележи, че ако вземем изостадията като навигационен параметър, тогава от неговата дефиниция следва, че за изостадията ще имаме

За да решим проблема с конструирането на карти на разстоянията до най-близките навигационни опасности за автоматизирани системи за управление на подводни превозни средства, използваме обобщение на концепцията за стадиометрични мрежи (рис. 1б).
Всяка картографирана навигационна опасност има някаква форма на Ω: точка, линия или област. Навигационната опасна зона Ω има външна граница ∂Ω, която може да бъде дефинирана от плоска късогладка крива или точка. Всеки (краен) брой региони може да присъства във водната зона Ψ

Нека дефинираме (евклидовото) разстояние от някаква точка от водната площ Ψ до най-близката до нея гранична точка ∂Ω на някаква навигационна опасност Ω във формата:

където Ψ / Ω означава множеството от точки Ψ, лежащи извън областта Ω. С други думи, за всяко Ψ

Изрази (6), (7) дефинират математическа функция на разстоянието със знак или ориентирана функция на разстоянието (SDF), която определя разстоянието на дадена точка от границата на областта Ω, а знакът се определя от това дали е вътре в Ω. Функцията има отрицателни стойности за точки вътре в Ω, тя нараства, когато се приближи до границата на Ω, където функцията за разстояние със знак е нула и приема положителни стойности извън Ω (сигурно е, че вместо това може да се използва алтернативна конвенция, т.е. положителни стойности вътре в Ω и отрицателни извън).

Да дадем примери. Функцията на разстоянието от някаква точка с увеличаване на разстоянието от нулата е повърхността на конуса на въртене (рис. 2а) с върха, разположен в точката. От израз (4) следва, че ъгълът на отваряне на конуса е 90°. Функцията за разстояние за навигационна опасност под формата на кръг има формата на конус на въртене с връх в центъра на кръга, отрицателни стойности вътре в кръга, нулеви стойности по кръга и положителни стойности извън кръга (рис. 2б). Функцията за разстояние за навигационна опасност под формата на квадрат изглежда като обърната пирамида с връх в центъра на квадрата, отрицателни стойности вътре в квадрата, нулеви стойности по страните на квадрата и положителни стойности извън квадрата (рис. 2в).

Рис. 2. Графики на функция за разстояние със знак: a – за точкова опасност, б – за опасност с граница под формата на кръг с център в нула и радиус две единици, в – за опасност с граница под формата на квадрат с център нула и радиус две единици. На рисунки a и б синята равнина съответства на нулевата стойност на функцията за разстояние

Ако набор от {Ω}=1 навигационни опасности с различни форми е разположен във водната зона Ψ, тогава ще считаме стойността на функцията на разстоянието до най-близката граница на навигационната опасност като минимално разстояние от всички разстояния:

Очевидно повърхността на функцията може да бъде изключително сложна, тъй като в точка това е минималната стойност на всички. За пример рис. 3 показва графиката D(x) за две точкови навигационни опасности (сравнете тази рисунка с рисунка 1б).

Рис. 3. Графики на функция за разстояние със знак за две точкови опасности (обяснения в текст)

По този начин, ако се изгради цифрова карта на стойностите D(x) за зоната на навигация, тогава тя ще бъде доста просто анализирана от компютърната система за автоматично управление, което ще повиши безопасността на маневрирането на подводни автоматизирани превозни средства. Остава въпросът как да се изчисли такава карта от наличната картографска информация за навигационни опасности.
За да направим това, отбелязваме, че градиентът на навигационния параметър (3) и функциите (6) – (8) отговарят на уравнението:

Израз (9), който е напълно идентичен с израз (5), използван в традиционната навигация, се нарича (в този случай, изотропно) уравнение на ейконала – това е нелинейно частично диференциално уравнение, срещани при проблеми с разпространението на вълните, когато вълновото уравнение се апроксимира с помощта на полукласическото приближение. Това уравнение е получено от уравненията на Максуел и свързва вълновата оптика с геометричната оптика. В океанологията уравнението на ейконала моделира разпространението на предния фронт на вълна цунами.
По този начин, за да се изградят цифрови карти D(x) за акваторията Ψ, е необходимо да се реши уравнение (9) за дадени граници на навигационни опасности {Ω}=1 , тоест да се реши уравнението на ейконала с гранични условия:

Алгоритъмът, който комбинира изброяването на всички изчислени точки във водната зона Ψ с определяне на разстоянията от всяка гранична точка Ω, има голяма изчислителна сложност, където броят на вътрешните изчислени точки на площ е броят на граничните елементи. Въпреки това, в началото на 21-ви век бяха разработени ефективни числени методи за решаване на уравнение (9): бърз преход (fast marching method) и бързо почистване (fast sweeping method).

Обърнете внимание, че тези методи решават общото уравнение на ейконала, което се различава от (9) по това, че дясната страна не съдържа единица, а някаква скаларна функция на координатите, т.е. общото уравнение на ейконала е анизотропно. В нашия случай изотропността на израза (9) дава възможност да се опростят алгоритмите за числено решение на общото уравнение на ейконала.
Нека опишем алгоритъмът за решаване на общото уравнение на ейконала, адаптиран към израз (9) чрез метода на бързия преход. Методът за бързо почистване се различава от метода за бързо прескачане само в детайлите на изчислителния процес.

Акваторията Ψ се представя като дискретна правилна мрежа от точки (мрежа). Нека обозначим точките на мрежата на акваторията Ψ като индекси 1,2, . . . , и съответния масив от стойности на решение на уравнение (10). Да приемем, че всички граници на опасността са дигитализирани, така че вътрешната й област да е отляво по отношение на обхода на границата (рис. 4).

Рис. 4. Параметризиране на границите на навигационните опасности

Алгоритъмът за решаване на уравненията на ейконала чрез метода на бързия преход е итеративен процес на разпространение на кръгъл вълнов фронт върху решетка от вътрешни възли от всяка гранична точка Ω (рис. 4). Процесът на разпространение на фронта се извършва в дискретни последователни моменти от време, равни на членовете на естествения ред 0,1, . . . , В началния момент 0 = 0, в съответствие с граничните условия за всички точки ∂Ω, стойностите на решението са равни на нула. Последният момент съответства на момента, в който стойността се изчислява за всички точки на мрежата.

Във всеки момент > 0, всеки елемент от матрицата принадлежи към един от трите типа: „неизчислен“, „изчислен“ и „съседен“ с (изчислен). Имената на видовете говорят сами за себе си.
В момент 0 = 0, елементите Ω, съответстващи на граничните точки, очевидно са от „изчисления“ тип, тъй като те са зададени на нула, а останалите елементи са от типа „неизчислени“.

В следващия момент 1 = 1, сред „неизчислените“ елементи се идентифицират най-близките до „изчислените“ елементи и намерените елементи се присвояват на типа „съсед“. След това стойността 1 се присвоява на всички намерени „съседни“ елементи, а „съседните“ елементи се присвояват на „изчисления“ клас.
Това продължава до момента, когато всички елементи ще бъдат класифицирани като „изчислени“. Матрицата D(x) ще съдържа стойностите на разстоянието до най-близката точка от границата на навигационната опасност в единици от разстоянието на мрежата.
Разделянето на елементите на трите споменати типа е показано на рис. 5, където методът за бърз преход вече е преминал през няколко итерации, така че са представени набори от три типа елементи.

Рис. 5. Разделяне на елементи на три типа едновременно

Важна част от ефективността на алгоритъма за бърз преход е начинът, по който се съхраняват изчислените съседни стойности. За да направите това, е важно да използвате ефективна структура, тъй като при всяка итерация е необходимо да се намери най-малката стойност на тези точки. Този процес може да отнеме много дълго време, ако стойностите се съхраняват на случаен принцип. Минималната структура на купчина е много ефективен начин за съхраняване на тези стойности. Характеристика на минималната купчина е, че децата на всеки възел са по-големи или равни на самия възел. Тази функция принуждава най-малката стойност на купчинаta да бъде първият запис. Следователно, намирането на най-малката стойност за всяка итерация може да се направи много ефективно.

В компютърните науки купчината е специализирана дървовидна структура от данни, която удовлетворява свойството купчина: ако B е наследник на възел A, тогава ключ (A) ≥ ключ (B). От това следва, че елементът с най-големия ключ винаги е коренният възел на купчината, така че понякога такива купчини се наричат максимални купчини (алтернативно, ако сравнението е обърнато, най-малкият елемент винаги ще бъде коренният възел, такива купчини се наричат мин-купчини). Няма ограничение за това колко дъщерни възли има всеки възел на купчината, въпреки че на практика този брой обикновено не е повече от два. Купчината е най-ефективното изпълнение на абстрактен тип данни, наречен приоритетна опашка. Купчините са от решаващо значение в някои ефективни графични алгоритми, като алгоритъма на Дейкстра. Обърнете внимание, че алгоритъмът на Дейкстра е логическата основа за численото решение на уравнението на ейконала.
Горното ни позволява да формулираме прост метод за изчисляване на цифрови карти на разстояния до най-близките навигационни опасности за автоматизирани системи за управление на подводни превозни средства.
Вход. Векторизирани граници {Ω}, = 1,2, . . . , постоянни навигационни опасности в стереографската проекция за навигационния район Ψ. Ориентацията на границите трябва да съответства на рис. 4.

Стъпка 1. Задайте дължината на стъпката на мрежата, изчислете координатите на точките на мрежата, създайте празен масив.
Стъпка 2. Изчислете стойностите на елементите според алгоритъма за решаване на уравнението на ейконала по-горе.
Изход. Матрицата, която съдържа стойностите на разстоянието до най-близката точка от навигационната опасна граница в единици от интервала на мрежата, координатите на точките на мрежата.

Нека дадем илюстративен пример за приложението на горния метод. На рис. 6 е показана диаграма на квадратна акватория, по периметъра на която има нулева изобата, която е линейна навигационна опасност. Има четири граници на навигационните опасности във водната зона: 1 – сегмент от права линия, например хребет от камъни; 2 – кръг, например петно (набор от отличителни дълбочини); 3 – четириъгълник, например зона за депониране на земна маса; 4 – многоъгълник, например скалист праг. Стрелките на фигурата показват посоките на дигитализиране на границите на навигационните опасности. Линейният мащаб е условен.
Въз основа на тази информация беше изчислена цифрова карта на разстоянията до най-близките навигационни опасности. Резултатите са представени графично на рис. 7а, б. Цветните ленти отдясно на фигурите предават цветовото кодиране на стойностите на разстоянието в точките на мрежата. Имайте предвид, че фигурите ясно показват линиите на хребетите, които съответстват на най-отдалечените маршрути по отношение на навигационни опасности.

Рис. 6. Условна акватория и положение на границите на навигационните опасности

Рис. 7. Цифрова карта на разстоянията до най-близките навигационни опасности, показана на рис. 7: а – в двуизмерна, б – в триизмерна форма

По този начин е представен метод за конструиране на цифрови карти на разстоянията до най-близките навигационни опасности за автоматизирани системи за управление на подводни апарати. Предложеният метод е естествено обобщение на метода на стадиометричните мрежи за дистанционни наблюдения, използвани в традиционната навигационна практика. Разликата на представения метод е, че той е приложим за навигационни опасности от всякаква форма, докато стадиометричните мрежи работят само върху точкови мрежи. Описаният метод е фокусиран върху компютърни изчисления, използва знакова функция за разстояние, което позволява прилагането на изотропното уравнение на ейконала за решаване на задачата за конструиране на цифрови карти на разстоянията до най-близката навигационна опасност. Нов момент е използването на нулеви гранични условия за изграждане на цифрови карти на разстоянието. Предложен е алгоритъм за числено конструиране на цифрови карти на разстояния, базиран на алгоритъма за бърз преход.

Цифровите карти на разстоянията до най-близките навигационни опасности ще позволят на автоматизираните системи за управление на подводни превозни средства да оценяват разстоянието на превозното средство до навигационна опасност в реално време при маневриране и да избират най-отдалечените навигационни маршрути от навигационни опасности.
Предложеният метод е приложим само за постоянни навигационни опасности, но може лесно да се адаптира и използва за временни навигационни опасности.
Предложеният метод използва линеен алгоритъм за изчисление, но може да бъде написан и за паралелни изчисления. Освен това методът е описан във връзка с разделянето на акваторията с правилна мрежа от точки. Няма пречки за използването на произволни системи от точки, които запълват акваторията.

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