NPTEL 2020 – Artificial Intelligence Search Methods For Problem Solving Week 6 Assignment 6 Answers

Assignemnt 6

Due date: 2020-10-28, 23:59 IST.
The figure shows a map (repeated from Week 5) with several locations on a grid where each tile is 10km 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 and the cost is the same in both directions



For this map, MoveGen returns nodes in alphabetical order.

When several nodes have the same cost, use alphabetical order to break ties.

When the same node occurs multiple times with the same cost then use the open-sequence-number to break ties, i.e., pick up the node occurrence that is oldest (was placed earliest in time) in the OPEN list.

Where needed, use Manhattan distance as the heuristic function.

Simulate WA* with w=2, Breadth First Heuristic Search with U=312, Sparse-Memory Graph Search, and Beam Search with w=2 on the above map and answer the following questions


BEGIN GROUP

For w=2, in f = g + w*h, simulate WA* algorithm on the given map. List the 3rd, 6th and 9th nodes inspected by the algorithm.

Enter node labels as a comma separated list. DO NOT enter extraneous characters like spaces, dots, brackets, extra commas, etc.
1 point
What are the f-values of the 3rd, 6th and 9th nodes listed in the previous question?

Enter the costs as a comma separated list of natural numbers. DO NOT enter extraneous characters like spaces, dots, brackets, extra commas, etc
1 point
For WA* with w=2,​ ​ what is the path found by the algorithm?

Enter the path (starting from S and ending in G) as a comma separated list of node labels. DO NOT enter extraneous characters like spaces, dots, brackets, extra commas, etc
1 point
What is the cost of the path found by WA* algorithm?

Enter a natural number
1 point


END GROUP


BEGIN GROUP

Simulate the Breadth First Heuristic Search (BFHS) with U=312 on the given map. Remember that the MoveGen function generates nodes in alphabetic order and that the algorithm does not add nodes that are in OPEN or CLOSED to OPEN.

Assume f = g + h, where g is the actual-cost of the path generated by BFHS (not by A*), and h is the heuristic value. Prune the new nodes if f-value is greater than or equal to U. Prune the nodes before placing them in OPEN list.
List the 5th, 8th, 11th and 14th nodes visited by BFHS.

Enter the node labels as a comma separated list. DO NOT enter extraneous characters like spaces, dots, brackets, extra commas, etc.
1 point
What are the costs of the 5th, 8th, 11th and 14th nodes listed in the previous question?

Enter the costs as a comma separated list of natural numbers. DO NOT enter extraneous characters like spaces, dots, brackets, extra commas, etc
1 point


END GROUP


BEGIN GROUP

For the following questions assume that the Sparse-Memory Graph Search (SMGS) has enough memory to only hold 4 nodes in Kernel. We will not count S to be part of the Kernel (because it is never deleted).

In this group, enter ALL node-lists in ALPHABETIC order.

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

If there are no nodes then enter NIL, otherwise enter the node labels as a comma separated list in ALPHABETIC order. DO NOT enter extraneous characters like spaces, dots, brackets, extra commas, etc
1 point
List the nodes in the BOUNDARY after SMGS has inspected 4 nodes starting with S, where S is the first node.

If there are no nodes then enter NIL, otherwise enter the node labels as a comma separated list in ALPHABETIC order. DO NOT enter extraneous characters like spaces, dots, brackets, extra commas, etc
1 point
List the nodes in the KERNEL after SMGS has inspected 4 nodes starting with S, where S is the first node.

If there are no nodes then enter NIL, otherwise enter the node labels as a comma separated list in ALPHABETIC order. DO NOT enter extraneous characters like spaces, dots, brackets, extra commas, etc.
1 point
List the nodes in OPEN after SMGS has inspected 8 nodes starting with S, where S is the first node.

If there are no nodes then enter NIL, otherwise enter the node labels as a comma separated list in ALPHABETIC order. DO NOT enter extraneous characters like spaces, dots, brackets, extra commas, etc.
1 point
List the nodes in the BOUNDARY after SMGS has inspected 8 nodes starting with S, where S is the first node.

If there are no nodes then enter NIL, otherwise enter the node labels as a comma separated list in ALPHABETIC order. DO NOT enter extraneous characters like spaces, dots, brackets, extra commas, etc
1 point
List the nodes in the KERNEL after SMGS has inspected 8 nodes starting with S, where S is the first node.

If there are no nodes then enter NIL, otherwise enter the node labels as a comma separated list in ALPHABETIC order. DO NOT enter extraneous characters like spaces, dots, brackets, extra commas, etc
1 point
List the nodes in OPEN after SMGS has inspected 12 nodes starting with S, where S is the first node.

If there are no nodes then enter NIL, otherwise enter the node labels as a comma separated list in ALPHABETIC order. DO NOT enter extraneous characters like spaces, dots, brackets, extra commas, etc
1 point
List the nodes in the BOUNDARY after SMGS has inspected 12 nodes starting with S, where S is the first node.

If there are no nodes then enter NIL, otherwise enter the node labels as a comma separated list in ALPHABETIC order. DO NOT enter extraneous characters like spaces, dots, brackets, extra commas, etc
1 point
List the nodes in the KERNEL after SMGS has inspected 12 nodes starting with S, where S is the first node.

If there are no nodes then enter NIL, otherwise enter the node labels as a comma separated list in ALPHABETIC order. DO NOT enter extraneous characters like spaces, dots, brackets, extra commas, etc
1 point


END GROUP


BEGIN GROUP

Simulate the Beam Search (with f-values) with beam width w=2. This means the best two nodes are retained at each level irrespective of whether they are better than their parents or not.
What is the path found by Beam Search?

Enter the path (starting from S and ending in G) as a comma separated list of node labels. DO NOT enter extraneous characters like spaces, dots, brackets, extra commas, etc
1 point
What is the cost of the path found in the previous question?

Enter a natural number.
1 point
What is the other node in the beam (apart from G) at the point when the algorithm terminates?
1 point
What is the cost of the node found in the previous question?

Enter a natural number.
1 point


END GROUP

1 point
When the Monotone Condition is satisfied we sometimes force the search to “never leak” back because

You may submit any number of times before the due date. The final submission will be considered for grading.