Робот для состязаний «Выход из лабиринта»
Проход робота по лабиринту является одной из классических задач для всякого рода состязаний по робототехнике. Задача сама по себе интересна, тем, что ее базовый алгоритм достаточно прост. Но в тоже время он предоставляет большой простор как для усложнения поведения робота для выхода из сложных лабиринтов, так и, наоборот, для оптимизации поведения робота, для обхода лабиринтов специфичных видов.
Для начала, собираем базовую модель учебного робота Robot Educator, для этого можно использовать инструкцию в программном обеспечении MINDSTORMS EV3.
Что вы будете делать в таком случае? Идти вперед выставив руки перед собой? Не плохая идея. А потом что? И вообще, что значит "вперед"? А если это очень большой зал? В таком случае, есть вероятность, что, поскольку вы не видите ориентира, на который могли бы равняться, то вы будете шагать чуть-чуть в сторону. В итоге, прошагав окружность вы вернетесь на тоже место с какого начали, но так и не узнаете, что вернулись в него – так вы будете ходить очень долго.
Наиболее разумной идеей было бы попытаться найти опору в виде стены для какой-либо руки. Допустим, правой. Как только стена обнаружена, вы в вправе двигаться вперед или назад. Стена в таком случае будет являться вашим путеводителем, опорой в этом "темном" мире.
У робота такой рукой могут быть сенсоры расстояния, касания или даже освещенности. Если робот использует сенсор касания, то во время движения в момент, когда стена потеряется, он выдаст сигнал, который будет служить для робота поводом изменить свое поведение. Если используется сенсоры расстояния, то для того, чтобы двигаться вдоль стены, не обязательно приближаться к ней вплотную – достаточно приблизится на какое-нибудь удобное расстояние и во время движения стараться находиться все время на том же расстоянии от стены. В таком случае, резкое изменение расстояния, сигнализирует о том, что роботу нужно совершить существенную корректировку своего курса, например, поворот за угол.
|
|
|
Когда мы рукой чувствуем стену – мы спокойно движемся. Когда стена обрывается, значит, лабиринт в этом месте делает поворот. Мы тоже сделаем тогда поворот.
Если все время держать руку на стене и двигаться вперед, в конце концов, произойдет такая ситуация, когда лбом вы стукнитесь об стену – в том месте, где стена справа заканчивается, соединяясь с другой стеной.
Поэтому, чтобы уберечь свой лоб, рекомендуется вторую руку держать перед собой. Для робота второй рукой будет еще один сенсор. Причем, можно использовать как один из тех трех сенсоров, что перечислялись выше – сенсор расстояния, сенсор касания, сенсор освещенности, так и счетчики поворота оси двигателей. Если до столкновения счетчик поворота оси двигателя увеличивался на одну постоянную величину за единицу времени, то после столкновения характер изменений будет другим – за ту же единицу времени прирост будет значительно меньше - при столкновении со стеной-препятствием, двигатели начнут вращаться медленнее.
|
|
|
Ответной реакцией на столкновение со стеной будет поворот к ней боком, после чего уже эта стена будет использована как "опорная" вашей правой рукой. Движение продолжится вдоль нее.
В итоге на текущий момент, получается следующее правило обхода лабиринта: двигаемся прямо, пока под нашей рукой чувствуется стена, как только стена обрывается поворачиваемся направо, чтобы найти ее и двигаемся снова вдоль стены, если же другой рукой мы ощутили стену спереди, то поворачиваемся налево и используем уже эту стену для движения вдоль нее.
Приведенный выше алгоритм называется "Правилом правой руки" и может быть успешно использован для выхода из всех лабиринтов, которые имеют выход.
Согласно заданию, лабиринт состоит из шести секций, соединенных между собой проходами. Конфигурация проходов заранее неизвестна. Таким образом, одно из возможных конфигураций лабиринта будет выглядеть следующим образом:
|
|
|
Напомним, что идея "Правила правой руки" состоит в том, что роботу все время необходимо двигаться "держась" правой стенки. Обрыв стены означает для робота, поиск ее с правой стороны. Если перед роботом возникает препятствие, то робот выполняет левый поворот, так что препятствие становится по правую сторону и используется роботом к новая "опоре", вдоль которой нужно перемещаться. Как результат, траекторию движения робота в приведенной выше конфигурации лабиритна можно будет отобразить как:
А что если для поиска опоры использовать не правую, а левую руку? Тогда методика обхода лабиринта будет уже называться "Правилом левой руки". В ней все действия будут аналогичны, только направление движения будет меняться: роботу все время необходимо двигаться "держась" левой стенки. Обрыв стены означает для робота, поиск ее с левой стороны. Если перед роботом возникает препятствие, то робот выполняет правый поворот, так что препятствие становится по левую сторону и используется роботом как новая "опора", вдоль которой нужно перемещаться.
|
|
|
Траектория движения в этом же лабиринте изменится:
Очевидно, что "Правило левой руки" дает более оптимальную траекторию – т.е. робот сможет проехать лабиринт за меньшее время. И в первую очередь, в данном конкретном задании, это обуславливается положением старта и финиша в лабиринте.
Хотя и в конкретном приведенном примере было видно, что траектория движения робота, выполняющего "Правило левой руки", - более оптимальна, их этого нельзя сделать вывод, что в каждом лабиринте такой робот будет опережать робота, запрограммированного на движение по "Правилу правой руки".
Если теперь рассмотреть варианты прохода для каждой конфигурации лабиринта, то получится такая вот статистика:
Где:
· в первой строчке – идеальные конфигурации – робот не сделает ни одного ненужного заворота.
· остальных строчки для проходов с одним или несколькими "ненужными" заворотами в тупики. Причем, если написано два «ненужных» прохода, то это может быть заворот в один длинный тупик или два коротких – в любом случае, на их проходы тратиться почти одинаковое время.
· в последней строчке – сколько "ячеек" придется посетить при самой неудачной конфигурации лабиринта.
Из таблицы видно, что в 45 конфигурациях лабиринта из 180 робот, обходящий алгоритм по "Правилу левой руки", будет делать только верные перемещения. В то время как роботу, выполняющий программу по "Правилу правой руки" доступно только 13 таких конфигураций. Даже на то, что роботу выпадет конфигурация, в которой ему придется сделать всего лишь два "ненужных" прохода, вероятность больше в случае "Правила левой руки" - 41 к 180, тогда как у "Правила правой руки" - всего 36 к 180. Следовательно, можно сделать вывод, что у робота, двигающегося вдоль левых стенок, вероятность прийти к финишу первым выше. Т.е. при выборе, какой именно алгоритм реализовывать у робота, выбор, безусловно, ложиться на "Правило левой руки". Причем, если вспомнить о необходимости собирать шарики по пути движения робота (а они лежать в строго определенных позициях в 3-ем, 4-ом и 5-ом коридорах), статистика не сильно изменится.
Структура основной программы однозначно диктуется правилом правой руки:
Алгоритм начинает свое выполнение с движение вперед. Как уже говорилось, в общем случае, это может быть обычное движение.
Затем, друг за другом идет проверка на обнаружение прохода в правой стене, либо на обнаружение столкновения с препятствием. И, в зависимости от того, какая проверка сработала, вызываются блоки поворотов. Если никакая проверка не сработала в этот момент времени, то в следующий момент времени нужно сделать еще одну проверку, а потом еще и еще.Очевидно, что после выполнения поворотов нужно опять продолжить движение вперед, и опять перейти к проверкам на проход или препятствие.
Логично было бы все время выполнять периодическую корректировку или просто добиться упрощения алгоритма, принимая во внимание, что команды "включить мотор" не блокируют дальнейшую работу алгоритма, а передают управление следующим инструкциям. Далее на следующем занятии проводится программирование в специальной программе Лего.
Дата добавления: 2020-12-22; просмотров: 219; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!