CSCI 373 Spring 1998 Final Exam Review

The final exam may contain questions from the two earlier exams as well as any of the questions listed below.

QUESTIONS ON AGENTS

Explain the difference between an episodic and a nonepisodic environment.
All other considerations aside, would a reflex agent be appropriate for an episodic environment? Explain your answer.

SEARCH QUESTIONS

Many of the search algorithms that we studied used a common algorithm referred to in the book as the "general search algorithm". Write a pseudo-code description of that algorithm. Describe the differences in the queuing functions (i.e., the functions that determine the order in which the nodes are expanded) used by the following search algorithms:
- breath-first
- depth-first
- uniform-cost
A* search makes use of the "general search algorithm" as well, but as we know it can be the most efficient of the optimal and complete search algorithms. This is because of the evaluation function used in A* search. Describe that evaluation function. Include a description of the relationship that the A* search evaluation function has to the evaluation functions used in uniform cost search and greedy search. When is A* search not complete and optimal?
Explain the difference between best-first search (also called greedy search) and hill-climbing search.
When is a heuristic admissible?
Describe a search space in which iterative deepening search performs worse than depth-first search.
List the 3 constituents that define a search problem? These constituents are same for any search strategy.
It has been said (in class and in the book) that the process of finding a proof can be formulated as a search problem. In such a formulation, what are the 3 constituents listed above?
State whether each of the search algorithms listed below is both complete and optimal.
- breath-first search
- uniform-cost
- depth-first search
- iterative deepening
- A* search
Is it possible to generate an infinite search tree when searching a finite search space? Briefly explain your answer.
The sliding-title puzzle consists of three black tiles, three white tiles, and an empty space in the configuration shown below.

	-----------------------------
	|   |   |   |   |   |   |   |
	| B | B | B |   | W | W | W |
	|   |   |   |   |   |   |   |
	-----------------------------

The puzzle has two legal moves with associated costs:
- A tile may move into any adjacent empty location. This has a cost of 1. A tile can hop over one or two other tiles into the empty position. This has a cost equal to the number of tiles jumped over.
- The goal is to have all white tiles to the left of all black tiles. The position of the blank is not important.
What is the average branching factor of this state space?
Propose 1 heuristic for solving this problem. Is the heuristic admissible?

LOGIC QUESTIONS

Give a definition for the following:
- a term
- a ground term
- an atomic sentence
- a literal
- a valid sentence
- a sentence that is satisfiable
- entailment
- a sound inference procedure
- a complete inference procedure
- proof theory
For each of the following pairs of clauses, choose an instantiation of the variables that allows a deduction to be made and give the deduced clause. THIS MAY NOT BE POSSIBLE IN ALL CASES---IF IT IS NOT POSSIBLE, SAY SO. You may think of father(x,y) as asserting that x is the father of y. (To permit the use of a function, assume that a unique brother exists and the same for the son.)
- ~father(george,x) | wealthy(son(x))
  father(george,mike)
- ~father(george,x) | wealthy(son(x))
  father(george,brother(jim))
- ~father(george,x) | wealthy(son(x))
  ~wealthy(son(brother(mike)))
- equal(sum(minus(x),x),0)
  ~equal(sum(minus(4),y),z) | equal(sum(z,4),y)
- equal(times(x,x),square(x))
  ~equal(times(y,z),z) | equal(y,1) | equal(z,1)

The problems below refer to the simplified wumpus world introduced in class in which there were only 2 actions: grab and goForward, and all cells were laid out in a straight line:

at(W,X,S) means that Wumpus is at location X in situation S
holding(gold,S) means that the agent is holding the gold in situation S
result(X,S) designates the situation that results from doing action X in situation S.
Suppose that the following FOPL sentence is in the knowledge base:
- all S, X (at(agent,X,S) & at(gold,X,S) & -holding(gold,S) -> holding(gold, result(grab,S))).
Write an axiom that allows the system to infer that, once the agent has grabbed the gold (in situation S), it is still holding the gold in situations resulting from performing goForward actions. (Just represent this relatively small piece of knowledge.)
Is the axiom you wrote in the previous question an effect, or frame axiom?
Suppose that we are solving a part of the simplified wumpus world problem using situation calculus in standard FOPL, and the following is the only implication currently in the knowledge base with holding on the right-hand side:
all X, S (at(agent,X,S) & at(gold,X,S) & -holding(gold,S) -> holding(gold, result(grab,S))).
Suppose that the only other sentences currently in the knowledge base are:
- at(agent,start,s0).
- at(gold,middle,s0).
- -holding(gold,s0).
Is the system able to infer holding(gold,result(grab,s))? How about -holding(gold,result(grab,s))?
For each of the following, translate it into a FOPL sentence, and then convert the result into conjunctive normal form (clausal form).
- Every husband is-married-to a wife.
  (note: the husbands are not all married to the same wife).
- Every Englishman is-subject-to a queen.
  (note: there is only one queen)
Is this sentence valid or is it satisfiable?
- ((Smoke & Heat) -> Fire) -> ((Smoke -> Fire) | (Heat -> Fire))
Explain the difference in semantics (if there is any---there may not be) that exists in each pair of FOPL sentences listed below:
As an example, given the pair:
- Exists x P(x) and All x P(x)
an acceptable explanation of the difference in semantics would be:
Exists x P(x) is true when one or more objects in the model have the property P. All x P(x) is true when all objects in the model have the property P.
- All y Exists x P(x,y) and Exists x All y P(x,y)
- All x P(x) -> Exists y Q(y) and All x Exists y P(x) -> Q(y)
- All x P(x) -> Q(x) and All x P(x) & Q(x)
- Exists x P(x) & Q(x) and Exists x P(x) -> Q(x)
Using the following predicates:
- animal(x) which means x is an animal
- plant(x) which means x is a plant
- eats(x,y) which means x eats y
- smaller(x,y) which means x is smaller than y
encode the sentence below in FOPL:
- Every animal either likes to eat all plants or all animals smaller than itself.
Given the following English sentences, prove that:
Someone watchs sports and is not an athlete. Use resolution-refutation.
- Athletes play sports.
- Couch potatoes do not play sports.
- Some couch potatoes watch sports.
Given the following information, prove that:
Bill is an animal abuser. Use resolution-refutation.
- Someone who beats the dog that they own is an animal abuser. Pasta is a dog and she is beaten by Bill. Bill is Pasta's owner.
Which of the following sentences are valid:
- (Smoke -> Fire) -> ((Smoke & Heat) -> Fire)
- (Smoke -> Fire) -> (~Smoke -> ~Fire)
- Smoke | Fire | (Smoke -> Fire)
- (Smoke & Fire) | ~Fire

Do the proof described below

           The Mislabeled Boxes
      
   There are three boxes a, b, and c on a table.
   Each box contains apples or bananas or oranges.
   No two boxes contain the same thing.
   Each box has a label that says it contains apples
   or says it contains bananas or says it contains
   oranges. No box contains what it says on its label.
   The label on box a says "apples".
   The label on box b says "oranges".
   The label on box c says "bananas".
   You pick up box b and it contains apples.

Prove that box a contains bananas.