Introduction to Artificial Inteligence
Assignment 3 - Solutions
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 solves the 8 puzzle.
A goal driven agent is "theoretically" the best. However, since
this particular problem has a very small state space, a reflex
agent, even based on TABLE LOOKUP, will suffice!
b) An agent that plays backgammon.
Table lookup will probably NOT work, as the state space is too large.
Reflex is possible IF we can
find a nearly perfect heuristic. Utility based is probably the best
way to go.
c) An agent that can imitate Saddam Hussein.
This problem is ill posed - first we need to define Saddam Hussein. Some
will argue that table lookup will suffice, and reflex is more than
enough. However, if we concede that he is human, we will need a
utility based agent. The utility function used will be very counter
intuitive...
d) An autonomous robot for exploring the bottom of the sea.
A goal-based agent in very simple cases, and utility based for
anything else.
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 a perfect admissible heuristic h, i.e. is
never wrong.
How many expansion steps are needed in A* to find an optimal solution of
length d, in the worst case, if:
1) There is exactly ONE optimal solution.
2) There are k optimal solutions.
You need to PROVE your answer!
The proof for (1) goes as follows. First, we note that for every node n*
on the optimal path, we have f(n*)=g(n*)+h(n*)=d.
That is because h is the exact number of steps in an optimal partial
solution from n* to the goal state, and g(n*) is the number of steps
from the initial state to a node in an optimal path. Now, let n be a
node expanded by A* that is NOT on the optimal path, and assume that
is the FIRST such node. Clearly, its parent in A*, call it N, is on
the optimal path. Now, from n, there is a path of cost h(n) to the goal
state, because h is exact. Now, f(n) = g(n) + h(n) = g(N) + 1 + h(n)
and clearly h(n) > h(N) - 1, because otherwise the path through N and n
and then proceeding optimally to the goal will have
length <= g(N) + h(N) = d, another solution with cost at most d.
But if h(n) > h(N) - 1, then f(n) > g(N) + h(N) = d. Thus, all nodes
on the optimal path (including the goal state) are expanded BEFORE n,
and thus n is never expanded, i.e. in this case ONLY nodes on the optimal
path are expanded - a total of d+1 expansions - since there is
only one optimal path (assuming that if goal=initial-state we count this
as a depth of 0)
In case (2), AGAIN only nodes along an optimal path are expanded, but this
time there are k paths, so no more than k*d+1 nodes are expanded. In fact,
the number must be smaller, unless k <= b, because if k >= b some nodes
MUST be shared between paths, IN ADDITION to the initial state.
3) Give an example of a 2-ply (the ply count not including the random element, i.e.
the tree should have a move by each opponent) EXPECTI-minimax game tree
where modified alpha-beta pruning saves NOTHING, and another where the savings
is maximal. The tree should have branching factor 2 -
both for players and random element, which can be assumed to be a (not necessarily
balanced) coin. How many nodes are pruned in each case?
We will denote a coin toss by 0 or 1, moves of MAX by A or B, and moves
of MIN by a or b. Thus, a path to a leaf node is denoted by
(MAX-move)(Coin)(MIN-move), e.g. A0b. In this case, we need to state
the probabilities of the coin toss and the score at the leaf, in this
case only ONE coin toss, so we can denote the tree as a list of
paths: (MAX-move)(Coin)(MIN-move)(probability)(score). We will assume
that the paths are sorted by the order visited by the algorithm (unless
they are pruned). First, note that NOTHING can be pruned unless the
scores are BOUNDED or the probabilities are extreme (i.e. some are 0).
In this example, we will assume a FAIR coin, and thus omit the
probability, which is always 0.5. We will assume that the score is
guaranteed to be between -10 and 10.
a) In the following case, no pruning is possible:
A0a 10
A0b 4 (preferred by MIN)
A1a 0 (preferred by MIN)
A1b 2
B0a -4 (preferred by MIN)
B0b -2
B1a 8 (preferred by MIN)
B1b 10
Value of A0 is 4, and value of A1 is 0, thus value of A is the average,
i.e. 2.
Now, with no random element, once we see B0a (score -4) we would not
be interested in the rest of the nodes, because MAX will not pick
B. However, due to averaging, in fact we have - score of B0 is -4,
Score of B1 is 8, and thus score of B is the average, i.e. 3, so
MAX should pick B.
b) In the same example, suppose that B0a has score -8, and all the rest
stays the same. Now, it is clear that score of B0 is at most -8.
Score of B1 is at most 10 (the global bound on scores), and thus
the score of move B cannot be more than 1, so MAX should pick A and
the result in B0b, B1a, and B1b is irrelevant to this choice, so
B0b, as well as B1 and its children can be pruned.
4) Use truth tables to show that the following sentences are valid:
a) (P <=> ~Q) <=> ((~P v ~Q) ^ (P v Q))
b) ~(P ^ Q) <=> (~P v ~Q)
Note: this is one of the De-Morgan rules.
c) (~P => Q) <=> ~(~P ^ ~Q)
This is trivial, so no answer provided here...
5) Which of the following are valid, satisfiable, or neither. For each
satisfiable sentence, how many models does it have (assuming that each
sentence contains ALL the variables in the world).
a) Good => Good
Valid, so 2^n models, with n (number of variables)=1...
b) Good => Bad
Satisfiable, where only (Good ^ ~Bad) not being a model, so 2^2-1=3
b) Bad => Good
Satisfiable, again 3 models.
c) (Bad => ~Good) => (Good => ~Bad)
This is equivalent to (Good ^ Bad) v ~Good v ~Bad which is valid
(actually, a well-known tautology), and has 2^2=4 models.
d) (Good => ~Good)
Satisfiable, 1 model: ~Good
e) Big v Dumb v (Big => Dumb)
This is equivalent to: Big v Dumb v ~Big v Dumb
Which is valid, so 2^2=4 models
f) Good v Bad v Ugly
Satisfiable, where only (~Good^~Bad^~Ugly) is not a model, so 2^3-1=7
6) Represent the following sentences in FOPC - define the vocabulary first.
a) Every cloud has a silver lining.
(forall x) cloud(x) => has-silver-lining(x)
Where cloud(x) is a predicate denoting that its argument is a cloud,
and has-silver-lining(x) is a predicate denoting that its argument
has a silver lining.
The above is NOT good knowledge engineering! Better is:
(forall x) cloud(x) =>
(exists y) part-of(x, y) and lining(y) and colour(y, silver)
Where part-of(x, y) denotes that y is part of x, lining(x) denotes
that x is a lining, and colour(y, z) denotes that y has colour z -
note that this allows for more than one colour per object.
From now on, we will NOT state what the predicates denote, we will
use indicative names, but YOU should still state the intended
meaning of all predicates.
b) All men are mortal, but cats have 9 lives.
((forall x) man(x) => mortal(x)) and
(forall x) cat(x) => has-9-lives(x)
Again, the last part is BAD knowledge engineering!
At the very least, we should define a function counting the number
of lives a creature has - num-lives(x), and state:
(forall x) cat(x) => num-lives(x)=9
c) Some polititians can fool all stupid people all of the time.
(exists x) politician(x) and
(forall y, t) (person(y) and stupid(y)) => can-fool(x, y, t)
d) Every dog has more than 2 legs and exactly one tail.
(forall x) dog(x) =>
(((exists y) tail(y) and part-of(x, y) and
(forall z) (tail(z) and part-of(x, z)) => y=z) and
((exists y, z) leg(y) and leg(z) and part-of(x, y) and part-of(x, z) and
(forall w) (leg(w) and part-of(x,w)) => (w=y or w=z)))
e) There is a barber who shaves all men in town who do not shave
their barber.
(exists x) barber(x) and
(forall y) (man(y) and and in-town(y) ~shaves(y, barber(y))) =>
shaves(x, y)
where barber(x) is a function denoting the object who is the barber
of x.
7) In the wumpus world, in situation S0, the robot is in room (x, y), which has
the gold.
The move(dx, dy) action moves the robot by dx and dy, resp. (no "turn" necessary
in this version).
If the robot has the gold, the gold moves with the robot, and is considered
to be in the room (in_room(gold, (x, y), S)).
The pickup action results in the robot holding the gold (has_gold),
if the gold is in the same room as the robot.
a) Write down the axioms for the above information for variant of
wumpus world.
axiom for what move does:
(forall x, y, dx, dy, s) in_room(robot, (x, y), s) =>
in_room(robot, (x+dx, y+dy), result(move(dx, dy), s))
axiom for location of gold on the robot:
(forall x, y, s) in_room(robot, (x, y), s) and has_gold(s) =>
in_room(gold, (x, y), s)
axiom for what grab does:
(forall x, y, s) in_room(robot, (x, y), s) and in_room(gold, (x, y), s) =>
has_gold(result(grab, s))
b) Can you prove that in_room(gold, (x+dx, y+dy),
result(move(dx, dy), result(grab, S0)))
with your axioms? If yes, do so. If not, what is missing?
No, because we cannot prove that the robot still has the gold in
the situation resulting from the move. This can be "fixed" by adding
an axiom stating that "move" does not affect has_gold:
(forall dx, dy, s) has_gold(s) => has_gold(result(move(dx, dy), s)
c) Can you prove that in_room(gold, (x+dx, y+dy), result(move(dx, dy), result(wait,
result(grab, S0))))
with your axioms? If yes, do so. If not, what is missing?
Again, no, because again one must add "frame" axioms for wait:
(forall s) has_gold(s) => has_gold(result(wait, s)
(forall x, y, s) in_room(robot, (x, y), s) =>
in_room(robot, (x, y), result(wait, s)) =>
Predicates are: has_gold(situation), in_room(object, room, situation).
Actions are: grab, move(dx, dy), wait.
Deadline: December 5, 2002, at 12 noon.