# 6.1. searchÂ¶

Some notes on search based on Berkeleyâ€™s CS 188 course and â€śArtificial Intelligenceâ€ť Russel & Norvig 3rd Edition.

## 6.1.1. Uninformed Search - R&N 3.1-3.4Â¶

### 6.1.1.1. problem-solving agentsÂ¶

*goal*- 1st step*problem*formulation - deciding what action and states to consider given a goal

*uninformed*- given no info about problem besides definitionan agent with several immediate options of unknown value can decide what to do first by examining future actions that lead to states of known value

5 components

initial state

actions at each state

transition model

goal states

path cost function

### 6.1.1.2. problemsÂ¶

toy problems

vacuum world

8-puzzle (type of sliding-block puzzle)

8-queens problem

Knuth conjecture

real-world problems

route-finding

TSP (and othe touring problems)

VLSI layout

robot navigation

automatic assembly sequencing

### 6.1.1.3. searching for solutionsÂ¶

start at a node and make a search tree

*frontier*=*open list*= set of all leaf nodes available for expansion at any given point*search strategy*determines which state to expand next

want to avoid redundant paths

TREE-SEARCH - continuously expand the frontier

GRAPH-SEARCH - tree search but also keep track of previously visited states in

*explored set*=*closed set*and donâ€™t revisit

### 6.1.1.4. infrastructureÂ¶

*node*- data structure that contains parent, state, path-cost, actionmetrics

*complete*- terminates in finite steps*optimal*- finds best solutiontime/space complexity

theoretical CS: \(\vert V\vert +\vert E\vert \)

b -

*branching factor*- max number of branches of any noded -

*depth*- number of steps from the rootm -

*max length*of any path in the search space

*search cost*- just time/memory*total cost*- search cost +*path cost*

### 6.1.1.5. uninformed search = blind searchÂ¶

bfs

*uniform-cost search*- always expand node with lowest path cost g(n)frontier is priority queue ordered by g

dfs

*backtracking search*- dfs but only one successor is generated at a time; each partially expanded node remembers which succesor to generate nextonly O(m) memory instead of O(bm)

*depth-limited search**diameter of state space*- longest possible distance to goal from any start

*iterative deepening dfs*- like bfs explores entire depth before moving on*iterative lengthening search*- instead of depth limit has path-cost limit

*bidirectional search*- search from start and goal and see if frontiers intersectjust because they intersect doesnâ€™t mean it was the shortest path

can be difficult to search backward from goal (ex. N-queens)

## 6.1.2. A* Search and Heuristics - R&N 3.5-3.6Â¶

### 6.1.2.1. informed searchÂ¶

*informed search*- use path costs \(g(n)\) and problem-specific heuristic \(h(n)\)has

*evaluation function**f*incorporating path cost*g*and heuristic*h**heuristic*h = estimated cost of cheapest path from state at node n to a goal state

*best-first*- choose nodes with best f*greedy best-first search*- let f = h: keep expanding node closest to goalwhen f=g, reduces to uniform-cost search

\(A^*\) search

\(f(n) = g(n) + h(n)\) represents the estimated cost of the cheapest solution through n

\(A^*\) (with tree search) is optimal and complete if h(n) is

*admissible*\(h(n)\) never overestimates the cost to reach the goal

\(A^*\) (with graph search) is optimal and complete if h(n) is

*consistent*(stronger than admissible) =*monotonicity*\(h(n) \leq cost(n \to n') + h(n')\)

can draw contours of f (because nondecreasing)

\(A^*\) is also

*optimally efficient*(guaranteed to expand fewest nodes) for any given consisten heuristic because any algorithm that that expands fewer nodes runs the risk of missing the optimal solutionfor a heuristic,

*absolute error*\(\delta := h^*-h\) and*relative error*\(\epsilon := \delta / h^*\)here \(h^*\) is actual cost of root to goal

bad when lots of solutions with small absolute error because it must try them all

bad because it must store all nodes in memory

memory-bounded heuristic search

*iterative-deepening*\(A^*\) - iterative deepening with cutoff f-cost*recursive best-first search*- like standard best-first search but with linear spaceeach node keeps f_limit variable which is best alternative path available from any ancestor

as it unwinds, each node is replaced with

*backed-up value*- best f-value of its childrendecides whether itâ€™s worth reexpanding subtree later

often flips between different good paths (h is usually less optimistic for nodes close to the goal)

\(SMA^*\) - simplified memory-bounded A* - best-first until memory is full then forgot worst leaf node and add new leaf

store forgotten leaf node info in its parent

on hard problems, too much time switching between nodes

agents can also learn to search with

*metalevel learning*

### 6.1.2.2. heuristic functionsÂ¶

*effective branching factor*\(b^*\) - if total nodes generated by A* is N and solution depth is d, then b* is branching factor for uniform tree of depth d for N+1 nodes: $\(N+1 = 1+b^* +(b^*)^2 + ... + (b^*)^d\)$want \(b^*\) close to 1

generally want bigger heuristic because everything with \(f(n) < C^*\) will be expanded

\(h_1\) dominates \(h_2\) if \(h_1(n) \geq h_2(n) \: \forall \: n\)

*relaxed problem*- removes constraints and adds edges to the graphsolution to original problem still solves relaxed problem

cost of optimal solution to a relaxed problem is an admissible heuristic for the original problem

also is consistent

when there are several good heuristics, pick \(h(n) = \max[h_1(n), ..., h_m(n)]\) for each node

*pattern database*- heuristic stores exact solution cost for every possible subproblem instance*disjoint pattern database*- break into independent possible subproblems

can learn heuristic by solving lots of problems using useful features

arenâ€™t necessarily admissible / consistent

## 6.1.3. Local Search - R&N 4.1-4.2Â¶

