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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Lee’s Algorithm. O(n ^ 2 \log n) pseudocode)
Строка 5: Строка 5:
 
|[[Файл:notShort.png|300px|thumb|right|Такой путь не самый короткий]]
 
|[[Файл:notShort.png|300px|thumb|right|Такой путь не самый короткий]]
 
|}
 
|}
Рассмотрим задачу нахождения кратчайшего пути от точки <tex> S </tex> до <tex> T </tex> с препятствиями. Для начала рассмотрим движение материальной точки, случай произвольного полигона будет [[Visibility graph и motion planning#Motion planning|позднее]]. Для нахождения можно построить [[Трапецоидная карта | трапецоидную карту]], соединить ребрами середины вертикальных сторон с центрами трапецоидов и в этом графе любым алгоритмом поиска кратчайших путей (например, алгоритмом [[Алгоритм Дейкстры|Дейкстры]] или [[Алгоритм A*|A*]]) найти путь от <tex> S </tex> до <tex> T </tex>. Но этот путь, очевидно, не будет кратчайшим.  
+
Рассмотрим задачу нахождения кратчайшего пути от точки <tex> S </tex> до <tex> T </tex> с препятствиями. Для начала рассмотрим движение материальной точки, случай произвольного полигона будет [[Visibility graph и motion planning#Motion planning|позднее]].  
  
Однако этот алгоритм обширно используется, так как трапецоидная карта дает хорошее приближение, строится за <tex> O(n \log n) </tex> и занимает <tex> O(n) </tex> памяти, в то время как точные решения в лучшем случае работают за <tex> O(n^2) </tex> и требуют <tex> O(n^2) </tex> памяти (здесь и далее <tex> n </tex> {{---}} количество всех вершин).
+
Для нахождения пути можно построить [[Трапецоидная карта | трапецоидную карту]], соединить ребрами середины вертикальных сторон трапецоидов с их центрами и в этом графе любым алгоритмом поиска кратчайших путей (например, алгоритмом [[Алгоритм Дейкстры|Дейкстры]] или [[Алгоритм A*|A*]]) найти путь от <tex> S </tex> до <tex> T </tex>. Однако, этот путь не будет абсолютно кратчайшим.
 +
 
 +
Этот алгоритм поиска пути через трапецоидную карту обширно используется, так как дает хорошее приближение, работает за <tex> O(n \log n) </tex> и занимает линейное количество памяти, в то время как точные решения в лучшем случае работают за <tex> O(n^2) </tex> времени и памяти (здесь и далее <tex> n </tex> {{---}} количество всех вершин).
 +
 
 +
Теперь рассмотрим точное решение с помощью построения графа видимости. Для этого нам потребуется лемма:
  
 
{{Лемма
 
{{Лемма
 +
|about=О кратчайшем пути
 
|statement=
 
|statement=
 
Любой кратчайший путь от <tex> S </tex> до <tex> T </tex> с полигональными препятствиями представляет собой ломаную, вершины которой {{---}} вершины полигонов.
 
Любой кратчайший путь от <tex> S </tex> до <tex> T </tex> с полигональными препятствиями представляет собой ломаную, вершины которой {{---}} вершины полигонов.
 
|proof=
 
|proof=
 
[[Файл:short.png|150px|thumb|right|Short cut]]
 
[[Файл:short.png|150px|thumb|right|Short cut]]
Пусть кратчайший путь {{---}} не ломаная. Тогда рассмотрим участок пути, где он не является прямым. По неравенству треугольника в окрестности этого участка мы сможем немного срезать. Значит этот путь не кратчайший. Противоречие, значит лемма доказана.
+
Пусть кратчайший путь {{---}} не ломаная. В таком случае, на пути существует такая точка <tex> p </tex>, которая не принадлежит ни одному прямому отрезку. Это означает, что существует <tex>\epsilon</tex>-окрестность точки <tex> p </tex>, в которую не попадает ни одно препятствие. В таком случае, подпуть, который находится внутри <tex>\epsilon</tex>-окрестности, по неравенству треугольника может быть сокращён по хорде, соединяющий точки пересечения границы <tex>\epsilon</tex>-окрестности с путем. Раз часть пути может быть уменьшена, значит и весь путь может быть уменьшен, а значит исходное предположение некорректно.
 +
}}
 +
{{Определение
 +
|definition =
 +
'''visibility graph''' {{---}} граф, вершины которого {{---}} вершины полигонов, а также <tex> S </tex> и <tex> T </tex>. Между вершинами <tex> u </tex> и <tex> v </tex> существует ребро, если из <tex> u </tex> <i> видна </i>(mutually visible) <tex> v </tex>.
 
}}
 
}}
Таким образом для нахождения точного решения определим visibility graph. Его вершины {{---}} вершины полигонов. Между вершинами <tex> u </tex> и <tex> v </tex> существует ребро, если из <tex> u </tex> <i> видна </i>(mutually visible) <tex> v </tex> (ребра полигонов тоже входят в этот граф). К множеству вершин графа нужно добавить <tex> S </tex> и <tex> T </tex>, а также ребра в видимые из них вершины полигонов. В получившемся графе опять же любым алгоритмом находим кратчайший путь. По лемме любое ребро кратчайшего пути {{---}} ребро visibility графа, так что мы нашли то, что нужно.
 
 
Чтобы уменьшить объем графа, из него можно удалить ребра, по которым точно не пройдет путь.
 
  
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
 
[[Файл:edgeToDelete.png|150px|thumb|right|Удаляем <tex> BD </tex>]]
 
[[Файл:edgeToDelete.png|150px|thumb|right|Удаляем <tex> BD </tex>]]
Если существуют вершины <tex> A, B, C </tex> одного препятствия и вершина <tex> D </tex> такая, что поворот <tex> DBA </tex> не совпадает с поворотом <tex> DBC </tex>, то ребро <tex> DB </tex> можно удалить. (См. поясняющую картинку справа)
+
Если существуют вершины <tex> A, B, C </tex> одного препятствия и вершина <tex> D </tex> такая, что поворот <tex> DBA </tex> не совпадает с поворотом <tex> DBC </tex>, то ребро <tex> DB </tex> не принадлежит кратчайшему пути и его можно удалить из графа. (См. поясняющую картинку справа)
 
|proof=
 
|proof=
 
[[Файл:edgeNotToDelete.png|200px|thumb|right|Не удаляем <tex> BS </tex>]]
 
[[Файл:edgeNotToDelete.png|200px|thumb|right|Не удаляем <tex> BS </tex>]]
 
Путь проходящий через ребро <tex> BD </tex> будет длиннее, чем через соседей точки <tex> B </tex>, так как по неравенству треугольника <tex> AB + BD < AD </tex>
 
Путь проходящий через ребро <tex> BD </tex> будет длиннее, чем через соседей точки <tex> B </tex>, так как по неравенству треугольника <tex> AB + BD < AD </tex>
 
}}
 
}}
 +
 +
