Hardware components | ||||||
 |
| × | 1 | |||
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 SolvedMAZE-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.
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.
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.
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.
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.
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.
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.
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.
The wings and fins are only for decoration.
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.
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.
Comments