Unformatted text preview:

Example: The 8-puzzleExample: The 8-puzzleProblem formulationSelecting a State SpaceFormulating Problem as a GraphSearch GraphProblem Solving as SearchProblem Solving as SearchExample: The 8-puzzleProblem FormulationFormulating the 8-puzzle ProblemFormulating the 8-puzzle ProblemPreconditions and EffectsA Better FormulationA Better FormulationPreconditions and EffectsHalf states are not reachable?Half states are not reachable?The Water Jugs ProblemThe Water Jugs ProblemThe Water Jugs Problem: OperatorsThe Water Jugs ProblemReal-World Search ProblemsProblem SolutionA Simple Search ProblemHanoi Tower ProblemMore on GraphsDirected GraphsFrom Search Graphs to Search TreesFrom Graphs to TreesTree Search AlgorithmsImplementation: states vs.~nodesSearch StrategiesUninformed Search StrategiesBreadth-First SearchBreadth-First SearchBreadth-First SearchBreadth-First SearchProperties of Breadth-First SearchProperties of Breadth-First SearchProperties of Breadth-First SearchProperties of Breadth-First SearchProperties of Breadth-First SearchProperties of Breadth-First SearchDepth-First SearchDepth-First SearchDepth-First SearchDepth-First SearchDepth-First SearchDepth-First SearchDepth-First SearchDepth-First SearchDepth-First SearchDepth-First SearchDepth-First SearchDepth-First SearchProperties of depth-first searchProperties of depth-first searchProperties of depth-first searchProperties of depth-first searchProperties of depth-first searchDepth-Limited SearchIterative Deepening SearchIterative deepening search $l=0$Iterative deepening search $l=1$Iterative deepening search $l=2$Iterative deepening search $l=3$Properties of iterative deepening searchProperties of iterative deepening searchProperties of iterative deepening searchProperties of iterative deepening searchProperties of iterative deepening searchBidirectional SearchBidirectional Search: ExampleUniform-Cost SearchUniform-Cost Search: ExampleRepeated statesSummaryUninformed Search StrategiesComplexity of Iterative Deepening SearchComplexity of Iterative Deepening SearchA2 Uninformed SearchHantao Zhanghttp://www.cs.uiowa.edu/∼hzhang/c145The University of IowaDepartment of Computer ScienceArtificial Intelligence – p.1/82Example: The 8-puzzle21768 345It can be generalized to 15-puzzle, 24-puzzle, or(n2− 1)-puzzle for n ≥ 6.Artificial Intelligence – p.2/82Example: The 8-puzzleGo from state S to state G.(G)(S)2 8 31 6 47 51 2 364578RLLRD UD ULLRRDD UU1 6 47 52 8 38 31 6 4578 31 47 568 31 6 47 58 31 67 5 48 317 56431 47 5688 347 5618 36 457122 22 2222Artificial Intelligence – p.3/82Problem formulationA problem is defined by four items:initial state e.g., the starting configurationsuccessor function S(x) = set of action–state pairse.g., for each configuration, we may perform fouractions: Move the blank tile up, down, left and right.For each action, we have a new configuration.goal test, e.g., x = the target configurationpath cost (additive) e.g., sum of distances, number ofactions executed, etc. Usually given as c(x, a, y), thestep cost from x to y by action a, assumed to be ≥ 0.A solution is a sequence of actions leading from theinitial state to a goal stateArtificial Intelligence – p.4/82Selecting a State SpaceReal world is absurdly complex ⇒ state space must beabstracted for problem solving(Abstract) state = set of real states(Abstract) action = complex combination of real actionse.g., “Cedar Rapids → Chicago” represents a complexset of possible routes, detours, rest stops, etc.For guaranteed realizability, any real state “in CedarRapids” must get tosome real state “in Chicago”.Each abstract action should be “easier” than theoriginal problem!(Abstract) Solution(path-sensitive) solution = set of paths that are solutionsin the real world(path-insensitive) solution = set of states that pass thegoal testArtificial Intelligence – p.5/82Formulating Problem as a GraphIn the grapheach node represents a possible state;a node is designated as the initial state;one or more nodes represent goal states, states in whichthe agent’s goal is considered accomplished.each edge represents a state transition caused by aspecific agent action;associated to each edge is the cost of performing thattransition.Artificial Intelligence – p.6/82Search GraphHow do we reach a goal state?4335742542BFASGCDinitial stategoal statesEThere may be several possible ways. Or none!Factors to consider:cost of finding a path;cost of traversing a path.Artificial Intelligence – p.7/82Problem Solving as SearchSearch space: set of states reachable from an initial state S0via a (possibly empty/finite/infinite) sequence of statetransitions.To achieve the problem’s goalsearch the space for a (possibly optimal) sequence oftransitions starting from S0and leading to a goal state;execute (in order) the actions associated to eachtransition in the identified sequence.Depending on the features of the agent’s world the two stepsabove can be interleaved.Artificial Intelligence – p.8/82Problem Solving as SearchReduce the original problem to a search problem.A solution for the search problem is a path initialstate–goal state.The solution for the original problem is eitherthe sequence of actions associated with the path orthe description of the goal state.Artificial Intelligence – p.9/82Example: The 8-puzzleStates: configurations of tilesOperators: move one tile Up/Down/Left/RightThere are 9! = 362, 880 possible states (all permutationsof { , 1, 2, 3, 4, 5, 6, 7, 8}).There are 16! possible states for 15-puzzle.Not all states are directly reachable from a given state.(In fact, exactly half of them are reachable from a givenstate.)How can a computer represent the states and the statespace for this problem?Artificial Intelligence – p.10/82Problem Formulation1. Choose an appropriate data structure to represent theworld states.2. Define each operator as a precondition/effects pairwhere theprecondition holds exactly in the states the operatorapplies to,effects describe how a state changes into asuccessor state by the application of the operator.3. Specify an initial state.4. Provide a description of the goal (used to check if areached state is a goal state).Artificial Intelligence – p.11/82Formulating the 8-puzzle ProblemStates: each represented by a 3 × 3 array of numbers in[0 . . . 8], where value 0 is for the empty cell.21768 345becomes A =2 8 31 6 47 0 5Artificial Intelligence – p.12/82Formulating the 8-puzzle ProblemOperators: 24


View Full Document
Download A2 Uninformed Search
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view A2 Uninformed Search and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view A2 Uninformed Search 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?