Note: Be Brief. Do Not Provide Long Explanations

Name:

Note: Be brief. Do not provide long explanations.

Also, please write down your name on every page.

1.  (10 points) Name and explain (briefly) the 4 components of a learning agent.

A learning agent is divided in 4 components:

a.  Performance Element (selects actions)

b.  Learning Element (makes improvements)

c.  Critic (how well the agent is doing)

d.  Problem Generator (suggest new experiences)

2.  (10 points) For each of the following search techniques, answer the question attached to it. Use b as the branching factor, m as the maximum length of any path in the search tree, and d as the length of the optimal path.

a. Uniform Cost Search. State if it is optimal and complete and under what conditions. Can it get stuck in an infinite loop? why?

It is complete if b and d are finite; it is optimal if path cost increases with depth. Uniform cost search can get stuck in an infinite loop if there is a path with an infinite sequence of zero-cost actions.

b. Iterative Deepening. It is usually used in combination with what other method? State if it is optimal and complete and under what conditions.

It is used in combination with depth-first search. It is complete if b and d are finite; it is optimal if path cost increases with depth.

c. A*. State if it is optimal and complete and under what conditions.

It is complete and optimal if the heuristic is admissible and consistent.

d. Bi-directional search. What is the time complexity? State if it is optimal and complete. Name at least one disadvantage of this method.

Time complexity is bd/2 + bd/2 . It is complete and suboptimal. Space requirement is the most significant disadvantage of this method. Knowing how to search backwards is another limitation.

3.  (10 points) You have been asked to design a genetic algorithm to solve a particular search problem. After using the algorithm you noticed a problem known as “crowding” where one individual is much more fit than others. The population then begins to concentrate around this individual and variations of it. Population diversity is then reduced. Someone suggests to you to change the probability function. Instead of using the fitness of individuals you could use their ranking. That is, the ranking of the best individual R(h) = 1, the ranking of the second best individual is R(h) = 2 and so on. Re-define the probability to select an individual using Rank(hi) instead of the fitness function Fitness(hi). The only requirement in your definition is that each probability be such that

0 <= P(hi) <= 1.

There are different solutions. One is as follows:

P(hi) = MaxRank - Rank(hi) / MaxRank

where MaxRank is the size of the population.

4.  (10 points) Under propositional logic, assume you have 4 propositions named A, B, C, and D (all Boolean). Observe that V is disjunction or OR, & is conjunction or AND, and ~ is negation or NOT. Answer the following.

a.  What is the total number of models defined in this language?

16. This the total combinations of truth values.

b.  Is the statement A V B valid? why?

No, the statement is not true for all models (truth value assignments).

c.  Is the statement A V ~A valid? why?

Yes, the statement is always true, no matter what model we choose.

d.  How many models are true under the statement B D ?

4.

e.  Are the following two statements equivalent? explain why.

statement 1: ~(A V B)

statement 2: ~A & ~B

Yes, because they are true in the same set of models.

f.  Is the following statement satisfiable? why?

Statement: A V B V C V D

Yes, because it is true in at least one model.

5.  (10 points) Apply resolution and unification to the following sentences and prove if the statement galaxy(Andromeda) is true. Observe that the existential quantifier is represented with the symbol Зx (i.e., there exists an x such that).

Knowledge Base of sentences:

Sentence 1: Зx star(X) & red(X)

Sentence 2: neighbor_galaxies())

Sentence 3: neighbor_galaxies(MilkyWay,Andromeda)

Sentence 4: galaxy(NGC56) V galaxy(Andromeda) V ~bright(Millennium)

Sentence 5: galaxy(NGC56) V galaxy(Andromeda) V ~bright(NGC56)

Sentence 6: star(Sun)

Sentence 7: star(AlphaCentauri)

Sentence 8: red(NGC456)

Sentence 9: red(NGC78)

Sentence 10: neighbor_galaxies(X,Neighbor(X)) V bright(X)

Sentence 11: ~galaxy(NGC56)

Sentence 12: ~neighbor_galaxies(Millennium,Neighbor(Millennium))

The order can vary, but in essence you can do the following:

Sentence 4 and 10 can be unified if X/Millennium

That gives: galaxy(NGC56) V galaxy(Andromeda) V neighbor_galaxies(Millennium,Neighbor(Millennium))

this can be resolved with sentence 12 to produce:

galaxy(NGC56) V galaxy(Andromeda),

