Chapter-3-Cvml-part-1.pptx This is About un informed cost techniques in Artificial intelligence

This is About un informed cost techniques in Artificial intelligence

1. Cs-321 Artificial Intelligence Chapter-3

2. Problems, Problem Spaces and Search

3. Problem solving We want: To automatically solve a problem We need: A representation of the problem Algorithms that use some strategy to solve the problem defined in that representation CS-321

4. Define the problem precisely by including specification of initial situation, and final situation constituting the solution of the problem. Analyze the problem to find a few important features for appropriateness of the solution technique. Isolate and represent the knowledge that is necessary for solution. Select the best problem solving technique. To build a system to solve a problem

5. Problem representation General: State space : a problem is divided into a set of resolution steps from the initial state to the goal state Reduction to sub-problems: a problem is arranged into a hierarchy of sub-problems Specific: Game resolution Constraints satisfaction CS-321

6. Important Terms Search space  possible conditions and solutions. Initial state  state where the searching process started. Goal state  the ultimate aim of searching process. Problem space  “what to solve” Searching strategy strategy for controlling the search. Search tree  tree representation of search space, showing possible solutions from initial state.

7. States A problem is defined by its elements and their relations. In each instant of the resolution of a problem, those elements have specific descriptors (How to select them?) and relations. A state is a representation of those elements in a given moment. Two special states are defined: Initial state (starting point) Final state (goal state) CS-321

8. State Space The state space of a problem includes : An initial state, One or more goal states. Sequence of intermediate states through which the system makes transition while applying various rules. State space may be a tree or a graph.

9. State modification: successor function A successor function is needed to move between different states. A successor function is a description of possible actions, a set of operators. It is a transformation function on a state representation, which convert it into another state. The successor function defines a relation of accessibility among states. Representation of the successor function: Conditions of applicability Transformation function CS-321

10. State space The state space is the set of all states reachable from the initial state. It forms a graph (or map) in which the nodes are states and the arcs between nodes are actions. A path in the state space is a sequence of states connected by a sequence of actions . The solution of the problem is part of the map formed by the state space.

11. Problem solution A solution in the state space is a path from the initial state to a goal state or, sometimes, just a goal state. Path/solution cost : function that assigns a numeric cost to each path, the cost of applying the operators to the states Solution quality is measured by the path cost function, and an optimal solution has the lowest path cost among all solutions. Solutions: any, an optimal one, all. Cost is important depending on the problem and the type of solution sought.

12. Problem description Components: State space (explicitly or implicitly defined) Initial state Goal state (or the conditions it has to fulfill) Available actions (operators to change state) Restrictions (e.g., cost) Elements of the domain which are relevant to the problem (e.g., incomplete knowledge of the starting point) Type of solution: Sequence of operators or goal state Any, an optimal one (cost definition needed), all

13. Example Problems Toy Problems  Real-world Problems Vacuum World Route Finding 8 -Puzzle  Traveling Salesperson  8 -Queens VLSI Layout  Crypt Arithmetic Robot Navigation  Missionaries And Cannibals Web Search

14. Production System Production system s can be defined as a kind of cognitive architecture, in which knowledge is represented in the form of rules . So, a  system that uses this form of knowledge representation is called a production system . To simply put, production systems consists of rules and factors. Knowledge is usually encoded in a declarative from which comprises of a set of rules of the form.

15. The rules in a production system are determined by LHS (left-hand side) and RHS (right-hand side) equations, where LHS denotes the specific condition to be applied , and RHS shows the output of the applied condition .

16. Components of a production system A Global Database Set of Production rules A control System

17. The major components of Production System in Artificial Intelligence are : Global Database:   The global database is the central data structure used by the production system in Artificial Intelligence. Set of Production Rules:   The production rules operate on the global database. Each rule usually has a precondition that is either satisfied or not by the global database. If the precondition is satisfied, the rule is usually be applied. The application of the rule changes the database. A Control System:  The control system then chooses which applicable rule should be applied and ceases computation when a termination condition on the database is satisfied. If multiple rules are to fire at the same time, the control system resolves the conflicts.

18.   Advantages  of Production system in artificial intelligence are : Provides an excellent base for structuring AI Problems Each rule can be added, removed or modified independently, which makes the system highly modular. Helpful in designing real-time applications. Provides opportunities for heuristic control of the search. A good way to model the state-driven nature of intelligent machines. More flexible than algorithmic control. Language independent

