1. What Is AI? Explain Any Four Approaches to AI. 16

ARTIFICIAL INTELLIGENCE

November 2008:

SET1:

1. What is AI? Explain any four approaches to AI. [16]

2. Explain various blind search strategies. [16]

3. Explain each of the following with an example:

(a) Constraint graph

(b) Constraint satisfaction problem

(c) Cryptarithmetic puzzle. [4+6+6]

4. Explain Alpha-Beta cutoffs during minimax search. [16]

5. (a) Show that the following sentences are inconsistent using propositional logic

i. If Jack misses many classes through illness, then he fails high school

ii. If Jack fails high school, then he is uneducated

iii. If Jack reads a lot of books, then he is not uneducated

iv. Jack misses many classes through illness and reads a lot of books

(b) Some agents make inferences as soon as they are told a new sentence, while

other wait until they are asked before they do any inferencing. What difference

does this make at the knowledge level, the logical level, and the implementation

level. [10+6]

6. (a) Comment on propositional Vs first-order inference

(b) How can resolution be used to show that a sentence is

i. valid

ii. unsatisfiable

For each of the following pairs of atomic sentences, give the most general uni-

fier if it exists

i. P(A,B,B), P(X,Y,Z)

ii. Q(Y, G(A,B)), Q(G(X,X),Y) [6+6+4]

7. Define the operator schemata for the problem of putting on shoes and socks and a hat and coat; assuming that there are no pre-conditions for putting on the hat and coat. Give a partial-order plan that is a solution, and show that there are 180 different linearizations of this solution. [16]

8. (a) Explain supervised learning, reinforcement learning, and unsupervised learn-ing

(b) Comment on the expressiveness of decision trees

(c) What do you mean by incremental learning. [6+6+4]

SET2:

1. Compare a computer and human brain and also explain how human brain process the information. [16]

2. How breadth first search works? What are the features and applications of breadth first search? [16]

3. (a) Explain difference between simple hill climbing and steepest ascent hill climb-ing.

(b) Explain difference between best first search and steepest ascent hill climbing. [8+8]

4. Explain the following with respect to minimax procedure.

(a) Static evaluation function.

(b) Maximizing ply, Maximizing player

(c) Manimizing ply, Manimizing player

(d) Minimax procedure. [3+3+3+7]

5. Jones, Smith, and Clark hold the jobs of programmer, knowledge engineer, and manager. Jones owes the programmer $10. The manager’s spouse prohibits bor-rowing money. Smith is not married. Your task is to figure out which person has which job. Solve the problem using propositional logic. [16]

6. (a) Give the steps for conversion to implicative normal form

(b) For each of the following pairs of atomic sentences, give the most general

unifier if it exists

i. older(father(y),y), older(father(x),john)

ii. knows(father(y),y), knows(x,x)

iii. f(Marcus,g(x,y)) and f(x,g(Caeser,Marcus)) [10+6]

7. (a) Distinguish between simple planning agent and problem solving agent

(b) Explain forward state space search with an example

(c) What do you mean by partial order planning. [6+6+4]

8. What are decision trees? Draw a decision tree for the problem of deciding whether

or not to move forward at a road intersection given that the light has just turned

green.

[16]

SET3:

1. Explain the Neuron and a simulated neuron with a diagram and compare. [16]

2. What is a greedy best first search? Explain with example and diagram. [16]

3. Explain simulated annealing algorithm with an example. [16]

4. Explain the following with respect to minimax procedure.

(a) Static evaluation function.

(b) Maximizing ply, Maximizing player

(c) Manimizing ply, Manimizing player

(d) Minimax procedure. [3+3+3+7]

5. (a) Describe a generic knowledge based agent.

(b) What are the problems with propositional logic?

(c) How can a knowledge-based agent be made fully autonomous. [6+6+4]

6. (a) Give the steps for conversion to implicative normal form

(b) For each of the following pairs of atomic sentences, give the most general unifier if it exists

i. older(father(y),y), older(father(x),john)

ii. knows(father(y),y), knows(x,x)

iii. f(Marcus,g(x,y)) and f(x,g(Caeser,Marcus)) [10+6]

7. Let us consider a version of the milk/banana/drill shopping problem

(a) Let CC denote a credit card that the agent can use to buy any object. Write the description of Buy so that the agent has to have its credit card in order to buy any thing.

