77221

Массовая задача построения маршрутов движения судов

Курсовая

Экономическая теория и математическое моделирование

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

Русский

2015-02-02

222.21 KB

6 чел.

2

Санкт-Петербургский государственный университет

Математико-механический факультет

Кафедра системного программирования

Массовая задача

построения маршрутов движения судов

Курсовая работа студента 444 группы

Кудасова Федора Сергеевича

Научный руководитель:

Кариженский Евгений,

аспирант кафедры информатики

математико-механического факультета.

Санкт-Петербург

2009


Оглавление

Оглавление 2

Введение 3

1. Постановка задачи 5

2. Обзор существующих решений задачи построения маршрутов 6

Метод, основанный на графе видимости 6

Алгоритм, основанный на построении графа смежности 6

Карта дорог 7

Метод потенциалов 7

Алгоритмы BUG 8

3. Алгоритм Advanced Bug 10

3.1. Предобработка 10

3.2. Квазивыпуклые оболочки 11

3.3. Алгоритм Advanced Bug 12

4. Постобработка 15

Заключение 16

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


Введение

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

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

  1.  Характеристика пространства (на плоскости, сфере, в трехмерном пространстве и т.п.)
  2.  Возможны ли изменения каких-либо характеристик задачи по мере перемещения объекта (учитывать другие движущиеся объекты)
  3.  Существенна ли форма и размер самого объекта, его скорость передвижения и другие кинематические характеристики

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

- Требования к алгоритму (ограничения по времени-памяти)

В данной работе рассматривалась следующая постановка задачи:

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

Собственно алгоритм состоит из следующих частей:

  1.  Для конкретного судна и района земной поверхности строится сечение, задающее препятствия
  2.  По сечению строится структура (Grid2L[1]), существенно снижающая затраты на определение пересечений с препятствиями
  3.  Задаются координаты начальной и конечно точек судна
  4.  По полученным данным строятся квазивыпуклые оболочки, которые, как показала практика на реальных районах, снижают затраты на обсчет пересечений при работе основного алгоритма
  5.  Строится маршрут по алгоритму Advanced BUG
  6.  Производятся локальные улучшения маршрута
  7.  Маршрут сглаживается


1. Постановка задачи

Есть часть плоскости, ограниченная некоторым достаточно большим прямоугольником (P). То, что находится за пределами этого прямоугольника – нас не интересует. Внутри него есть препятствия, представляющие из себя конечное множество полигонов, у этих полигонов отсутствуют самопересечения и пересечения друг с другом. Свободным для передвижения считается все пространство внутри исходного прямоугольника за исключением препятствий. Требуется по двум входным точкам, находящимся внутри P, получить ломаную, которая бы соединяла бы эти точки и не пересекалась бы с препятствиями, или сообщить о невозможности построения такой ломаной, если это действительно так.

Существует несколько особенностей, характерных для построения маршрутов в данной задаче:

  1.  Неравномерность препятствий, связанная с географическими характеристиками рельефа и береговой линии
  2.  Большое количество информации, характеризующей препятствия (как показывает практика на реальных районах, количество отрезков, задающих препятствия, варьируется от десятков до сотен тысяч)
  3.  Требуется обеспечить построение маршрута близкого к оптимальному по длине
  4.  Построение маршрута должно происходить в реальном времени в зависимости от требований пользователя (а не по заранее намеченному сценарию)


2. Обзор существующих решений задачи построения маршрутов

Рассмотрим существующие алгоритмы решения задачи нахождения по возможности кратчайших путей в описанном выше пространстве.

Метод, основанный на графе видимости

Этот метод подробно описан в работе [4].

Рис. 1. Редуцированный граф видимостей и его достройка (обозначена пунктиром)

Модификация этого метода, называемая сокращенным графом видимости,  позволяет уменьшить количество вершин графа и осуществить предобработку с временной сложностью T(n)=O(m+nlogn) и емкостной сложностью S(n)=O(n), где m=|EVG| – количество ребер в VG(P), а n – количество вершин в P. Достройка графа видимости осуществляется с той же асимптотической сложностью.

