[SOLVED] Comp 5600/6600 assignment 1 – using search for robot path planning

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’]