Description
Forward Graph Search (150 total points) The lectures so far have focused on performing search on grids and graph representations. This project will focus on implementing and analyzing some of the algorithms we’ve discussed. To help you with getting started there is an included python le graph_serach.py which has some classes de ned to help you focus on the algorithm implementation. There is an additional le named PythonPointers.pdf on Canvas which gives some links and simple examples to help people who are new to python. The code also contains function headers for the search methods you need to implement. Feel free to change the function arguments necessary to make it easier for you to solve the problems. In addition to the code le included there are a few text les with included maps which we will use for evaluating our algorithms. If you write you own code you’ll need to have it read this kind of le so that it can be evaluated on new maps once you’ve submitted it for grading. The map is de ned as follows: 0 – denotes clear cell x – denotes obstacle g – denotes goal location (clear) i – denotes init location (clear) 1 For now the robot has actions A = {left, right, up, down}. The robot can move to a free cell, but if the action attempts to move to an occupied cell or o the map the action is not valid and the robot remains in the same state. 1 Depth First Search (40 pts) We will start by implementing depth rst search. I’ll walk you through this one. Implement DFS You may nd the Python list class helpful. For a list instance l = [] you can push to the end of the list by performing l.append(n) and pop from the end using the function call x = l.pop() The provided class GridMap reads in a map le and sets up a transition function for the grid world. It also provides methods for testing if the goal location has been reached. I’ve provided psuedocode for a version of depth rst search below: def DFS(init_state, f, is_goal, actions): frontier = [] # Search stack n0 = SearchNode(init_state, actions) visited = [] frontier.push(n0) while len(frontier) > 0: # Peak last element n_i = frontier.pop() if n_i not in visited: visited.add(n_i.state) if is_goal(n_i.state): return (path(n_i), visited) else: for a in actions: s_prime = f(n_i.state, a) n_prime = SearchNode(s_prime, actions, n_i, a) frontier.push(n_prime) return None I should be able to run your code using a map le as described above and it should be clear how to change the transition function and actions used. 1.1 (10 pts) Run DFS on map0.txt. Report the path and set of states visited. Include an image of the path taken in your answer. Is the path found the shortest path? Explain why the algorithm did or did not nd the shortest path. 1.2 (5 pts) Perform the same test and analysis for map1.txt. 1.3 (5 pts) Perform the same test and analysis for map2.txt. 2 1.4 (4 pts) The DFS algorithm explained in the psuedocode above adds search nodes for all actions from a given node at once. What issues may arise from doing this? How could this be alleviated? 1.5 (6 pts) Reverse the order of the actions explored by DFS and run it again on map0.txt and map1.txt. Does anything change in your results? What? Why is this the case? 1.6 (10 pts) Extend DFS to iterative deepening DFS. You need to add an argument to your DFS function that it only explores to a maximum depth m during execution. Additionally, you need to modify your visited set to take into account the depth at which nodes are visited, since they may be revisited at a shallower path which leads to the goal in fewer than m steps. Run your iterative deepening implementation on map0.txt and map1.txt. Did your algorithm nd the shortest path? Explain why it did or did not. 2 Breadth First Search (25 pts) Implement BFS Now implement breadth rst search. Remember we want to use a queue as our frontier data structure. In Python we can implement this by again using the list data structure. For a given list l = [] we can push to the end of the queue using l.append(n) and pop from the front using n = l.pop(0). Note the parameter 0 provided to pop, this tells the list to pop element 0 from the list (the front). You could pop the second element using l.pop(1) or explicitly from the rear of the list by using l.pop(-1) 2.1 (5 pts) Run BFS on map0.txt. Report the path and set of states visited. Is the path found the shortest path? Explain why the algorithm did or did not nd the shortest path. 2.2 (5 pts) Perform the same test and analysis for map1.txt. 2.3 (5 pts) Perform the same test and analysis for map2.txt. 2.4 (10 pts) Compare the performance of your algorithm to DFS and iterative deepening DFS above. How do the paths found dier? How do the states visited dier? Which was easier to implement and why? Discuss anything else you found interesting or di cult in implementing and evaluating the three algorithms. Searching with Costs We will now switch to examining algorithms for planning with costs associated to actions. To begin with all actions will have the same cost of 1. We will change this below. 3 Uniform Cost Search (20 pts) Implement Uniform Cost Search Remember that for implementing uniform cost search you need a priority queue to access the lowest cost path currently in the frontier. I have pro3 vided the python class PriorityQ. This function is setup to work with the SearchNode class and I have not used it with other classes. The class has the functions push(), pop(), and peak(), which respectively allow you to add an element with an associated cost to the queue, remove the lowest cost element, and see what the lowest cost element is. There is also a replace function for updating an element with the same state as the element added, however you can also access this function by calling push() with a SearchNode that has a state already in the queue. You can also get the length of a PriorityQ instance q using len(q) or test if a state s is in the priority queue by using sinq which will return True if the state s is currently in the queue. 3.1 (5 pts) Run uniform cost search on map0.txt. Report the path and set of states visited. Is the path found the lowest cost path? Is the path found the shortest path? Explain why the algorithm did or did not nd the lowest cost path. 3.2 (5 pts) Perform the same test and analysis for map1.txt. 3.3 (10 pts) Now extend the set of actions to allow the robot to move diagonally on the grid. Make diagonal action cost 1.5 as opposed to 1 for lateral and vertical moves. Perform the same test and analysis for map0.txt, map1.txt, and map2.txt as in 3.1. 4 A* Search (35 pts) Implement A* You now need to implement A* search by incorporating heuristics. You should make it easy to swap out heuristic functions as we will be evaluating a few below. 4.1 (10 pts) Implement a euclidean distance heuristic for evaluating A*. Run your algorithm on maps map0.txt, map1.txt, and map2.txt and give the results. How does the path you get compare to uniform cost search? How do the states explored compare to uniform cost search? Did you notice any other dierences in comparing the two? 4.2 (10 pts) Now implement a Manhattan distance heuristic. Run it on the same three maps and perform the same analysis. 4.3 (10 pts) Now extend the set of actions to allow the robot to move diagonally on the grid. Make diagonal action cost 1.5 as opposed to 1 for lateral and vertical moves. Run the same tests and analysis from 4.1 and 4.2 using both heuristics. Are these heuristics still admissable for our new problem? Why or why not? What is the eect of the new actions being added compared to the previous problems? What is the eect of the heuristic being admissable or not on the solutions your implementation gives? 4.4 (5 pts) Compare the Uniform Cost Search with diagonal actions (3.3) and A* with diagonal actions (4.3). 4 5 Graph search with 2D pose (25 pts) Handle 2D Pose You now need to change the action space to correspond to a nonholonomic mobile robot that only has 3 actions, (move forward, turn left, turn right). The state space already contains an unused third state dimension allocated for theta. Theta has 8 discrete possible states (0, 45, 90, 135, 180, 225, 270, 315) degrees each corresponding to pointing at a neighbouring cell. Assume theta=0 corresponds to pointing directly up. (Hint: You can express theta as an angle like degrees or just as 0-7 indicating the 8 possible values). 5.1 (5 pts) Run breadth rst search with the new action space on map1.txt and compare the solutions and number of visited nodes to with the original action set. 5.2 (5 pts) Run depth rst search with the new action space on map1.txt and compare the solutions and number of visited nodes to with the original action set. 5.3 (5 pts) Add costs associated with the new actions. For forward actions going diagonal, use a cost of 1.5. For forward actions going in a cardinal direction, use a cost of 1. For turning actions use a cost of 0.25. With these new costs are the original heuristics still admissable? 5.4 (5 pts) Run uniform cost search with the new action space on map1.txt and compare the solutions and number of visited nodes to with the original action set. 5.5 (5 pts) Run A* (using each heuristic) with the new action space on map1.txt and compare the solutions and number of visited nodes to with the original action set. 6 Self Analysis (5 pts) 6.1 (1 pt) What was the hardest part of the assignment for you? 6.2 (1 pt) What was the easiest part of the assignment for you? 6.3 (1 pt) What problem(s) helped further your understanding of the course material? 6.4 (1 pt) Did you feel any problems were tedious and not helpful to your understanding of the material? 6.5 (1 pt) What other feedback do you have about this homework? 5