Homework 2: Search Problems

EECS    492   
Homework 2: Search Problems (100 pts)

Instructions
● Submit a pdf of your work to gradescope, making sure to mark all pages
relevant to each outlined section on gradescope (including relevant code)
● Append all written code to the end of your pdf
Overview
This assignment covers topics in problem solving such as search
(including uninformed and informed search methods), local search
methods, and constraint satisfaction problems. You will apply search
methods to solve a variety of problems, some of which you will have
to formulate yourself. Some problems will require you to apply these
methods by hand while others will require you to implement them as
a computer program.
Task 1: Search Formulation (20 points)
In this problem you will learn to formulate problems as instances of
search problems on which you can run the algorithms we’ve talked
about in class. We will be considering the fox, goose, and bag of
beans puzzle, which, like the similar Missionaries and Cannibals
problem discussed in class, is a famous riddle that has existed in
many forms across many cultures for centuries.
https://en.wikipedia.org/wiki/Fox,_goose_and_bag_of_beans_puzzle
You need to transport a fox, a goose, and a bag of beans across a
river. Your boat only holds yourself and one of the three at a time, so 
EECS    492    Winter    2017 Prof.    Ed    Durfee
you must leave the other two on the bank of the river—either the
initial bank you start on, or the far bank to which you eventually want
to get. If left alone together, the fox would eat the goose, and
likewise the goose would eat the beans. (So for example, you cannot
leave the fox and the goose alone on the far bank of the river while
you go back for the beans, nor can you take the fox across the river
while leaving the goose and the beans alone.) The challenge of the
riddle is to figure out how to eventually get all three to the far bank of
the river without any of them devouring the other.
a. Develop the problem formulation that can be used to search for a
solution, providing a detailed description of the following:
1. A specific state representation that captures important details
and leaves out unimportant ones.
2. The initial state, expressed in your representation.
3. The goal test, expressed in terms of your representation.
4. The possible actions in any state and what successor
state(s) they lead to, again in terms of your state
representation.
5. A path cost function defined in terms of the actions and/or
states. There might be more than one reasonable choice for
this; briefly justify your choice.
b. Also, give numbers for the following:
1. How many different states are representable given your
choice of representation?
2. How many different representable states satisfy the goal
test?
3. How many of the representable states are “legal” (don’t
violate any constraints)?
4. How many different legal states are reachable (without
passing through illegal states) given your choice of representation,
the initial state, and the set of actions? 
EECS    492    Winter    2017 Prof.    Ed    Durfee
Task 2: Uninformed and Informed Search (30 points)
The components of a search problem can be encoded into a state
space graph like the one shown below.
• Each vertex (A-I) represents a state of the world.
• The initial state is labeled with “Start”.
• All states (here there is just one) that satisfy the goal test are
labeled with “Goal”.
• Directed edges show which actions (X, Y, or Z) transition
between which states. The cost of each action is also shown.
• Values of one particular heuristic are shown (e.g. h=5) for
each state.
Figure 1: The example graph you will use for this task.
You will work through the execution of various search algorithms as
they attempt to find a path to get from A, the start state, to a goal
state. Use the general search process discussed in class (goal test
only applied on examination/expansion), summarized in the textbook
in Figure 3.7. When writing out your solutions to the problems below,
use this notation:
• You can indicate a node by the path it represents (e.g. ADF)
• Write out the fringe as a list. For example, the fringe after
expanding node A could be written as: [AB, AC, AD]
EECS    492    Winter    2017 Prof.    Ed    Durfee
• The “front” of the fringe is on the left. In the above, AB would
be expanded next. When expanding a node and generating its
successors, assume the available actions (X, Y, or Z) are
processed in alphabetical order.
Here are two examples to rule out any possible confusion.
Expanding Node ADF with Breadth First Search
Actions Successor Nodes Updated Fringe (a
queue)
X, Z ADFG, ADFC […, ADFG, ADFC]
Expanding Node ADF with Depth First Search
Actions Successor Nodes Updated Fringe (a
stack)
X, Z ADFG, ADFC [ADFC, ADFG, …]
To show your work, show which node is expanded and which
successor nodes are generated at each step. Also write out the
contents of the fringe after and, if appropriate, the contents of the
explored set. If a successor is generated but immediately discarded
or if a node on the fringe is replaced, cross it out. As an example of
the format we’re looking for, here’s the execution of the start of
breadth first (graph) search:
Breadth First Search
Fringe Examined/
Expanded
Successors Explored Set
[A] A AB, AC, AD {A}
[AB, AC, AD] AB ABA, ABE {A, B}
If something goes wrong that prevents your algorithm from finding a
solution, show your work up to that point and include a description of
why the algorithm fails.
Show the execution of the following (graph) search algorithms:
a. Breadth First Search
EECS    492    Winter    2017 Prof.    Ed    Durfee
b. Depth First Search
c. Iterative Deepening Search (show all iterations)
Now, we will consider “best-first” algorithms that use an evaluation
function f(x) to prioritize node examination/expansion. If node ACF
has f(ACF) = 5, you should now write it as ACF(5). When adding new
nodes to the fringe, first add them to end and then make sure to sort
the nodes in a stable fashion. That is, if two nodes have equal
priority, the one that has been in the fringe longer will be
examined/expanded first. And if two successor nodes have the same
value, they will appear in their generated order.
Show the execution of the following search algorithms:
d. Uniform-Cost Search
e. Greedy Best-First Search
f. A* Search
The heuristic in the graph above turns out to be admissible (and
consistent). Consider specifically the heuristic value for state F,
h(F)=2.
Find a different (nonnegative real) value for h(F) that would make the
heuristic:
g. Inadmissible
h. Admissible but inconsistent
In both cases, explain your reasoning.
Task 3: Local Search (30 points)
The goal of the 8 queens problem, as discussed in the book (pg. 71 &
pg. 109) is to find a placement of 8 queens on a chessboard where
no two queens can attack each other. (Recall that queens can move
as far as they want in vertical, horizontal, or diagonal lines.) Choosing
any programming language you prefer, you are going to implement
the (steepest-descent) hill climbing and random-restart (steepest
descent) hill climbing algorithms to search for a solution to this
problem.
EECS    492    Winter    2017 Prof.    Ed    Durfee
 Figure 2. Left: the initial state Right: A possible solution
