Solving a Simple Maze

Build Materials (For each team)

Required Materials (enough materials for each team to build a 12 inch square by 2 inch high maze)

• For base:
  • Cardstock
  • Cardboard
• For walls: 
  • Foam sheets
  • Corrugated cardboard
  • Styrofoam
  • Cardstock

Teacher Resource 

Design Challenge

You are a team of engineers given the challenge of selecting materials and building a maze. The maze design will be provided. The finished maze should be no more than 30cm square and 2 inches tall. It should contain 16 cells and have a start (source) and finish (destination). 

Criteria 

• Contains 16 cells
• Copied from the design provided
• Has a source (start) at the bottom left of the maze and a destination (finish) at the top right of the maze

Constraints

• No more than 30 cm square and 2 inches tall
• Use only the materials provided
• Teams may trade unlimited materials

1. Break class into teams of 2-4.
2. Hand out the Solving a Simple Maze worksheet, as well as some sheets of paper for sketching designs. 
3. Discuss the topics in the Background Concepts Section. To set the scene, show students any video of micromouse/maze solving robot (see Digging Deeper section). Instruct students to think about what makes the robots actually drive toward the destination on its own. This will help introduce them to the understanding of algorithms. 
4. Review the Engineering Design Process, Design Challenge, Criteria, Constraints and Materials. 
5. Share the photo of the maze shown in the Materials Section under Teacher Resource. Tell students their challenge is to determine what materials they will use to design the same maze. While they are brainstorming about their design, they should think about the steps it will take for a robot to complete the maze and document how those steps are numbered. They should also determine a start and end to the maze.  
6. Provide each team with their materials.
7. Announce the amount of time they have to design and build (1 hour recommended). 
8. Use a timer or an on-line stopwatch (count down feature) to ensure you keep on time. (www.online-stopwatch.com/full-screen-stopwatch). Give students regular “time checks” so they stay on task. If they are struggling, ask questions that will lead them to a solution quicker. 
9. Students meet and develop a plan for building their maze. They agree on materials they will need and write/draw their plan. Teams may trade unlimited materials with other teams to develop their ideal parts list.
10. Teams build their mazes. They should mark the start of the maze (the source) and the end of the maze (the destination) with a marker. Then, they should number the rows of the maze beginning with “1” for the “source” and moving across the bottom row and then moving to the next row. The “destination” should be labeled “16.” A diagram of the numbering is shown in the Teacher Resources.
    
11. Instruct students to imagine a robot is moving through their maze from the “source” to the “destination.” They should think about what the robot sees and document the path the robot will take by writing the sequence of numbers down. As the students are documenting the path, ask them to consider:
    • Does the robot know the numbers beforehand and it knows the destination number it needs to reach before stopping?
    • Does the robot start from the source and check to see which path is open, looking to the right, left, front, and back before moving? Once it finds the open path, then it moves to the next cell? When it reaches the next cell, it checks to see if that cell is “16?” If it isn’t, will it again check the path and move forward to an empty cell until it reaches “16,” then stop?
12. As a class, discuss the student reflection questions.
13. For more content on the topic, see the “Digging Deeper” section.

Extension

As an extended activity, have students change the maze from the standard design to one of their own. Encourage them to think about any modifications their algorithms will require for the new maze. Mention they may want to be careful not to design a maze with dead ends or loops. If their design contains these, the algorithm will need to keep a record of the previous path. When there is only one path, only the previous cell needs to be recorded. 

Student Reflection (engineering notebook)

1. Did you succeed in building the maze based on the figure given to you? If not, why?
   
2. Did you succeed in arriving at the solution for the maze? In other words, were you able to give the robot proper ‘instructions’ such that it could reach the destination? If not, why?
3. Did you negotiate any material trades with other teams? How did that process work for you?
   
4. Once you started building the maze, did you decide to change materials or add more materials?
5. Do you think that engineers have to stick to their original plan during the building stage? Why?
   
6. Do you think that the “building” stage helped you visualize the problem very clearly? If yes, how did it help you in solving the problem?
   
7. If you were working alone, would you have been able to complete the project easier? Explain.
8. Based on this activity, what do you think of algorithm development? Explain.

The lesson can be done in as little as 1 class period for older students. However, to help students from feeling rushed and to ensure student success (especially for younger students), split the lesson into two periods giving students more time to brainstorm, test ideas and finalize their design. Conduct the testing and debrief in the next class period.

