ASSIGNMENT 2 SOLUTION

Q. 1

    a) Are there any pairs of cities (A,B) for which the algorithm finds a different path from B to A than from A to B? Are there any pairs of cities (A,B) for which the algorithm expands a different total number of nodes from B to A than from A to B?

Ans: There is no such pair of cities (A,B) for which the A* algorithm finds a different path from A to B than from B to A.

But, Yes, there are few pairs of cities (A,B) for which A* expands a different total number of nodes from A to B than from B to A.

For: A = El Paso and B = Tallahassee

A->B:
Nodes expanded = {austin, batonRouge, beaumont, elPaso, houston, lafayette, newOrleans, pensacola, sanAntonio, tallahassee}

Number of nodes expanded = 10

Nodes in solution path = {elPaso, sanAntonio, austin, houston, beaumont, lafayette, batonRouge, newOrleans, pensacola, tallahassee}

Number of nodes in solution path = 10

Total distance from A to B in the solution path = 1554

B->A:
Nodes expanded = {albanyGA, austin, batonRouge, beaumont, dallas, elPaso, houston, lafayette, lakeCity, mexia, newOrleans, pensacola, sanAntonio, tallahassee}

Number of nodes expanded = 14

Nodes in solution path = {elPaso, sanAntonio, austin, houston, beaumont, lafayette, batonRouge, newOrleans, pensacola, tallahassee}

Number of nodes in solution path = 10

Total distance from B to A in the solution path = 1554

    b) Greedy search

c)

    1) Find at least one path that is longer using greedy search than that found using A*, or to satisfy yourself that there are no such paths.

For: A = AlbanyNY and B = Vancouver

Greedy:
Nodes  expanded  =  {albanyNY,  albuquerque,  buffalo,  cincinnati,  cleveland, coloradoSprings,  columbus,  dayton,  denver,  elPaso,  eugene,  grandJunction, indianapolis, kansasCity, lincoln, losAngeles, medford, oakland, omaha, phoenix,
pointReyes, portland, provo, redding, reno, rochester, sacramento, salem, salinas, sanDiego, sanFrancisco, sanJose, sanLuisObispo, santaFe, seattle, stLouis, tucson, vancouver, wichita, yuma}

Number of nodes expanded = 40

Nodes in solution path: {albanyNY, rochester, buffalo, cleveland, columbus, dayton, cincinnati, indianapolis, stLouis, kansasCity, wichita, denver, coloradoSprings, santaFe, albuquerque, elPaso, tucson, phoenix, yuma, sanDiego, losAngeles, sanLuisObispo, salinas, sanJose, oakland, sanFrancisco, sacramento, pointReyes, redding, medford, eugene, salem, portland, seattle, Vancouver}

Number of nodes in solution path = 35

Path length from albanyNY to vancouver: 5162

A*:
Nodes expanded = {albanyNY, boston, buffalo, calgary, cincinnati, cleveland, columbus, dayton, indianapolis, kansasCity, montreal, newHaven, ottawa, pittsburgh, providence, rochester, saultSteMarie, stLouis, stamford, thunderBay, toronto, vancouver, wichita, winnipeg}

Number of nodes expanded = 24

Nodes in solution Path: {albanyNY, rochester, buffalo, toronto, saultSteMarie, thunderBay, winnipeg, calgary, vancouver}

Number of nodes expanded in solution path = 9

Total distance from albanyNY to vancouver = 3069

As compared to A* for the same pair of cities, A* finds the path of cost 3069 whereas greedy finds the path of 5162.

    2) Find at least one path that is found by expanding more nodes than the comparable path using A*, or satisfy yourself that there are no such paths.

For: A = Vancouver and B = Sacramento

Greedy:
Nodes expanded = {boise, eugene, medford, pointReyes, portland, redding, sacramento, salem, seattle, vancouver}

Number of nodes expanded = 10

Nodes in solution Path: {vancouver, seattle, portland, salem, eugene, medford, redding, pointReyes, sacramento}

Number of nodes expanded in solution path = 9

Total distance from vancouver to sacramento = 1044

A*:
Nodes expanded = {eugene, medford, pointReyes, portland, redding, sacramento, salem, seattle, vancouver}

Number of nodes expanded = 9
Nodes in solution Path: {vancouver, seattle, portland, salem, eugene, medford, redding, pointReyes, sacramento}

Number of nodes expanded in solution path = 9

Total distance from vancouver to sacramento = 1044

For the same pair of citites, A* expands 9 nodes, whereas greedy expands 10 nodes.

d) Uniform cost search

e)

    1) Find at least one path that is longer using uniform cost than that found using A*, or to satisfy yourself that there are no such paths.

Ans: There are no such paths as Uniform Cost Search finds the shortest possible path between the pair of cities, so does the A*. Their path length is same but the number of expanded nodes might be different.

    2) Find at least one path that is found by expanding more nodes than the comparable path using A*, or satisfy yourself that there are no such paths.

For: A = Vancouver and B = Sacramento

Uniform Cost Search:

Nodes expanded = {boise, calgary, eugene, medford, pointReyes, portland, redding, sacramento, salem, seattle, vancouver}

Number of nodes expanded = 11

Nodes in solution Path: {vancouver, seattle, portland, salem, eugene, medford, redding, pointReyes, sacramento}

Number of nodes expanded in solution path = 9

Total distance from vancouver to sacramento = 1044

A*:

Nodes expanded = {eugene, medford, pointReyes, portland, redding, sacramento, salem, seattle, vancouver}

Number of nodes expanded = 9

