Unit 2 -- Problem Solving (Search) -- Oct 11, 2011 Definition of a Problem 1. Initial state 2. Actions( state ) -- set of possible actions from that state 3. Result( state, action ) -- produce new state 4. GoalTest( state ) -- T/F, is this state the goal? 5. PathCost( state transition set ) -- cost of following path usually sum of each individual step: StepCost( state, action, newState ) simplest is cost of each state transition i.e. number of steps Route Finding problem 1. Arad is Initial State 2. Actions are roads between cities 3. Result function takes roads to new cities 4. Bucharest is Goal State 5. StepCost is number of Actions taken there are 3 sets of states frontier -- list of furthest explored states explored -- what we looked at already unexplored -- what's beyond the frontier Tree Search algorithm frontier = {initial state} -- but they call it the "path" too loop: if frontier is empty: return FAIL path = remove_choice( frontier ) -- get and remove state from frontier state = path.end if state is a goal: return path else for possible actions add all the path+action results to frontier (i.e., push Result( state, action ) onto frontier) !note: stops when when popping frontier, not when action is expanded! operation depends on algorithm for "remove_choice()": Breadth First Search (shortest first -- lowest step count from start) keep popping frontier until lowest step count is the goal note: in Tree Search expansion the path back to the previous state is also listed and is redundant Fix redundancy by keeping track of "explored" states by [+]adding an "explored" state list: Graph Search algorithm frontier = {initial state} -- but they call it the "path" too [+] explored = {empty} loop: if frontier is empty: return FAIL path = remove_choice( frontier ) -- get and remove state from frontier state = path.end [+] add state to explored if state is a goal: return path else for possible actions add path+action result [Result( state, action )] to frontier [+] unless result already in frontier or explored Another type of remove_choice(): Uniform Cost Search (cheapest first) 5. StepCost is the distance between each city. keep popping frontier until cheapest is the goalstate problem: topologically it searchs about half the whole space to find goal Algorithm Comparison: optimal: find path that best matches criteria complete: will goal be found if it exists? Breadth First -- smallest steps (optimal for steps), complete Cheapest First -- least costly steps (optimal for cost), complete Depth First -- longest path (not optimal for steps/cost), will not be complete with infinite depth tree memory usage: Breadth -- frontier 2^N paths at depth N Cheapest -- similar to BFS frontier Depth -- frontier is N paths at depth N To improve performance use an estimate of cost to goal (heuristic) Greedy Best First Search (expand states estimated to be least costly) but may find longer path than optimal because it doesn't consider total cost Best Estimated Total Cost A* Search (expand path that has minimum of f = g + h) g = path cost from start (minimizing will keep path short) h = heuristic estimate of cost to goal (minimizing keeps focus on goal) In map example use h = straight line distance between cities g = actual distance Optimality depends on having a good heuristic if ( h <= true-cost ) it will be optimal (note lecture said: h < cost) so h never over-estimates, is optimistic, and thus is: "admissible" generally true for Tree Search, but more complicated for Graph Search(?) A* will find the lowest cost path if h is admissible Other Problms and State Spaces Vacuum world -- vacuum and two positions w/w/o dirt = (2^2 * 2) = 8 states two "board" positions each can be dirty/clean two vacuum positions then add: power switch on/off/sleep dirt camera on/off brush at 5 heights 10 positions states = 307,200 --> each position has dirty/clean state! 3power * 2camera * 5height * 10positions * 2^10dirty/clean Sliding Block -- 15 Puzzle heuristics: h1 = Number of misplaced blocks h2 = Sum of the distances to move into right position (manhattan) both are admissible, i.e., they don't over-estimate h2 >= h1 (always) -- thus h2 expands fewer paths Automatically generating good heuristics: Generating a "relaxed" problem (adds new links to state space) Rule for 15-Puzzle: block can move A->B if (A is adjacent to B) and (B is blank) remove (B is blank) rule to get h2: block can move A->B if (A is adjacent to B) remove (A is adjacent) rule to get h1: block can move A->B Can combine to get: h = max( h1, h2 ) because both are admissible !relaxing the rules will never over-estimate the solution cost! Problems with Search All solutions are a fixed sequence Necessary Conditons Environment must be: Fully observable -- current state fully known Known -- All the available Actions must be known Discrete -- Finite number of Actions to be taken Deterministic -- Can know the result of each Action Static -- Only our Actions can change the environment Implementation Notes Node -- representation of a "path" state -- value at end of this path action -- action taken to get from parent to here cost -- cumulative cost to here parent -- points to previous node, null at the beginning Lists Frontier -- remove best item, add new item, check for membership use Queue for popping, with Hash Set for membership lookup Explored -- add new item, check for membership use Hash Set or Tree for lookup schip's implementation note gleaned from the Java code: The basic search algorithm behavior (e.g., the Graph Search above) can be controlled using the FRONTIER queue mechanism -- * Breadth First Search -- uses a FIFOQueue; The oldest Node on the queue is popped off, so it goes to the Node nearest the starting position. * Depth First Search -- uses a LIFOQueue; The newest Node on the queue is popped off, so it goes to the Node nearest the current position. * Priority Search -- uses a PriorityQueue, usually based on Cost; The least costly Node on the queue is popped off, so it explores the cheapest routes first. The Cost can be just the PathCost or cumulative StepCost, or it can add a heuristic so Cost = PathCost + Heuristic