Problem Solving Based on Searching Module 2

Problem searching

1. MODULE 2-Problem Solving based on Searching Introduction to Problem Solving by searching Methods-State Space search, Uninformed Search Methods – Uniform Cost Search, Breadth First Search- Depth First Search-Depth limited search, Iterative deepening depth-first, Informed Search Methods- Best First Search, A* Search

2. Artificial intelligence Intelligence : “Ability to learn, understand, and think”. The study of the capacity of machines to simulate intelligent human behavior. AI is the study of how to make computers make things which at the moment people do better. ARTIFICIAL INTELLIGENCE 2

3. Formal description for defining a problem Representation : State Space Initial State Goal State Transformation Rules ARTIFICIAL INTELLIGENCE 3

4. Problem solving System Define the problem. Analyze the problem. Isolate & represent the task knowledge necessary to solve the problem. Choose the best problem- solving techniques & apply it to the problem. ARTIFICIAL INTELLIGENCE 3

5. Production Systems Production System Consists of A set of rules : (Pattern) 🡺Operation to be performed One / more Knowledge/ databases Control strategy –specifies order in which rules will be compared Rule applier ARTIFICIAL INTELLIGENCE 5

6. Example 1: 8-Puzzle problem ARTIFICIAL INTELLIGENCE 6 URL:http://www.cs.mun.ca/~oram/cs3754/AI6.pdf

7. State spaces ARTIFICIAL INTELLIGENCE 7 http://www.cs.mun.ca/~oram/cs3754/AI6.pdf

8. 8-PUZZLE Initial State Goal State Apply 2 heuristic functions; Misplaced Tile & Manhattan Distance

9. 8-PUZZLE

10. 8-PUZZLE

11. 8-PUZZLE

12. Example 2: Game Playing ARTIFICIAL INTELLIGENCE 12

13. Game Playing ARTIFICIAL INTELLIGENCE 13

14. Chess game ARTIFICIAL INTELLIGENCE 14 Transformation Rules: white pawn at square(file e, rank 2) AND square(file e, rank 3) is empty AND square(file e, rank 4) is empty Initial state : Current board position Goal state : opponent does not have a legal move and his /her king is under attack. Move pawn from square(file e, rank 2) to square(file e, rank 4)

15. State spaces: ARTIFICIAL INTELLIGENCE 15

16. ARTIFICIAL INTELLIGENCE 16

17. Problem types Deterministic, fully observable ⇒ single state problem Agent knows exactly which state it will be in solution is a sequence. E.g:Chess game Partial knowledge of states and actions: Non-observable ⇒ sensorless or conformant problem Agent may have no idea where it is; solution (if any) is a sequence. Nondeterministic (stochastic) and/or partially observable ⇒ contingency problem E.g: Self Driving Cars  Unknown state space ⇒ exploration problem (“online”) When states and actions of the environment are unknown. ARTIFICIAL INTELLIGENCE 17

18. Problem characteristics Is the problem decomposable into a set of independent smaller or easier sub problems ? E.g: ∫(x^2+ 3x + sin2^x * cos2^x) dx Can solution steps be i gnored or at least undone if they prove unwise? In real life, there are three important types of problems: Ignorable ( theorem proving) Recoverable ( 8-puzzle) Irrecoverable ( Chess) Is the problem’s universe predictable? Is a good solution absolute or relative? ARTIFICIAL INTELLIGENCE 18

19. Problem characteristics .. Is the solution a state or path? Is a large amount of knowledge absolutely required to solve the problem , or is knowledge important only to constrain the search? Can a computer that is simply given the problem return the solution , or will the solution of the problem require i nteraction between the computer and a person? ARTIFICIAL INTELLIGENCE 19

20. Production System characteristics Monotonic : application of rule never prevents later application of another rule when both are used at the same time (that could have been applied at the time first rule was selected) Non Monotonic : this is not true Partially commutative : If the application of a particular sequence of rules transform x🡺y, then any permutation of those rules ie allowable also transform x🡺y Commutative : both Monotonic & Partially commutative ARTIFICIAL INTELLIGENCE 20

