Instructions for seekGoal

(produced at 19:20 UTC on 2021-10-05)

This task is part of ps04 which is due at 23:59 EDT on 2021-10-05.

You have the option to work with a partner on this task if you wish. Working with a partner requires more work to coordinate schedules, but if you work together and make sure that you are both understanding the code you write, you will make progress faster and learn more.

You can submit this task using this link.

Put all of your work for this task into the file seekGoal.py
(which is provided among the starter files)

This task involves using simple conditionals to specify a strategy 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 (nonwall) tile in which the robot can be positioned and through which it can move. The maze is represented by a multiline 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 adjoining 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 adjoining tiles contains the goal or has been previously visited by the robot.

As described in more detail below in the Background section below, the robot can use the sensor information to, in one step, turn towards an adjoining 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 adjoining 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 seekGoal.py, and you will modify only this file. (You do not need to view the library file maze.py.)

You must create the following three policies (in the seekGoal.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 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 bouncePolicy is supposed to behave using traceSurroundings, animateText, and animateTurtle.

  2. A leftWallPolicy that implements 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:

Supplied Helper Functions

The following two helper functions are already defined in seekGoal.py. You must use isNotWall in your bouncePolicy and leftWallPolicy. In those two functions, you must not use isNotVisited and 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 seekGoal.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. E.g., 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

There are numerous commented out test cases at the bottom of the file. You can uncomment one or a few of these at a time to test your code every time you run it. This is usually better than interactive testing, because there's no risk that you forget to re-run the code after making a change.

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.)


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 doesnt_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.

Examples

bouncePolicy traceSurroundings Example

This example shows the text printed out by traceSurroundings for bouncePolicy on the maze MAZE3. In this maze, the robot moves back and forth along three corridors which are parallel and connected at their ends to form a hallway traveling south, then north, then south again from the robot to the goal.

Note that in the function call to traceSurroundings, bouncePolicy is used as an argument to traceSurroundings without any parentheses or argument expressions following it. This means that we are not calling bounceFunction to return a result. Rather, we are using the function itself as an argument to traceSurroundings. animateText, and animateTurtle also take the policy functions themselves as arguments.

In []:
maze.traceSurroundings(maze.MAZE3, bouncePolicy, 40, 25)
Prints
Tracing surroundings with 40 fuel in the following maze: ####### #v# # # # # # # #G# ####### Step 0: Facing south. Three walls north, east, and west. Decision: forward. Step 1: Facing south. Two walls east and west. Visited north. Decision: forward. Step 2: Facing south. Two walls south and west. Visited north. Decision: left. Step 3: Facing east. Two walls north and south. Visited west. Decision: forward. Step 4: Facing east. Two walls east and south. Visited west. Decision: left. Step 5: Facing north. Two walls east and west. Visited south. Decision: forward. Step 6: Facing north. Two walls north and west. Visited south. Decision: right. Step 7: Facing east. Two walls north and south. Visited west. Decision: forward. Step 8: Facing east. Two walls north and east. Visited west. Decision: right. Step 9: Facing south. Two walls east and west. Visited north. The goal is to the south! Decision: forward. Step 10: The robot has reached the goal. Found the goal! Hooray! The final maze state is: ####### #.#...# #.#.#.# #...#S# #######

bouncePolicy animateText Example

This example shows the text printed out by animateText for bouncePolicy on the maze MAZE3 described above.

In []:
maze.animateText(maze.MAZE3, bouncePolicy, 40, 25)
Prints
Animating maze movement with 40 fuel: Step 0 ####### #v# # # # # # # #G# ####### Step 1 ####### #.# # #v# # # # #G# ####### Step 2 ####### #.# # #.# # # #v #G# ####### Step 3 ####### #.# # #.# # # #.> #G# ####### Step 4 ####### #.# # #.# # # #..>#G# ####### Step 5 ####### #.# # #.#^# # #...#G# ####### Step 6 ####### #.#^ # #.#.# # #...#G# ####### Step 7 ####### #.#.> # #.#.# # #...#G# ####### Step 8 ####### #.#..># #.#.# # #...#G# ####### Step 9 ####### #.#...# #.#.#v# #...#G# ####### Step 10 ####### #.#...# #.#.#.# #...#S# ####### Found the goal! Hooray!
bouncePolicy animateTurtle animation for maze `MAZE3` (click on the triangle to see details) An turtle animation of a robot using the bounce policy moving through a maze. The robot moves back and forth along three corridors which are parallel and connected at their ends to form a hallway travelling south, then north, then south again from the robot to the goal.

