exemplu subiect examen si sisteme inteligente05-iia-res.18.02.16

8/20/2019 Exemplu Subiect Examen SI Sisteme Inteligente05-Iia-res.18.02.16

1/15

18 February 2016/R2 Name: Group: Pages:

Exam in Introduction to Artificial Intelligence

• Time: 3 hours. This exam is worth 90 points. Each point represents two minutes of time. Use thepoint totals as a guide for budgeting your time. Use all your 180 minutes.

• Read exercises carefully. Be sure you understand exactly what is required. To assure fairness among

you, questions are not allowed.

• Write each exercise on a separate paper! At the end of the exam, order the exercises.• The exam is closed-book, closed-notes, closed-phones, closed-friends, open-mind. Write clearly; un-

readable = wrong! If we observe any attempt of deception, the whole exam will be evaluated to0.

Exercise 1 Exercise 2 Exercise 3 Exercise 4 SumAvailable Points 25 20 20 25 90Achieved Points

1. Search. Consider the route-finding problem of computing the cheapest path from Buffalo to Utica.For the straight-line distance heuristic, draw the search tree after expansion of each node until the

termination of the algorithm for: (Trasati urmatorii algoritmi cu starea initiala Buffalo si finala Utica.)

(a) (Uniform cost search (label all nodes with their g values). What is the solution found by thealgorithm? Assume no cycles. (Afisati arborele, valoarea g pentru fiecare nod si solutia pentrualgoritmul de cautare cu cost uniform).

Solution: Step 0:

Buffalo (g=0)

Step 1:

Buffalo

Batavia (g=20) Lockport (g=15) Olean (g=30)

Step 2:


2/15

Buffalo

Batavia (g=20) Lockport Olean (g=30)

Step 3:Buffalo

Batavia

Rochester (g=50) Syracuse (g=35) Ithaca (g=60)

Lockport Olean (g=30)

Step 4:

Buffalo

Batavia

Rochester (g=50) Syracuse (g=35) Ithaca (g=60)


Binghamton (g=90)

Step 5:

Buffalo

Batavia

Rochester (g=50) Syracuse

Ithaca (g=40) Utica (g=100)

Ithaca (g=60)


Binghamton (g=90)

The algorithm stops when the goal is reached.

Solution: Buffalo, Batavia, Syracuse, Utica.

(b) (Assume that the uniform cost algorithm found a path with g=100 and the frontier contains the

nodes Rochester (g=50), Ithaca (g=40), Binghamton (g=90). Does the algorithm continue, hopingto identify a better path? (Presupunand ca este gasita o cale cu g=100 iar frontiera contine nodurileRochester (g=50), Ithaca (g=40), Binghamton (g=90), algoritmul se va opri sau va continua insperanta gasirii unui drum mai bun?)

Solution: It stops because uniform cost search is optimal.

No better path will be found, as the following expansion illustrates:


3/15

Step 6:

Buffalo

Batavia

Rochester (g=50) Syracuse

Ithaca (g=40)

Binghamton (g=70)

Utica (g=100)

Ithaca (g=60)


Binghamton (g=90)

Step 7:

Buffalo

Batavia

Rochester (g=50)

Oswego(g=100)

Syracuse

Ithaca(g=40)

Binghamton (g=70)

Utica(g=100)

Ithaca (g=60)


Binghamton (g=90)

Step 8:


4/15

Buffalo

Batavia

Rochester

Oswego(g=100)

Syracuse

Ithaca

Binghamton (g=70)

Utica(g=100)

Ithaca

Syracuse(g=95)

Binghamton (g=90)

Lockport Olean

Binghamton (g=90)

Step 9:

Buffalo

Batavia

Rochester

Oswego(g=100)

Syracuse

Ithaca

Binghamton

Olean

(g=130)

Oneonta

(g=110)

Utica(g=100)

Ithaca

Syracuse(g=95)

Binghamton(g=90)

Lockport Olean

Binghamton (g=90)

Step 10:


5/15

Buffalo

Batavia

Rochester

Oswego(g=100)

Syracuse

Ithaca

Binghamton

Olean(g=130)

Oneonta(g=110)

Utica(g=100)

Ithaca

Syracuse(g=95)

Binghamton(g=90)

Olean(g=150)

Oneonta(g=130)

Lockport Olean

Binghamton (g=90)

Step 11:

Buffalo

Batavia

Rochester

Oswego(g=100)

Syracuse

Ithaca

Binghamton

Olean(g=130)

Oneonta(g=110)

Utica(g=100)

Ithaca

Syracuse(g=95)

Binghamton

Olean(g=150)

Oneonta(g=130)

Lockport Olean

Binghamton

Ithaca(g=120)

Oneonta(g=130)

Step 12:


6/15

Buffalo

Batavia

Rochester

Oswego(g=100)

Syracuse

Ithaca

Binghamton

Olean(g=130)

Oneonta(g=110)

Utica(g=100)

Ithaca

Syracuse

Utica(g=160)

Binghamton

Olean(g=150)

Oneonta(g=130)

Lockport Olean

Binghamton

Ithaca(g=120)

Oneonta(g=130)

(c) (Greedy best-first search (label all nodes with their h values). What is the solution found by thealgorithm? (Afisati arborele, valoarea h pentru fiecare nod si solutia pentru algoritmul de cautaregreedy best first).

Solution: Step 0:

Buffalo (h=85)

Step 1:

Buffalo

Batavia (h=75) Lockport (h=90) Olean (h=100)

Step 2:

Buffalo

Batavia

Rochester (h=55) Syracuse (h=65) Ithaca (h=90)

Lockport (h=90) Olean (h=100)

Step 3:


7/15

Buffalo

Batavia

Rochester

Oswego (h=30)

Syracuse (h=65) Ithaca (h=90)


Step 4:

Buffalo

Batavia

Rochester

Oswego

Utica

Syracuse (h=65) Ithaca (h=90)


Solution: Buffalo, Batavia, Rochester, Oswego, Utica

(d) (A* search (label all nodes with their f values). What is the solution (list of visited cities) foundby the algorithm? (Afisati arborele, valoarea f pentru fiecare nod si solutia pentru algoritmul decautare A*).

Solution:

Buffalo (f=85)

Step 1:

Buffalo

Batavia (f=95) Lockport (f=105) Olean (f=130)Step 2:


8/15

Buffalo

Batavia

Rochester (f=105) Syracuse (f=100) Ithaca (f=150)

Lockport (f=105) Olean (f=130)

Step 3:

Buffalo

Batavia

Rochester (f=105) Syracuse

Ithaca (f=160) Utica (f=100)

Ithaca (f=150)

Lockport (f=105) Olean (f=130)

Solution: Buffalo, Batavia, Syracuse, Utica.

(e) (If f (s), g(s) and h(s) are all admissible heuristics then which of the following are also guaranteedto be admissible heuristics: (Daca f (s), g (s) si h(s) sunt euristici admisibile, care din urmatoareleeuristici sunt de asemenea admisibile?)

f (s) + g(s) + h(s)√ f (s)/6 + g(s)/3 + h(s)/2

√ min(f (s), g(s), h(s))√ max(f (s), g(s), h(s))

√ f (s)/3 + g(s)/3 + h(s)/3

f (s)

∗g(s)

∗h(s)

√ min(f (s), g(s) + h(s)) max(f (s), g(s) + h(s))

Solution: Taken from MIT FINAL 2014.

"In order to guarantee that a function of admissible heuristics is still admissible, the expressionmust be less than or equal to the max of the heuristics. Sums and products do not satisfy these,so bubbles 1, 6, and 8 all immediately fail. Bubbles 3, 4, and 7 all work because the max of admissible heuristics is still admissible, as is the min of an admissible heuristic and anythingelse. Bubble 5 is the average of the heuristics, so it must be less than the max, and is thusadmissible. Lastly, bubble 2 is a weighted average, and is thus also less than the max, and isthus admissible."

2. Satisfiability. Our department offers the following forth year classes: JAVA, CPP, ARC, HAR, KBS.The chief of department decided that: i) there should be at least one programming class, ii) at least oneclass on computer architecture, iii) at least one class on artificial intelligence, and iv) there should beno more than one class on each topic. In addition, CPP and ARC are designed to be given together,so it does not make sense to include one without the other. JAVA and CPP are programming classes,ARC and HAR are on computer architecture, and KBS is on artificial intelligence. (Oferta de cursuri


9/15

pentru anul 4 include JAVA, CPP, ARC, HAR, KBS. Constrangerile pe orar sunt: i) cel putin un cursde programare, ii) cel putin un curs de IA, iii) nu mai mult de un curs din acelasi domeniu. CPP siARC trebuie predate impreuna. JAVA si CPP sunt cursuri de programare, ARC si HAR de arhitecturacalculatoarelor, iar KBS de IA.)