Алгоритм, основанный на построении графа смежности

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

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

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

Карта дорог

Неплохим методом по времени работы является метод построения карты дорог. Подробнее он описан в работе [4].

Рис. 3. Метод карты дорог.

Основным недостатком этого метода является невозможность построения оптимального по пути маршрута.

Метод потенциалов

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

  1.  Препятствия отталкивают объект, то есть при приближении к ним потенциальная энергия возрастает
  2.  Конечная точка притягивает объект, то есть при приближении к ней потенциальная энергия убывает

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

Рис. 4. Метод потенциалов.

Недостатком этого метода является наличие потенциальных ям – мест, где невозможно локальное уменьшение потенциальной энергии объекта. Данное состояние проиллюстрировано на Рис. 4. при попытке построить траекторию XZ.

Алгоритмы BUG

Методы из серии BUG [3] являются методами, ориентированными на агента, то есть мы не обладаем всей информацией о структуре пространства, а лишь его частью в окрестности нашего объекта.

Концепция алгоритмов основана на представлениях о передвижении жука. Он идет по прямой от начальной точки до конечной, если встречает препятствие – обходит его.

Эти методы, в отличие от метода потенциалов гарантированно достигаю конечной точки, если имеется такая возможность. Однако, они являются далеко не оптимальными по длине маршрута, а Bug2 требует выпуклости многоугольников, образующих препятствия. Bug1 в худшем случае находит путь длиной 1.5*P+D, где P – сумма периметров всех препятствий, а D – Евклидово расстояние между начальной и конечной точками. Bug2 работает чуть лучше, и его показатели худшего маршрута – P+D, а в среднем 0.5*P+D

Рис. 5. Методы Bug1 и Bug2.


3. Алгоритм Advanced Bug

3.1. Предобработка

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

После создания набора полигонов начинается разбиение района в структуру Grid2L . Происходит это следующим образом:

  1.  Изначально район разбивается на некоторое небольшое количество достаточно больших прямоугольников, являющихся ячейками сетки
  2.  Для каждого прямоугольника просматривается наличие в нем препятствий. Если их нет, или их мало (меньше определенного числа), то мы ничего не делаем с данной ячейкой
  3.  Если препятствий большое количество, то мы разбиваем ячейку на подсеть - несколько прямоугольников меньшего размера

Рис. 6. Пример разбиения района “Антверпен”.

Стоит отметить, что данная вспомогательная структура существенно ускоряет работу в связи с неравномерностью распределения препятствий в районе плавания. Основная их часть находится около береговой линии, при том, что в открытом море их почти нет. Эта структура позволяет за O(1) по точке найти индексы ячейки содержащей точку, а за O(L) (где L – длина отрезка) позволяет реализовать запрос на пересечение с препятствиями, а также некоторые другие полезные геометрические операции.

3.2. Квазивыпуклые оболочки

Уже после введения пользователем начальной и конечной точки существует еще одна стадия оптимизации представления препятствий – построение квазивыпуклых оболочек. Суть этого преобразования сводится к доведению полигонов-препятствий до полигонов наиболее приближенных к выпуклым, но не пересекающихся друг с другом, а также обладающим следующим свойством: если исходный полигон не пересекается с отрезком соединяющим начальную и конечную точки, то и квазивыпуклая оболочка не пересекается с ним. Рис. 7 иллюстрирует отличие квазивыпуклых оболочек от выпуклых.

Рис. 7. Препятствия, их выпуклые и квазивыпуклые оболочки.

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

Нужно обратить внимание на то, что квазивыпуклые оболочки могут существенно зависеть от начальной и конечно точек создаваемого маршрута (Рис. 8), именно поэтому они не могут быть построены на этапе предобработки.

