Problem Solving: State-Space Search and Control Strategies 2.1 Introduction Problem solving is a method of deriving solution steps beginning from initial description of the problem to the desired solution. It has been conventionally one of the focus areas of Artificial Intelligence (AI) and can be characterized as a systematic search using a range of possible steps to achieve some predefined solution. The task is solved by a series of actions that minimizes the difference between the given situation and the desired goal. In Al, the problems are frequently modelled as a state space problem where the state space is a set of all possible states from start to goal states, The set of states form a graph in which two states are linked if there is an operation Which ean be executed to transform one state to other. While solving a problem, the state space is generated in the process of searching for its solution. There is difference between the state space search used in AI and the conventional computer science search methods. In case of the former, the states of the graph (search space) are generated as they are explored for the solution path and discarded thereafter, whereas in the traditional search method, searches are applied to the existing graphs. The typical state-space graph for solving problem is too large to be generated and stored in memory. The two types of problem-solving methods that are generally followed include gen- eral purpose and special-purpose methods. A general-purpose method is applicable to a wide variety of problems, whereas @ special-purpose method is tailor-made for a particular problem and often exploits very specific features of the problem. The most general approach for solving a problem is to generate the solution and test it. For generating new state in the search space, an action/operator/rule is applied and tested whether the state is the goal state or not, In case the state is not the goal state, the procedure is repeated. The order of application of the rules to the current state is called control strategy. Since AI programs involve clean separation of computational components of operations, control, and data, it is useful to structure AI programs in such a way that it helps describe search process efficiently that forms the core of many intelligent processes.24 Artificial Intelligence This chapter introduces various general-purpose problem-solving search techniques, such as exh tive and intelligent searches, followed by strategy used to solve constraint satisfaction Problems, 2.2 General Problem Solving wa oengn monn The following subsections describe production systems and state space search methods thy facilitate the modeling of problems and search processes (Rich and Knight, 2003), 2.2.1 Production System Production system (PS) is one of the formalisms that helps AI programs to do search process mie conveniently in state-space problems. This system comprises of start (initial) state(s) and Bod | (final) state(s) of the problem alon 1g with one or more databases consisting of suitable and neces sary information for the particular task, Generally, knowledge representation schemes are used! structure information in these databases. PS consis ts of number of production rules in which ead production rule has left side that determines the applicability of the rule and « right side tha lescribes i i PS also consists of control strate; the rules are applied when sever System which is used for exper describing search, following | gies (discussed later in detail) that specify the sequence in whi ral rules match at once. One of the examples of PS is an Expet tt opinion in a specific domain, In addition to usefulness of PSit are other advantages of it as a formalism in AI: yer Itis a good way to model the strong state-driven nature of intelligent action, ~ New rles can be easily added to account for new situations without disturbing the rest of the syste: + Tt is quite important in real-time environment and ay qr. applicati i changes the behaviour of the system, plications where new input to the databat problem. Water Jug Problem Problem statement: We hi measuring marker on gallon of water in the ae a2 pea 5-gallon (5-g) and the other 3: . IS endle: ‘ Spine. Ss supply of water through tap. Solution: State space for thi Y) suel gallon (3-g) with ® Our task is to get is problem cay il be described as the set of ordered pairs of integers 5-8 jug and Y for 3-g jug. | 2. Goal states (4, N) for any value of N <3, ) h that X represents the number of £allons of water j r 1. Start state is (0, 0) /Problem Solving: State-Space Search and Control Strategies 25 The possible operations that can be used in this problem are listed as follows: | Gi Sg jug from the ta i sO rae 'p and empty the 5-g jug by throwing water down the drain « Fill 3-g jug from the tay : if 'p and empty the 3-g jug by throwing water down the drain # Pour some or 3-g water from 5-g jug into the 3-g jug to make it full + Poursome or full 3-g jug water intorthe 5-g jug » 1 — a These operations can formally be defined as produce as given in Table 2: Table 2.1 Production Rules for Water Jug Problem \e jug until. 3-g jug is full It should to be noted that there may be more than one solutions for a given problem. We have shown two possible solution paths as given in Table 2.2 and Table 2.3. We notice that solution-1 requires 6 steps as compared to solution-2 that requires 8 steps. In order to apply rules, we have to choose appropriate control strategy which is discussed later. Table 2.2 Solution Path I Rule applied 5-g jug 3-g jug Step No Start state 0 | 0 1 5 0 i 2 3 2 2 0 3 0 2 4 5 2 7 —j—-—- ; _ a ye — _ - RuleNo | Left of rule Right of rule] Desc | i | &Y|X<5) 6,Y) _|_ Ail s-g jug 8 2 | &Y|xX>0) @Y) [Empty 5-2 jug > .=- 3 | & YY <3) (3) Fill 3-g jug a | g 3 4 |_&Y]¥>0) (x0) Empty 3-g jug a |S == 5 (XY |X+Y<5AY>0) (X+Y,0) Empty 3-g into 5-g jug er 6 | KY|X+Y<3AX>0) (,X+Y) Empy S-ginto3-giug *§ SSSR —| =——=3 7 | &Y|X+Y25AY>0) (5, ¥-(S-X)) Pour water from 3-g jug int. $s | until 5-g jug is full 3 | (&Y|X+¥23AX>0) (X=@=Y),3) | Pour water from 5-g jug into 3-g |26 Artificial intelligence ‘Table 2.3. Solution Path 2 Rule applied 3-g jug Step No Stant state 0 3 dL 3 1 dL 0 2 _ | 3 3 7 — 1 4 | 1 5 - 0 6 a 3 7 5 0 8 ___ Goal state nn Let us consider another problem of *Missiona this using production system, Missionaries and Cannibals Problem Problem Statement: Three mis on their side of the river that c: boat to cross the river in such a the river? If the cannibals ever will be eaten. How can they al lonaries and three cannibals want to cross a river, Ther in be used by either one or two persons. How should they use tts | | way that cannibals never outnumbe: issionaries on either sided || > outnumber the missionaries (on either by I cross over without anyone be ank) then the missionats g eaten? Solution: State space for this problem can be banks of the river as (L, R) where number of missionaries M, m is the mn described as the set of ordered pairs of left and ch bank is represented as a list [nM, mC, B], Here nist | > lumber of cannibals C, and B Tepresents the boat | 4. Start state: ([3M, 3C, 1B]. [0M, 0C, 0B} ), 18 me Any state: ([nyM,m,C, _}, [n.M/m,c, nstraints/conditions any state as ny (#0)205 | | ne (@ 0) 2 msi ny + 0; =3, m, +m, = 3; boat can be either side ( 3. Goal state: ( [0M, 0C, 0B}, 3M, 3C, 1B} —D. with con that boat is present and OB means it is abset Xt should be noted that by no means, this representation ig unique representations for the same problem. Table 2.4 consis \ representation. States on the left or right sides of ve constraints given in (2) above, . ql In fact, one may have nuns , Of Production rules based on the cho?) 9) er should be valid states satisfying ® | One of possible solution path trace is given in the Table 2 5Problem Solving: State-Space Search and Control Strategies 27 Table 2.4 Production Rules for Missionaries and Cannibals Problem [Rw Left side of rule OB) Tr | GeM,m(C, 1B), (23M, mC. E ma 1M, m,C, OB}) BB}, [n.M, m,C, 1B]) .C, 0B}, [n,M, m,C, 1B]) R3 | ((jM,m,C, 0B}, [nM,m,C, 1B)) RA | dnyM,m,C, OB, [n;M, m,C, IB) | a.M, mC, 0B), [n9M, mC, 1B) 0B) Rules for boat coming fro {= ] Right side of rule Rules for boat going from left bank to right benk of the river + | (()- DM, | i Libisis GM, (m= 1, 01 (m+ right bank to left Bank of the river g) Lididis | ((y=2M, m,C, 0B}, [(a,+2)M, m3C, 1B) | (aM, 26, 0B}, [mM, (m,+2)C, (= DM, mC, 0B), {(@+M,m,C, 1B) ({(a, + 2)M, m,C, 1B], [(2)-2)M, m,C, 0B (G+ Mm + 1)C, 1B) {(0,— 1)M,(m,— (aM, (m,+2)C, 1B}, [n:M, (m,—2)C, 0B) | + DM, m,C,1B},{(.~ 1M, mC, 0B) > | (QM, @m,+ NC, 1B}, [m2M, (m,— NC, 0B) Table2.5 Solution Path Rulenumber (BM, 3C, 1B}, [OM, 0C, OB] < Start State (2M, 2C, 0B}, [1M, 1, 1B) ((3M,2C, 1B}, [0M, 1C, 0B)) (GM,0C, 0B}, [0M, 3C, 1B) (3M, IC, 1B}, (0M, 2C, 0B) ((IM, 1C, 0B}, [2M, 2C, 1B) (2M, 2C, 1B}, [1M, 1C, 08)) (OM, 2C, 0B], (3M, 1C, 1B) ((0M, 3C, 1B}, 3M, 0C, OB) ((M, IC, 0B], [3M, 2c, IB) (OM, 2C, 1B], [3M, 1C, 0B) ‘((0M, 0C, 0B], [3M, 3C, 1B])_—> Goal state 2.2.2 State-Space Search |_-~ Similar to production system, state space is another method of problem repre sentation that facilitates easy search. Using this method, one can also find a path from start state to goal state while solving a problem. A state space basically consists of four components: 1. A set containing start states of the problem28 Artificial Intelligence A solution path is a path through the graph from a node in S to a node Bees fa Sbiectveg search algorithm is to determine a solution path in the'graph. There Nae ft one sol tutioy paths, as there may be more than one ways of solving the problem. One wot i arene a choi between various solution paths based on some criteria of goodness or on some heuristic function, Commonly used approach is to apply appropriate operator to transfer one State of problem another. It is similar to production system search method where we use production rules instead operators. Let us consider again the problem of ‘Missionaries and Cannibals’. The possible operators that are applied in this problem are {2MOC, 1M1 C,0M2C, 1MOC, OMG), Here M is missionary and C is cannibal. Digit before these characters indicates number of mis sionaries and cannibals possible at any point in time. These operators can be used in both th situations, i.e., if boat is on the left bank then, we write ‘Operator >’ and if the boat is on the right bank of the river, then we write “Operator —”, For the sake of simplicity, let us represent state (L : R), where L = nM m,CIB and R | m,COB. Here B represents boat with 1 or 0 indicating the presence or absence of the boat, | | | | 1. Start state: (3M3CIB : OMOCOB) or simply (331:000) 2. Goal state: (OMOCOB : 3M3C1B) or simply (000:331) Furthermore, we will filter out invalid states, illegal operators not applicable to some states, and Some states that are not required at all. For example,Problem Solving: State-Space Search and Control Strategies 29 lied, are called leaf nodes, which have no arcs leading from them, To simplify, we have not areitl od entire search space and avoided illegal and looping states. Depth-first or breadth-first em or some intelligent heuristic searches (explained later) is used to generate the search space, The search space generated using valid operators are shown in the Fig 2.1. The sequence of operators applied to solve this problem is given in Table 2.6 [ese (331 : 000) MIC <= omzc —| (220: 111) (310: 021) Moc =| omic (321 :010) «--S8M°__.. (321010) owe > tc ~ (300 ; 031) (310 : 021) OM1C ~— | oz —_ (311 ; 020) (331 : 000) Moc —— Loop (110 : 221) ~ AMic <— (221: 110) 2Moc — (020 : 311) omic | (031 : 300) OM2c — (010: 321) | omic 4Moc = (021 : 310) (111 :220) oM2c —> Mic —__ 00: 331) (000:331) Goal State en _ Sea igure 2.1 Search Space omic (320: 011) omic—— (331 : 000) Loop x30 Artificial Intelligence Table 2.6 Two Solution Paths Solution Path 1 Solution Path 2 MIC > IMIC 5 IMIG IMoc oM2c + omac + MICE OMIC 2M0C > 2Moc > Mice IMIC 2MOC > 2M0c > . oMIc OMIC — x omc = om2c Mice IMO — OM2C = IMIC Let us consider another problem called cight-puzale problem and sce how we can model this sig State space search method (Nilsson N. J 1980) The Eight-Puzzle Problem creating a new empty 4 Problem involves arranging tiles such that we get the go! & state from the start state. Fig 2.2 shows start and goal states a Goal state | 4 3 7 6 | 5 3 6 4 4 5 4 2 | I | 2 ‘ | : 8 | | 4 1 8 ~ 4 eure2.2 Eight-Puzzle ‘Problem | ) , + nt A state for this problem should keep track of the position of all tiles on the game board, wily 1 sented ae ee oank (empty cell) positiog on the board. The start and goal states may be 1°? \ Sented as follows with each tigt “presenting corresponding row { \ 1. Start state: [ (3.7.6), (5.1.2), [40,8)] ' 2. The goal state could be represented as: (15,36 3,6] (7,0,21, (4,1, 8]) 3. The operators can be thought . oe sok. \ effectively moves, ™°¥iNg {Up, Down, Leh Right}, the direction in which blank SP ; can move to the empty ctl, LProblem Solving: State-Space Search and Control Strategies 31 To simplify, a search tree up to level 2 is drawn as shown in Fig 2.3 to illustrate the use of operators to generate next state. i Initial State en | 37 6 | | 5 12 | 4s I | On | | | | = | | 6 37 6 | 2 5 12 | 8 46] ae | fstie 3 a7 | ta) 5 7 2 5 2 | | 44 8 a4 | 1 , Y | al Figure 2.3 Partial Search Tree for Eight Puzzle Problem : 1 Continue searching like this till w \iydepth-first or breadth-first strategies explained | also be made to find solution faster. e reach the goal state. The exhaustive search can proceed using later in this chapter. Some intelligent searches can 2.2.3 Control Strategies nents of problem solving that describes the is one of the most important compot ‘ontrol strategy should be such that it causes Control strategy Jes to the current state. Cc order of application of the ru! iotion towards. solution. For example, in water jug problem, if we apply a simple control strat- egy of starting cach time from the top of rule list and select the first applicable one, then we will never move towards solution. The second requirement of control strategy is that it should explore the solution space-in a systematic manner. For example, if we select a control strategy where we select a rulyfandomly from the applicable rules, then definitely it causes motion and eventually willlead t@ a solution. But there is every possibility that we arrive to same state several times. This is because control strategy is not systematic Depth-first and breadth-first are systematic | control strategies but these are blind searches. In depth-first strategy, we follow a single branch of fefthe tree until it yields a solution or some pre-specified depth has reached and then g0 back to immediate previous node and explore other branches using depth-first strategy. In breadth-first search, a search space tree is generated level wise until we find a solution or some specified depth is reached, These strategies are exhaustive, uninformed, and blind searches in nature. If the problem is simple, then any control strategy that causes motion and is systematic will lead to solution. However, to solve some real-world problems, effective control strategy must be used.32 Artificial Intelligence As mentioned earlier that the problem can be solved by searching for Pear the area of search strategies is to find the correct search strategy for a given two directions in which such a search could proceed. The main Problem, ‘Ther Work, ea * Data-driven search, called forward chaining, from the start sa © Goal-driven sear ining, from the goal state Goal-driven search, called backward chaining, from the g Forward Chaining: The process of forward chaining begins with known facts and works tow, a conclusion. For example in eight-puzzle problem, we start from the start state and work fory, to the conclusion, i.c., the goal state. In this case, we begin building a tree of move sequences yj, the root of the tree as start state. The states of next level of the tree are generated b; tules whose left sides match with root and use their right side to create the new state. is continued until a configuration that matches the goal state is generated. Lan; forward reasoning rules. Rules are expressed in the form of if-then rules, Backward Chaining: It is a working backward, generatit We reach to start state. Prok y finding This proceg gage OPSS iq goal-directed strategy that begins with the goal state and contin ing more sub-goals that must also be satisfied to satisfy main goal un log (Programming in Logic) language uses this strategy. ‘We can use both data-driven and nature of the problem. The eight- therefore, it makes no difference goal-directed strategies for problem solving, depending on th Puzzle problem has a single start state and a single goal sta Cases, same state space is searched but in different order. If then States and one start state, then it would not be efficient to because we do not know which chaining in such problems. © are large number of explicit gol solve using backward chaining strategy, goal state is closest to the start state. So it is better to use forwati Therefore, the general observations are that move from the smaller set of states to the larger setdl states and proceed in the direction with the lower branching factor (the average number of nods that can be reached directly from single node). Let us consider an example to justify our argumett- Suppose we have to prove a theorem in mathem atics. We know that from small set of axioms, st can prove large number of theorems. On the other hand, the large number of theorems must? back to the small set of axioms, Here branching factor 1s Significantly greater going forward fra! axioms to theorem rather than going from theorems to anion Therefore, proving theorem usi backward strategy is more useful, . 2.3 Characteristics of Problem WAProblem Solving: State-Space Search and Control Strategies 33 « [gnorable: These are the problems where we can ignore the solution steps. For example, in proving theorem, if some’lemma is proved to prove a theorem and later on we realize that itis not useful, then we can ignore this solution step and prove another lemma. Such problems can be solved using, simple control —ese « Recoverable: These are the problems where solution steps can be undone. For example, in water jug problem, if we have filled up the jug, we can empty it also, Any state can be reached again by undoing the steps. These problems are generally puzzles played by a single player. Such prob! can be solved by backtracking, so control strategy can be implemented using a push-down stack, « Técoverable: The problems where solution steps cannot be undone, For example, any two-player ¢game such as chess, playing cards, snake and ladder, etc. are examples of this category. Such prob- ; _—_— Decomposability of a problem: Divide the problem into a set of independent smaller sub-prob- lems, solve them and combine the solutions to get the final solution. The process of dividing sub- problems continues till we get the set of the smallest sub-problems for which a small collection of specific rules are used. Divide-and-conquer technique is the commonly used method for solving such problems. It is an importantand useful characteristic, as each sub-problem is simpler to solve and can be handed over to a different processor. Thus, such problems can be solved in parallel processing environment. = Role of knowledge: Knowledge plays an important role in solving any problem. Knowledge could bein the form of rules and facts which help generating search space for finding the solution. Consistency of Knowledge Base used in solving problem: Make sure that knowledge base used to solve problem is consistent. Inconsistent knowledge base will lead to wrong solutions. For exam- ple, if we have knowledge in the form of rules and facts as follows: If it is humid, it will rain. If it is sunny, then it is daytime. It is sunny day. It is nighttime. This knowledge is not consistent as there is a contradiction because ‘it is a daytime’ can be deduced from the knowledge, and thus both ‘it is night time’ and ‘it is a day time’ are not possible at the same time. If knowledge base has such inconsistency, then some methods may be used to avoid such conflicts. Requirement of solution: We should analyze the problem whether solution required is al relative. We call solution to be absolute if we have ser exact solution, whereas it we have reasonably good and approximate solution. For example, in water jug problem, if Lan are more than one ways to solve a problem, then we follow one path successfully. There is m0 ne to 0 back and find a better solution, In this case, the solution is absolute. In travelling salestt problem (discussed later), our goal is to find the shortest route. Unless all routes are now ath difficult to know the shortest route. This is a best-path problem, whereas water JU is astcs problem, Any-path problem is generally solved in reasonable amount of time by usin Ty wivh that suggest good paths to explore. Best-path problems are computationally harder comp’ any-path problems.34 Artificial Intelligence 2.4 Exhaustive Searches we . sul? Let us discuss some of'systematic uninformed exhaustive ae peecnt thea ahah della ? depth-first iterative deepening, -and bidirectional searches, and pre: gc S. 2.4.1 Breadth-First Search The breadth-first search (BFS) expands all the states one step away from a Start state, and t | expands all states two steps from start state, then three steps, etc., until a goal state is reached, Successor states are examined at the same depth before going deeper. The BFS always gives optimal path or solution This search is implemented using two lists called OPEN and CLOSED. The OPEN Ii those states that are to be expanded ai ind CLOSED list keeps track of states already OPEN list is maintained as a queue and CLOSED list as a stack. For the sake of ei Writing BFS algorithm for checking whether a goal node exists or not. Furthermor can be modified to get a path from back to its parent in the search tree Algorithm (BFS) Input: START and GOAL states Local Variables: OPEN, CLOSED. STATE-x, SUCCs. FOUND: Output: Yes or No ist Contains expanded. Heg implicity, we ar e, this algorithy 1g CLOSED list with pointer Method: © initialize OPEN list with START and CLOSED = 4: * FOUND = false; * while (OPEN #@ and FOUND = false) do { * remove the first state from * put STATE-X in the fron * if STATE-x = { © perform EXPAND operation on STATE-X Producing @ list of SUCCs: ‘| * remove fror , Tiere TOM Successors those states, 47 any, that are in the CLOSED * append SUCCs at the end of the OPEN list : OPEN and call t Of CLOSED list. { GOAL then FOUND = true else /*queue*/ } /* end while */ ° if FOUND = true then return Yes else return No © StopProblem Solving: State-Space Search and Control Strategies 35 Let us see the search tree generation from start state of the water jug problem using BFS algo- rithm. At each state, we apply first applicable rule. If it generates previously generated state then cross it and try another rule in the sequence to avoid the looping. If new state is generated then expand this state in breadth-first fashion, The rules given in Table 2.1 for water jug problem are applied and enclosed in {}. Figure 2.4 shows the trace of search tree using BFS. Start State (0.0) (0) 0.3) | 90] Ne ty | Neo | 0) 63) (23) - 63) (0.0) (3,0) | x x | 4 & 1 No , 4/ ve 14,2) | (20) 60) (0.0) 33) a) | x x x | nag Ne « anf AG | x (02) x 1) | of \ ees af \ peo) {5:2) “ (0.1) x | nag Ne W | ) x (43) — Goat state 1, 0) Figure 2.4 Search Tree Generation using BFS 2)—5 (v,0) Search tree is developed level wise. This is not memory efficient as partially developed tree is to be kept in the memory but it finds optimal solution or path. We can easily see the path from start to goal by tracing the tree from goal state to start state through parent link. This path is optimal and we cannot get a path shorter than this. Solution path: (0,0) > (5,0) > (2,3) > 2,0) > (0,2) 3 6,2) > (4,3) The path information can be obtained by modifying CLOSED list in the algorithm by putting Pointer back to its parent. 2.4.2 Depth-First Search Tn the dey bi pth-first search (DFS), we go as far down as possible into the search tree/graph before ost ‘acking up and trying alternatives. It works by always generating a descendent of the ™36 Aniificial Intelligence recently expanded node until some depth cut off is reached and then backtracks to no recently expanded node and generates one of its descendants, DFS is memory efficieny, « Stores a single path from the root to leaf node along with the remaining uunexpanded sipyi, cach node on the path. me We can implement DFS by using two lists called OPEN and CLOSED. The OPEN list cont those states that are to be expanded, and CLOSED list keeps track of states alteady egy Gere OPEN and CLOSED lists are maintained as stacks. If we discover that first clemeny § OPEN is the Goal state, then search terminates successfully. We can get track of, the path thro, « Slate space as we traversed, but in those situations where many nodes after expansion are in closed list, we fail to keep track of our path. This information can be obtained by modi te CLOSED list by putting pointer back to its parent in the search tree. The algorithm for DR given as follows: “a Algorithm (DFS) Input: START and GOAL states of the problem focal Variables: OPEN, CLOSED. RECORD_X. SUCCESSORS, FOUND Output: A path sequence from START to GOAL state. if one exists otherwise return No . Method: | © initialize OPEN list with (START, nil) and set CLOSED = o: * FOUND = false; * while (OPEN * ® and FOUND = false) do { © remove the first record (initially (START, ni1)) from OPEN list and call it RECORD-x; | * put RECORD-X in the front of CLOSED list (maintained as stack); ° if (STATE_X of RECORD_X= GOAL) then FOUND = true else { * perform EXPAND operation on STATE-X Producing a list of records called SUCCESSORS; create each record by associating parent link with its state; * remove from SUCCESSORS any record that is already in the CLOSED list: * insert SUCCESSORS in the front of the OPEN list /* Stack */ } }/* end while */ ¢ if FOUND = true then return the path by tracing through the pointers to the Parents on the CLOSED list else return No ¢ Stop —i Problom Solving: Stato-Space Search and Control Strategies 37 § Let us see the search tree generation from start stat '¢ of the water jug problem using DFS : ing }) algorithm. | [ Waerstgreaiee { Y Mist | CLOSE - | ration | _OPEN list ‘CLOSED list | (0,0) (0,0), — ‘i | Hoi 6,0) 60) 0) ae 6.0}, 0.0) | (0.0), ny *" 6.3) : {3.6ON | ((6.0).(0.0), (0.0), nin t @.3) (©3), 6.3 166.3), 6.0), (6.0), (0.99, (0,0), 14] 6 mi) * Bo) (0.31 (0), 6.3), (63), 6.09, (6.0), lo (©.0)), (0.0), nil) 6.3). (9.60 169). G09,(03),69), 69), vag] a (5,0), 0), (0,0)), (0,0), nil)} x” 61) 11:1 1 a | : 0.1) ; \ (124) ! | a ' : ez 1,2) 3) : 2-4, ° (4.0).(4.3)), (1,3), (1,0), (1, (0.19), (0.1), (6.1)), (5,1), ((3.3), (3.0)),((3.0), (0.3)),( waa “4 a (5.3). (6.3), 6.0), (6.0 x (4,0) Goal state [(4,0), (1.3))] {(60), ny (5.0)), (5.0), (0, Figure 2.5 Search Tree Generation using DFS ‘The path is obtained from the list stored in CLOSED. The solution Path is 0.0) > 5,0) > (5,3) > @.3) > B,0) 36,3) > 6.1) > 0, 1) 3 (1,0) > (1,3) 3 4,0) Comparisons: Since these are unguided, blind, and exhaustive searches, we cannot say much about them but can make some observations. * BES is effective when the search tree has a low branching factor. * BFS can work even in trees that are infinitely deep.38 Artificial Intelligence BFS requires alot of memory as number of nodes in level ofthe tee increases exponentiany BFS is superior when the GOAL exists in the upper right portion of a search tree, BFS gives optimal solution. DES is effective when there are few sub res in the search tree that have only One Connection gg, to the rest of the states. DFS is best when the GOAL exists in the lower left portion of the search tree. DFS can be dangerous when the path closer to the START and farther from the GOAL has bg chosen. | DES is memory efficient as the path from start to current node is stored. Bach node should congy state and its parent. . . . There is another search algorithm named as ‘Depth-First Iterative Deepening’ which removes drawbacks of DFS and BFS (Richard G. Korf, 1985) DFS may not give optimal solution. | | 2.4.3 Depth-First Iterative Deepening | Depth-first iterative deepening (DFID) takes advantages of both BFS and DFS searches on tre, The algorithm for DFID is given as follows: Algorithm (DFID) Input: START and GOAL states | Local Variables: FOUND: Output: Yes or No Method: e initialize d = 1 /* depth of search tree */ . FOUND = false e while (FOUND = false) do { ¢ perform a depth first search from start to depth d. ¢ if goal state is obtained then FOUND = true eise discard th nodes generated in the search of depth d ed-dtil } /* end while */ e if FOUND = true then return Yes otherwise return Wo « StopKs Oe ee Problem Solving; State-Space Search ‘and Control Strategies 39 since DFID expands all nodes at a given depth before expanding any nodes at greater depth, it is guaranteed to find a shortest path or optimal solution from start to goal state. The working of DFID algorithm is shown in Fig. 2.6 as given below: [inital State = — = | | oO | toto | 28 tteration | | . | | | | | 3*iteration ‘o C | Continue this way Figure 2.6 Search Tree Generation using DFID [At any given time, it is performing a DFS and never scarches deeper than depth ‘d’, Thus, the space it uses is O(d). Disadvantage of DFID is that it performs wasted computation before reach- ing the goal depth. 2.4.4 Bidirectional Search sas . P 7 search Bidirectional search is a graph search algorithm that runs two simultaneous searches. on oe wi moves forward from the start state and other moves backward from the goal and stops40 Artificial Intelligence two meet in the middle. It is useful for those problems which have a single start state and gi goal state, The DFID can be applied to bidirectional search for k = 1, 2, .... The kth iterate consists of generating all states in the forward direction from start sate up to depth k Using Be and from goal state using DFS one to depth k and other to depth k + 1 not storing States but sin. matching against the stored states generated from forward dircetion. Here the backward seare depth k + 1 is necessary to find odd-length solutions. If match is found, then path can be t e from start to the matched state and from matched to the goal state. It should be noted that. node has link to its successors as well as to its parent. These links will help generating path from start to goal states. 2, Comply The reason for this approach is that each of the two searches has time complexity (6), 0(6*” +b) is much less than the running time of one search from the beginning to the Q which would be O(6%) This search can be made in already existing graph/tree or search gr tree can be generated as a part of search. Let us illustrate the working of this method using exigi graph. Consider the following graph as shown in Fig. 2.7. Find a route/path from node labeled | node labeled 16. Figure 2.7 Graph to be Searched using Bidirectional Search ‘The trace of finding path from node | to 16 using bidirectional search is given in Fig. 2.8. Wecat clearly see that the path obtained is: 1, 2, 6, 11, 14, 16 2.4.5 Analysis of Search methods Effectiveness of any search strategy in problem solving is measured in terms of: * Completeness: Completeness means that an algorithm guarantees a solution if it exists © Time Complexity: Time required by an algorithm to find a solution. * Space Complexity: Space required by an algorithm to find a solution. ‘* Optimality: The algorithm is optimal if it finds the highest quality solution when there are several different solutions for the problem, \Problem Solving: State-Space Search and Control Strategies 41 Bidirectional Tree a Goal ‘6 { Figure 2.8 Trace of Bidirectional Space We will compare searches discussed above on these Parameters. Let us assume ‘b’ to be the branching factor and ‘d’ to be the depth of the tree in the worst case. DFS: Ifthe depth cut off is ‘d’, then the space requirement is of O(d). The time complexity of DFS to depth ‘d’ is of O(b") in the worst case. The DFS requires some cut-off depth. If branches are not Cut off and duplicates are not checked for, the algorithm may not even terminate. We can not say on optimality of solution. BFS: In BFS, all the nodes up to depth ‘a’ must be generated in the worst case. At level i there will be b' nodes generated. So, total number of nodes generated in the worst case is l+b+b +b +... +b! = 0(b%) Space complexity in the worst case is also O(b*). The solution obtained using BFS is optimal but | itmay take higher computational time. It will terminate and find solution if it exists. —42. Arificial Intelligence i e is ited using DF: FID: Space requirement of DFID is of O(d), as search tree is generated using DES rey time requirement for DFID will be based on number of nodes generated during search me y nodes in tree are calculated as follows: == = ‘© Nodes at depth d are generated once during the final iteration of the search, # Nodes at depth d-I are generated twice, + Nodes at depth d-2 are generated thrice, and so on. Thus, the total number of nodes generated in DFID to depth d is N=b! + 28! + 3b42 +. db , [1+ 2b! +3b-2 +... db! 4] t bil t2x43x2 44x +... tds? ] fifx=b'} { N converges to (b8) * (1 - x)? for |x| < 1. Since (1 - x)" is a constant and independent of can say that N « O(b*) if b > 1. So time complexity is of O(b*). 7” Since DFID also moves level wise, it finds the optimal solution. The following table summarizes the results. Table 2.7. Performance Comparison Search Technique Time Space Solution DFS. Ob") o@ = BFS, oO) Ow’) Optimal DFID Ob) o@) Optimal 7 Bi-directional oe?) ow") = | Above-mentioned searches are blind and are not of much use in real-life applications. There ae problems where combinatorial explosion takes place as the size of the search tree increases, su |iex as travelling salesman problem. We need to have some intelligent searches which take into a | count some relevant problem information and finds solutions faster. ys To illustrate the need of intelligent searches, let us consider a problem of. travelling salesman. | Travelling Salesman Problem i x Statement: In travelling salesman problem (TSP), onc is required to find the shortest routed |\)* visiting all the cities once and returning back to starting point, Assume that there are ‘n’ cities |\* the distance between each pair of the cities is given, The problem seems to be simple, but deceptive. The TSP is one of the most intensely studi! problems in computational mathematics and yet no effective solution method is known for general case. In this problem, a simple motion causing and systematic control strategy could, in principles) applied to solve it. All possible paths of the search tree are explored and the shortest patl®Problem Solving: State-Space Search and Control Strategies 43 retuned. This will require (n- 1)! (i.c., factorial of n — 1) paths to be examined for ‘n’ cities. If number of cities grows, then the time required to wait a salesman to get the information about the shortest path is not a practical situation. This phenomenon is called combinatorial explosion Above-mentioned strategy could be improved little bit using the following techniques « Start generating complete paths, keeping track of the shortest path found so far. « Stop exploring any path as soon as its partial length becomes greater than the shortest path length found so far. This method is efficient than the first one but still requires exponential time that is directly proportional to some number raised to ‘n’. Let us consider an example of five cities and see how we can find solution to this problem using above-mentioned technique. Assume that C1 is the start city. | D(C1,C2) = 7; D(C1,C3) = 11; D(C4,C4) = 12; D(C1,C8) = 5; D(C2,C3) 17, D(C4,C5) D(C2,C4) = 10; D(C2,C5) =12; D(C3,C4) =13; DIC3,C5) Figure2.9 Graph for Travelling Salesman Problem Table 2.8 shows some possible paths gencrated using modified approach upto some level. Some of the partial paths are pruned if the distance computed is less than minimum computed distance so far between any pair of cities. Initially, first complete path is taken to be the minimum and Y is put along with the distance, and if the distance (full or partial) is greater than the previously calculated minimum, then x is put to show pruning of that path. Continue till all the paths have been explored. In this case, there will be 4! = 24 possible paths. We notice that out of 13 paths shown in Table 2.8. 5 paths are partially evaluated. But still it requires exponential time. Therefore, some kind of thumb rules or heuristic techniques may be thought of and applied. Furthermore, there may be more than one ways of solving the problem and one would like to exercise a choice between various solution paths based on some criteria of goodness or on some thumb rule. The following sections describe various heuristic search techniques. ves So we need some intelligent methods which can make use of problem knowledge and improv the search time substantially.Artificial Intelligence ‘Table2.8 Performance Comparison Paths explored. Assume CI to be the start city | Distance 1 92343659! current best path 601 x 7 20 8 5 15 - 2740 45, 60. + a 2 C323 GIG 3C4 Cl jeu 7 20 7 5 1 274449 61 3. C139 C2943 C3305 > Cl Rx 7 1 13 17 15 17 40.57 72. Lasas 496 505Cl ‘current best path, cross path 50 ¥ x 7 ww 5 WU at [Link] 1. | tT 3950 5 C13 C2365 33 > C49 Cl 61x 7 12 7 13 12 - 19 36 49 61 6 Cl Clo C5 3645 GC current best path, cross path 48 ¥ 7 12 SX 304 at [Link] 4. - 19° 24 37. 48 7. Cl> > C2 3C4> C5 (not to be expanded further) 52 x 7 20 1 5 partially evaluated _ 374782 8 Cl > G> C29C53C4 (not to be expanded further) 54 x W 2 12 ~5 partially evaluated 37.49. 54 % Clo C33 C4 9C2> CSCI 61x uo 613 10 28 24 34 46 1 10. Cl > C33 C4 9053 C29C1 same as current best path 48 no BS 27 at S. No. 6, 2429 1B Ul. Cl> G4 C5902 no 2 wtiall 38 50 partially evaluated M12, Cl C3 C5 3C4 C2 nos 10 384353 B. Clo C45 C2303 C5 t PACs aCe ral (not to be expanded further) 59 x lees partially evaluated (not to be expanded further) 53 x t (not to be expanded further) | 50 x ' q i partially evaluated / Continue like this 2.5 Heuristic Search Techniques Heuristic technique is a criterion for determining which among several alternatives will eb most effective to achieve some goal. This technique improves the efficiency of a search proSearch and Control Strategies Problem Solving: State-Space sort OPEN list: ind empt; «select top W elements from OPEN list and put it in W_OPEN list a pty OPEN list: «for each NODE from W_OPEN list { * if NODE = Goal state then FOUND = true else find SUCCs of NODE, if any with its estimated cost and store in OPEN list: } } /* end while */ * if FOUND = true then return Yes otherwise return No: © Stop ‘The search tree generated using Beam search algorithm, assume W = 2 and B = 3 is given below. Here, black nodes are selected based on their heuristic values for further expansion. an! i, 1 Continue till goal state is Found or not able to proceed further 2.5.5 Best-First Search Best-first search is based on expanding the best partial path from current node to goal node. Here forward motion is from the best open node so far in the partially developed tree. The cost of Partial paths is calculated using some heuristic. Xf the statchas been generated earlier and new path is better than the previous one, then change the Parent and update the cost ee be noted that in hill climbing, sorting is done on the successors nodes, whereas in e Bn Search, sorting is done on the entire list. It is not guaranteed to find an oO ber [nethod et Seuerally it finds some solution faster than solution obtained from any ues 8c nena tion. performance varies directly with the accuracy of the heuristic evaluation fun et — _80 Artificial intelligence Algorithm (Best-First Search) ao! ee | lize OPEN list by root node: CLOSED = 6: FOUND = false: e while (OPEN #oand FOUND = vif the first element is the goal node. then FOUND = try 0a s Tenove it from OPEN 14 put it in CLOSED list: add its successor, if any OPEN Tist nourietic ¢ tb ue of some function thy * sort the entire list by the va url the assigns to each node, the estimate to reach to the goal node ) © if FOUND = true then return Yes otherwise return Wo; * Stop 2 ely Condition for Termination Instead of terminating when a path is found, terminate when the shortest incomplete path is loge than the shortest complete path. In most problems of practical interest, the entire search giz graph will be too large to be explicitly represented in a computer memory. The problem speciis tions, however, will contain rules that will allow a computer program to generate the graph (te incrementally from the start node in any desired direction 2.5.6 A* Algorithm \w Algorithm (‘Aystar"; proposed by Hart in 1972) is a combination of “branch and bound ® est search’ methods combined with the dynamic programming principle. It uses a heurisi! evaluation function usually denoted by f(X) to determine the order in which the search, nodes in the tree . The heuristic function Tor a node N is defined as follows: FUN) = g(N) + hN) The function g isa measure ofthe cost of getting from the start node to the current node N:ié! is Sunt of costs of the rules that were applied along the best path to the current node. The fu “Tis an estiniate of additional cost of getting from the current node N to the goal node. This Place where knowledge about the problem domain is exploited. Generally, A* algorithm is _OR graph / tee search algorithm, aie — "a FI ’ (a algorithm incrementglly searches all the routes starting from the start node until it ind “shortest path to a goalAStarting with a given node, the algorithm expands the no. ale.