*local search*looks for solution not path ~ like optimizationmaintains only

*current node*and its neighbors

### 6.1.3.1. discrete spaceÂ¶

*hill-climbing*=*greedy local search*also stochastic hill climbing and random-restart hill climbing

*simulated annealing*- pick random moveif move better, then accept

otherwise accept with some probability pâ€™roportional to how bad it is and accept less as time goes on

*local beam search*- pick k starts, then choose the best k states from their neighbors*stochastic beam search*- pick best k with prob proportional to how good they are

*genetic algorithms*- population of k individualseach scored by

*fitness function*pairs are selected for

*reproduction*using*crossover point*each location subject to random

*mutation**schema*- substring in which some of the positions can be left unspecified (ex. \(246****\))want schema to be good representation because chunks tend to be passed on together

### 6.1.3.2. continuous spaceÂ¶

hill-climbing / simulated annealing still work

could just discretize neighborhood of each state

use gradient

if possible, solve \(\nabla f = 0\)

otherwise SGD \(x = x + \alpha \nabla f(x)\)

can estimate gradient by evaluating response to small increments

*line search*- repeatedly double \(\alpha\) until f starts to increase again*Newton-Raphson*methodfinds roots of func using 1st derive: \(x_\text{root} = x - g(x) / g'(x)\)

apply this on 1st deriv to get minimum

\(x = x - H_f^{-1} (x) \nabla f(x)\) where H is the Hessian of 2nd derivs

## 6.1.4. Constraint satisfaction problems - R&N 6.1-6.5Â¶

CSP

set of variables \(X_1, ..., X_n\)

set of domains \(D_1, ..., D_n\)

set of constraints \(C\) specifying allowable values

each state is an

*assignment*of variables*consistent*- doesnâ€™t violate constraints*complete*- every variable is assigned

*constraint graph*- nodes are variables and links connect any 2 variables that participate in a constraint*unary constraint*- restricts value of single variable*binary constraint**global constraint*- arbitrary number of variables (doesnâ€™t have to be all)

converting graphs to only binary constraints

every finite-domain constraint can be reduced to set of binary constraints w/ enough auxiliary variables

*dual graph*transformation - create a new graph with one variable for each constraint in the original graph and one binary constraint for each pair of original constraints that share variables

also can have

*preference constraints*instead of*absolute constraints*

### 6.1.4.1. inference (prunes search space before backtracking)Â¶

*node consistency*- prune domains violating unary constraints*arc consistency*- satisfy binary constraints (every node is made arc-consistent with all other nodes)uses AC-3 algorithm

set of all arcs = binary constraints

pick one and apply it

if things changed, re-add all the neighboring arcs to the set

\(O(cd^3)\) where \(d = \vert domain\vert \), c = ## arcs

variable can be

*generalized arc consistent*

*path consistency*- consider constraints on triplets - PC-2 algorithmextends to

*k-consistency*(although path consistency assumes binary constraint networks)*strongly k-consistent*- also (k-1) consistent, (k-2) consistent, â€¦ 1-consistentimplies \(O(k^2d)\)

establishing k-consistency time/space is exponential in k

global constraints can have more efficient algorithms

ex. assign different colors to everything

*resource constraint*=*atmost constraint*- sum of variable must not exceed some limit*bounds propagation*- make sure variables can be allotted to solve resource constraint

### 6.1.4.2. backtrackingÂ¶

CSPs are

*commutative*- order of choosing states doesnâ€™t matter*backtracking search*- depth-first search that chooses values for one variable at a time and backtracks when no legal values leftvariable and value ordering

*minimum-remaining-values*heuristic - assign variable with fewest choices*degree*heuristic - pick variable involved in largest number of constraints on other unassigned variables*least-constraining-value*heuristic - prefers value that rules out fewest choices for nieghboring variables

interleaving search and inference

*forward checking*- when we assign a variable in search, check arc-consistency on its neighbors*maintaining arc consistency (MAC)*- when we assign a variable, call AC-3, intializing with arcs to neighbors

intelligent backtracking - looking backward

keep track of

*conflict set*for each node (list of variable assignments that deleted things from its domain)*backjumping*- backtracks to most recent assignment in conflict settoo simple - forward checking makes this redundant

*conflict-directed backjumping*let \(X_j\) be current variable and \(conf(X_j)\) be conflict set. If every possible value for \(X_j\) fails, backjump to the most recent variable \(X_i\) in \(conf(X_j)\) and set \(conf(X_i) = conf(X_i) \cup conf(X_j) - X_i\)

*constraint learning*- findining minimum set of variables/values from conflict set that causes the problem =*no-good*

### 6.1.4.3. local search for cspsÂ¶

start with some assignment to variables

*min-conflicts*heuristic - change variable to minimize conflictscan escape plateaus with

*tabu search*- keep small list of visited statescould use

*constraint weighting*

### 6.1.4.4. structure of problemsÂ¶

connected components of constraint graph are independent subproblems

*tree*- any 2 variables are connected by only one path*directed arc consistency*- ordered variables \(X_i\), every \(X_i\) is consistent with each \(X_j\) for j>itree with n nodes can be made directed arc-consisten in \(O(n)\) steps - \(O(nd^2)\)

two ways to reduce constraint graphs to trees

assign variables so remaining variables form a tree

assigned variables called

*cycle cutset*with size c\(O[d^c \cdot (n-c) d^2]\)

finding smallest cutset is hard, but can use approximation called

*cutset conditioning*

*tree decomposition*- view each subproblem as a mega-variable

*tree width*w - size of largest subproblem - 1solvable in \(O(n d^{w+1})\)

also can look at structure in variable values

ex.

*value symmetry*- can assign different coloringsuse

*symmetry-breaking constraint*- assign colors in alphabetical order