21. Examples of Problems “Toy” Problems : Water jug 8 – Queens 8 Puzzle ARTIFICIAL INTELLIGENCE 21 “ Real” Problems : Schedules Traveling Salesman. Robot navigation. Language Analysis (Parsers, Grammars). VLSI design. Speech Recognition

22. Issues in the design of Search programs Direction in which to conduct the search (forward Vs Backward reasoning) How to select applicable rules (matching) How to represent each node of the search process ARTIFICIAL INTELLIGENCE 22

23. Control /Search Strategies Control Strategy decides which rule to apply next during the process of searching for a solution to a problem Requirements for a good Control Strategy It should cause motion. It should explore the solution space in a systematic manner Types Uninformed Heuristic ARTIFICIAL INTELLIGENCE 23

24. Control/ Search Algorithms : ARTIFICIAL INTELLIGENCE 24

25. Search strategies-performance measure A strategy is defined by picking the order of node expansion . Problem-solving performance is measured in four ways : Completeness; Does it always find a solution if one exists? Optimality; Does it always find the least-cost solution? Time Complexity; Number of nodes generated/expanded? Space Complexity; Number of nodes stored in memory during search? ARTIFICIAL INTELLIGENCE 25

26. Search strategies-performance measure Time and space complexity are measured in terms of problem difficulty defined by: b - maximum branching factor of the search tree( the number of children at each node, the outdegree) d - depth of the least-cost solution (   the depth of its deepest leaf-longest path from node to leaf) m - maximum depth of the state space (may be ∞) ARTIFICIAL INTELLIGENCE 26

27. ARTIFICIAL INTELLIGENCE 27

28. Uninformed search strategies Blind search uses only the information available in problem definition. Types Breadth-first search (BFS) Depth-first search (DFS) Depth-limited search Iterative deepening search. ARTIFICIAL INTELLIGENCE 28

29. BF-search : Breadth-First Search At each level we expand all nodes(possible solutions) Expand shallowest unexpanded node ARTIFICIAL INTELLIGENCE 29 A

30. BF-search ARTIFICIAL INTELLIGENCE 30 A B C

31. BF-search, an example ARTIFICIAL INTELLIGENCE 31 A B C D E

32. BF-search, an example ARTIFICIAL INTELLIGENCE 32 A B C D E F G

33. ARTIFICIAL INTELLIGENCE 33

34. BF-search: Evaluation Completeness: YES (if b is finite) Time complexity: Total number of nodes generated T (b) = 1+b 2 +b 3 +.......+ b d = O (b d )  Where the d= depth of shallowest solution and b is a node at every state Space complexity: Memory requirements are a bigger problem than its execution time. O (b d ) Optimality: Does it always find the least-cost solution? In general YES unless actions have different cost. ARTIFICIAL INTELLIGENCE 34

35. Example :Water Jug problem ARTIFICIAL INTELLIGENCE 35 .Example: Water Jug Problem You are given two jugs, a 4-gallon one and a 3-litre one. Neither have any measuring markers on it. There is a pump that can be used to fill the jugs with water. How can you get exactly 2 gallons of water into 4-gallon jug. Let x and y be the amounts of water in 4-gallon and 3-gallon Jugs respectively. (x,y) refers to water available at any time in 4-gallon, 3-gallon jugs. (x,y) 🡪 (x-d,y+dd) means drop some unknown amount d of water from 4-gallon jug and add dd onto 3-gallon jug.

36. Example :Water Jug problem ARTIFICIAL INTELLIGENCE 36

37. Elements of Production Systems State Space: (x,y) Where x=0,1,2,3,4 y=0,1,2,3 Initial State: (0,0) Goal State: (2,n) Production Rules ARTIFICIAL INTELLIGENCE 37

38. ARTIFICIAL INTELLIGENCE 38

39. Solution :using BFS ARTIFICIAL INTELLIGENCE 39

40. BF-search: Evaluation Completeness: YES Time complexity: Total number of nodes generated O (b d ) Space complexity: Memory requirements are a bigger problem than its execution time. O (b d ) Optimality: YES ARTIFICIAL INTELLIGENCE 40

