Практикум по спецкурсу «Введение в робототехнику» (стр. 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:// на языке 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:///processing/BlobDetection/), которая находится в jar-файле и подключается к проекту аналогично библиотеке Simbad.

Решение

Это сложная геометрическая задача, и её стоит давать в виде готового математического решения, с задачей запрограммировать алгоритм.

Задача 7. Поиск пути в лабиринте

Постановка задачи

Имеется лабиринт, роботу известна карта. Он должен найти кратчайший путь и проехать по нему.

Решение

Лабиринт представляется как булева матрица со значениями true, где есть стена, и false, где её нет. Для отрисовки лабиринта мы использовали алгоритм проекта Algernon (http:///projects/lemaze/).

Предлагается решить задачу нахождения оптимального пути в лабиринте тремя способами:

1)  Метод А*

2)  Метод Дейкстры

3)  Волновой фронт

Идеально было бы перед тем, как отправлять робота в путь, визуализировать работу алгоритма разноцветными блоками.

Можно не писать алгоритм с нуля, а взять одну из готовых реализаций — их много в Интернете. Необходимо определить, что у метода на входе и что на выходе. У всех методов — по-разному!

Вопрос: как роботу потом ехать по построенному маршруту? Очень просто! Метод выдаёт список точек, мы можем ехать по этим точкам, каждый раз выбирая как целевую очередную точку этого списка. Задача «Езда в точку» уже была.

В общем виде задача выглядит так: на входе есть двоичная матрица — карта лабиринта. Есть стартовая точка и финишная точка. На выходе должен быть путь — набор точек.

Задача 8. Движение по неизвестной карте с датчиками

Постановка задачи

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

Решение

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

Алгоритм

Написать функцию: вход — показание датчика, координаты робота и угол поворота робота, выход - координаты препятствия на карте (клетка, которой оно принадлежит).

Написать функции, при помощи которых робот будет ехать вперёд на заданное число клеток и поворачивать на 90 градусов.

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

Применять wavefront на материале этих измерений в каждой новом клетке

Расширение задачи

Эта задача, как и все остальные, может быть решена в симуляторе, и затем перенесена на мобильного робота. В этом случае на робота потребуется прикрепить ИК-дальномер SHARP GP2D120 на сервомашинке. Датчик должен постоянно вращаться и делать хотя бы 3 измерения на каждые 180 градусов — одно прямо перед собой, два других слева и справа от себя. Для проверки решения, в классе должны быть клетчатая карта и препятствия.