Алгоритм Wavefront для покрытия территории - PullRequest
Новая
       6

Алгоритм Wavefront для покрытия территории

2 голосов
/ 09 октября 2011

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

Любой другой совет по различным типам алгоритма WaveFront также будет полезен.

Ответы [ 2 ]

1 голос
/ 10 октября 2011

Я посетил ваш сайт. Вы заявили, что робот может получать команды типа «Перейти к кетчену». Ну, я советую не изобретать велосипед. На самом деле, вам не нужно посещать каждую клетку или «область отверстия». Скорее, вы должны выбрать кратчайший путь к нему, а затем пройти через него.

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

Улучшенная версия Дейкстры: A * алгоритм , который в среднем занимает меньше времени.

Здесь вы можете найти примеры того, как они работают, эффективно.

EDIT:

Я снова посетил ваш сайт. Вы заявили, что вам нужен алгоритм для навигации по всей области. Ну, насколько я знаю, повторение алгоритма A * будет намного лучше. A * использует BFS, которая имеет лучшую производительность в среднем случае. Это очень эффективно по сравнению с волновым фронтом. Псевдокод выглядит следующим образом:

  • A) Найдите кратчайший путь с помощью алгоритма A * между местоположением и целью
    • B) Если нет пути к цели, укажите временное местоположение и перейдите к нему. (С вами указано, это может найти способ позже). После прибытия в временное местоположение, перейдите к шагу А.
    • C) В противном случае, если вы нашли способ, перейдите к цели.
0 голосов
/ 16 декабря 2015

В этой статье 1993 года был представлен вариант планировщика волнового фронта ванили, который обеспечивает полный охват, в дополнение к навигации от начала до цели:

A. Зелинский Р.А. Джарвис, Дж. С. Бирн, С. Юта, "Планирование путей полный охват неструктурированной среды мобильным роботом " Материалы Международной конференции по передовой робототехнике, 1993, стр. 533-538.

Также см. Следующий обзорный документ для получения дополнительных идей о планировании пути покрытия:

Enric Galceran, Marc Carreras, "Обследование по планированию пути покрытия для робототехника, «Робототехника и автономные системы», том 61, выпуск 12, Декабрь 2013, страницы 1258-1276.

...