Local Beam Search

Keep track of k states instead of one Initially: k random states Next: determine all successors of k states If any of successors is goal, then finished Else select k best from successors and repeat Major difference with k random-restart search - Information is shared among k search threads Can suffer from lack of diversity Stochastic variant: choose k successors at random, with the probability of choosing a given successor being an increasing function of its value