Introduction to Artificial Inteligence
Assignment 3 - solutions
Homework assignment - agents, search and propositional logic
1) For each of the following domains, which type of agent is appropriate
(table lookup, reflex, goal based, or utility based):
a) An agent that solves the cannibals and missionaries problem.
Goal based is OK. Since this is a VERY SMALL problem, however,
a reflex agent or even table lookup are sufficient!
b) An agent that plays chess.
Table lookup is out for practical reasons. Reflex is reasonable,
since only the current state matters. Goal based or utility is
probably the RIGHT way to do this, especially if we want to consider
MULTIPLE games of chess, but then this is NOT the way Deep Blue was
implemented!
c) An agent that can pass the Turing test.
It is unlikely that an agent that is not utility-based can pass such
a test. Of course, under the current state of the art, this is
also true for utility-based agents...
d) An autonomous robot for exploring Mars
Either planning agent, and even better would be a utility-based agent.
A pure reflex agent is unlikely to be very useful. Obviously,
table-driven is out.
EXPLAIN each choice in about 2 sentences.
2) We are given a search problem that has a path cost equal to the number
of operators applied on the path to reach the goal (i.e. the path length,
as in, e.g. the 8 puzzle). The branching factor is bounded by b (i.e. is
never more than b). We are given an admissible heuristic h, that is
never wrong by more than 2. There is exactly ONE optimal solution. How
many expansion steps are needed in A* to find an optimal solution of
length d, in the worst case, if there is NO other solution of length
less than d+3.
The right answer is: number of expansions is d+1.
Proof: consider a node n that is not on the optimal solution path. Any
solution that has n in the path has path cost at least d+3, and thus
f*(n) = g(n) + h*(n) >= d + 3, (where f* and h* are the exact total cost
and heuristic, respectively).
Since we have h*(n) - h(n) <= 2 we get
f(n) = g(n) + h(n) >= g(n) + h*(n) - 2 >= d+1
For the optimal goal node g, we have f(g) = d, since h is admissible,
and because f is monotonic g is expanded before n. Thus, only nodes on
the optimal path are expanded.
SORRY, earlier solution was an answer to some OTHER question...
3) Invent a heuristic function for the travelling sales-person problem (TSP)
and show a case where it can lead to a sub-optimal solution where the
path cost is the total tour length (or argue
that such a case does NOT exist DESPITE the over-estimate)!
(Recall that TSP is the problem of finding a minimal-weight complete
(i.e. visit every node once) tour in a weighted graph).
Obviously, we mean an INADMISSIBLE heuristic, or with A* we will not
get a sub-optimal solution. It is interesting to find a such a heuristic
that is also USEFUL (as shown below), but that was NOT a strict
requirement of the exercise.
Assuming the search problem definition uses a state thet is a partial
solution, and an operator adds an arc to the tour (initial state
being the empty tour), we now define a heuristic as follows, based on an
ADDMISSIBLE heuristic... (Alternate definition of TSP as a search
problem is ALSO possible, e.g. start from a complete graph and remove
edges, etc.)
The heuristic for node n in the search space will be: number of missing
arcs (= number of unvisited cities, if we need the version of TSP that
is also Hamiltonian), multiplied by some weight. Now, if we use a weight
that is the MINIMAL COST of all remaining arcs, we get an ADDMISSIBLE
heuristic. However, if we take a LARGER weight, we can get an INADDMISSIBLE
heuristic. We will use heuristic where we take cost of the MOST EXPENSIVE
arc as a weight. This heuristic is useful, but can lead to a
suboptimal solution in the following graph (assume we want a CYCLIC
HAMILTONIAN tour for this example, and that the arcs are UNDIRECTED).
Nodes in graph: a, b, c, d
arc cost
----------------------
a - b 1
b - c 1
b - c 5
a - c 100
a - d 5
c - d 2
There are 3 possible cycles:
a-b-c-d-a (cost 13)
a-b-d-c-a (cost 104)
a-d-b-c-a (cost 111)
What will happen is that the partial tour a-b-d which has an f cost
of 202 (g is 2, and 2*100 is the heuristic evaluation here) is expanded
next as it is beeter than all the rest. The node leading to the optimal
solution, (a-b-c) will have an f-cost of 1+5+2+100 = 108, and before
it is visited, node a-b-d-c-a (cost 108) will be expanded and returned!
4) Give an example of a 3-person game tree where the best choice of move
made by player A will be DIFFERENT for all of the following assumptions:
a) Paranoid assumption: all that players B and C want is to make it bad
for player A.
b) Each player out to help itself, with no communication.
c) Same as b, but player B and C can make deals.
d) Same as c, but A can also make deals.
Th following tree. We denote by tuples (a b c) the score for a, b, c
respectively. Also, as we can't draw very easily in ASCII, we will
denote choices by "i" where i is a number, for each player. Tree is:
A B C scores
0 0 0 (9 0 10)
0 0 1 (-10 3 0)
0 1 0 (-10 -10 3)
0 1 1 (-10 2 2)
1 0 0 (1 -10 -10) (moves for B, C forced - no choice)
2 0 0 (-1 2 1)
2 0 1 (-10 1 -10)
2 1 0 (3 3 3)
2 1 1 (-5 0 4)
3 0 0 (-10 10 5)
3 0 1 (-5 5 5)
3 1 0 (10 4 0)
Now, consider the options:
a) Under the paranoid assumption, the only move that will guarantee a positive
score for A is choice 1.
b) If each player is out to improve his own score with no communication,
optimal choice for A is 0 - in order to get 9,
since B will choose 0 (to avoid -10 due to C
choosing C's optimum, 0 - leading to a score of 2 for C).
Note choice 2 will result in a score < 10 for A, and choice 3 will result
in B choosing 0 (guaranteeing 4 for B), and a bad score for A.
c) If B and C can deal, choice 0 is bad because then B, C will deal to get 2
each (option 0 1 1 - a score of -10 for A). In choice 2, B and C will make
a deal to get 3 each and 3 for A. If A chooses 3, B will move 0 and
A will get a negative score. Optimal move for A is 2.
d) If A can deal with B only, then A should choose 3 if B agrees to move 1
(benefits B because A can always move 1) - resulting in 10 for A. This
good score is not avaiable elsewhere.
5) Which of the following are valid, satisfiable, or neither:
a) Good => Good VALID (since this is like ~Good v Good,
which holds if Good is T and also if it is F)
b) Good => Bad SATISFIABLE (Good = F, Bad = F is a model,
but Good = T, Bad = F is not)
c) (Bad => ~Good) => (Good => ~Bad)
VALID. In fact, both sides of the main
implication have the same models, so this
is like the tautology a => a.
d) (Good => ~Good) SATISFIABLE (Good = F is a model,
but Good = T is not)
e) Big v Dumb v (Big => Dumb) VALID (the first 2 disjuncts are satisfied
for every assignment, except F, F. But
the last disjunct is satisfied in that case,
since F => F is true.)
f) Good v Bad v Ugly SATISFIABLE (but not valid - all propositions
F is not a model)
g) (P <=> Q) <=> ((~P v Q) ^ (P v ~Q))
Consider the truth table below:
P Q P<=>Q ~PvQ Pv~Q (~PvQ)^(Pv~Q)
---------------------------------------------------
F F T T T T
F T F T F F
T F F F T F
T T T T T T
We can see that under all possible assignments ("worlds"), the left
hand side is the same as the right-hand side of the equivalence
statament. Thus, the sentence is VALID.