Задачи в симуляторе Simbad
Далее приведены формулировки задач и некоторые указания к их выполнению. Исходные тексты задач все имеются в папках, пронумерованных соответственно.
Задача 1. Робот, следующий на свет.
Постановка задачи.
Робот, следующий на свет (photovore), или, как вариант, следующий по линии (line tracer) - это своего рода "Hello World" в робототехнике. На Западе такие «машинки» называют ещё Breitenberg Vehicles. При простоте алгоритма, они показывают достаточно интересное, зависящее от перемен в окружающей среде поведение.
Устройство программы робота
Обычно вся программа робота выглядит следующим образом. При старте робота, запускается некоторая функция инициализации систем робота. В Simbad эти действия происходят в конструкторе робота и функции initBehavior. Потом программа входит в бесконечный цикл и сама из него никогда не выходит. Работа этого цикла завершается только при отключении питания робота или, в случае с симулятором, принудительном завершении его программы. В Simbad такой цикл называется performBehavior. Устроен он так:
Бесконечный цикл {
Опрос датчиков();
Выбор действия();
Действие();
}
Как правило, кроме основного цикла других циклов во всей программе нет. Такая модель ещё называется на Западе Sense-Think-Act. Вначале робот «чувствует», то есть воспринимает окружающую среду. Затем «думает», то есть анализирует данные и принимает решение о том, что делать дальше. И наконец «действует», то есть посылает сигналы на свои моторы.
Смена кинематической модели
В стандартных примерах Simbad роботу сообщается угловая (рад/с) и линейная (м/с) скорость. Но в существующих роботах чаще используется другая, дифференциальная модель, при которой движения робота управляются посредством разности скоростей на моторах. В ней можно задать только скорости двигателей (левого и правого).
Поэтому в программе лучше сразу сменить модель на дифференциальную.
Для начала нужно завести переменную класса «Робот»:
L=10.0 //ширина колесной базы
Объявляется кинематическая модель — тоже как переменная класса «Робот»:
DifferentialKinematic kinematic;
Она инициализируется в конструкторе класса “Робот” с параметром L:
kinematic = new DifferentialKinematic(L);
Там же даётся команда:
setKinematicModel(kinematic);
Теперь скорость задается так:
kinematic.setWheelsVelocity(left, right);
где left, right – скорости на моторах в м/с.
Отрицательное число означает вращение мотора назад.
Работа с источниками света
На сцене располагается 2 источника освещения - две лампы (можно повращать камерой и увидеть их). Источники света в Simbad реализованы не очень удачно. Их нельзя конструировать, можно только менять их параметры в конструкторе среды:
light1IsOn = true;
light1SetPosition(3,1,-3);
light1Color = white;
Аналогично и со вторым источником цвета, только тогда переменные будут вида light2IsOn.
Их лучше переместить так, чтобы было видно; можно поменять цвет лампы.
Работа с датчиками освещённости
К роботу нужно добавить 2 датчика освещённости. Они будут выглядеть как желтые точки слева и справа от робота. Датчики объявляются как переменные класса «Робот»:
LightSensor sensorLeft;
LightSensor sensorRight;
Они инициализируются в конструкторе класса «Робот»:
sensorLeft = RobotFactory.addLightSensorLeft(this);
sensorRight = RobotFactory.addLightSensorRight(this);
Чтобы считать показания датчика света:
float llum = sensorLeft.getAverageLuminance();
float rlum = sensorRight.getAverageLuminance();
Дальше студенты должны догадаться, каким образом нужно использовать показания от датчиков света, чтобы робот ехал к лампе.
Задача 2. Робот, приезжающий в заданную точку
Постановка задачи
Задача является вспомогательной и нужна для того, чтобы сделать следующую задачу с ездой по опорным точкам. На входе алгоритма выдаются координаты точки, в которой должен оказаться робот.
В Simbad есть функция getCoords, дающая глобальные координаты робота. Если робот уже знает свои координаты, то ему остается высчитать свой угол поворота относительно заданной точки, повернуться так, чтобы стоять к ней «лицом», и затем просто приехать в неё по прямой.
Устройство пространства и времени в симуляторе
Необходимо обратить внимание на то, что по умолчанию X и Z — это ширина и длина, а Y — это высота. Время в симуляторе устроено следующим образом: каждые 0.05 секунд (50 миллисекунд) происходит шаг симуляции, в ходе которого робот выполняет то, что задано в функции performBehavior. Это время тоже можно менять по своему усмотрению, но для простых задач вполне хватит и такого.
Алгоритм
Завести переменную для текущего угла
-
Каждый шаг симуляции:
Измерить текущий угол робота: вычислить угловую скорость робота и прибавить к текущему углу шаг времени, умноженный на угловую скорость.
Если робот уже развёрнут по направлению к цели - дать роботу команду ехать вперёд
Иначе:
Найти угол между текущим направлением робота и направлением на заданную точку
Повернуть робота так, чтобы разница между ними стала почти равна нулю. Возможны ситуации, когда робот проскакивает направление: из-за временного шага в 200 миллисекунд на достаточно большой скорости он почти всегда проворачивается мимо. Поэтому необходимо ввести epsilon.
Если робот уже находится на расстоянии delta от заданной точки - остановиться
Дополнительная задача — следование по маршруту из списка точек (ArrayList). Это пригодится в следующей задаче.
Задача 3. Нахождение пути робота на заданной карте методом Дейкстры
Постановка задачи
У робота имеется карта помещения. Заранее неизвестны старт и финиш. На входе робот получает точку, в которую должен попасть. Свои координаты он по-прежнему знает.
В данном случае задача решается при помощи явного задания опорных точек. Эта же постановка задачи будет впоследствии в задаче «Лабиринт», но там опорными точками будут уже все точки, где нет стены.
Способ решения
Можно облегчить роботу задачу и задать некоторое число опорных точек:
(0,0),(0,5),(1,7),(3,0),(3,4),(4,7),(4,10),(6,4),(6,7),(9,10),(10,6),(10,0)
и возможных переходов между ними. Точки и переходы следует выбирать разумно, чтобы робот мог проехать от одной точки к другой, не застряв.
(0,1),(0,3),(1,4),(1,2),(2,5),(3,4),(3,10),(4,7),(5,6), (5,8),(6,9),(7,10),(7,11),(8,7),(9,11),(10,11)
Таким образом, карта превращается в граф. Теперь на этом графе можно применять известные методы поиска кратчайшего пути, такие как метод Дейкстры.
Нет необходимости писать метод Дейкстры с нуля — этот алгоритм достаточно известен, и можно взять любую рабочую реализацию в Интернете. В нашем случае была взята программа с сайта http://algowiki.net на языке C и переделана под Java. Студентам предлагалось доработать эту программу, чтобы она стала применимой для конкретного случая.
Но чтобы найти в этом графе кратчайший путь, список вершин и рёбер нужно представить в виде матрицы смежности. В ячейках матрицы пишутся расстояния между вершинами. Если между вершинами нет ребра – пишется “бесконечное расстояние” (часто задаётся числом вроде 999)
На выходе предлагаемая реализация метода Дейкстры даёт массив preced с числом элементов, равным числу вершин. В этом массиве для каждой вершины указывается предыдущая вершина на кратчайшем пути. Таким образом, двигаясь от конца к началу, можно восстановить весь путь из стартовой вершины. Написать эту функцию студенты тоже должны самостоятельно.
Подзадачи
1. Задать массив опорных точек (Waypoints)
2. Задать возможные переходы между этими точками (Edges)
3. Дописать код в методе Дейкстры (порождение матрицы смежности из списка вершин и рёбер в функции create_adj_matrix)
4. Написать функцию, которая из списка preced создаст путь (ArrayList – список точек)
5. Заставить робота следовать по этому пути, используя предыдущую задачу
Задача 4. Определение координат робота в пространстве путем решения дифференциального уравнения.
Постановка задачи
В данной задаче основной упор делается на то, чтобы студенты поняли, откуда берется уравнение, зачем оно нужно и как оно решается.
Нужно узнать координаты робота в пространстве, основываясь на известных нам данных: скоростях на колёсах и времени.
Решение
Cоставляется и решается простое дифференциальное уравнение.
Получится такое уравнение:
x' = v*sin(th)
y'=v*cos(th)
th' = w
То, что находится в левой части – зависимые от t переменные. t (время) – независимая переменная. Переменные w и v не зависят от t (строго говоря, зависят, но мы упростили задачу). Самое простое – это посчитать текущий угол. Это уже было сделано в задаче 2:
th = th_prev + h*w
Таким образом, третье уравнение системы уже решено (методом Эйлера, хоть мы об этом и не догадывались). Как быть с остальными двумя?
Это уравнение нельзя решить аналитически, потому что оно не принадлежит к известным классам (линейным, с разделяющимися переменными, однородным).
С другой стороны, численные методы можно использовать всегда – даже тогда, когда есть аналитическое решение. Поэтому можно применить численный метод Рунге-Кутты.
Задача 5. Использование пропорционального регулятора для решения задачи езды вдоль стены
Постановка задачи
Имеется составленная из простых блоков стена с различными изогнутыми участками.
Устраивается соревнование — чей робот быстрее проедет вдоль стены.
Подключение ультразвуковых дальномеров
В Simbad есть ультразвуковые дальномеры. Их можно добавить несколько, и тогда они образуют «пояс» вокруг робота. В классе “Робот” заводится переменная:
RangeSensorBelt sonars;
В конструкторе класса “Робот” она инициализируется:
sonars = RobotFactory.addSonarBeltSensor(this, число датчиков);
Считать информацию с датчика:
double cur_dist = sonars.getMeasurement(номер датчика);
При запуске вокруг робота должны появиться чёрточки (датчики). А в панели робота появится новое окошко. Слева красными лучами выделяются активные датчики, справа — численные показания на датчиках.
Использование ультразвуковых дальномеров
Для решения задачи нужно выбрать один или несколько датчиков, снимать с них показания и использовать для движения вдоль стены. Датчик выдаёт значения от 0.0 до 1.5 метров, а дальше – бесконечность (константа Double.POSITIVE_INFINITY), и этот случай нужно отдельно обрабатывать. Вначале проще взять один датчик. Если выбран датчик по диагонали, его значение нужно умножить на косинус угла, под которым стоит датчик, чтобы получить верное расстояние.
Релейный регулятор
Требуемое расстояние до стены вводится как константа (разумно сделать её 1.0, чтобы расчёты были проще). Дальше нужно посчитать текущее расстояние до стены и установить скорости на двигателях. Для соревнования необходимо договориться, что максимальная скорость - не более 1.5 м/с на двигателе. После выполнения задачи нужно зафиксировать время прохождения роботом трассы (lifetime) – как только его координата по X превысит значение, соотвествующее краю карты (на предлагаемой трассе оно равно 1.0).
Пропорциональный регулятор
Задача выполняется аналогично. Считается текущее отклонение от требуемого значения (разница, величина рассогласования). Разница используется, чтобы установить скорости на двигателях. Интересно посмотреть, что будет при разных значения коэффициента пропорциональности: 0.5, 1, 5. Сможет ли робот в конце дистанции обогнуть стену?
Мы устраивали соревнование, и студентам оно очень понравилось. В итоге победу одержала студентка, которая внимательно и тщательно подобрала коэффициент пропорциональности, раз за разом улучшая результат.
Задача 6. Навигация по трём маякам
Постановка задачи
Есть 3 маяка (изображены цветными кубиками). Их робот может видеть при помощи видеокамеры. Он распознаёт цвет кубика и его угол по отношению к роботу. Имея 3 угла и зная координаты маяков, робот должен определить, где он находится в текущий момент.
Реализация распознавания цвета
Распознавание цветных кубиков делается при помощи внешней библиотеки blobDetection (http://v3ga.net/processing/BlobDetection/), которая находится в jar-файле и подключается к проекту аналогично библиотеке Simbad.
Решение
Это сложная геометрическая задача, и её стоит давать в виде готового математического решения, с задачей запрограммировать алгоритм.
Задача 7. Поиск пути в лабиринте
Постановка задачи
Имеется лабиринт, роботу известна карта. Он должен найти кратчайший путь и проехать по нему.
Решение
Лабиринт представляется как булева матрица со значениями true, где есть стена, и false, где её нет. Для отрисовки лабиринта мы использовали алгоритм проекта Algernon (http://sourceforge.net/projects/lemaze/).
Предлагается решить задачу нахождения оптимального пути в лабиринте тремя способами:
Метод А*
Метод Дейкстры
Волновой фронт
Идеально было бы перед тем, как отправлять робота в путь, визуализировать работу алгоритма разноцветными блоками.
Можно не писать алгоритм с нуля, а взять одну из готовых реализаций — их много в Интернете. Необходимо определить, что у метода на входе и что на выходе. У всех методов — по-разному!
Вопрос: как роботу потом ехать по построенному маршруту? Очень просто! Метод выдаёт список точек, мы можем ехать по этим точкам, каждый раз выбирая как целевую очередную точку этого списка. Задача «Езда в точку» уже была.
В общем виде задача выглядит так: на входе есть двоичная матрица — карта лабиринта. Есть стартовая точка и финишная точка. На выходе должен быть путь — набор точек.
Задача 8. Движение по неизвестной карте с датчиками
Постановка задачи
Задача отличается от предыдущей тем, что в ней у робота нет полной карты, и поэтому он должен составлять её по ходу движения. Самый простой способ решить эту задачу — использовать уже известный алгоритм волнового фронта. Предполагается, что у робота есть средства навигации, выдающие ему угол поворота и координаты (это делалось в предыдущих задачах).
Решение
Робот едет и поворачивается в разные стороны, измеряя расстояние до препятствий. Измерения используются для построения грубой карты лабиринта.
Алгоритм
Написать функцию: вход — показание датчика, координаты робота и угол поворота робота, выход - координаты препятствия на карте (клетка, которой оно принадлежит).
Написать функции, при помощи которых робот будет ехать вперёд на заданное число клеток и поворачивать на 90 градусов.
При езде запоминать каждую точку в глобальный массив и закрашивать соответствующую клетку на карте.
Применять wavefront на материале этих измерений в каждой новом клетке
Расширение задачи
Эта задача, как и все остальные, может быть решена в симуляторе, и затем перенесена на мобильного робота. В этом случае на робота потребуется прикрепить ИК-дальномер SHARP GP2D120 на сервомашинке. Датчик должен постоянно вращаться и делать хотя бы 3 измерения на каждые 180 градусов — одно прямо перед собой, два других слева и справа от себя. Для проверки решения, в классе должны быть клетчатая карта и препятствия.
|