(b) Write a Pick-Up operator that enables the agent to have an object if it is portable and at the same location as the agent.

(c) Assume that the credit card is at home, but Have(CC) is initially false. Con-struct a partially ordered plan that achieves the goal, showing both ordering constraints and causal links

(d) Explain in detail what happens during the planning process when the agent explores a partial plan in which it leaves home without the card. [4+4+4+4]

8. (a) Explain the major issues that affect the design of the learning element.

(b) Explain various forms of learning [8+8]

SET4:

1. What is an agent? Explain the vacuum cleaner world example? [16]

2. What is iterative deepening depth first search? Explain with an algorithm and

diagram. [16]

3. Explain why it is a good heuristic to choose the variable that is most constrained,

but the value that is least constraining in a CSP search. [16]

4. Explain the following:

(a) Waiting for quiescence

(b) Secondary search. [8+8]

5. Jones, Smith, and Clark hold the jobs of programmer, knowledge engineer, and manager. Jones owes the programmer $10. The manager’s spouse prohibits bor-rowing money. Smith is not married. Your task is to figure out which person has which job. Solve the problem using propositional logic. [16]

6. (a) Comment on propositional Vs first-order inference

(b) How can resolution be used to show that a sentence is

i. valid

ii. unsatisfiable

For each of the following pairs of atomic sentences, give the most general uni-

fier if it exists

i. P(A,B,B), P(X,Y,Z)

ii. Q(Y, G(A,B)), Q(G(X,X),Y) [6+6+4]

7. Let us consider a version of the milk/banana/drill shopping problem

(a) Let CC denote a credit card that the agent can use to buy any object. Write the description of Buy so that the agent has to have its credit card in order to buy any thing.

(b) Write a Pick-Up operator that enables the agent to have an object if it is portable and at the same location as the agent.

(c) Assume that the credit card is at home, but Have(CC) is initially false. Con- struct a partially ordered plan that achieves the goal, showing both ordering constraints and causal links

(d) Explain in detail what happens during the planning process when the agent explores a partial plan in which it leaves home without the card. [4+4+4+4]

8. What are decision trees? Draw a decision tree for the problem of deciding whether or not to move forward at a road intersection given that the light has just turned green.[16]

May/Jun 2009

SET1:

1. Explain 8-Puzzle problem and 8-queens problems. [8+8]

2. Write several iterations of iterative deepening and also explain with algorithm anddiagrams. [16]

3. Explain each of the following with an example:

(a) Constraint graph

(b) Constraint satisfaction problem

(c) Cryptarithmetic puzzle. [4+6+6]

4. (a) Is exhaustive search for games such as chess is possible? Explain with your own measures.

(b) Explain secondary research. [8+8]

5. Jones, Smith, and Clark hold the jobs of programmer, knowledge engineer, and manager. Jones owes the programmer $10. The manager’s spouse prohibits bor-rowing money. Smith is not married. Your task is to figure out which person haswhich job. Solve the problem using propositional logic. [16]

6. (a) Explain forward-chaining algorithm

(b) Here are two sentences in the language of first-order logic:

i. –Vx ∋ y (x=y)

ii. ∋y –Vx (x=y)

Assume that the variable range over all natural numbers 0, 1, 2, .... , and that the”=” predicate means “greater than or equal to”. Try to provethat

(i) follows from (ii) using resolution; continue until the proof breaks down and you cannot proceed. Show the unifying substitution for each resolution step. If the proof fails, explain exactly where, how, and why itbreaks down. [8+8]

7. Let us consider a version of the milk/banana/drill shopping problem

(a) Let CC denote a credit card that the agent can use to buy any object. Write the description of Buy so that the agent has to have its credit card in orderto buy any thing.

(b) Write a Pick-Up operator that enables the agent to have an object if it is portable and at the same location as the agent.

(c) Assume that the credit card is at home, but Have(CC) is initially false. Construct a partially ordered plan that achieves the goal, showing both ordering constraints and causal links

(d) Explain in detail what happens during the planning process when the agent explores a partial plan in which it leaves home without the card. [4+4+4+4]

8. (a) Explain the major issues that affect the design of the learning element.

(b) Explain various forms of learning [8+8]

SET2:

1. What are four basic kinds of agent program that embody the principles underlying almost all intelligent system? Explain any two of them with diagram. [4+6+6]

