CSE 471 Introduction to Artificial Intelligence - Assignment: Graph Search Algorithm
Setting up the Environment
1. Set up the platform for this assignment using the new Virtual Machine file (Links to an external site.). (Use login password: aairobots) It already contains hw1 directory at ~/catkin_ws/src/. (If you're having trouble importing the virtual machine file, try adjusting the RAM, the number of processors, and video memory in the settings of Virtual Machine. Also, try closing all the other applications running in your system.)
2. You can also use your VM from Programming Project 0 or your own installation of Ubuntu 20.04 with ROS Noetic. Use hw1.zip (Links to an external site.) available here. Simply extract the hw1 directory and place it in ~/catkin_ws/src/.
3. Open ~/catkin_ws/src/hw1/doc/index.html in a browser to view all the instructions on setting up the code and running it. There are also some useful tips that will aid you in the project.
Task 1 40 Points
Use the Turtlebot environment that was set up in Programming Project 0 along with the helper code that we provided above to implement the graph search algorithm (similar to best-first search) and make it behave like the following search algorithms:
· Breadth-First Search (BFS)
· Greedy Best First Search (GBFS)
· Uniform Cost Search (UCS)
· A* Search (Astar)
For h(s), use the Manhattan heuristic. Please note that not all of the algorithms in this task might need a heuristic.
Task 2 20 Point
Create a line-plot for the time taken to search for a path to the goal by each of the search algorithms in Task 1.
· The x-axis of the plot represents the grid dimension.
· The y-axis of the plot represents the average time taken for each of the grid dimensions (grids with different # of obstacles but the same dimension are to be included when considering the average).
· Each search algorithm will be a different line in the same plot.
The data for generating the plots will be present in the hw1_results.csv file that you will be submitting as a part of the submission instructions detailed in the HTML file provided in the description.
Task 3 20 Points
Plot a line-plot for the nodes expanded while searching for a path to the goal by each of the search algorithms in Task 1.
EDIT: Any node with x =-1 or y=-1 should not be expanded. Please refer to the API given in HTML instructions for more details.
· The x-axis of the plot represents the grid dimension.
· The y-axis of the plot represents the average nodes expanded for each of the grid dimensions (grids with different # of obstacles but the same dimension are to be included when considering the average).
· Each search algorithm will be a different line in the same plot.
The data for generating the plots will be present in the hw1_results.csv file that you will be submitting as a part of the submission instructions detailed in the HTML file provided in the description.
Extra Credit 15 Points
Write a different heuristic h(s) for the A* search algorithm. This heuristic will be named "custom-astar". The rubric for extra credit is as follows:
1. 2 points if the custom heuristic is well reasoned (put the explanation in the code as comments).
2. 3 points for executability (The code executes without errors and finds a solution).
3. 5 points if your heuristic outperforms the Manhattan heuristic.
4. 5 points if the plots in Task 2 and Task 3 include this heuristic as well.
Your custom heuristic must be different from the Manhattan heuristic that you used in Task 1.