41. DF-search: Depth-First Search Expands one of the nodes at the deepest level ARTIFICIAL INTELLIGENCE 41 A

42. DF-search, an example Expand deepest unexpanded node ARTIFICIAL INTELLIGENCE 42 A B C S-A-B-D-E-C-G

43. Solution :using DFS ARTIFICIAL INTELLIGENCE 43

44. DF-search: evaluation Completeness: NO unless search space is finite. Time complexity : T(n)= 1+ n 2 + n 3  +.........+ n m =O(n m ) Where, m= maximum depth of any node and this can be much larger than d (Shallowest solution depth) Space complexity: Backtracking search uses even less memory.   O(bm) . Optimality : No Same issues as completeness ARTIFICIAL INTELLIGENCE 44

45. Uniform-cost Search Algorithm Uniform-cost search is a searching algorithm used for traversing a weighted tree or graph. This algorithm comes into play when a different cost is available for each edge. The primary goal of the uniform-cost search is to find a path to the goal node which has the lowest cumulative cost. A uniform-cost search algorithm is implemented by the priority queue. It gives maximum priority to the lowest cumulative cost. Uniform cost search is equivalent to BFS algorithm if the path cost of all edges is the same. ARTIFICIAL INTELLIGENCE 45

46. Uniform cost search ARTIFICIAL INTELLIGENCE 46

47. Depth-Limited Search Algorithm A depth-limited search algorithm is similar to depth-first search with a predetermined limit. Depth-limited search can solve the drawback of the infinite path in the Depth-first search. In this algorithm, the node at the depth limit will treat as it has no successor nodes further. Depth-limited search can be terminated with two Conditions of failure: Standard failure value: It indicates that problem does not have any solution. Cutoff failure value: It defines no solution for the problem within a given depth limit. ARTIFICIAL INTELLIGENCE 47

48. EXAMPLE:DLS ARTIFICIAL INTELLIGENCE 48

49. Iterative deepening depth-first Search The iterative deepening algorithm is a combination of DFS and BFS algorithms. This search algorithm finds out the best depth limit and does it by gradually increasing the limit until a goal is found. This algorithm performs depth-first search up to a certain "depth limit", and it keeps increasing the depth limit after each iteration until the goal node is found. This Search algorithm combines the benefits of Breadth-first search's fast search and depth-first search's memory efficiency. The iterative search algorithm is useful uninformed search when search space is large, and depth of goal node is unknown. ARTIFICIAL INTELLIGENCE 49

50. ARTIFICIAL INTELLIGENCE 50 1'st Iteration-----> A 2'nd Iteration----> A, B, C 3'rd Iteration------>A, B, D, E, C, F, G 4'th Iteration------>A, B, D, H, I, E, C, F, K, G In the fourth iteration, the algorithm will find the goal node.

51. Informed search strategies Uses problem specific knowledge beyond the definition of the problem. Types of Heuristic search algorithms Local search algorithms Generate and test Hill Climbing Global search algorithms A* search (Best First Search) AO* search (Problem reduction) Constraint Satisfaction Problem(CSP) Means-ends Analysis(MEA) ARTIFICIAL INTELLIGENCE 51

52. Local search algorithm: Generate and Test Steps: Generate a possible solution Test to see if this is a solution by comparing the chosen point / end point to the set of acceptable goal states If a solution has been found , quit. Otherwise return to step 1 ARTIFICIAL INTELLIGENCE 52 Not an Effective Technique Use Combination- Plan _Generate _ Test Combination = G&T+ CSP

53. Example - Traveling Salesman Problem (TSP) Traveler needs to visit n cities. Know the distance between each pair of cities. Want to know the shortest route that visits all the cities once. ARTIFICIAL INTELLIGENCE 53

54. TSP - generation of possible solutions is done in lexicographical order of cities: 1. A - B - C - D 2. A - B - D - C 3. A - C - B - D 4. A - C - D - B 5. A - D - C - B 6. A - D - B - C n=80 will take millions of years to solve exhaustively! ARTIFICIAL INTELLIGENCE 54

