На этот раз я расскажу о роботе LEGO EV3, проходящем лабиринт ТУДА-ОБРАТНО.
Инструкцию по его сборке можно скачать по ссылке в описании. И хотя последовательность сборки, которую генерирует программа Lego Digital Disigner можно назвать странной, но, как видно, робот не очень сложный и даже с такой инструкцией собрать его не вызовет проблем.
Чтоб ещё было понятней ниже 2 фото с видом сверху и снизу.
Вид сверху с откинутым блоком EV3:
Вид снизу:
Задачу прохождения лабиринта ТУДА-ОБРАТНО можно разбить на три этапа:
Прохождение роботом лабиринта ТУДА, то есть от клетки «старт» до клетки «финиш».
Анализ пройденного пути и вычисление оптимального (кратчайшего) пути ОБРАТНО.
По вычисленному пути ОБРАТНО возвращение робота в клетку «старт».
Прохождение роботом лабиринта ТУДА
Для прохождения роботом лабиринта ТУДА воспользуемся известным правилом правой руки.
Смысл этого правила – робот всегда должен держаться правой стены.
Если справа стена, а впереди свободно – делаем шаг вперёд (в нашем случае шаг равен длине стороны клетки лабиринта, то есть 30 см).
Если справа стены нет – поворачиваем направо и делаем шаг вперёд.
Если справа стена и впереди стена – поворачиваем налево и делаем шаг вперёд. При этом полного шага вперёд может и не получиться, и робот наткнётся впереди на стену. Это случится, если робот дошёл до конца тупика. Тогда ещё раз поворачиваем налево и делаем шаг вперёд.
Следуя этому правилу, мы обязательно достигнем конца лабиринта, пройдя при этом все тупиковые ответвления на своём пути.
Но в реальности получается не всё так гладко.
Мы должны держаться правой стены – то есть всё время контролировать расстояние до стены. При этом робот делает неизбежные небольшие отклонения по курсу. Пройти шаг ровно 30 см тоже не всегда удаётся из-за того, что правое и левое колёса хотя немного, но отличаются и по трению, и по размещению на оси и т.д. По этой же причине мы не можем повернуть ровно на 90 градусов при повороте налево или направо. То есть постоянно имеет место небольшая ошибка, которая с течением времени накапливается, и в конце концов наш робот неизбежно собьётся с пути – или наедет на стену, или сделает лишние повороты и т.д.
Чтобы избежать этого мы должны обязательно как-то позиционировать робот посередине клетки и как-то подправлять его угловое положение.
Во-первых, при движении прямо вдоль стены мы должны контролировать расстояние до правой стены в 7 см – этим мы всегда придерживаемся линии, проходящей примерно посередине клеток.
Во вторых, встретив стену прямо, мы упираемся в неё и не сразу отключаем моторы, а через пол секунды. Тем самым мы выравниваем робота перпендикулярно стене, то есть выравниваем его угловое положение. Далее отъезжаем назад на середину клетки и поворачиваем налево. При этом происходит сброс длины шага. Тем самым исключаем нарастающую ошибку по длине шага.
В третьих, если в результате поворотов мы всё же отклонимся от стены более чем на 10 см, то поворачиваемся направо к этой стене, упираемся в неё, выравниваем робота перпендикулярно этой стене, отъезжаем назад на середину клетки и поворачиваем налево.
Благодаря этим трём приёмам, нашему роботу всё же удаётся добраться до клетки финиша.
Анализ пройденного пути и вычисление оптимального (кратчайшего) пути ОБРАТНО.
При прохождении лабиринта ТУДА, робот движется по клеткам, делая всего три типа движения:
Налево
Прямо
Направо
Движения назад при корректировке положения не считаются информативными и в зачёт не идут.
Разворот робота – это два поворота налево подряд.
И каждое такое движение мы должны записывать в массив на всём пути ТУДА:
При повороте налево в массив записывается значение (-1).
При движении прямо на один шаг в массив записывается значение 0.
При повороте направо в массив записывается значение 1.
Пройдя до конца лабиринта, в массиве будут записаны все ходы нашего робота.
Итак, пройдя до конца этот лабиринт, робот записал в массив следующую последовательность ходов:
0, 0, 0, -1, -1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, -1, -1, 0, -1, 0, -1, 0, 0, 1, 0, 1, 0, 0, -1, -1, 0, 0, 1, 0, 1, 0
В этом лабиринте три тупика в клетках A5, B4 и A2.
В массиве, который записал робот, мы видим три пары (-1)(-1).
0, 0, 0, -1, -1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, -1, -1, 0, -1, 0, -1, 0, 0, 1, 0, 1, 0, 0, -1, -1, 0, 0, 1, 0, 1, 0
Именно здесь робот делал два подряд поворота налево. Это и есть разворот в конце тупика.
Рассмотрим ходы робота при прохождении тупика №1:
0, 0, 0, -1, -1, 0, 0, 1
Пара -1, -1 соответствует тупику в клетке А5.
Смотрим команды слева и справа от этой пары и попарно их складываем. Видно, что на всём протяжении тупика сумма равноудалённых от тупика ходов равна нулю:
Пара, сумма значений ходов которой > 0, и является выходом из тупика и соответствует клетке С5.
В данном случае на выходе из тупика сумма Σ = 1.
Давайте рассмотрим ходы робота при прохождении тупика №2:
1, 0, 0, 1, 0, 1, 0, -1, -1, 0, -1, 0, -1, 0, 0, 1
Этот тупик гораздо длиннее, но и для него попарная сумма значений ходов на всём протяжении тупика =0.
И пара, сумма значений ходов которой > 0, и является выходом из тупика и соответствует клетке С3.
В данном случае на выходе из тупика сумма Σ = 2.
В результате видно, что тупики бывают двух видов:
1. Тупик остаётся прямо, нам же перед тупиком надо повернуть налево. Сумма на выходе из тупика Σ = 1.
2. Заход в тупик с поворотом направо, нам же надо двигаться прямо, оставив тупик справа. Сумма на выходе из тупика Σ = 2.
Исходя из этого, сформулируем два правила сокращения тупиковых веток.
Если на выходе из тупика попарная сумма ходов Σ = 1, то есть для этого случая крайняя пара может быть вида (1+0) или (0+1). Тогда правило для этого случая:
Все пары ходов, сумма которых Σ < 1, из массива удаляются.
В крайней паре (1+0) или (0+1) значение 1 заменяется на -1.
Сама изменённая крайняя пара не удаляется.
2. Если на выходе из тупика попарная сумма ходов Σ = 2, то есть для этого случая крайняя пара может быть вида только (1+1). Тогда правило для этого случая:
Все пары ходов, сумма которых Σ < 1, из массива удаляются.
Сама крайняя пара (1+1) также удаляется.
По этим правилам теперь можно составить алгоритм программы оптимизации пути «ОБРАТНО», или удаления тупиковых ответвлений, и по этому алгоритму написать программу для нашего LEGO-робота.
Тут может возникнуть вопрос, а почему после удаления тупика программа начинает проверять путь опять с начала массива (index = 1), а не продолжает с того места, до которого уже дошла. Тогда вроде как можно бы было за один проход удалить все тупики.
Это было бы справедливо, если бы все тупики шли последовательно один за другим.
Но даже в таком простом лабиринте 5х4 можно разместить тупик в тупике, то есть разветвляющиеся тупики.
В таком тупике розовые клетки остаются несокращёнными. То есть путь до разветвления тупиков не удаляется.
Если же после удаления тупика 1,
мы начнём проверять массив с первого (правильнее нулевого) индекса, то ко второму проходу программы после удаления тупика 1 розовые клетки станут частью тупика 2 и поэтому удалятся при оптимизации пути.
А ведь вложенность тупиков может быть и больше двух, то есть тупик в тупике в тупике и т.д.
Поэтому проверку пути после каждого удаления тупика надо обязательно начинать с начала массива и количество проходов программы будет равно числу тупиков на пути до финиша.
Путь ОБРАТНО: возвращение робота в клетку «старт».
На пути «ОБРАТНО» правило правой руки отменяется.
Полученный массив после оптимизации является последовательностью ходов, которую должен выполнить робот, чтобы вернуться в клетку «старт».
Робот считывает этот массив, начиная с последнего элемента и до нулевого, и выполняет записанные в нём команды.
Ход (-1) теперь это поворот направо, ход 1 – поворот налево, ход 0 – остаётся ходом прямо.
При движении «ОБРАТНО» робот также контролирует расстояние до правой стены, и также если это расстояние превысит 10см поворачивается направо, упирается в стену, отъезжает на середину клетки и поворачивается налево.
留言