RUS UKR ENG
ДонНТУ> Портал магістрів ДонНТУ
Магістр ДонНТУ Порицький Олександр Валентинович

Порицький Олександр Валентинович

Факультет: Комп'ютерних наук і технологій
Спеціальність: Системне програмування

Тема випускної роботи:

Алгоритми генерації траєкторії руху рухомого об'єкта

Науковий Керівник: Красічков Олексій Олександрович

Матеріали до теми випускної роботи: Про автора

Реферат з теми випускної роботи


Зміст

  1. Вступ
  2. Математична модель руху судна
  3. Цифрова картографія
  4. Знаходження шляху до мети
  5. Висновки
  6. Список літератури

Введение

Предметом досліджень магістерської роботи є завдання створення траєкторії руху рухомого об'єкта з високою інертністю. Сучасний рівень обчислювальних пристроїв дозволяє практично без обмежень реалізовувати різні алгоритми управління рухомими об'єктами.

У даній магістерській роботі будуть розроблені принципи інтелектуальної системи прийняття рішень для вибору оптимального шляху проходження судна з одного пункту в інший і утримування корабля на згенерованій траєкторії. Дана система включає математичну модель руху судна, цифрову карту місцевості, логічну базу даних, що описує поточну ситуацію, блок формування траєкторій руху та програмне забезпечення, яке дозволяє вирішувати завдання навігації.

Актуальність теми

Тема магістерської роботи має актуальне значення, так як розвиток водного транспорту ніколи не зупиняється, і в цій галузі недостатньо кваліфікованих судноводіїв. Для підготовки капітанів кораблів вищого рівня потрібно мати велику матеріальну базу, тобто, судно для тренування, але це з точки зору економіки потребує великих коштів. Навігаційні системи, до складу яких входить пристрій генерації траєкторії руху, вирішують цю проблему, як з економічного боку, так і з боку безпеки життєдіяльності.

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

Все вищевикладене і визначає актуальність питань, що розглядаються в даній роботі.

Метою даної роботи є розробка алгоритму генерації траєкторії руху рухомого об'єкта.

Завданнями даної роботи є побудова спрощеної моделі судна, перетворення цифрової карти в вид зручний для роботи алгоритму пошуку, пошук найкращої траєкторії, протидія зовнішнім чинникам.

Наукова значимість роботи – буде розроблено алгоритм генерації траєкторії руху рухомого об'єкта.

Практична цінність результатів роботи – розроблений алгоритм можна буде використовувати на судах, для їх автоматичного руху з одного пункту в інший.

Огляд досліджень по темі в ДонНТУ

Нікітенко Станіслав Вікторович у своїй випускний роботі «Субмодуль-GPS інтегрованої навігаційної системи для річкових судів» розробив програмну модель обчислювача координат по GPS-даними з супутників.

Ганущак Надія Костянтинівна у своїй магістерській роботі «Дослідження існуючих алгоритмів вирішення транспортних задач в ГІС» вивчала три алгоритму знаходження найкоротшого шляху (алгоритм Дейкстри, алгоритм Уоршелла-Флойда і алгоритм Левіта).

Зайцев Олександр Анатолійович у своїй магістерській роботі «Дослідження методів організації розподіленої програмної системи для планування переміщення на графах» вирішив задачу про знаходження оптимального шляху на зваженому графі.

Огляд досліджень по темі у світі

У цілому робіт з навігації водного транспорту представлено не мала кількість. Найчастіше розробляються алгоритми для судноводіння якогось конкретного типу судна, тобто відома певна апріорна інформація.

Математична модель руху судна

Як відомо, у загальному випадку математична модель керованої динамічної системи описує з тим чи іншим ступенем точності зміна станів даної системи з плином часу при заданих керуючих впливах та заданих умовах функціонування системи і може бути представлена наступним чином:

S(t) = F(t, S(0), U(t), L(t), E(t)), (1)

де F – деяка векторна функція або оператор, який характеризує дану конкретну математичну модель; S(t) – сукупність параметрів, що описують стан системи в момент часу t; U(t) – керуючі впливу на систему в різні моменти часу; L(t) – функція навантаження на систему; E(t) – функція зовнішніх збурюючих впливів на систему.

