# Artificial Intelligence Search Methods For Problem Solving 2021 NPTEL Artificial Intelligence Search Methods For Problem Solving the course aims to be successful, an autonomous agent should be able to move from a given situation or state of affairs to arrive at decisions that will transform one’s current situation into a desired goal-state. With the capacity to imagine the consequences of its decisions and actions, a robot can learn how to identify what works best in its environment versus what does not respond well towards the goal being sought after by an agent.

Artificial Intelligence Search Methods For Problem Solving is a MOOC course offered by IIT Madras on the NPTEL platform. This course helps the students to go into the details of how an agent can represent its world and reason with what it knows. The course is developed By Prof. Deepak Khemani is Professor at the Department of Computer Science and Engineering, IIT Madras.

1. INTENDED AUDIENCE: UG/PG students who are interested in AI
2. Requirements/Prerequisites: Nil
3. INDUSTRY SUPPORT: Any industry

CRITERIA TO GET A CERTIFICATE

Average assignment score = 25% of the average of the best 8 assignments out of the total 12 assignments given in the course.
Exam score = 75% of the proctored certification exam score out of 100 Final score = Average assignment score + Exam score

Students will be eligible for CERTIFICATE ONLY IF AVERAGE ASSIGNMENT SCORE >=10/25 AND EXAM SCORE >= 30/75. If any of the 2 criteria are not met, the student will not get the certificate even if the Final score >= 40/100.

## NPTEL Artificial Intelligence Search Methods For Problem Solving ASSIGNMENT WEEK 12 ANSWERS:-

Q1. To model a problem as a CSP one has to __________________ .

Q2. A constraint on a subset of the variables __________________ .

Q3. Which of the following statements are true regarding solving a CSP?

Q4. When a set of statements in Propositional Logic is seen as a CSP then __________________ .

Q5. When a set of statements in Propositional Logic is viewed as a CSP then __________________ .

Q6. While modeling components for the task of model based diagnosis, each component is modeled as _________

Q7. The goal of constraint propagation or consistency enforcement is __________________ .

Q8. Does the above puzzle have a unique solution?

Q9. Is the value for the letter G unique for the above puzzle? If your answer is yes, then enter the value below, otherwise enter NIL.

Q10. Is more than one value possible for the letter J (in different solutions of course)?

Q11. What can one say about the value for the letter D?

Q12. What can one say about the value for the letter O?

Q13. For the above CSP the value of Dx after the network is made arc consistent is _________ .

Q14. For the above CSP the value of Dy after the network is made arc consistent is _________ .

Q15. For the above CSP the value of DZ after the network is made arc consistent is _________ .

Q16. The algorithm will next assign a value to the variable _________ .

Q17. What is the value that the algorithm will assign to the above variable?

Q18. What are the values in the domain DD of region D at this point (after the variable in question 17 was  assigned a value)?

Q19. What are the values in the domain DE of region E at this point (after the variable in question 17 was assigned a value)?

Q20. What are the values in the domain DF of region F at this point (after the variable in question 17 was assigned a value)?

## NPTEL Artificial Intelligence Search Methods For Problem Solving ASSIGNMENT WEEK 11 ANSWERS:-

Q1. An agent who creates a representation of its domain, needs to have the ability to reason because ____________ .

Q2. Given a knowledge base KB of true statements, entailment is concerned with ____________ .

Q3. A rule of inference ____________ .

Q4. An algorithm for making inferences is a procedure to add new statements using rules of inference. The algorithm is ____________ .

Q5. Modified Modus Ponens ____________ .

Q6. Automated theorem proving is a search algorithm ____________ .

Q7. Identify the true statements.

Q8. Given a KB and a proof procedure, ____________ .

Q9. Let P stand for “path is empty” and Q for “count is different” and ¬Q for “count is same”. Are the statements A and B, given below, equivalent? If yes, then identify the equivalence formula, or else, mark the last option.

Q10. Select the valid entailments.

Q11. Which of the following variable substitutions (Θ) will make the following two formulas equal.

Q12. Consider a knowledge base with three statements:

Q13. Identify the rules that participate in the MoveGen function for Forward Chaining. Against each rule write the number of instances of that rule that form the MoveGen with the above facts.

