Wk 2-3 (Ch 3/4) : Solving Problems by Searching

Question 1

Why does the contour map for uniform cost look like a circle while A*’s contour map looks like something else?

Answer 1

[INSERT]

Question 2

What does the contour map for A* look like, why?

Answer 2

[INSERT]

Question 3

What is the definition of completeness? What is the definition of admissible?

Answer 3

[INSERT]

Question 4

Describe the concept of pruning?

Answer 4

[INSERT]

Question 5

What are the strengths and drawbacks of A*?

Answer 5

[INSERT]

Question 6

What is relative error? What is absolute error?

Answer 6

[INSERT]

Question 7

What does it mean for A* to be optimally efficient?

Answer 7

[INSERT]

Question 8

Describe A* algorithm…see notecard.

Answer 8

[INSERT]

Question 9

Which types of A* are optimal, when?

Answer 9

[INSERT]

Question 10

Describe the greedy best-first search algorithm

Answer 10

[INSERT]

Question 11

What is the basic improvement that informed searches add over uninformed searches?

Answer 11

[INSERT]

Question 12

What is the main difference between IDA* and the std ID algorithm? What are its main drawbacks?

Answer 12

[INSERT]

Question 13

How does recursive best-first search work? What are its strengths? What are its drawbacks?

Answer 13

[INSERT]

Question 14

How do admissibility and monotonicity make algorithms optimal?

Answer 14

[INSERT]

Question 15

How does SMA work? How does thrashing relate to it? How does it improve on A*? How does it use memory?

Answer 15

[INSERT]

Question 16

Explain the statement….memory limitations can make a problem intractable from the point of view of computation time….

Answer 16

[INSERT]

Question 17

What is metalevel learning? What is a metalevel state space? object-level state space? metalevel learning? How does this improve search?

Answer 17

[INSERT]

Question 18

When would I want to use tree search vs. graph search?

Answer 18

[INSERT]

Question 19

What is effective branching factor? How does it relate to the effectiveness of a heuristic?

Answer 19

[INSERT]

Question 20

Explain the statement “ the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem”

Answer 20

[INSERT]

Question 21

Explain triangle inequality and how it relates to a heuristic being consistent.

Answer 21

[INSERT]

Question 22

What is a composite heuristic, when and how would you use it?

Answer 22

[INSERT]

Question 23

How does a pattern database work?

Answer 23

[INSERT]

Question 24

How does a disjoint database improve even further on pattern databases?

Answer 24

[INSERT]

Question 25

How do features help inductive learning methods? How are these constructed to create faster algorithms?

Answer 25

[INSERT]

Question 26

What environments do we use “beyond-classical” search to solve problems?

Answer 26

Classical search, apparently, has worked well in observable, deterministic, and discrete environments. [INSERT]

Question 27

Explain the hill-climbing search method.

Answer 27

.

Question 28

What is simulated annealing? How does it relate to the hill-climbing search method?

Answer 28

.

Question 29

What is a complete state formulation? How is it relevant to hill climbing?

Answer 29

.

Question 30

How is goal formulation related to problem formulation?

Answer 30

In goal formation, we’re talking about the parts of the world we’re interested in, what we can abstract away, and what should be included. Must come before problem formulation or we have no idea what we’re including and whether we’re even in near or far from the goal. In practice, they go back an forth in their definitions and implementations.

Question 31

What is a well defined problem?

Answer 31

assuming that reaching a goal is a series of fixed actions, we can search through all those actions to find the sequence of actions that ends in the goal state…..

So, we have an initial state,
the set of possible actions
the transition model that takes states to other states based on those actions.
A path which is the sequence of states connected by sequence of actions that ends in a goal, as verified by a goal test.

The cost function exists as well which says how much each action penalizes us.

Question 32

Define state space

Answer 32

the initial state, actions and transition model.

Question 33

what are the things we can legitimately abstract away from a problem?

Answer 33

things that for the set of all possible states, they all either have or dont have this thing I’m taking away.

Question 34

how can state space be different than physical space?

Answer 34

even if the problem I’m solving may be over physical space, the state space is the collection of all possible representations of the part of the problem that matters. The distance between jets in the intercept….may not take into account the actual physical space of the merge, etc. (or consider the 2 friends meeting in a city problem)

Question 35

what are parts of problem formulation

Answer 35

initial state
goal test
successor function
cost function
state space.

Question 36

whats the book definition of state?

State space?

Answer 36

A state is a situation that an agent can find itself in. We distinguish two types of states:
world states (the actual concrete situations in the real world) and representational states (the
abstract descriptions of the real world that are used by the agent in deliberating about what to
do).

A state space is a graph whose nodes are the set of all states, and whose links are
actions that transform one state into another

Question 37

What is the book definition of transition model? branching factor? search tree

Answer 37

The branching factor in a search tree is the number of actions available to the agent.

A search tree is a tree (a graph with no undirected loops) in which the root node is the
start state and the set of children for each node consists of the states reachable by taking any
action.
A search node is a node in the search tree.
A goal is a state that the agent is trying to reach.
An action is something that the agent can choose to do.

Question 38

Mathematcially describe the successor function?

Answer 38

A successor function described the agent’s options: given a state, it returns a set of
(action, state) pairs, where each state is the state reachable by taking the action.

Question 39

What’s the difference betwen a world state, a state description, and a search node? Why is this distinction important?

Answer 39

world state is how reality is or could be. In one world state we’re in Arad, in another
we’re in Bucharest. The world state also includes which street we’re on, what’s currently on
the radio, and the price of tea in China. A state description is an agent’s internal description
of a world state. Examples are In(Arad) and In(Bucharest). These descriptions are
necessarily approximate, recording only some aspect of the state.
We need to distinguish between world states and state descriptions because state description
are lossy abstractions of the world state,

because the agent could be mistaken about how the world is, because the agent might want to imagine things that aren’t true but it could
make true, and because the agent cares about the world not its internal representation of it.

Search nodes are generated during search, representing a state the search process knows
how to reach. They contain additional information aside from the state description, such as
the sequence of actions used to reach this state. This distinction is useful because we may
generate different search nodes which have the same state, and because search nodes contain
more information than a state representation.