Рис. 8. Синим цветом обозначены начальные и конечные точки маршрута, черным – препятствие, красным – его псевдовыпуклая оболочка.

3.3. Алгоритм Advanced Bug

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

Работа начинается с построения отрезка прямой, соединяющего начальную и конечную точку маршрута. Далее мы ищем пресечения этого отрезка с препятствиями. Уже на после этого этапа можно сказать – удастся ли построить маршрут или нет. При нахождении пересечений мы смотрим их количество для каждого препятствия, если у какого-то препятствия количество пресечений нечетное – мы либо входим в него, либо выходим, что невозможно.

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

Алгоритм обхода препятствия работает следующим образом:

  1.  Смотрит, есть ли заведомо ненужные точки пересечения. Такие точки пересечения обычно встречаются в препятствиях со сложной структурой, они находятся как бы “внутри” препятствия. Иллюстрацией это является Рис. 9 Лишние точки обведены красными эллипсами. Рис. 10 - результат решения проблемы Рис. 9
  2.  Далее алгоритм начинает идти параллельно в 2 стороны вдоль препятствия (по и против часовой стрелки)
  3.  В зависимости от встреченной точки пересечения, мы либо обходим препятствие, либо перемещаемся вне его к следующей точке по отрезку, являющемуся подмножеством прямой линии, соединяющей первую и последнюю точки маршрута
  4.  При обходе препятствия мы всегда рассматриваем обход его как с одной сторону, так и с другой и выбираем кратчайший обход (делается быстро из-за параметризации)
  5.  Если среди точек пересечения с одним прямоугольником мы встречаем точки пересечения с другим (Рис. 11), то для них мы вызываем алгоритм обхода препятствия рекурсивно (предварительно находим первую и последнюю точки пересечения)
  6.  Когда обходы препятствия с обеих сторон подсчитаны – мы выбираем кратчайший обход и возвращаем его в качестве результата

Рис. 9.

Рис. 10.

Рис. 11.

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

Построенная ломаная представляет из себя предварительный результат.


4. Постобработка

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

Рис. 12. Пример оптимизации.

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


Заключение

Предварительная ломаная имеет длину, не превышающую 0.5*P + D, где P – сумма периметров всех препятствий, D – расстояние между начальной до конечной точками. На самом деле при реальных условиях и с учетом постобработки эта оценка сильно снижается и часто достигается оптимальный маршрут.

Легко понять, что время и память, которую занимает предобработка, линейны относительно суммарного количества граней полигонов-препятствий.

Время работы основного алгоритма можно оценить как O(N*R), где N – количество отрезков препятствий, с которыми пересекается отрезок, соединяющий начальную и конечную точку, а R – максимальное количество вложенных объектов (Рассмотренных на Рис. 11) R – максимальная глубина рекурсии алгоритма обхода препятствия. Стоит заметить, что R не превосходит C/2, где C -  количество пересечений отрезка, соединяющего начальную и конечную точку, с препятствиями.

Лишь отчасти решенными остались вопросы, связанные с размерами судов и их кинематическими характеристиками. Как расширение маршрута до трубы, так и сглаживание возможно не всегда. Первую проблему можно решить, посчитав полигональное приближение суммы Минковского с описывающим диском судна.


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

  1.  Е.И. Жидков, «Массовая задача определения кратчайшего расстояния до многоугольников на плоскости», 2005
  2.  J.-C. Latombe, «Robot Motion Planning», Kluwer Academic Publishers, 1991
  3.  V. Lumelsky, A. Stepanov, «Path-Planning Strategies for a Point Mobile Automaton Moving Amidst Unknown Obstacles of Arbitrary Shape», Algorithmica 2:403-430, 1987 
  4.  J. O’Rourke, «Computational Geometry in C», Cambridge University Press, 1995
  5.  J. O’Rourke, «Handbook of Discrete and Computational Geometry», Ed. by J.E. Goodman, J. O’Rourke, CRC Press, 1997
  6.  M. Sharir, «Algorithmic motion planning», in «Handbook of Discrete and Computational Geometry», Ed. by J.E. Goodman, J. O’Rourke, CRC Press, 1997
  7.  Steven M. LaValle «Planning Algorithms», Cambridge University Press, 2006

 

