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.