You might also like

• Chapter 2

  

  No ratings yet

  Chapter 2

  43 pages
• AIA - UNIT-1-Material

  

  No ratings yet

  AIA - UNIT-1-Material

  56 pages
• AI Problem Solving: Strategies & Techniques

  

  No ratings yet

  AI Problem Solving: Strategies & Techniques

  55 pages
• Problem Solving: State-Space Search Techniques

  

  No ratings yet

  Problem Solving: State-Space Search Techniques

  55 pages
• Unit-1 Heuristic Search Techniques

  

  No ratings yet

  Unit-1 Heuristic Search Techniques

  106 pages
• Problem Solving in AI: Techniques & Examples

  

  No ratings yet

  Problem Solving in AI: Techniques & Examples

  52 pages
• AI Problem Solving and Search Strategies

  

  No ratings yet

  AI Problem Solving and Search Strategies

  46 pages
• Unit-2 (Ai)

  

  No ratings yet

  Unit-2 (Ai)

  54 pages
• AI Problem Solving and Search Techniques

  

  No ratings yet

  AI Problem Solving and Search Techniques

  95 pages
• Chapter 2

  

  No ratings yet

  Chapter 2

  54 pages
• Problems Problem Spaces and Search - PPT Download

  

  No ratings yet

  Problems Problem Spaces and Search - PPT Download

  47 pages
