|
ХЕРСОНСЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ
НГУЕН ВАН ТАМ
УДК 004.048:629.12.014
СИСТЕМА ПІДТРИМКИ ПРИЙНЯТТЯ РІШЕНЬ
ДЛЯ КЕРУВАННЯ МАНЕВРУВАННЯМ
КОРАБЛІВ І СУДЕН БЕРЕГОВОЇ ОХОРОНИ
У СКЛАДНИХ НАВІГАЦІЙНИХ УМОВАХ
05.13.06 – автоматизовані системи управління
та прогресивні інформаційні технології
Автореферат
дисертації на здобуття наукового ступеня
кандидата технічних наук
Херсон – 2005
Дисертацією є рукопис.
Робота виконана в Національному університеті кораблебудування імені адмірала Макарова Міністерства освіти і науки України.
Науковий керівник: Доктор технічних наук, професор
Рябенький Володимир Михайлович,
Національний університет кораблебудування імені адмірала Макарова, завідувач кафедри теоретичної електротехніки та електронних систем.
Офіційні опоненти: Доктор технічних наук, професор
Фісун Микола Тихонович,
Миколаївський державний гуманітарний університет імені Петра Могили, завідувач кафедри інформаційних технологій.
Доктор технічних наук, професор
Бідюк Петро Іванович,
Інститут прикладного системного аналізу при Національному технічному університеті України (КПІ), професор кафедри математичних методів системного аналізу.
Провідна установа: Харківський національний університет радіоелектроніки Міністерства
освіти і науки України, м. Харків.
Захист відбудеться " 09 " грудня 2005 р. о 15.00 годині на засіданні спеціалізованої вченої ради
Д 67.052.01 Херсонського національного технічного університету за адресою: 73008, м. Херсон-8, Бериславське шосе 24, корпус 1, ауд. 223.
З дисертацією можна ознайомитися у бібліотеці Херсонського національного технічного університету за адресою: 73008, м. Херсон-8, Бериславське шосе 24.
Автореферат розісланий " 26 " жовтня 2005 р.
Вчений секретар
спеціалізованої вченої ради Костін В.О.
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. Територія В'єтнаму вузькою смугою простягнулася на 1750 км уздовж східного узбережжя півострова Індокитаю, який омивається Південно-Китайським морем. Майже половину довжини загального кордону країни займає морський кордон. Це означає, що морські комунікації і морська економіка займає важливе місце в розвитку країни.
Крім того, В'єтнам не може зневажати явищам прибережного піратства і разом з тим контрабанди і браконьєрства в Південно-Китайському морі і у Малаккській протоці між Сінгапуром і Індонезією. (По даним Міжнародної морської організації (ИМО) в 2000р. відбулося 469 випадків піратства у всіх регіонах світового океану, що на 56% більше в порівнянні з 1999р. і в 4,5 рази вище рівня 1991р.).
Зі сказаного стає зрозумілим прагнення здійснювати надійний морський суверенітет держави. Тому проблема берегової охорони держави вимагає розвитку її сил, що передбачає поповнення кораблями і судами спеціального призначення. Причому це поповнення передбачається здійснювати сучасними і перспективними типами кораблів і суден, здатних не тільки безпечно патрулювати, але й швидко і ефективно виконувати тактичні маневри з метою перешкоди проникненню і виконанню порушниками нелегальних операцій в зоні охорони та успішному їхньому переслідуванні і затримки.
З іншого боку, збільшення числа надводних об'єктів, що маневрують, і швидкостей їхнього руху у водних акваторіях Земної кулі вимагає прискорення процесу прийняття рішення по маневруванню, а в деяких випадках екстреного виконання маневру. У зв'язку із цим до особи, що приймає рішення (ЛПР) по керуванню об'єктом, пред'являються високі вимоги відносно уваги, тактичного і стратегічного мислення. Можна сказати, що в сучасних умовах мореплавання навіть висококваліфіковані навігатори, що управляють надводними об'єктами, що маневрують, не можуть забезпечити обробку наявної інформації в максимально стислий термін. Це привело в останні роки до використання в процесі інформатизації керування маневруванням суден (у тому числі кораблів і суден берегової охорони - КБО) спеціалізованих електронних обчислювальних машин.
З вищесказаного, видно, що розробка сучасних методів і засобів, спрямованих на скорочення часу прийняття рішення в процесі маневрування, тобто розробка інформаційних технологій для систем підтримки прийняття рішення (СППР) по керуванню маневруванням кораблів і суден залишається актуальним питанням наукового дослідження.
Зв'язок роботи з науковими програмами, планами, темами підтверджується державними програмами "Розвитку океанської економіки і будівництва суден В'єтнаму", "Створення і розвиток Державної морської поліції В'єтнаму" і в рамках "Програми розвитку кораблів і суден берегової охорони В'єтнаму", які передбачають проектування і будівництво значної групи суден різного призначення, а також удосконалення їхнього оснащення.
Дисертаційна робота є складовою частиною вищесказаних програм і відповідає напрямкам досліджень державної компанії "ХІТАКО" В'єтнаму, в яких автор приймав участь як виконавець (тема дисертації рекомендована компанією в листі про напрямок дослідження здобувача). У виконані роботи роль автора полягала в удосконаленні відомих та розробці нових методів, моделей і алгоритмів СППР по керуванню маневруванням КБО.
Мета і задачі дослідження. Метою дисертаційної роботи є розробка СППР керування маневруванням кораблів і суден берегової охорони в складних навігаційних умовах.
Для досягнення поставленої мети вирішені наступні задачі:
1. На основі аналізу сучасних АСУ маневруванням кораблів і суден берегової охорони (зокрема КБО В'єтнаму) необхідно розробити концепцію підвищення швидкодії і точності керування маневруванням КБО шляхом створення СППР керування маневруванням у складних навігаційних умовах на основі застосування методів і алгоритмів штучного інтелекту;
2. Формалізувати процеси маневрування і конкретизувати характерні задачі маневрування для КБО;
3. На основі системного підходу до аналізу моделей і алгоритмів рішення задач маневрування дослідити їхні основні характеристики, розробити граф процесу керування маневруванням;
4. На основі аналізу моделей і алгоритмів пошуку оптимального шляху розробити моделі процесу керування маневруванням суден у складних навігаційних умовах;
5. Розробити структурну схему запропонованої СППР;
6. Зробити перевірку працездатності розроблених моделей у СППР за допомогою створеного програмного забезпечення.
Об'єктом дослідження є процес маневрування морських надводних об'єктів.
Предмет дослідження – маневрування при зближенні КБО в складних навігаційних умовах.
Методи дослідження. Для рішення поставлених задач у роботі використовуються методи математичної статистики (аналіз умов навігації й маневрування), метод імітаційного моделювання, методи дослідження операцій, а також метод, що базується на теорії і ідеях штучного інтелекту (розробка моделей і алгоритмів пошуку оптимального шляху при маневруванні).
Наукова новизна одержаних результатів. У результаті проведених досліджень були отримані наступні наукові результати:
1. Вперше з позиції системного підходу проведене дослідження моделей і алгоритмів штучного інтелекту для пошуку шляху на карті з метою застосування їх для вирішення задачі маневрування КБО;
2. Запропоновано модель обліку навігаційних перешкод (у вигляді цільової функції знаходження оптимального шляху) і розроблено дискретну модель вибору оптимального шляху (у вигляді навігаційного графу ), що дозволяє аналізувати ситуацію для наступного прийняття рішень;
3. Визначені і оптимізовані коефіцієнти евристичної функції h(x) для А*-алгоритму пошуку шляху;
4. Вперше запропоновано структуру СППР на основі навігаційного графу і А*-алгоритму пошуку оптимального шляху;
5. Перевірено працездатність і ефективність роботи розроблених моделей вибору шляху і вироблення рекомендації для керування маневруванням на реальних даних за допомогою пакета прикладної програми (ППП).
Наукова новизна отриманих результатів підтверджується практично повною відсутністю літератури і наукових праць, присвячених створенню СППР керування маневруванням і використанню методів теорії штучного інтелекту в моделях функціонування і проектування АСУ для КБО.
Практичне значення одержаних результатів. Отримані автором результати мають як наукове, так і практичне значення. Наукове значення результатів дисертаційної роботи полягає в тому, що задача пошуку найкоротшого шляху між двома об'єктами (крапками) є актуальною для широкого кола народногосподарських задач. До них можна віднести задачі трасування друкованих плат, задачі прокладки кабельних комунікацій, трубопроводів, навігаційні задачі і т.п. У кожному конкретному випадку ці задачі доповнюються вихідною інформацією, однак загальний алгоритм їхнього рішення залишається незмінним. Практичне значення результатів дисертаційної роботи полягає в застосуванні при розробку СППР методів і алгоритмів штучного інтелекту і дискретної моделі процесу маневрування суден. Прикладне значення результатів також полягає в створенні програмних засобів для автоматизованого керування КБО при виконанні властивих їм задач. Застосування даних засобів дає можливість істотно поліпшити ефективність експлуатації і функціонування КБО.
Особистий внесок здобувача полягає в постановці і обґрунтуванні задачі та мети дослідження. Автором проведений аналіз науково-технічної літератури, на основі якого запропоновано створити адаптовану до задач маневрування КБО СППР із застосуванням сучасних інформаційних технологій. При цьому сформульовані вимоги до програмного забезпечення і проведене узагальнення отриманих при дослідженнях результатів.
Наукові положення, висновки, рекомендації, практичні результати належать авторові і не містять результатів, які належать співавторам, разом з якими опубліковані наукові праці.
Результати обговорювалися і аналізувалися співавторами спільно.
Апробація результатів дисертації. Основні результати дисертації доповідалися і обговорювалися на V, VI і VII науково-практичних міжнародних конференціях "Інформаційні технології в освіті та управлінні" (м. Нова Каховка, 2003-2005р.), на I і II "Міжнародній науково-технічній конференції студентів, аспірантів і молодих наукових робітників" Інституту автоматики і електротехніки (ІАЕ) Національного університету кораблебудування (НУК) (м. Миколаїв, 2004-2005р.), на розширеному науково-технічному семінарі кафедри теоретичної електротехніки та електронних систем ІАЕ НУК (2005р.) і на міжкафедральних наукових семінарах професорсько-викладацького складу кафедри "Інформаційних технологій" Херсонського національного технічного університету (м. Херсон, 2004-2005р.).
Публікації. Основні результати виконаної роботи відображені в 5-ти друкованих наукових працях фахових видань, які входять у перелік ВАК України і в 1 тезі доповіді на конференції.
Структура та обсяг роботи. Дисертаційна робота складається із вступу, чотирьох розділів, висновку, списку використаних джерел та п'яти додатків. Дисертація містить 156 сторінок тексту, 58 рисунків і 5 таблиць, 116 найменувань літературних джерел. Обсяг додатків – 40 сторінок.
ОСНОВНИЙ ЗМІСТ РОБОТИ
У вступі обґрунтована актуальність теми, розкритий стан наукової задачі, теоретичне і практичне значення дисертації, сформульовані мета і основні задачі досліджень, показана наукова новизна роботи.
У першому розділі проведений аналіз стану і функціонування сучасних АСУ маневруванням на кораблях і судах (зокрема на кораблях і судах берегової охорони) і перспективи їхнього розвитку. На основі цього аналізу запропонована структурна схема АСУ для КБО, що включає в себе інтегровану систему орієнтації і навігації (ІСОН) і систему підтримки прийняття рішень (рис.1). Поставлена задача дослідження.
Рис. 1. Запропонована структурна схема АСУ для КБО (зі СППР)
Другий розділ присвячений моделям і алгоритмам рішення задач маневрування суден. Зроблено узагальнення і формулювання задач процесу маневрування, рішення характерних для КБО задач функціонування. Проведено аналіз моделей і алгоритмів рішення задачі маневрування при зближенні об'єктів (рис. 2).
Рис. 2. Системний підхід до методів рішення задачі маневрування
На основі системного підходу до аналізу моделей і алгоритмів рішення задачі маневрування запропонований граф процесу керування маневруванням КБО (рис. 3).
Рис. 3. Граф процесу керування маневруванням КБО
На рисунку 3 вершини (позиції) графу мають наступне функціонально-змістове значення:
1 – первинна обробка інформації;
2 – вторинна обробка інформації;
3 – аналіз надводної ситуації;
4 – прийняття рішення;
5 – вивід команд керування;
6 – оцінка точності маневру;
7 – корекція маневру.
(СППР/ЭКНИС) – Операторська станція
Наведено загальний випадок зближення впритул (рис. 4) з його аналітичним рішенням:
Км = Пмц ± qМО; (1)
(“+”, якщо qМО лівого борту; “–”, якщо qМО правого борту),
Рис. 4. Зближення впритул
 , (2)
 , (3)
 , (4)
де Kм – курс маневруючого; Пмц – пеленг “маневруючий – ціль”;
q і qЦ – поточні курсові кути маневруючого і цілі відповідно;
qMO і qЦО – початкові курсові кути маневруючого і цілі відповідно;
VM і VЦ – швидкості маневруючого і цілі відповідно.
Проаналізована проблема безперервного простору навігації і запропонований шлях її рішення в задачах маневрування (рис. 5). Дискретизація простору навігації і маневрування вирішена за допомогою осередків (варіант 5,б).
Рис. 5. Способи дискретизації простору навігації
Обґрунтовано підхід до рішення задачі маневрування. Після ретельного аналізу методів і алгоритмів пошуку шляху, часто використаних в інтелектуальних системах, обрані найбільш коректно працюючі алгоритми пошуку шляху на карті для подальшого порівняння. Створено підпрограми на основі цих алгоритмів. Результати їхньої роботи добре відображені на рисунку 6.
Рис. 6. Робота обраних алгоритмів штучного інтелекту:
а- випадковий пошук; б- пошук у глибину; в- пошук у ширину; г- пошук з А* (оптимальний).
Дано порівняльні параметри роботи алгоритмів (табл. 1).
Таблиця 1
Порівняльні параметри роботи алгоритмів
Виходячи із цього, був обраний алгоритм А* (Найбільш відомий з них метод, розроблений Хартом, Нільсоном і Рафаелем на основі загального методу градієнтів - докладно описаний у роботах Бондарева В.Н., Аді Ф.Г. "Штучний інтелект" і Лорьера Ж.Л. "Системи штучного інтелекту") для рішення задачі маневрування (вибору оптимального шляху). Він виражений формулою:
 , (5)
де g(S) – реальна поточна вартість ситуації S, h(S) – евристична функція, що оцінює вартість найкращої послідовності дій, що починається з S і закінчується рішенням задачі маневрування. Отже, f(S) є мірою вартості рішень, “підлеглих” ситуації S, тобто рішень, що включають ту ж підмножину вихідних дій, що і S.
Визначення евристичної складової h*(S) залежить від безлічі параметрів, що описують відносне положення маневруючого об'єкта і об'єкта маневру, таких як координати об'єктів, відстань, швидкості і напрямки руху об'єктів, пеленги і т.д.
Конкретизація застосування А*-алгоритму та опис блок-схеми його роботи для рішення задачі маневрування - вибору оптимального шляху показані на рисунку 7.
Розроблено метод оптимізації обраного А*-алгоритмом шляху для застосування в судновій навігації і маневруванні (процедура зрізання і спрощення).
Пропонований А*-алгоритмом шлях для використання стосовно до безперервного водного простору в навігаційних і маневрових цілях виглядає неоптимальним, як показано ламаною лінією №1 на рисунку 8. Для подолання цього, після побудови шляху за допомогою А*-алгоритму необхідно проводити обробку. Ця процедура є клітинним автоматом - аналогом машини Тьюринга для двомірного дискретного простору. Кінцевий результат обробки цілком задовольняє реальності навігації і керування (лінія №2 на рисунку 8).
Рис. 7. Блок-схема роботи А*-алгоритму
Рис. 8. Вихідний та спрощений шлях А*
Третій розділ присвячений розробці моделей процесу керування маневруванням. Для обліку умов маневрування були вивчені у розділі 3 гідрографічна і гідрометеорологічна характеристики району плавання. На основі цього виведена можлива зона дії КБО (вони будуть виконувати специфікаційні задачі тільки в прибережній зоні і зоні відкритого моря). Також була створена база даних за середнім значенням кліматичних і гідрологічних елементів району (табл. 2) і наведений спосіб обліку факторів, що обурюють (вітрового дрейфу і плину).
Таблиця 2
Статистика середніх значень гідрометеорологічних елементів району плавання
Розроблено модель обліку навігаційних перешкод у вигляді цільової функції знаходження оптимального шляху на основі аналізу традиційного способу пошуку навігатором шляху зближення. Цільова функція (функціонал) може бути записана в такому виді:
   ;  (6)
Умови задачі (обмеження) виражені:
   ; 
 ; r0 – припустимий радіус;
   ; 
 h0 – припустима глибина.
Метод рішення задачі: знаходження найкоротшого шляху на мережі (на замкнутому графі). Для цього спочатку ми повинні розраховувати найкоротшу відстань до попереднього вузла i плюс відстань між поточним вузлом d і попереднім вузлом i , тобто:
Si = min {ug + sid} = mini ; (7)
Після цього розраховувати функцію в цілому по формулі (6).
У випадку простої берегової лінії виконується наступний ітераційний алгоритм:
umin = u3+ u5+ u4+ u2 ; (8)
umin = u3+ u5+ min{u3 + s34 ; u5 + s54 }+ min{u1+ s12; u4+ s42 }; (9)
Якщо берегова лінія порізана, то маємо:
umin = u3+ u4+ u5+ u6 +u7 + u2 ; (10)
umin =( u1 + s13)+(u3 + s34 )+(u3 + s35 )+ min{u4 + s46 ; u5 + s56 }+
min{u5+ s57; u6+ s67 }+(u7+ s72); (11)
У випадку протоки можна записати:
umin = u3+ u4+ u5+ u6 +u7 + u2 ; (12)
umin =( u1 + s13)+(u3 + s34 )+(u3 + s35 )+ min{u4 + s46 ; u5 + s56 }+
min{u5+ s57; u6+ s67 }+(u7+ s72); (13)
Для острова:
umin = u3+ u5+ u4+ u2 ; (14)
umin =(u1 + s13)+(u3 + s35 )+ min{u3 + s34 ; u5 + s54 +
min{u4 + s42 ; u7 + s72 }; (15)
Проведений аналіз методів моделювання показав, що найбільш ефективними в нашому випадку є імітаційне моделювання, що і було прийнято в даній роботі для рішення поставлених задач.
Проаналізувавши процес маневрування КБО на основі матеріалів попереднього розділу і на основі досвіду їхнього функціонування і експлуатації запропонована дискретна модель процесу керування маневруванням КБО у вигляді навігаційного графу (рис. 9).
Рис. 9. Навігаційний граф – дискретна модель маневрування
Для пошуку крапки перехоплення був запропонований метод Ньютона. Суть цього методу в тім, що ним може бути знайдений мінімум функції n змінних F(x1 ,...,xn ) або знайдені рішення системи рівнянь виду:
Fi (x1 , x2 , ..., xn ) = 0, i = 1, ..., n (16)
Рішення даної системи еквівалентно відшуканню рівного нулю мінімуму функції:  (17)
Для знаходження мінімуму F задаємо деяке початкове наближення xi (0) (i=1,...,n) і будуємо наступні наближення по формулі:
 (18)
де напрямки vi (j) і величина кроку на j-ом кроці відповідно рівні:
Всі похідні обчислюються при xi = xi (j). Ітераційний процес триває доти, доки не буде задовольнятися умова |xi (j+1) -xi(j)|<e(i=1,...,n)або всі похідні d/dxk не стануть дорівнювати нулю.
У процедурі використовуються функції:
– F(x: array [1...n] of real): real - мінімізіруєма функція ;
– DF (i: integer; x: array [1...n] of real): real - похідні d/dxi ; DF2 (i, j: integer; x: array [1...n] of real): real - похідні d 2F/dxi dxj.
Блок-схема роботи методу Ньютона наведена на рисунку 10.
Також запропонований метод евристичних оцінок стосовно процесу маневрування (рис. 11, а–г). Прогнозування можливого маршруту об'єкта маневру буде відбуватися, опираючись на евристичні оцінки кожної із крапок навігаційного графу . Для кожного з вузлів цього графу розраховується значення евристичної функції h(x), що характеризує, наскільки ймовірно те, що об'єкт маневру у своєму шляху пройде біля цієї крапки (області карти). Ця функція складається з декількох складових і має наступний загальний вид:
h(x) = a∙ Kб + b∙ KL + c∙ Kn + d∙ Kns ; (19)
Кожна із цих складових розраховується виходячи із емпіричних міркувань щодо можливого поводження об'єкта маневру в цій ситуації, і вплив кожної з них нівелюється за допомогою коефіцієнтів.
Курсова оцінка Kб характеризує, наскільки об'єкт маневру схильний, на даний момент, повертатися на ту чи іншу гілку навігаційного графу, виходячи з її поточного курсу. Вона (Kб) розраховується в залежності від відносних величин кутів між гілками першого рівня навігаційного графу та поточним курсом об'єкта маневру. Для вузлів наступних рівнів, вона буде такою ж. Наглядно це представлено на рис. 11,а.
Рис. 10. Блок-схема роботи методу Ньютона
Оцінка найкоротшої відстані KL визначає, наскільки коротким може бути шлях від цього вузла до кінцевої мети переміщення. Логічно взяти до уваги, що об'єкт маневру схильний обрати більш короткий шлях до своєї мети. Розраховується KL у залежності від відносних величин найкоротших шляхів від вузла до кінцевої мети. Для вузла з мінімальним шляхом серед вузлів першого рівня певного вузла графу KL рівняється значенню цієї ж оцінки для верхнього за ієрархією вузла. Для вузла з максимальним серед його сусідів шляхом KL = 0 (рис. 11,б).
Рис. 11. Складові евристичної функції h(x)
Оцінка розміру дерева Kn. Якщо припустити, що об'єкт маневру обирає шлях до кінцевої мети рівноймовірно з будь-яких інших, незалежно від їхньої довжини чи інших факторів, то чим більше шляхів проходить через вузол, тим вірогіднішим буде те, що він обере гілку, що веде до цього вузла. Саме цю ймовірність і відображає оцінка Kn (рис. 11,в).
Оцінка середньої відстані Kns. Аналогічно до попередньої оцінки, об'єкт маневру може обрати шлях, що приведе до кінцевої мети по самому найкоротшому шляху, або по одному з коротких шляхів. Оцінка Kns дозволяє проявляти такі гілки графу, які приводять у середньому до менш довгих шляхів (рис. 11,г). Ця оцінка обернено пропорційна відносним величинам середньої довжини шляхів від цього вузла до мети. На відміну від оцінки Kn, об'єкт маневру все одно обирає нижній шлях (на рис. 11,г), коли Kn рекомендує верхній, і робить це незалежно від того, чи є пристань наприкінці верхнього шляху чи ні, оскільки суб'єктивно, нижнім шляхом до берега ближче.
Після підрахування складові функції h(x) і значення самої функції для кожного з вузлів навігаційного графу, ми отримаємо евристичні оцінки "перспективності" кожного з вузлів і гілок графу, які будуть зважені, як і серед сусідніх вузлів того ж рівня графу, так і вздовж кожної гілки графу.
На основі цих оцінок будуються оптимальний шлях переміщення суден і шлях перехоплення.
Четвертий розділ роботи присвячений питанню розробки СППР за допомогою обраного алгоритму і розробленої моделі. Запропоновано структуру СППР, що представлена на рисунку 12. Внутрішня структура побудови програми реалізує етапи рішення задачі у вигляді окремого автономного модуля. Вона складається з модуля генератора маршрутів (на основі А*-алгоритму), модуля сховища маршрутів, модуля навігаційного графу, модуля евристичної оцінки, і модуля висновку результатів для прийняття рішень (разом з розрахунком маршруту перехоплення).
У таблиці 3 показані порівняльні результати рішення задачі маневрування по декількох характеристиках (традиційним способом і за допомогою ППП СППР відповідно).
Таблиця 3
Порівняння способів рішення задачі маневрування
| 
