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
ДонНТУ > Портал магистров ДонНТУ
Об авторе | Библиотека | Ссылки | Отчет о поиске | | Индивидуальный раздел