1CS 2710 Foundations of AICS 2710 Foundations of AILecture 2Milos [email protected] Sennott SquareProblem solving by searchingCS 2710 Foundations of AIExample• Assume a problem of computing the roots of the quadratic equationDo you consider it a challenging problem? 02=++ cbxax2CS 2710 Foundations of AIExample• Assume a problem of computing the roots of the quadratic equationDo you consider it a challenging problem?Hardly we just apply the standard formula: aacbbx2422,1−±−=02=++ cbxaxCS 2710 Foundations of AISolving problems by searching• Some problems have a straightforward solution– Just apply the formula, or follow a standardized procedureExample: solution of the quadratic equation– Hardly a sign of intelligence• More interesting problems require search:– more than one possible alternative needs to be explored before the problem is solved – the number of alternatives to search among can be very large, even infinite.3CS 2710 Foundations of AISearch example: Traveler problem• Find a route from one city (Arad) to the other (Bucharest)CS 2710 Foundations of AIExample. Traveler problem• Another flavor of the traveler problem: – find the route with the minimum length between S and T4CS 2710 Foundations of AIExample. Puzzle 8.• Find the sequence of the empty tile moves from the initial game position to the designated target position Initial position Goal positionCS 2710 Foundations of AIExample. N-queens problem.Find a configuration of n queens not attacking each otherGoal configurationBad goal configuration5CS 2710 Foundations of AIA search problemis defined by:• Search space:– The set of objects among which we search for the solution Example: objects = routes between cities, or N-queen configurations• Goal condition– What are the characteristics of the object we want to find in the search space?–Examples:• Path between cities A and B• Path between A and B with the smallest number of links• Path between A and B with the shortest distance• Non-attacking n-queen configurationCS 2710 Foundations of AISearch• Search (process)– The process of exploration of the search space• The efficiency of the search depends on:– The search space and its size– Method used to explore (traverse) the search space– Condition to test the satisfaction of the search objective(what it takes to determine I found the desired goal object)• Important to remember !!!– Conveniently chosen search space and the exploration policy can have a profound effect on the efficiency6CS 2710 Foundations of AIGraph search• Many search problems can be naturally represented as graph search problems• Typical example: Route finding– Map corresponds to the graph, nodes to cities, links to available connections between cities– Goal: find a route (path) in the graph from S to TstarttargetSTABCDEFGHIJKLCS 2710 Foundations of AIGraph search• Less obvious conversion:Puzzle 8. Find a sequence of moves from the initial configuration to the goal configuration.– nodes corresponds to states of the game, – links to valid moves made by the playerstarttarget7CS 2710 Foundations of AIGraph search problem• States - game positions, or locations in the map that are represented by nodes in the graph• Operators - connections between cities, valid moves• Initial state – start position, start city• Goal state – target position (positions), target city (cities)starttargetSTABCDEFGHIJKLCS 2710 Foundations of AIGraph search• More complex versions of the graph search problems:– Find a minimal length path(= route with the smallest number of connections, the shortest sequence of moves that solves Puzzle 8) starttargetSTABCDEFGHIJKL8CS 2710 Foundations of AIGraph search• More complex versions of the graph search problems:– Find a minimum cost path(= a route with the shortest distance) starttargetSTABCDEFGHIJKL2322332244244335CS 2710 Foundations of AIGraph search• How to find the path between S and T ?• A strawman solution: – Generate systematically all sequences of 1, 2, 3, … edges– Check if the sequence yields a path between S and T.• Can we do better? starttargetSTABCDEFGHIJKL9CS 2710 Foundations of AIGraph searchCan we do better? • We are not interested in sequences that do not start in S and that are not valid paths• Solution:–?starttargetSTABCDEFGHIJKLCS 2710 Foundations of AIGraph searchCan we do better?• We are not interested in sequences that do not start in S and that are not valid paths• Solution:– Look only on valid paths starting from SstarttargetSTABCDEFGHIJKL10CS 2710 Foundations of AIGraph search• Being smarter about the space we search for the solution pays off in terms of search process efficiency. starttargetSTABCDEFGHIJKLCS 2710 Foundations of AIN-queensSome problems can be converted to the graph search problems• But some problems are harder and less intuitive– Take e.g. N-queens problem.• Problem: – We look for a configuration, not a sequence of moves– No distinguished initial state, no operators (moves) Goal configuration11CS 2710 Foundations of AIstartTarget 1Graph searchA trick: generate a configuration step by step (one queen per step)• States (nodes) correspond to configurations of 0,1,2,3,4 queens• Links (operators) correspond to the addition of a queen• Initial state: no queens placed on the boardTarget 2CS 2710 Foundations of AIGraph searchN-queens problems• This is a different graph search problem when compared to Puzzle 8 or Route planning:We want to find only the target configuration, not a path12CS 2710 Foundations of AITwo types of graph search problems• Path search– Find a path between states S and T– Example: traveler problem, Puzzle 8– Additional goal criterion: minimum length (cost) path• Configuration search (constraint satisfaction search)– Find a state (configuration) satisfying the goal condition– Example: n-queens problem, design of a device with a predefined functionality– Additional goal criterion: “soft” preferences for configurations, e.g. minimum cost design CS 2710 Foundations of AISearch problemSearch problems that can be represented or converted into a graph search problems can be defined in terms of: • Initial state– State (configuration) we start to search from (e.g. start city, initial game position)• Operators: – Transform one state to another (e.g. valid connections between cities, valid moves in Puzzle 8)• Goal