A Increasing Cost Infeasible Feasible 3/17/2004 opyright Brian Williams, 2002 A米 Search: Search Tree Problem: State Space Search Problem Initial State Expand(node) Children of search node next states Goal-Test(node True if search node at a goal-stat Admissible Heuristic-Optimistic cost to go Search node: Node in the search tree State State the search is at Parent Parent in search tree copyright Brian Williams, 2002
3/17/2004 copyright Brian Williams, 2002 11 Increasing Cost Feasible Infeasible A* 3/17/2004 copyright Brian Williams, 2002 12 A* Search: Search Tree Problem: State Space Search Problem Θ Initial State Expand(node) Children of Search Node = next states Goal-Test(node) True if search node at a goal-state h Admissible Heuristic -Optimistic cost to go Search Node: Node in the search tree State State the search is at Parent Parent in search tree ds search node to those to be expanded
A Search State of search Problem: State Space Search Problem Initial State Expand(node) Children of Search Node adjacent states Goal-Test(node) True if search node at a goal-state Nodes Search Nodes to be expanded Expanded Search Nodes already expanded Initialize Search starts at e, with no expanded nodes Admissible Heuristic-Optimistic cost to go Search node: Node in the search tree State State the search is at Parent Parent in search tree Nodes[Problem] Remove-Best(f) Removes best cost node according to f Enqueue(new-node, f) Adds search node to those to be expanded 3/17/2004 copyright Brian Williams, 2002 A米 Search Function A*(problem, h) returns the best solution or failure Problem pre-initialized f(×)←- pRoblem](x)+h(x) loop do xpand if Nodes[ problem] is empty then return failure best first node <Remove-Best(Nodes[problem], f) state← State(node) remove any n from Nodes[problem] such that State(n)=state Expanded[problem]<Expanded [problem]u(state) new-nodes <Expand(node, problem) for each new-node in new-nodes unless State (new-node)is in Expanded[problem] then Nodes[problem]< Enqueue(Nodes[], new-node, if Goal-Test[problem] applied to State(node) succeeds then return node end 3/17/2004 copyright Brian Williams, 2002
3/17/2004 copyright Brian Williams, 2002 13 A* Search: State of Search Problem: State Space Search Problem Θ Initial State Expand(node) Children of Search Node = adjacent states Goal-Test(node) True if search node at a goal-state Nodes Search Nodes to be expanded Expanded Search Nodes already expanded Initialize Search starts at Θ, with no expanded nodes h Admissible Heuristic -Optimistic cost to go Search Node: Node in the search tree State State the search is at Parent Parent in search tree Nodes[Problem]: Remove-Best(f) Removes best cost node according to f Enqueue(new-node, f ) Adds search node to those to be expanded 3/17/2004 copyright Brian Williams, 2002 14 A* Search Function A*(problem, h) returns the best solution or failure. Problem pre-initialized. f(x) ← g[problem](x) + h(x) loop do if Nodes[problem] is empty then return failure node ← Remove-Best(Nodes[problem], f) state ← State(node) remove any n from Nodes[problem] such that State(n) = state Expanded[problem] ← Expanded[problem] ∪ {state} new-nodes ← Expand(node, problem) for each new-node in new-nodes unless State(new-node) is in Expanded[problem] then Nodes[problem] ← Enqueue(Nodes[problem], new-node, f ) if Goal-Test[problem] applied to State(node) succeeds then return node end Expand best first
A Search Function A*(problem, h) returns the best solution or failure Problem pre-initialized f(×)←- problem](x)+h(x) op Terminates if Nodes[problem] is empty then return failure when node < Remove-Best(Nodes[problem], f) state←- State(noe) remove any n from Nodes[problem] such that State(n )= state Expanded[problem]<Expanded[problem]u(state) new-nodes < Expand(node, problem) for each new-node in new-nodes unless State (new-node) is in Expanded[problem then Nodes[problem]<Enqueue(Nodes[problem], new-node, if Goal-Testiproblem] applied to state(node) succeeds then return node end 3/17/2004 copyright Brian Williams, 2002 A米 Search Function A*(problem, h) returns the best solution or failure Problem pre-initialized f(×)←- pRoblem](x)+h(x) Dynamic loop do if Nodes[ problem] is empty then return failure Programming node +Remove-Best(Nodes[problem f) Principle state← State( node) remove any n from Nodes[problem] such that State(n)= state Expanded[problem]<Expanded[problem]u(state) new-nodes <Expand(node, problem) for each new-node in new-nodes unless State(new-node)is in Expanded [problem] then Nodes[problem]<Enqueue(Nodes[problem], new-node, if Goal-Test[problem] applied to State(node) succeeds then return node end 3/17/2004 copyright Brian Williams, 2002
3/17/2004 copyright Brian Williams, 2002 15 A* Search Function A*(problem, h) returns the best solution or failure. Problem pre-initialized. f(x) ← g[problem](x) + h(x) loop do if Nodes[problem] is empty then return failure node ← Remove-Best(Nodes[problem], f) state ← State(node) remove any n from Nodes[problem] such that State(n) = state Expanded[problem] ← Expanded[problem] ∪ {state} new-nodes ← Expand(node, problem) for each new-node in new-nodes unless State(new-node) is in Expanded[problem] then Nodes[problem] ← Enqueue(Nodes[problem], new-node, f ) if Goal-Test[problem] applied to State(node) succeeds then return node end Terminates when . . . 3/17/2004 copyright Brian Williams, 2002 16 A* Search Function A*(problem, h) returns the best solution or failure. Problem pre-initialized. f(x) ← g[problem](x) + h(x) loop do if Nodes[problem] is empty then return failure node ← Remove-Best(Nodes[problem], f) state ← State(node) remove any n from Nodes[problem] such that State(n) = state Expanded[problem] ← Expanded[problem] ∪ {state} new-nodes ← Expand(node, problem) for each new-node in new-nodes unless State(new-node) is in Expanded[problem] then Nodes[problem] ← Enqueue(Nodes[problem], new-node, f ) if Goal-Test[problem] applied to State(node) succeeds then return node end Dynamic Programming Principle . .
Outline Optimal csPs Review of a Conflict-directed A Generating the Best Kernel Intelligent Tree Expansion Extending to Multiple Solutions Performance Comparison 3/17/2004 copyright Brian Williams, 2002 Conflict-directed A* Increasing Cost Infeasible Feasible copyright Brian Williams, 2002
3/17/2004 copyright Brian Williams, 2002 17 Outline • Optimal CSPs Review of A* Conflict-directed A* Generating the Best Kernel Intelligent Tree Expansion Extending to Multiple Solutions Performance Comparison 3/17/2004 copyright Brian Williams, 2002 18 Increasing Cost Feasible Infeasible Conflict-directed A*
Conflict-directed A* Increasing Cost Conflict 1 Infeasible Feasible 3/17/2004 opyright Brian Williams, 2002 Conflict-directed A* Increasing Cost ○○O Conflict 1 Infeasible Feasible copyright Brian Williams, 2002
3/17/2004 copyright Brian Williams, 2002 19 Increasing Cost Feasible Infeasible Conflict 1 Conflict-directed A* 3/17/2004 copyright Brian Williams, 2002 20 Increasing Cost Feasible Infeasible Conflict 1 Conflict-directed A*