Problem Solving Strategies - Artificial Intelligence - Anna University - Regulation 2021

Problem Solving Strategies - Artificial Intelligence - Anna University

1. Problem Solving Strategies Artificial Intelligence

2. Example problems Toy Problem Exact and precise description can be given Provides basis for solving some real-life problems Used to compare performance of algorithms E.g. : 8-queen puzzle, ball picker robot Real World Problem Problem need to be solved and the solution can be utilised in practical life Examples: Route finding for a trip, robot navigation, car reversing guide

3. Problem Formulation for Toy Problems Four aspects of problem formulation Initial State Successor Function Goal State Path Cost

4. Ball Picker Robot Problem Formulation Problem Statement 2 buckets full of balls, either a ball is white or red colour. The objective is to pick all black colour balls from bucket. Initial State: Any state Successor function: Generates legal states that result from trying the three actions (Left, Right, Pick Black colour ball) Continued on the next slide…

5. Ball Picker Robot Problem Formulation Goal Test Check if all the black coloured balls from both the buckets are picked up Path Cost Path cost is the number of steps in the path States 2 (locations) x 2 2 (Two possibilities) =8 possible world states

6. Real World Problem Examples General Route Finding Problem Problem Statement It is defined in terms of specified locations and transitions along links between them States: Locations Initial State: Starting point Successor Function: Move from one location to another Continued on the next slide…

7. Real World Problem Example Goal Test : Arrive at a certain location Path Cost: May be quite complex, which can involve factors like money, time travel comfort, scenery, etc.

8. Problem Characteristics Is the problem decomposable to smaller or easier problems? Can problem solution steps be ignored or undone? Is the problem universally predictable? Is a good solution absolute or relative? Is the solution a state or a path? Is the problem using consistent knowledge base? Does the problem require lots of knowledge or uses knowledge to constrain solutions? What is the role of knowledge? Does the task require periodic human-interaction with computer?

9. Searching for solution A set of all possible states for a given problem is the state space of the problem Construction of state space Terminology used in Search trees Node in a tree State Fringe Leaf node

10. Searching for solution Node representation in a Search Tree State Parent-node Action Path-cost Depth The Node Searching and Expansion Algorithms

11. Searching for solution Measuring Problem solving performance Completeness Optimality Time Complexity Space Complexity Branching Factor Depth of goal node Maximum length of path