А также другие работы, которые могут Вас заинтересовать

52783. Якщо друг у тебе є, життя радісним стає 41.5 KB
  Мета: Виховувати почуття справжньої дружби колективізму чесності щирості у відносинах відповідальності перед другом уміння допомогти у важку хвилину. Вірші про дружбу Якщо друг у тебе є 4 Якщо друг у тебе є Життя радісним стає. Разом можна все зробити Ти не зрадь його ніколи Тож без друга не прожити.
52784. Я + МЫ = Дружба 63 KB
  Все расселись по местам никому не тесно по секрету скажу вам будет интересно Упражнение Я рад с тобой общаться Дети поворачиваясь друг к другу называют товарища по имени говорят: Я рад с тобой общаться Правила работы в группе Четко и громко проговаривать все слова Активно работать Обращаться друг к другу только по имени Внимательно слушать говорящего Не...
52785. Година спілкування на тему: «Добре там жити, де вміють дружити» 76 KB
  Робота в парах Збери прислів’я Без вірного друга дорожчі від багатства. Людина без друга велика туга. Друга шукай як дерево без коріння. Людина без друга як їжа без солі.
52786. Сценарий воспитательного мероприятия «В поисках дружбы» 62.5 KB
  Нас ДРУЖБА учит жизнью рисковать В огонь и в воду за друзей идти. 2 Пират Кругом сокровища лежат Все вместе: Вперёд и прочь тревоги Ждёт где-то нас заветный клад и новые дороги 3 Пират: О капитан Вражда впереди на горизонте шхуна Дружба Что прикажете делать Ведь там же множество детей А с ними сказочных затей. С неё начинается дружба. Музыка Если с другом вышел в путь Учитель: Народная мудрость говорит Дружба великая сила.
52788. Классный час. Наши меньшие друзья 109.5 KB
  Параскевич Олененок Однажды пограничники шли из наряда на заставу. Пограничники осторожно подошли к дереву и увидали маленького олененка. Следов оленихи пограничники не обнаружили и взяли олененка с собой. Пограничники давали олененку печенье и конфеты.
52789. “ОЙ РОДЕ НАШ КРАСНИЙ, РОДЕ НАШ ПРЕКРАСНИЙ…” ВИХОВНИЙ ЗАХІД 81 KB
  Батько мати брат сестричка І всі інші члени роду – Всі належать до одного Українського народу. дійові особи: мати батько хлопчик дівчинка Дівчинка. Мати. Заходь доню будемо хліб виймати На рушник долі його викладати.
52790. Виховання духовності на уроках образотворчого мистецтва 56.5 KB
  Учитель музики: Україна – це щира пісня яка завжди була поруч з людиною у радості і смутку у праці і відпочинку. Це пісня. Сьогодні пісня у нас в гостях. Входить дівчинка в українському вбранні та виконує українську пісню Учитель образотворчого мистецтва: І полетіла пісня неозорими просторами України полями та лісами горами та полонинами містами та селами.
52791. Наш край у 1960-1980-ті роки. Дудчани: на вістрі часу і подій 77.5 KB
  Випереджувальне завдання: підготувати звіт груп про соціологічне опитування мешканців села Дудчани ХІД УРОКУ І. А що думають пересічні громадяни нашої країни зокрема села про ті часи ІІІ. Вивчення нового матеріалу Звіт про соціологічне опитування мешканців села Дудчани 1 група. У процесі облаштування ділянки біля Будинку культури та насадженні липової алеї в честь загиблих у Велику Вітчизняну війну односельчан брали участь жителі села учні школи та вчителі.