which can be resolved with sentence 11 and the added statement ~galaxy(Andromeda) to give the null statement.

6.  (10 points) Write a PROLOG program that does the following . When 2 cities are

neighbors (are found within a certain radius) we can claim the statement: neighbors(A,B). Other forms to claim if two cities are neighbors are given by clauses below. Assume the following PROLOG program:

neighbors(Dallas, Houston)

neighbors(Dallas, San Antonio)

neighbors(Houston, Galveston)

neighbors(Houston, Austin)

neighbors(Arlington, Dallas)

neighbors(Irving, Dallas)

neighbors(SanAntonio, Floresville)

neighbors(SanAntonio, Luling)

neighbors(X,Y) := neighbors(Y,X)

neighbors(X,Y) := neighbors(X,W), !, neighbors(W,Y)

List all possible outputs for the following query in the correct order:

> neighbors(Dallas,Y)

The answer would be in this order:

Houston

San Antonio

Arlington

Irving

Galveston

Austin

7.  (10 points) Write a PROLOG program that does the following. The program should compare two lists L1 and L2 and determine if the first list L1 is a subset of the second list L2. Call the main predicate: subset(List1, List2). Note 1: The empty list is a subset of any other list. Note 2: You can use the predicate member(X,Y) that is true if element X is a member of list Y.

Example:

?- subset([],[4,5,6,2])

yes

?- subset([1,2],[a,1,e,2])

yes

?- subset([1,2],[a,b,e,2])

no

Answer:

subset([],_).

subset([H|T],S) :- member(H,S), subset(T,S).

8.  (10 points) Write a PROLOG program to count the elements in a list (a list within the list counts as one element). Call the main predicate: count_elements(List,X), where X contains the number of elements in List. Hint: you can state things like

X = A (where A is an algebraic expression).

Example:

?- count_elements([2,8,9,1],X)

X = 4.

?- count_elements([a,b,[3,s],d,[3,y,g]],X)

X = 5.

count_elements([H|T],N) :- count_elements(T,N1), N = N1+1.

count_elements([],0).

9.  (5 points) Answer the following questions:

a. How is partial-order planning different from classical planning? What components in partial-order planning are different from classical planning?

In partial-order planning we are able to explore paths simultaneously; all paths are then combined to form a complete plan. The new components in partial-order planning are as follows:

·  Ordering Constraints A < B

·  Causal Links A à B (A achieves p for B)

b. What is a consistent plan?

A consistent plan is one in which there are no cycles in the ordering constraints and no conflicts with casual links.

10.  (5 points) Explain briefly how is multi-agent planning done.

It can be cooperative or competitive:

a.  Cooperative where there is a joint plan and a goal is achieved when each agent performs its assigned actions.

b.  Competitive when agents compete to see who is able to reach the goal.

11.  (10 points) Assume the following Bayesian Belief Network:

a. Assume the two variables Train Hard (TH) and Set Clear Goals (SCG) form a noisy-or relation with the inhibition probabilities defined below. Generate the remaining conditional probabilities (you need to provide two additional probabilities). Note. Well Trained Physically is represented as WTP.

Inhibition Probabilities:

P(~WTP | TH, ~SCG ) = 0.5

P(~WTP | ~TH, SCG ) = 0.5

P(~WTP | ~TH, ~SCG ) = 1.0

P(~WTP | TH, SCG ) = 0.5 x 0.5 = 0.25

b. Assume Hire Coach (HC) is Boolean but Read Sports (RS) can take three values (low, medium, high). What is the size of the conditional probability table stored on Well Trained Mentally WTM?

6.

c. Assume Well Trained Mentally (WTM) is Boolean. Using the result of the previous question (b), assume also that the probability P(WTM | ? ) where ? is a combination of values for Hire Coach and Read Sports follows a uniform distribution (that is all prob. have equal value. For example if there are 10 combinations, then each prob. equals 1/10). Assume also that the prior probabilities equal 0.5 (i.e., P(HC), and P(RS) = 0.5). What is the joint probability of Well Trained Mentally being true, Hire Coach being true, and Read Sports having a value of low? (show only the prob. involved without doing the actual computation).

P(WTM, HC, RS = low) = P(WTM | HC, RS = low ) x P( HC) x P( RS = low)

P(WTM, HC, RS = low) = 1/6 x 0.5 x 0.5.

Total = 100 points.