CIS 471/571: Introduction to Artificial Intelligence, Fall 2020
Written Assignment 1: Solution Deadline: Oct 10th, 2020
Instruction: You may discuss these problems with classmates, but please complete the write- ups individually. (This applies to BOTH undergraduates and graduate students.) Remember the collaboration guidelines set forth in class: you may meet to discuss problems with classmates, but you may not take any written notes (or electronic notes, or photos, etc.) away from the meeting. Your answers must be typewritten, except for figures or diagrams, which may be hand-drawn.
Q1. Word Ladder (30 points)
Wikipedia describes the rules for the word game Word Ladder as: The player is given a start word and an end word (of equal length). In order to win the game, the player must change the start word into the end word progressively, creating an existing word at each step. Each step consists of replacing a single letter. For example, the following is a solution to the Word Ladder puzzle between words “Cold” and “Warm”: COLD → CORD → CARD → WARD → WARM
1. (10 pts) Formulate the problem of solving word ladders as a search problem.
Answer. The start word is the start state and the goal test is to check if the current word is the goal word. A state is a valid word that can be generated. An action is to change one letter of the current word the lead to an existing word. The successor function determines the resulting valid word according to the action taken.
2. (10 pts) Consider a restriction where the words can only use the first seven letters (a-g). Draw the state space graph for converting “bee” to “dad”.
Answer. See Figure 2.
3. (10 pts) (Tree Search) Which part of the search tree is expanded by DFS? BFS?
1
bee
fee gee
dad
bed beg bad bag
fad gad
Figure 1: State space graph
Answer. For DFS, it depends on which order we use to select a node to expand in the search tree when a tie-break happen. For example, we may end up at the loop bee-fee-gee. Or we may follow the path bee-bed-bad-dad to reach the goal “dad”.
For BFS, it also depends on which order we use to select nodes to expand when a tie- break happen. However, unlike DFS, BFS can always find a solution if a solution exists. In particular, an example of an outcome of BFS is:
bee
gee bee fee
fee gee
bee bee
bed beg
dad
beg
bad bee bed bag
fad gad
bag
Figure 2: An example of the BFS expansion. All gray nodes are the nodes expanded. BFS stops the search when it find “dad” which is the goal.
Q2. Graph Search (50 points)
Consider the following graph. For the following sub-questions, ties are broken in alphabetical order. 1. (8 pts) In what order are states expanded by DFS? What path would DFS return?
2
Answer. States expanded: Start-A-B-D-Goal. Path: Start-A-B-D-Goal.
2. (8 pts) In what order are states expanded by BFS? What path would BFS return?
Answer. States expanded: Start-A-C-B-E-F-D-Goal. Path: Start-C-E-Goal.
3. (8 pts) In what order are states expanded by UCS? What path would UCS return?
Answer. States expanded: Start, A, C, F, E, B, Goal. Path: Start-C-E-Goal.
4. (8 pts) In what order are states expanded by Greedy? What path would Greedy return?
Answer. States expanded: Start-C-E-Goal. Path returned: Start-C-E-Goal 5. (8 pts) In what order are states expanded by A∗? What path would A∗ return?
Answer. States expanded: Start-A-C-E-B-F-Goal. Path returned: Start-C-E-Goal.
6. (5 pts) Is the heuristic in the graph admissible? If not, provide a minimal set of edges whose
costs must be changed along with their new costs to make the heuristic admissible.
Answer. Yes, the heuristic is admissible.
7. (5 pts) Is the heuristic in the graph consistent? If not, provide a minimal set of edges whose
costs must be changed along with their new costs to make the heuristic consistent.
Answer. Yes, the heuristic is consistent. Every arc true cost is greater than the arc heuristic cost.
Important note. For graph search, we never expand a state type twice.
B
h=3 2
AD
5
3 h=7 3 2
h=2 3
F Goal
h=5 h=0
Start h=9
4
424
C3E h=6 h=3
3
Q3. Hive Minds: Lonely Bug (20 points)
You control a single insect in a rectangular maze-like environment with dimensions M × N . Figure below is an example of such environment. The insect must reach a designated target location X, also known as the hive. There are no other insects moving around. At each time step, an insect can either (a) move into an adjacent square if that square is currently free, or (b) stay in its current location. Squares may be blocked by walls, but the map is known. Optimality is always in terms of time steps; all actions have cost 1 regardless of the number of insects moving or where they move.
1. (10 pts) Provide a minimal correct state space representation? What is the size of the state space?
Answer. A tuple ((x, y)) encoding the (x) and (y) coordinates of the insect. The size of the state is (MN).
Explanation. The position tuple is enough to calculate the goal test and successor func- tions.
Goal test: (x,y)=Goal
Successor: Similar to Pacman successors. EAST changes (x,y) to (x+1,y), for example. There are MN total values that the position (x,y) can take.
2. (10 pts) Provide two heuristics which are admissible.
Answer. (i) Manhattan distance from the insect’s location to the hive; and (ii) Euclidean distance from the insect’s location to the hive.
4