LPG: Local search for Planning Graphs Seung H. Chung 16.412J Cognitive Robotics 2 Outline ? ? ? ? ? Stochastic Local Search and Temporal Action Graphs”, to appear in Journal of Artificial Intelligence Research (JAIR). Temporal Action Graph Walksat: Stochastic Local Search Better Neighbor Relaxed Plan A. Gerevini, A. Saetti, I. Serina “Planning through 3 Overview ? resources to the planning description: Planning Domain Definition Language (PDDL) 2.1 ? – plan graph, but adds temporal representation – – to FF ? the time and metric resource domains (3 rd IPC) 4 INIT Level 1 Level 2 Level 3 Level 4 Linear Action Graph (LA-graph) f 1 f 2 f 3 f 4 f 5 no-op f 6 f 3 f 4 f 5 f 6 f 9 f 5 f 6 f 12 f 5 f 13 f 12 f 5 no-op no-op no-op no-op no-op a 1 no-op no-op f 7 f 7 f 7 no-op no-op a 4 f 10 a 2 no-opa 3 One action per layer Uses Strips-like operator but adds time and metric Features: Uses Temporal Action graphs (TA-graphs): Similar to a Uses stochastic local search: Similar to Walksat Uses relaxed plan for heuristic to guide the search: similar LPG outperformed all general purpose planners in 5 INIT Level 1 Level 2 Level 3 Level 4 Temporal Action Graph (TA-Graph) f 1 f 2 f 3 f 4 f 5 no-op f 6 f 3 f 4 f 5 f 6 f 9 f 5 f 6 f 12 f 5 f 13 f 12 f 5 no-op no-op no-op no-op no-op a 1 no-op no-op f 7 f 7 f 7 no-op no-op a 4 f 10 a 2 no-opa 3 0 0 0 0 0 [50] 50 [70] 120 [100] 220 [40] 160 50 50 50 (–) (–) (–) (–) 50 160 160220 2200 220 120 Inconsistent precondition 6 INIT Level 1 Level 2 Level 3 Level 4 Ordering Constraint f 1 f 2 f 3 f 4 f 5 no-op f 6 f 3 f 4 f 5 f 6 f 9 f 5 f 6 f 12 f 5 f 13 f 12 f 5 no-op no-op no-op no-op no-op a 1 no-op no-op f 7 f 7 f 7 no-op no-op a 4 f 10 a 2 no-opa 3 0 0 0 0 0 [50] 50 [70] 120 [100] 220 [40] 160 50 50 50 (–) (–) (–) (–) 50 160 160220 2200 220 120 Causal Constraint ?a 1 < a 4 ?a 2 < a 3 Exclusive Constraints ?a 1 < a 2 ?a 2 < a 3 ?a 2 < a 4 7 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? 9 Better Neighbor? ? A’∈ N(σ,A) resolves the inconsistency σ by inserting or deleting an action. ? E(a) = E(a) i = α?Execution_cost (a) i + β?Temporal_cost(a) i + γ?Search_cost(a) i E(a) r = α?Execution_cost (a) r + β?Temporal_cost(a) r + γ?Search_cost(a) r 10 Relaxed Plan ? ? – – – ? ? End_time(EvalAdd(a)) ? – unsupported due to removal of a – actions – ? ? End_time(EvalDel(a)) A neighbor Use evaluation function E(a) Idea: Don’t consider the mutex relation and perform reachability analysis. Insert action a Find all actions that is required to support the preconditions of a Compute the maximum time duration required for all actions Return: Set of actions added: Aset(EvalAdd(a)) Max time duration of the actions: Remove action a Find all actions that is required to support all preconditions that were Compute the maximum time duration required for all newly inserted Return: Set of actions added: Aset(EvalDel(a)) Max time duration of the actions: 11 Better Neighbor ? ? Execution_cost (a) i = Σ a’∈Aset(EvalAdd(a)) Cost(a’) Temporal_cost(a) i = End_time(EvalAdd(a)) Search_cost(a) i = |Aset(EvalAdd(a))| + Σ a’∈Aset(EvalAdd(a)) Threats(a’) Execution_cost (a) r = Σ a’∈ )) Cost(a’) Temporal_cost(a) r = End_time(EvalAdd(a)) Search_cost(a) r = |Aset(EvalAdd(a))| + Σ a’∈ )) Threats(a’) 12 Advantages and Disadvantages – – – – – – Insert an action Remove an action Aset(EvalDel(a Aset(EvalDel(a ?Pros One of the fastest domain-independent planners Relatively expressive domain description languages Can easily be extended to be anytime algorithm ?Cons Algorithm is not guaranteed to be complete No guarantee on the quality of the plan Does not allow flexible time bounds