人工智能英文版課件：03 Solving Problem by Serching

1、Chapter 3 Solving Problem by Searching2OutlineProblem Solving AgentsExample ProblemsSearching for SolutionsUninformed Search StrategiesAvoiding Repeated StatesSearching with Partial Information3Problem Solving AgentsIntelligent AgentsMaximize their performance measureAchieving this is sometimes simp

2、lified if the agent can adopt a goal and aim to satisfying it4Problem Solving AgentsExample: An agent who enjoys a touring holiday in Hong KongPerformance measure:Buy newest digital productsEnjoy Cantonese dim-sum, etcSightseeingThe decision problem is complex and involve many tradeoffs and reading

3、of guidebooks5Problem Solving AgentsExample: An agent in Hong Kong enjoying a touring holidayIf the agent get a train ticket from Guangzhou to HKAny action that make the agent fail to get on the train (i.e. go to HK) on time will be rejectedThis greatly simplifies the decision problemGoalHelp to org

4、anize behaviors by limiting the objectives that the gent is trying to achieve6Problem Solving AgentsGoal FormulationBased on the current situation and agents performance measureThe first step in problem solvingGoalA set of world statesThe task of agent is to find the action sequence which leads to a

5、 goal state7Problem Solving AgentsWhat sorts of actions and states to consider?If the agent would properly never find its way out of the parking lot if it was to consider actions at the level ofMove the left foot forward an inch, orTurn the steering wheel one degree leftAt this level of detail, ther

6、e is too much uncertainty in the worldThere would be too many steps in a solution8Problem Solving AgentsProblem formulationThe process of deciding what actions and states to consider for a given goalIf the agent is considering the action of driving from Arad to Bucharest at the level of driving from

7、 one city to another, the states it will consider should be corresponding to being in a particular city9Problem Solving AgentsDriving a car from Arad to Bucharest, there are three cities connecting to AradSibiuTimisoaraZerindWhich one to go ahead?10Problem Solving AgentsDriving from Guangzhou to Hon

8、g KongSibiuTimisoaraZerindWithout the information about those cities, no one knows which is the best way to driveThe best way for nowDrive randomly to try out a road11Problem Solving AgentsInformationSo, what you need is a mapNo matter it is on paper or in your memoryTo tell the agent about states t

9、hat it will get intoTo tell the agent that what actions it could takeThe agent can use this information to consider or predict subsequence stages of a hypothetical journey via each of these routesOnce the agent found the route from Arad to Bucharest, it can carry out the driving actions accordingly1

10、2Problem Solving AgentsAn agent with several immediate options of unknown value can decide what to do by first examining different possible sequences of actions that lead to states of known valuethen choosing the best sequenceThis process is called Search13Problem Solving AgentsSearchTake problem as

11、 inputOutput a solution in the form of action sequenceOnce the solution is found, the agent can act accordingly ExecutionFormulate, Search, Execution14Problem Solving AgentsExecutionTake the first action in the recommended sequenceRemove it from the sequenceRepeat Step 1 until no more action in the

12、sequenceFormulate a new goal15Problem Solving Agents16Problem Solving AgentsAssumptions on the environmentStaticOtherwise, the sequence of actions may need to change during executionObservableKnow the initial stateDiscreteEnumerating alternative courses of actionDeterministicMost important, otherwis

13、e we can not predict the outcomeThe agent can execute the plan with eyes closedIgnore the percepts which breaks the loop between agent and environment - Open-loop system17Problem Solving AgentsWell-defined problems and solutionsInitial StateWhere the agent starts inIn(Arad)Successor functionA descri

14、ption of the possible actions available to the agentGiven a state x, SUCCESSOR-FN(x) returns a set of ordered pairEach action is one of the legal actions in state xEach successor is a state that can be reached from x by applying the action18Problem Solving AgentsWell-defined problems and solutionsIn

15、itial StateSuccessor functionState SpaceGoal TestPath CostSolution19Problem Solving AgentsWell-defined problems and solutionsState SpaceThe initial state and the successor function implicitly define the state space of the problemForms a graphNodes are statesEdges are actionsA path in the state space