Q14. If the,, Forward Chaining algorithm runs till no more inferences are made, which of the following facts will be added to ,the KB?

Q15. If the Goal is CanVisit(?X, concert) then which of the rules (A,B,C,D) will be part of the MoveGen in Backward Chaining? That is, what are the relevant rules that generate subgoals, and how many instances of those rules will find a place in the search tree rooted at the goal? Against each rule write the number of instances that will be in the MoveGen.

Q16. If the Goal is CanVisit(?X, concert) which of the following goals will be reported as true by Backward Chaining?

Q17. Which of the following queries/goals result in an answer “True” by a theorem prover in the Forward Chaining Mode?

Q18. Which of the following queries/goals result in an answer “True” by a theorem prover in the Backward Chaining Mode?

Q19. Which of the following queries/goals result in an answer “True” by a theorem prover in the Forward Chaining Mode?

Q20. Which of the following queries/goals result in an answer “True” by a theorem prover in the Backward Chaining Mode?

## NPTEL Artificial Intelligence Search Methods For Problem Solving ASSIGNMENT WEEK 10 ANSWERS:-

Q1. Select the options that relate to Production Systems.

Q2. In a Production System, knowledge is stored as a ________ .

Q3. Conflict resolution ____________

Q4. In a Match-Resolve-Execute cycle ______________

Q5. When a WME enters a Rete Net ______________.

Q6. When the production system is in flight, after the first two rounds of firings, the newly created WME (timestamp 103) is _________ .

Q7. When the production system is in flight, after rule-2 is fired for the second time, the newly created WME (timestamp 106) is _________ .

Q8. Now, the production system has halted. In total, rule-1 was fired _______ times. Your answer must be a whole number.

Q9. Now, the production system has halted. In total, rule-2 was fired _______ times. Your answer must be a whole number.

Q10. How many classes are referred-to in the rule given above? Your answer must be a whole number.

Q11. Which of the following Rule-WME tuples will be present in the conflict set?

Q12. How many WMEs will be present in the WM after 2 cycles of execution? Your answer must be a whole number.

Q13. The location of WME 201 is _________ . Enter the label of the alpha nodes as a comma separated list in NUMERICAL ASCENDING order. Or enter Nil.

Q14. The location of WME 203 is _ .

Q15. The location of WME 211 is _________ . Enter the label of the alpha nodes as a comma separated list in NUMERICAL ASCENDING order. Or enter Nil.

Q16. The number of instances of R6 in the conflict set is _________ . Enter the count, or the number 0 if the rule is not in the conflict set.

Q17. The number of instances of R4 in the conflict set is _________ . Enter the count, or the number 0 if the rule is not in the conflict set

Q18. The number of instances of R2 in the conflict set is _________ . Enter the count, or the number 0 if the rule is not in the conflict set.

Q19. If the inference engine uses Specificity as the conflict resolution strategy then identify the rule-data tuples that will be ready to fire. If multiple rule-data tuples qualify then choose the rule Ri with the smallest index i. Your answer must be a comma separated list starting with a rule label followed by the

Q20. If the inference engine uses Recency as the conflict resolution strategy then identify the rule-data tuples that will be ready to fire. If multiple rule-data tuples qualify then choose the rule Ri with the smallest index i.

## NPTEL Artificial Intelligence Search Methods For Problem Solving ASSIGNMENT WEEK 9 ANSWERS:-

Q1. From the set of actions given below, what are the actions that will be present in the first layer of the planning graph being constructed by algorithm Graphplan?

All the best for the final exam, for extra preparation, take our membership for better score in exam read more here:- Final Exam Membership

Q2. What is the number of actions, not counting the No-op actions, in the plan produced by Graphplan?

Q3. What is the makespan of the plan produced by Graphplan?

Q4. Which of the planning algorithms are guaranteed to find an optimal problem in any domain?

Q5. The term “Means” in the Means-Ends-Analysis (MEA) proposed by Newell and Simon refers to

Q6. The term “Ends” in the Means-Ends-Analysis (MEA) proposed by Newell and Simon refers to

Q7. The term “Analysis” in the Means-Ends-Analysis (MEA) proposed by Newell and Simon refers to

