Artificial Intelligence

• Can there be more than one agent program that implements a given agent function? Give an example, or show why one is not possible.
  • There are infinite agent programs that implement a given agent function. If an agent function acts only depend on previous \(n\) percepts. Than, the agent implementations that have n or more memory will always produce the same action.
• Are there agent functions that cannot be implemented by any agent program?
  • Yes. As the textbook said: "No machine can tell in general whether a given program will return an answer on a given input or run forever."
• Given a fixed machine architecture, does each agent program implement exactly one agent function?
  • Yes. A program implements a mapping from percepts to actions. The same percept will only result in one action.
• Given an architecture with n bits of storage, how many different possible agent programs are there?
  • There would be \(a^{2^n}\) possible programs; \(2^n\) possible states and \(a\) choices for each state.
• Suppose we keep the agent program fixed but speed up the machine by a factor of two. Does that change the agent function?
  • No. The speed does not have influence on the produced action.

Give a complete problem formulation for each of the following. Choose a formulation that is precise enough to be implemented. d. You have three jugs, measuring 12 gallons, 8 gallons, and 3 gallons, and a water faucet. You can fill the jugs up or empty them out from one to another or onto the ground. You need to measure out exactly one gallon.

Define a 3-tuple (x,y,z) where x,y,z are the amount of water in the three jugs.

• Initial state: (0,0,0).
• Action:
  • FILL: given values (x,y,z) , generate
    • (12,y,z), (x,8,z), (x,y,4)
  • EMPTY: given values (x,y,z) , generate
    • (0,y,z), (x,0,z), (x,y,0)
  • POUR: Given value (x,y), let t = min(x+y, cap(y)), pour x into y, generate:
    • (x-(t-y), t)
• Cost function: Number of actions.

三个野人，三个传教士，一艘船。如何过河？

3.26 Consider the unbounded version of regular 2D grid shown in Figure 39. The start state is at the origin, (0,0), and the goal state is at (x,y).

• What is the branching factor b in the state space?
• How many distict states are there at depth k (for k > 0)?
• What is the maximum number of nodes expanded by breadth-first tree search?
• What is the maximum number of nodes expanded by breadth-first graph search?
• Is h= |u-x| + |v-y| an admissible heuristic for a state at (u,v)? explain.
• How many nodes are expanded by A* graph search using h?
• Does h remain admissible if some links are removed?
• Does h remain admissible if some links are added between nonadjacent states?

• What is the branching factor b in the state space?
  • Since it is a 2D grid, there're 4 directions for each node. The branching factor is 4.
• How many distict states are there at depth k (for k > 0)?
  • For depth 1, there're 1+4 states;
  • For depth 2, there're 1+4+8 states;
  • For depth 3, there're 1+4+8+12 states;
  • For depth k, there're 1 + 4 + 8 + .. + 4k = 2k² + 2k + 1
• What is the maximum number of nodes expanded by breadth-first tree search?
  • The depth of the goal is |x|+|y|, and if we allow the loopy states on the search tree, we will have 4 branches for each node. Thus the maximum total nodes to be expanded: \(1 + 4^1 + 4^2 + .. + 4^(|x|+|y|)\)
• What is the maximum number of nodes expanded by breadth-first graph search?
  • For graph search, we only expand nodes that are not in exploded set. The expanded nodes will be the distinct state of depth |x|+|y|: 1 + 4 + 8 + .. + 4k
• Is h= |u-x| + |v-y| an admissible heuristic for a state at (u,v)? explain.
  • Yes. Because it never overestimates the cost: it is the optimal path from (u,v) to (x,y) in a 2D grid given that all links cost 1.
• f. How many nodes are expanded by A* graph search using h?
  • It is |x|*|y|. Because all the paths in the rectangle are optimal paths.
• g. Does h remain admissible if some links are removed?
  • Yes. Removing links can only make the best path longer if possible, so h remains an underestimate.
• h. Does h remain admissible if some links are added between nonadjacent states?
  • No. We could add some links that makes the optimal solution shorter. Thus h would overestimate the cost.

6.4 Given the precise formulations for each of the following as a Constraint Satisfaction Problems:

1. Rectilinear floor-planning: find non-overlapping places in a large rectangle for a number of smaller rectangles.