55. Hill Climbing (HC) Variant of G&T based on Feedback In G& T, Test Procedure 🡪 Yes (or) No Here, “Test Function is Augmented with heuristic“ HC often used when a good heuristic Function is available & when no useful knowledge available Example : To reach a place in Unfamiliar city without a map ARTIFICIAL INTELLIGENCE 55

56. Hill Climbing Consider all possible successors as “one step” from the current state on the landscape. At each iteration, go to The best successor (steepest ascent) Any uphill move (first choice) Any uphill move but steeper is more probable (stochastic) All variations get stuck at local maxima Types: ARTIFICIAL INTELLIGENCE 56 Simple Hill climbing Steepest –Ascent Hill climbing Simulated Annealing

57. Simple Hill climbing Algorithm Evaluate the initial state. Loop until a solution is found or there are no new operators left to be applied: - Select and apply a new operator - Evaluate the new state: goal → quit better than current state → new current state Example: 8 puzzle problem Here, h(n) = the number of misplaced tiles (not including the blank), the Manhattan Distance heuristic helps us quickly find a solution to the 8-puzzle. ARTIFICIAL INTELLIGENCE 57 Click to add text

58. Advantages of Hill Climbing Estimates how far away the goal is. Is neither optimal nor complete. Can be very fast.   ARTIFICIAL INTELLIGENCE 58

59. Global Search Strategies Best-First Search – an algorithm in which a node is selected for expansion based on an evaluation function f(n) -node with the lowest evaluation function is selected Choose the node that appears to be the best ARTIFICIAL INTELLIGENCE 59

60. A Quick Review g(n) = cost from the initial state to the current state n h(n) = estimated cost of the cheapest path from node n to a goal node f(n) = evaluation function to select a node for expansion (usually the lowest cost node) Example: in route planning the estimate of the cost of the cheapest path might be the straight line distance between two cities ARTIFICIAL INTELLIGENCE 60

61. Greedy Best-First Search Expand the node that is closest to the goal assuming it will lead to a solution quickly -aka “Greedy Search” f(n) = h(n) Implementation expand the “most desirable” node into the fringe queue sort the queue in decreasing order of desirability Example: consider the straight-line distance heuristic h SLD Expand the node that appears to be closest to the goal ARTIFICIAL INTELLIGENCE 61

62. Greedy Best-First Search ARTIFICIAL INTELLIGENCE 62 176

63. Greedy Best-First Search ARTIFICIAL INTELLIGENCE 63 h SLD (In(Arad)) = 366

64. Greedy Best-First Search ARTIFICIAL INTELLIGENCE 64

65. Greedy Best-First Search ARTIFICIAL INTELLIGENCE 65 Shortest path cost is 450

66. A* Search A* (A star) is the most widely known form of Best-First search It evaluates nodes by combining g(n) and h(n) f(n) = g(n) + h(n) Where g(n) = cost so far to reach n h(n) = estimated cost to goal from n f(n) = estimated total cost of path through n ARTIFICIAL INTELLIGENCE 66

67. Example ARTIFICIAL INTELLIGENCE 67

68. A* Search ARTIFICIAL INTELLIGENCE 68

69. A* Search ARTIFICIAL INTELLIGENCE 69

70. A* Search ARTIFICIAL INTELLIGENCE 70 415=317+98

71. A* Search ARTIFICIAL INTELLIGENCE 71 Shortest path cost A->S->R->P->B=418 415=317+98

72. A* Search Complete Yes Time Exponential The better the heuristic, the better the time Space Keeps all nodes in memory and save in case of repetition A* usually runs out of space before it runs out of time Optimal Yes, cannot expand f i+1 unless f i is finished ARTIFICIAL INTELLIGENCE 72

73. References http://www.cs.mun.ca/~oram/cs3754/AI6.pdf https://www.codingninjas.com/blog/2021/03/24/solving-water-jug-problem-using-bfs/ Kevin Night and Elaine Rich, Nair B., “Artificial Intelligence (SIE)”, Mc Graw Hill-2008.