2. (a) Explain why A* algorithm is admissible and computationally optimal.

(b) What is uniform cost search? [8+8]

3. (a) What is steepest descent? What are the drawbacks of it?

(b) Explain the map coloring as a constraint satisfaction problem. [8+8]

4. “Minimax procedure is a depth first, depth limited Recursive Procedure” Explain this fact by using your own example and diagram. [16]

5. (a) Describe generic knowledge based agent.

(b) What are the problems with propositional logic?

(c) How can a knowledge-based agent be made fully autonomous? [6+6+4]

6. (a) Give the steps for conversion to implicative normal form

(b) For each of the following pairs of atomic sentences, give the most general unifier if it exists

i. older(father(y),y), older(father(x),john)

ii. knows(father(y),y), knows(x,x)

iii. f(Marcus,g(x,y)) and f(x,g(Caeser,Marcus)) [10+6]

7. (a) What are the limitations of the problem solving approach and what is the motivation behind the design of planning systems?

(b) What do you mean by state space search?

(c) What do you mean by regression planning? [6+6+4]

8. Explain with an example decision tree learning algorithm [16]

SET3:

1. Explain 8-Puzzle problem and 8-queens problems. [8+8]

2. What is a heuristic search? Explain various types of heuristic searches. [16]

3. Explain Arc consistency and path consistency of CSPs. [16]

4. (a) Is exhaustive search for games such as chess is possible? Explain with your own measures.

(b) Explain secondary research. [8+8]

5. (a) What do you mean by monotonicity? Are propositional and first-order logic

monotonic?

(b) Is the sentence ”Either 2+2=4 and it is raining, or 2+2=4 and it is not raining” making a claim about arithmetic, weather, or neither? Explain.

(c) Look at the following sentences and decide for each if it is valid, unsatisfiable, or neither using equivalence rules.

i. ((smoke ^ heat) ! fire) , (smoke)

ii. (big V dumb) V (big ! dumb). [6+6+4]

6. (a) What do you mean by semidecidability? What is semidecidable in first-order logic?

(b) Comment on completeness of first-order logic

(c) What do you mean by conjunctive normal form and implicative normal form? [6+6+4]

7. (a) What are the limitations of the problem solving approach and what is the motivation behind the design of planning systems?

(b) What do you mean by state space search?

(c) What do you mean by regression planning? [6+6+4]

8. (a) Explain about inducing decision trees with an example.

(b) Explain EM algorithm. [8+8]

SET4:

1. (a) Define rational agent, and explain it.

(b) What are the four things that “What is rational at any given time depends

on”?

(c) Compare rationality and omniscience with an example. [6+4+6]

2. Explain depth first search and breadth first search with neat diagrams. [8+8]

3. Explain each of the following with an example:

(a) Constraint graph

(b) Constraint satisfaction problem

(c) Cryptarithmetic puzzle. [4+6+6]

4. For a chess game, assume the average branching factor in 35 and the number of

moves made by each player to win or loss is 50 is exhausted search is possible?[16]

5. (a) Explain forward and backward chaining in propositional logic

(b) Consider the following axioms.

P

(P ^ Q) ! R

(SVT) ! Q

T

Prove R using resolution in propositional logic. [10+6]

6. (a) Comment on propositional Vs first-order inference

(b) How can resolution be used to show that a sentence is

i. valid

ii. unsatisfiable

(c) For each of the following pairs of atomic sentences, give the most general uni-fier if it exists

i. P(A,B,B), P(X,Y,Z)

ii. Q(Y, G(A,B)), Q(G(X,X),Y) [6+6+4]

7. Let us consider a version of the milk/banana/drill shopping problem

(a) Let CC denote a credit card that the agent can use to buy any object. Writethe description of Buy so that the agent has to have its credit card in orderto buy any thing.

(b) Write a Pick-Up operator that enables the agent to have an object if it isportable and at the same location as the agent.

(c) Assume that the credit card is at home, but Have(CC) is initially false. Con-struct a partially ordered plan that achieves the goal, showing both orderingconstraints and causal links

(d) Explain in detail what happens during the planning process when the agentexplores a partial plan in which it leaves home without the card. [4+4+4+4]

8. (a) Explain supervised learning, reinforcement learning, and unsupervised learn-ing

(b) Comment on the expressiveness of decision trees

(c) What do you mean by incremental learning? [6+6+4]