CH 3

Question 1

Problem Solving Agent

Answer 1

decides what to do by finding sequences of actions that lead to desirable states

Question 2

Uniformed

Answer 2

given no information about the problem other than its definition

Question 3

Informed

Answer 3

search algorithms that have some idea of where to look for solutions

Question 4

Goal Formulation

Answer 4

based on the current situation and the agent’s performance measure. is the first step in problem solving.

Question 5

Problem Formulation

Answer 5

which actions and states to consider given a goal

Question 6

Search Algorithm

Answer 6

takes a problem as input and returns a solution in the form of an action sequence (formulate. search. execute)

Question 7

Initial State

Answer 7

the state that the agent start in

Question 8

Successor Function

Answer 8

a description of possible actions available to the agent. The successor function. given a state. returns

Question 9

State Space

Answer 9

The initial state and the successor function implicitly define the state space (all possible states from the initial state)

Question 10

Goal Test

Answer 10

test which determines if a given state is the goal state

Question 11

Path Cost

Answer 11

assigns a numeric cost to each path

Question 12

Step Cost

Answer 12

the step cost of taking action a to go from state x to state y is denoted by c(x. a .y)

Question 13

Abstraction

Answer 13

process of removing detail from a representation is called abstraction

Question 14

n-puzzle

Answer 14

object is to reach a specified goal state such as the one shown on the right of the figure

Question 15

Route Finding Problem

Answer 15

is defined in terms of specified locations and transitions along links between them

Question 16

Touring Problem

Answer 16

visit every node (The Traveling Salesperson problem)

Question 17

Measuring Problem Solving Performance

Answer 17

completeness optimality time complexity space complexity

Question 18

Branching Factor

Answer 18

Maximum number of successors to any node

Question 19

Breadth-First Search

Answer 19

root node is expandd first then all the successors of the root node are expanded next and so on. Expands the shallowest unexpanded node

Question 20

Uniform Cost Search

Answer 20

Expands the node n with the lowest path cost (if all step costs are equal this is identical to a breadth-first search)

Question 21

alwaysDepth First Search

Answer 21

always expands the deepest node until the node has no successor

Question 22

Depth-Limited Search

Answer 22

same as depth first search but limit the maximum depth allowed (not useful unless the maximum possible depth can be determined)

Question 23

Iterative Deepening Depth First Search

Answer 23

depth first search but when all the nodes have been expanded and no solution found the depth limit is increased.

Question 24

Bidirectional Search

Answer 24

two simultaneous searches one from the initial state and from the goal state

Question 25

Sensorless Problems

Answer 25

if the agent has no sensors at all then it could be in one of several possible initial states and each action might therefore lead to one of several possible successor states

Question 26

Contingency Problems

Answer 26

if the environment is partially observable or if actions are uncertain then the agent’s percepts provide new information after each action. Each possible percept defines a contigency that must be planned for.

Question 27

Exploration Problems

Answer 27

when the states and actions of the environment are unknown the agent must act to discover them.