Q8. The main idea behind Means-Ends-Analysis is

Q9. An And-Or graph is a graph where

Q10. The AO* algorithm is most similar to

Q11. The termination criterion for the AO* algorithm is

Q12. Starting with S list the nodes in the order they are expanded by algorithm AO*. Observe that primitive nodes are not expanded. Your answer must be a comma separated list of node names.

Q13. List the value of the start node S after every expansion listed above. Your answer must be a comma separated list of numbers.

Q14. What is the cost of the solution found? Your answer must be a number.

Q15. Is the solution found by the algorithm the optimal solution?

Q16. Starting with S list the nodes in the order they are expanded by algorithm AO*. Observe that primitive nodes are not expanded. Your answer must be a comma separated list of node names.

Q17. List the value of the start node S after every expansion listed above. Your answer must be a comma separated list of numbers.

Q18. What is the cost of the solution found? Your answer must be a number.

Q19. Is the solution found by the algorithm the optimal solution?

Q20. Given the heuristic values given in the graph above, on inspection the heuristic function

## NPTEL Artificial Intelligence Search Methods For Problem Solving ASSIGNMENT WEEK 8 ANSWERS:-

Q1. Which agent has the shortest optimal plan?

Answer:- b(can be wrong, do it yourself and if wrong correct us)

Q2. What is the length of the above agent’s optimal plan?

All the best for the final exam, for extra preparation, take our membership for better score in exam read more here:- Final Exam Membership

Q3. Which agent has the longest optimal plan?

Q4. What is the length of the above agent’s optimal plan?

Q5. Using Forward State Space Planning (FSSP) which of the following could be the first operator considered by Ayesha?

Q6.

Q7.

Q8.

Q9.

Q10.

Q11.

Q12.

Q13.

Q14.

Q15.

Q16.

Q17.

All the best for the final exam, for extra preparation, take our membership for better score in exam read more here:- Final Exam Membership

Q18.

Q19.

Q20.

## NPTEL Artificial Intelligence Search Methods For Problem Solving ASSIGNMENT WEEK 7 ANSWERS:-

Q1. Game Theory is concerned with _________ .

Q2. The Prisoner’s Dilemma demonstrates that _________ .

Q3. The games studied in this course are _________ .

Q4. In the Alpha-Beta algorithm, list the line numbers where alpha-cutoff and beta-cutoff occur, respectively.

Q5. A strategy for MAX in a two player game tree is a subtree that is chosen as below:

Q6. Four two-player game-trees are shown below with some edges highlighted in bold. Which of these depict a game strategy for the root (MAX)?

Q7. What is the outcome (W, L or D) of the game when both players play perfectly?

Q8. Which of the moves P, Q, R, S are best moves for Max?

Q9. Which of the moves P, Q, R, S lead to a draw if both play perfectly after the first move?

Q10. What is the MinMax value of the game?

Q11. List the nodes (node reference numbers) in the best strategy.

Q12.Change the eval of one horizon node to get a MiniMax value of 64. Which node will you change and what will be its new eval? Choose the maximum possible eval for the horizon node that you wish to change.

Q13. Simulate AlphaBeta algorithm on Game Tree 1. What is the number of alpha-cuts and beta-cuts? Note that a single cut may remove a bunch of edges at once.

Q14. List the horizon nodes pruned by alpha-cuts.

Q15.List the horizon nodes pruned by beta-cuts.

Q16. What is the total number of strategies in Game Tree 1?

Q17. In Game Tree 1, what is the number of initial clusters formed by SSS*?

Q18. List the horizon nodes in the initial clusters formed by SSS*?

Q19. Simulate SSS* algorithm on Game Tree 1. When the h-values are equal then select the leftmost deeper node in the tree to break the tie. What is the total number of horizon nodes moved to SOLVED status by SSS*?

Q20. What are the horizon nodes that are assigned SOLVED status by SSS*? When h-values are equal then select the leftmost deeper node in the tree to break the tie.

## NPTEL Artificial Intelligence Search Methods For Problem Solving ASSIGNMENT WEEK 6 ANSWERS:-

Q1. In the city map, which of the following are true?

