FOL resolution strategiesResolution in FOL via searchResolution strategiesResolution strategies…SubsumptionSearch ISlide 8Slide 9Slide 10Slide 11Slide 12Data type nodeSlide 14Slide 15Goodness of a search strategyUninformed vs. informed searchBreadth-First SearchBreadth-First Search …Uniform-Cost SearchDepth-First SearchDepth-Limited SearchIterative Deepening SearchSlide 24Slide 25Slide 26Bi-Directional SearchBi-Directional Search …Time, Space, Optimal, Complete?Avoiding repeated statesFOL resolution strategiesTuomas SandholmCarnegie Mellon UniversityComputer Science Department[Finish reading Russell & Norvig Chapter 9 if you haven’t yet]Resolution in FOL via search•Resolution can be viewed as the bottom-up construction (using search) of a proof tree•Search strategy prescribes –which pair of sentences to pick for resolution at each point, and –which clause to unify from those sentencesResolution strategies•Strategy is complete if it is guaranteed to find the empty clause whenever it is entailed•Level 0 clauses are the original ones. Level k clauses are the resolvents of two clauses, one of which is from level k-1 and the other from an earlier level•Breadth-first–Compute all level 1 clauses, then level 2 clauses…–Complete, but inefficient•Set-of-support–At least one parent clause must be from the negation of the goal or one of the descendants of such a goal clause–Complete (assuming all possible set-of-support clauses are derived)Resolution strategies…•Unit resolution–At least one parent clause must be a unit clause, i.e., contain a single literal–Not complete (but complete for Horn clause KBs)–Unit preference speeds up resolution drastically in practice•Input resolution–At least one parent from the set of original clauses (axioms and negation of goal)–Not complete (but complete for Horn clause KBs)•Linear resolution (generalization of input resolution)–Allow P and Q to be resolved together if P is in the original KB or P is an ancestor of Q in the proof tree–Complete for FOLSubsumption•Eliminate more specific sentences than existing ones•E.g., if P(x) is in KB, then do not add P(A) or P(A) V Q(B)Search ITuomas SandholmCarnegie Mellon UniversityComputer Science Department[Read Russell & Norvig Sections 3.1-3.4. (Also read Chapters 1 and 2 if you haven’t already.)]Search IGoal-based agent (problem solving agent)Goal formulation (from preferences). Romania example, (Arad  Bucharest)Problem formulation: deciding what actions & state to consider.E.g. not “move leg 2 degrees right.”No map vs. Mapphysical deliberative search searchSearch I“Formulate, Search, Execute” (sometimes interleave search & execution)For now we assume full observability, i.e., known stateknown effects of actionsData type problem Initial state (perhaps an abstract characterization) vs. partial observability (set)OperatorsGoal-test (maybe many goals)Path-cost-functionKnowledge representationMutilated chess board exampleCan make huge speed difference in integer programming, e.g., edge versus cycle formulation in kidney exchangeSearch IExample problems demonstrated in terms of the problem definition.I. 8-puzzle (general class is NP-complete)How to model operators? (moving tiles vs. blank) Path cost = 1Search III. 8-queens (actually, even the general class with n queens happens to have an efficient solution, so search would not be the method of choice) path cost = 0: in this application we are interested in a node, not a pathIncremental formulation: (constructive search)States: any arrangement of 0 to 8 queens on boardOps: add a queen to any square# sequences = 648Improved incremental formulation:States: any arrangement of 0 to 8 queens on board with none attackedOps: place a queen in the left-most empty column s.t. it is not attacked by any other queen# sequences = 2057Complete State formulation: (iterative improvement)States: arrangement of 8 queens, 1 in each columnOps: move any attacked queen to another square in the same columnAlmost a solution to the 8-queen problem:Search IIII. Rubik’ cube ~ 1019 statesIV. Crypt arithmetic FORTY 29786+ TEN + 850+ TEN + 850SIXTY 31486V. Real world problems 1. Routing (robots, vehicles, salesman) 2. Scheduling & sequencing 3. Layout (VLSI, Advertisement, Mobile phone link stations) 4. Winner determination in combinatorial auctions 5. Which combination of cycles to accept in kidney exchange?…Data type node • State• Parent-node• Operator• Depth• Path-costFringe = frontier = open list (as queue)Goodness of a search strategy•Completeness•Time complexity•Space complexity•Optimality of the solution found (path cost = domain cost)•Total cost = domain cost + search costsearch costUninformed vs. informed searchCan only distinguish goal states from non-goal stateBreadth-First Searchfunction BREADTH-FIRST-SEARCH (problem) returns a solution or failure return GENERAL-SEARCH (problem, ENQUEUE-AT-END)Breadth-first search tree after 0,1,2 and 3 node expansionsBreadth-First Search …Max 1 + b + b2 + … + bd nodes (d is the depth of the shallowest goal)- Complete- Exponential time & memory O(bd)- Finds optimum if path-cost is a non-decreasing function of the depth of the node.Uniform-Cost SearchInsert nodes onto open list in ascending order of g(h).Finds optimum if the cost of a path never decreases as we go along the path. g(SUCCESSORS(n))  g(n)<= Operator costs  0If this does not hold, nothing but an exhaustive search will find the optimal solution.G inserted into open list although it is a goal state. Otherwise cheapest path to a goal may not be found.Depth-First Searchfunction DEPTH-FIRST-SEARCH (problem) returns a solution or failure GENERAL-SEARCH (problem, ENQUEUE-AT-FRONT)•Time O(bm) (m is the max depth in the space)•Space O(bm) !•Not complete (m may be )•E.g. grid search in one direction•Not optimalAlternatively can use a recursive implementation.Depth-Limited Search- Depth limit in the algorithm, or - Operators that incorporate a depth limitL = depth limitComplete if L  d (d is the depth of the shallowest goal)Not optimal (even if one continues the search after the first solution has been found, because an optimal solution may not be within the depth limit L)O(bL) timeO(bL) spaceDiameter of a search spaceIterative Deepening SearchIterative Deepening SearchComplete,