16、 (the graph) is a sequence of states connected by a sequence of actions20Problem Solving Agents21Problem Solving AgentsWell-defined problems and solutionsGoal TestDetermines whether a given state is a goal stateIf there is an explicit set of possible goal states, just check whether we get in either

17、one of those statesIn(Bucharest)22Problem Solving AgentsWell-defined problems and solutionsPath CostA path cost function assigns a numeric cost to each pathThe problem-solving agent chooses a cost function that reflects its own performance measureFor our driving problem, we may chooseDistance betwee

18、n cityStep CostThe cost of taking action A to go from state x to state y23Problem Solving AgentsWell-defined problems and solutionsSolutionA path from the initial state to a goal stateOptimal solutionA path from the initial state to a goal state with the lowest path cost among all solutions24Problem

19、 Solving AgentsFormulating ProblemsWe simplified the problem formulation in previous slidesIn real world, the state In(Arad)How to get into Arad?What is the road condition?Do I need a visa or application for entry?Any place for dinner in Arad?Any sightseeing place in Arad?etc25Problem Solving Agents

20、Abstraction of stateWe ignore details and small problems in a stateWe still can find our path heading to Bucharest without knowing such informationAbstraction of actionDriving a car is not easyDetail of how to drive could be ignored without affecting our plan of trip26Problem Solving AgentsLevel of

21、abstraction What is the appropriate level of abstraction?The problem of getting from Arad to Bucharest is already an abstract problemThe solution of Arad - Sibiu - - Bucharest is also an abstract solutionWe could have many detail paths information within each city27Problem Solving AgentsLevel of abs

22、traction An abstraction is valid if we can expand any abstract solution into a solution in the more detailed worldA sufficient condition is that for every detailed state that is In(Arad) there is a detailed path to some state that is In(Sibiu)The abstraction is useful if the action of abstract solut

23、ion is easier to carry out when compared with the originals28Problem Solving AgentsLevel of abstraction The choice of good abstract level involves removing as much detail as possible while retaining validity and ensuring that the abstract action is easy to carry outWithout a good abstraction, intell

24、igent agents would be completed swamped by the real world and can not do anything29Example ProblemsToy problems Any problem is intended to illustrate or exercise various problem-solving methodsEasy to use by different users to compare the performance of algorithmsReal world problemsIs a real problem

25、 with real solution that people actually care aboutTend not to have a single agreed-upon description30Example ProblemsVacuum WorldStates: the agent is in one of two locationsEach location might or might not contain dirt2 x 22 = 8 possible world statesInitial state: Any state can be designated as ini

26、tial stateSuccessor function: generates the legal states that result from trying the three actions (Left, Right, Suck)31Example ProblemsSuccessor function32Example ProblemsVacuum WorldGoal test: checks whether all the squares are cleanPath cost: each step costs 1So, the path cost is the number of st

27、eps in the path33Example ProblemsComparing with real worldDiscrete locationsDiscrete dirtReliable cleaningNever gets messed up once cleanedState is determined by both agent location and dirt locationHow many states for a world with n locations?34Example ProblemsHow many states for a world with n loc

28、ations?n2n statesn possible current location of the agent2n possible locations have dirt35Example Problems8-puzzleStates: a state description specifies the location of each of the eight tiles and the blank in one of the nine squaresInitial state: Any state can be designated as initial stateSuccessor

29、 function: generates the legal states that result from trying the four actions (Left, Right, Up, Down)36Example Problems8-puzzleGoal test: checks whether the state matches the goal configurationPath cost: each step costs 1So, the path cost is the number of steps in the path37Example Problems38Exampl

30、e ProblemsAny abstraction have we included here?States are results of many detail actionsShaking the board when pieces get stuckExtracting the pieces with a knife and putting them back againWe are left with a description of the rules of the puzzleAvoiding all the details of physical manipulations39E

