Lecture 2 - State Space Search

Question 1

What are the 4 elements to represent the state space problem?

Answer 1

1. Initial State
    starting state
    ex. unsolved puzzle, being at home
2. Set of operators
    actions responsible for transition between states (up, down, etc)
3. Goal test function
    Applied to a state to determine if it is a goal state
    ex. solved puzzle, arrived at Concordia
4. Path cost function
    Assigns a cost to a path to tell if a path is preferable to
   another

Question 2

Informed vs Uninformed Search

Answer 2

Uninformed search
 We systematically explore the alternatives
 aka: systematic/exhaustive/blind/brute force search

Informed search (heuristic search)
 We try to choose smartly

Question 3

DFS vs BFS

Answer 3

Determine order for examining states
Depth-first:
 visit successors before siblings
- Uses Stack

Breadth-first:
visit siblings before successors
i.e. visit level-by-level
-Uses Queue

Question 4

Particularities of BFS:

Answer 4

• WIll always find shortest path
• Inneficient if there’s a high branching factor B
• High memory Requirement - B^n

Question 5

Particularities of DFS:

Answer 5

Does not guarantee finding the shortest path, but requires less memory

Question 6

What is Depth-Limited Search?

Answer 6

Compromise for DFS :
 Do depth-first but with depth cutoff k (depth at which nodes are not expanded)

Question 7

What is iterative Deepening?

Answer 7

Compromise between BFS and DFS:
 use depth-first search, but
 with a maximum depth before going to next level
-Finds the shortest path, and is preferred when there is a large search space

Question 8

Uniform Cost Search

Answer 8

• Uses a priority queue sorted using hte cost from the root to node n (g(n).
• This will find lowest cost solution path

Question 9

What is heuristic

Answer 9

 Heuristic search:
A technique that improves the efficiency of search,
possibly sacrificing on completeness
Focus on paths that seem most promising according to
some function
Need an evaluation function (heuristic function) to
score a node in the search tree

 Heuristic function h(n) = an approximation of the
lowest cost from node n to the goal

Question 10

What is Hill Climbing

Answer 10

General hill climbing strategy:
 as soon as you find a position that is better than the current one, select it.
 Does not maintain a list of next nodes to visit (an open list)
 Similar to climbing a mountain in the fog with amnesia … always go higher than where you are now,
but never go back…

Question 11

What is Steepest ascent Hill climbing?

Answer 11

Steepest ascent hill climbing:
 instead of moving to the first position that is better than the current one
 pick the best position out of all the next possible moves

Question 12

problems with hill climbing

Answer 12

Foothills (or local maxima)
 reached a local maximum, not the global maximum
 a state that is better than all its neighbors but is not better
than some other states farther away.
 at a local maximum, all moves appear to make things worse.

Plateau
 a flat area of the search space in which the next states
have the same value.
 it is not possible to determine the best direction in which
to move by making local comparisons.

Question 13

Some Solutions to hill-climbing

Answer 13

Random-restart hill-climbing
 random initial states are generated
 run each until it halts or makes no significant progress.
 the best result is then chosen.
keep going even if the best successor has the same value as current node
 works well on a “shoulder”
 but could lead to infinite loop
on a plateau

Question 14

What is best first search?

Answer 14

The thing about hill-climbing is that it selects one move and forgets the others.

Solution:
- Use open as a priority queue -> this is best first search.
- Insert nodes into an open list so that the nodes are sorted in ascending h(n)

Question 15

What is manhattan distance?

Answer 15

of moves required for a piece to be at the correct location

Question 16

What are the various variables in evaluating heuristics

Answer 16

Evaluation function f(n) = g(n) + h(n) for node n:
 g(n) current cost from start to node n
 h(n) estimate of the lowest cost from n to goal
 f(n) estimate of the lowest cost of the solution path (from start to goal passing through n)

Now consider f(n) = g(n) + h(n):
 g(n) cost of lowest cost path from start to node n
 h(n) actual lowest cost from n to goal
 f(n) actual cost of lowest cost of the solution path (from start to goal passing through n)

Question 17

The 3 different factors to evaluate a heuristic

Answer 17

1. Admissibility:
    “optimistic”
    never overestimates the actual cost of reaching the goal
    guarantees to find the lowest cost solution path to the goal (if it
   exists)
2. Monotonicity:
    “local admissibility”
    guarantees to find the lowest cost path to each state n encountered
   in the search
   A heuristic is monotonic if it always finds the optimal path to
   each state the 1st time it is encountered !
    guarantees to find the lowest cost path to each state n
   encountered in the search
3. Informedness:
    measure for the “quality” of a heuristic
    the more informed, the better
   More informed heuristics search smaller space to find the
   solution path

Question 18

Benefits of heuristics admissibility

Answer 18

• ## Guarantees to find the lowest cost SOLUTION PATH

Question 19

What is Algorithm A

Answer 19

Heuristics might be wrong:
 so search could continue down a wrong path
 Solution:
 Maintain depth/cost count, i.e., give preference to
shorter/least expensive paths
 Modified evaluation function f:
f(n) = g(n) + h(n)
 f(n) estimate of total cost along path through n
 g(n) actual cost of path from start to node n
 h(n) estimate of cost to reach goal from node n

Question 20

A* vs A Algorithm

Answer 20

Same as A, but for A*, h(n) must be asmissible, and will therefor guarantee lowest cost solution path