Каковы современные алгоритмы поиска пути на непрерывной карте Земли?

14

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

  • Каковы детерминированные алгоритмы для поиска морского маршрута на земном шаре?
  • Каковы их время и сложность памяти?

  • Могу ли я, например, использовать A * после преобразования карты земного шара в диаграмму со связанными многоугольниками (т. Е. Триангуляцией Делоне на сфере / эллипсоиде) и каковы другие возможные подходы?

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

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

Здесь есть интересные подтемы (торговля временем до хранения / хранение для онлайн-вычислений, предоставление немного неоптимальных маршрутов до наступления крайнего срока и т. Д.), Но они являются вспомогательными по отношению к основной проблеме.

Охотник на оленей
источник
1
@JDong - наземная навигация, в общем, следует маршрутам / дорогам, поэтому A * приходит естественно. Предварительно построенный график - это то, что я бы использовал.
Охотник на оленей
1
Ах, я пропустил критическую часть вашего вопроса: «непрерывно». В этом случае, возможно, вектор или потенциальные поля могут быть перспективными.
JDong
1
@RobLang - вопрос отредактирован.
Охотник на оленей
1
Для морского маршрута вам нужно будет принять во внимание уровень моря, ветер и поток воды. О каком корабле идет речь? OpenSeaMap предоставляет несколько маршрутов доставки. Если бы вы могли использовать эти *, это сработало бы. Я также думаю, что этот вопрос является широким для этой бета-версии.
PiTheNumber
1
Я думаю, что этот вопрос хорошо, если он просто запрашивает лучшие алгоритмы динамического поиска пути для непрерывных пространств сегодня. Я мог бы попытаться ответить на это позже сегодня после небольшого исследования.
JDong

Ответы:

7

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

Алгоритм RRT * является одним из тех, кого он описывает. Этот алгоритм генерирует дерево пространства состояний со случайными выборками и несколькими эвристиками, чтобы обеспечить выполнимость (например, избегание препятствий) и оптимальность. Подробности о RRT * можно найти в книге LaValle или на веб-сайте Sertac Karaman . Асимптотические характеристики времени и памяти описываются как O (nlogn) для обработки и O (n) для запросов. Алгоритм линейный, O (n), также в сложности пространства.

jdmartin86
источник
Проголосовал за реф. Рассмотрим возможность принятия после прочтения книги LaValle и проверки материала RRT *. Благодарность!
Охотник на оленей
4

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

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

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

Имейте это в виду, если вы приобретете армию плавательных роботов.

JDong
источник