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

Where are the Answers ?

ReplyDeleteexactly , did you find the answers?

DeleteNoo , Today is the last date

ReplyDelete