• Problem Solving in AI: Search Strategies

  

  No ratings yet

  Problem Solving in AI: Search Strategies

  54 pages
• Problem Solving with State-Space Search

  

  No ratings yet

  Problem Solving with State-Space Search

  39 pages
• Problem Solving in AI: Techniques & Strategies

  

  No ratings yet

  Problem Solving in AI: Techniques & Strategies

  49 pages
• AI Problem Solving Techniques Overview

  

  No ratings yet

  AI Problem Solving Techniques Overview

  66 pages
• AI Problem Characteristics and Search Methods

  

  No ratings yet

  AI Problem Characteristics and Search Methods

  46 pages
• AI Problem Solving and Search Strategies

  

  No ratings yet

  AI Problem Solving and Search Strategies

  86 pages
• Problem Solving Strategies Overview

  

  No ratings yet

  Problem Solving Strategies Overview

  65 pages
• AI Problem Solving and Search Techniques

  

  No ratings yet

  AI Problem Solving and Search Techniques

  48 pages
• Defining Problems in AI Solutions

  

  No ratings yet

  Defining Problems in AI Solutions

  29 pages
• AI Problem-Solving Techniques Explained

  

  No ratings yet

  AI Problem-Solving Techniques Explained

  63 pages
• State Space Search in AI: Concepts & Examples

  

  No ratings yet

  State Space Search in AI: Concepts & Examples

  54 pages
