Алгоритмы поиска пути для непрерывных карт (например, полигонов)
Я пытаюсь исследовать различные алгоритмы для короткого пути между двумя точками на плоскости с многоугольными препятствиями. Подавляющее большинство найденных мной алгоритмов используют дискретные карты (сетка, граф видимости, дорожная карта Вороного и т. Д.). В некоторых книгах (например, «Элементы робототехники» Бен-Ари или «Введение в автономных роботов» Николауса Коррелла) упоминаются непрерывные карты (например, необработанные полигональные данные), но не объясняются соответствующие алгоритмы. Они заявляют о преимуществах памяти или эффективности для нескольких простых препятствий, что может быть очень интересно для меня.
Я считаю, что должен быть умный подход с использованием геометрических вычислений (например, обнаружение пересечения) и некоторой алгоритмической парадигмы (например, ветвление и граница с наименьшими затратами), но я не хочу плохо изобретать велосипед.
Есть ли какие-либо ресурсы для алгоритмов короткого (наиболее подходящего) пути с использованием непрерывных карт или полезных ключевых слов для поиска?
Как и было предложено, я пытаюсь указать некоторые из используемых мной терминов:
Непрерывные карты (см. Рис. ) Относятся к хранению (непрерывных) действительных числовых значений геометрических фигур. Препятствие / Треугольник I. будет сохранено как: A = (3,2), B = (7,5), C = (7,2).
Дискретные карты (см. Рис. ) Относятся к подразделению на блоки (дискретизация, например, как в сеточной карте). Препятствие / Треугольник I. теперь будет храниться как индексы ячеек: (3,2), (4,2), (5,2), (6,2), (5,3), (6,3), ( 6,4) поиск пути в дискретных картах часто выполняется с помощью алгоритмов на основе графов, таких как Dijkstra или A *.
Геометрический расчет - это всего лишь расплывчатый термин, который я использую для операций вычислительной геометрии, которых я ожидал бы от алгоритма поиска пути для непрерывных карт. (например, перенос, перпендикулярное расстояние, обнаружение пересечения)
Ответы
Для «непрерывных карт», как вы это назвали, просто используйте Dijkstra на всех своих вершинах. Единственное отличие состоит в том, что при расчете расстояния между узлами необходимо проверять наличие отсечения.
Другой, более часто используемый термин для обозначения моей проблемы - это кратчайший евклидов путь (и) . Различие между алгоритмами для непрерывных карт и дискретных карт мне кажется немного неоднозначным.
Однако ближе всего к алгоритму непрерывного отображения я нашел алгоритм Митчелла для непрерывной задачи Дейкстры (или непрерывный метод Дейкстры). Этот алгоритм использует вейвлеты, которые равномерно распространяются от начальной точки. Путем «дифракции» вейвлетов они достигают участков, недоступных напрямую. Это создает карту кратчайшего пути, которая может использоваться для определения евклидова кратчайшего пути к любой точке в непрерывном конфигурационном пространстве.
Для получения дополнительной информации см .:
- «Евклидовы кратчайшие пути, точные или приближенные алгоритмы» Ф. Ли и Р. Клетте
- хорошая, но немного глючная анимация от Ивана Чена
- заявка Антона Ковшарова
Кто-то может возразить, что созданная карта кратчайшего пути - это просто еще одна дискретизация непрерывного конфигурационного пространства. Однако я полагаю, что карта кратчайшего пути - это просто результат, который можно получить, если применить алгоритм ко всему пространству конфигурации. Если требуется только кратчайший путь между двумя точками, алгоритм может остановиться после достижения целевой точки. Я по-прежнему не уверен в классификации этих алгоритмов, но это должно ответить на мой вопрос.