Робот для состязаний: выход из лабиринта. Часть I

Проход робота по лабиринту является одной из классических задач для всякого рода состязаний по робототехнике. Задача сама по себе интересна, тем, что ее базовый алгоритм достаточно прост. Но в тоже время он предоставляет большой простор как для усложнения поведения робота для выхода из сложных лабиринтов, так и, наоборот, для оптимизации поведения робота, для обхода лабиринтов специфичных видов.

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

Итак, вы оказались в лабиринте...


Нет. На самом деле, если вы робот, собранный на базе Lego Mindstorms, как только вы попали в лабиринт, он будет для вас выглядеть вот так.

Да. Вы ничего не видите. У вас нет глаз. У вас нет стереозрения. Для вас расположение стен лабиринта и уж тем более наличие ответвлений и проходов – загадка. Единственное, что вы, скорее всего, знаете наверняка, что прямо под вами твердая поверхность.

Что вы будете делать в таком случае? Идти вперед выставив руки перед собой? Не плохая идея. А потом что? И вообще, что значит "вперед"? А если это очень большой зал? В таком случае, есть вероятность, что, поскольку вы не видите ориентира, на который могли бы равняться, то вы будете шагать чуть-чуть в сторону. В итоге, прошагав окружность вы вернетесь на тоже место с какого начали, но так и не узнаете, что вернулись в него – так вы будете ходить очень долго.
Наиболее разумной идеей было бы попытаться найти опору в виде стены для какой-либо руки. Допустим, правой. Как только стена обнаружена, вы в вправе двигаться вперед или назад. Стена в таком случае будет являться вашим путеводителем, опорой в этом "темном" мире.

У робота такой рукой могут быть сенсоры расстояния, касания или даже освещенности. Если робот использует сенсор касания, то во время движения в момент, когда стена потеряется, он выдаст сигнал, который будет служить для робота поводом изменить свое поведение. Если используется сенсоры расстояния, то для того, чтобы двигаться вдоль стены, не обязательно приближаться к ней вплотную – достаточно приблизится на какое-нибудь удобное расстояние и во время движения стараться находиться все время на том же расстоянии от стены. В таком случае, резкое изменение расстояния, сигнализирует о том, что роботу нужно совершить существенную корректировку своего курса, например поворот за угол.

Сенсор освещенности может также использоваться роботом в контексте определения расстояния – чем ближе сенсор к стене, тем больше света возвращается (от светлой стены), чем дальше от стены, тем меньше света возвращается.

Итак,как будет выглядеть наше движение?

Когда мы рукой чувствуем стену – мы спокойно движемся. Когда стена обрывается, значит, лабиринт в этом месте делает поворот. Мы тоже сделаем тогда поворот.

Если все время держать руку на стене и двигаться вперед, в конце концов, произойдет такая ситуация, когда лбом вы стукнитесь об стену – в том месте, где стена справа заканчивается, соединяясь с другой стеной.

Поэтому, чтобы уберечь свой лоб, рекомендуется вторую руку держать перед собой. Для робота второй рукой будет еще один сенсор. Причем, можно использовать как один из тех трех сенсоров, что перечислялись выше – сенсор расстояния, сенсор касания, сенсор освещенности, так и счетчики поворота оси двигателей. Если до столкновения счетчик поворота оси двигателя увеличивался на одну постоянную величину за единицу времени, то после столкновения характер изменений будет другим – за ту же единицу времени прирост будет значительно меньше - при столкновении со стеной-препятствием, двигатели начнут вращаться медленнее.

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

В итоге на текущий момент, получается следующее правило обхода лабиринта: двигаемся прямо, пока под нашей рукой чувствуется стена, как только стена обрывается поворачиваемся направо, чтобы найти ее и двигаемся снова вдоль стены, если же другой рукой мы ощутили стену спереди, то поворачиваемся налево и используем уже эту стену для движения вдоль нее.

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

Приведенный выше алгоритм называется "Правилом правой руки" и может быть успешно использован для выхода из всех лабиринтов, которые имеют выход.