Q2. Beam Search is used before DCBFS and BSS to find an upper bound U for the solution. Which variations of Beam will do the task of finding U for going from S to G in the graph below?

The figure (repeated from Week 5) shows a map with several locations on a grid where each tile is 10 km x 10 km in size. In this map, S is the start node and G is the goal node, the locations are connected by two-way edges (roads). Each edge has a cost which is the same in both directions.

Q3. Using w=3 in f = g + wh, simulate WA algorithm on the given map. Let S be the first node to be inspected, now list the 4th, 5th and 6th nodes inspected by the algorithm.

Q4. What are the f-values of the 4th, 5th and 6th nodes listed in the previous question?

Q5. For WA* with w=3, what is the path found by the algorithm?

Q6. What is the cost of the path found by WA* algorithm? (Compare 3A* with Best First Search and A* from Week 5 assignment.)

Q7. List the 4th, 8th and 12th nodes inspected by BFHS.

Q8. What are the costs of the 4th, 8th and 12th nodes listed in the previous question?

Q9. List the nodes in OPEN after SMGS has inspected the 4th node, where S is the first node inspected.

Q10. List the nodes in the BOUNDARY after SMGS has inspected the 4th node, where S is the first node inspected.

Q11. List the nodes in the KERNEL after SMGS has inspected the 4th node, where S is the first node inspected.

Q12. List the nodes in OPEN after SMGS has inspected the 8th node, where S is the first node inspected.

Q13. List the nodes in the BOUNDARY after SMGS has inspected the 8th node, where S is the first node inspected.

Q14. List the nodes in the KERNEL after SMGS has inspected the 8th node, where S is the first node inspected.

Q15. List the nodes in OPEN after SMGS has inspected the 12th node, where S is the first node inspected.

Q16. List the nodes in the BOUNDARY after SMGS has inspected the 12th node, where S is the first node inspected.

Q17. List the nodes in the KERNEL after SMGS has inspected the 12th node, where S is the first node inspected.

Q18. What is the path found by Beam Search?

Q19. What is the cost of the path found in the previous question?

Q20. What is the other node in the beam (apart from G) at the point when the algorithm terminates?

## NPTEL Artificial Intelligence Search Methods For Problem Solving ASSIGNMENT WEEK 5 ANSWERS:-

Q1. Consider the (not to scale) map of Triangle Country. We can think of this map as a complete graph with hidden edges carrying an infinite (or +LARGE) cost. To avoid clutter the infinite-cost edges are not shown in the map.

Q2. What is the actual cost of the optimal tour for the above problem?

Q3. The reasons why one needs to underestimate the estimated cost of fully refining a candidate in order to guarantee an optimal solution are:

Q4. In the A* algorithm, the cost and parent pointers of new nodes (nodes not present in OPEN or CLOSED) are updated in _________________ .

Q5. In the A* algorithm, the cost and parent pointers of nodes in OPEN list are updated in _________________ .

Q6. In the A* algorithm, the cost and parent pointes of nodes in CLOSED list are updated in _________________ .

Q7.

Q8.

Q9.

Q10.

Q11.

Q12.

Q13.

Q14.

Q15.

Q16.

Q17.

Q18.

Q19.

Q20.

## NPTEL Artificial Intelligence Search Methods For Problem Solving ASSIGNMENT WEEK 4 ANSWERS:-

Q1. Consider the influence graph shown below, it depicts a closed ecosystem. Do not impose any more conditions (from nature) on this graph. Work only with the given data. Keep it simple.

Q2. The idea of using population based methods to solve optimization problems _________ .

Q3. Which of the following are true? Mark all correct answers

Q4. Genetic Algorithms work best when _________ .

Q5. Darwin’s theory of natural selection can be seen as _________ .

Q6. Which one of the following completes the quote from Paul Valery in the context of Genetic Algorithms? “It takes two to invent anything. The one makes up combinations, _________________”

Q7. When Christof Koch said “The most complex object in the known universe” he was referring to _________ .

Q8. What is the role an individual ant plays in the Ant Colony Algorithm?

Q9. Consider chromosomes made of 5-bit binary strings and a fitness function f(a,b,c,d,e) that is a square of (a + 2b + 3c + 4d + 5e) where “abcde” is the chromosome. An initial population is given in the table.