(a) (Encode the above search problem in propositional logic. Use the first letter of the class. (Translatatiin logica propozitionala. Utilizati ca notatie prima litera din numele cursului).

Solution: The constraint that there should be at least one class in each topic is expressed as

(J ∨ C ) ∧ (H ∨ A) ∧ K The constraint that no more than one class from each area is included is formalised as

¬(J ∧ C ) ∧ ¬(H ∨ A)The constraint that CPP and ARC should be given together is expressed as

C ≡ A

(b) (Convert to CNF. (Convertiti in CNF).

Solution:

The first sentence is in CNF.

Applying de Morgan rule on the second constraint we get:

(¬J ∨ ¬C ) ∧ (¬H ∨ ¬A)

C ≡ A is the same with (C → A) ∧ (A → C ) which becomes

(¬C ∨ A) ∧ (¬A ∨ C )

(c) (1Chief of department suggested to apply the Davis Putnam SAT solving algorithm. Help the chief of department to take a consistent decision, by tracing the algorithm. For each recursive call, statepure symbols and unit clauses. State the solution returned. Which are the classes that shouldappear in the fourth year? Assume the order of symbols: J,C,H,A,K . (Trasati algoritmul Davis-Putnam. Pentru fiecare apel recursiv, indicati literalii puri si clauzele unitate. Aratati solutia sinumele cursurilor care vor figura in orar. Ordinea simbolurilor este J,C,H,A,K .)

Solution: The clauses are:

J ∨ C H ∨ AK

¬J ∨ ¬

C ¬H ∨ ¬A¬C ∨ A¬A ∨ C

First call: There are no pure symbols. There is a unit clause, hence K = 1.The current model: K = 1


10/15

The resulted clauses are:

J ∨ C H ∨ A¬J ∨ ¬C ¬H ∨ ¬A¬C ∨ A¬A ∨ C

Second recursive call: there are no pure symbols and no unit clauses. We call the algorithmwith the first variable in the specifeid order, that is J .

The current model: K = 1, J = 1.

The resulted clauses are: H ∨ A¬C ¬H ∨ ¬A¬C ∨ A¬A ∨ C

Third recursive call: there are no pure symbols. There is a unit clause ¬C . Hence we assignfalse to C .The current model becomes: K = 1, J = 1, C = 0.

The resulted clauses are: H ∨ A¬H ∨ ¬A¬A

Forth recursive call: there are no pure symbols. There is a unit clause ¬A. Hence we assignfalse to A.The current model becomes: K = 1, J = 1, C = 0, A = 0.

The resulted clauses are:H

Fifth recursive call: we assign true to H and call the algorithm with the empty list of clausesand symbols.

The model is: K = 1, J = 1, C = 0, A = 0, H = 1.

The classes are: KBS, JAVA and HAR.

3. Searching with observations. Consider an agent which is trying to escape from a labyrinth with 8rooms: room1 to room8. The agent cannot see where it is, but it can feel the walls. Its percepts aresubsets of {WN, WW, WE, WS, Ex} which stand for ’Wall to the North’, ’Wall to the West’, ’Wall to

the East’, ’Wall to the South’, and ’Exit’. The actions available to the agent are moving North, West,East and South. The actions of moving North and South are deterministic and move the agent one roomto the North or one room to the South if there exists such a room, otherwise leave the agent where itis. The actions of moving West and East are non-deterministic: they move the agent to some room tothe West or to the East, not necessarily to the next one. (Agentul doreste sa iasa din labirintul dinfigura. Perceptele sale sunt submultimi ale multimii {WN, WW, WE, WS, Ex}, unde elementele suntprescurtari pentru perete la nord, vest, est, sud, respectiv iesire. Actiunile posibile sunt deplasarea la


11/15

nord, vest, est, sud. Deplasarile la nord si sud sunt deterministe, agentul ajungand cu o casuta maila nord, respectiv sud daca labirintul permite. Daca nu, agentul ramane pe pozitia curenta. ActiunileWest si East sunt nedeterministe: agentul se deplaseaza la vest, respectiv est, dar nu neaparat in casuta vecina.)

North

room6room5 room7 room8

room1 room2 room3 room4

South

West East

(a) (Formalise the percepts for each state Percepts(roomi), and the Results(roomi, action). Youcan use index i for compact representation of similar pairs of states and actions. For instancePercept(room1) = {W N , W W } and Results(roomi,North) = {roomi} for i ∈ {1, 2, 3, 4}. (For-malizati perceptele pentru fiecare stare Percepts(roomi) si Results(roomi, action).)

Solution:

Percept(room1) = {W N , W W }Percept(room2) = {W N }Percept(room3) = {W N }Percept(room4) = {W N , W E }Percept(room5) = {W S , W W }Percept(room6) = {W S }Percept(room7) = {W S }Percept(room8) = {WS,WE ,E x}

Results(roomi,North) = {roomi} for i ∈ {1, 2, 3, 4}Results(roomi,North) = {roomi−4} for i ∈ {5, 6, 7, 8}Results(roomi,South) = {roomi+4} for i ∈ {1, 2, 3, 4}Results(roomi,South) = {roomi} for i ∈ {5, 6, 7, 8}Results(roomi,West) = {roomi} for i ∈ {1, 5}Results(roomi,West) = {roomi−1} for i ∈ {2, 6}Results(roomi,West) = {roomi−1,roomi−2} for i ∈ {3, 7}Results(roomi,West) = {roomi−1,roomi−2,roomi−3} for i ∈ {4, 8}Results(roomi,East) = {roomi} for i ∈ {4, 8}Results(roomi,East) = {roomi+1} for i ∈ {3, 7}Results(roomi,East) = {roomi+1,roomi+2} for i ∈ {2, 6}Results(roomi,East) = {roomi+1,roomi+2,roomi+3} for i ∈ {1, 5}

(b) (The agent starts in total ignorance of where it is. Define its initial belief state b0. (Agentul este

initial total ignorant legat de pozitia in care se afla. Definiti starea initiala de credinte.)

Solution: b0 = {room1,room2,room3,room4,room5,room6,room7,room8}

(c) (Define updated belief state b1 = Update(b0, {W N }}. (Definiti starea de credinte actualizate b1 =Update(b0, {W N }}.)


12/15

Solution: b1 = Update(b0, {W N }} = {room2,room3}

(d) (Define Results(b1,East). (Definiti Results(b1,East).)

Solution: b̂1 = Predict(b1,East) =

{room3,room4

}Possible percepts for b̂1 are:φ2 = Percept(room3) = {W N }and

φ3 = Percept(room4) = {W N , W E }Hence

b2 = Update(b̂1, φ2) = {s ∈ b̂1 : φ2 = Percept(s)} = {room3}b3 = Update(b̂1, φ3) = {s ∈ b̂1 : φ3 = Percept(s)} = {room4}Therefore:

Results(b1,East) = {b2, b3} = {{room3}, {room4}}

(e) (Draw two solution subtrees of the AND-OR search tree for this problem, starting in belief state b1

,with the goal to be in room8. (Desenati doua solutii sub forma de subarbori din arborele de cautareAND-OR pentru aceasta problema. Starea initiala este b1, iar telul room8.)

Solution: One solution is given the sequence of actions: 1. East 2. East or South 3. South

b1[r2, r3]

∧

b2

[r3]

∧

b3[r4]

∧

b4[r8]

South

b3

[r4]

∧

b4[r8]

The second solution could be: going South first and then East.

4. Partial Order Planning.


13/15

(a) (1Explain how partial order planning works in English and pseudocode. Don’t forget to explainissues such as: open condition, clobberer, operators on partial plans. (Explicati cum functioneazaplanificarea cu ordonare partiala in limbaj natural si pseudocod. Explicati notiunile: conditiedeschisa, suprascriere de literali, operatori pe planuri partiale.)

Solution: Part of these issues were discussed during lecture on Classsical Planning. Part of

them are briefly introduced in section 10.4.4 AIMA, 3rd edition.Partial ordered plans are created by a search through the space of partial plans . Partial plansalways have a Start step which has the initial state description as its effect, and a Finishstep which has the goal description as its precondition. Partial plans have a list of temporalconstraints ai ≺ aj stating that action ai should precede action aj . The algorithm uses alist of causal links from outcome of one step to precondition of another. It gradually movesfrom incomplete/vague plans to complete, correct plans and backtracks if an open condition isunachievable or if a conflict (flaw) is unresolvable. At every step, the algorithm make the least commitment possible to fix the flaw.

An open condition is a precondition of a step not yet causally linked.

A plan is complete if every precondition is achieved.

A precondition is achieved if it is the effect of an earlier step and no possibly intervening step

undoes it.A clobberer is a potentially intervening step that destroys the condition achieved by a causallink. It should be either moved before the first step or after the second.

Operators on partial plans are:

• add a link from an existing action to an open condition• add a step to fulfill an open condition• order one step wrt another to remove possible conflicts

Gradually move from incomplete/vague plans to complete, correct plans. Backtrack if an opencondition is unachievable or if a conflict is unresolvable.

(b) (1Solve the following blocks world problem below using partial order planning. Trace the searchfrom the initial empty plan to a complete solution. State the current steps, links, orderings, openconditions, and clobberers at each step. The actions are: (Rezolvati utilizand planificare cu ordonarepartiala. Trasati cautarea de la planul initial gol la solutia completa. Aratati pasii, legaturile,relatiile de ordine, conditiile deschise, suprascrierile de literali.)

Actions Move(b; x; y):Precond: On(b, x) ∧ Clear(b) ∧ Clear(y)Effect: On(b, y) ∧ Clear(x) ∧ ¬On(b, x) ∧ ¬Clear(y)

Movetotable(b; x):Precond: On(b, x) ∧ Clear(b)Effect: On(b,Table) ∧ Clear(x) ∧ ¬On(b, x)

The initial state is: On(B, A) ∧ On(A,Table) ∧ On(C,Table) ∧ Clear(B) ∧ Clear(C ).The goal is: On(C, B) ∧ On(B,Table).Solution: Steps = {Start, F inish} where the effect of Start is: On(B, A) ∧ On(A,Table) ∧On(C,Table) ∧ Clear(B) ∧ Clear(C ),and the Finish step has On(C, B) ∧ On(B,Table) as its precondition.


14/15

Steps = {Start,Finish}Links = {}Orderings = {}Open conditions = On(C, B), On(B,Table) (for the Finish step).

Suppose you choose the first open condition as a selected subgoal. An action which would make

it true is Move(C ; x; B). You add it as a step to the partial plan, and a link from it to Finish:

Steps = {Start, Move(C,x,B),Finishg}Links = {Move(C,x,B) →On(C,B) Finish}Orderings = {Start ≺ Move(C,x,B),Move(C,x,B) ≺ Finish}Open conditions = On(B,Table) (for the Finish step),

On(C, x),Clear(C ),Clear(B) (for the Move(C,x,B) step).

There are no clobberers.

Suppose you choose the first open condition as a selected subgoal. An action which would makeit true is Movetotable(B, y). You add it as a step to the partial plan, and a link from it toFinish:

Steps = {Start, Move(C,x,B), M ovetotable(B, y),Finish}Links = {Move(C,x,B) →On(C,B) Finish,

Movetotable(B, y) →On(B,Table) Finish}Orderings = {Start ≺ Move(C,x,B),Move(C,x,B) ≺ F inish,

Start ≺ Movetotable(B, y), Movetotable(B, y) ≺ Finish}Open conditions = On(C, x),Clear(C ),Clear(B) (for the Move(C,x,B) step),

On(B, y),Clear(B) (for the Movetotable(B, y) step).

There is also clobbering: Move(C,x,B) destroys a precondition for Movetotable(B, y) (Clear(B)).Since you cannot put Movetotable(B, y) after Finish, you put it before Move(C,x,B):

Orderings = {Start ≺ Move(C,x,B),Move(C,x,B) ≺ Finish, Start ≺ Movetotable(B, y),Movetotable(B, y)

≺ F inish, M ovetotable(B, y)

≺ Move(C,x,B)

}Now you can deal with the open conditions by adding a link from Start to all of them: On(C, x)with x = T able,C lear(C ),Clear(B), On(B, y) with y = A is made true by Start.

The resulting complete plan is as follows:

Steps = {Start, Move(C,Table,B), Movetotable(B, A),Finish}Links = {Move(C,Table,B) →On(C,B) Finish,

Movetotable(B, A) →On(B,Table) Finish,Start →On(C,x),Clear(C ),Clear(B) Move(C,Table,B),Start →On(B,y),Clear)B) Movetotable(B, A)}

Orderings = {Start ≺ Move(C,x,B),Move(C,x,B) ≺ F inish,Start ≺ Movetotable(B, y),Movetotable(B, y) ≺ F inish, Movetable(B, y) ≺ Move(C,x,B)}

Open conditions = On(C, x),Clear(C ),Clear(B) (for the Move(C,x,B) step),

On(B, y),Clear(B) (for the Movetotable(B, y) step).

Anonymous Questionaire

Write on an anonymous paper your opinion regarding:

1. What did you like at this course?


15/15

2. Identify what you found easiest and most difficult about this course (or during learning) and why.

3. Identify what you found easiest and most difficult during laboratory work and why.

4. What are the changes that would most improve the course?

5. What would you say to students considering taking the course?

exemplu subiect examen si sisteme inteligente05-iia-res.18.02.16

Documents