It has been so many years since the challenge of maze solving robots came up. So many people in the past developed and demonstrated various models for the same. If you think the basic problem statement, you will be reminded of your childhood days where you were challenged to help a mouse find its route towards the destination, in a maze. The maze got complicated structure as you grew up!!!… So, have you ever imagined a real scenario, where you could make a mouse intelligent enough to solve the maze by its own? As technology evolved further such that intelligent robots can be developed, this problem has got its own place. That is how micromouse has become a standard problem statement. You can go back home and search for the problem statement, or even you can search in YouTube for videos, where people demonstrate their own bots solving the maze. Hey!! It’s not only about solving the maze, but to solve it in the shortest possible time… Oh!! Yes, the problem gets complicated as you grow up.. But, to get started with the world of ‘artificial intelligence and robotics’, let’s think of a simple maze and move towards the ultimate mission. You may forget about the hardware part. There is something, which doesn’t have any limit; it’s our imagination, our way of thinking towards solving a problem. Yes!! It’s all about software development. Software development for such activities is merely based on algorithms. By the way, what is an algorithm?? It is nothing but ‘step by step’ procedure in completing a mission. So, are you ready to tackle the problem?

• Algorithm: A set of guidelines that describes how to perform a task. Think of an algorithm as step-by-step instructions that create a predictable pattern in a set of numbers or in lines of code.
• Artificial Intelligence: The theory and development of computer systems able to perform tasks that normally require human intelligence, such as visual perception, speech recognition, decision-making, and translation between languages.
• Constraints: Limitations with material, time, size of team, etc.
• Criteria: Conditions that the design must satisfy like its overall size, etc.
• Engineers: Inventors and problem-solvers of the world. Twenty-five major specialties are recognized in engineering (see infographic).
• Engineering Design Process: Process engineers use to solve problems. 
• Engineering Habits of Mind (EHM): Six unique ways that engineers think.
• Iteration: Test & redesign is one iteration. Repeat (multiple iterations).
• Maze: A path or collection of paths, typically from an entrance to a goal.
• Prototype: A working model of the solution to be tested.

Internet Connections

• http://www.youtube.com/watch?v=xrF4v28AOlc
• http://www.youtube.com/watch?v=H5F1nfFgBdI

Recommended Reading

• http://en.wikipedia.org/wiki/Maze_solving_algorithm
• http://www.astrolog.org/labyrnth/algrithm.htm#solve

Writing Activity 

Read the Wikipedia page on maze solving algorithms and the Astrolog page on types of mazes and write a summary of the different approaches. Pick one of the approaches and list its strengths in terms of criteria such as complexity (simple is better) and speed (faster is better)

Alignment to Curriculum Frameworks

Note: Lesson plans in this series are aligned to one or more of the following sets of standards:  

