Build a graph for the (offline) road map/network

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

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 mayor’s 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 doesn’t 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 makes sure the heuristic value is admissible but doesn’t guarantee that it is consistent. Write

 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 Dijsktra’s 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:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of