Visibility graph и motion planning — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Motion planning)
(Motion planning)
Строка 112: Строка 112:
 
Рассмотрим задачу нахождения кратчайшиго пути, когда движимый объект {{---}} это выпуклый полигон. Например, робот, которого надо доставить из начальной в конечную точку.
 
Рассмотрим задачу нахождения кратчайшиго пути, когда движимый объект {{---}} это выпуклый полигон. Например, робот, которого надо доставить из начальной в конечную точку.
  
Если полигон вращать нельзя, задача сводится к движению точки. Выбирается точка на полигоне, которая принимается за начало координат. В такой системе координат для каждого препятствия считается [[Сумма Минковского (определение, вычисление)|сумма Минковского]] с полигоном. Получаются бОльшие препятствия, но теперь достаточно двигать точку, что было описано выше.
+
Если полигон вращать нельзя, задачу сводится к движению точки так : выбирается точка на полигоне, которая принимается за начало координат. В такой системе координат для каждого препятствия считается [[Сумма Минковского (определение, вычисление)|сумма Минковского]] с полигоном. Получаются бОльшие препятствия, но теперь достаточно двигать выбранную точку, что было описано выше.
  
Теперь рассмотрим случай, когда мы можем вращать полигон. Для начала построим [[Трапецоидная карта|трапецоидную карту]], как будто мы не можем вращать полигон. Теперь будем вращать полигон на малый угол, пока он не сделает полный оборот вокруг своей оси, и для каждого угла сделаем трапецоидную карту. Теперь разместим(мысленно) все карты друг над другом. Таким образом получится, что поворот на малый угол {{---}} это движение вверх/вниз между слоями. Осталось [[Пересечение многоугольников (PSLG overlaying)|попересекать]] соседние слои и добавить между ними ребра (помним что первый и последний слои одинаковы) и уже в этом графе найти путь.
+
Если полигон можно вращать, задача нахождения ''кратчайшего'' пути становится достаточно ресурсоёмка, поэтому обычно рассматривают нахождение какого-нибудь пути между конечными точками.
  
При такой реализации в некоторых случаях у нас может возникнуть ошибка в повороте, так как в одной плоскости мы все можем делать точно: положения на соседних слоях могут допускаться, а повернуть мы не сможем. Это лечится в основном двумя способами: измельчением угла поворота и изначальным сглаживанием углов полигона {{---}} повращать полигон на <tex> +\epsilon </tex> и <tex> -\epsilon </tex> и объединить с исходным, получив новый полигон.
+
Первый шаг решения этой задачи совпадает с предыдущим случаем : выберем точку и построим [[Сумма Минковского (определение, вычисление)|сумма Минковского]] препятствий с полигоном. Рассмотрим малый угол <tex> \epsilon </tex>. Представим, что поворот полигона на этот угол {{---}} это движение вверх-вниз между слоями, на каждом из которых посчитана сумма Минковского с полигоном, повернутым на этот угол.
  