По доказанным леммам любое ребро кратчайшего пути содержится в графе, таким образом для нахождения кратчайшего пути осталось найти кратчайший путь в этом графе от <tex> S </tex> до <tex> T </tex>.
 +
 
=== Построение visibility графа ===
 
=== Построение visibility графа ===
 
==== Наивный алгоритм. <tex> O(n ^ 3) </tex> ====
 
==== Наивный алгоритм. <tex> O(n ^ 3) </tex> ====

Версия 00:09, 30 апреля 2014

Visibility graph

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

Рассмотрим задачу нахождения кратчайшего пути от точки [math] S [/math] до [math] T [/math] с препятствиями. Для начала рассмотрим движение материальной точки, случай произвольного полигона будет позднее.

Для нахождения пути можно построить трапецоидную карту, соединить ребрами середины вертикальных сторон трапецоидов с их центрами и в этом графе любым алгоритмом поиска кратчайших путей (например, алгоритмом Дейкстры или A*) найти путь от [math] S [/math] до [math] T [/math]. Однако, этот путь не будет абсолютно кратчайшим.

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

Теперь рассмотрим точное решение с помощью построения графа видимости. Для этого нам потребуется лемма:

Лемма (О кратчайшем пути):
Любой кратчайший путь от [math] S [/math] до [math] T [/math] с полигональными препятствиями представляет собой ломаную, вершины которой — вершины полигонов.
Доказательство:
[math]\triangleright[/math]
Short cut
Пусть кратчайший путь — не ломаная. В таком случае, на пути существует такая точка [math] p [/math], которая не принадлежит ни одному прямому отрезку. Это означает, что существует [math]\epsilon[/math]-окрестность точки [math] p [/math], в которую не попадает ни одно препятствие. В таком случае, подпуть, который находится внутри [math]\epsilon[/math]-окрестности, по неравенству треугольника может быть сокращён по хорде, соединяющий точки пересечения границы [math]\epsilon[/math]-окрестности с путем. Раз часть пути может быть уменьшена, значит и весь путь может быть уменьшен, а значит исходное предположение некорректно.
[math]\triangleleft[/math]
Определение:
visibility graph — граф, вершины которого — вершины полигонов, а также [math] S [/math] и [math] T [/math]. Между вершинами [math] u [/math] и [math] v [/math] существует ребро, если из [math] u [/math] видна (mutually visible) [math] v [/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]

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

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

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

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

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

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