Q10. In the previous question, the individual instances selected for crossover are ___________ .

Q11. The single point crossover can be used to solve the TSP problem if the representation is

Q12. For each graph in the figure, produce a tour by traversing only along the given edges.

Q13. Which of the following are valid path representations of the tour?

Q14. Which of the following are valid adjacency representations of the tour?

Q15. Which of the following are valid ordinal representations of the valid path representations listed in question 13.

Q16. Path representations of two tours are given below. Generate offsprings using Partially Mapped Crossover between P1 and P2 using the locations from 4 to 8 as the mapping segment.

Q17. Path representations of two tours are given below. Generate offsprings using Order Crossover between P1 and P2 and use locations from 4 to 8 as the mapping segment. In the child tour, retain the mapping segment in the middle. For example, C1 = ?,?,?,T,Y,Q,Z,V,?,?,?

Q18. Path representations of two tours are given below. Generate offsprings using Cycle Crossover between P1 and P2. Inherit odd cycles from one parent and even cycles from the other parent to create offspring.

Q19. Path representations of two tours are given below. Compute the ordinal representations of the parent tours. And use single point crossover (cut right after the 5th location) to generate offsprings.

Q20. A single tour of N cities has a ___________ .

## NPTEL Artificial Intelligence Search Methods For Problem Solving ASSIGNMENT WEEK 3 ANSWERS:-

Q1. In the map, starting with node S, list the first 7 nodes inspected by Depth First Search (DFS) algorithm. List the nodes in the order they were inspected. If the algorithm terminates early then list the nodes inspected up until termination.

Answer:- S,E,A,B,C,D,I CAN BE WRONG DONT COPY BLINDLY

Q2. In the map, starting with node S, list the first 7 nodes inspected by the Breadth First Search (BFS) algorithm. List the nodes in the order they were inspected. If the algorithm terminates early then list the nodes inspected up until termination.

Answer:- S,E,J,K,O,A,B CAN BE WRONG DONT COPY BLINDLY

Q3. Which node has the largest heuristic value? What is its heuristic value? Remember to use the Manhattan distance.

Answer:- A,220 CAN BE WRONG DONT COPY BLINDLY

Q4. Which node has the smallest non zero heuristic value? What is its heuristic value? When there are multiple nodes with the smallest heuristic value then you may choose any one of those nodes.

Answer:- Y,-30 CAN BE WRONG DONT COPY BLINDLY

Q5. In the map, starting with node S, list the first 7 nodes inspected by the Best First Search algorithm. During inspection if multiple candidate nodes have the same estimated cost then inspect those nodes in alphabetical order.

Answer:- S,K,L,H,M,P,G CAN BE WRONG DONT COPY BLINDLY

Q6. In the map, starting with node S, list the first 7 nodes inspected by Hill Climbing algorithm. During inspection if multiple nodes have the same cost then inspect those nodes in alphabetical order.

Answer:- S,K,L CAN BE WRONG DONT COPY BLINDLY

Q7. For the given map, which of the algorithms finds a path from the start node S to the goal node G?

Answer:- A,B,D CAN BE WRONG DONT COPY BLINDLY

Q8. For the given city map, try and find a TSP tour using only the edges in the map. Choose the correct options below.

Answer:- A,B CAN BE WRONG DONT COPY BLINDLY

Q9. For the given city map, starting from T and using only the given edges and Euclidean distance as the edge cost, construct a TSP tour using the Nearest Neighbour algorithm. Then,

Q10.

Q11.

Q12.

Q13. Select the correct statements.

Answer:- A,D CAN BE WRONG DONT COPY BLINDLY

Q14. Given a finite state space or a finite solution space, which of these algorithms will always find a path/solution if one exists?

Answer:- A,B,C CAN BE WRONG DONT COPY BLINDLY

Q15. Working with the 2-City-Exchange or the 2-Edge-Exchange operator means that:

Answer:- C,D CAN BE WRONG DONT COPY BLINDLY

Q16. The Iterated Hill Climbing algorithm _________ .

Q17. The Hill Climbing algorithm may run into a local optimum because _________.