31、xample Problems8-puzzleBelongs to the family of sliding-block puzzlesOften being used as test problems for new search algorithm in AINP-complete problemOne does not expect to find methods significantly better in the worst case than the search methods we will discuss soon40Example Problems8-puzzleHas

32、 9!/2 = 181,440 reachable statesBut it is still easy to solve15-puzzle on a 4 x 4 boardHas around 1.3 x 1012 statesCould be solved optimally in a few milliseconds by the bet search algorithms24-puzzle on a 5 x 5 boardHas around 1025 statesDifficult to solve in current machine and algorithm41Example

33、Problems8-queens problem42Example Problems8-queens problemPlace eight queens on a chessboard such that no queen attacks any otherA queen will attack the one on the same row, column or diagonal with herTwo formulations of problemIncremental formulationComplete-state formulationWe have no interest in

34、the path cost in this case43Example ProblemsIncremental formulation of 8-queens problemStates: Any arrangement of 0 to 8 queens on the board is a stateInitial state: no queen on the boardSuccessor function: add a queen to any empty squareGoal test: 8 queens are on the board, none attacked44Example P

35、roblemsIncremental formulation of 8-queens problemIt looks easier to observe if we add queens one by one, i.e. incrementallyBut, there are 64 x 63 x x 57 = 1.8 x 1014 possible sequences to investigate!We could reduce the number of states by prohibiting some states which must not lead to a goal state

36、Prohibit state which a queen will be attacked45Example ProblemsComplete-state formulation of 8-queens problemStates: Arrangements of n queens (n is between 0 to 8), one per column in the leftmost n columns, with no queen attacking another are statesInitial state: no queen on the boardSuccessor funct

37、ion: add a queen to any square in the leftmost empty column such that it is not attacked by any other queenGoal test: 8 queens are on the board, none attacked46Example Problems8-queens problem47Example ProblemsComplete-state formulation of 8-queens problemThis is the way human solve the 8-queens pro

38、blemOnly 2057 possible states in the state space48Example ProblemsRoute-finding problemImportant to routing in computer networks, military operations, airline travel, etcTypically a complex to specific problem49Example ProblemsAirline travel (route-finding) problemStates: Each is represented by a lo

39、cation (airport) and the current timeInitial state: specified by the problemSuccessor function: This returns the states resulting from taking any scheduled flight from the current airport to anotherleaving later than the current time plus the within-airport transit time50Example ProblemsAirline trav

40、el (route-finding) problemGoal test: Are we at the destination by some pre-specified timePath cost: This depends on monetary cost, waiting time, flight time, customs and immigration procedures, seat quality, time of day, type of airplane, frequent-flyer mileage awards, etc51Example ProblemsAirline t

41、ravel (route-finding) problemCommercial travel advice systems use this kind of problem formulation with many additional complicationsContingency planHowever, sometimes air travels do not go according to plan Backup reservations on alternate flights52Example ProblemsTouring problemVery similar to rou

42、te-finding problemHowever, require visiting each city on map at least once with the same place for starting and endingActions are still travelling from a city to another53Example ProblemsTouring problemState space is very differentIn addition to current locationNeed to keep the set of cities has bee

43、n visitedGoal test needs to checkAre we returned to the starting location?Have all cities being visited at least once?54Example ProblemsTravelling Salesman Problem (TSP)The goal is to visit every city exactly onceAim to find the shortest path for this goalNP-hard problemApplications:Automatic circui

44、t-board drillsStocking machines on shop floors55Example ProblemsVLSI Layout problemVery Large Scale Integrated circuitRequires positioning millions of components and connections on a chip to minimize areaLogical design of a circuitCell layoutChannel layout56Example ProblemsVLSI Layout problemCell la

45、youtGroup components into cells for some particular functionsEach cell has a fixed footprint (shape and size) and requires certain connections to othersAim to place cells on the chip so that there is no overlapping and space for connectionsChannel layoutFinds a specific route for each wire through t

