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....
  
  DFS  (loops, progress, dead-ends).  Advantage: only keeps nodes on
  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
  
  There are commercial ones like OPS5 you can download.
   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
   bad.
  
  
  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
  final answer (!!).
  
  
  
  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...