Алгоритм кратчайшего пути в роботе линейного следования
Как графические алгоритмы могут быть использованы в роботе для решения задач с лабиринтами. Я решил грид с помощью поиска DFS, но не знаю, как реализовать его на самом деле робот следования линии. мой кратчайший путь поиска реализуется на сетке 20 на 20. где s = начало и g = пункт назначения, а числа обозначают положение каждой точки внутри сетки (построчно).
Решение
-Если вы новичок в микроконтроллере, то я бы порекомендовал вам сначала добиться того, чтобы ваш робот следовал линии.
-Если робот работает хорошо по линии следования, то вы должны попробовать сделать так, чтобы ваш робот пропустил полосы (соединения в сетке) и сделал вашего робота поперечной полной сеткой (все координаты сетки), одновременно вы можете сделать подсчет числа полос, пройденных роботом (вы можете использовать двумерный массив для хранения там координат).
-Если вы можете решить две вышеупомянутые задачи, тогда вы можете применить свою логику в решении лабиринта внутри сетки.
Другие решения
Однажды я реализовал алгоритм кратчайшего пути на плате AVR.
Вот шаги, которым вы должны следовать.
Шаг 1: Выполните пробный прогон арены и сохраните все координаты в двумерном массиве. Как вы уже описали, кажется, что существует два типа соединения. Обязательно мигайте другим светодиодом на борту каждый раз, когда вы проходите перекресток. Таким образом, вы можете убедиться, что вы правильно читаете доску.
Шаг 2: Теперь у вас есть все координаты в двумерном массиве. Вы применяете DFS. Я бы не рекомендовал это. так как у вас есть решетка, а не дерево для решения. Используйте алгоритм Дейкстры.
Реализация этого не должна быть сложной. Поскольку компилятор AVR очень похож на C.
Шаг 3: Теперь следуйте за результатом. Пусть день у вас есть массив 8 * 8. определите нумерацию от 1 до 64. ваш вывод должен быть в форме
1 9 10 18 …. и так далее
Теперь посчитайте разницу между двумя соседними числами
8, 1, 8 и т. Д.
и зафиксируйте ход для каждого числа, например, для 8 — налево, для 1 — север. Просто помните свое текущее направление, чтобы двигаться в другом направлении. То, как идти на север с запада, будет отличаться от движения на север с востока.
Опять же, я бы порекомендовал вам сначала показать ваш окончательный результат на светодиоде Иногда ваш алгоритм работает нормально, и оборудование перестает работать.
Алгоритм кратчайшего пути для робота следования за линией, в котором нет петель на линии, относительно прост в реализации.
Это может быть сделано путем исчерпывающего обхода всех возможных маршрутов, делая поворот влево / вправо по умолчанию в каждой точке принятия решения. Таким образом, если на дорожке нет петель, робот в конечном итоге доберется до места назначения. Робот должен отслеживать все повороты, которые были сделаны до достижения цели.
После этого необходимо уменьшить количество ненужных поворотов, которые сделал робот. Я подробно обсудил этот алгоритм короткого пути в своем блоге Вот.