Objectives: Develop a path-planning solution from scratch Calculate cost and (consistent) heuristic functions Implement the graph-based path planning algorithm(s) Problem Definition: Assume the mayors of different cities/districts in a region (e.g., greater Vancouver area) use a driverless car for traveling from their office in the city hall to meet the mayor of another city. In this assignment we assume the car loses its real-time GPS data and need to rely only on an off-line map built according to the instruction provided in the following Part A section. Write a program according to Part B to guide the car for path finding. Part A [3 marks]: Build a graph for the (offline) road map/network 1- Consider the following as the list of major cities in the greater Vancouver area and lower mainland: Vancouver, North Vancouver, West Vancouver, Burnaby, Richmond, Surrey, New Westminster, Delta, Langley, Abbotsford, Chilliwack, Hope, Mission. Hint: you can use the two-letters from the name of the city when defining a variable for that city in your program (use capital letters) 2- Calculate the cost function (using Google map application) a. Consider the minimum distance between the city halls (assume the mayors office is in the city hall) as the cost of traveling between two cities. For simplicity, you could round down this number. For example, the cost of traveling from city hall Abbotsford to Chilliwack operation center= 32.7Km i. Note: if the city/district doesnt have a city hall, search for a municipality building or downtown or . 3- Build a heuristic function a. X= minimum distance between the city halls b. Y= a random number between 5 to 10 c. H(c1,c2)=round_down (X-Y) # heuristic value between city 1 and 2 4- (Optional/bonus) Subtracting the random number (Y) from X in the heuristic function makessure the heuristic value is admissible but doesnt guarantee that it is consistent. Write 2 a function that makes sure the heuristic values are consistent as well. This means, for some nodes the Y value should be changed to make their heuristic consistent. Part B [7 marks]: Write a program that uses a graph-based path planning algorithm (i.e., A*) to guide the driverless car for traveling between two city halls. 1- Write the function PathFinder where the input arguments to the function are the name of two cities and the search algorithm. a. Example: when you call the function PathFinder (VA, LA, A_Star), it returns the optimal path between Vancouver and Langley using A* algorithm. b. (required) the function should implement the A* algorithm c. (optional/bonus) extend your code to include Grassfire and Dijsktras algorithms as well. 2- Write your program with an intuitive user interaction parts for both taking the inputs from the user to providing the results. Bonus-Part C [5 marks]: The basic lab will be marked out of 10. There are two optional/bonus items (i.e., consistent heuristic and extended search algorithms) for an extra 5 marks in total.

Attachments:

objectives.docx