TASK 1 - Path Planning

Create an algorithm which finds a path on the road graph of United Kingdom (UK) between two nodes (intersections).

Assignment

Input:

Graph representing road network in UK
- The graph edges contain length of the edge and maximal allowed speed
- The nodes are signed with unique identifier ID.
Initial node
Goal node

Output:

Quality criteria, listed in descending priority:

The algorithm fulfills all parts of the assignment (classes name and location, using given structures and the method add() in the open list - see below)
The path is correct, i.e., leads from origin to destination, the path is connected, i.e., two subsequent edges have a common node and the edges are sorted correctly.
The found path minimizes transport time between initial and goal state
The number of expanded nodes is minimal

Grading

Algorithm fulfills the assignment completely
The path is correct, i.e., leads from origin to destination, the path is connected, i.e., two subsequent edges have a common node and the edges are sorted correctly. [+1b]
The found path minimizes transport time between initial and goal state [+3b]
The number of expanded nodes is minimal [+0-4b]

Date/time: Monday, 20.3.2017 03:59:59
Content: compressed content of Java package student (pack only .java source files, no subfolders please)

Use the codebase available HERE.
Implement class Planner in package student (implementation of the interface PlannerInterface)
Create class OpenList which extends class AbstractOpenList in your package. For adding the items to OpenList use only the method add(T item)
If you modify any item in OpenList (you have added it to the OpenList earlier, you just recompute its cost), then you don't need to call the add method (however, you can - the Counter value is going to be increased though).
The algorithm is going to return null if the path does not exist

The class RoadGraph allows you to access the graph and contains a set of method which you can use to move along the graph
The class GraphEdge contains the methods getAllowedMaxSpeedInKmph() and getLengthInMetres() which return the maximal allowed speed in km and length in meters respectively.
The class Utils gives you the metric for counting the distance between any two nodes in the graph.
The class PlannerExecutor allows the body of the program where you can test your algorithm.