Week 9

By admin On February 24th, 2010

Week 9: Finishing the Intelligent Maze Robot, and Graph Theory

Finishing the Maze Robot

Let's finish our maze solving robot. Now that we've generated our goodChoices list, we need to make the robot turn around and get back to the starting point, only making the choices which are in the goodChoices list. Here's how we'll make our robot do that:

When the robot reaches an intersection, it will check to see if it's in the list goodChoices. Here's how to test to see ifa particular element is in a list:

if something in myList:

print "Yup, it's in there!"

else:

 print "Not in there"

If something is inside myList, the above code will print out "Yup, it's in there!" else, it'll spit out "Not in there". Use this method to test to see if the current position, as retrieved by get_position(), is inside goodChoices.

Note that when initially solving the maze, we used the following logic:

  • If the right is clear, turn right
  • elif the front is clear (i.e., if the right is not clear but the front is clear), go forward
  • else (i.e., if none of the above are true), turn left.

When solving the maze in reverse, we'll need to reverse the logic. Note that the above logic tells the robot to follow the wall on the right — you'll need to tell the robot to follow the wall on the left in order to retrace his steps. Here's how we do that:

  • If the left is clear, turn left.
  • elif the front is clear, go forward
  • else, turn right

Here's how we'll use the information we've stored up in goodChoices:

  • If the left is clear, and the current position is in goodChoices, turn left.
  • elif the front is clear, and the current position is in goodChoices, go forward
  • else, turn right (Note that we don't need to check to see if this is a good choice… because it's the only choice we have left).

But what if the current position is not in goodChoices? We'll make the robot avoid the choice he would have normally have made and proceed to evaluate his other options. That is:

  • If the left is clear, do the following:
    • If the current position is in goodChoices, turn left.
    • else, do the following:
      • If the front is clear, go forward.
      • Else, turn right.
  • elif the front is clear, do the following:
    •  If the current position is in goodChoices, go forward.
    • Otherwise, turn right.
  • else, turn right.

Graph Theory

I'm sure you're all familiar with connect-the-dots. Graph theory is the study of more advanced connecting the connect-the-dots, known as graphs.

Here's the steps used to make a graph from a maze:

  1. Draw a dot at every intersection in the maze. Number the dots — you can number them any way you want.
  2. On a separate page (i.e., not on the maze), draw those dots again. Then, connect the dots — whenenever it's possible to get from one intersection to another (without passing through any other intersection), draw a line between the two dots.
  3. Count the number of spaces required to move between any two intersections — write this number next to the line connecting the two respective dots.