Quizlet aa— is of No Use in Robotics Because Percepts States and Actions Are Continuous

Quiz: Classical search¶

Question 1

True or False: A* is of no use in robotics because percepts, states, and actions are continuous.

True

False

Question 2

The sheep and wolves problem is usually stated as follows. Three sheep and three wolves are on one side of a river, along with a boat that can hold one or two creatures. Find a way to get everyone to the other side without ever leaving a group of sheep in one place outnumbered by the wolves in that place. Any animal can steer the boat, and the boat cannot move on its own.

(This problem is famous in AI because it was the subject of the first paper that approached problem formulation from an analytical viewpoint (Amarel, 1968).)

Suppose we formulate the state as a six-tuple, where the first 3 indices hold the number of sheep, wolves, and boats on the first side of the river, and the other 3 hold the numbers on the second side. If the start state is (3,3,1,0,0,0), which of the following are valid goal states

(3, 3, 0, 0, 0, 1)

(0, 0, 1, 3, 3, 0)

(3, 0, 0, 0, 3, 1)

(0, 0, 0, 3, 3, 1)

Question 3

The sheep and wolves problem is usually stated as follows. Three sheep and three wolves are on one side of a river, along with a boat that can hold one or two creatures. Find a way to get everyone to the other side without ever leaving a group of sheep in one place outnumbered by the wolves in that place. Any animal can steer the boat, and the boat cannot move on its own.

(This problem is famous in AI because it was the subject of the first paper that approached problem formulation from an analytical viewpoint (Amarel, 1968).)

In formulating search problems, the first step involves determining what the state is. Which of the following constitute as valid state representations for this problem? Select all that apply.

An integer which translates to the number of sheep, wolves, and boats on one side of the river.

A six-tuple of integers, where the first 3 indices hold the number of sheep, wolves, and boats on the first side of the river, and the other 3 hold the numbers on the second side.

A seven-tuple of binary (i.e. 0 or 1) digits, where each index represents one of the sheep, wolves, or boats on one side of the river (0 would mean they are not on that side of the river, but on the other, and 1 would mean they are on that side).

A three-tuple of integers where each index holds the number of sheep, wolves, and boats on one side of the river, respectively.

Question 4

Which of the following elements is not a part of the problem formulation for a search problem

Actions

Goal state

States

Search tree

Initial state

Question 5

Consider BFS and DFS in a maze. Assuming the distance between two nodes is proportional to the cost, which of the following best represents the paths

Both algorithms will always find paths of the same length.

BFS will sometimes, but not always, find a shorter path than DFS.

DFS will always find a shorter path than BFS.

BFS will always find a shorter path than DFS.

DFS will sometimes, but not always, find a shorter path than BFS.

Question 6

Which of the following search algorithms is not matched with its appropriate search strategy (order of node expansion)

DFS: Deepest node first

Greedy search: Node closest to the goal state first

BFS: Cheapest node first

Question 7

The sheep and wolves problem is usually stated as follows. Three sheep and three wolves are on one side of a river, along with a boat that can hold one or two creatures. Find a way to get everyone to the other side without ever leaving a group of sheep in one place outnumbered by the wolves in that place. Any animal can steer the boat, and the boat cannot move on its own.

(This problem is famous in AI because it was the subject of the first paper that approached problem formulation from an analytical viewpoint (Amarel, 1968).)

For each of the following search algorithms, can the algorithm be used to solve this problem? Select it if it can.

BFS

DFS

A *

Question 8

Suppose h1 and h2 are admissible heuristics. For each of the following heuristics, select answer if it is guaranteed to be admissible, and otherwise do not select it.

max(h1,h2)

h1 + h2

min(h1,h2)

Assuming non-negative step costs, h(n)=0 is an admissible heuristic for any search problem.

An admissible heuristic always underestimates the true cost of getting from a state to the goal state.

Question 9

Is the following statement True or False?

Breadth-first search is complete even if zero step costs are allowed.

True

False

Question 10

Is the following statement True or False?

Greedy best first search guarantees both completeness and optimality.

True

False

Question 11

Consider A* graph search on the graph above. Arcs are labeled with action costs and states are labeled with heuristic values. Assume that ties are broken alphabetically.

What path does A* graph search return?

Start-A-B-Goal

Start-A-D-Goal

Start-A-C-Goal

Start-B-Goal

Start-A-B-D-Goal

Question 12

Consider A* graph search on the graph above. Arcs are labeled with action costs and states are labeled with heuristic values. Assume that ties are broken alphabetically.

In what order are states expanded by A* graph search? You may find it helpful to execute the search on paper.

Start, A, D, Goal

Start, A, B, Goal

Start, A, B, C, D, Goal

Start, A, C, Goal

Start, B, A, D, C, Goal

Start, B, A, D, B, C, Goal

Question 13

For each of the following search strategies, does the strategy use domain knowledge? Select answer if it use.

Breadth First Search

Uniform Cost Search

A *

Greedy Best-First Search

Question 14

Consider the state space shown above. If nodes are expanded ascending order, what is the order in which nodes will be visited for BFS with goal state 11.

Question 15

Consider the state space shown above. If nodes are expanded ascending order, what is the order in which nodes will be visited for depth-limited search with limit 2 and goal state 6.

Question 16

You control one insect in a rectangular maze-like environment with dimensions MxN, as shown in the figure above. The insect must reach a designated target location X, also known as the hive. There are no other insects moving around.

At each time step, the insect can move into an adjacent square if that square is currently free, or the insect may stay in its current location. Squares may be blocked by walls, but the map is known. Optimality is measured in terms of time steps; all actions have a cost of 1 regardless of whether the insect moves or stays put.

Note: your answer should reflect a general instance of the problem, not necessarily the example map shown.

Which of the following is a minimal correct state space representation?

An integer d encoding the Manhattan distance to the hive.

A tuple (x,y) encoding the x and y coordinates of the insect.

A tuple (x,y,d) encoding the insect's x and y coordinates, as well as d, the Manhattan distance to the hive.

This cannot be represented as a search problem.

Question 17

You control one insect in a rectangular maze-like environment with dimensions MxN, as shown in the figure above. The insect must reach a designated target location X, also known as the hive. There are no other insects moving around.

At each time step, the insect can move into an adjacent square if that square is currently free, or the insect may stay in its current location. Squares may be blocked by walls, but the map is known. Optimality is measured in terms of time steps; all actions have a cost of 1 regardless of whether the insect moves or stays put.

Note: your answer should reflect a general instance of the problem, not necessarily the example map shown.

What is the size of the state space in this problem?

max(M,N)

(MN) ²

M ^N

N ^M

MN

2 ^MN

Question 18

You control one insect in a rectangular maze-like environment with dimensions MxN, as shown in the figure above. The insect must reach a designated target location X, also known as the hive. There are no other insects moving around.

At each time step, the insect can move into an adjacent square if that square is currently free, or the insect may stay in its current location. Squares may be blocked by walls, but the map is known. Optimality is measured in terms of time steps; all actions have a cost of 1 regardless of whether the insect moves or stays put.

Note: your answer should reflect a general instance of the problem, not necessarily the example map shown.

Which of the following heuristics (if any) are admissible? Select all that apply.

Number of steps taken by the insect

Manhattan distance from the insect's location to the hive

Euclidean distance from the insect's location to the hive

parkerpectiong.blogspot.com

Source: https://plus.tuni.fi/data.ml.310/summer-2022/m02/classicalsearchquiz/

Share this post