Out of the Maze | Maqueen Plus Advanced Tutorial Lesson 6

Line-following and maze algorithms are always a classic combination. How can we find the best way out of a complicated maze? We have become known about the basic line-tracking function of Maqueen Plus in the previous chapters, now can we make a project to let Maqueen Plus auto-get through a maze by the left-hand rule? Let’s have a try! The line-tracking map can be used as a maze.

Left-hand Rule: turn left first when arriving at a junction.

Function

In this project, Maqueen Plus will judge the road junction type using its line-tracking sensors. At the cross-junction, T-junction, and left L-junction, Maqueen Plus first turns left. The traveled routes will be memorized, and the best one will be calculated after all routes are recorded. At last, when driving from the starting point again, Maqueen Plus will drive along the best route to reach the endpoint.

Bill of Material

Hardware Connection

1. Connection: connect the OLED screen on the I2C interface.

2. Map: prepare a map like the one below. The calibration area will be the endpoint. The starting points are marked as follows. There are 9 starting points in total.

3. Reform Map: to complete this project, we still have to reform the map above. Hide the short lines of the start points with non-black tape (we use blue tape here). Extend the black area of the endpoint with black tape for improving error tolerance rate, as shown below:

Note: it is recommended to use white tape to hide the lines, for other colors, you’d better apply two layers of tape on them. The intention of hiding the black short lines is to make sure that the detected value is 0 when Maqueen Plus is at the start point.

Knowledge Field

There could be many kinds of junctions in a maze, such as, straight, T junction, cross-junction, dead end. The most common way for traversing mazes is to use the “left-hand rule” or “right-hand rule” to handle all the routes in the maze, and then get the most optimized path, which also means the least time a line-tracking car will take from the beginning to end.

1. What is a Maze Map?

A maze map usually contains a complicated pattern, which is composed of black lines. And there are 8 types of junctions on a maze map: cross, T-junction, left L-junction, right L-junction, straight or go left, straight or go right, start/endpoint, dead end.

2. Strategy for Out of the Maze

①　Left-hand Rule

According to the left-hand rule, the priority level direction for the line-tracking car is: turn left->go straight->turn right. That is to say, in the maze, when arriving at a cross-junction or T-junction(can turn left, go straight or turn right), the line-tracking car always turns left; at the “straight or go right” junction, go straight. It only turns right at the right L-junction.

②　Right-hand Rule

Opposite to the rule above, the right-hand rule follows the priority of right->straight->left, which means that the line-tracking car first turns right at a cross-junction or T-junction; at the “straight or go left” junction, go straight; It only turns left at the left L-junction.

The line-tracking car can get out of a maze in both ways. You can choose the rule you prefer.

Project Practice

The project will be mainly making use of the 6 line-tracking sensors on Maqueen Plus to recognize the road junctions, and then it will determine which way to go based on the recognized result. While, how do we make Maqueen Plus distinguish junction type, and select the corresponding program to execute after that? Let’s find the approaches to these problems step by step in the following Tasks!

Task 1: Basic Line-tracking of 4 Sensors

1. Program Design

Step 1 Function Analysis

Line-tracking is an essential part of a maze traversing project, and 4 line-tracking sensors will be used in the project for improving the error tolerance rate. Then, let’s get to know how to use 4 line-tracking sensors.

The line-tracking sensors need to be calibrated before use.

Step 2 Flowchart Analysis

The function of 4 line-tracking sensors:

Note:

1) The output 0 means no black line is detected, 1 for black line detected.

2) Small, medium, large refer to the speed difference of the two wheels of Maqueen Plus. When the value is small, Maqueen Plus will make a small turn, and so forth.

2. Sample Program

Whole sample program:

Line-tracking Function:

3. Effect Display

Turn on Maqueen Plus’s power switch, put it on the map. Maqueen Plus will drive along the black line, and the frequency of deviating from the black line at the corner gets smaller compared with only 2 line-tracking sensors used.     

1. Program Design

Step 1 Process of Getting Through the Maze

There are 3 steps for Maqueen Plus to complete during the process of getting through the maze.

1. Move forward along the path and detect if there is a junction ahead.

