Introduction to Artificial Inteligence
Assignment 3
Homework assignment - simulators, agents, search and 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 can play chess.
b) An agent that plays poker.
c) An agent that can imitate Saddam Hussein.
d) An autonomous robot for guarding the border against infiltrations by hostiles.
EXPLAIN each choice in about 2 sentences.
2) Represent the following sentences in FOPC - define the vocabulary first.
a) Every tripod has three equal-length legs.
b) All animals are equal, but some are more equal than others.
c) All polititians can fool all stupid people some of the time.
d) You will get this report when hell freezes over.
e) The town barber shaves every man who does not shave himself.
3) In the wumpus world, in situation S0, the robot, is facing the wumpus
(facing_wumpus), and has an arrow (has_arrow), and does not have the gold.
The pickup action results in the robot holding the gold (has_gold).
The shoot action results in the wumpus being dead (not alive(wumpus))
if the robot is facing the wumpus and has an arrow.
a) Write down the axioms for the above information for variant of
wumpus world.
b) Can you prove that has_gold(result(grab, result(shoot, S0)))
with your axioms? If yes, do so. If not, what is missing?
c) Can you prove that not alive(wumpus, result(shoot, result(grab, S0)))
with your axioms? If yes, do so. If not, what is missing?
d) Convert the knwoledge base (after fixes) into CNF.
e) Perform the proof of b and c formally using resolution refutation proof.
Predicates are: has_gold(situation), has_arrow(situation), alive(who, situation)
facing_wumpus(situation)
Actions are: grab, shoot
4) We have a search problem where the cost of each operator is 1. The branching
factor is bounded by b. We have a heuristic evaluation function h(n) that
is admissible, and such that h(n) >= h*(n) - 1 (that is, it is never off by more than 1).
We use h(n) as a search heuristic in the A* algorithm.
a) Suppose that there is only one solution to the problem. How many nodes will be
expanded by A* using h(n) above as a heuristic, in the worst case, if
h*(initial_state) = d ?
b) How does the above change if there is more than one solution, but any other solution
has path cost at least 2 greater than d?
c) Same as in (b), but there is also ONE solution with cost d+1.
5) Consider a 3-person complete information game between players A, B, and C,
playing in turn (first A, then B, then C, and then the game ends).
The game tree is defined as follows:
A B C scores
----------------------------
A1 B1 C1 (100, 5, 20)
C2 (50, 10, 0)
B2 C1 (10, 20, 30)
C2 (20, 0, 50)
A2 B1 C1 (90, 0, 80)
C2 (0, 20, 90)
A3 B1 C1 (90, 0, 20)
C2 (80, 30, 0)
B2 C1 (80, 0, 40)
C2 (0, 0, 0)
B3 C1 (30, 20, 50)
A4 B1 C1 (0, 90, 50)
C2 (20, 70, 70)
B2 C1 (100, 100, 0)
C2 (95, 95, 1)
Assume that the scores theoretically achievable by each player are
all between 0 and 100.
a) What is the best play for A, assuming that each player is out to improve
its own score, and there is no communication between players?
b) If players can reach agreements, will this make any difference
(answer separately for each different type of agreements).
c) How will the answer change if A is paranoid (i.e. believe that the other
players will act to minimize A's score)?
d) Suppose that C always plays randomly with uniform probability. What
is the best action by A now?
e) Will using alpha-beta pruning above (modified alpha-beta in case d)
save any search in the search algorithm for the best move? What will
be the savings in each case? Assume
(and show) the best-case ordering for the search.
f) How would you treat the problem if B could not observe the move
made by A?
6) A rational agent has a choice of algorithms to apply for a search problem.
Suppose the agent need to minimize total operating costs,
which are given as: 1000 * G + S, where G is the cost of the path taken
by the agent, and S is the number of search steps used by the search
algorithm.
a) Assuming that the agent knows the above, and reasons to optimize
the cost, what type of agent is this (reactive? goal-based? etc.).
b) Assume that the agent has 3 choices:
1) Use default actions without search, and use an immediately available
solution with cost 10000.
2) Use A*, where it has an admissible heuristic that is usually
wrong by a factor of 2.
3) Use RTA*, with the same heuristic, and a limit of 100 search steps.
We assume that the branching factor is 2, and that the agent knows
(correctly) that there exists a solution at depth 10. (Assume operator
cost of 1, and that the search space is acyclic).
(Note: there may be insufficient information to answer b, but the point
is to try to answer, and to figure out what's missing, if anything, and
what further assumptions may be necessary).
7) Consider the following search problem (also known as the WEIGHTED ABDUCTION
problem, which is NP-hard). You have a list KB of weighted
of propositional Horn clauses, i.e. clauses of the form:
X1 and X2 and ... and Xn implies Y
where each clause C has a weight w(C). For some rules, n=0, i.e.
nothing is required to imply Y. A proof is defined as a set of clauses P
(from KB), such that if C is in P, then all propositions in the body of C
must also be in the head of some clause C' in P. In addition, proof P
is a proof of X if X is also in the head of some clause C' in P.
The weight (or cost) of a proof P is
the sum of costs of all the clauses in P. The problem is: given clauses KB and
proposition Y, find the proof P (subset of KB) for Y that has the least cost.
a) Write the above problem as a formal search problem. Note that the
path cost has to reflect the proof cost.
b) If we represent the state in a node as a set of clauses P (that is
not necessarily a proof), we consider the following heuristic:
h(P) = sum of the costs of all clauses in P
Now, we run the A* algorithm on this problem, using the above h as
a heuristic. Is the algorithm guaranteed to find the least-cost proof?
PROVE you answer.
(As discussed in class: clue - what would happen if we used as a heuristic
h(P) = 0 for all P? How would the search be different, if at all?)
c) This sub-question also serves as an example for the above. Suppose that
the give clauses in the knowledge base (KB) are:
C1: A and B implies X (with cost 5)
C2: B and C implies X (with cost 2)
C3: D implies B (with cost 3)
C4: D implies C (with cost 1)
C5: E implies A (with cost 14)
C6: E implies D (with cost 1)
C7: E (with cost 2)
C8: Y implies X (with cost 1)
C9: Y (with cost 30)
Note that here, the set of clauses P = {C8, C9} is a proof of X,
because X is at the head of rule C8, and Y is at the head of rule C9,
and there are no other propositions mentioned in P. The cost of P is 31.
Show all the steps of the search using A* on the above problem, where
we need to find the least-cost proof for X.
d) Consider the following heuristic h'(P):
h'(P) = h(greedy_extension(P)-P)
where greedy_extension(P, KB) is computed as follows:
greedy_extension(P, KB) {
P' = P;
while(P' is not a proof and P' not = KB) {
Find an arbitrary C in P', and Z in the body of C, such that
Z does not appear as the head of any rule in P'. (Intuitively:
some Z that is not "justified" in P'.)
From all the given rules in KB, find the lowest-cost
rule C' that has Z as its head, and add C' to P'.
If there is no such rule, return KB.
}
return P'
}
Is the above heuristic computable in polynomial time? Is it addmissible?
Prove your answers!
Deadline: May 10, 2006, at 12 noon.