Однако можно это сделать за [math] O(n ^ 2 \log n) [/math]. Для каждой вершины найдём все видимые из неё вершины при помощи метода плоского заметания. Нам нужно решить следующую задачу: на плоскости дано множество отрезков (рёбер препятствий) и точка [math] v [/math]. Найти все концы отрезков, видимые из точки [math] v [/math]. Будем заметать плоскость вращающимся лучом с началом в точке [math] v [/math]. Статусом заметающего луча будут отрезки, которые его пересекают, упорядоченные по возрастанию расстояния от точки [math] v [/math] до точки пересечения. Точками событий будут концы отрезков. Итак, первым делом вершины [math] w \in V [/math] сортируются по углу между лучом [math] vw [/math] и вертикальной полуосью, проходящей через [math] v [/math](достаточно рассматривать только точки, которые лежат правее [math] v [/math], так как все точки левее мы уже рассмотрели). Затем происходит инициализация множества видимых вершин (по умолчанию такое множество пустое). Далее начинается заметание плоскости. В порядке сортировки вершин для каждой из них выполняется проверка: видна ли вершина [math] w [/math] из вершины [math] v [/math]. Для этого нам достаточно проверить только пересечение заметающего луча с ближайшим отрезком в статусе, т. е. эта проверка выполняется за [math] O(1) [/math]. Если вершина видима, необходимо добавить её в список видимых вершин. И, наконец, вне зависимости от видимости вершины, необходимо изменить статус заметающего луча. Для этого для текущей вершины [math] w [/math] необходимо удалить из списка текущих пересечений все рёбра (отрезки), которые заканчиваются в этой вершине (лежат слева от прямой [math] vw [/math]) и добавить все рёбра (отрезки), которые в ней начинаются (лежат справа от прямой [math] vw [/math]).

Псевдокод
void getVisibleVertexes(vertex v)
   vertexes.add(for w in V if w.x >= v.x)
   status.add(for e in E if e isHigher than v and intersects vertical line from v to infinity)
   sort status by distance
   sort vertexes by angle
   for w in vertexes
      add visiblePair (v, w) if intersection(vw, status.closest) == null
      delete from status all edges ending in w
      add in status all edges beginning in w

Вершин у нас [math] O(n) [/math], сортируем за [math] O(n \log n) [/math] плюс обновление статуса, которое суммарно выполняется за [math] O(n \log n) [/math], так как у нас [math] O(n) [/math] ребер. Итого [math] O(n^2 \log 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

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

Тут мы двигаем не точку, а произвольный выпуклый полигон. Если мы его не можем вращать, просто считаем configuration space, т. е. "обводим" препятствия нашим полигоном (делаем сумму Минковского препятствий и полигона, сдвинутого в начало координат какой-нибудь точкой) и получаем другие препятствия, но зато теперь мы двигаем точку. А это мы уже научились делать выше.

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

При такой реализации в некоторых случаях у нас может возникнуть ошибка в повороте, так как в одной плоскости мы все можем делать точно: положения на соседних слоях могут допускаться, а повернуть мы не сможем. Это лечится в основном двумя способами: измельчением угла поворота и изначальным сглаживанием углов полигона — повращать полигон на [math] +\epsilon [/math] и [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
  • Хабр