Симулятор прохождения лабиринта по линии с LSRB

Управление

Режим выбирает между полным запуском из трёх актов — исследование, упрощение и быстрое прохождение — и переходом сразу к готовому маршруту. Скорость выполнения задаёт скорость движения робота. Пуск, Пауза и Шаг запускают его непрерывно или по одному ходу, Сброс повторяет тот же лабиринт, а Новый лабиринт создаёт новый. Установите фокус на холсте и используйте Space, N, R, M и F для тех же элементов управления с клавиатуры.

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

Теория

Робот для прохождения лабиринта по линии состоит из двух слоёв, и именно их разделение делает задачу управляемой.

Нижний слой — обычный робот, следующий по линии. Восьмиканальный массив датчиков отражения считывает ленту, показания сводятся к одной взвешенной ошибке, а контур ПИД-регулятора превращает её в две разные скорости колёс. Этот слой ничего не знает о лабиринтах.

Верхний слой просыпается только тогда, когда лента ветвится. Он классифицирует перекрёсток — левая ветвь, правая ветвь, T-образный перекрёсток, крестовина, тупик или финиш — выбирает ветвь по правилу левой руки и добавляет один символ к строке. Линейка, нарисованная поперёк передней части корпуса робота в этом симуляторе, — это массив датчиков; вы можете видеть, как при ветвлении загорается целая его сторона.

Нюанс в том, что мгновенное показание неоднозначно. T-образный перекрёсток, перекрёсток четырёх направлений и блок финиша сообщают, что все каналы чёрные. Робот должен проехать за перекрёсток и считать показания ещё раз, прежде чем узнать, через что он только что проехал.

Алгоритм

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

Каждый ход добавляет символ. L, S и R — повороты; B появляется только там, где робот выходил задним ходом из тупика. Поэтому каждый B в готовой строке отмечает ошибку вместе с поворотом перед ним и после него.

Это трёхсимвольное окно всегда можно заменить одним поворотом, потому что три поворота в сумме дают угол. Если считать поворот налево как −90°, прямо как 0°, направо как +90°, а назад как 180°, то L B L даёт 0°, то есть S: проехать прямо, вообще не заходя в боковую ветвь. Шесть правил подстановки — это та же арифметика, представленная таблицей.

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

Исходный код

// Repeat until a full pass changes nothing: collapsing one detour
// can push two turns together that are themselves reducible.
void simplify(String& route) {
  bool changed = true;
  while (changed) {
    changed = false;
    for (int i = 1; i + 1 < route.length(); i++) {
      if (route[i] != 'B') continue;          // windows centre on a turn-back
      route = route.substring(0, i - 1)
            + fold(route[i - 1], route[i + 1])
            + route.substring(i + 2);
      changed = true;
      break;
    }
  }
}

fold — это таблица подстановок, и она короткая, поскольку представляет собой только арифметику углов: складываются два поворота по обе стороны от разворота на 180°, результат переносится в диапазон ±180° и сопоставляется с символом.

Допущения и отличия от реального оборудования

Лента отображается идеально чёрной на идеально белом фоне без заломов, бликов и теней, а массив датчиков отражения сообщает идеальные двоичные значения на фиксированной высоте. Реальный массив IR видит отражения в оттенках серого, которые меняются вместе с освещением, высотой датчиков и износом ленты, поэтому перед каждым реальным запуском необходимо откалибровать белый и чёрный цвета, как указано в разделе о соединениях. Симулятор также запускает контур ПИД-регулятора с идеальным периодом и продвигает одну чистую клетку за одно решение; на Arduino появляются дрожание цикла, проскальзывание колёс и смещение при монтаже 2 mm, которые приводят к неверной классификации перекрёстков. Переносите сюда коэффициенты и строку LSRB, а не числа.

Схема соединений

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

Главное правило соединений касается разделения питания. Аккумулятор двигателей подключается только к выводу VM драйвера; 5 V Arduino питает только логику; все общие провода — плата, драйвер, массив датчиков и отрицательный вывод аккумулятора — должны быть соединены, иначе управляющие сигналы не имеют общей точки отсчёта, а отказ будет незаметным.