Всі перераховані функції мають зовсім конкретну емпіричну інтерпретацію з точки зору предметної області, і існує можливість виміряти значення цих функцій на реальному об'єкті та порівняти поведінку реального об'єкта з моделлю. На виході математичної моделі ми маємо еволюцію модельованої системи S(t), яка може, як збігатися, так і дещо відрізнятися від еволюції реального об'єкта SЕ(t) за інших рівних умов. Модель може вважатися адекватною, якщо похибка моделі |S(t) - SЕ(t)|, виміряна в деякої вибраної метриці, не перевищує допустимих деяких меж для даного класу задач. Природно, що ні одна математична модель не може бути ідеальною через не повноти обліку зовнішніх впливів E(t), через недосконалість математичного апарату або неправильного розуміння процесів у даній системі. З іншого боку, з практичної точки зору цілком прийнятно, якщо похибка моделювання порівнянна з інструментальними похибками вимірювання параметрів реального об'єкту, так як більш високої точності відповідності моделі ми не можемо домогтися в принципі. Математичні моделі керованих динамічних систем можна класифікувати на наступні типи:

1) за охопленням можливих об'єктів моделювання:
– Моделі для однієї конкретної керованої системи;
– Моделі для деякого класу (безлічі, сімейства) таких систем. В останньому випадку математична модель має наступний вигляд:

S(t) = F(t, C, S(0), U(t), L(t), E(t)), (2)

де C - вектор постійних параметрів системи, які характеризують дану конкретну динамічну систему і відрізняють її від безлічі інших систем;

2) за сферою застосування та типами розв'язуваних завдань:
– Універсальні моделі (загального призначення);
– Спеціальні моделі – придатні лише для обмеженого кола завдань та відображають лише один з можливих режимів функціонування даної динамічної системи. Спеціальні моделі адекватні не при будь-яких реально досяжних керуючих впливах U(t) і не з будь-якого реально можливого початкового стану S(0). Однак у тих випадках, коли умови їх застосовності повністю дотримуються, спеціальні моделі мають, як правило, меншою похибкою, ніж універсальні;

3) за способом побудови – емпіричні і теоретичні;

4) з математичного опису – дискретні і безперервні, лінійні і нелінійні. У випадку з безперервними математичними моделями найбільш типовими формами їх подання є системи диференціальних рівнянь – звичайних, якщо кожен стан моделі S(t) описується вектором, або в приватних похідних, якщо кожне стан S(t) описується скалярним або векторним полем. [1]

Цифрова картографія

Чисельні методи аналізу емпіричних даних використовуються в науці та інженерних галузях ось вже більше 300 років. Якщо в інженерних галузях a priori емпіричні чисельні дані є базисом для різних побудов, роблячи їх більш економічними і простими, то в науці (особливо в науках про Землю) чисельне моделювання довго не виходило за рамки статистичної обробки та / або створення абстрактних моделей (включаючи геологічні карти). Протягом останніх тридцяти років, виключно швидкий розвиток обчислювальної техніки і пов'язаної з нею інформаційної індустрії, істотно знизили вартість процесів чисельного моделювання, одночасно збільшивши швидкість рутинних операцій в тисячі й мільйони разів. [2]

Сучасна електронна картографія складається з трьох основних елементів – цифрових карт, приймача GPS і комп'ютера з програмним забезпеченням. Електронна картографія є винятково ефективним засобом навігації. Висока автоматизація роботи штурмана і підвищення безпеки судноводіння є основними перевагами цифрових карт. [3]

Розрізняють два види цифрових карт:

Растрові електронні карти – електронні карти, картографічна інформація яких представлена у вигляді матриці, її елементами є коди кольорів картографічного зображення. Растрові електронні карти створюються шляхом сканування традиційних топографічних матеріалів або растеризації векторних цифрових моделей місцевості. Растрові матеріали можуть бути чорно-білими, півтоновими і кольоровими. Основною характеристикою растрового зображення є його щільність, вимірювана зазвичай у точках на дюйм (dpi). [4]

Мінуси цих карт:

