Local and Online Search PDF

Local and online search Artificial intelligence Kristóf Karacs PPKE-ITK Recap n What is intelligence? n Agent model n Problem solving by search ¨ Non-informed search strategies ¨ Informed search strategies...

Local and online search Artificial intelligence Kristóf Karacs PPKE-ITK Recap n What is intelligence? n Agent model n Problem solving by search ¨ Non-informed search strategies ¨ Informed search strategies 1 Program n Problem solving by search n Search including other agents n Logic and inference n Search in logic representation, planning n Inference in case of constraints n Bayesian networks n Fuzzy logic n Machine learning Outline n Local search algorithms n Online search methods 2 Local search n Path to solution is irrelevant ¨ n-queens problem, circuit design, automatic layout of graphs n Global optimization problem ¨ State space: set of “complete” configurations n Advantages ¨ Low memory footprint ¨ Easy implementation ¨ Possibility of iterative improvement steps Local search algorithms n Discrete ¨ Hill climbing ¨ Random walk ¨ Simulated annealing ¨ Local beam search ¨ Genetic algorithms n Continuous ¨ Gradient 3 Hill climbing n Applicable when goal is to find resulting artefacts n e(): evaluation function, measures proximity n Algorithm ¨ Random initial state ¨ Improve e() in every step n Advantage ¨ Memory requirement: one state n Problems… Hill climbing problems 4 Variants of hill climbing n Steepest ascent n Sideways moves n Random restart n Stochastic ¨ probability of selection is proportional to the steepness of the surface n First-choice ¨ first state is chosen in a random follower state sequence that gives a better value Example – 8 queens problem n Hill Climbing: ¨ put queens on randomly ¨ e() = number of queen pairs attacking each other ¨ move a queen out of other’s way ¨ if it’s not possible, then throw queens on randomly again 5 Random walk n Randomly choose a step in an arbitrary direction n Lattice random walk n Gaussian random walk Simulated annealing n Overcomes local maxima problem n Random step ¨ If it improves, then do it! ¨ If not, then do it with probability prop. to e-DE/T(t) n T(t): cooling schedule ¨ T: thermic noise ¨ slow cooling ® global optimum ¨ From Random Walk to Stochastic Hill climbing n Question: acceptance probability 6 Local beam search n Take k parallel threads n Generate all follower states (N > k) n Choose the k best states n Influence between beams ¨ Ifone state generates several good successors, they all end up in the next iteration ¨ States generating bad successors are weeded out n Stochastic beam search Genetic algorithms n Population of individuals ¨ basic GA: binary strings n Goal: optimizing some function of the bit-strings n Evaluation: Fitness function n Start: random individuals n Operators ¨ Selection, crossover, mutation n Stop: based on fitness threshold 7 Operators in GAs [Dean, Allen, Aloimonos, AI: Theory and Practice, Benjamin Cummings, 1995] Cycle in GAs GX : current generation of N bitstrings (b0, b1, … bN-1) n For each bi, let pi = fitness(bi) / Σj fitness(bj). n GX+1 = Ø n For k = 0 ; k < N/2 ; k = k+1 ¨ Select: two parents each with probability P(parent = bi) = pi ¨ Crossover: randomly swap bits in the two parents to obtain two new bitstrings ¨ Mutation: for each bit in the new bitstrings, randomly invert it with some low probability ¨ Add the two new bitstrings to GX+1 8 Online search n Compute, act, observe n The agent only knows ¨ Actions (s) ¨ Step-cost function c(s,a,s’) ¨ Goal-test (s) n Competitive ratio = actual cost / cost of shortest path n Exploring in physical order (evident choice: DFS) ¨ Backtracking also has to take place in a physical manner ® actions have to be reversible ¨ Worst case: every node is expanded twice ¨ Solution: online iterative DFS Online local search n Hill climbing ¨ Already online ¨ Random restart version is not feasible (without teleportation) n Adding exploration ¨ Random walk ¨ LRTA*: Hill climbing with memory n H(s) : maintains best estimates of cost to goal for each node n Assumes lowest possible cost for unexplored nodes n Update H(s) through experience n Demo: http://www.youtube.com/watch?v=idNr7YhAUWM 9 Summary n Local search algorithms n Online search methods 10