Walkplan: Stochastic Local Search Walkplan(Il, max steps, max restarts, p) II: Planning problem description max steps: Maximum number of search max restarts Maximum number of restart p: Noise factor Solution TA-graph ea With probability p use stochastic local search to find a plan Search the plan space max steps number of times If no plan is found, try restarting the search from the beginning up to max restarts number of time Walkplan Algorithm Walkplan(l, max steps, max restarts, p) for i =1 to max restarts de A= an initial TA-graph derived from n Set of TA-graphs in which an action for 3 =1 to max steps do was inserted or fa is solution then return A removed to o= an inconsistency in A resolve the N(o, A)= neighborhood of A for o inconsistency if彐A′∈N(o,A) such that A′ is no worse than a then else if random p then A=A′∈N(,A) A= best A′∈N(σ,A) What is a better neighbor? return fail7 Walkplan: Stochastic Local Search • Walkplan(Π,max_steps,max_restarts,p) – Input • Π : Planning problem description • max_steps : Maximum number of search • max_restarts : Maximum number of restart • p : Noise factor – Output • Solution TA-graph • Idea: – With probability p use stochastic local search to find a plan – Search the plan space max_steps number of times – If no plan is found, try restarting the search from the beginning up to max_restarts number of time 8 Walkplan Algorithm Walkplan(Π,max_steps,max_restarts,p) for i = 1 to max_restarts do A = an initial TA-graph derived from Π for j = 1 to max_steps do if A is solution then return A σ = an inconsistency in A N(σ,A) = neighborhood of A for σ if ∃A’∈ N(σ,A) such that A’ is no worse than A then A = A’ else if random < p then A = A’∈ N(σ,A) else A = best A’∈ N(σ,A) return fail Set of TA-graphs in which an action was inserted or removed to resolve the inconsistency What is a better neighbor? What is a better neighbor?