Плюси:

Векторні електронні карти – електронні карти, картографічна інформація яких представлена у вигляді послідовності векторів. Семантична інформація у векторних електронних карт може не визначатися (відсутня). Векторні електронні карти створюються на основі автоматизованих методів (передача інформації з електронних накопичувачів геодезичних приладів) або шляхом сканування графічного зображення традиційних планів і їх подальшої векторизації. [4]

Плюси:

Мінуси:

Знаходження шляху до мети

Під пошуком шляху буде розумітися знаходження такої траєкторії, для якої будуть характерні такі риси як мінімальна відстань до цілі, мінімальні витрати, максимальна швидкість.

Задача пошуку шляху полягає в тому, що б знайти траєкторію, уздовж якої об'єкт можна провести з поточної позиції в задану. Але з умовою, що цей шлях найменший з можливих. Алгоритми пошуку шляху зазвичай працюють з графами (у математичному сенсі – об'єкт, що складається з вершин і з'єднуючих їх ребер). Тому цифрову карту, за якою буде здійснюватися пошук, треба представити у вигляді графа. Для цього береться растрова карта і кожен піксел (або група пікселів) цієї карти ставиться у відповідність з вершиною графа. Розташовані поряд вершини з'єднуються ребрами. У результаті кожна вершина (крім крайніх) з'єднана з сусідами вісьмома ребрами (чотирма ортогональними і чотирма діагональними). Граф є зваженим, так як кожне ребро зберігає вартість переходу по ньому в наступну вершину. А вершина, у свою чергу, ознака прохідності області.

Виходить, що область пошуку розділена на сітку з квадратними осередками, але це не обов'язково. Спрощення області пошуку це перший крок у пошуку шляху. При реалізації даної задачі за допомогою обчислювальної техніки граф зручно представляти в якості матриці. Тоді кожна вершина графа відповідає клітинці матриці. Для пошуку по першому найкращому збігу на графі за допомогою алгоритму А* не обхідно виконати наступне:

1) Додаємо стартову клітку у відкритий список.
2) Повторюємо наступне:
a) Шукаємо у відкритому списку клітку з найменшою вартістю F. Робимо її поточної кліткою.
b) Розміщуємо її в закритий список і видаляємо з відкритого.
c) Для кожної з сусідніх 8-ми клітин:

d) Зупиняємося якщо:

3) Зберігаємо шлях. Рухаючись тому від цільової точки, проходячи від кожної точки до її батьків до тих пір, поки не дійдемо до стартової точки. Це і буде наш шлях.

Вартість шляху F розраховується за формулою F = G + H, де

  1. G = вартість пересування з стартовою точки A до даній клітині, слідуючи знайденому шляху до цієї клітці.
  2. H = приблизна вартість пересування від даної клітини до цільової . Вона зазвичай є евристичної функцією. Причина, по якій вона так називається в тому, що це припущення. Ми дійсно не дізнаємося довжину шляху, поки не знайдемо сам шлях, тому що в процесі пошуку нам може зустрітися безліч непрохідних місць. [5]
Прімер роботи алгоритму А*

