COMP 5600/6600 Using Search for Robot Path Planning Solved

Problem Scenario

You are designing a robot whose goal is to move from one location to another, just as we discussed in Lecture 6. You want to evaluate the ability of informed and uninformed searches to find the optimal path (shortest) to get from the start to the goal state. To help you, I have converted the map of the building into a state-space graph. Your goal is to implement 2 uninformed search algorithms (BFS and DFS) and 1 informed search (A* algorithm) to search for an optimal path from the start node to the end node. You will be given 3 test cases on which to evaluate your implementations.


Deliverables:

You will need to have your own implementation of each of the three algorithms as well as a short report that discusses your design choices, your implementation strategy, and a comparison of the performance of the three algorithms on each of the test cases. You can compare them using any metric(s) of your choice, such as success rate, time taken to find a solution, and number of steps taken to find a solution. You should briefly describe your findings and provide your insights on which is suitable for this problem. For the informed search (A* algorithm) you must devise and evaluate at least 2 heuristics of your choice. You are free to choose any function as your heuristic. In your report, you should describe why you chose it, whether it is an admissible heuristic, and whether it helped the A* algorithm perform better than uninformed search.

Here are some more details about your assignment.

    • Input: 3 test cases, with varying levels of complexity, are provided. Each test case consists of 2 files. The first, labeled “TestCase_XX_EdgeList.txt” is a text file where each line corresponds to an edge list of the form <n1, n2, w>, which indicates an edge between nodes n1 and n2 with a weight of w. The second file, labeled “TestCase_XX_NodeID.csv”, is a CSV file with each line of the form “n1,x,y”, where x and y are the coordinates of the state n1.

    • Expected Output: Your program should print out a list of states visited by your algorithm, from the start state (indicated by the first line of the NodeID file) to the goal state (the last line of the NodeID file).

    • Submission Format: Your code must be an IPython Notebook. You can have text blocks to write your report and the code blocks for your implementation. You can use Google Colab for implementing your code since your code will be evaluated on Colab so that everyone’s code is evaluated on a standard platform. You can download your file for submission by going to “File->”Download”->”Download .ipynb”.

To Verify your implementation, the expected output of BFS and DFS are given below. Since heuristic functions can vary and hence result in different solutions, the output for A* is not provided here.

Case 1:
---------------

BFS: ['N_0', 'N_1', 'N_6', 'N_2', 'N_5', 'N_7', 'N_3', 'N_10', 'N_12', 'N_15', 'N_11', 'N_13', 'N_17', 'N_20', 'N_16', 'N_8', 'N_14', 'N_18', 'N_22', 'N_21', 'N_9', 'N_19', 'N_23', 'N_4', 'N_24']

DFS: ['N_0', 'N_1', 'N_2', 'N_3', 'N_6', 'N_7', 'N_12', 'N_17', 'N_22', 'N_23', 'N_13', 'N_18', 'N_19', 'N_24']