• State-Space Search in Problem Solving

  

  No ratings yet

  State-Space Search in Problem Solving

  32 pages
• State Space Search in AI Fundamentals

  

  No ratings yet

  State Space Search in AI Fundamentals

  13 pages
• AI Unit-2 Notes

  

  No ratings yet

  AI Unit-2 Notes

  26 pages
• Water Jug Problem and Search Strategies

  

  No ratings yet

  Water Jug Problem and Search Strategies

  25 pages
• AI Problem Solving: Search Strategies

  

  No ratings yet

  AI Problem Solving: Search Strategies

  69 pages
• Sample PDF To Split-16-30

  

  No ratings yet

  Sample PDF To Split-16-30

  15 pages
• AI Production Systems Overview

  

  No ratings yet

  AI Production Systems Overview

  31 pages
• State Space Search in AI Problem Solving

  

  No ratings yet

  State Space Search in AI Problem Solving

  29 pages
• State Space Search in Problem Solving

  

  No ratings yet

  State Space Search in Problem Solving

  47 pages
• State Space and Heuristic Search Techniques

  

  100% (1)

  State Space and Heuristic Search Techniques

  16 pages
• AI Problem Solving Techniques Overview

  

  No ratings yet

  AI Problem Solving Techniques Overview

  103 pages
