State-Space SearchesState spacesExample 1: MazeExample 2: The 15-puzzleExample 3: Missionaries and cannibalsStatesOperationsThe state spaceExample 3, revisitedState-space searchingThe basic search algorithmHeuristic searchingHeuristicsBest-first searchingIterative deepeningThe A* algorithmThe A* formula: f(N) = g(N) + h(N)How good is A*?IDA*ConclusionThe EndState-Space Searches2State spacesA state space consists ofA (possibly infinite) set of statesThe start state represents the initial problemEach state represents some configuration reachable from the start stateSome states may be goal states (solutions)A set of operatorsApplying an operator to a state transforms it to another state in the state spaceNot all operators are applicable to all statesState spaces are used extensively in Artificial Intelligence (AI)3Example 1: MazeA maze can be represented as a state spaceEach state represents “where you are” in the mazeThe start state represents your starting positionThe goal state represents the exit from the mazeOperators (for a rectangular maze) are: move north, move south, move east, and move westEach operator takes you to a new state (maze location)Operators may not always apply, because of walls in the maze4Example 2: The 15-puzzleThe start state is some (almost) random configuration of the tilesThe goal state is as shownOperators areMove empty space upMove empty space downMove empty space rightMove empty space leftOperators apply if not against edge 3 10 13 7 9 14 6 1 4 15 2 11 8 5 12Start state: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15Goal state:5Example 3: Missionaries and cannibalsAn old puzzle is the “Missionaries and cannibals” problem (in various guises)The missionaries and cannibals wish to cross a riverThey have a canoe that can hold two peopleIt is unsafe to have cannibals outnumber missionariesMMMCCCInitial stateMMMCCCGoal state6StatesA state can be represented by the number of missionaries and cannibals on each side of the riverInitial state: 3m,3c,canoe / 0m,0cGoal state: 0m,0c / 3m,3c,canoeWe assume that crossing the river is a simple procedure that always works (so we don’t have to represent the canoe being in the middle of the river)However, this is redundant; we only need to represent how many missionaries/cannibals are on one side of the riverInitial state: 3m,3c,canoeGoal state: 0m,0c7OperationsAn operation takes us from one state to anotherHere are five possible operations:Canoe takes 1 missionary across river (1m)Canoe takes 1 cannibal across river (1c)Canoe takes 2 missionaries across river (2m)Canoe takes 2 cannibals across river (2c)Canoe takes 1 missionary and 1 cannibal across river (1m1c)We don’t have to specify “west to east” or “east to west” because only one of these will be possible at any given time8The state space3m, 2c3m, 1c2m, 3c1m, 3c2m, 2c1m2m2c1m1c1c1c3m, 2c,canoe2m, 3c,canoe1m1m1c3m, 3c,canoeetc.etc.etc.etc.9Example 3, revisited3 missionaries, 3 cannibals, 1 canoeThe canoe can hold at most two peopleCannibals may never outnumber missionaries (on either side)Initial state is (3, 3, 1), representing the number of missionaries, cannibals, boats on the initial sideThe goal state is (0, 0, 0)Operators are addition or subtraction of the vectors (1 0 1), (2 0 1), (0 1 1), (0 2 1), (1 1 1)Operators apply if result is between (0 0 0) and (3 3 1)10State-space searchingMost problems in AI can be cast as searches on a state spaceThe space can be tree-shaped or graph-shapedIf a graph, need some way to keep track of where you have been, so as to avoid loopsThe state space is often very, very largeWe can minimize the size of the search space by careful choice of operatorsExhaustive searches don't work—we need heuristics11The basic search algorithm Initialize: put the start node into OPEN while OPEN is not empty take a node N from OPEN if N is a goal node, report success put the children of N onto OPEN Report failureIf OPEN is a stack, this is a depth-first searchIf OPEN is a queue, this is a breadth-first searchIf OPEN is a priority queue, sorted according to most promising first, we have a best-first search12Heuristic searchingAll the previous searches have been blind searchesThey make no use of any knowledge of the problemIf we know something about the problem, we can usually do much, much betterExample: 15-puzzleFor each piece, figure out how many moves away it is from its goal position, if no other piece were in the wayThe total of these gives a measure of distance from goalThis is a heuristic measure13HeuristicsA heuristic is a rule of thumb for deciding which choice might be bestThere is no general theory for finding heuristics, because every problem is differentChoice of heuristics depends on knowledge of the problem space14Best-first searchingUse the same basic search algorithmChoose from OPEN the “best” node, that is, the one that seems to be closest to a goalGenerally, even very poor heuristics are significantly better than blind search, but...No guarantee that the best path will be foundNo guarantee on the space requirements15Iterative deepening Set LIMIT to zero do forever Do a depth-first search up to LIMIT levels deep If a goal is found, return success, else add 1 to LIMITEach time through the loop we start all over!If we find a path, it will be a shortest possible pathOnly requires linear space, because it only uses DFSIncreased time requirements are only linear16The A* algorithmSuppose:You keep track of the distance g(N) that each node N that you visit is from the start state You have some heuristic function, h(N), that estimates the distance between node N and a goalThen:f(N) = g(N) + h(N) gives you the (partially estimated) distance from the start node to a goal nodeThe A* algorithm is: choose from OPEN the node N with the smallest value of f(N)17The A* formula: f(N) = g(N) + h(N)g(N) is the (known) distance from start to Nh(N) is the (estimated) distance from N to a goalf(N) is just the sum of thesef(N) is our best guess as to the distance from start to a goal, passing through NstartNgoalf(N)g(N)h(N)18How good is A*?Memory usage depends on the heuristic functionIf h(N) =
View Full Document