```
Ch. 3 from Norvig

General idea of state space search,  with examples of famous search
problems.

Some data structures for search problems, including
state, parent node, operator applied, depth of node, cost so far.
Big issue: the FRAME PROBLEM:  what does NOT change when you perform
an operator?

SEARCH STRATEGY

Complete
Time Complexity (often exp.)
Space complexlty (possibly exp.)
Optimality

Must cause motion.
Should be systematic (e.g. DFS, BFS).

Forward vs. backward.

METHODS

BFS  Advantage: doesn't get caught in blind alley, ``depth-firsting''
into a problem.  E.g. looking up references to references, taking
courses to take courses....

current path.  So if you're good you don't examine much of the search
space, like the grandmaster.

Uniform cost (like  BFS but use cost, not depth)

Depth-Limited -- like DFS but backtrack if go beyond certain depth.
don't want a ridiculous length, like the total # nodes in a
path-finding problem.

Iterative Deepening --
Like maybe the diameter of the search space is upper bound.  But
may not know.  So try all depths in order.... downside is expanding
states several  times.  Can analyze the problem and it doesn't hurt
much... as you remember 1/2 the nodes of a binary tree are at the
lowest level, and the ratio gets better with higher branch factors.

Bidirectional Search --
Search from initial, back from goal.  In everyday life you often do
that when figuring out how to drive somewhere.  Downside: need to be
able to compute predecessors.  Lots of goals, use multiple-state
search, as when the state of the world is inaccessible until you
take some action.

Avoid repeated states!  Don't go back where you came from, detect and
avoid cycles, or don't even generate a state you've generated
before...  remember your past (hash table?).

Constraint Satisfaction Search.
states are a set of variables,  goal is a set of constraints
(e.g. cryptarithmetic, 8 queens).  Operators assign values (subject
to constraints), goal test checks the answer.  DFS OK since we have
a max. depth dictated by number of variables.

Backtracking Search checks violations as we go, and quits that path
before assigning all variables.  This generalizes to lots of DFS
algorithms.  Forward-checking eliminates states rendered impossible by
current configuration.   Constraint Propagation progressively
eliminates future choices.

From Rich

Production Systems: lots to say.  Situation-Action rules,
corresponding to operators.  Theories of development, learning,
expert systems.  Problems: structure (hierarchical), rule conflicts,
multiple rules apply.

Set of rules  (LHS --> RHS in a forward system).
Databases, permanent or temporary (per/problem), which stores the
state of the world or the facts used in deciding whether a LHS applies
Control strategy
Rule applier

Expert Systems Shells
SOAR and general meta-methodology.
Hope is you get surprising intelligent emergent behavior, but in fact
usually you fix it so there are no surprises since they are usually

Heuristic Search:
E.g. greedy approach to TSP: check out the closest next city, or the
one that might have many direct connections, or whatever.  Great
idea, often non- systematic.  Put your knights out, don't get queen
out too early, control center of board, etc. etc.

Heuristic Function maps states to ``goodness'', which should correlate
with likelihood that that state leads to solution:  We'll see this
again, but you might give points to a move in chess as above, or count
1 in tic-tac-toe if you have  a marker and could win that row,
2 for two in a row unblocked, etc.

Problem Characteristics:

Decomposable into smaller instances (integration, not block
stacking... subgoal interaction motivates PLANNING).
AND-OR graphs... decompose the ANDS and search the ORs as normal, but
need to be careful (see below).

Can steps be undone or not? (Ignorable: Theorem proving, just generate truths
until the right one pops out.  Recoverable: In 8-puzzle, once slide a block and
decide that's wrong, have to do work to unslide it. Unrecoverable:
chess, Quatro!).

Is universe predictable or are there unknowns?  (8-puzzle vs. bridge).
Robot arm control is unpredictable, legal advice,...

Is good solution obvious without comparison to ALL other solutions?
Theorem proving can give longer proof (but so what?).  TSP, how
guarantee shortest (exp. we think).  Best-path harder than any-path!

Is the desired solution a particular state, or the path to the state,
or both (costs?).

``The bank president ate a dish of pasta with the fork.''
How interpret ``bank'', financial institution or river bank?
Knowledge helps, as does knowing you don't eat dishes, pasta salad
has pasta but dog food doesn't have dogs, with the fork modifies eat
but could have been ``with vegetables''.  So structure depends on
constraints.   So need search, but the answer is one parse.

But in jugs problem, you want the PATH to the solution, not just the

Is knowledge absolutely required, or important only to constrain
search?

Playing chess, very little knowledge.

Scanning a newspaper to see if it supports Democrats or Republicans...
need lots of world knowledge.

Can computer do it alone or must it interact with human?
Proving theorems vs. medical diagnosis, say...want to know ``why'' a
particular conclusion.

HEURISTIC SEARCH TECHNIQUES

Generate and Test:  generate a state, if goal quit, else iterate.
it's DFS procedure: implement with DFS and backtracking.  Good for
simple problems.  Add heuristics for better performance.

Hill Climbing:  Uses heuristic function,
generate a state better than the current one next.

Steepest-Ascent: (gradient search).  Famous from mathematics.
generate the most-promising state next.
Problems for ALL this (NNs, optimization programs, everyone!)
Plateaus where nothing seems to improve you,
Ridges
Local Maximum

So:  Genetic algorithms, simulated annealing, variable step size,
infinite lore here.

Local vs. global heuristic functions.   In block stacking,
Start (AHGFEDCB, want HGFEDCBA).
Local:    +1 for every block resting on thing it is supposed to, -1
if not.
Global: if complete structure under block is OK, +1 for every block
in the support structure.  for each block with incorrect support
structure, -1 for every block in existing structure.

Best-First Search:  for OR graphs...
Combines DFS, BFS:  follow single path but switch when some
competing path looks better.  Need heuristic function.

AND-OR Graphs:
Need to extend best-first to deal with ANDs correctly.... each AND
arc leads to its own goal state.

To be continued...

```