В статье показано создание робота, которые ездит по линиям и может проходить лабиринты, после изучения лабиринта он может пройти его кратчайшим путём. Автор долго создавал этот проект, удача настигла его с третьего раза.
Демонстрация работы машины:
Материалы и инструменты:
- Arduino RBBB
- Микродвигатели 2 шт
- Кронштейны для двигателей 2 шт
- Колёса 2 шт
- Шариковое колесо
- Датчик отражения аналоговый
- Гайки с болтами по 2 шт
- Драйвер двигателя
- Держатель для батарей 4 шт ААА
- Батарейки (аккумуляторы) ААА 4 шт
- Корпус
- Гайки, болты, шайбы
- Соединительные провода
- Припой
- Плоскогубцы
- Паяльник
- Отвёртка
Шаг первый. Теория.
Автору нужен был робот , который сам будет находить выход из лабиринта, после чего сможет оптимизировать обратный путь. При создании машины для лабиринтов руководствовались методом левой руки. Чтоб было понятнее следует представить что вы оказались в лабиринте и всегда держите левую руку на стене. После прохождения определённого пути это поможет выйти вам из лабиринта если он не замкнут. Робот может работать только с незамкнутыми лабиринтами.
Принципы работы способа левой руки довольно прост:
- Если есть возможность повернуть налево, поверните налево.
- Если есть возможность двигаться прямо, двигайтесь прямо.
- Если есть возможность повернуть направо, поверните направо.
- Если вы зашли в тупик, развернитесь на 180 градусов.
Также роботу нужно принимать решения на перекрёстке, если же на повороте он не свернёт, тогда поедет прямо. Для построения лучшего маршрута обратного пути, каждое решение записывается в память.
L = левый поворот
R= правый поворот
S= пропустить поворот
B= развернутся на 180 градусов
Ниже показан этот метод в действии на примере простого лабиринта. Робот прошёл дистанцию путём команд LBLLBSR.
Путь вышел довольно большой, его требуется превратить в оптимальный SRR. Для этого определяется где робот повернул не туда. Везде где использована команда «В» путь будет неверным, так как робот был в тупике, поэтому «В» следует заменить на что-то другое. Первым неверным движением было LBL, робот свернул и развернулся, в то время когда требовалось просто следовать прямо LBL = S. Таким образом, выстраивается идеальный путь LBL = S, LBS = R. На основе таких замен робот выстраивает для себя идеально короткий путь.
Шаг второй. Шасси робота.
Основой для шасси робота стал акрил толщиной 0.8 мм, резка производилась лазером согласно чертежу. В архиве под статьёй будет файл чертежа из AutoCAD. Использовать такой материал было необязательно, но автор взял то что было в наличии.
В нижней части сделаны отверстия для крепления двигателей, платы, колёс и датчиков. Верхняя часть имеет большое отверстие для проводов.
Шаг третий. Установка колёс.
Оба двигателя автор прикрепил с помощью болтов. Далее, на их ось просто одел колёса, совместив вал с отверстием колеса.
Шаг четвёртый. Arduino.
На этом этапе автор сначала следовал инструкциям по сборке Arduino RBBB. Далее, он отрезал часть платы для уменьшения её размеров. Ножницами по металлу был отрезан разъём питания и стабилизатор. После чего, к левой стороне платы на контакты от 5В до А0 припаяли 9-контактный разъем, для подключения к нему датчика. К правой стороне платы на контакты от D5 до D8 был припаян 4-контактный разъём, к нему подключат контроллер двигателя. Для подачи питания 2-контактный разъем припаяли к 5В и GND.
Шаг пятый. Контроллер двигателя.
Автор сам разработал печатную плату для этого шага, схема в формате Eagle прикреплена в архиве под статьёй. Первый двигатель подключили к контактам M1-A и M1-B, второй к M2 и M2-B. Первый вход первого двигателя In 1A подключили к 7 выводу Arduino. In 1B был подключён к выводу 6 Arduino. К первому входу второго двигателя In 2A подключён к 5 выводу Arduino. Контакт In 2B подключается к 8 выводу Arduino. Питание и земля подключили к питанию и земле Arduino.
Шаг шестой. Датчики.
Данный элемент продается в виде платы из датчиков, изначально их восемь штук, два крайних были удалены автором. На плату припаяли разъем из 9 контактов, к ним подключат провод ведущий к Arduino. Датчик обнаруживает белый и чёрный участок лабиринта с помощью отражения от поверхности.
Шаг седьмой. Верхняя часть.
Шасси с верхней частью робота соединили болтами и стойками. Аккумулятор был закреплён на верхней части липучкой. Провода от него проложили через подготовленное отверстие. При креплении автор решил не использовать винты, а оставить аккумулятор на липучке, чтоб можно было проще заменять батарейки. С помощью выключателя на корпусе для батарей была произведена проверка работоспособности.
Шаг девятый. Питание.
К Arduino просто припаяли провода от аккумулятора. Включение и выключение робота будет происходить выключателем на аккумуляторе, поэтому было решено использовать пайку. На этом сборка робота завершена.
Шаг десятый. Программная часть.
Программа имеет несколько функций отвечающих за алгоритм работы. Функция «левой руки» получает показания от датчиков и управляет роботом по этим правилам. Функция поворотов включается до того как робот заметит чёрную линию, заметив, её он едет прямо. Также встроена функция оптимизации пути. Программу можно скачать под статьёй в архиве.
Видео робота:
В статье описано создание робота, который ездит по линиям и может проехать через лабиринт, а потом кратчайшим путем вернутся в начало. Этот робот получился у меня с 3-ей попытки.
Для начала, видео работы робота:
Список деталей:
2 микродвигателя.
Пара кронштейнов для двигателя.
Пара колес.
Шарик и корпус.
Аналоговые датчики отражения.
Болты и гайки #2.
Arduino RBBB
Драйвер для моторов.
Держатель 4х AAA батарей.
4 аккумулятора AAA.
Болты, гайки, шайбы и стойки.
Провода.
Припой.
Инструменты:
Паяльник.
Отвертка.
Плоскогубцы.
Теория
Есть две задачи которые надо решить: найти выход и оптимизировать обратный путь.
Для обнаружения выхода я руководствовался методом левой руки. Представьте, что вы находитесь в лабиринте и постоянно держите левую руку на стене. В конце концов, это позволит вам выйти из незамкнутого лабиринта. Робот работает только с незамкнутыми лабиринтами.
Способ левой руки описывается простыми условиями:
- Если вы можете повернуть налево, поверните налево.
- Если вы можете двигаться прямо, то двигайтесь прямо.
- Если вы можете повернуть направо, поверните направо.
- Если вы в тупике, развернитесь.
Робот должен принимать решение на перекрестке. Если робот на повороте не поворачивает, то он движется прямо. Каждое решение принятое роботом записывается в его памяти для построения оптимального обратного маршрута
L = Левый поворот
R = Правый поворот
S = Пропуск поворота
B = Разворот.
На картинке выше показан этот метод в действии. Путь к выходу - это LBLLBSR.
Мы должны превратить путь LBLLBSR в оптимальный путь SRR. Для этого необходимо найти место где робот повернул не туда. "B" это разворот, который может произойти в тупике, т.е. на неверном пути.Чтобы
оптимизировать путь мы должны заменить "B" на что то другое.
Давайте рассмотрим первые 3 действия LBLLBSR - LBL. Вместо того, чтобы повернуть налево, развернуться и опять повернуть налево, робот должен был пойти прямо. Таким образом, мы можем сказать, что LBL = S.
Вот полный список подобных замен:
LBR = B
LBS = R
RBL = B
SBL = R
SBS = B
LBL = S
В лабиринте могут быть не все эти повороты, но они необходимы. Некоторые из них даже возвращают B обратно. Это необходимо для дальнейшей правильной оптимизации пути.
LBL = S, новый путь SLBSR. LBS = R, новый путь SRR. Как вы видите, мы получили оптимальный путь. Мой робот оптимизирует путь во время движения. Путь хранится в массиве, и каждый раз перед сохранением хода он проверяет, что предыдущий ход не B, а если В, то оптимизирует путь. Роботу необходимо знать по крайней мере 3 последних хода, для оптимизации алгоритма прохождения пути.
Рассмотрим другой пример.
Если использовать правило левой руки для вышеприведенного лабиринта, то получим следующий алгоритм: LLLBLLLRBLLBSRSRS
Начинаем сокращать:
LL (LBL = S) LL (RBL = B) (LBS = R) RSRS = LLSLLBRRSRS
Продолжаем:
LLSL(LBR = B)RSRS = LLSLBRSRS
Продолжаем:
LLSBSRS
Продолжаем:
LL (SBS = B)RS = LLBRS
Продолжаем:
L (LBR = B)S = LBS
Итого:
LBS = R
Шасси
Шасси робота сделано из акрила толщиной 0.8 и вырезано лазером. К статье прилагается файл AutoCAD с чертежом. Если у вас нет возможности точно повторить его, можете сделать его как вам удобно. На функционал это не повлияет, возможно придётся немного поправить код.
Нижняя часть имеет отверстия для крепежа двигателей, Arduino, металлического шарика, датчика и верхней части. В верхней части есть одно больше отверстие для проводов от аккумулятора, который крепится на липучки и отверстия для прикрепления низа.
Установка привода колес
Я просто прикрепил каждый двигатель при помощи двух болтов. После этого, я одел на ось колёса простым надавливанием. Совместите D образный вал с отверстием в центре колеса.
Arduino
Следуйте инструкциям по сборке Arduino RBBB. Вам нужно будет отрезать часть платы для уменьшения размеров. Если вы не нуждаетесь в разъеме питания и стабилизаторе просто отрежьте их. Для этого можно использовать ножницы по металлу, пилу по металлу или любой подобный инструмент. Не паяйте на плату разъёмы кроме тех, которые необходимы для программирования по порту FTDI. Потом припаяйте 9-контактный разъем на левой стороне платы на контакты от "5В" до "А0". Позже к ним будет подключен датчик. Припаяйте 4-контактный разъем на правую сторону платы на контакты от "D5" до"D8". К ним будет присоединён контроллер двигателя. Припаяйте 2-контактный разъем к GND и 5V. На них будет подаваться питание.
Контроллер двигателя
Я разработал и приложил печатную плату в формате Eagle для контроллера двигателя.
Если вы не используете плату, вы можете сделать это навесным монтажом.
Первый двигатель подключается к контактам, которые я назвал "М1-А" и "M1-B". Второй двигатель подключается к "М2" и "М2-B". 7 вывод Arduino подключается к первому входу первого двигателя "В 1А". 6 вывод Arduino подключается к "В1B". 5 вывод Arduino подключается к первому входу второго двигателя "В2А". 8 вывод подключается к "В 2В". Питание и GND подключается к +5В и GND контактам Arduino.
Датчики
Изначально датчик продается в виде платы из 8 датчиков. Два датчик по краям могут быть удалены. 9-контактный разъем должен быть припаян к датчику от "GND" до "6". Потом к ним подключается ответная часть провода, от которой идут к Arduino.
Эти датчики уменьшают напряжение в зависимость от того, как сильно ИК-лучи отражаются от поверхности. Мы можем использовать их для обнаружения белых и черных участков лабиринта. Датчик выдает напряжение около 0В при обнаружении белой поверхности и напряжение около Vin при обнаружении тёмной поверхности.
Сборка верхней части
Прикрепите верхнюю часть к нижней, при помощи болтов и стоек. Аккумулятор прикрепите к ней при помощи липучки. Закрепите верхнюю палубу. Используйте липучку для крепления аккумулятора. Пропустите провода от него через большее отверстие в верхней части. Мой аккумулятор имеет встроенный выключатель питания. Я обнаружил, что проще не ставить винт на крышке аккумулятора. Она и так неплохо держится, а отсутствие винта позволяет быстро вынуть один из аккумуляторов.
Подключение и установка датчиков
Датчик крепится при помощи болтов к нижней части. Вывод GND на дальней левой части датчика подключается к GND Arduino. Следующий вывод это Vcc, который подключается к 5В Arduino. Контакты 6 - 1 аналоговых датчиков подключены к контактам АЦП 5 – 0 Arduino. Т.е. контакт 6 датчика подключен к контакту АЦП 5 Arduino, контакт 5 датчика подключен к 4 Arduino, и т.д
Одним из самых простых правил для прохождения лабиринта является правило "одной руки": двигаясь по лабиринту, надо все время касаться правой или левой рукой его стены. Этот алгоритм, вероятно, был известен еще древним грекам. Придется пройти долгий путь, заходя во все тупики, но в итоге цель будет достигнута. Хотя у этого правила и есть один недостаток, но о нем мы поговорим позже.
Попробуем описать робота, действующего в соответствии с правилом "правой руки".
В начале своей работы робот должен найти стену, по которой он будет следовать. Для этого он может просто двигаться вперед, пока не упрется в преграду.
После того как робот наткнулся на препятствие, он начинает передвигаться в соответствии с правилом "правой руки".
Двигаясь вдоль стены, робот следит, есть ли проход справа. Если проход есть, робот должен идти по нему, чтобы не оторваться от стены справа.
Если прохода нет - впереди стена - робот поворачивает налево. Если прохода снова нет, он еще раз поворачивает налево, таким образом разворачиваясь на 180 градусов, и идет в обратном направлении.
Блок-схема алгоритма для робота, работающего по правилу "правой руки", представлена на рисунке.
Попробуем проверить работу данного алгоритма и напишем для него программу. Для этой цели обратимся к среде программирования . Эта среда является удобным средством для моделирования различных алгоритмов, связанных с управлением роботами. В ней есть исполнитель черепаха, который по своей сути является не чем иным, как самым настоящим роботом. Черепаха располагает очень удобным набором команд - вперед, направо, налево, назад. Кроме того, в центре черепахи есть датчик, принимающий значение от 0 до 100, в зависимости от тона поверхности, на которой она находится.
Диалект языка Лого, который мы будем использовать, очень прост и похож на Basic. Познакомиться с командами языка можно . А бесплатно скачать среду программирования GameLogo - . Размер дистрибутива невелик - всего 1 Mb.
В архиве с GameLogo есть фоны с лабиринтами, одним из которых мы и воспользуемся.
В самом начале программы дадим команду черепахе, чтобы она подняла перо (по умолчанию черепаха оставляет после себя след).
Размер поля - 800 на 600 точек. Исходное положение для черепахи находится в месте с координатами 115, 545 (белый квадрат).
Цвет дорожек лабиринта - светлый, на них датчик будет принимать значения больше 50. Цвет стен лабиринта - темный, значение датчика будет меньше 50. Выход из лабиринта представлен черным квадратом, значение датчика над которым будет равно 0.
Объявим переменную флаг, с помощью которой будем контролировать, достигнут ли выход из лабиринта.
Напишем программу и запустим ее с помощью большой красной кнопки с надписью "Выполнить".
Переменная флаг фон = maze1.gif поднять перо место 115, 545 " поиск первой стены повторять пока датчик > 50 { вперед 12 } " правило правой руки повторять пока флаг = 0 { направо 90 вперед 12 если датчик = 0 то флаг = 1 иначе если датчик
Если известно, что у лабиринта нет отдельно стоящих стенок, то есть нет замкнутых маршрутов, по которым можно возвращаться в исходную точку, то такой лабиринт называют односвязным и его всегда можно обойти полностью, применив правило "одной руки".
Если же лабиринт содержит отдельно стоящие стенки, то, применяя правило "одной руки", не всегда можно пройти все коридоры и тупики. Лабиринты с отдельно стоящими стенками и с замкнутыми маршрутами называются многосвязными. При этом многосвязные лабиринты можно разделить на две группы: без "петли" вокруг цели (замкнутый маршрут не проходит вокруг цели) и с замкнутой "петлей" вокруг цели (цель можно обойти по замкнутому маршруту).
В многосвязных лабиринтах второй группы правило "одной руки" не работает и, применяя его, достичь цели невозможно. Но и эти лабиринты можно пройти, полагаясь на точный алгоритм.
Решение задачи о таких лабиринтах принадлежит сравнительно позднему времени, и начало ему положено Леонардом Эйлером. Эйлер не без оснований полагал, что выход из любого лабиринта может быть найден, и притом сравнительно простым путем.
Универсальный алгоритм прохождения любых лабиринтов был описан только через столетие в книге французского математика Э. Люка "Recreations matematiques", изданной в 1882 году. Интересно, что Люка при описании алгоритма указал на первенство другого французского математика М. Тремо. Таким образом, алгоритм стал известен как алгоритм Люка-Тремо .
Тремо предлагает следующие правила: выйдя из любой точки лабиринта, надо сделать отметку на его стене (крест) и двигаться в произвольном направлении до тупика или перекрестка; в первом случае вернуться назад, поставить второй крест, свидетельствующий, что путь пройден дважды - туда и назад, и идти в направлении, не пройденном ни разу, или пройденном один раз; во втором - идти по произвольному направлению, отмечая каждый перекресток на входе и на выходе одним крестом; если на перекресте один крест уже имеется, то следует идти новым путем, если нет - то пройденным путем, отметив его вторым крестом.
Зная алгоритм Тремо, можно скорректировать поведение легендарного Тесея. Вдохновленный подарком любимой Ариадны, он уверенно идет по лабиринту. Вдруг перед ним возникает ход, по которому уже протянута нить... Что делать? Ни в коем случае не пересекать ее, а вернуться по уже известному пути, сдваивая нить, пока не найдется еще один непройденный ход.
Применив вариант алгоритма Тремо, отец теории информации Клод Шеннон (Claude Elwood Shannon) построил одного из первых самообучающихся роботов. Шеннон дал ему звучное имя "Тесей", но в истории "Тесей" стал больше известен как "мышь" Шеннона. "Мышь" сначала обследовала весь лабиринт, а затем (во второй раз) проходила весь путь значительно быстрее, избегая участков, пройденных дважды.
|
|
На первой Российской Олимпиаде Роботов проводились соревнования, целью которых было прохождение своеобразного лабиринта: за наиболее короткое время, двигаясь через "открытые двери" в стенках, робот должен был добраться от места старта до места финиша. Контролировать свое движение робот мог по черным линиям, нанесенным на пол лабиринта.
Для того, чтобы понять, как запрограммировать робота, для перемещения его по лабиринту, рекомендуется поставить себя на место робота и думать, а как бы вы начали действовать...
Итак, вы оказались в лабиринте...
Нет. На самом деле, если вы робот, собранный на базе Lego Mindstorms, как только вы попали в лабиринт, он будет для вас выглядеть вот так.
Да. Вы ничего не видите. У вас нет глаз. У вас нет стереозрения. Для вас расположение стен лабиринта и уж тем более наличие ответвлений и проходов – загадка. Единственное, что вы, скорее всего, знаете наверняка, что прямо под вами твердая поверхность.
Что вы будете делать в таком случае? Идти вперед выставив руки перед собой? Не плохая идея. А потом что? И вообще, что значит "вперед"? А если это очень большой зал? В таком случае, есть вероятность, что, поскольку вы не видите ориентира, на который могли бы равняться, то вы будете шагать чуть-чуть в сторону. В итоге, прошагав окружность вы вернетесь на тоже место с какого начали, но так и не узнаете, что вернулись в него – так вы будете ходить очень долго.
Наиболее разумной идеей было бы попытаться найти опору в виде стены для какой-либо руки. Допустим, правой. Как только стена обнаружена, вы в вправе двигаться вперед или назад. Стена в таком случае будет являться вашим путеводителем, опорой в этом "темном" мире.
У робота такой рукой могут быть сенсоры расстояния, касания или даже освещенности. Если робот использует сенсор касания, то во время движения в момент, когда стена потеряется, он выдаст сигнал, который будет служить для робота поводом изменить свое поведение. Если используется сенсоры расстояния, то для того, чтобы двигаться вдоль стены, не обязательно приближаться к ней вплотную – достаточно приблизится на какое-нибудь удобное расстояние и во время движения стараться находиться все время на том же расстоянии от стены. В таком случае, резкое изменение расстояния, сигнализирует о том, что роботу нужно совершить существенную корректировку своего курса, например поворот за угол.
Сенсор освещенности может также использоваться роботом в контексте определения расстояния – чем ближе сенсор к стене, тем больше света возвращается (от светлой стены), чем дальше от стены, тем меньше света возвращается.
Итак,как будет выглядеть наше движение?
Когда мы рукой чувствуем стену – мы спокойно движемся. Когда стена обрывается
, значит, лабиринт в этом месте делает поворот. Мы тоже сделаем тогда поворот.
Если все время держать руку на стене и двигаться вперед, в конце концов, произойдет такая ситуация, когда лбом вы стукнитесь об стену – в том месте, где стена справа заканчивается
, соединяясь с другой стеной.
Поэтому, чтобы уберечь свой лоб, рекомендуется вторую руку держать перед собой. Для робота второй рукой будет еще один сенсор. Причем, можно использовать как один из тех трех сенсоров, что перечислялись выше – сенсор расстояния, сенсор касания, сенсор освещенности, так и счетчики поворота оси двигателей. Если до столкновения счетчик поворота оси двигателя увеличивался на одну постоянную величину за единицу времени, то после столкновения характер изменений будет другим – за ту же единицу времени прирост будет значительно меньше - при столкновении со стеной-препятствием, двигатели начнут вращаться медленнее.
Ответной реакцией на столкновение со стеной будет поворот к ней боком, после чего уже эта стена будет использована как "опорная" вашей правой рукой. Движение продолжится вдоль нее.
В итоге на текущий момент, получается следующее правило обхода лабиринта: двигаемся прямо, пока под нашей рукой чувствуется стена, как только стена обрывается
поворачиваемся направо
, чтобы найти ее и двигаемся снова вдоль стены, если же другой рукой мы ощутили стену спереди
, то поворачиваемся налево
и используем уже эту стену для движения вдоль нее.
Если продолжить наблюдать за роботом, выполняющим данный алгоритм, то в итоге можно увидеть, что он достигает выхода из лабиринта:
Приведенный выше алгоритм называется "Правилом правой руки" и может быть успешно использован для выхода из всех лабиринтов, которые имеют выход.