19. A Water Jug Problem:1 You are given two jugs, a 5 -gallon one and a 3-gallon one, a pump which has unlimited water which you can use to fill the jug, and the ground on which water may be poured. Neither jug has any measuring markings on it . Our task is to get 4 gallon of water in the 5 gallon jug

20. State Space Representation : we will represent a state of the problem as a tuple (x, y) where x represents the amount of water in the 5-gallon jug and y represents the amount of water in the 3-gallon jug. Note that 0 ≤ x ≤ 5, and 0 ≤ y ≤ 3 . Here , T he initial state is (0, 0 ). The goal state is (5, y) for any value of y

21. Production rules

22. To solve this water jug problem all we need is a control structure that  can  loop over certain applicable rules till the solution is achieved. For the water jug problem there are several sequences of operators that solve the problem.

23. One of the possible solution :

24. Another possible solution:…..

25. Production Systems A production system classifies the common characteristics shared by a class of reasoning problems, and has the following components: 1. Collection of states Start or initial state Goal state 2. Collection of productions: rules or moves Each production may have preconditions 3. Control system: decides which production to apply next CS-321

26. Production Systems • But how do you decide what order to apply the rules. • Requires a control strategy. – The order in which rules are applied will have a huge impact on the speed of a system. • There are two essential requirements for a control strategy. 1) A good control strategy causes motion. – Consider the jug problem. – If the strategy was to search through the rules and choose the first applicable one. – Applying the rules from top down will lead to an indefinite filling of the 4 liter jug with water. – Never moves forward so a solution is never reached . 2) A good control strategy is systematic. – Another strategy for the jug problem - on each cycle, choose at random from among the applicable rules. – Better than the first, but we will arrive at the same state several times throughout the solving process. – Will eventually arrive at a solution, but the control strategy is not systematic.

27. Control Strategies Control Strategies

28. Un-Informed VS Informed

29. Un-Informed VS Informed

30. Introduction To Graph Traversal  The process of visiting and exploring a graph for processing is called graph traversal . To be more specific it is all about visiting and exploring each vertex and edge in a graph such that all the vertices are explored exactly once . There are several graph traversal techniques such as Breadth-First Search, Depth First Search and so on. 

31. Breadth First Search

32. What is the Breadth-First Search Algorithm ? Breadth-First Search algorithm is a graph traversing technique, where you select a random initial node (source or root node) and start traversing the graph layer-wise in such a way that all the nodes and their respective children nodes are visited and explored . The BFS always gives an optimal path or solution.

33. Breadth-First Search Algorithm is a graph search algorithm. It begins from root node and continues to expand all Neighbour node 1- level below. In artificial intelligence, it is categorized as Uninformed (Blind) Search. In worst case, the time complexity of this algorithm is O ( b ^d ). ( b: maximum branching factor of the search tree ;  d: depth of the least-cost solution ) In worst case, the space complexity of this algorithm is O ( b ^d ).

34. This search is implemented using two lists called open and closed . The open list contains those states that are to be expanded . The closed list keeps track of states already expanded. Here open list is maintained as a queue and closed list as stack .

35. Consider the following State Space to be searched: A B C E D H F G Let A be the start state and G be the final or goal state to be searched. NODE_LI S T= { A} A is not goal node it is expanded . Closed list={}

36. B C E D H F G NODE_LI S T = { B , C } A

37. C E D H F G NODE_LIST={C, D,E } A B

38. E D H F G NODE_LIST={D,E, G } A B C

39. H F G NODE_LIST={G,F} A B C D E

40. H F G NODE_LIST={ G ,F} A B C D E GOAL NODE FOUND!!

41. H F G NODE_LIST={ G ,F} A B C D E TRAVERSAL ORDER: A - B - C - D - E - G

42. Advantages of BFS: BFS is a systematic search strategy- all nodes at level n are considered before going to n+1 th level. If any solution exists then BFS guarantees to find it. If there are many solutions , BFS will always find the shortest path solution. Never gets trapped exploring a blind alley. Disadvantages of BFs: All nodes are to be generated at any level. So even unwanted nodes are to be remembered. Memory wastage. Time and space complexity is exponential type- Hurdle.

43. WATER JUG PROBLEM :               There is a 4l container and 3l container ; neither has any measuring markers on it. There is a pump that can be used to fill the containers with water . Problem to solve is to get exactly two liters of water in the 4l container by using BFS     SOLUTION :          From initial state to goal state through appropriate sequence of moves or actions    such         as filling and emptying the containers. Content of the two containers at any given time is a  problem state         Let     x - content of the 4l container                   y - content of the 3l container        Then ( x,y ) - problem state represented by an ordered pair.         The set of all ordered pairs is the  space  of problem states or the  state-space  of the problem .           State-space :  { ( x,y ) | x = 0,1,2,3,4  y=0,1,2,3 }

