mmouse

1.

Регламент категории “Лабиринт”
КОР 2020/2021г
Категория “Лабиринт”
Размер лабиринта: 9 x 9 ячеек
Финишная
ячейка
соревнований
задается
в
день
Время для решения лабиринта: 10 минут.
После
тренировки
все
попадают
в
карантин
перестраивается
микромыши
и
лабиринт
Во время совершения попыток команда не
может перепрограммировать робота.
Разрешается:
чистка
конструктивных
элементов робота, переключение режимов
работы, замена источника энергии и
устранение механических повреждений.

2.

Решение лабиринта
Основная задача - решить
лабиринт за наименьшее время
Решить лабиринт – найти путь от
стартовой до финишной(целевой)
ячейки
Решений лабиринта может быть
несколько.
Не всегда наименьший путь оптимальное решение.
Необходимо учитывать скорость
пробега по прямой и на поворотах.

3.

Финишная (целевая) ячейка
Варианты расположения финишной ячейки :
с привязкой к периметру
лабиринта
без привязки к периметру
лабиринта

4.

Общий подход к решению
Выделяют два этапа в решении
лабиринта:
Исследование и построение карты
лабиринта. Робот пытается
исследовать, как можно большую
область ( Explorer mode ).
Нахождение оптимальных путей и
быстрый пробег робота ( Fast Run
mode ).

5.

Инструменты для решения
лабиринта
4 ИК датчика : FL, DL, DR, FR
энкодеры моторов (12 тиков на один оборот мотора)
моторы N20
гироскоп и акселерометр (отсутствуют)
регуляторы движения мыши
алгоритмы поиска и оптимизации пути

6.

Регуляторы движения мыши в
лабиринте
Варианты
регулятора движения
в коридоре
по правой
стенке
по левой
стенке
к передней
стенке

7.

Регулятор движения мыши между
стенками
Lspeed = BASE_SPEED + (DL - DGOAL) * kPd
Rspeed = BASE_SPEED + (DR - DGOAL) * kPd
DL, DR – показание диагональных датчиков
BASE_SPEED - базовая скорость
DGOAL – целевое значение для
диагональных датчиков
kPd – коэффициент
м
DL
DR

8.

Регулятор движения мыши по одной
стенке (правой или левой)
По правой стенке:
Rspeed = BASE_SPEED + (DR - DGOAL) * kPd
Lspeed = BASE_SPEED - (DR - DGOAL) * kPd
DR – показание правого диагонального датчика
BASE_SPEED - базовая скорость
DGOAL – целевое значение для диагональных
датчиков
kPd – коэффициент
DL
DR

9.

Регулятор выравнивания мыши по
передней стенке
Lspeed = (FGOAL_LEFT - FL) * kPf
Rspeed = (FGOAL_RIGHT - FR) * kPf
FL, FR – показание фронтальных датчиков
BASE_SPEED - базовая скорость
FGOAL_LEFT, FGOAL_RIGHT – целевое
значение для фронтальных датчиков
kPf – коэффициент
FL
FR

10.

Регулятор выравнивания мыши по
энкодерам
countR = getRightEncoder()
countL = getLeftEncoder()
Lspeed = BASE_SPEED + (countR - countL) * kPs
Rspeed = BASE_SPEED + (countL - countR) * kPs
BASE_SPEED - базовая скорость
countR, countL – текущие значения правого и левого
энкодеров
kPs – коэффициент

11.

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

12.

Основные команды движения
робота
Команда
Функция
Кодировка в пути
Вперед
moveDistance
‘F’
Правый поворот
turnRight
‘R’
Левый поворот
turnLeft
‘L’
U – разворот
Uturn
‘B’
Пример пути для режима Fast Run:
“BFFFRRLFLS”
‘B’ – начало последовательности пути
‘S’ – конец последовательности пути

13.

Способы представления лабиринта
Лабиринт – это граф. К нему применимы способы
представления графов.
Матрица смежности вершин
Список смежности вершин
Недостатки: накладные расходы по памяти для
хранения дополнительных атрибутов (посещаемость,
вхождение в путь и т.д.).
Одномерный(двумерный) массив, c кодированием
стенок

14.

Кодировка ячеек лабиринта
XXPVWSEN
бит
назначение
Биты ячейки
N=1
северная стенка
E =2
восточная стенка
S =4
южная стенка
W=8
западная стенка
V =16
посещаемость
N
W
E
P = 32 присутствие в пути
X
зарезервировано
0xB(11)

15.

Алгоритм следования по стенке
Правило правой или левой руки –
самый простой алгоритм
исследования и решения
лабиринта
Не гарантирует решение
Решает лабиринты только, где цель
привязана к периметру
В некоторых случаях получается
очень длинный путь
После этого алгоритма можно
применять алгоритмы поиска
оптимального пути (поиск в ширину
- BFS)

16.

Алгоритм следования по стенке c
построением карты и оптимизацией
Строим карту лабиринта
Оптимизируем путь
следования:
⮚ исключаем тупиковые ячейки
⮚ исключаем циклы в пути