Q18. The Variable Neighbourhood Descent _________.

Q19. Simulated Annealing _________.

Q20. In stochastic local search _________.

## NPTEL Artificial Intelligence Search Methods For Problem Solving ASSIGNMENT WEEK 2 ANSWERS:-

Q1. Starting from (0, 5, 3), what is the least number of moves required to reach (4, 4, 0)?

Answer:- 5 CAN BE WRONG DONT COPY BLINDLY

Q2. Starting from (4, 4, 0), what is the least number of moves required to reach (0, 5, 3)?

Answer:- 2 CAN BE WRONG DONT COPY BLINDLY

Note:- WE NEVER PROMOTE COPYING AND We do not claim 100% surety of answers, these answers are based on our sole knowledge and by posting these answers we are just trying to help students to reference, so we urge do you assignment on your own.

Q3. What is the total number of states reachable from (0, 5, 3) via zero, one or more moves?

Answer:- 14 CAN BE WRONG DONT COPY BLINDLY

Q4. Starting from (0, 5, 3), what is the least number of moves required to reach (6, y, z) where y and z can be any values?

Q5. Starting from (0, 5, 3), what is the least number of moves required to measure 4 litres?

Q6. Starting from (0, 5, 3), what is the least number of moves required to measure 1 litre?

Answer:- 3 CAN BE WRONG DONT COPY BLINDLY

Note:- WE NEVER PROMOTE COPYING AND We do not claim 100% surety of answers, these answers are based on our sole knowledge and by posting these answers we are just trying to help students to reference, so we urge do you assignment own your own.

Q7. Starting from (0, 5, 3), what is the least number of moves required to reach (3, 3, 2)?

Q8. Which of the following is true about 6-5-3 water jug puzzle’s Reachable Subspace (see Notes) of the state space?

Q9. Four search trees associated with the above state space are shown below, where the open nodes are white filled and the closed nodes are blue filled. The search trees are shown for the case when the goal test has passed and the algorithm has ended.

Q10. Identify the BFS search tree?

Q11. At the instance when BFS finds G, the CLOSED list is _____ .

Answer:- yet to solve if know answer can drop in telegram group

Q12.

Q13.

Q14.

Q15.

Q16.

Q17.

Q18.

Q19.

Q20.

## NPTEL Artificial Intelligence Search Methods For Problem Solving ASSIGNMENT WEEK 1 ANSWERS:-

Q1. ________ is often referred to as the “first programmer”.

Q2. Who among the following was the first to build a calculating machine?

Q3.What can you recall about the “Dartmouth conference” discussed in the lectures? Remember that you will get a zero for even one wrong choice.

Q4. Who said the following? – “Thoughts themselves are symbolic representations”

Q5. The “Universal Grammar” is ______________________

Q6.  Can you recall the picture (below) from the lectures? In what context was it used?

Answer:- A- To express the richness,

Q7. The “Logic Theorist” is ____________________

Q8. Which of the following statements is/are true about “Physical Symbol System Hypothesis”?

Q9._________ was the first general-purpose mobile robot to be able to reason about its own actions.

Q10. ELIZA _________

Q11. Which of the following addresses the question whether machines can be intelligent? Tick all correct answers.

Q12.As discussed in the lectures, which of the following is/are successfully deployed embodied robots in the current times?

NOTE:- IF THERE IS ANY CHANGE IN ANSWERS OF Artificial Intelligence Search Methods For Problem WILL UPDATE BEFORE LAST DATE AND NOTIFY ON TELEGRAM OR WHATSAPP. SO KINDLY JOIN US, CLICK ON BELOW IMAGE AND JOIN US.

Q13. Which of the following AI agents demonstrated that machines can beat the very best humans at chess?

Q14.As discussed in the “Artificial Intelligence: Search Methods for Problem Solving – Prologue”, this course is about

Q15. The motorcycle soon overtook the school bus because it was going very fast. What was going very fast?

Q16.The motorcycle soon overtook the school bus because it was going very slow. What was going very slow?

Q17.  Suresh told Ramesh that he scolded him because he had hit the little dog. Who had hit the little dog?

Q18. Suresh told Ramesh that he scolded him because he had hit the little dog. Who did the scolding?