Рис.1 – Приклад роботи алгоритму А * (Анімація: об'єм – 70 КБ, палітра – 131 квітів, кількість кадрів – 6, кількість циклів повторення – 7, розмір – 362x256, затримка між кадрами – 1000 мс, затримка повтору – 1000 мс)

Часова складність алгоритму A* залежить від евристики. У гіршому разі, число вершин, досліджуваних алгоритмом, зростає експоненціально в порівнянні з довжиною оптимального шляху. Але ще більшу проблему, ніж тимчасова складність, представляють собою споживані алгоритмом ресурси пам'яті. У гіршому випадку йому доводиться пам'ятати експоненційний кількість вузлів. Для боротьби з цим було запропоновано декілька варіацій алгоритму. [6]

Висновки

У підсумку виходить приблизно наступний алгоритм управління судном:
  1. Отримуємо координати пункту призначення і завантажуємо карту місцевості.
  2. Обчислюємо своє місце розташування за допомогою глобальної системи позиціонування.
  3. За допомогою алгоритму пошуку шляху генерується траєкторія руху.
  4. Намагатися утримати судно на траєкторії, поки не буде досягнута бажана область.
  5. Якщо судно відхилилося від траєкторії на значну величину, то слід повернутися на пункт 3.

Таким чином, можна вирішити поставлене завдання.

Список літератури

  1. Юдин Ю.И., Сотников И.И. Математические модели плоскопараллельного движения судна. Классификация и критический анализ [Электронный ресурс] / Юдин Ю.И., Сотников И.И. – Мурманск, 2006. – 95 с. – Режим доступа к статье: http://vestnik.mstu.edu.ru/v09_2_n22/articles/04_sotn_f.pdf
  2. Лебедева О.А. Картографические проекции: Методическое пособие. Новосибирский учебно-методический центр по ГИС и ДЗ / Лебедева О.А. – Новосибирск, 2000. – 35 с.
  3. Картография [Электронный ресурс] – Режим доступа к статье: http://navmarine.ru/pages.php?CID=110
  4. Электронная карта [Электронный ресурс] / СПБ Техникум геодезии и картографии – Режим доступа к статье: http://www.spbtgik.ru/book/5056.htm
  5. Патрик Лестер. Алгоритм A* для новичков [Электронный ресурс] / Патрик Л.; пер. с англ. Morpher – Режим доступа к статье: http://www.policyalmanac.org/games/aStarTutorial_rus.htm
  6. Википедия. Алгоритм поиска A* [Электронный ресурс] — Режим доступа к статье: http://ru.wikipedia.org/wiki/Алгоритм_поиска_A*
  7. Википедия. Судно [Электронный ресурс] — Режим доступа к статье: http://ru.wikipedia.org/wiki/Судно
  8. Википедия. Спутниковая система навигации [Электронный ресурс] — Режим доступа к статье: http://ru.wikipedia.org/wiki/Спутниковая_навигация
  9. Dechter R., Pearl J. Generalized best-first search strategies and the optimality of A* [Электронный ресурс] / Dechter R., Pearl J. – 1985 – Режим доступа: http://portal.acm.org/citation.cfm?id=3830&coll=portal&dl=ACM
  10. Википедия. Цифровая карта [Электронный ресурс] — Режим доступа к статье: http://ru.wikipedia.org/wiki/Цифровая_карта
  11. Nygren, Ingemar. Terrain navigation for underwater vehicles [Электронный ресурс] / Nygren, Ingemar – Stockholm, 2005 — Режим доступа к статье: http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-540
  12. Skog, Isaac. Low-Cost Navigation Systems: A Study of Four Problems [Электронный ресурс] / Skog, Isaac – Stockholm, 2009 — Режим доступа к статье: http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-11736
  13. Кривошеев С.В. Особенности реализации интеллектуальных тренажерных комплексов на основе интегрированной навигационной системы [Электронный ресурс] / Кривошеев С.В. — Режим доступа к статье: http://www.nbuv.gov.ua/portal/natural/Npdntu/Pm/2008/08ksvins.pdf
  14. Кривошеев С.В., Потапенко В.А. Подходы к моделированию работы интегрированных навигационных систем для судов внутреннего и смешанного плавания //Наукові праці Донецького державного технічного університету. Серія: Інформатика, кібернетика та обчислювальна техніка, вип. 6. – Донецьк: ДонДТУ. – 1999. С.115-120.
  15. Аноприенко А.Я., Кривошеєв С.В. Информационно-программное обеспечение интегрированной навигационной системы. Збірка наукових праць міжнародної наукової конференції «Інтелектуальні системи прийняття рішень та прикладні аспекти інформаційних технології ISDMIT’2006». Т.3. Євпаторія, 2006 – с.90-93
  16. Святный В.А., Кривошеев С.В. Автоматизация судовождения на основе интегрированной навигационной системы для речных судов. Збірка наукових праць міжнародної наукової конференції «Інтелектуальні системи прийняття рішень і проблеми обчислювального інтелекту ISDMCI’2008». Т.1 (ч.2). Євпаторія, 2008 – с.60-63
ДонНТУ> Портал магістрів ДонНТУ
Про автора