44. Rule NO Operators for the problem state-space  The forwarded set of production rules  1. Fill the 4l container IF ( x,y | x?4) THEN (4,y) 2 Fill the 3l container  IF ( x,y | y?3) THEN (x,3) 3 Empty the 4l container  IF ( x,y | x>0) THEN (0,y) 4 Empty the 3l container IF ( x,y | y>0) THEN (x,0) 5 Pour water from 3l container into 4l container until 4l container is full IF ( x,y | x+y >=4 ? y>0 ? x?4) THEN (4,y-(4-x)) 6 Pour water from 4l container into the 3l container until the 3l container is    full IF ( x,y | x+y >=3 ? x>0 ? y?3) THEN (x-(3-y),3) 7 Pour all the water from 3l container into the 4l container IF ( x,y | x+y ?=4 ? y>0) THEN (x+y,0) 8 Pour all the water from 4l container into the 3l container IF ( x,y | x+y ?=3 ? x>0) THEN (0,x+y)

45. Nodes are examined level by level. Open nodes are ordered in ascending order of their depth (nodes at the lowest level of the depth are at the front of the queue) FIFO structure. 

46. Depth F irst S earch

47. Introduction Depth-first search is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. So the basic idea is to start from the root or any arbitrary node and mark the node and move to the adjacent unmarked node and continue this loop until there is no unmarked adjacent node. Then backtrack and check for other unmarked nodes and traverse them. Finally, print the nodes in the path.

48. A B C E D H F G Consider the following Search Space: DF S ( A )

49. A B C E D H F G Consider the following Search Space: DF S ( A )

50. C E D H F G Consider the following Search Space: DF S (B) A B

51. C D H F G Consider the following Search Space: DF S (E ) A B E

52. C D H F G Consider the following Search Space: DF S (B) A B E

53. C D H F G Consider the following Search Space: DF S (D) A B E

54. C D H F G Consider the following Search Space: DF S (F) A B E

55. C D H F G Consider the following Search Space: DF S (H) A B E

56. C D H F G Consider the following Search Space: DF S (F) A B E

57. C D H F G Consider the following Search Space: DF S ( G ) A B E GOAL NODE FOUND!!

58. WATER JUG PROBLEM :               There is a 4l container and 3l container ; neither has any measuring markers on it. There is a pump that can be used to fill the containers with water . Problem to solve is to get exactly 2 liters of water in the 4l container by using DFS     SOLUTION :          From initial state to goal state through appropriate sequence of moves or actions    such         as filling and emptying the containers. Content of the two containers at any given time is a  problem state         Let     x - content of the 4l container                   y - content of the 3l container        Then ( x,y ) - problem state represented by an ordered pair.         The set of all ordered pairs is the  space  of problem states or the  state-space  of the problem .           State-space :  { ( x,y ) | x = 0,1,2,3,4  y=0,1,2,3 }

59. Rule NO Operators for the problem state-space  The forwarded set of production rules  1. Fill the 4l container IF ( x,y | x?4) THEN (4,y) 2 Fill the 3l container  IF ( x,y | y?3) THEN (x,3) 3 Empty the 4l container  IF ( x,y | x>0) THEN (0,y) 4 Empty the 3l container IF ( x,y | y>0) THEN (x,0) 5 Pour water from 3l container into 4l container until 4l container is full IF ( x,y | x+y >=4 ? y>0 ? x?4) THEN (4,y-(4-x)) 6 Pour water from 4l container into the 3l container until the 3l container is    full IF ( x,y | x+y >=3 ? x>0 ? y?3) THEN (x-(3-y),3) 7 Pour all the water from 3l container into the 4l container IF ( x,y | x+y ?=4 ? y>0) THEN (x+y,0) 8 Pour all the water from 4l container into the 3l container IF ( x,y | x+y ?=3 ? x>0) THEN (0,x+y)

60.   Search proceeding in the parent-to children direction until forced to backtrack.(stopping search in one direction, going back to the previous node and expand in a new direction. ) Open nodes are ordered in descending order of their depth in a search tree(deepest node at the front of the list ). Such structure is stack data structure(LIFO ). nodes already on the closed list is not added to the open list to avoid recycling.

61. There is a 5l container and 3l container ; neither has any measuring markers on it. There is a pump that can be used to fill the containers with water . Problem to solve is to get exactly 4 liters of water in the 5l container by using BFS and DFS