Artificial Intelligence : Search Methods For Problem Solving week 9 Solved

 

The Blocks World defines the following predicates and planning operators.

PREDICATES

on(X,Y)    - X is directly placed on Y.

onTable(X) - X is on the table.

holding(X) - The arm is holding X.

clear(X)   - X has nothing above it, it is clear.

armEmpty   - The arm is not holding any block, it is empty.

OPERATORS

Pickup(X) - Pick up X from the table.

   Preconditions: { armEmpty, clear(X), onTable(X) }

   Add-Effects  : { holding(X) }

   Del-Effects  : { armEmpty, onTable(X) }

Putdown(X) - Place X on the table.

   Preconditions: { holding(X) }

   Add-Effects  : { armEmpty, onTable(X) }

   Del-Effects  : { holding(X) }

Unstack(X,Y) - Pick up X which is directly on Y.

   Preconditions: { armEmpty, clear(X), on(X,Y) }

   Add-Effects  : { clear(Y), holding(X) }

   Del-Effects  : { armempty, on(X,Y) }

Stack(X,Y) - Place X on Y.

   Preconditions: { holding(X), clear(Y) }

   Add-Effects  : { armEmpty, on(X,Y) }

   Del-Effects  : { holding(X), clear(Y) }

Consider the following planning problem being solved by the Graphplan algorithm.

  

Start: { onTable(A), onTable(C), onTable(E),

clear(A), clear(D), clear(B),

on(D,C), on(B,E),

armEmpty }

Goal: { onTable(D), on(B,C), on(A,D) }

Fill in the mutex links and extend this plan graph as needed and then answer the questions in this group.

   

1 point

Which of the following are mutex action pairs in Layer 1?

 Pickup(A), Pickup(D)

 Pickup(A), Unstack(D,C)

 Unstack(B,E), Unstack(D,C)

 [nop-9], Unstack(D,C)

1 point

Which of the following are mutex proposition pairs in Layer 1?

 holding(A), [nop-4]

 holding(A), armEmpty

 clear(A), armEmpty

 holding(A), clear(C)

1 point

Which of the following are applicable actions in Layer 2

 Pickup(A)

 Pickup(C)

 Putdown(B)

 Stack(B,C)

 Stack(B,E)

 Unstack(B,E)

1 point

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

 Forward State Space Planning

 Backward State Space Planning

 Goal Stack Planning

 Partial Order Planning

 Graphplan

1 point

Which of the following statement(s) is/are true about the Planning Graph (PG)?

 The size of the PG increases monotonically (non decreasing) with each new layer. But the set of mutexes do not grow monotonically.

 While growing the PG, the algorithm does not consider the goal and applies all applicable actions at each layer.

 While growing the PG, the algorithm always considers the goal to decide the actions at each layer.

 The algorithm grows the PG until it levels off only when it does not find a plan.

1 point

A mutex relation in a planning graph __________ .

 can occur across layers signifying mutual exclusion

 is a relation between the preconditions of an action

 is a relation between a proposition and an action

 can occur across an individual proposition layer signifying mutual exclusion

 can occur across an individual action layer signifying mutual exclusion

 signifies a no-op action

GROUP 2

1 point

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

 the semantics or meaning of the domain predicates

 the average length of the solutions possible for a given problem

 the set of operators available to the problem solver

 a set of goalTest functions for the domain

1 point

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

 the termination criteria for the problem solving algorithm

 the moment when the problem solving process ends

 the set of goals the problem solver is tasked to achieve

 an external signal for the algorithm to end

1 point

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

 to grow the plan from the start state to the goal state

 to grow the plan from the goal conditions to the start state

 to reduce the largest difference between the start state and the goal state

 to work with an operator-difference table that organizes the domain

1 point

An AND-OR graph is a graph where __________ .

 each node is a problem or a goal

 edges from nodes transform a problem into one or more simpler problems

 solved nodes stand for primitive problems that do not need further work

 the solution is always a path from the start node to a solved node

1 point

The AO* algorithm is most similar to __________ .

 Backward State Space Planning

 Forward State Space Planning

 The SSS* algorithm for game playing

 The A* algorithm

1 point

The termination criterion for the AO* algorithm is __________ .

 as soon as a goal state has been reached

 as soon as a leaf labeled Solved is found

 as soon as the root node is labeled Solved

 as soon as the estimated cost of the root node is unacceptable

GROUP 3

The figure below is an AND-OR graph that depicts how a problem S can be decomposed and transformed into one or more, hopefully simpler, problems. Each node has a label (S, A, B, …).

The number in each node is the heuristic estimate of the cost of solving that node.

Nodes in double circles are primitive nodes, and their values are actual costs. Observe that a primitive node is added to the graph by its parent when the parent is expanded, and the primitive node is labeled as SOLVED and it will not be expanded subsequently.

Tie-breaker 1: For nodes with the same cost, expand in the ascending order of node labels.

Tie-breaker 2: For AND nodes, select the branch with the highest cost.

In the given AND-OR graph, how many full solutions (decompositions) exist for the problem S? Count the number of full solutions.

Enter a number.

NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.

Answer format: 42

1 point

GROUP 3.1

Let the cost of each edge be 2 units, now apply AO* algorithm to solve S and then answer the questions below.

Starting with S, list the nodes in the order they are expanded by AO* algorithm till it terminates. Observe that primitive nodes are not expanded.

Enter a list of node labels as a comma separated list.

NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.

Answer format: X,Y,Z

1 point

List the value of the start node S after every expansion listed above.

Enter a list of numbers.

NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.

Answer format: 4,1,4

1 point

What is the cost of the solution found by AO*?

Enter a number.

NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.

Answer format: 42

1 point

1 point

Did AO* find an optimal solution?

 Yes

 No

 Cannot say

GROUP 3.2

Let the cost of each edge be 10 units, now apply AO* algorithm to solve S and then answers the questions below.

Starting with S list the nodes in the order they are expanded by algorithm AO*. Observe that primitive nodes are not expanded.

Enter a list of node labels as a comma separated list.

NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.

Answer format: X,Y,Z

1 point

List the value of the start node S after every expansion listed above.

Enter a list of numbers.

NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.

Answer format: 4,1,4

1 point

What is the cost of the solution found by AO*? Enter a number.

NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.

Answer format: 42

1 point

1 point

Did AO* find an optimal solution?

 Yes

 No

 Cannot say

1 point

The heuristic values given in the AO graph __________ .

 is admissible for the graph in Case 1

 is not admissible for the graph in Case 1

 is admissible for the graph in Case 2

 is not admissible for the graph in Case 2