46、he gaps between cellsExtremely complex and very worthy to solve57Example ProblemsRobot navigationA generalization of the route-finding problemRobot moves in a continuous spaceInfinite set of possible actions and states2-dimensional for a robot with wheel as leg walking on a flat surfaceMulti-dimensi

47、onal for a robot with legs and arms, etcError of sensors58Example ProblemsAutomatic assembly sequencing of complex objectE.g. assembling a car or a 1/35 tank modelGoal state can never be reached when an incorrect sequence of assembling is selectedExcept undoing some stepsProtein designFind the seque

48、nce of amino acids that will fold into a 3-D protein for curing some diseases59Searching SolutionsWe know how to formulate a problem nowButhow to solve it?60Searching SolutionsWe know how to formulate a problem nowButhow to solve it?We search through the state space61Searching SolutionsSearch treeEx

49、plicit search tree is generated by the initial state and successor functionsSearch graphIn general, we may have a search graph insteadWhat are the differences between tree and graph?62Searching SolutionsSearch graphWhen multiple paths lead to the same node, a graph is a more appropriate descriptionT

50、ree can not have loop 63Searching SolutionsRoot node of a search treeSearch node corresponding to the initial stateIn(Arad) in our driving exampleShould we test whether it is a goal state?64Searching SolutionsRoot node of a search treeShould we test whether it is a goal state?Yessometimes, we may ha

51、ve a goal state equal to the initial state. E.g. go to find Dr. Wing Ng nowHowever, it is not the goal state, so we need to search for other states65Searching SolutionsSearch for the next stateExpanding the current stateApplying the successor function to the current stateIt will generate a new set o

52、f statesIn(Sibiu), In(Timisoara), In(Zerind)We could choose our next move among these 3 choices66Searching SolutionsThe essence of searchFollowing up one option nowPutting the others aside for laterIn case our first choice can not lead to a solutionWe select Sibiu first, then we get 4 connected node

53、sIncluding the In(Arad)67Searching SolutionsWe could select any of those new nodes to go onWe also could go back and select at the 2nd level again68Searching SolutionsSearch StrategyThe choice of which state to expandWe only have 20 cities on the mapHowever, there are infinite number of paths in thi

54、s state spaceE.g. we could loop between Arad and Sibiu for any number of timesThis already generates infinitely many pathsSo, the search tree also has infinite number of nodesRepeated pathAvoiding repeated path could reduce the search complexity significantly69Searching Solutions70Searching Solution

55、sStateCorresponds to a configuration of the worldThere are only 20 states in the states space for our driving route problemOne for each city on the mapNodeA data structure used to represent the search treeThere are infinite number of nodes in the search treeInfinite number of paths between any two c

56、itiesTwo nodes may have the same state71Searching SolutionsNode in the search treeState: state in the state space to which the node correspondsParent-node: the node in the search tree that generated this nodeAction: the action that was applied to the parent to generate the nodePath cost: the cost of

57、 the path from the initial state to the node, g(n)Depth: the number of steps along the path from the initial state72Searching Solutions73Searching SolutionsFringeThe collection of nodes that have been generatedBut not yet expandedLeaf nodeA node with no successors in the tree74Searching SolutionsFri

58、ngeA search strategy may focus on expanding every node on fringeSimpleBut computational expensiveNeed to check every node to select the best oneQueueInstead, we may arrange unexpanded nodes in a queue75Searching Solutions76Searching SolutionsOperations on a queueMAKE-QUEUE (element, )Create a queueE

59、MPTY? (queue)Returns true if the queue is emptyFIRST (queue)Returns the first element of the queueREMOVE-FIRST (queue)Returns FIRST (queue) Removes it from the queue77Searching SolutionsOperations on a queueINSERT (element, queue )Inserts an element into the queueReturns the resulting queueDifferent

60、 types of queues insert elements in different ordersINSERT-ALL (elements, queue )Inserts a set of elements into the queueReturns the resulting queue78Searching SolutionsMeasuring problem-solving performanceCompletenessIs the algorithm guaranteed to find a solution when there is one?OptimalityDoes th