a1tD0000007kes5IAA

Course: Free Lessons
Scratch with Autonomous Cars - Maze Solving Algorithms

  • 1-5 grade
  • Beginner

Lesson Description:

Learn about how computers solve mazes and program your own maze solving algorithm.


 

Standards Covered

image description

Lesson Modules


Teaching Tips:

To start the lesson today and generate interest in the topic, we will start with a question. The question introduces the the theme of maze solving algorithms. If time permits, discuss the "algorithms" students create in their heads to solve problems like the maze above. Ask them to talk out their process if they can.

Question 1: If you said "using an algorithm" you'd be correct!  People can look at the whole maze at once, and then look at each part by itself.  Your car can’t do that.  It can only see and make choices based on what’s right in front of it.

Have you ever solved a maze before?

Try working out this one now:

How did you do that?  

Do you know the set of steps you took?  Maybe you went down a path in your mind before you started, or maybe you just figured it out as you wrote it down!  



How would a computer solve this maze?  



 

In the next section we will look at some of the algorithms robots like the RobotLAB Autonomous car use to get through a maze.


 


Teaching Tips:

If possible, make a maze of your own before class to show students.  

The class will need:

  1. Large sheets of white or light colored paper
  2. Pens
  3. The box for the Autonomous Car

As you may have guessed, in this lesson we will build a maze and program the RobotLAB Autonomous car to solve it.


Here are some example mazes so you can get some ideas:

      


In order for your maze to work, it needs to be big enough for the robot to move around inside it.  Here’s how to make sure the car has enough space:


Take a large sheet of paper, and place the car on it.

Make sure the car is turned off, then turn the front wheels to the left as far as they will comfortably go.


Try pushing the car along with your hand.  You will see the car turn as sharply as it can.  


Hold a pen in your hand as you turn the car.  

Now you have captured how the car turns.  


Do the same on the other side.  (For my measurement, I put the pen right behind the front wheel)


Your maze will probably be sharp rather than curved, so it will be easier to make your template with sharp edges.  

An easy way to do that is to draw straight lines from the outer edges of the upper curve, and from the center of the inner curve.

The box your car came in is a good reference for how wide your path should be.

You may want to widen the part after the turn to match.

Finally, you can cut your template out and use it to draw a maze!

         

Remember to keep your maze simple.


 


Teaching Tips:

Here is the code: Lesson 8 Code

Here is a Step-by-Step guide to complete the code: Lesson 8 Code Instructions


This simualtion can model many possible mazes.

Here is the solution to the Task 1 (default) maze that shows when the simulation is first loaded:


The code below may seem like the correct answer, but if you run it you will find that the car turns to a parking spot (dead end) before it reaches the intersection:

There are many maze solving algorithms, and different ones work better for different robots.  Here are four of the most common ones.


Random mouse

  1.  Go down a path.
  2. When you reach a place where you have to turn, pick a path at random and go that way.

This algorithm can take a very long time, but it requires very little memory.  It usually works, but it is possible that this algorithm will never stop, and the mouse will never reach the end.

Here are some examples of what could happen when using the Random Mouse algorithm:

         


Wall Follower 

  1. Choose a random starting direction.
  2. At each intersection, take the right turn. At dead-ends, turn around.

This algorithm will work faster than the random mouse, but it can get stuck!


Here are some examples of what could happen when using the Wall Follower algorithm:
         


Tremaux’s algorithm

  1. Pick a direction, draw a line behind you to mark where you have been.
  2. When you reach a place where you have to turn and you haven't visited it before, pick a new passage at random.
  3. When you hit a dead end, turn around and go back the way you came.
  4. If you encounter a place you have marked once, go back the way you came (and mark your path a second time).


All passages will either be empty (haven't visited yet), marked once (gone down it exactly once), or marked twice, (gone down it and backtracked). Paths marked once will indicate a direct way back to the start.





Teaching Tips:

Run each of the programs multiple times to show how the result of the Random Mouse is different every time, while the Wall Follower remains the same.

Here is the correct answer for how to implement the Wall Follower on the Autonomous car:

https://www.robotlab.com/hubfs/Education.Robotlab.com/Autonomous%20Car/Scratch/lesson8scratch.sb2

In the last module you learned about 3 popular maze solving algorithms.  They all have their merits, but which one is the best for our purposes?  Take a look at the first two:


Random mouse

  1. Go down a path.
  2. When you reach a junction, pick a path at random and go that way.

Here is an example of that algorithm using Scratch:



Wall follower (can be left or right-hand)

  1. Choose a random starting direction.
  2. At each intersection, take the rightmost turn. At dead-ends, turn around.

Here is an example of that algorithm using Scratch:




Which algorithm would you rather use?
  • Random Mouse
  • Wall Follower
  • Tremaux's


The Random Mouse is very simple, but there is a chance that it will not solve the maze.  The Wall Follower is a little harder to do, but it works much better.


Try turning this Wall Follower algorithm into an algorithm for your car.


Here are some blocks that may help you: 
 


Teaching Tips:

Question 1: What was the coolest thing you learned today?  Write your answer in the box, and see it appear with your classmates answers!
Any answer will do here.  If time permits, have a short discussion with students about their answers.
 

Question 2: Check the concepts you understand.  Don’t worry, this isn’t for a grade, it’s just so your teacher can check the classes’ understanding.
This is the students' self-assessment of their understanding of the material.  You will see a bar graph once all the poll answers are submitted.
 

Question 3: What is an algorithm?
An algorithm is a set of (specific) rules a computer follows to complete a task.  (Anything similar to this answer is correct.)


Question 4: In your own words, give all the steps for one of the maze solving algorithms you learned today (or if you want, create your own!)
(One of these in the student's own words is correct.  A unique invention is also acceptable even if it wouldn't work on the real robot).

Random mouse

  1.  Go down a path.
  2. When you reach a place where you have to turn, pick a path at random and go that way.

Wall Follower 

  1. Choose a random starting direction.
  2. At each intersection, take the right turn. At dead-ends, turn around.

Tremaux’s algorithm

  1. Pick a direction, draw a line behind you to mark where you have been.
  2. When you reach a place where you have to turn and you haven't visited it before, pick a new passage at random.
  3. When you hit a dead end, turn around and go back the way you came.
  4. If you encounter a place you have marked once, go back the way you came (and mark your path a second time).




What was the coolest thing you learned today?  Write your answer in the box, and see it appear with your classmates answers!


Check the concepts you understand.  Don’t worry, this isn’t for a grade, it’s just so your teacher can check the classes’ understanding.
  • Algorithm
  • Wall-Follower
  • Random Mouse


What is an algorithm?


In your own words, give all the steps for one of the maze solving algorithms you learned today (or if you want, create your own!)