Your Task
In this assignment, you will implement a map navigation solution for wheelchair users.
Many people use a navigation program like Google Maps. However, no program currently supports planning a route specifically for wheelchair users. While Google Maps provides information on the accessibility of certain locations, it does not consider factors such as kerb ramps, sidewalk width, slope, and indoor lifts.
Objective: The objective of this assignment is to implement the A* algorithm for wheelchair map navigation.
Prepare a wheelchair-friendly map (P/C-level Task)
Create a map of wheelchair-accessible routes and locations in your local area, for example, your campus or your local shopping centre. You can use tools such as Google Maps or OpenStreetMap to mark wheelchair-friendly routes and points of interest such as accessible restrooms, car parks, and kerb ramps. The map may include information on the slope of sidewalks, the presence of obstacles or barriers, and any other relevant accessibility features. You may conduct an onsite inspection, use your own experience and online resources, or collaborate with local disability organisations to gather information for the map.
You should discuss the process of creating it.
Implement map navigation (P/C-level Task)
Implement the A* algorithm for wheelchair map navigation. You may create a simplified environment, with an adjacency matrix representing the connections between locations and the cost/speed of travel. Justify the heuristic you choose.
Test the implementation with different start and end points. Verify that the path returned is valid and optimal.
Compare heuristics (D-Level Task)
Try different heuristics. Explain the pros and cons of each heuristic.
Record and compare the search efficiciency of different heuristics.
Fine-tune the performance (HD-level Task)
Implement another algorithm, such as Contraction Hierarchies or Transit Node Routing, and compare its performance to your A* implementation.
Characterise the conditions under which the alternative algorithm is more efficient.
Graphical user interface (Optional Bonus Task)
Create a graphical user interface that allows the user to input the start and end points of the path and to visualise the path on the map. The user interface should also display additional information about the path, such as the estimated time to traverse it and any obstacles or landmarks that may be encountered along the way.
