#algorithm #artificial-intelligence #robotics
#алгоритм #искусственный интеллект #робототехника
Вопрос:
Мне интересно, можно ли изменить алгоритм волнового фронта (или любой другой алгоритм навигации), пытаясь достичь определенного местоположения цели, чтобы перейти ко всем доступным местоположениям.
Любые другие советы по различным типам алгоритма волнового фронта также были бы полезны.
Ответ №1:
Я посетил ваш сайт. Вы заявили, что робот может получать команды типа «Перейти к кетчену». Что ж, я советую не изобретать колесо заново. На самом деле, вам не нужно посещать каждую ячейку или «область отверстия». Скорее, вы должны выбрать кратчайший путь к нему, а затем пройти.
Я считаю, что алгоритм Дейкстры намного лучше подходит для поиска пути вашего робота.
Усовершенствованная версия Дейкстры — это алгоритм A *, который в среднем занимает меньше времени.
Здесь вы можете найти примеры того, как они работают, эффективно.
Редактировать:
Я снова посетил ваш сайт. Вы заявили, что вам нужен алгоритм для навигации по всему erea. Ну, насколько я знаю, повторение алгоритма A * будет намного лучше. A * использует BFS, которая имеет лучшую производительность в среднем случае. Он очень эффективен по сравнению с волновым фронтом. Псевдокод выглядит следующим образом:
- А) Найдите кратчайший путь с помощью алгоритма * между местоположением и целью
- Б) Если пути к цели нет, укажите временное местоположение и двигайтесь к нему. (Поскольку вы указали, он может найти способ позже). После прибытия во временное местоположение перейдите к шагу A.
- В) В противном случае, если вы нашли способ, перейдите к цели.
Комментарии:
1. Спасибо, но, к сожалению, мой вопрос заключается в том, что для робота нет датчика и предварительной карты, и робот должен убедиться, что каждое место посещено и очищено. Это y-поиск пути в некотором смысле бессмыслен для этого робота!
2. @FidEliO хммм.. Почему бы вам не предоставить вашему роботу подготовленные карты области? (например, 2d-массив, подобный вашему: единицы и нули). Роботу очень сложно посещать каждое место
3. DDD Вот почему я имел в виду, но есть ли какой-либо другой метод поиска по всей области?
4. @FidEliO Ты хочешь просто искать? или пройти через всю область?
5. @DDD нет, мне нужно обойти всю область… И я хочу лучший алгоритм, я мог бы подумать о BFS, DFS. Есть предложения, мистер DDD?
Ответ №2:
В этой статье 1993 года был представлен вариант ванильного планировщика волнового фронта, который обеспечивает полное покрытие в дополнение к навигации от начала до цели:
А. Зелинский, Р.А. Джарвис, Дж. К. Бирн, С. Юта, «Планирование путей полного покрытия неструктурированной среды мобильным роботом», Материалы Международной конференции по передовой робототехнике, 1993, стр. 533-538.
Также смотрите Следующий обзорный документ для получения дополнительных идей по планированию пути покрытия:
Энрик Гальцеран, Марк Каррерас, «Обзор планирования пути покрытия для робототехники», Робототехника и автономные системы, том 61, выпуск 12, декабрь 2013, страницы 1258-1276.