Project #1: State-Space Search

ROB311: Artificial Intelligence
Project #1: State-Space Search

Overview
In this project, you will implement and analyze a number of uninformed and informed search strategies for
different problem domains. The goals are to:
• experiment with basic uninformed search strategies on an explicit graph; and
• implement A?
for a simple 2D maze domain and analyze the difficulty of random problem instances.
The project has two parts, worth a total of 50 points. All submissions will be via Autolab; you may submit as
many times as you wish until the deadline. Submission details are provided at the end of this document. To
complete the project, you will need to review some material that goes beyond that discussed in the lectures—
more details are provided below. The due date for project submission is Saturday, February 5, 2022 by
23:55 EST.
Preliminaries - Handout Code
We have provided ‘starter code,’ consisting of a series of Python files that you will use to implement your
solutions to Parts 1 and 2. Your task is to complete the following template files:
1. breadth_first_search.py: a simple breadth-first search (BFS) algorithm for problem domains
with uniform action costs;
2. bidirectional_search.py: a bidirectional BFS algorithm that simultaneously searches from the
initial and goal states until the intersection of each search’s frontier representing an optimal path is
found (also only for the uniform action cost case); and
3. a_star_search.py: a best-first search that computes optimal paths when supplied with a consistent
heuristic for its problem domain.
These files contain function template s that you must fill in as your solution. You should not change the
function templates or add to the import statements at the top of these files: the autograding software will strip
out any additional imports and replace them with the default upon submission, causing your code to produce
an error when the removed import is referenced. If you need additional libraries for testing or visualizing,
use them in a separate file that imports your solutions from these 3 files. Each of these files constains some
simple problem instances after the if __name__ == '__main__': statement. You will need to create
more extensive tests to ensure the correctness of your solutions. For all search implementations, your function
should return None or the empty list when a solution cannot be found.
The file search_problems.py, which you must not modify, implements a number of classes and a function
you will need for your solutions:
1 of 5
ROB311: Artificial Intelligence Project #1: State-Space Search
1. a Node class that contains the parent, state, action, and path_cost fields required for state
space search (see class notes and AIMA);
2. abstract base classes SearchProblem and SimpleSearchProblem which our main problem classes
will inherit from;
3. a GraphSearchProblem class which you will use with your breadth_first_search and
bidirectional_search solutions;
4. a GridSearchProblem class which you will use with your a_star_search solution; and
5. get_random_grid_problem(), a helper function that produces random GridSearchProblem instances.
This file, along with the standard library and permitted imports at the top of the submission templates, are
sufficient for you to implement your solutions. You do not need to submit search_problems.py as part of
your solutions: it is already on the grading server.
The class BasicSearchProblem is an abstract base class with required functionality for the network and grid search problems you will be solving. It is extended by the GridSearchProblem and
GridSearchProblem classes, which together provide all the methods needed to implement a generic search
algorithm like breadth-first search. Note that while these classes support multiple goal states, our problems
will only involve one goal state, so you may assume that you can simply use problem.goal_states[1]
to access the goal state (or just use the goal_test() method).
Part 1: Uninformed Search
You have been hired by PluggedUp, a tech startup that runs a social network focussed on “plugging” professionals into their dream careers. Your first task is to determine the shortest path connecting two users in the
network so that recruiters can introduce employers to prospective hires through mutual acquaintances. The
social network is stored as an undirected graph G where the vertices v ∈ V representing users are labelled
with unique integers and users that are in one another’s contact lists are connected with an edge e ∈ E.
Connections are assumed to be uniformly weighted so that the shortest path is simply the number of edges
or hops between two vertices.
The GridSearchProblem class has a constructor that takes in an initial state, a list of goal states (we will
only ever have a single goal state in this assignment), and a graph specified by a set of vertices V and edges E.
The example at the bottom of breadth_first_search.py and bidirectional_search.py gives an
example problem setup using the provided file stanford_large_network_facebook_combined.txt.
These edges are from real anonymized Facebook data made available by the Stanford Large Network Dataset
Collection. Your tasks are to:
1. Implement breadth-first search (BFS) to find the shortest path between two users in the graph. Use the
function template called breadth_first_search in breadth_first_search.py. Your function
should return a tuple with list of states representing your path from the initial state to the goal state,
the number of nodes expanded by your search, and the maximum frontier size encountered during the
search. Only the first element of this tuple (the path) will be graded, but the other fields are useful for
comparing algorithms and will be needed in Part 2. You are free to implement your own data structures
in this file, but you would be wise to make use of the deque structure provided in the import. The set()
data structure is also potentially useful.
2 of 5
ROB311: Artificial Intelligence Project #1: State-Space Search
2. Implement bidirectional search to solve the shortest path problem, using the function template
bidirectional_search in bidirectional_search.py. The textbook (AIMA) describes bidirectional search on page 90, but it leaves out some details that you will have to fill in to ensure that your
bidirectional search is optimal. To test and debug your code, compare your results with those from the implementation of breadth_first_search. You should think about the relative runtime, max. frontier
size, and number of nodes expanded by each algorithm.
You will submit your implementations through Autolab (instructions at the end of this document).
Part 2: Occupancy Grid Planning With A?
In this section, you will work with the GridSearchProblem class to find optimal paths through a 2D occupancy grid maze (see Figure 1 for an example). In the lecture slides and on page 84 of AIMA, the pseudocode
describing uniform cost search provides a good guide, but there are other variants that you are free to explore.
For example, you do not have to remove a node from the frontier if a node with a shorter path to the initial
state is found. This results in a less memory efficient but sometimes faster algorithm. We recommend using
the PriorityQueue class provided by the queue library (note that you do not have access to deque for
this problem).
Our ultimate goal is to study the “hardness” of grid search problem instances in the same manner as the
graphs on page 264 of AIMA. Your tasks are to:
1. Fill in the a_star_search function in a_star_search.py so that it outputs a tuple consisting of a
path (once again a list of integer states), the number of nodes generated, and the maximum frontier size
encountered. You may once again find the set() data structure useful, as well as the standard dictionary
(dict()).
2. For different values of a square map with dimension N, recreate the graphs on page 264 of AIMA for
our grid search problem. Rather than the clause to symbol ratio, our “hardness” parameter on the
x-axis will be the probability pocc of a grid cell being occupied. This value is the first argument of
get_random_grid_problem.py. On the y-axis of one chart, plot the portion of nruns that were solvable by A?
, and on the other plot the average number of nodes generated over nruns. Generated nodes
include those not added to the frontier (i.e. legal state transitions that are not added because they have
already been explored). Plot one curve for square grid size N = 20, N = 100, and N = 500 (M = N in
all cases). Use nruns = 100 and use a resolution of 0.05 for values of pocc from 0.1 to 0.9. For each of the
nruns problem instances at each value of pocc and N, use get_random_grid_problem to generate your
problem instance. This experiment may take a while to run! Does A? exhibit the same “phase transition”
phenomenon as SAT? What effect does increasing N appear to have on each plot? Would you conjecture
that this threshold becomes sharp as N → ∞?
3. Complete the simple template function search_phase_transition in a_star_search.py. This
function simply returns the hardness “transition interval” [l, b] ⊂ [0, 1] and the single peak computational
effort (in terms of nodes generated) ppeak ∈ [0, 1] observed for your N = 500 experiment. Do not worry
about being too precise, just choose the interval of length ≤ 0.2 where the probability of solvability transitions from approximately 1 to approximately 0. To be clear, you do not need to submit code that runs
the phase transition experiment: simply modify the the 3 outputs of search_phase_transition to
report your findings.
You will submit and check your implementations of a_star_search and search_phase_transition
through Autolab (both of these should be implemented as functions in a_star_search.py).
3 of 5
ROB311: Artificial Intelligence Project #1: State-Space Search
5 10 15 20 25 30 35 40
5
10
15
20
25
30
35
40
Figure 1: Example solution to a 2D maze problem. Black cells are “occupied” by an obstacle and cannot be
entered. Each cell represents a state, and our agent can only transition between cells that share a side (i.e.,
no diagonal movement).
4 of 5
ROB311: Artificial Intelligence Project #1: State-Space Search
Grading and Submission
We would like to reiterate that only functions submitted via Autolab will affect your marks. There are other
questions in the sections above, but only those that ask you to submit a function via Autolab will affect your
total. The remainder are useful for your understanding or are there to aid you in creating your solutions.
Points for each portion of the project will be assigned as follows:
• Uninformed Search – 20 points (5 problems × 4 marks each)
Each test will check either breadth_first_search or bidirectional_search for the shortest
path from an initial state in a graph with undirected edges E to a final state.
• Occupancy Grid Planning With A? – 30 points (4 problems × 5 marks each + 10 marks)
Each of the 4 instances test of a_star_search will provide a GridSearchProblem instance for a
total of 20 points. The test of search_phase_transition is worth 10 points.
Total: 50 points
When you are ready to submit, archive the files with the following command:
tar cvf handin.tar breadth_first_search.py bidirectional_search.py a_star_search.py
Then upload the handin.tar file to the Project 1 page on Autolab. Please note other file formats will not
be accepted by the system. You can make multiple submissions, your latest submission will be evaluated, but
all submissions will be checked for plagiarism.
Grading criteria include: correctness and succinctness of the implementation of support functions, proper
overall program operation, and code commenting. Please note that we will test your code in Python 3.8 and
it must run successfully. It is worth knowing that there is a 300 seconds time limit for each submission, which
means that the presence of an infinite loop may result in no marks. Please test your code for such loops
rigorously well before the deadline.
Code that is not properly commented or that looks like ‘spaghetti’ may result in an overall deduction of
up to 10%. The expectation is that it should be possible to understand your algorithm by simply reading your comments. There is no specific commenting format that you have to follow. Please check the file
search_problems.py for some basic commenting examples.
Late Submissions – Grace Days
Across the four programming projects in this course, each student is given a total of three complimentary
grace days, to be used as they see fit. If you submit a project after the deadline, the Autolab system will
automatically deduct the appropriate number of grace days, but to ensure correct accounting please email the
TA when you are ‘cashing in’ any grace days with a late submission. After these grace days are used, no further
late submissions will be accepted, and a mark of zero will be recorded.
5 of 5