leftWallPolicy traceSurroundings Example

This example shows the text printed out by traceSurroundings for leftWallPolicy on the maze MAZE4 described above. This time, the maze consists of a hallway along the south edge with four corridors each stretching two spaces north from the hallway. The goal is at the end of the third hallway from the west edge, and the robot starts in the center of the hallway facing west (between the second and third corridors). The robot continues west until it hits the end of the hallway and turns into the first corridor, then it continues to fallow its left wall through that corridor, back to the main hallway, into the second corridor, back again to the main hallway, and finally into the third corridor where it reaches the goal.

In []:
maze.traceSurroundings(maze.MAZE4, leftWallPolicy, 40, 25)
Prints
Tracing surroundings with 40 fuel in the following maze: ######### # # #G# # # # # # # # < # ######### Step 0: Facing west. Two walls north and south. Decision: forward. Step 1: Facing west. One wall south. Visited east. Decision: forward. Step 2: Facing west. Two walls north and south. Visited east. Decision: forward. Step 3: Facing west. Two walls south and west. Visited east. Decision: right. Step 4: Facing north. Two walls east and west. Visited south. Decision: forward. Step 5: Facing north. Three walls north, east, and west. Visited south. Decision: backward. Step 6: Facing south. Two walls east and west. Visited north and south. Decision: forward. Step 7: Facing south. Two walls south and west. Visited north and east. Decision: left. Step 8: Facing east. Two walls north and south. Visited east and west. Decision: forward. Step 9: Facing east. One wall south. Visited east and west. Decision: left. Step 10: Facing north. Two walls east and west. Visited south. Decision: forward. Step 11: Facing north. Three walls north, east, and west. Visited south. Decision: backward. Step 12: Facing south. Two walls east and west. Visited north and south. Decision: forward. Step 13: Facing south. One wall south. Visited north, east, and west. Decision: left. Step 14: Facing east. Two walls north and south. Visited west. Decision: forward. Step 15: Facing east. One wall south. Visited west. Decision: left. Step 16: Facing north. Two walls east and west. Visited south. The goal is to the north! Decision: forward. Step 17: The robot has reached the goal. Found the goal! Hooray! The final maze state is: ######### #.#.#S# # #.#.#.# # #..... # #########

leftWallPolicy animateText Example

This example shows the text printed out by animateText for leftWallPolicy on the maze MAZE4 described above.

In []:
maze.animateText(maze.MAZE4, leftWallPolicy, 40, 25)
Prints
Animating maze movement with 40 fuel: Step 0 ######### # # #G# # # # # # # # < # ######### Step 1 ######### # # #G# # # # # # # # <. # ######### Step 2 ######### # # #G# # # # # # # # <.. # ######### Step 3 ######### # # #G# # # # # # # #<... # ######### Step 4 ######### # # #G# # #^# # # # #.... # ######### Step 5 ######### #^# #G# # #.# # # # #.... # ######### Step 6 ######### #.# #G# # #v# # # # #.... # ######### Step 7 ######### #.# #G# # #.# # # # #v... # ######### Step 8 ######### #.# #G# # #.# # # # #.>.. # ######### Step 9 ######### #.# #G# # #.# # # # #..>. # ######### Step 10 ######### #.# #G# # #.#^# # # #.... # ######### Step 11 ######### #.#^#G# # #.#.# # # #.... # ######### Step 12 ######### #.#.#G# # #.#v# # # #.... # ######### Step 13 ######### #.#.#G# # #.#.# # # #..v. # ######### Step 14 ######### #.#.#G# # #.#.# # # #...> # ######### Step 15 ######### #.#.#G# # #.#.# # # #....> # ######### Step 16 ######### #.#.#G# # #.#.#^# # #..... # ######### Step 17 ######### #.#.#S# # #.#.#.# # #..... # ######### Found the goal! Hooray!
leftWallPolicy animateTurtle animation for the maze `MAZE4` described above (click on the triangle to see details) An animation of a robot using the left wall policy moving through a maze. This time, the maze consists of a hallway along the south edge with four corridors each stretching two spaces north from the hallway. The goal is at the end of the third hallway from the west edge, and the robot starts in the center of the hallway facing west (between the second and third corridors). The robot continues west until it hits the end of the hallway and turns into the first corridor, then it continues to fallow its left wall through that corridor, back to the main hallway, into the second corridor, back again to the main hallway, and finally into the third corridor where it reaches the goal.

