Robotics Homework: Wall Following

Hand out

Reference program: maze.pyo (2. Update April 2nd, 18:18) (SHA-1: 51e27a9af95c4d600d21a23926bd845f4a5c0e7a).
Example input: maze.test.
To run the reference program on the example input, type: python3 maze.pyo < maze.test
Log in the Gradebot to find the due date and how to clone the repository of this homework.
This homework is for ALL stuents.

Check in

maze.py and any other modules as needed.
Your program may not use any third-party libraries.

Policy on plagiarism

This is an individual homework. While you may discuss the ideas and algorithms of this homework with others, at no time should you read, possess, or submit the solution source code of any other person (including people outside this course), or allow anyone else to read or possess your source code. We will detect plagiarism using automated tools and will prosecute all violations to the fullest extent of the university regulations, including failing this course, academic probation, and expulsion from the university.

Description

Input:

The input to the program is a text file containing comments, the robot start pose and a 2D map. Comment lines begin with a hash character (number sign; #) and should be ignored by your program.
The first non-comment line of that text file encodes the start pose of the robot. Those are three integer numbers separated by spaces. They encode x, y and orientation of the start, in that order. For the purpose of this assignment the orientation is encoded as four integer values between 0 and 3.

0: positive in x-axis (east)
1: positive in y-axis (north)
2: negative in x-axis (west)
3: negative in y-axis (south)

The second part of the input is the map. It consists of either 0 (a free cell) or 1 (occupied cell = wall). The bottom left cell in the text file is located in the origin of the coordinate system (0, 0). The x-axis follows this line to the west (right) while the y-axis follows this column to the north (up).
The width of the map is defined by the number of characters in the line (if the lines of the map have different length the program behavior is undefined - all gradebot test cases have the same line length for the map part.) The height of the map is defined by the number of lines in the map part.

Output:

The program has to output all poses the robot drives through while following the right hand wall following algorithm (see below). The output starts with the start pose and ends with the end pose. All intermediate poses have to be displayed as well. Make sure that you do not print the same pose immediately again - with the exception if start and end pose are the same! The end pose is always outside of the map (we have exited the maze). The pose output has to have the following format:
[[x, y], o]
with x and y being the coordinates and o the orientation with the same encoding as the input. There is a space after the comma. Write each pose in a new line.

Algorithm:

The algorithm has two parts: 1) Find the Wall and 2) Follow the Wall.

Find Wall

Go forward until you either:
  Reach an exit
  Have a wall to the right side
  Have a wall in front of you
    In this case turn left once

Follow Wall

Do until you reach an exit:
  If no wall on your right:
    Turn right
    Step forward
  Else if wall in front of you:
    Turn left
  Else:
    Go forward

Hints

Process the input through the following stages:

Map: Write a map class with a get function that takes a position as input and returns the map value (0 or 1) or, in case the position is outside the map, another value (for example 2).
Parser: Read the input and puts the values in the state variable (pose) and the map class.
Executor: First executes the Find Wall algorithm and then the Follow Wall algorithm.

Writing the following helper functions might be very helpful:

forward: move a pose one cell in the current orientation
turnLeft: changes the orientation of a pose by turning left
turnRight: changes the orientation of a pose by turning right
isWallInFront: return true if there is an obstacle in front. (might make use of "forward")
isWallOnRight: return true if there is an obstacle on the right side. (might make use of "turnRight" and "forward")

It might be a good idea to include a step counter in Follow Wall that exits the program after a certain number of steps. The reference program includes such a counter. This is to prevent an endless loop if the program does not find an exit. Using the above algorithm, all test cases in the grade bot are guaranteed to find an exit in less than 500 steps.