Pathfinding with voronoi

Я достиг тупика с моим университетским проектом, и я не могу найти способ решить. Проблема заключается в следующем:Pathfinding with voronoi

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

изображение ниже

Препятствия красные многоугольники и вокруг них голубые линии представляют собой сумму Минковского.
Черные точки представляют собой диаграмму ворона.
Синий ящик вокруг наружной границы

Так первый я, хотя я должен найти более близкие точки к точке старта (робот) и конечной точкой точек диаграммы Вороного. И эти точки показаны на изображении (голубые точки).

Тогда я подумал с некоторым королем алгоритма, как A *, чтобы найти путь для голубых точек, найденных выше вдоль точек voronoi, таким образом я найду самый безопасный путь.

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

Так что же вы предлагаете?

Спасибо за ваше время.

источник

2016-07-04 George P

есть ли ограничение на размер карты? – Saikios

Синий полигон вокруг препятствий - это граница. Его размеры примерно 1000х700 пикселей (зависит от размера окна). –

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

Создание черно-белое изображение, представляющее вашу карту. Он должен начинаться как весь черный.
Отдайте свои препятствия как белые.
Разбавьте изображение, используя круговой фильтр, размер вашего кругового робота.
Найдите кратчайший путь от A до B, который перемещается по черным пикселям.

источник

2016-07-07 18:52:24

Действительно классный уникальный подход. Насколько быстро это происходит на практике? Вы рассматривали графики видимости или другие традиционные методы планирования движения (RRT, PRM, Potential Fields)? – AndyG

Мне очень нравится это решение, хотя я уже решил проблему с использованием графика видимости и поиска A *. Я заинтересован, чтобы узнать, можно ли использовать аналогичный подход для вашей следующей части проблемы, которая представляет собой двумерный робот, который может вращаться. Если вы не можете рекомендовать то, что относительно легко реализовать? –

@GeorgeP Например: создайте N фильтров с разверткой-поворотным роботом для N разных оборотов для создания N навигационных изображений (по одному для каждого диапазона поворотов). С N = 8 вы создадите фильтр, который соответствует подметанию формы, представляющей ваш робот, от 0 до 45 градусов, от 45 до 90, ... от 315 до 360. Затем вы можете выполнить поиск по графу, чтобы найти путь , где вы также можете прыгать между N изображениями (что соответствует вращению робота, пересекающему кратное 45 градусов). –

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

Там, наверное, лучшее решение, но вот простой алгоритм, вы можете попробовать:

найти (или установить вручную) наибольшее расстояние между «Connected» точками, Д.
Сделайте таблицу расстояний между каждой парой точек диаграммы Вороного, где это расстояние меньше или равно D.
Подключить все пункты, начиная с более короткого расстояния за исключением того, что между ними уже существует путь меньше D (чтобы избежать ненужных небольших петель и углов резания).
Найдите ближайший к вашему роботу и ближайший пункт к месту назначения.
Запустить алгоритм кратчайшего пути на графике, который вы построили на шаге 3.

источник

2016-07-04 13:08:11 user5226582

Pathfinding with voronoi

ответ

Смежные вопросы