• U.S. Science Education Standards (http://www.nap.edu/catalog.php?record_id=4962)
• U.S. Next Generation Science Standards (http://www.nextgenscience.org/) 
• International Technology Education Association’s Standards for Technological Literacy (http://www.iteea.org/TAA/PDFs/xstnd.pdf)
• U.S. National Council of Teachers of Mathematics’ Principles and Standards for School Mathematics (http://www.nctm.org/standards/content.aspx?id=16909)
• U.S. Common Core State Standards for Mathematics (http://www.corestandards.org/Math)
• Computer Science Teachers Association K-12 Computer Science Standards (http://csta.acm.org/Curriculum/sub/K12Standards.html)

Principles and Standards for School Mathematics

As a result of activities, all students should develop

Geometry Standard

• Specify locations and describe spatial relationships using coordinate geometry and other representational systems
• Use visualization, spatial reasoning, and geometric modeling to solve problems

Problem Solving Standard

• Apply and adapt a variety of appropriate strategies to solve problems.
• Solve problems that arise in mathematics and in other contexts.

Representation

• Use representations to model and interpret physical, social and mathematical phenomena

Common Core State Standards for School Mathematics Grades 3-8 (ages 8-14)

Operations & Algebraic Thinking

• Generate and analyze patterns.
• CCSS.Math.Content.4.OA.C.5 Generate a number or shape pattern that follows a given rule. Identify apparent features of the pattern that were not explicit in the rule itself. For example, given the rule “Add 3” and the starting number 1, generate terms in the resulting sequence and observe that the terms appear to alternate between odd and even numbers. Explain informally why the numbers will continue to alternate in this way.

Standards for Technological Literacy – All Ages

The Nature of Technology

• Standard 2: Students will develop an understanding of the core concepts of technology. 

CSTA K-12 Computer Science Standards Grades 6-9 (ages 11-14)

5. 2 Level 2: Computer Science and Community (L2)

• Computational Thinking (CT)

3. Define an algorithm as a sequence of instructions that can be processed by a computer.
4. Describe and analyze a sequence of instructions being followed (e.g., describe a character’s behavior in a video game as driven by rules and algorithms).
5. Examine connections between elements of mathematics and computer science including binary numbers, logic, sets and functions.

• Collaboration (CL)

2. Collaboratively design, develop, publish, and present products (e.g., videos, podcasts, websites) using technology resources that demonstrate and communicate curriculum concepts.
3. Collaborate with peers, experts, and others using collaborative practices such as pair programming, working in project teams, and participating in group active learning activities.
4. Exhibit dispositions necessary for collaboration: providing useful feedback, integrating feedback, understanding and accepting multiple perspectives, socialization.

• Collaboration (CL)

3. Collaborate with peers, experts, and others using collaborative practices such as pair programming, working in project teams, and participating in group active learning activities.

• Computing Practice & Programming (CPP)

4. Demonstrate an understanding of algorithms and their practical application.

Design your own maze and solve it..

You are working as a team of engineers who have been given the challenge to design a maze using the materials given to you, and then solve it. By this time, you might have already seen what a maze looks like, and some interesting maze solving robots. Before jumping into the real game, let’s get started with building the maze. As you have seen, the maze consists of a platform and walls fitted onto it. Once you build your own maze with the dimensions suggested by your teacher, you will have to solve the maze – coming up with a step by step procedure you can give to the robot such that it can travel from source to destination. The maze has sixteen cells. The source is at the left bottom cell of the maze and the destination is at the right top of the maze.

Planning

As a team, discuss among yourselves how to go about building the maze. You will have to decide what all materials you need. You can get them from your teacher. You may return materials, exchange materials with other teams. Consult with your teacher, if you need any clarification or doubts at this stage.

Building

Take the material you use for the platform, say, the cardboard. Using the pencil or sketch pen, draw a layout of the maze on the platform. Share materials with other teams to build your maze. This is team work and it is important that you discuss among your team members and enjoy the spirit of working in a team. Share your thoughts and share your work. Listen to your friends, and help them out.  Be sure to watch how other teams have designed their maze and how different the mazes are, compared to yours.

Solving

Now it’s time to start solving the maze. Take down the path in terms of the cell numbers, through which a mouse (a robot) has to travel to the reach the destination from the source. Now, think what made you arrive at your solution. Describe the logic behind your solution. Discuss among your friends and write it down.

It’s important to think of the solution in terms of numbers.  You can see the whole maze, and think about how to get from the source to the destination.  However, you are much smarter than the robot.  The robot cannot see the destination or understand the whole maze – the robot just knows the number of its current position and the numbers of the neighboring squares it can move to.

This is the real problem, how do you describe the solution to the robot? The robot doesn’t know how to solve the maze. It only knows the source number is 1, and destination number is 16. So you have to give the robot a set of instructions such that the robot reaches the destination. Take down the instructions; consult your teacher for verification.

When you are doing this, think about how your solution would work if the maze was constructed differently.  It is easy to design a solution if you know the maze beforehand, and simple tell the robot the moves it requires.  However, can you come up with a solution that would work no matter what the pattern of the maze was?  Can you think of ways of testing your solution?

Evaluation

Use this worksheet to evaluate your team’s results in this lesson.

1. Did you succeed in building the maze based on the figure given to you? If not, why?

2. Did you succeed in arriving at the solution for the maze? In other words, were you able to give the robot proper ‘instructions’ such that it could reach the destination? If not, why?

3. Did you negotiate any material trades with other teams? How did that process work for you?

4. Once you started building the maze, did you decide to change materials or add more materials?

5. Do you think that engineers have to stick to their original plan during the building stage? Why?

6. Do you think that the “building” stage helped you visualize the problem very clearly? If yes, how did it help you in solving the problem?

7. If you were working alone, would you have been able to complete the project easier? Explain.

8. Based on this activity, what do you think of algorithm development? Explain.