search

Some notes on search based on Berkeley’s CS 188 course and “Artificial Intelligence” Russel & Norvig 3rd Edition.

# Uninformed Search - R&N 3.1-3.4

## 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 definition
• an 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
1. initial state
2. actions at each state
3. transition model
4. goal states
5. path cost function

## problems

• toy problems
1. vacuum world
2. 8-puzzle (type of sliding-block puzzle)
3. 8-queens problem
4. Knuth conjecture
• real-world problems
1. route-finding
2. TSP (and othe touring problems)
3. VLSI layout
5. automatic assembly sequencing

## 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
1. TREE-SEARCH - continuously expand the frontier
2. GRAPH-SEARCH - tree search but also keep track of previously visited states in explored set = closed set and don’t revisit

## infrastructure

• node - data structure that contains parent, state, path-cost, action
• metrics
• complete - terminates in finite steps
• optimal - finds best solution
• time/space complexity
• theoretical CS: $\vert V\vert +\vert E\vert$
• b - branching factor - max number of branches of any node
• d - depth - number of steps from the root
• m - max length of any path in the search space
• search cost - just time/memory
• total cost - search cost + path cost
• • 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 next
• only 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 intersect
• just because they intersect doesn’t mean it was the shortest path
• can be difficult to search backward from goal (ex. N-queens)

# A* Search and Heuristics - R&N 3.5-3.6

• 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 goal
• when 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 solution
• for 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 space
• each 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 children
• decides 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

## 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 graph
• solution 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

# Local Search - R&N 4.1-4.2

• local search looks for solution not path ~ like optimization
• maintains only current node and its neighbors

## discrete space

• hill-climbing = greedy local search
• also stochastic hill climbing and random-restart hill climbing
• simulated annealing - pick random move
• if 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 individuals
• each 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

## continuous space

• hill-climbing / simulated annealing still work
• could just discretize neighborhood of each state
• 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 method
• finds 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

# Constraint satisfaction problems - R&N 6.1-6.5

• CSP
1. set of variables $X_1, …, X_n$
2. set of domains $D_1, …, D_n$
3. 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

## 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 algorithm
• extends to k-consistency (although path consistency assumes binary constraint networks)
• strongly k-consistent - also (k-1) consistent, (k-2) consistent, … 1-consistent
• implies $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

## 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 left
1. variable 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
2. 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
3. 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 set
• too 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

## local search for csps

• min-conflicts heuristic - change variable to minimize conflicts
• can escape plateaus with tabu search - keep small list of visited states
• could use constraint weighting

## 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>i
• tree with n nodes can be made directed arc-consisten in $O(n)$ steps - $O(nd^2)$
• two ways to reduce constraint graphs to trees
1. 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
2. tree decomposition - view each subproblem as a mega-variable
• tree width w - size of largest subproblem - 1
• solvable in $O(n d^{w+1})$
• also can look at structure in variable values
• ex. value symmetry - can assign different colorings
• use symmetry-breaking constraint - assign colors in alphabetical order