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