2. Judge the type of junction when a junction is detected.

3. Select the corresponding turning mode after the last step is finished.

The steps above will be executed repeatedly until Maqueen Plus arrived at the endpoint.

Step 2 Junction Recognition and Judgement

Maqueen Plus can drive along the path now after completing Task 1, but it cannot judge the junction or do correct action at each junction. Well, let’s focus on these two points.

As we mentioned before that there are 8 types of junctions in the maze, and now we will analyze them in detail.

Normally, a junction is where two or more roads meet, which means there are over one direction a car can go. So theoretically the left L-junction, right L-junction and dead-end cannot be called a junction. At these positions, Maqueen Plus will only directly turn left/right/around without “judging” which direction to go.

1. Dead End

Dead end is the simplest junction to be recognized and handled. When the sensors L2, L1, R1, R2 all output “0000”, Maqueen Plus arrived at a dead end.

Maqueen Plus has to turn around at the dead end (call function U-turn). As shown below:

2. Right L-junction and “Straight or go right” junction

When encountering these two junctions, the values of line-tracking sensors of L2, L1, R1 and R2 will be “0111”, but how does Maqueen Plus distinguish them?

What we have to do here is to make Maqueen Plus move forward a little bit when the values of the sensors above are “0111”. After the four sensors crossed the junction, detect again, now if the sensor readings of L1 and R1 are both 1, then the junction must be “straight or go right”. If both are 0, it is a right L-junction.

According to the “left-hand rule”, Maqueen Plus has to react as follows at these two junctions:

Turn right (call State when turning right function) at theGo straight or right” junction; Go straight (call State when going straight function) at the “Go straight or right” junction. As shown below:

3. Left L-junction and “Go straight or left” junction

The sensors readings of L1, L2, R1, R2 will be “1110” when Maqueen Plus arrived at these two junctions.

Maqueen Plus has to turn left(call State when turning left function) at both two junctions based on the “left-hand rule”. The flowchart is shown as follows:

4. T-junction and Cross-junction 

The sensor readings of L2, L1, R1 and R2 will be “1111” when Maqueen Plus arrived at a T-junction or Cross-junction. How does it judge the junction type?

Note: when L2 and R2 both output 1, then it must be arriving at “T-junction” or “Cross-junction”.

Similarly, here Maqueen Plus also needs to move forward slightly to cross the junction for  determining the junction type. If L1 and R1 output 1, it must be a “cross-junction; if 0, “T-junction”.

Maqueen Plus needs to turn left at both two junctions as per “left-hand rule”.

5. Endpoint

When arriving at the endpoint, the values of line-tracking sensors of L3, L2, L1, R3, R2, R1 will be “111111”, and Maqueen Plus stop moving at this time.

Note: when L3, L2, R2, R3 all output 1, it arrives at the endpoint.

The related flowchart is shown below:

2. Sample Program

Details of some important functions:

fault_tolerant_L: fault-tolerant function when turning left

fault_tolerant_R: fault-tolerant function when turning right

State when turning left: the left RGB LED keeps on in red when turning left at a junction.

State when turning right: the right RGB LED keeps on in blue when turning right at a junction.

State when going straight: all the RGB LEDs turn on in green when going straight at a junction.

U-turn: all the RGB LEDs keep on in yellow when turning around at a dead end.

Turn R：motor on the right moves forward, motor on the left moves back, turn right.

Turn L： motor on the right moves back, motor on the left moves forward, turn left.

Back： Maqueen Plus moves backward.

go forward： move forward for 0.35 seconds, and the motor stops.

Note: the complete program is attached at the end of the tutorial.

3. Effect Display

Put Maqueen Plus at a starting point, as shown below. The driving routes: start → turn left â†’ turn left â†’ turn right â†’ turn around â†’ turn left â†’ turn left â†’ turn left â†’ turn around â†’ go straight â†’ endpoint.

Project Development

Now, Maqueen Plus can find the optimal route of the maze. If we put it on a more complicated map like the one below, will the learned algorithm work here? If not, what change we have to make? Try calculating the best route of the maze below based on the tips.

Tip: Use black electrical tape to make the maze map.