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...