Suppose each queen is assigned to a particular column, and at each
step of the search you are allowed to move a single queen to another
square in the same column. The heuristic cost function is the number
of pairs of queens attacking each other, either directly (meaning that
one queen could capture the other, if this were an actual game and
they were of different colors) or indirectly (meaning that another
queen is in the way, but otherwise the queens could capture each
other).
Decide on a state representation and implement a cost function that
takes as input a given state and returns the heuristic cost value.
a. How would you represent the initial state and the solution state in
Figure 2? What are the outputs of your function for each of these two
states?
Next, implement a function that calculates the cost after each
possible single move, given a current state, and returns the best
move. If no possible single move provides improvement, then the
function should return the current state. Break ties by choosing the
move in the column farthest to the left. Given a tie within that column,
choose the move closest to the top of the board.
The steepest-descent algorithm starts with an initial state and
chooses a move that provides the greatest improvement. It then 
EECS    492    Winter    2017 Prof.    Ed    Durfee
repeats this process with the state resulting from the chosen move,
over and over again. The algorithm should halt when no single move
provides an improvement.
b. Using the initial state given in Figure 2, run your steepest-descent
algorithm. Was a solution found? What is the final state after the
algorithm terminates? What is the number of moves taken to reach
that final state?
Using the steepest-descent algorithm from above, implement the
random-restart hill climbing algorithm. For each (re)start, you should
choose a new, random initial state and begin steepest-descent with
this new initial state. This process should continue in a loop until a
solution (no attacking queens) is found, or until some limit on the
number of allowed (re)starts is reached. In your implementation, set
the limit on allowed (re)starts to 10.
c. Run your random-restart algorithm at least 5 times. (Note, because
of randomness it most likely won’t behave the same way each run!)
For each run of the algorithm, record the current best solution (the
number of attacking queens is sufficient) found for each (re)start
(including the final iteration right before the algorithm terminates), the
final state (best overall solution found across the (re)starts) when the
algorithm terminates, as well as the total number of moves taken
(summed over the (re)starts during a run). Was a solution found in
each run? If not, how often was one found?
d. Describe briefly how you can modify the steepest descent
algorithm above using simulated annealing to solve the 8 queens
problem. You do not need to provide pseudo-code or implement it.
What is an advantage compared with the steepest-descent algorithm
used in part b? Does it have any disadvantages?
Task 4: Constraint satisfaction (20 points)
You have been given the task of creating the University of Michigan's
football in conference schedule for the next (odd numbered) year.
The potential opponents and their home/away situation for each
weekend are listed below. 
EECS    492    Winter    2017 Prof.    Ed    Durfee
Team Weeks available for a
Michigan home game
Weeks available for a
Michigan away game
Michigan State 2
Nebraska 6 1, 6
Minnesota 4 3,4
Iowa 1,2,4,6 2
Northwestern 5,6 3,7
Indiana 6, 7
Illinois 1
Ohio State 5, 9
Penn State 7 6
Purdue 7,9
Wisconsin 7
The first five teams listed are all in the Legends Division of the Big
Ten Conference, and the final six are all in the Leaders Division of the
Big Ten Conference.
The schedule must meet the following constraints.
• Michigan can only play against one team each week
• Michigan only has one bye week (a week where they don't
play any opponent)
• Michigan cannot play the same team twice
• Michigan must play Michigan State, and Ohio State
• Michigan State is an away game for Michigan
• Ohio is a home games for Michigan
• Michigan must play all five other teams in the Legends
Division of the Big Ten Conference
• Michigan must play three teams from the Leaders Division of
the Big Ten Conference
• Michigan's last game of the season must be against Ohio
State
• Michigan must play exactly four home games and four away
games
The variables in this problem are W1, W2, ... W9 representing the
nine weeks of in conference play. Write values as the name (or
abbreviation) of an opposing school followed by an (a) or (h) for an 
EECS    492    Winter    2017 Prof.    Ed    Durfee
away or home game, respectively, or just “bye” for the value
corresponding to a bye week. For example, assigning Michigan to
play Ohio State at home on week 9 could be written by assigning W9
the value OSU (h).
Initially each week's domain is all the listed teams (11) at home + all
the listed teams away + the possibility of not playing that week (for a
total of 23 possibilities). The product of the (constrained) domain
sizes for every variable is the number of candidate solutions, as it is
an upper bound on the number of possible assignments that a simple
CSP solver needs to check. Before applying the unary constraints
there are 239 ≈ 1012 candidate solutions.
a. Apply the unary constraints to limit the domains of all the variables.
Show the resulting domains. Now how many candidate solutions are
there?
b. If you were to perform a backtracking search with no mechanisms
for forward checking, in the order of W1, W2, ... W9, expanding the
variables in the order they are shown in the above chart ( MSU(h),
MSU(a), Neb(h), Neb(a), ... Wisc(a) ) followed by the bye week
option, how many value-to-variable assignments will be made during
the search? How many backtracking steps (from a variable to the
previous variable) will take place? (For this and other parts of the
problem, you can show your work for getting your answers if you like,
to receive partial credit, but it isn’t required. You can also use a
program if desired, but it isn’t essential.)
c. Starting with the domains found in part 1, do a backtracking search
this time using forward checking and the MRV heuristic to order the
variables. Ties in the MRV heuristic should be broken so that the
variables are assigned in the same relative order as in part 2. How
many value-to-variable assignments will be made? How many
backtracking steps (from a variable to the previous variable) will take
place?