• Variables:
  • WIDTH and HEIGHT for the large rectangle.
  • R_i for each rectangles, R_i.w and R_i.h for the width and height of R_i respectively.
  • the position P_i for top-left corner of the rectangle R_i (P_i.x and P_i.y for the co-ordinates)
• Domains: {P_i.x ∈ [0, WIDTH]}
• Constraints: the four corners of R_i should not be inside the area of R_j, for each \(i \neq j\)
  • for each \(i \neq j\)
  • for each corner \((x,y)\) in \(\{(P_{i}.x, P_{i}.y)\), \((P_i.x + R_i.w, P_i.y)\), \((P_i.x, P_i.y + R_i.h)\), \((P_i.x+R_i.w, P_i.y + R_i.h)\}\)
  • \(\neg (P_{j}.x < x < P_{j}.x + R_{j}.w \cap P_{j}.y < y < P_{j}.y + R_{j}.h)\)

1. Class scheduling: There is a fixed number of professors and classrooms, a list of classes to be offered, and a list of possible time slots for classes. Each professor has a set of classes that he or she can teach.

• Variables:
  • P_i for each professor, with \(P_i.classes\) be the set of classes he or she can teach
  • R_i for each room
  • C_i for each class
  • T_i for each time slot
  • Assignment A_i, the i-th assignment, is a 4-tuple \((A_i.prof, A_i.room, A_i.class, A_i.time)\).
• Domain
  • \(A_i.prof\) ∈ {P_j}
  • \(A_i.room\) ∈ {R_j}
  • \(A_i.class\) ∈ {C_j}
  • \(A_i.time\) ∈ {T_j}
• Constraint
  • \(A_i.class \in A_i.prof.classes\) for all i
  • \(\neg (A_i.time = A_j.time \cap A_i.prof = A_j.prof)\) for all \(i \neq j\)
  • \(\neg (A_i.time = A_j.time \cap A_i.room = A_j.room)\) for all \(i \neq j\)

Consider the following logic puzzle: In five houses, each with a different color, live five persons of different nationalities, each of whom prefers a different brand of candy, a different drink, and a different pet. Given the following facts, the questions to answer are "where does the zebra live, and in which house do they drink water?" Discuss different representations of this problem as a CSP. Why would one prefer one representation over another?

The Englishman lives in the red house.
The Spaniard owns the dog.
The Norwegian lives in the first house on the left.
The green house is immediately to the right of the ivory house.
The man who eats Hershey bars lives in the house next to the man with the fox.
Kit Kats are eaten in the yellow house.
The Norwegian lives next to the blue house.
The Smarties eater owns snails.
The Snickers eater drinks orange juice.
The Ukrainian drinks tea.
The Japanese eats Milky Ways.
Kit Kats are eaten in a house next to the house where the horse is kept.
Coffee is drunk in the green house.
Milk is drunk in the middle house.

Given the following, can you prove that the unicorn is mythical? How about magical? Horned?

If the unicorn is mythical, then it is immortal, but if it is not mythical, then it is a mortal mammal. If the unicorn is either immortal or a mammal, then it is horned. The unicorn is magical if it is horned.

The formula writes:

• \(\neg mythical \vee immortal\)
• \(mythical \vee mammal\)
• \(\neg (immortal \vee mammal) \vee horned\)
• \(\neg horned \vee magical\)

We have the enumerated truth table:

Based on these, we can derive:

• We cannot prove unicorn is mythical.
• We can prove it is magical.
• We can prove it is horned.

7.18 Consider the following sentence: \(((Food \Rightarrow Party) \vee (Drinks \Rightarrow Party)) \Rightarrow ((food \wedge drinks) \Rightarrow Party)\)

1. Determine, use enumeration, whether the sentence is valid, satisfiable (but neg valid), or unsatisfiable.
2. Convert the left-hand and right-hand sides of the main implication into CNF, Showing each step, and explain how the results confirm your answer to (a)
3. Prove your answer to (a) using resolution.

It is Valid. The enumeration:

left-hand CNF:

((F ⇒ P) ∨ (D ⇒ P)

♠ (¬ F ∨ P) ∨ (¬ D ∨ P)

♠ (¬ F ∨ P ∨ ¬ D ∨ P)

♠ (¬ F ∨ ¬ D ∨ P)

right-hand CNF:

(F ∧ D) ⇒ P

♠ ¬ (F ∧ D) ∨ P

♠ (¬ F ∨ ¬ D) ∨ P

♠ ¬ F ∨ ¬ D ∨ P

As we can see, they are exactly the same. Thus the production is valid.

We can prove it by proving the negation is unsatisfiable.

\(\neg ((F \Rightarrow P) \vee (D \Rightarrow P) \Rightarrow ((F \vee D) \Rightarrow P))\)

♠ ¬ (((F ⇒ P) ∨ (D ⇒ P)) ⇒ ((F ∧ D) ⇒ P))

♠ ¬ ( ¬ ((F ⇒ P) ∨ (D ⇒ P)) ∨ ((F ∧ D) ⇒ P))

♠ ((F ⇒ P) ∨ (D ⇒ P)) ∧ (¬ ((F ∧ D) ⇒ P))

♠ ((¬ F ∨ P) ∨ (¬ D ∨ P)) ∧ (¬ (¬ (F ∧ D) ∨ P))

♠ (¬ F ∨ ¬ D ∨ P) ∧ (F ∧ D) ∧ ¬ P

♠ (¬ F ∨ ¬ D ∨ P) ∧ F ∧ D ∧ ¬ P

This resolves to empty clause, thus the original sentence is valid.

There're two players, Min and Max, each takes turn to execute. Max moves first.

The problem of minimax algorithm is its node grow exponential. This algorithm is used to prune the subtree that does not affect the result.

This is similar for MiniMax algorithm

• α is the value of the best choise so far, for max, init from -∞
• β is the best value for min, init from +∞

There're two procedures:

Alpha-Beta-Search(state)

returns an action. state is the current state.

Max-Value(state, \alpha, \beta)

returns a utility value

Min-Value(state, \alpha, \beta)

returns a utility value

Alpha-Beta-Search(state) {
  v = Max-Value(state, -999, +999);
  return action in ACTIONS with value v;
}

Max-Value(state, alpha, beta) {
  v = INT_MIN;
  for each a in ACTIONS(state) do
    v = Max(v, Min-Value(result(s,a), alpha, beta));
    if v >= beta then return v;
    alpha = MAX(alpha,v);
  return v;
}

• it uses general purpose heuristic rather than problem-specific ones.

• continuous or discrete domain
• finite or infinite domain
• linear or non-linear constraint
• unary or binary or high order constraint

Entailment: β \models α, reads: the sentence β entails the sentence α if and only if α is true in all worlds where β is true.

a.k.a. boolean logic.

logical equivalence;

• A sentence is valid if it is true in all models. Deduction theorem: KB \models α iff KB ⇒ α is valid
• A sentence is satisfiable if it is true in some models. KB \models α iff KB ∧ ¬ α is unsatisfiable.

Proof method:

• inference rules: transform the sentences to a normal form
• model checking: truth table

A clause is a disjunction of literals. Factoring: the result clause keeps only one copy of each literal.

Conjunction: ∧ Disjunction: ∨ CNF: conjunctive normal form. Conjunction of (disjunctions of literals).

Resolution algorithm: proof by contradiction. I.e. to show KB \models α, we show KB ∧ ¬ α is unsatisfiable. The naming resolution is because, the pair of complementary literals is resolved.

Definite clause

disjunction of literals with exactly one positive literal.

∧ is the natural connective with ∃. Using ⇒ as the main connective with ∃ often causes errors:

∃ x At(x,ISU) ⇒ Smart(x)

is true if there's anyone who is not at ISU, which may not be what you want.

Properties:

For each pair of atomic sentences, give the most general unifier if it exists:

1. P(A,B,B), P(x,y,z)
2. Q(y,G(A,B)),Q(G(x,x),y)
3. Older(Father(y),y),Older(Father(x),John)
4. Knows(Father(y),y), Knows(x,x)

9.20 Let L be the first-order language with a single predicate S(p, q), meaning “p shaves q.” Assume a domain of people.

1. Consider the sentence “There exists a person P who shaves every one who does not shave themselves, and only people that do not shave themselves.” Express this in L.
2. Convert the sentence in (a) to clausal form.
3. Construct a resolution proof to show that the clauses in (b) are inherently inconsistent. (Note: you do not need any additional axioms.)