Robotics Homework 2

Introduction to Information Science and Technology School of Information Science and Technology SIST

Goals

The goals of this homework are:

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.

Easy option for class B

Only for students of class B the following option is offered:
Instead of implementing Dijkstra's algorithm you can program a simple program for calculating prime numbers. This should be much more easy than implementing Dijkstra's algorithm. If you choose this option you can get a maximum of 75% for this homework!

Prime numbers

Implement a program that CALCULATES and prints all prime numbers in a certain range. The range is given as two numbers on stdin. Print all prime numbers (including the given numbers if they are prime) within that range, sorted, with the smallest prime numbers first, each prime number on a new line. Example output for input 18 7:
7
11
13
17
Save your python program called primes.py on gradebot. If there is a file called 'primes.py' found in your gradebot repo we will assume that you want to use this option! So if you first implement primes.py and then later want to rather submit the other task you have to delete primes.py (git rm primes.py). You can always add it again if you change your mind. The status that is in the gradebot once the due date is over is final!

Hand out

Check in

Dijkstra's for path planning

This task is for all students from class A (SIST) and for those from class B that choose not to do the prime number task but instead try to get 100% score by implmenting Dijkstra's.

Description

Input:

The input to the program is a text file very similar to the robotics homework one. It contains comments, a start position, a goal position and a 2D map. Comment lines begin with a dollar character ($) and should be ignored by your program.
The first non-comment line of that text file encodes the start position of the robot and the second non-comment line is the goal position. Those are two integer numbers separated by spaces. They encode x, y, in that order.

The second part of the input is the map. It consists of either '.' (a free cell) or 'X' (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 east (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 three things: 1) The calculated distances for all cells of the map, 2) A sentence with the number of cells touched and 3) the found path. For the map print the values of one line in the map with 'print (format(value, '6.2f'), end = "")'. At the end of that line add a new line.
The sentence should be printed via 'print ("Found goal in %d steps" % steps)'. The step counter is incremented when we read the distance value saved in an unoccupied map cell. The path is all cells visited from the start to the goal, including those two. If no path can be found output an empty list: '[]'.

Algorithm:

We save the calculated distance values in the map - each calculated (minimum) distance per map cell. At the beginning all values are initialized as infinite. Distance values for map cells which are occupied ('X') will never get updated.

Remember in Dijkstra's we keep a set of active nodes, which initially is the whole graph. We optimize this by instead using a wavefront algorithm: We start with the active set just consisting of the start node. During the algorithm only the neighboring nodes whose distance value we updated will be added to the active set.

The pseudocode for the Algorithm is now as follows: 

Initialize all map cells with infinite distance
Initialize the start cell with 0 distance
step counter = 0
Add start cell to wavefront (active set)
While wavefront not empty:
  select the first node with the minimum dist value from the wavefront  
    remove node from the wavefront
    if node == goal:
      break
    for all 8 neighbors of the node:
      if the neighbor is valid and not a wall:
        increase step counter
        neighDist = distance saved in node + distanceToNeighbor (1 or sqrt(2))
        if neighDist < distance saved in neighbor:
          update distance saved in neighbor with nieghDist
          append neighbor to the wavefront (active set)
Print the map values
Print the number of steps
Create the path:
  starting from the goalCell select the neighbor with the lowest distance saved
    add the selection to the path and continue with the selection to save it's lowest neighbor
      till you reached the start point
Print the path

Order of cell access

In order to achieve the same output as the reference program the gradebot uses we have to access the cells in the same order. The oder is given as follows: Start with the bottom neighbor (y-1) (changed!) and visit counter-clockwise CLOCK-WISE (changed!) (when looking at the text file) all 8 neighbors.

Additional Info

Length of Functions

The maximum number of lines of code (not counting blank, comment-only lines and sub-functions) per function is 40. If even a single function of your program exceeds this number you will be deducted 50% further points. (Point deductions are multiplied together - if you violate all three rules you will only get 25% of your gradebot points.)

Reason for this rule: You should practice to use a good coding style and split your problems/ algorithms into sub-tasks using properly named functions.

Comments in the Code

You are required to write meaningful comments for your program. Gradebot will ensure that you have a comment in at least 50% of the non-blank lines (so please do keep blank lines in your code to make it easier on the eyes). Your comments have to be in English and meaningful. The TAs will check your code by hand for comments. You will loose up to 50% of your score if you don't adhere to this rule.

Reason for this rule: Writing comments is essential once you start programming in a group/ company. This will help other programmers (TAs) to understand your code. Having lots of comments is a very good coding practice which is very often neglected.

Additional task just for Class A (SIST)

Copy dijkstra.py to astar.py. In astar.py implement an A* search. The program is very similar to Dijkstra's: instead of selecting the next node to expand based purely on the distance value we now select the node based on an addition of the distance value with an heuristic.
The heuristic we use is the geometric distance from the node to the goal.
The input is exactly the same as above. The output changes as follows: Instead of printing the map with the distance values you print the map using the sum of the distance value with the heuristic.

For class A both tasks are each 50% of this homework.

Gradebot instructions

The grading for gradebot is ready.

Exit status

Your program must not exit with a non-zero status. This means that if your program calls exit(), the argument must be zero.