Instructions for mazePolicies

Click here to toggle highlighting for goal links

Note that this week, both tasks count separately towards the project credit. In other words, you need to do both of them, instead of just picking one.

This task involves using conditionals to specify a policy for a robot to find a goal in a maze. The actual code you need to write is fairly simple, but you will need to understand the problem setup in order to write it correctly.

This task is an exercise in writing a small piece of code that will become part of a larger and more complicated system, as well as a chance to practice thinking about how to achieve a complex result via simple behavior rules.

In this task, a maze is a two-dimensional grid of tiles, where each tile is either a wall (through with the robot cannot move) or an open (non-wall) tile in which the robot can be positioned and through which it can move. The maze is represented by a multi-line string in which characters represent the state of a tile:

• A hash character (#) represents a wall;
• A space character indicates an open tile without anything in it;
• A G character indicates the open tile containing the goal that the robot is trying to find; the G turns into an S (success) if the robot moves into this tile.
• The robot's position and heading in an open tile of the maze are represented by one of the four arrow characters (<, ^, >, or v, depending which direction it is facing).
• A dot (.) character indicates an open tile that the robot has visited before.

A trivial maze looks like this:

######
#>  G#
######

Here is a more complicated maze:

########
#     ##
# #^# G#
########

The robot leaves a trail of dots behind when it moves, so after some exploration, the same maze might look like this:

########
#....>##
#.#.# G#
########

Some mazes may contain areas in which some open tiles do not directly touch walls, and the goal may be in one of these tiles. Here is an example:

##########
#        #
#    #v  #
#  G  #  #
#        #
##########

When the goal is not touching a wall, it is more difficult for the robot to find.

The robot has sensors on all four of its sides that can detect whether or not the adjacent tile on that side contains a wall. So it can detect whether there is a wall immediately in front of it, immediately to its left or right, or immediately behind it. It can also detect whether any of these four adjacent tiles contains the goal or has been previously visited by the robot. However, the robot CANNOT see the map of the whole maze like we can, so it cannot see which direction to go in to get to the goal unless the goal is adjacent to it. Your goal is to develop a policy that will work from the robot's perspective to solve the maze.

As described in more detail below in the Background section, the robot can use the sensor information to, in one step, turn towards an adjacent open tile and move forward into that tile.

The robot starts with a certain amount of fuel (an integer), and each step consumes one unit of fuel. It stops moving when it runs out of fuel.

The robot's goal is to navigate through the maze to reach the G before it runs out of fuel. If it moves into the tile with the G, the simulation stops, and that tile is marked S to indicate that the robot succeeded.

Background

We have given you a file maze.py which implements this maze world, and your task is to write the rules that the robot will use to decide how to move. (We have provided code that will use those rules to move the robot, and you don't need to understand or even look at this code.)

A set of rules for moving the robot is called a policy, and is implemented using a function. A policy function has 5 parameters:

1. The character in the tile directly in front of it;
2. The character in the tile directly to its right;
3. The character in the tile directly behind it;
4. The character in the tile directly to its left;
5. An integer indicating how much fuel is left (each unit of fuel allows the robot to move once).

Parameters 1-4 are what the robot can sense from the four adjacent tiles. Each is one of the following one-character strings: '#' (a wall), ' ' (a space, indicating an unoccupied open tile the robot has not visited before), '.' (a previously visited open tile), or 'G' (a tile with the goal).

Policy functions must return one of the four special values from maze.py that indicate a direction to (possibly turn towards and) move in, all in one step:

• maze.FORWARD: take a step forward into the tile robot is facing;
• maze.RIGHT: turn right 90 degrees and move forward one tile after turning;
• maze.BACKWARD: turn 180 degrees and move forward one tile after turning;
• maze.LEFT: turn left 90 degrees and move forward one tile after turning.

If a policy function returns any other value by accident, even just None, the robot will explode (indicated by an error), and the simulation ends.

If the value returned by a policy function attempts to move the robot into a tile containing a wall the robot will not explode, but also will not be able to move into that tile. In this situation, the policy may have changed the direction of the robot. For example, consider the following state of a maze:

########
#...  ##
#v#.# G#
########

If in this state the robot's policy returns maze.RIGHT, it can turn to its right, but cannot move into the tile with the wall that's in front of it after turning. In this case, the state of the maze after one step would be

 
########
#...  ##
#<#.# G#
########

For this task, you only need to write several policy functions. You don't need to write the code to move the robot or draw/print the maze. (We've provided that code in maze.py.)

Here's an example of a very simple policy which goes forward and turns around if it cannot go forward:

def turnAroundPolicy(ahead, right, behind, left, fuel):
    """
    The turnAroundPolicy always moves forward unless there's a wall ahead,
    in which case it turns 180 degrees and attempts to move in that direction.
    It is very bad at solving mazes!
    """
    if isNotWall(ahead): # there's no wall in front of us: go forward
        return maze.FORWARD # keep going forward
    else: # otherwise go back
        return maze.BACKWARD # tell the robot to go backwards

turnAroundPolicy uses a supplied helper function isNotWall, a predicate that takes a one-character string as its single argument and returns True if that character is not the wall string '#'; otherwise it returns False.

The maze.py file defines functions traceSurroundings, animateText, and animateTurtle, each of which take four parameters: a maze, a policy, a fuel budget, and an animation speed, and they provide different ways to simulate the robot's movement through the maze:

• traceSurroundings prints out two lines for each step the robot takes. See the example of traceSurroundings for the bouncePolicy you are asked to define below. The first line describes the robot's current surroundings, including any walls or visited locations, the goal if it's adjacent, and which direction the robot is facing. This is the same information that's available to the robot's policy function via the 5 parameters (the fuel remaining is not printed, but can be inferred from the step number). The second printed line states what decision the robot makes in the situation described, based on the chosen policy. This trace helps you understand the robot's perspective and can help you figure out why it does something unexpected. The trace will also print the maze twice: once at the beginning of the trace and once at the very end.
• animateText simply prints out the maze repeatedly after every step the robot takes, allowing you to watch its progress in the shell, and once it's done, you can still scroll up to see exactly where it was at each step. See the example of animateText for the bouncePolicy you are asked to define below.
• animateTurtle is similar to animateText, except it uses the turtle module to draw the robot in the maze, instead of just printing out the maze as text. This might make it easier to see the details of what's going on, but there is no history available once the animation is done. See the example of animateTurtle for the bouncePolicy you are asked to define below.

Your Job

All policies will be expressed in the file mazePolicies.py, and you will modify only this file. You do not need to view the library file maze.py. You may use the provided test_mazePolicies.py file to test your policies.

You must create the following three policies (in the mazePolicies.py file):

1. A bouncePolicy that always moves forward if it can; otherwise, if there's an open tile to the left, it turns left and moves into it; if it's also blocked by a wall on the left but not on the right, it turns right and moves forward; and if it's blocked by walls in front and to the left and right, it turns 180 degrees and moves in the opposite direction. This policy can solve labyrinths (corridor-based mazes without branches) but it gets stuck in most true mazes.

   Your bouncePolicy must use a conditional and it must use the isNotWall function to determine where walls are, and it must not use the isNotVisited function. It should not use the == or != operators to perform any comparisons..

   We have included examples of how bouncePolicy is supposed to behave using traceSurroundings, animateText, and animateTurtle.

2. A leftWallPolicy that uses a conditional to implement the left-hand rule for solving mazes: always keep your hand on the left wall as you seek the goal. Specifically, the leftWallPolicy should do the following:

   • If there is no wall to the left, turn left and move one step in that direction.
   • If there is a wall to the left and there is no wall in front, move forward.
   • If there are walls on the left and ahead, but there is no wall to the right, turn right and move one step in that direction.
   • If there are walls to the left, ahead, and to the right, give up by backtracing: turn 180 degrees and move on step in that direction.

   This policy, although it isn't that different from the bounce policy, can actually solve any maze that doesn't include an open area (i.e. consists only of a network of corridors).

   Your leftWallPolicy must use the isNotWall function to determine where walls are, and it must not use the isNotVisited function and it must not use the == or != operators to perform any comparisons..

   See an example of how the leftWallPolicy is supposed to behave using traceSurroundings, animateText, and animateTurtle.

3. A customPolicy, which works however you wish, but which must obey the following restrictions:

   • It must include at least one if statement of its own..

   • It must be possible for it in some case to call and return the result of either leftWallPolicy or bouncePolicy.. This call should be placed in an elif or else branch as a fallback or default behavior.

   • As an extra goal, your customPolicy should be able to solve at least three of the six harder mazes (mazes 7-12) defined in maze.py (given 100 fuel). If your customPolicy uses randomness, it counts as being able to solve a maze if it can solve it at least 50% of the time.

Supplied Helper Functions

The following two helper functions are already defined in mazePolicies.py. You must use isNotWall in your bouncePolicy and leftWallPolicy functions, and in those two functions you must not use isNotVisited. You also must not use == or != for comparisons . But you may use any of isNotWall, isNotVisited, == and != in your customPolicy function.

def isNotWall(tile):
    """
    Returns True if the given tile is NOT a wall.
    """
    return tile != '#'


def isNotVisited(tile):
    """
    Returns True if the given tile is not a wall and hasn't been visited
    (either it's blank or it's the goal).
    """
    return tile == ' ' or tile == 'G'

Randomness

In your customPolicy function, you may want to make certain decisions randomly. E.g., if the tiles to the front, left, and right are all open, you might want to chose one of these three directions randomly with equal probability.

The mazePolicies.py file imports the random module to help with this. One particularly useful function in this module is random.randint, which takes two integer arguments (where the first is <= the second) and returns an integer between the two numbers (inclusive). So random.randint(0,1) returns one of 0 or 1, each of which with probability 1/2; random.randint(1,3) returns one of 1, 2, or 3, each of which with probability 1/3; and so on.

To choose between n options with equal probability, it's a good idea to store the result of random.randint(1,n) in a variable and check for each option in a chained conditional. Here's an example where n is 4:

randVal = random.randint(1,4)
if randVal == 1: 
  ... option 1 code here ...
elif randVal == 2: 
  ... option 2 code here ...
elif randVal == 3: 
  ... option 3 code here ...
else: 
  ... option 4 code here ...

Testing

The file test_mazePolicies.py includes testing code. You will have to follow the directions in that file to edit it in order to test your code, as by default it only tests the turnAroundPolicy.

Note that this task does not use optimism for fully automatic testing: you will have to inspect the results of the tests yourself to determine if things are working or not.

Mazes Used in Testing

Here are the twelve sample mazes used in testing (They are defined in maze.py). To satisfy the extra goal, your customPolicy must be able to complete at least 3 of the six mazes numbered 7 through 12. If you are using randomness, being able to finish a maze at least 50% of the time counts as completing it.

MAZE1:
######
#    #
# ## #
#G#> #
######

MAZE2:
#######
#     #
# ### #
#  <#G#
#######

MAZE3:
#######
#v#   #
# # # #
#   #G#
#######

MAZE4:
#########
# # #G# #
# # # # #
#   <   #
#########

MAZE5:
#########
# # #G# #
# # # # #
#   >   #
#########

MAZE6:
#########
# #     #
#   # # #
# ### ###
# ^#   G#
#########

MAZE7:
##################
#v#     #   ##   #
# # ###   #    # #
#     ##### # ## #
# ### #     #  ###
#   ### ######   #
# # ##   #   ### #
# # G# # # #     #
##################

MAZE8:
##########
#        #
#    v#  #
# G#     #
#        #
##########

MAZE9:
#######
#     #
#     #
#  G  #
#     #
#^    #
#######

MAZE10:
#########
#>      #
#       #
#       #
##     ##
###   ###
### G ###
###   ###
#########

MAZE11:
###########
###     ###
###     ###
###  G  ###
###     ###
###     ###
### ### ###
###     ###
##       ##
#         #
#         #
#>        #
###########

MAZE12:
###############
#             #
#   #######   #
#             #
# # # ### # # #
# #         # #
# # #     # # #
# # #  G  # # #
# # #     # # #
# #         # #
# # # ### # # #
#             #
#   #######   #
#>            #
###############

Notes

• As usual, all of your functions must be documented.

• Also as usual, you must not waste fruit. However, the "don't waste boxes" rule is not in effect in this problem, because your policies may not examine all of the parameters they are given.

• Your policy function will be called once for every step the robot takes to decide what to do, getting fresh arguments each time based on the robot's current surroundings. Each time it returns a value, that value is used to move the robot, and 1 fuel unit is used up. If there is a wall blocking the selected direction, the robot will turn to face that direction but it will not move, and a unit of fuel will still be expended. If the robot runs out of fuel (based on the fuel budget given to the traceSurroundings, animateText, or animateTurtle function) then it has failed to solve the maze.

• Because your code is being used by a larger system to make decisions, it doesn't make sense for you to use any kind of loop, and you are not allowed to do so. The code in maze.py takes care of the looping part of the problem. So none of bouncePolicy, leftWallPolicy or customPolicy may use a loop.

• Each of the first four parameters to the policy function can be tested by passing it into isNotWall or (only in customPolicy) isNotVisited, or you can test their values directly (only in customPolicy). The turnAroundPolicy has an example of how to use isNotWall.

• If your policy function returns None, the simulation will crash. You need to make sure that this cannot possibly happen, no matter which branch(es) of which conditional(s) end up being used.

• You can use the maze.leftOf, maze.rightOf, and maze.reverseOf functions to get direction values relative to other directions. Each of these is a fruitful function that returns the relevant value (so for example, maze.leftOf(maze.FORWARD) will return maze.LEFT).

• You can use maze.randomDirection() to get a random direction value.