Прокладка маршрута роботом

[Admin]

Сегодня появилось свободное время и я модифицировал волновой алгоритм поиска кратчайшего пути
Для чего я его модифицировал? Дело в том что, волновой алгоритм прокладывает путь по кратчайшему расстоянию , то есть рисует диагональные линии под разными углами
Такой маршрут для навигации робота будет просто кошмаром
Роботу для движения по помещению желательно двигаться параллельно стенам. Двигаясь параллельно стене робот может контролировать свое положение с помощью атчиков расстояния или сонаром, с диагоналями все гораздо сложнее
При помощи этой утилиты робот сможет найти выход из любого лабиринта.
Осталось только научить его двигаться по этому маршруту

Карта предложенная мной роботу.
0-препятствия
1-свободно(нет препятствий)

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0
0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0
0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0
0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0
0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0
0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0
0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0
0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0
0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0
0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0
0 1 0 1 1 1 1 1 1 1 0 0 0 1 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 0
0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0
0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0
0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 0 0 0
0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0
0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0
0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0
0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0
0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0
0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0
0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0
0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0
0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0
0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0
0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0
0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0
0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0
0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Робот проложил маршрут из пункта А в пункт В
5-путь проложенный роботом

[Arhat109]

Очень интересно. А где код для Ардуино посмотреть?

[Admin]

Эта утилита написана для роутера с CyberWrt, хотя при желании можно и на ардуину портировать

P.S.
Оперативки у ардуины не хватит
Если только для маленьких карт максимум 20х20

[Arhat109]

У меня - хватит. Темку про доп. память к Ардуино, надеюсь помните? Как вернусь из поездки, так сразу и займусь "расширением памяти".

[kulverstukas]

Admin то что нужно! Именно так я и представлял' подскажи где почитать про саму логику алгоритма? Буду пробовать сам это описать в ардуино "индусским кодом"

[Admin]

Я допилю и выложу в репозиторий готовые пакеты
Если хотите понимания самого алгоритма , то читайте здесь

[Aircat]

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

[Admin]

Одними энкодерами на обойтись. Пробуксовки, погрешность угла поворота и прочие тонкости, приведут к большому отклонению от маршрута

[Arhat109]

Да. Нужно регулярное повторное сканирование пространства и совмещение карты препятствий со свежеполученными данными для уточнения собственного положения тележки.

[Admin]

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

Для поиска конечной точки маршрута человек сначала:
1 - нащупает ближайшую стену
2 - найдет ориентир, например проем в стене расположенный близко к углу или угол стены не стандартный и т.д.
3 - начнет движение в сторону конечной точки, нащупывая стены

Для данной задачи не нужны дальномеры, гироскопы, акселерометры, магнитометры, энкодеры и прочие датчики, достаточно только зарядную станцию с ИК маяком и круговой ИК бампер. Карту можно нарисовать в ручную, приблизительную, без расстояний
Я по этой причине и алгоритм прокладки маршрута адаптировал, что бы он прокладывался по стенам, а не по кротчайшему пути