11OptimizationBurr H. SettlesCS-540, UW-Madisonwww.cs.wisc.edu/~cs540-1Summer 20032AnnouncementsProject groups and preliminary topic ideas will be due on 6/30– A week from Monday– Be thinking about what you’d like to do– Try to find others in the class who might are interested in the same topic!We’re almost ready to start using the class discussions on the mailing list3Last TimeSomeone asked why, in the textbook’s example on page 98, A* search looks backward to nodes already exploredThe answer is: they don’t appear to be using a closed listIf g(n) ≥ 0 for all n, closed lists prevent such unnecessary work (back-tracked states will always be toward the end of the queue)However, if -∞ ≤ g(n) ≤ ∞ (i.e. costs can be negative: or rewards!), you would want to allow such moves, and ignore the closed listClosed lists aren’t necessary, but are often useful4Searching: So FarWe’ve discussed how to build goal-based and utility-based agents that search to solve problemsWe’ve also presented both uninformed (or blind) and informed (or heuristic) approaches for searchWhat we’ve covered so far are called partial search strategies because they build up partial solutions, which could enumerate the entire state space before finding a solution5Complete SearchingIn complete search strategies, each state or node already represents a complete solution to the problem at hand– We aren’t concerned with finding a path– We don’t necessarily have a designated start stateThe objective is to search through the problem space to find other solutions that are better, the best, or that that meet certain criteria (goal)6OptimizationProblems where we search through complete solutions to find the best solution are often referred to as optimization problemsMost optimization tasks belong to a class of computational problems called NP– Non-deterministic Polynomial time solvable– Computationally very hard problems– For NP problems, state spaces are usually exponential, so partial search methods aren’t time or space efficient27Optimization ProblemsThe k-Queens ProblemOf course this isn’t real chess8Optimization ProblemsTraveling Salesman Problem (TSP)Perhaps most famous optimization problem9Optimization ProblemsAs it turns out, many real-world problems that we might want an agent to solve are similarly hard optimization problems:– Bin-packing– Logistics planning– VLSI layout/circuit design– Theorem-proving– Navigation/routing– Production scheduling, supply/demand– Learning the parameters for a neural network(more in the machine learning part of the course)10Optimization ProblemsFor optimization (also sometimes called constraint-satisfaction) problems, there is a well-defined objective function that we are trying to optimize11Satisfiability (SAT)Classic NP problemBelongs to a specific class of problems in the complexity hierarchy called NP-Complete– Any other NP problem can be converted to a SAT problem in polynomial time– These are the hardest problems we know ofPNP-CompleteNP12Satisfiability (SAT)Given:– Some logical formula– Array of binary variables in the formulaDo:– Find a truth assignment for all variables such that the formula is satisfied (true)313Satisfiability (SAT)For example, given the following formula with 8 clauses and 10 variables:(x1∨ x2∨ ¬x3) ∧ (x2∨ ¬x10) ∧ (¬x2) ∧(x4∨ x10) ∧ (x3∨ x5) ∧ (¬x4∨ x2∨ ¬x5) ∧(¬x1∨ x6∨ ¬x7) ∧ (x8∨ x10)We need to find a 10-bit array that makes the formula logically true– There are 210= 1024 possible binary arrays– Only 32 of them (~3%) are solutions to this formulaA bit of notation: ∧ and ∨ are a logical “and” and “or” operators, respectively. A clause (x1∨ ¬x2) is true if either x1= 1 or x2= 0. The formula is satisfied when all of its clauses are true.14Greedy Search for SATA state is a 10-bit array x– e.g. x = “0101010101”– For this array, x1= 0, x2= 1, etc.Our actions are to toggle any single bit in the array to generate a new oneOur heuristic (or objective function) will be to minimize the number of clauses in the formula that are unsatisfied by the candidate string– We are trying to satisfy them all15Greedy Search for SAT0000000000 | h=316Greedy Search for SAT0000000000 | h=31000000000 | h=30000010000 | h=30100000000 | h=40000001000 | h=30010000000 | h=30000000100 | h=20001000000 | h=20000000010 | h=30000100000 | h=20000000001 | h=217Greedy Search for SAT0000000000 | h=31000000000 | h=30000010000 | h=30100000000 | h=40000001000 | h=30010000000 | h=30000000100 | h=20001000000 | h=20000000010 | h=30000100000 | h=20000000001 | h=21000000100 | h=20000010100 | h=20100000100 | h=30000001100 | h=20000100100 | h=10000000101 | h=20001000100 | h=10000000110 | h=20010000000 | h=218Greedy Search for SAT1000000000 | h=30000010000 | h=30100000000 | h=40000001000 | h=30010000000 | h=3 0001000000 | h=20000000010 | h=30000100000 | h=20000000001 | h=21000000100 | h=20000010100 | h=20100000100 | h=30000001100 | h=20010000000 | h=20000000110 | h=20000100100 | h=10000000101 | h=20001000100 | h=11011000100 | h=00011000100 | h=1……7 other states…… ……7 other states …………6 other states …… ……6 other states ……0000000100 | h=20000000000 | h=3419Greedy Search for SATGreedy search does the right thing in that it does find a solution, and quicklyHowever, it only expanded 4 out of the 35 that are generated in the search (i.e. placed in the open list)– You may work it all out yourself if you wishIt also found a direct route, and we don’t need to remember the path, so storing all those extra states pretty much wasted space!20Local SearchLocal search is a type of greedy, complete search that focuses on a specific (or local) part of the search space, rather than trying to branch out into all of itWe only consider the neighborhood of the current state rather than the entire state space so far (so as not to waste time/space)21Beam SearchOne type of local search is beam search, which uses f(n), as in other informed searches, but uses a “beam” with a width w to restrict the possible search directionsOnly keep the w-best nodes in the open list, and throw the rest awayMore space efficient than best-first search, but can throw away nodes on a solution path22Beam Search Example# of states tested: 0, expanded: 0f(n) = g(n) +