Одним из видов соревнований по робототехнике является прохождение роботом лабиринта. Сегодня мы представляем простую модель, собранную на базе домашней версии EV3. Эту модель и программу вы можете использовать как пример для собственной модели робота. Это даст вам возможность принять участие в соревнованиях, которые проходят во многих крупных городах Украины.
Итак, начнем.
1) Скачайте архив с инструкцией по сборке
2) Распакуйте его в любую папку.
3) Запустите файл «Building Instructions [MazeSolver].html»
4) В бровзере откроется инструкция для сборки конструкции.
5) Скачайте программу для робота
6) Запустите среду программирования Lego Ev3 и загрузите файл «MazeSolver.ev3″
7) Подключите робота к ПК и загрузите программу в робота.
Робот готов. Поставьте его рядом со стеной (датчик расстояния должен смотреть в стену).
9) Выберите на блоке управления загруженную программу с названием «index» и запустите ее.
Описание принципа работы
Робот использует два датчика:
— датчик касания (кнопка) для определения препятствия спереди
— датчик расстояния (в нашем случае удьтразвуковой, который можно заменить на инфракрасный) для определения препятствия справа.
После старта программы робот начинает двигаться вперед вдоль препятствия справа. Если препятсвие далеко (более 4 см), то он поворачивает вправо, приближаясь к препятствию. Если препятствие близко (менее 4 см), то робот поворачивает влево, удалясь от препятствия. Таким образом робот все время движется вдоль препятствия справа на одном расстоянии. Если препятсвие справа отсутсвует (поворот), то робот старается найти его и поворачивает вправо, пока не обнаружит его.
Если же препятствие будет спереди, то при его достижении сработает датчик касания (кнопка). В этом случае робот отъезжает назад, поворачивается влево на 90 градусов и включает алгоритм движения вдоль препятствия. И так по циклу.
Если переставить датчик расстояния на другую сторону, то робот будет двигаться вдоль препятствия слева.
Мы собрали два примера лабиринта для демонстрации.
Это базовая модель, которую вы можете улучшить, изменив некоторые параметры программы или усовершенстовав конструкцию.
До встречи в роболабиринтах!
Обновлено: 29 нояб. 2020 г.
На этот раз я расскажу о роботе 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см поворачивается направо, упирается в стену, отъезжает на середину клетки и поворачивается налево.
▼Инструкция по сборке робота ▼
▼Программа labirint.ev3▼
▼Блок-схема алгоритма оптимизации массива пройденного пути▼
1. Движение в лабиринте
2. Диаграмма состояний
3. Поворот направо
Срабатывает
датчик
Поворот
одним колесом
Поворот вокруг своей оси
4. Поворот направо
Смещаем датчик
назад
или в середину
5. Поворот направо
Перед началом поворота проезжаем немного вперед
6. Поворот направо
После поворота сдвигаемся
Немного вперед
Если видим пролом,
значит объезжаем
перегородку
7. Поворот налево
Для обнаружения преграды спереди
устанавливаем второй датчик
8. Блок-схема
9. Программа EV3
Introduction: AI in LEGO EV3 Maze-Driving Robot
This is a simple, autonomous robot with some artificial intelligence. It is designed to explore a maze and when placed back at the entrance, to drive thru to the exit and avoid the dead ends. It is much more complicated than my previous project, which simply drove thru the maze. Here, the robot must remember the path it has travelled, remove dead-ends, store the new path, and then follow the new path.
My previous robot is described here: https://www.instructables.com/id/LEGO-Robot-Drives-Thru-a-Maze
The robot is built using LEGO Mindstorms EV3. The EV3 Software runs on a computer and generates a program, which is then downloaded to a microcontroller called an EV3 Brick. The programming method is icon-based and high-level. It’s very easy and versatile.
Supplies
PARTS
- LEGO Mindstorms EV3 set
- LEGO Mindstorms EV3 ultrasonic sensor. It’s not included in the EV3 set.
- Corrugated cardboard for the maze. Two cartons should be sufficient.
- A small piece of thin cardboard to help stabilize some corners and walls.
- Glue and tape to connect cardboard pieces together.
- A red greeting-card envelope to identify the exit of the maze.
TOOLS
- Utility knife to cut the cardboard.
- Steel ruler to aid the cutting process.
SOFTWARE
The program is here: https://github.com/Tony-file/myEV3maze
Step 1: How a Maze Is Solved
MAZE-DRIVING METHOD
There are several methods of navigating a maze. If you are interested in studying them, they are described very well in the following Wikipedia article: https://en.wikipedia.org/wiki/Maze_solving_algorithm
I chose the left-hand wall-following method. The idea is that the robot will keep a wall on its left side by making the following decisions as it goes thru the maze:
- If it’s possible to turn left, do so.
- Otherwise, go straight if possible.
- If it can’t go left or straight, turn right, if possible.
- If none of the above are possible, this must be a dead end. Turn around.
One caution is that the method could fail if the maze has a loop in it. Depending on the placement of the loop, the robot could keep going around and around the loop. A possible solution for this problem would be for the robot to switch to the right-hand wall-follower rule if it realized that it was going in a loop. I didn’t include this refinement in my project.
SOLVING THE MAZE TO FIND A DIRECT PATH
While driving thru the maze the robot must memorize the path it is travelling and eliminate dead-ends. It accomplishes this by storing each turn and intersection in an array, checking for specific combinations of turns and intersections as it goes, and replacing the combinations that include a dead-end. The final list of turns and intersections is the direct path thru the maze.
The possible turns are: Left, Right, Back (at a dead-end), and Straight (which is an intersection).
Combinations are replaced as follows:
- «Left, Back, Left» becomes «Straight.»
- «Left, Back, Right» becomes «Back.»
- «Left, Back, Straight» becomes «Right.»
- «Right, Back, Left» becomes «Back.»
- «Straight, Back, Left» becomes «Right.»
- «Straight, Back, Straight» becomes «Back.»
HOW THE ROBOT HANDLES MY MAZE
- When the robot starts driving it sees a space to the right and stores Straight in the list in the array.
- Then it turns left and adds Left to the list. The list now contains: Straight, Left.
- With a dead end, it turns around and adds Back to the list. The list now contains: Straight, Left, Back.
- Passing the lane it used from the entrance, it adds Straight to the list. The list now contains: Straight, Left, Back, Straight. It recognizes a combination and changes Left, Back, Straight to Right. The list now contains Straight, Right.
- With a dead end, it turns around and adds Back to the list. The list now contains: Straight, Right, Back.
- After the left turn the list contains Straight, Right, Back, Left. It recognizes a combination and changes Right, Back, Left to Back. The list now contains Straight, Back.
- After the next left turn the list contains Straight, Back, Left. It changes that combination to Right. The list now contains only Right.
- It passes a space and adds Straight to the list. The list now contains Right, Straight.
- After the right turn the list contains Right, Straight, Right which is the direct path.
Step 2: Considerations When Programming the Robot
CONSIDERATIONS FOR ANY MICROCONTROLLER
When the robot decides to turn it should either make a wide turn, or go forward a short distance before turning and after turning go forward a short distance again without checking the sensor. The reason for the first short distance is that the robot shouldn’t bump into the wall after the turn, and the reason for the second short distance is that after the robot has turned, the sensor would see the long space it had just come from, and the robot would think it should turn again, which is not the proper thing to do.
When the robot senses an intersection on the right but it’s not a right turn, I have found that it’s good to have the robot drive forward about 10 inches (25 cm) without checking its sensors.
CONSIDERATIONS SPECIFIC TO LEGO MINDSTORMS EV3
Although LEGO Mindstorms EV3 is very versatile, it allows no more than one of each type of sensor connected to one Brick. Two or more Bricks could be daisy-chained, but I didn’t want to buy another Brick, and so I used the following sensors (instead of three ultrasonic sensors): infrared sensor, color sensor, and ultrasonic sensor. This worked out well.
But the color sensor has a very short range, of about 2 inches (5 cm), which leads to a few special considerations as described below:
- When the color sensor detects a wall in front and the robot decides to turn right or turn around, it should back up first, in order to give itself enough space to turn without bumping into the wall.
- A complicated issue occurs with some “Straight” intersections. Because of the short range of the color sensor, the robot cannot determine whether it senses a proper “Straight” intersection or the lead-up to a right turn. I have tried to fix this issue by setting the program to store a “Straight” in the list every time the robot senses one, and then eliminate more than one “Straight” in a row in the list. This fixes the situation where a right turn follows a “Straight” in the maze but not the situation where there is a right turn without a “Straight” before it. I also tried setting the program to eliminate a “Straight” if it is just before a “Right” but this doesn’t work if a right turn follows a “Straight”. I haven’t been able to find a solution that fits all cases, altho I suppose it would be possible for the robot to look at the distance travelled (by reading the motor rotation sensors) and decide whether it’s a “Straight” or a right turn. I didn’t think this complication was worth doing for the purposes of demonstrating the AI concept in this project.
- An advantage of the color sensor is that it distinguishes between the brown of a wall and the red of the barrier I used at the exit, and provides an easy way for the robot to decide when it has finished the maze.
Step 3: The Main Program
LEGO Mindstorms EV3 has a very convenient icon-based programming method. Blocks are shown at the bottom of the display screen on the computer and can be drag-and-dropped into the programming window to build a program. The EV3 Brick may be connected to the computer by either a USB cable, Wi-Fi or Bluetooth, and the program may then be downloaded from the computer to the Brick.
The program consists of a main program and several “My Blocks” which are subroutines. The uploaded file contains the entire program, which is here: https://github.com/Tony-file/myEV3maze
The steps in the main program are as follows:
- Define and initialize the turn-counting variable and the array.
- Wait 5 seconds and say “Go.”
- Start a loop.
- Drive thru the maze. When the exit is reached, the loop is exited.
- Display on the Brick’s screen, the intersections found in the maze so far.
- Check if the path should be shortened.
- Display the intersections in the shortened path.
- Loop back to step 4.
- After the loop, drive the direct path.
The screen shot shows this main program.
Step 4: The My Blocks (Subroutines)
The Navigate My Block, which controls how the robot drives thru the maze, is shown. The print is very small and may not be legible. But it’s a good example of how versatile and powerful are the if-statements (called Switches in the LEGO EV3 system).
- Arrow #1 points to a Switch that checks if the infrared sensor sees an object more than a specific distance away. If so, the top series of blocks is executed. If not, then control is passed to the large, bottom series of blocks, where arrow #2 is located.
- Arrow #2 points to a Switch that checks what color the color sensor sees. There are 3 cases: no color at the top, red in the middle, and brown at the bottom.
- Two arrows #3 point to Switches that check if the ultrasonic sensor sees an object more than a specific distance away. If so, the top series of blocks is executed. If not, then control is passed to the bottom series of blocks.
The My Blocks for shortening the path and for driving the direct path are more complicated and would be totally illegible, and so they aren’t included in this document.
Step 5: Starting to Build the Robot: the Base
As mentioned previously, LEGO Mindstorms EV3 allows no more than one of each type of sensor connected to one Brick. I used the following sensors (instead of three ultrasonic sensors): infrared sensor, color sensor, and ultrasonic sensor.
The pairs of photos below show how to build the robot. The first photo of each pair shows the parts needed, and the second photo shows the same parts connected together.
The first step is to build the base of the robot, using the parts shown. The robot base is shown upside-down. The small L-shaped part at the back of the robot is a support for the back. It slides as the robot moves. This works okay. The EV3 kit doesn’t have a rolling-ball-type part.
Step 6: Top of the Base, 1
ThIs step and the next 2 steps are for the top of the base of the robot, the color sensor, and the cables, which are all 10 inch (26 cm) cables.
Step 7: Top of the Base, 2
Step 8: Top of the Base, 3
Step 9: Infrared and Ultrasonic Sensors
Next, are the infrared sensor (on the left side of the robot) and the ultrasonic sensor (on the right). Also, the 4 pins for attaching the Brick on top.
The infrared and ultrasonic sensors are located vertically instead of the normal horizontal. This provides better identification of the corners or ends of the walls.
Step 10: Cables
The cables connect to the Brick as follows:
- Port B: left large motor.
- Port C: right large motor.
- Port 2: ultrasonic sensor.
- Port 3: color sensor.
- Port 4: infrared sensor.
Step 11: Final Step in Building the Robot: Decoration
The wings and fins are only for decoration.
Step 12: Build a Maze
Two corrugated cardboard cartons should be sufficient for the maze. I made the maze walls 5 inches (12.5 cm) high, but 4 inches (10 cm) should work just as well if you’re short of corrugated cardboard.
First, I cut around the walls of the cartons, 10 inches (25 cm) from the bottom. Then I cut around the walls 5 inches from the bottom. This provides several 5-inch walls. Also, I cut around the bottoms of the cartons, leaving about 1 inch (2.5 cm) attached to the walls for stability.
The various pieces can be cut and glued or taped wherever needed to form the maze. There should be an 11 or 12 inch (30 cm) space between the side walls in any path with a dead end. The length should be no less than 10 inches (25 cm). These distances are needed for the robot to turn around.
Some of the corners of the maze may need to be reinforced, Also, some straight walls need to be kept from bending if they include a straightened carton corner. Small pieces of thin cardboard should be glued to the bottom at those places, as shown.
The exit has a red barrier consisting of half a red greeting-card envelope and a base made from 2 pieces of thin cardboard, as shown.
Step 13: The Maze
One caution is that the maze should not be large. If the robot’s turns are at a slight angle from the proper one, the discrepancies add up after a few turns and the robot could run into the walls. I had to fiddle several times with the Rotations settings of the turns in order to get a successful drive thru even the small maze I made.
A way around that issue is to include a path-straightening routine that would keep the robot a specific distance from the left wall. I didn’t include this. The program is complicated enough as it is, and it is sufficient for demonstrating the AI concept in this project.
CONCLUDING REMARK
This was a fun project and a great learning experience. I hope you also find it interesting.
Dep-courses
- РЕГИСТРАЦИЯ
- ВОЙТИ
- НОВОСТИ
- ЭКСПЕРТЫ
- НАПРАВЛЕНИЯ
- СОРЕВНОВАНИЯ
- РЕЕСТР
- ГЛАВНАЯ
- — РЕГИСТРАЦИЯ
- — ВОЙТИ
- — НОВОСТИ
- — 3D-МОДЕЛИРОВАНИЕ
- — ГРАФИЧЕСКИЙ ДИЗАЙН
- — ПРОГРАММИРОВАНИЕ
- — ЭЛЕКТРОНИКА
- — РОБОТОТЕХНИКА
- СОРЕВНОВАНИЯ
- РЕЕСТР
E-mail
Dep-courses@ya.ru
LEGO MINDSTORMS EV3 семь инструкций по сборке.
Конвеер-сортировщик шариков
Робот сортирует шарики по двум корзинам.
СКАЧАТЬ ИНСТРУКЦИЮ
Вездеход
Робот на гусеницах
СКАЧАТЬ ИНСТРУКЦИЮ
Машина с пониженной передачей
В конструкции используется передача для увеличения силы
СКАЧАТЬ ИНСТРУКЦИЮ
Робот-чертежник
Робот рисует разметку
СКАЧАТЬ ИНСТРУКЦИЮ
Робот манипулятор
Робот позволяет перемещать объекты в ограниченном пространстве.
СКАЧАТЬ ИНСТРУКЦИЮ
Робот-бот
Простой бот для программирования передвижения.
СКАЧАТЬ ИНСТРУКЦИЮ
Робот-сортировщик
Робот программируется при помощи цветных квадратиков
СКАЧАТЬ ИНСТРУКЦИЮ
Политика в отношении обработки персональных данных
Обновлено: 29 нояб. 2020 г.
На этот раз я расскажу о роботе 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см поворачивается направо, упирается в стену, отъезжает на середину клетки и поворачивается налево.
▼Инструкция по сборке робота ▼
▼Программа labirint.ev3▼
▼Блок-схема алгоритма оптимизации массива пройденного пути▼