Foundations of Artificial IntelligenceProblem-Solving as SearchCS472 – Fall 2007Thorsten JoachimsIntelligent AgentsAgent: Anything that can be viewed as perceiving its environmentthrough sensors and acting upon that environment through actuators.Agent Function:Agent behavior is determined by the agent function that maps any given percept sequence to an action.Agent Program: The agent function for an artificial agent will be implemented by an agent program.A Simple Reflex AgentEnvironmentWhat the world is like nowWhat action I should do nowCondition-action rulesSensorsAgentActuatorsAgent with Model and Internal StateEnvironmentWhat the world is like nowWhat action I should do nowCondition-action rulesSensorsAgentActuatorsHow the world evolvesWhat my actions doStateGoal-Based AgentEnvironmentWhat the world is like nowWhat action I should do nowGoalsSensorsAgentActuatorsHow the world evolvesWhat my actions doStateWhat it will be like if I do action AProblem Solving as Search- Search is a central topic in AI- Originated with Newell and Simon's work on problem solving. Famous book: “Human Problem Solving” (1972)- Automated reasoning is a natural search task- More recently: Given that almost all AI formalisms (planning, learning, etc.) are NP-complete or worse, some form of search is generally unavoidable (no “smarter” algorithm available).Defining a Search ProblemState space - described byinitial state - starting stateactions - possible actions availablesuccessor function; operators - given a particular state x, returns a set of < action, successor > pairsGoal test - determines whether a given state is a goal state.Path cost - function that assigns a cost to a pathThe 8 Puzzle4456173282183765Initial State Goal StateCryptarithmeticSEND+ MORE------MONEYFind (non-duplicate) substitution of digits for letters such that the resulting sum is arithmetically correct.Each letter must stand for a different digit.Solving a Search Problem: State Space SearchInput:– Initial state– Goal test– Successor function– Path cost functionOutput:– Path from initial state to goal state. – Solution quality is measured by the path cost.Generic Search AlgorithmL = make-list(initial-state)loopnode = remove-front(L) (node contains pathof how the algorithmgot there)if goal-test(node) == true thenreturn(path to node)S = successors (node)insert (S,L)until L is emptyreturn failureSearch procedure defines a search treeSearch treeroot node - initial statechildren of a node - successor statesfringe of tree - L: states not yet expandedSearch strategy - algorithm for deciding which leaf node to expand next.stack: Depth-First Search (DFS).queue: Breadth-First Search (BFS).Solving the 8-Puzzle4456173282183765Start StateGoal StateWhat would the search tree look like after the start state was expanded?Node Data Structure45617328PARENT-NODEACTION= rightDEPTH=6PATH-COST=6CHILD-NODECHILD-NODENODESTATEEvaluating a Search StrategyCompleteness: Is the strategy guaranteed to find a solution when there is one?Time Complexity: How long does it take to find a solution?Space Complexity: How much memory does it need?Optimality: Does strategy always find a lowest-cost path to solution? (this may include different cost of one solution vs. another).Uninformed search: BFSConsider paths of length 1, then of length 2, then of length 3, then of length 4,....Time and Memory Requirements for BFS –O(bd+1)Let b = branching factor, d = solution depth, then the maximum number of nodes generated is: b + b2+ ... + bd+ (bd+1-b)Time and Memory Requirements for BFS – O(bd+1)Example:• b = 10 • 10000 nodes/second• each node requires 1000 bytes of storage1 exa3523 yrs10151410 peta35 yrs101312101 tera129 days1011101 tera31 hrs109810 gig19 min1076106 meg11 sec111,10041 meg.11 sec11002MemoryTimeNodesDepthUniform-cost Searchssss0AAAABBBCCCCGGGG155555151515151111 10s1B10Requirement: g(Successor(n)) g(n) ≥Use BFS, but always expand the lowest-cost node on the fringe as measured by path cost g(n).Uninformed search: DFSDFS vs. BFSTimem = d: DFS typically winsm > d: BFS might winm is infinite: BFS probably will do betterSpaceDFS almost always beats BFSO(bm)O(bm)NOFinite depthDFSO(bd+1)O(bd+1)YESYESBFSSpaceTimeOptimalCompletem is maximum depthWhich search should I use?Depends on the problem.If there may be infinite paths, then depth-first is probably bad.If goal is at a known depth, then depth-first is good.If there is a large (possibly infinite) branching factor, thenbreadth-first is probably bad.(Could try nondeterministic search. Expand an open node at random.)Iterative Deepening [Korf 1985]Idea:Use an artificial depth cutoff, c.If search to depth c succeeds, we're done. If not, increase c by 1 and start over.Each iteration searches using depth-limited DFS.Limit=1Iterative DeepeningLimit=0Limit=2Limit=3Cost of Iterative Deepeningspace: O(bd) as in DFS, time: O(bd)1.021001.08251.2101.552332ratio of IDS to DFSbBidirectional SearchComparing Search Strategies***Note that many of the ``yes's'' above have caveats, which we discussed when covering each of the algorithms.YesYesNoYesYesComplete?yesyesnoyesYesOptimal?bd/2bdbmbd+1Spacebd/2bdbmbd+1TimeBidirectional(if applicable)Iterative