Introduction to Artificial Intelligence Written HW 1

CS 188

Introduction to
Artificial Intelligence Written HW 1

For the self assessment, fill in the self assessment boxes in your original submission (you can
download a PDF copy of your submission from Gradescope). For each subpart where your original answer
was correct, write “correct.” Otherwise, write and explain the correct answer.
Policy: Can be solved in groups (acknowledge collaborators) but must be written up individually
Submission: Your submission should be a PDF that matches this template. Each page of the PDF should
align with the corresponding page of the template (page 1 has name/collaborators, question 1 begins on page
2, etc.). Do not reorder, split, combine, or add extra pages. The intention is that you print out the
template, write on the page in pen/pencil, and then scan or take pictures of the pages to make your submission.
You may also fill out this template digitally (e.g. using a tablet.)
First name
Last name
SID
Collaborators
1
Q1. Search
A G
F
E
C
D
B 1
3 5 3
1
2
9
8 5
4
Node h1 h2
A 9.5 10
B 9 12
C 8 10
D 7 8
E 1.5 1
F 4 4.5
G 0 0
Consider the state space graph shown above. A is the start state and G is the goal state. The costs for each edge
are shown on the graph. Each edge can be traversed in both directions. Note that the heuristic h1 is consistent but
the heuristic h2 is not consistent.
(a) Possible paths returned
For each of the following graph search strategies (do not answer for tree search), mark which, if any, of the
listed paths it could return. Note that for some search strategies the specific path returned might depend on
tie-breaking behavior. In any such cases, make sure to mark all paths that could be returned under some
tie-breaking scheme.
Search Algorithm A-B-D-G A-C-D-G A-B-C-D-F-G
Depth first search
Breadth first search
Uniform cost search
A* search with heuristic h1
A* search with heuristic h2
(b) Heuristic function properties
Suppose you are completing the new heuristic function h3 shown below. All the values are fixed except h3(B).
Node A B C D E F G
h3 10 ? 9 7 1.5 4.5 0
For each of the following conditions, write the set of values that are possible for h3(B). For example, to denote
all non-negative numbers, write [0, ∞], to denote the empty set, write ∅, and so on.
(i) What values of h3(B) make h3 admissible?
(ii) What values of h3(B) make h3 consistent?
(iii) What values of h3(B) will cause A* graph search to expand node A, then node C, then node
B, then node D in order?
2
Q2. n-pacmen search
Consider the problem of controlling n pacmen simultaneously. Several pacmen can be in the same square at the same
time, and at each time step, each pacman moves by at most one unit vertically or horizontally (in other words, a
pacman can stop, and also several pacmen can move simultaneously). The goal of the game is to have all the pacmen
be at the same square in the minimum number of time steps. In this question, use the following notation: let M
denote the number of squares in the maze that are not walls (i.e. the number of squares where pacmen can go); n
the number of pacmen; and pi = (xi
, yi) : i = 1 . . . n, the position of pacman i. Assume that the maze is connected.
(a) What is the state space of this problem?
(b) What is the size of the state space (not a bound, the exact size)?
(c) Give the tightest upper bound on the branching factor of this problem.
(d) Bound the number of nodes expanded by uniform cost tree search on this problem, as a function of n and M.
Justify your answer.
(e) Which of the following heuristics are admissible? Which one(s), if any, are consistent? Circle the corresponding
Roman numerals and briefly justify all your answers.
1. The number of (ordered) pairs (i, j) of pacmen with different coordinates:
h1(p1, . . . , pn) = Pn
i=1
Pn
j=i+1 1[pi 6= pj ] where 1[pi 6= pj ] = (
1 if pi 6= pj
0 otherwise
(i) Consistent? (ii) Admissible?
2. h2((x1, y1), . . . ,(xn, yn)) = 1
2 max {maxi,j |xi − xj |, maxi,j |yi − yj |}
(i) Consistent? (ii) Admissible?
3