• AI Problem Solving Techniques Explained

  

  No ratings yet

  AI Problem Solving Techniques Explained

  30 pages
• State Space Tree in AI Problem Solving

  

  No ratings yet

  State Space Tree in AI Problem Solving

  44 pages
• State Space Search and Control Strategies

  

  No ratings yet

  State Space Search and Control Strategies

  243 pages
• Problem Solving Techniques Explained

  

  No ratings yet

  Problem Solving Techniques Explained

  205 pages
• Problem Solving Techniques in AI

  

  No ratings yet

  Problem Solving Techniques in AI

  190 pages
• State Space Search in AI Problems

  

  No ratings yet

  State Space Search in AI Problems

  41 pages
• Problem Solving via Search Techniques

  

  No ratings yet

  Problem Solving via Search Techniques

  51 pages
• AI Problem Solving Techniques Overview

  

  No ratings yet

  AI Problem Solving Techniques Overview

  40 pages
• Water Jug Problem and Search Strategies

  

  No ratings yet

  Water Jug Problem and Search Strategies

  21 pages
• AI Problem Representation Techniques

  

  No ratings yet

  AI Problem Representation Techniques

  37 pages
• DFS Pathfinding from Node "s" to "z"

  

  No ratings yet

  DFS Pathfinding from Node "s" to "z"

  160 pages