Так как эта задача достаточно ресурсоемка, мы рассматриваем только наличие пути, а не нахождение кратчайшего.
+
На каждом слое построим трапецоидную карту и граф, как описано в [[Visibility graph и motion planning#Нахождение пути между точками с препятствиями|начале]]. Если [[Пересечение многоугольников (PSLG overlaying)|пересечь]] соседние слои и добавить между их графами ребра, получится один большой граф, в котором ищется кратчайший путь.
 +
 
 +
При таком подходе может возникнуть ошибка при пересечении слоев : на каждом слое состояния будут допустимые, а осуществить поворот физически будет невозможно. Обычно, эту проблему решают двумя способами : измельчением угла поворота и изначальным сглаживанием углов полигона. Первый способ повышает не только точность решения, но вычислительную сложность задачи. Второй подход практически исключает возможность нахождения пути, когда его нет, но повышает вероятность "ненахождения" пути, когда он есть.
  
 
== Источники ==
 
== Источники ==

Версия 19:28, 9 февраля 2015

Нахождение пути между точками с препятствиями

Путь с препятствиями через трапецоидную карту
Такой путь не самый короткий

Для начала рассмотрим движение материальной точки. Случай, когда размером и формой движимого объекта пренебречь нельзя, будет рассмотрен позднее.

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

Данный алгоритм работает за [math] O(n \log n) [/math] и за линейное количество памяти и идеально подходит для нахождения какого-нибудь пути между конечными вершинами. Но иногда нужно найти кратчайший путь, и этот алгоритм не подходит, хоть и дает хорошее приближение. Однако, решения нахождения кратчайшего пути в лучшем случае работают за [math] O(n^2) [/math] времени и памяти (здесь и далее [math] n [/math] — количество всех вершин).

Visibility graph

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

Для простоты рассуждений начальную и конечную вершины будем считать вершинами полигонов.

Лемма (О кратчайшем пути):
Любой кратчайший путь между двумя вершинами с полигональными препятствиями представляет собой ломаную, вершины которой — вершины полигонов.
Доказательство:
[math]\triangleright[/math]
Short cut
Пусть кратчайший путь — не ломаная. В таком случае, на пути существует такая точка [math] p [/math], которая не принадлежит ни одному прямому отрезку. Это означает, что существует [math]\epsilon[/math]-окрестность точки [math] p [/math], в которую не попадает ни одно препятствие (случай, когда точка попала на ребро рассматривается аналогично). В таком случае, подпуть, который находится внутри [math]\epsilon[/math]-окрестности, по неравенству треугольника может быть сокращён по хорде, соединяющий точки пересечения границы [math]\epsilon[/math]-окрестности с путем. Раз часть пути может быть уменьшена, значит и весь путь может быть уменьшен, а значит исходное предположение некорректно.
[math]\triangleleft[/math]
Определение:
Говорят, что вершина [math] u [/math] видна (англ. mutually visible) из [math] v [/math], если отрезок [math] uv [/math] не пересекает ни одного препятствия.


Определение:
Граф видимости (англ. visibility graph) — граф, вершины которого — вершины полигонов. Между вершинами [math] u [/math] и [math] v [/math] существует ребро, если из [math] u [/math] видна [math] v [/math].


В худшем случае в таком графе может быть [math] O(n^2) [/math] ребер. Однако по некоторым ребрам кратчайший путь точно не пройдет, и такие ребра из графа можно удалить.

Лемма:
Удаляем [math] BD [/math]
Если существуют вершины [math] A, B, C [/math] одного препятствия и вершина [math] D [/math] такая, что поворот [math] DBA [/math] не совпадает с поворотом [math] DBC [/math], то ребро [math] DB [/math] не принадлежит кратчайшему пути и его можно удалить из графа. (См. поясняющую картинку справа)
Доказательство:
[math]\triangleright[/math]
Не удаляем [math] BS [/math]
Путь проходящий через ребро [math] BD [/math] будет длиннее, чем через соседей точки [math] B [/math], так как по неравенству треугольника [math] AB + BD \lt AD [/math]
[math]\triangleleft[/math]

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

Построение visibility графа

Наивный алгоритм. [math] O(n ^ 3) [/math]

Для каждой пары вершин проверяем, можно ли добавить ребро между ними, то есть нет ли пересечений с полигонами. [math] O(n^2) [/math] пар вершин и [math] O(n) [/math] ребер, то есть [math] O(n^3) [/math].

Lee’s Algorithm. [math] O(n ^ 2 \log n) [/math]

Заметание плоскости вращающимся лучом

Однако можно это сделать за [math] O(n ^ 2 \log n) [/math]. Идея алгоритма проста : для каждой вершины найдем видимые из нее вершины. Если научиться делать это за [math] O(n \log n) [/math], задача решена, так как всего точек [math] n [/math].

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

Переформулируем задачу. Дано : точка [math] v [/math] и множество отрезков — ребер препятствий. Найти : множество концов отрезков, видимых из [math] v [/math].

Для решения этой задачи будем использовать заметающий луч с началом в точке [math] v [/math]. Его статусом будут отрезки, которые его пересекают, упорядоченные по возрастанию расстояния от точки [math] v [/math] до точки пересечения. Точками событий будут концы отрезков.

Пустим луч из рассматриваемой вершины [math] v [/math] вертикально вверх и добавим в статус все отрезки, которые он пересекает, по увеличению расстояния до них. Теперь будем рассматривать точки [math] w \in V [/math] в порядке сортировки по углу между [math] v [/math] и вертикальной полуосью [math] l [/math]. При таком обходе проверка видимости вершины будет выполняться за [math] O(1) [/math], так как достаточно проверить пересечение с отрезком, первым в статусе. Действительно, если вершина не видна, то отрезок [math] vw [/math] пересекает несколько отрезков, лежащих перед [math] w [/math], а значит и ближайший, то есть первый в статусе. В противном случае все пересекаемые лучом отрезки лежат за вершиной [math] w [/math] и пересечения отрезка [math] uw [/math] с ближайшим отрезком в статусе не будет. Вне зависимости от видимости вершины, необходимо изменить статус заметающего луча. Для этого необходимо удалить из статуса все отрезки, которые заканчиваются вершине [math] w [/math] (лежат слева от прямой [math] vw [/math]) и добавить все отрезки, которые в ней начинаются (лежат справа от прямой [math] vw [/math]).

Псевдокод
graph buildVisibilityGraph(Set<Segment> segments)
   Set<Vertex> vertices = getVertices(segments)       //получаем все вершины препятствий
   graph visibilityGraph(vertices)                    //изначально в графе только вершины
   for Vertex v in vertices                           //для каждой вершины
      for Vertex w in getVisibleVertices(v, segments) //добавляем в граф все видимые из нее вершины
         visibilityGraph.addEdge(v, w)
   return visibilityGraph

Здесь функция getVisibleVertices([math] v [/math]) возвращет все видимые из [math] v [/math] вершины и выглядит так:

vector<Vertex> getVisibleVertices(vertex v, set<segment> segments)
// Инициализируем статус
   for segment s in segments
      if intersection s and ray from v to up exists
         status.add(s)
// Инициализируем множество вершин, которые нужно рассматривать
   for point w in segments
      if w.x >= v.x
         currentVertices.add(w)
   sort(currentVertices) by angle
// Для каждой вершины проверяем, видима ли она и обновляем статус
   for w in currentVertices
      if intersection vw and status.first not exists
         answer.add(w)
      delete from status all edges ending in w
      add in status all edges beginning in w
   return answer

В качестве статуса нужно использовать структуру данных, позволяющую добавлять и удалять из нее отрезки за [math] O(\log n) [/math] и извлекать минимум за [math] O(1) [/math] или [math] O(\log n) [/math]. В этом случае достигается асимптотика [math] O(n^2 \log n) [/math], так как для каждой из [math] n [/math] точек выполняется сортировка([math] O(n \log n) [/math]), обновление статуса (суммарно [math] O(n \log n) [/math], так как каждый отрезок добавляется и удаляется из статуса только один раз) и запросы ближайшего отрезка ([math] O(\log n) [/math] или [math] O(1) [/math] на точку, то есть [math] O(n \log n) [/math] или [math] O(n) [/math]).

Обновление статуса заметающего луча
Обновление статуса заметающего луча
Обновление статуса заметающего луча

Overmars and Welzl’s Algorithm [math] O(n ^ 2) [/math]

visibility graph при помощи rotation tree

C помощью rotation tree можно достичь асимптотики [math] O(n^2) [/math].

Motion planning

Изменяем препятствия
Ищем путь для точки

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

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

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

Первый шаг решения этой задачи совпадает с предыдущим случаем : выберем точку и построим сумма Минковского препятствий с полигоном. Рассмотрим малый угол [math] \epsilon [/math]. Представим, что поворот полигона на этот угол — это движение вверх-вниз между слоями, на каждом из которых посчитана сумма Минковского с полигоном, повернутым на этот угол.

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

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

Источники

  • Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars (2008), Computational Geometry: Algorithms and Applications (3rd edition), Springer-Verlag, ISBN 978-3-540-77973-5 Chapter 15 page 324-331
  • статья про visibility graphs на academia.edu
  • Хабр

Ссылки

  • Моя реализация алгоритма за [math] O(n^2 \log n) [/math]. Далеко от идеального, но работает