Nodes in solution Path: {vancouver, seattle, portland, salem, eugene, medford, redding, pointReyes, sacramento}

Number of nodes expanded in solution path = 9

Total distance from vancouver to sacramento = 1044

For the same pair of citites, A* expands 9 nodes, whereas Uniform cost search expands 11 nodes.

Q. 2

    1. Construct the game-tree, assuming that A starts the game and the initial state is OOOOO, meaning that none of the coins are picked up yet.

Ans: In the figure below, circle represents the move made by A and square represents the move made by B. We have to maximize A’s chances of winning. Thus, circles will be maximizing nodes and squares will be minimizing nodes. The values on the edges represent how many coins are picked up in the move.





























    2. Suppose a static evaluation function scores a win for A as +1 and a loss for A as -1. At each level of your game tree, indicate the value for each node and the best next move for A. Ans: The static evaluation function is computed for all nodes in the tree. The best move for A is to pick up 1 coin at first (value of root is +1, which comes from its left child) The best move is shown in red in the above game tree.

    3. If both players play optimally, which player will win the game? Why?

Ans: If this is the case, then A will win. Suppose, A picks up a coin first. B has to pick either one or two coins from remaining four coins. B will have two choices:

        a) If B picks one coin, then A will have three coins remaining. Then, A will choose two coins (optimal choice instead of picking one coin again) and B has to choose the last coin. This results in A winning the game.

        b) If B picks two coins, then A will have two coins remaining. Then, A will choose one
coin leaving B with the last coin. In this case also A wins the game.

Thus, no matter what B chooses, if A choose only one coin in the first move, then A wins the game, provided both players play optimally.

Q. 3





Propositional symbols:



s - The cat is meowing
a - The cat wants attention
w - The cat wants dinner
i - It is 5pm


p - The cat will play.


Representation of sentences in Propositional Logic:


The cat will play if and only if it wants attention
:
p ⇔ a
If it is 5pm, the cat wants dinner
:
i ⇒ w
If the cat is meowing, it wants either dinner or attention
:
s ⇒ (w ∨ a)
If the cat is not meowing, then it is not 5pm
:
¬s ⇒ ¬i
The cat is meowing


:
s
Conversion into Conjunctive Normal Form (CNF):


p ⇔ a
:
(¬p ∨ a) ∧ (¬a ∨ p)


i ⇒ w
:
¬i ∨ w



s ⇒ (w ∨ a)  :
¬s ∨ w ∨ a


¬s ⇒ ¬i
:
s ∨ ¬i



s
:
s




Resolution:
    1. ¬p ∨ a
    2. ¬a ∨ p
    3. ¬i ∨ w
    4. ¬s ∨ w ∨ a
    5. s ∨ ¬i
    6. s

--------------------
7.
w ∨ a
By resolution of 6 and 4
8.
w ∨ p
By resolution of 7 and 2
9.
w ∨ a
By resolution of 8 and 1

(This is not going to terminate)

The theory is internally consistent, i.e., it can’t be derived false.

If (s,a,w,i,p) are assigned the truth values (t,f,t,t,f), then all the expressions come out to be true. Thus, the given set is logically consistent.
Q. 4

Predicates:

p(X) - X is a panda carn(X) - X is a carnivore

herb (X) - X is an herbivore

plant(X) - X eats plant

First Order Predicate Logic:

All pandas are herbivores
∀X (p(X) ⇒ herb(X))

No carnivores eat plants
∀X (carn(X) ⇒ ¬plant(X))

Herbivores all eat plants
∀X (herb(X) ⇒ plant(X))
Q. 5

Predicates:

cat(X) - X is a cat    mammal(X) - X is a mammal    headOf(H,X) - H is the head of X


    1. Conversion into First Order Predicate Logic:

All cats are mammals
Ans: ∀X (cat(X) ⇒ mammal(X))

The head of any cat is the head of a mammal
Ans: ∀X,H ∃Y ((cat(X) ∧ headOf(H,X)) ⇒ (mammal(Y) ∧ headOf(H,Y)))

    2. Conversion into CNF:
∀X (cat(X) ⇒ mammal(X))
CNF: ¬cat(X) ∨ mammal(X)
∀X,H ∃Y ((cat(X) ∧ headOf(H,X)) ⇒ (mammal(Y) ∧ headOf(H,Y)))
CNF:    ¬cat(X) ∨ ¬headOf(H,X) ∨ mammal(f(X,H)) ∧
¬cat(X) ∨ ¬headOf(H,X) ∨ headOf(H,f(X,H))
Q. 6


Predicates:


h(X) – X is a horse

p(X) – X is a prey animal
f(X) – X runs fast

m(X) – X eats meat
CNF:


All horses are prey animals -
¬h(X) ∨ p(X)
Prey animals all run fast
-
¬p(X) ∨ f(X)
No meat eaters run fast
-
¬m(X) ∨ ¬f(X)
Conclusion:


No horses are meat eaters
-
h(a) ∧ m(a)  (negated)

Resolution:
    1. ¬h(X) ∨ p(X)

    2. ¬p(X) ∨ f(X)
    3. ¬m(X) ∨ ¬f(X)

    4. h(a)
    5. m(a)
--------------------------
6.
¬f(a)
By resolution of 5 and 3
{a/X}
7.
¬p(a)
By resolution of 6 and 2
{a/X}
8.
¬h(a)
By resolution of 7 and 1
{a/X}
9.
□
By resolution of 8 and 4
{ }

It is proved that the contradiction of the conclusion is an empty clause (false) and the conclusion is, thus, true.