• State Space Search in Problem Solving

  

  No ratings yet

  State Space Search in Problem Solving

  25 pages
• Problem-Solving Strategies in AI

  

  No ratings yet

  Problem-Solving Strategies in AI

  56 pages
• Missionaries and Cannibals Problem Explained

  

  No ratings yet

  Missionaries and Cannibals Problem Explained

  178 pages
• Unit I - Session 5 - Study Guide

  

  No ratings yet

  Unit I - Session 5 - Study Guide

  4 pages
• Unit-2 Ai

  

  No ratings yet

  Unit-2 Ai

  34 pages
• AI Problem Solving Techniques

  

  No ratings yet

  AI Problem Solving Techniques

  71 pages
• Unit 1 Part 2

  

  No ratings yet

  Unit 1 Part 2

  12 pages
• Effective Problem Solving Techniques

  

  No ratings yet

  Effective Problem Solving Techniques

  81 pages
• To Build A System To Solve A Problem

  

  No ratings yet

  To Build A System To Solve A Problem

  60 pages
• Problem Solving Through Search Techniques

  

  No ratings yet

  Problem Solving Through Search Techniques

  103 pages
• AI Problem Solving Techniques Overview

  

  No ratings yet

  AI Problem Solving Techniques Overview

  154 pages
• Problem-Solving with Search Strategies

  

  No ratings yet

  Problem-Solving with Search Strategies

  86 pages
• AI Problem Solving and Search Methods

  

  No ratings yet

  AI Problem Solving and Search Methods

  38 pages