Rubric

 
unknown Style Requirements
How your code is written.
 
unknown Core goals
Complete all core goals for core credit. Get partial credit for completing at least half, and more partial credit for completing at least 90%.
 
unknown All functions are documented
Each function you define must include a non-empty documentation string as the very first thing in the function.
 
unknown Procedure Requirements
What code you use to solve the problem.
 
unknown Core goals
Complete all core goals for core credit. Get partial credit for completing at least half, and more partial credit for completing at least 90%.
 
unknown Define bouncePolicy with 5 parameters
Use def to define bouncePolicy with 5 parameters
 
unknown Call isNotWall
Within the definition of bouncePolicy with 5 parameters, call isNotWall in at least once place.
 
unknown Do not call isNotVisited
Within the definition of bouncePolicy with 5 parameters, do not call isNotVisited.
 
unknown Use a conditional
Within the definition of bouncePolicy with 5 parameters, use an if statement (possibly accompanied by an elif or else block) in at least once place.
 
unknown Do not use a loop
Within the definition of bouncePolicy with 5 parameters, do not use any kind of loop.
 
unknown Define leftWallPolicy with 5 parameters
Use def to define leftWallPolicy with 5 parameters
 
unknown Call isNotWall
Within the definition of leftWallPolicy with 5 parameters, call isNotWall in at least once place.
 
unknown Do not call isNotVisited
Within the definition of leftWallPolicy with 5 parameters, do not call isNotVisited.
 
unknown Use a conditional
Within the definition of leftWallPolicy with 5 parameters, use an if statement (possibly accompanied by an elif or else block) in at least once place.
 
unknown Do not use a loop
Within the definition of leftWallPolicy with 5 parameters, do not use any kind of loop.
 
unknown Define customPolicy with 5 parameters
Use def to define customPolicy with 5 parameters
 
unknown Use a conditional
Within the definition of customPolicy with 5 parameters, use an if statement (possibly accompanied by an elif or else block) in at least once place.
 
unknown Do not use a loop
Within the definition of customPolicy with 5 parameters, do not use any kind of loop.
 
unknown Extra goals
Complete all extra goals in addition to the core goals for a perfect score.
 
unknown Do not ignore the results of any fruitful function calls
According to the "Don't waste fruit" principle, every place you call a fruitful function (built-in or custom) you must store the result in a variable, or that function call must be part of a larger expression that uses its return value.
 
unknown Define bouncePolicy with 5 parameters
Use def to define bouncePolicy with 5 parameters
 
unknown bouncePolicy does not use any comparisons
Within the definition of bouncePolicy with 5 parameters, bouncePolicy should not use any comparisons (== or !=). Use isNotWall instead).
 
unknown Define leftWallPolicy with 5 parameters
Use def to define leftWallPolicy with 5 parameters
 
unknown leftWallPolicy does not use any comparisons
Within the definition of leftWallPolicy with 5 parameters, leftWallPolicy should not use any comparisons (== or !=). Use isNotWall instead).
 
unknown Define customPolicy with 5 parameters
Use def to define customPolicy with 5 parameters
 
unknown Call bouncePolicy
Within the definition of customPolicy with 5 parameters, call bouncePolicy or leftWallPolicy in at least once place.
 
unknown Product Requirements
Your code's result values.
 
unknown Core goals
Complete all core goals for core credit. Get partial credit for completing at least half, and more partial credit for completing at least 90%.
 
unknown bouncePolicy returns the correct result
The result returned when your bouncePolicy function is run must match the solution result.
 
unknown leftWallPolicy returns the correct result
The result returned when your leftWallPolicy function is run must match the solution result.
 
unknown Extra goals
Complete all extra goals in addition to the core goals for a perfect score.
 
unknown bouncePolicy returns the correct result
The result returned when your bouncePolicy function is run must match the solution result.
 
unknown leftWallPolicy returns the correct result
The result returned when your leftWallPolicy function is run must match the solution result.
 
unknown Your custom policy solves advanced mazes
Your customPolicy function solves at least 3 of mazes MAZE7 through MAZE12 at least 50% of the time given 300 fuel.