a1tD0000007kdmLIAQ

Course: Introduction to Programming with Ozobot
4) Maze Solving Algorithm

  • 6-12 grade
  • Intermediate

Lesson Description:

Objectives: 

1) Write a program that would solve a maze in the most effective way.
2) Write a program that would solve a variety of mazes in the most effective way.
3) Track and analyze the benefits and drawbacks of different algorithms to solve mazes.

image description

Lesson Modules


Teaching Tips:

This lesson will take about 2 hours to complete. You may have to split the lesson into multiple classes.



Materials:


• One Ozobot per student/group (suggestion: 2-3 students per group)
• One computer for each student/group
• Teacher computer
• Internet connection
• Projector
• printer

  • 1 timer per student group (often students can use their cell phones)

Preparation:


• Make sure Ozobots are charged before beginning the lesson

• Print ONE copy of each of the following mazes PER student/group.

Maze 1

Maze 2

Maze 3

Maze 4


Observation activity:

1) Have students go to their computers and answer the questions 1&2.

2) Once all of the students have submitted their responses click the “show results” button under question 1 on the class view to show the results. Facilitate a class discussion about their responses.
Answer: Seattle, Minneapolis, Chicago, Washington DC, New York

3) Have students share the process they did to get to their answer for question 1.

4) Once students have shared, facilitate a discussion about processes that would have been ineffective to find an answer to the question and explain why those processes would be ineffective. (ex: calculating the distance for every single possible path would be ineffective because it would take a lot of time and it is obvious that some paths would be a long distance).

5) Have students think about real life examples of when this process is done.
Ex: Google Maps

In this section we will begin to think about how algorithms work.



Which route is the shortest distance between Seattle and New York?
  • Seattle, Minneapolis, Chicago, Washington DC, New York
  • Seattle, Denver, Dallas, Washington DC, New York
  • Seattle, Denver, Dallas, Miami, New York
  • Seattle, Minneapolis, Chicago, Boston, New York

Explain the process you did to identify the shortest route.


Teaching Tips:

1) Show the students’ goals on the class view.

2) Hand out a copy of maze 1 to each student/group.
3) Go to the next section of the class view and have students write a program that has Ozobot solve this maze.

This maze exists in the examples section of the right toolbar. In this section, you can click the button “open example” and a successful code for that activity will automatically load onto the workspace. If students do this then they are not problem solving and learning how to program. Try to reduce the risk of students using the tutorial page to build their program.

4) Once students finalize their maze solving program, have them time how long it takes Ozobot to complete the maze and track that information on THIS document.

5) Show the next section on the class view (bird’s eye versus in-maze) and facilitate a class discussion: Is it easier to solve a maze when you have a bird’s eye view or an in-maze view? Explain why. (Answer: Bird’s eye view is easier because you have all of the information about the maze and thus can plan more accurately.)

In this section we will build a program which is an algorithm to solve a maze.


Teaching Tips:

1) Show the students’ goals on the class view: 1) Write a program that would solve a variety of mazes from an in-maze view in the most effective way. 2) Track and analyze the benefits and drawbacks of different algorithms to solve in-maze view mazes.

2) Then show the students the challenge with the step by step directions on the class view.


During the design time, walk around and prompt your students with questions to help deepen their learning and thinking process. Some examples of questions are:
• Why did you make that design decision?
• What do you predict your code will do?


Here is an example of an effective strategy to solve mazes


Wall follower/ right-hand rule


Once all the students have tracked the results of their maze solving program through responding to the questions on their computer, you can show their results to the class by clicking on the "Show Results" button at the bottom of questions 4-7. Show the class the results and facilitate a conversation about the benefits and drawbacks of different strategies.

In this section you will build an algorithm and test its effectiveness.


Describe your program for solving the mazes.


Explain why you think your maze solving program will work.




How many blocks are there in your program?

Time to track the results of your algorithm.



How many minutes did it take Ozobot to solve maze 2? (Answer in ONE word)



How many minutes did it take Ozobot to solve maze 3? (Answer in ONE word)



How many minutes did it take Ozobot to solve maze 4? (Answer in ONE word)


Teaching Tips:

Have students answer the following questions on their computers. Once all the students have finished answering the questions have a class discussion about their answers.

1. Explain a change you made in your maze solving program while testing it.
2. Explain the difference between solving a maze you have a bird’s eye view of versus an in-maze view.

Have students plug their Ozobots into their chargers.

In this section we will reflect on our learning.


Explain a change you made in your maze solving program while testing it.

Explain the difference between solving a maze you have a bird’s eye view of versus an in-maze view.


Plug your Ozobot in so it will be ready for you to use next time.