problem solving agent in artificial intelligence ppt

• My presentations

Auth with social network:

Download presentation

We think you have liked this presentation. If you wish to download it, please recommend it to your friends in any social system. Share buttons are a little bit lower. Thank you!

Presentation is loading. Please wait.

Problem Solving Agents

Published by Millicent McKinney Modified over 6 years ago

Similar presentations

Presentation on theme: "Problem Solving Agents"— Presentation transcript:

Artificial Intelligent

Solving problems by searching Chapter 3. Outline Problem-solving agents Problem types Problem formulation Example problems Basic search algorithms.

Additional Topics ARTIFICIAL INTELLIGENCE

Review: Search problem formulation

Announcements Course TA: Danny Kumar

Uninformed search strategies

Problem Solving by Searching Copyright, 1996 © Dale Carnegie & Associates, Inc. Chapter 3 Spring 2007.

Comp 307 Problem Solving and Search Formalize a problem as State Space Search Blind search strategies Heuristic search.

May 12, 2013Problem Solving - Search Symbolic AI: Problem Solving E. Trentin, DIISM.

1 Chapter 3 Solving Problems by Searching. 2 Outline Problem-solving agentsProblem-solving agents Problem typesProblem types Problem formulationProblem.

Solving Problem by Searching Chapter 3. Outline Problem-solving agents Problem formulation Example problems Basic search algorithms – blind search Heuristic.

Artificial Intelligence for Games Uninformed search Patrick Olivier

14 Jan 2004CS Blind Search1 Solving problems by searching Chapter 3.

EIE426-AICV 1 Blind and Informed Search Methods Filename: eie426-search-methods-0809.ppt.

UNINFORMED SEARCH Problem - solving agents Example : Romania  On holiday in Romania ; currently in Arad.  Flight leaves tomorrow from Bucharest.

An Introduction to Artificial Intelligence Lecture 3: Solving Problems by Sorting Ramin Halavati In which we look at how an agent.

CS 380: Artificial Intelligence Lecture #3 William Regli.

Problem Solving by Searching Copyright, 1996 © Dale Carnegie & Associates, Inc. Chapter 3 Spring 2004.

About project

© 2024 SlidePlayer.com Inc. All rights reserved.

UNIT 2 : AI Problem Solving

Sep 27, 2014

2.79k likes | 4.74k Views

UNIT 2 : AI Problem Solving. 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.

Share Presentation

• search strategies
• space complexity
• depth limited search
• space complexity maximum number

Presentation Transcript

UNIT 2 : AI Problem Solving • 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. By: AnujKhanna(Asst. Prof.) www.uptunotes.com

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. • The state space for WJP can be described as a set of ordered pairs of integers (x,y) such that x=0,1,2,3,or 4 and y= 0,1,2,or 3. the start state is (0,0) and the goal state is (2,n) By: AnujKhanna(Asst. Prof.) www.uptunotes.com

Rules for Water Jug Problem • {(x, y)| x<4 } (4,y) • {(x, y) y<3 } (x,3) • {(x, y) x>0 } (0,y) • {(x, y) |y>0 } (x,0) • {(x, y) | x + y ≥ 4 and y>0} (4, x + y -4 ) • {(x, y) x + y ≥3 and x>0} (x+y-3, 3) • {(x, y) | x+y≤4 and y>0} ( x + y , 0) • {(x, y) | x+y≤3 and x>0} (0, x + y) • (0,2) (2,0) • (2,y) (0,y) • { (x , y) | y >0} (x, y-d) Useless rule • { (x , y) | x>0 } (x-d, y) Useless rule By: AnujKhanna(Asst. Prof.) www.uptunotes.com

Problem Characteristics 1.) Is the problem decomposable? 2) . Can solution steps be ignored or at least undone if they prove unwise?E.g : 8- Puzzle problem , Monkey Banana Problem… In 8 – puzzle we can make a wrong move and to overcome that we can back track and undo that… Based on this problems can be : • Ignorable (e.g : theorem proving) • Recoverable (e.g : 8 - puzzle) • Irrecoverable (e.g: Chess , Playing cards(like Bridge game)) Note : ** Ignorable problems can be solved using a simple control structure that never back tracks. Such a structure is easy to implement. By: AnujKhanna(Asst. Prof.) www.uptunotes.com

**Recoverable problems can be solved by a slightly more complicated control strategy that can be error prone.(Here solution steps can be undone). ** Irrecoverable are solved by a system that exp[ands a great deal of effort Making each decision since decision must be final.(solution steps can’t be undone) 3). Is the Universe Predictable? Can we earlier plan /predict entire move sequences & resulting next state. E.g : In a Bridge game entire sequence of moves can be planned before making final play….. • Certain outcomes : 8- puzzle • Uncertain outcomes : Bridge • Hardest Problems to be solved : Irrecoverable + Uncertain Outcomes 4). Is a good solution absolute / relative? By: AnujKhanna(Asst. Prof.) www.uptunotes.com

5). Is the solution state or path? 6). Role of Knowledge 7). Requiring interaction with a person 8). Problem classification By: AnujKhanna(Asst. Prof.) www.uptunotes.com

Search Techniques(Blind) • Search strategies following the two properties (Dynamic and Systematic) are • Breadth First Search (BFS) • Depth First Search (BFS) • Problem with the BFS is “Combinatorial explosion”. • Problem with DFS is that it may lead to “blind alley”. • Dead end. • The state which has already been generated. • Exceeds to futility value. By: AnujKhanna(Asst. Prof.) www.uptunotes.com

Advantages Advantages of BFS are • Will not get trapped exploring a blind alley. • Guaranteed to find the solution if exist. The solution found will also be optimal (in terms of no. of applied rules) Advantages of DFS are • Requires less memory. • By chance it may find a solution without examining much of the search space. By: AnujKhanna(Asst. Prof.) www.uptunotes.com

Search Strategies • A search strategy is defined by picking the order of node expansion • Strategies are evaluated along the following dimensions: • completeness: does it always find a solution if one exists? • time complexity: number of nodes generated • space complexity: maximum number of nodes in memory • optimality: does it always find a least-cost solution? • Time and space complexity are measured in terms of • b:maximum branching factor of the search tree • d: depth of the least-cost solution • m: maximum depth of the state space (may be ∞) By: AnujKhanna(Asst. Prof.) www.uptunotes.com

Classification of Search Strategies I. Uninformed Search strategies use only the information available in the problem definition • Breadth-first search • Depth-first search • Depth-limited search • Iterative deepening search • Branch and Bound II . Informed Search (Heuristic Search) • Hill climbing (i) Simple Hill climbing (ii) Steepest Ascent Hill climbing • Best First Search • A*, AO * algorithms • Problem Reduction • Constraint Satisfaction • Means & End Analysis , Simulated Annealing. By: AnujKhanna(Asst. Prof.) www.uptunotes.com

Breadth-first search • Expand shallowest unexpanded node • Implementation: • fringe is a FIFO queue, i.e., new successors go at end By: AnujKhanna(Asst. Prof.) www.uptunotes.com

Properties of breadth-first search • Complete?Yes (if b is finite) • Time?1+b+b2+b3+… +bd + b(bd-1) = O(bd+1) • Space?O(bd+1) (keeps every node in memory) • Optimal? Yes (if cost = 1 per step) • Space is the bigger problem (more than time) By: AnujKhanna(Asst. Prof.) www.uptunotes.com

Depth-first search • Expand deepest unexpanded node • Implementation: • fringe = LIFO queue, i.e., put successors at front By: AnujKhanna(Asst. Prof.) www.uptunotes.com

Properties of depth-first search • Complete? No: fails in infinite-depth spaces, spaces with loops • Modify to avoid repeated states along path • complete in finite spaces. • Time?O(bm): terrible if m is much larger than d • but if solutions are dense, may be much faster than breadth-first • Space?O(bm), i.e., linear space! • Optimal?No By: AnujKhanna(Asst. Prof.) www.uptunotes.com

Comparison b/w DFS & BFS Depth First Search Breadth First Search Downward traversal in the tree. If goal not found up to the leaf node back tracking occurs. Preferred over BFS when search tree is known to have a plentiful no. of goal states else DFS never finds the solution. Depth cut-off point leads to problem. If it is too shallow goals may be missed, if set too deep extra computation of search nodes is required. 5. Since path from initial to current node is stored , less space required. If depth cut-off = d , Space Complexity= O (d). Performed by exploring all nodes at a given depth before moving to next level. If goal not found , many nodes need to be expanded before a solution is found, particularly if tree is too deep. Finds minimal path length solution when one exists. No Cut – off problem. Space complexity = O (b)d By: AnujKhanna(Asst. Prof.) www.uptunotes.com

Depth-limited search = depth-first search with depth limit l, i.e., nodes at depth l have no successors • Recursive implementation: By: AnujKhanna(Asst. Prof.) www.uptunotes.com

Iterative deepening search By: AnujKhanna(Asst. Prof.) www.uptunotes.com

Iterative deepening search l =0 By: AnujKhanna(Asst. Prof.) www.uptunotes.com

Iterative deepening search l =1 By: AnujKhanna(Asst. Prof.) www.uptunotes.com

Iterative deepening search l =2 By: AnujKhanna(Asst. Prof.) www.uptunotes.com

Iterative deepening search l =3 By: AnujKhanna(Asst. Prof.) www.uptunotes.com

Iterative deepening search • Number of nodes generated in a depth-limited search to depth d with branching factor b: NDLS = b0 + b1 + b2 + … + bd-2 + bd-1 + bd • Number of nodes generated in an iterative deepening search to depth d with branching factor b: NIDS = (d+1)b0 + d b^1 + (d-1)b^2 + … + 3bd-2 +2bd-1 + 1bd • For b = 10, d = 5, • NDLS = 1 + 10 + 100 + 1,000 + 10,000 + 100,000 = 111,111 • NIDS = 6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456 • Overhead = (123,456 - 111,111)/111,111 = 11% By: AnujKhanna(Asst. Prof.) www.uptunotes.com

Properties of iterative deepening search • Complete? Yes • Time?(d+1)b0 + d b1 + (d-1)b2 + … + bd = O(bd) • Space?O (bd) • Optimal?Yes , if step cost = 1 By: AnujKhanna(Asst. Prof.) www.uptunotes.com

Difference b/w informed & Uninformed search Un -Informed Search Informed Search Nodes in the state are searched mechanically, until the goal is reach or time limit is over / failure occurs. Info about goal state may not be given 3. Blind grouping is done 4. Search efficiency is low. 5. Practical limits on storage available for blind methods. 6. Impractical to solve very large problems. 7. Best solution can be achieved. E.g : DFS , BFS , Branch & Bound , Iterative Deepening …etc. More info. About initial state & operators is available . Search time is less. Some info. About goal is always given. Based on heuristic methods Searching is fast Less computation required Can handle large search problems 7. Mostly a good enough solution is accepted as optimal solution. E.g: Best first search , A* , AO *, hill climbing…etc By: AnujKhanna(Asst. Prof.) www.uptunotes.com

Heuristic Search • Search strategies like DFS and BFS can find out solutions for simple problems. • For complex problems also although DFS and BFS guarantee to find the solutions but these may not be the practical ones. (For TSP time is proportional to N! or it is exponential with branch and bound). • Thus, it is better to sacrifice completeness and find out efficient solution. • Heuristic search techniques improve efficiency by sacrificing claim of completeness and find a solution which is very close to the optimal solution. • Using nearest neighbor heuristic TSP can be solved in time proportional to square of N. By: AnujKhanna(Asst. Prof.) www.uptunotes.com

When more information than the initial state , the operators & goal state is available, size of search space can usually be constrained. If this is the case, better info. available more efficient is the search process. This is called Informed search methods. • Depend on Heuristic information • Heuristic Search improves the efficiency of search process, possibly by sacrificing the claims of completeness. “Heuristics are like tour guides. They are good to the extent that they point in generally interesting directions . Bad to the extent that they may miss points of interest to a particular individuals. E. g : A good general purpose heuristic that is useful for a variety of combinatorial explosion problems is the “Nearest Neighbor Heuristic”. This works by selecting the locally superior alternate at each step. Applying it to Traveling Salesman Problem, following algo is used: By: AnujKhanna(Asst. Prof.) www.uptunotes.com

1. Arbitrarily select a starting point let say A. 2. To select the next city , look at all the cities not yet visited & select the one closest to the current city…. Go to it Next. 3. Repeat step 2 until all the cities have been visited. Combinatorial Explosion TSP involves n cities with paths connecting the cities. A tour is any path which begins with some starting city , visits each of the other city exactly once & returns to the starting city. • If n cities then no. of different paths among them are (n-1) ! • Time to examine single path is proportional to n . T (total) = n ( n-1) ! = n !, this is total search time required • If n = 10 then 10 ! = 3, 628 , 800 paths are possible. This is very large no.. This phenomenon of growing no. of possible paths as n increases is called “ Combinatorial Explosion” By: AnujKhanna(Asst. Prof.) www.uptunotes.com

Branch and Bound Technique • To over come the problem of combinatorial explosion Branch & Bound Technique is used. • This begins with generating one path at a time , keeping track of shortest (BEST) path so far. This value is used as a Bound(threshold) for future paths. • As paths are constructed one city at a time , algorithm examines and compares it from current bound value. • We give up exploring any path as soon as its partial length becomes greater than shortest path(Bound value) so far…. • This reduces search and increases efficiency but still leaves an exponential no. of paths. By: AnujKhanna(Asst. Prof.) www.uptunotes.com

Heuristic Function • Heuristic function is a function that maps from problem state descriptions to measures of desirability and it is usually represented as a number. • Well designed heuristic functions can play an important role in efficiently guiding a search process towards a solution. • Called Objective function in mathematical optimization problems. • Heuristic function estimates the true merits of each node in the search space • Heuristic function f(n)=g(n) + h(n) • g(n) the cost (so far) to reach the node. • h(n) estimated cost to get from the node to the goal. • f(n) estimated total cost of path through n to goal. By: AnujKhanna(Asst. Prof.) www.uptunotes.com

Heuristic Search Techniques • Generate and Test • Hill Climbing • Simple Hill Climbing • Steepest Hill Climbing • Best First Search • Problem Reduction Technique • Constraint Satisfaction Technique • Means Ends Analysis By: AnujKhanna(Asst. Prof.) www.uptunotes.com

Generate and Test • Generate a possible solution and compare it with the acceptable solution. • Comparison will be simply in terms of yes or no i.e. whether it is a acceptable solution or not? • A systematic generate and test can be implemented as depth first search with backtracking. By: AnujKhanna(Asst. Prof.) www.uptunotes.com

Hill Climbing • It is a variation of generate and test in which feedback from the test procedure is used to help the generator decide which direction to move in the search space. • It is used generally when good heuristic function is available for evaluating but when no other useful knowledge is available. • Simple Hill Climbing: From the current state every time select a state which is better than the current state. • Steepest Hill Climbing: At the current state, select best of the new state which can be generated only if it is better than the current state. • Hill Climbing is a local method because it decides what to do next by looking only at the immediate consequences of its choice rather than by exhaustively exploring all the consequences. By: AnujKhanna(Asst. Prof.) www.uptunotes.com

Problems with Hill Climbing • Both simple and steepest hill climbing may fail to find solution because of the following. • Local Maximum: A state that is better than all its neighbors but is not better than some other states farther away. • A Plateau: Is a flat area of the search space in which a whole set of neighboring states have the same value. • A Ridge: A special kind of local maximum. An area of the search space that is higher than surrounding areas and that itself has slope By: AnujKhanna(Asst. Prof.) www.uptunotes.com

Example • Block World Problem Initial Goal By: AnujKhanna(Asst. Prof.) www.uptunotes.com

Example • Heuristic Function: Following heuristic functions may be used • Local: Add one point for every block that is resting on the thing it is supposed to be resting on. Subtract one point for every block that is sitting on the wrong thing. • Global: For each block that has the correct support structure, add one point for every block in the support structure. For each block that has incorrect support structure, subtract one point for every block in the existing support structure. • With local heuristic function the initial state has the value 4 and the goal state has the value 8 whereas with global heuristic the values are -28 and +28 respectively. By: AnujKhanna(Asst. Prof.) www.uptunotes.com

Example • From the initial state only one move is possible giving a new state with value 6 (-21). • From this state three moves are possible giving three new states with values as 4(-28), 4(-16), and 4(-15). • Thus we see that we are reached to plateau with local evaluation. • With global evaluation next state to be selected (with steepest hill climbing) is that with the value as -15 which may lead to the solution. • Why we are not able to find the solution? Because of deficiency of search technique are because of poor heuristic function. By: AnujKhanna(Asst. Prof.) www.uptunotes.com

• More by User

ai i: problem solving and search

24 augustus 2011. 2. AI 1. Outline. Problem-solving agentsA kind of goal-based agentProblem typesSingle state (fully observable)Search with partial informationProblem formulationExample problemsBasic search algorithmsUninformed. 24 augustus 2011. 3. AI 1. Example: Romania. 24 augustus 2011. 4.

1.14k views • 82 slides

AI I: problem solving and search

1.21k views • 82 slides

Chapter 2: Problem Solving

Chapter 2: Problem Solving. Software development method specification of needs problem analysis design and algorithmic representation implementation testing and verification documentation. Introduction to Problem Solving.

1.17k views • 26 slides

Chapter 2 - Problem Solving

Chapter 2 - Problem Solving. Program Development Cycle Programming Tools. Terminology tip. A computer program may also be called: Project Application Solution. 2.1 Program Development Cycle. Performing a Task on the Computer Program Planning. Program Development Cycle.

826 views • 42 slides

Math 2: Problem Solving

Math 2: Problem Solving. Steps . Read the problem (try to understand it upon the first read) Determine the type of problem Identify the variables Set up the equation Solve the equation/s Find the final solution Check the solution *Use trial and error only if you think it will be faster*

375 views • 27 slides

Unit 3 – Problem Solving

Unit 3 – Problem Solving.

263 views • 15 slides

Chapter 2: Problem Solving. Program Development Cycle (2.1) Programming Tools (2.2). David I. Schneider, An Introduction to Programming using Visual Basic.NET, 5th Edition , Prentice Hall, 2002. . Terminology tip. A computer program may also be called: Project Application Solution.

557 views • 42 slides

Problem Solving: Unit Rates

Problem Solving: Unit Rates. 4-step problem solving process: Read, Plan, Solve, Check. 1. Felicia’s Ride. Felicia takes 4 hours to ride her bike 56 miles. She rides at a constant speed during the 4-hour ride. What is her unit rate in miles per hour?

288 views • 11 slides

Problem Solving K-2

Problem Solving K-2. “Learning mathematics should make Sense!” “Real understanding comes from solving problems.”. Objectives for today… . To learn the 11 different problem types. To be able to write your own problems of any type .

476 views • 25 slides

Problem Solving #2

Problem Solving #2. ICS 201 Introduction to Computer Science. Consider the following two classes: public class ClassA { public void methodOne ( int i ) { } public void methodTwo ( int i ) { } public static void methodThree ( int i ) { } }

281 views • 15 slides

Unit 7 –Problem Solving

Unit 7 –Problem Solving. Mr. Gunn’s Track 1 Class. Causative Get and Have. Today we are going to look at get and have . We use get and have to say that we caused someone do something for us. Get someone to do something.

248 views • 11 slides

Unit 3 –Problem Solving

Unit 3 –Problem Solving. AO5 –Create suitable graphs and charts. Graphs/charts. Choose 3 different types for DISTINCTION Do not discuss what each graph shows at this point You MUST justify your choice of each type of graph Don’t touch line graphs unless you have continuous data!. Pie Charts.

158 views • 5 slides

Symbolic AI: Problem Solving

E. Trentin, DIISM. Symbolic AI: Problem Solving. Example: Romania. On holiday in Romania; currently in Arad. Flight leaves tomorrow from Bucharest Formulate goal : be in Bucharest Formulate problem : states : various cities actions : drive between cities Find solution :

585 views • 42 slides

Chapter 2: Problem Solving. In this chapter you will learn about: Introduction to Problem Solving Software development method (SDM) Specification of needs Problem analysis Design and algorithmic representation Implementation Testing and verification Documentation.

903 views • 36 slides

AI I: problem-solving and search

AI I: problem-solving and search. Outline. Problem-solving agents A kind of goal-based agent Problem types Single state (fully observable) Search with partial information Problem formulation Example problems Basic search algorithms Uninformed. Problem-solving agent.

1.8k views • 78 slides

Chapter 2 - Problem Solving. Program Development Cycle Programming Tools. Terminology tip. A computer program may also be called: Project (Visual Studio 6 term) Application (Generic term) Solution (Visual Studio .NET term). Program Development Cycle.

593 views • 46 slides

Unit 2 : Problem Solving Through Object

Unit 2 : Problem Solving Through Object. Content Software development cycle What are objects? Deriving objects from a given problem Generalization / Specialization Case Studies Appendix : a Diagram with different Names ?. A) SD L C - Software Development Life Cycle. pp-3.

554 views • 46 slides

1.5k views • 131 slides

Unit 2 Problem-solving and Building Smart Systems

Smart System Design and Applications. Unit 2 Problem-solving and Building Smart Systems. Prepared By: Pooja Mishra. Introduction to Problem solving process.

421 views • 39 slides

AI I: problem solving and search. Outline. Problem-solving agents A kind of goal-based agent Problem types Single state (fully observable) Search with partial information Problem formulation Example problems Basic search algorithms Uninformed. Example: Romania. Example: Romania.

942 views • 82 slides

AI: problem solving and search

AI: problem solving and search. Outline. Problem-solving agents A kind of goal-based agent Problem types Single state (fully observable) Search with partial information Problem formulation Example problems Basic search algorithms Uninformed. Example: Romania. Example: Romania.

1.93k views • 82 slides

141 views • 11 slides

• Preferences

Artificial Intelligence Chapter 3: Solving Problems by Searching - PowerPoint PPT Presentation

Artificial Intelligence Chapter 3: Solving Problems by Searching

Artificial intelligence chapter 3: solving problems by searching michael scherger department of computer science kent state university problem solving agents problem ... – powerpoint ppt presentation.

• Michael Scherger
• Department of Computer Science
• Kent State University
• Problem solving agent
• A kind of goal based agent
• Finds sequences of actions that lead to desirable states.
• The algorithms are uninformed
• No extra information about the problem other than the definition
• No extra information
• No heuristics (rules)
• Function Simple-Problem-Solving-Agent( percept ) returns action
• Inputs percept a percept
• Static seq an action sequence initially empty
• state some description of the current world
• goal a goal, initially null
• problem a problem formulation
• state lt- UPDATE-STATE( state, percept )
• if seq is empty then do
• goal lt- FORMULATE-GOAL( state )
• problem lt- FORMULATE-PROBLEM( state, goal )
• seq lt- SEARCH( problem ) SEARCH
• action lt- RECOMMENDATION ( seq ) SOLUTION
• seq lt- REMAINDER( seq )
• return action EXECUTION
• Assumes the problem environment is
• The plan remains the same
• Agent knows the initial state
• Agent can enumerate the choices
• Deterministic
• Agent can plan a sequence of actions such that each will lead to an intermediate state
• The agent carries out its plans with its eyes closed
• Certain of whats going on
• Open loop system
• Initial state
• Actions and Successor Function
• Given a 4 gallon bucket and a 3 gallon bucket, how can we measure exactly 2 gallons into one bucket?
• There are no markings on the bucket
• You must fill each bucket completely
• The buckets are empty
• Represented by the tuple ( 0 0 )
• One of the buckets has two gallons of water in it
• Represented by either ( x 2 ) or ( 2 x )
• 1 per unit step
• Fill a bucket
• (x y) -gt (3 y)
• (x y) -gt (x 4)
• Empty a bucket
• (x y) -gt (0 y)
• (x y) -gt (x 0)
• Pour contents of one bucket into another
• (x y) -gt (0 xy) or (xy-4, 4)
• (x y) -gt (xy 0) or (3, xy-3)
• Description of the eight tiles and location of the blank tile
• Successor Function
• Generates the legal states from trying the four actions Left, Right, Up, Down
• Checks whether the state matches the goal configuration
• Each step costs 1
• Eight puzzle is from a family of sliding block puzzles
• NP Complete
• 8 puzzle has 9!/2 181440 states
• 15 puzzle has approx. 1.31012 states
• 24 puzzle has approx. 11025 states
• Place eight queens on a chess board such that no queen can attack another queen
• No path cost because only the final state counts!
• Incremental formulations
• Complete state formulations
• Any arrangement of 0 to 8 queens on the board
• No queens on the board
• Successor function
• Add a queen to an empty square
• 8 queens on the board and none are attacked
• 646357 1.81014 possible sequences
• Arrangements of n queens, one per column in the leftmost n columns, with no queen attacking another are states
• Add a queen to any square in the leftmost empty column such that it is not attacked by any other queen.
• 2057 sequences to investigate
• Another Example Jug Fill
• Another Example Black White Marbles
• Another Example Row Boat Problem
• Another Example Sliding Blocks
• Another Example Triangle Tee
• Initial State
• e.g. At Arad
• A set of action state pairs
• S(Arad) (Arad-gtZerind, Zerind),
• e.g. x at Bucharest
• sum of the distances traveled
• Having formulated some problemshow do we solve them?
• Search through a state space
• Use a search tree that is generated with an initial state and successor functions that define the state space
• A state is (a representation of) a physical configuration
• A node is a data structure constituting part of a search tree
• Includes parent, children, depth, path cost
• States do not have children, depth, or path cost
• The EXPAND function creates new nodes, filling in the various fields and using the SUCCESSOR function of the problem to create the corresponding states
• Uninformed strategies use only the information available in the problem definition
• Also known as blind searching
• Breadth-first search
• Uniform-cost search
• Depth-first search
• Depth-limited search
• Iterative deepening search
• Completeness
• Will a solution always be found if one exists?
• How long does it take to find the solution?
• Often represented as the number of nodes searched
• How much memory is needed to perform the search?
• Often represented as the maximum number of nodes stored at once
• Will the optimal (least cost) solution be found?
• Page 81 in AIMA text
• Time and space complexity are measured in
• b maximum branching factor of the search tree
• m maximum depth of the state space
• d depth of the least cost solution
• Recall from Data Structures the basic algorithm for a breadth-first search on a graph or tree
• Expand the shallowest unexpanded node
• Place all new successors at the end of a FIFO queue
• Yes if b (max branching factor) is finite
• 1 b b2 bd b(bd-1) O(bd1)
• exponential in d
• Keeps every node in memory
• This is the big problem an agent that generates nodes at 10 MB/sec will produce 860 MB in 24 hours
• Yes (if cost is 1 per step) not optimal in general
• The memory requirements are a bigger problem for breadth-first search than is execution time
• Exponential-complexity search problems cannot be solved by uniformed methods for any but the smallest instances
• Same idea as the algorithm for breadth-first searchbut
• Expand the least-cost unexpanded node
• FIFO queue is ordered by cost
• Equivalent to regular breadth-first search if all step costs are equal
• Yes if the cost is greater than some threshold
• step cost gt e
• Complexity cannot be determined easily by d or d
• Let C be the cost of the optimal solution
• O(bceil(C/ e))
• Yes, Nodes are expanded in increasing order
• Recall from Data Structures the basic algorithm for a depth-first search on a graph or tree
• Expand the deepest unexpanded node
• Unexplored successors are placed on a stack until fully explored
• No fails in infinite-depth spaces, spaces with loops
• Modify to avoid repeated spaces along path
• Yes in finite spaces
• Not great if m is much larger than d
• But if the solutions are dense, this may be faster than breadth-first search
• O(bm)linear space
• A variation of depth-first search that uses a depth limit
• Alleviates the problem of unbounded trees
• Search to a predetermined depth l (ell)
• Nodes at depth l have no successors
• Same as depth-first search if l 8
• Can terminate for failure and cutoff
• Yes if l lt d
• No if l gt d
• Iterative deepening depth-first search
• Uses depth-first search
• Finds the best depth limit
• Gradually increases the depth limit 0, 1, 2, until a goal is found
• Yes if step cost 1
• Can be modified to explore uniform cost tree
• Faster than BFS even though IDS generates repeated states
• BFS generates nodes up to level d1
• IDS only generates nodes up to level d
• In general, iterative deepening search is the preferred uninformed search method when there is a large search space and the depth of the solution is not known
• Complication of wasting time by expanding states that have already been encountered and expanded before
• Failure to detect repeated states can turn a linear problem into an exponential one
• Sometimes, repeated states are unavoidable
• Problems where the actions are reversable
• Route finding
• Sliding blocks puzzles

PowerShow.com is a leading presentation sharing website. It has millions of presentations already uploaded and available with 1,000s more being uploaded by its users every day. Whatever your area of interest, here you’ll be able to find and view presentations you’ll love and possibly download. And, best of all, it is completely free and easy to use.

You might even have a presentation you’d like to share with others. If so, just upload it to PowerShow.com. We’ll convert it to an HTML5 slideshow that includes all the media types you’ve already added: audio, video, music, pictures, animations and transition effects. Then you can share it with your target audience as well as PowerShow.com’s millions of monthly visitors. And, again, it’s all free.

About the Developers

PowerShow.com is brought to you by  CrystalGraphics , the award-winning developer and market-leading publisher of rich-media enhancement products for presentations. Our product offerings include millions of PowerPoint templates, diagrams, animated 3D characters and more.

Academia.edu no longer supports Internet Explorer.

To browse Academia.edu and the wider internet faster and more securely, please take a few seconds to  upgrade your browser .

Enter the email address you signed up with and we'll email you a reset link.

• We're Hiring!
• Help Center

Download Free PDF

Artificial Intelligence: Session 3 Problem Solving Agent and searching for solutions

2023, Asst.Prof.M. Gokilavani

Related topics

•   We're Hiring!
•   Help Center
• Find new research papers in:
• Health Sciences
• Earth Sciences
• Cognitive Science
• Mathematics
• Computer Science
• Academia ©2024

• Data Science
• Data Analysis
• Data Visualization
• Machine Learning
• Deep Learning
• Computer Vision
• Artificial Intelligence
• AI ML DS Interview Series
• AI ML DS Projects series
• Data Engineering
• Web Scrapping

Problem Solving in Artificial Intelligence

Problem solving is a core aspect of artificial intelligence (AI) that mimics human cognitive processes. It involves identifying challenges, analyzing situations, and applying strategies to find effective solutions.

This article explores the various dimensions of problem solving in AI, the types of problem-solving agents, the steps involved, and the components that formulate associated problems.

Table of Content

Understanding Problem-Solving Agents

Types of problems in ai, 1. ignorable problems, 2. recoverable problems, 3. irrecoverable problems, steps in problem solving in artificial intelligence (ai), components of problem formulation in ai, techniques for problem solving in ai, challenges in problem solving with ai.

In artificial intelligence (AI) , agents are entities that perceive their environment and take actions to achieve specific goals. Problem-solving agents stand out due to their focus on identifying and resolving issues systematically. Unlike reflex agents, which react to stimuli based on predefined mappings, problem-solving agents analyze situations and employ various techniques to achieve desired outcomes.

These are problems or errors that have minimal or no impact on the overall performance of the AI system. They are minor and can be safely ignored without significantly affecting the outcome.

• Slight inaccuracies in predictions that do not affect the larger goal (e.g., small variance in image pixel values during image classification).
• Minor data preprocessing errors that don’t alter the results significantly.

Handling : These problems often don’t require intervention and can be overlooked in real-time systems without adverse effects.

Recoverable problems are those where the AI system encounters an issue, but it can recover from the error, either through manual intervention or built-in mechanisms, such as error-handling functions.

• Missing data that can be imputed or filled in by statistical methods.
• Incorrect or biased training data that can be retrained or corrected during the process.
• System crashes that can be recovered through checkpoints or retraining.

Handling : These problems require some action—either automated or manual recovery. Systems can be designed with fault tolerance or error-correcting mechanisms to handle these.

Description : These are critical problems that lead to permanent failure or incorrect outcomes in AI systems. Once encountered, the system cannot recover, and these problems can cause significant damage or misperformance.

• Complete corruption of the training dataset leading to irreversible bias or poor performance.
• Security vulnerabilities in AI models that allow for adversarial attacks, rendering the system untrustworthy.
• Overfitting to the extent that the model cannot generalize to new data.

Handling : These problems often require a complete overhaul or redesign of the system, including retraining the model, rebuilding the dataset, or addressing fundamental issues in the AI architecture.

The process of problem solving in AI consists of several finite steps that parallel human cognitive processes. These steps include:

• Problem Definition: This initial step involves clearly specifying the inputs and acceptable solutions for the system. A well-defined problem lays the groundwork for effective analysis and resolution.
• Problem Analysis: In this step, the problem is thoroughly examined to understand its components, constraints, and implications. This analysis is crucial for identifying viable solutions.
• Knowledge Representation: This involves gathering detailed information about the problem and defining all potential techniques that can be applied. Knowledge representation is essential for understanding the problem’s context and available resources.
• Problem Solving: The selection of the best techniques to address the problem is made in this step. It often involves comparing various algorithms and approaches to determine the most effective method.

Effective problem-solving in AI is dependent on several critical components:

• Initial State: This represents the starting point for the AI agent, establishing the context in which the problem is addressed. The initial state may also involve initializing methods for problem-solving.
• Action: This stage involves selecting functions associated with the initial state and identifying all possible actions. Each action influences the progression toward the desired goal.
• Transition: This component integrates the actions from the previous stage, leading to the next state in the problem-solving process. Transition modeling helps visualize how actions affect outcomes.
• Goal Test: This stage verifies whether the specified goal has been achieved through the integrated transition model. If the goal is met, the action ceases, and the focus shifts to evaluating the cost of achieving that goal.
• Path Costing: This component assigns a numerical value representing the cost of achieving the goal. It considers all associated hardware, software, and human resource expenses, helping to optimize the problem-solving strategy.

Several techniques are prevalent in AI for effective problem-solving:

1. Search Algorithms

Search algorithms are foundational in AI, used to explore possible solutions in a structured manner. Common types include:

• Uninformed Search : Such as breadth-first and depth-first search, which do not use problem-specific information.
• Informed Search : Algorithms like A* that use heuristics to find solutions more efficiently.

2. Constraint Satisfaction Problems (CSP)

CSPs involve finding solutions that satisfy specific constraints. AI uses techniques like backtracking, constraint propagation, and local search to solve these problems effectively.

3. Optimization Techniques

AI often tackles optimization problems, where the goal is to find the best solution from a set of feasible solutions. Techniques such as linear programming, dynamic programming , and evolutionary algorithms are commonly employed.

4. Machine Learning

Machine learning techniques allow AI systems to learn from data and improve their problem-solving abilities over time. Supervised, unsupervised, and reinforcement learning paradigms offer various approaches to adapt and enhance performance.

5. Natural Language Processing (NLP)

NLP enables AI to understand and process human language, making it invaluable for solving problems related to text analysis, sentiment analysis, and language translation. Techniques like tokenization, sentiment analysis, and named entity recognition play crucial roles in this domain.

Despite its advancements, AI problem-solving faces several challenges:

• Complexity : Some problems are inherently complex and require significant computational resources and time to solve.
• Data Quality : AI systems are only as good as the data they are trained on. Poor quality data can lead to inaccurate solutions.
• Interpretability : Many AI models, especially deep learning, act as black boxes, making it challenging to understand their decision-making processes.
• Ethics and Bias : AI systems can inadvertently reinforce biases present in the training data, leading to unfair or unethical outcomes.

Problem solving is a fundamental element of artificial intelligence, encompassing various techniques and strategies. By understanding the nature of problems, employing structured approaches, and utilizing effective agents, AI can navigate complex challenges and deliver optimal solutions. As AI continues to evolve, enhancing problem-solving capabilities will remain essential for advancing technology and improving human experiences.

Similar Reads

• Problem Solving in Artificial Intelligence Problem solving is a core aspect of artificial intelligence (AI) that mimics human cognitive processes. It involves identifying challenges, analyzing situations, and applying strategies to find effective solutions. This article explores the various dimensions of problem solving in AI, the types of p 6 min read
• Probabilistic Reasoning in Artificial Intelligence Probabilistic reasoning in Artificial Intelligence (AI) refers to the use of probability theory to model and manage uncertainty in decision-making processes. This approach is fundamental in creating intelligent systems that can operate effectively in complex, real-world environments where informatio 7 min read
• Artificial Intelligence in Robotics Artificial Intelligence (AI) in robotics is one of the most groundbreaking technological advancements, revolutionizing how robots perform tasks. What was once a futuristic concept from space operas, the idea of "artificial intelligence robots" is now a reality, shaping industries globally. Unlike ea 10 min read
• Turing Test in Artificial Intelligence The Turing Test is one of the most well-known and debated concepts in artificial intelligence (AI). It was proposed by the British mathematician and computer scientist Alan Turing in 1950 in his seminal paper, "Computing Machinery and Intelligence." He proposed that the "Turing test is used to deter 9 min read
• Game Playing in Artificial Intelligence Game playing has always been a fascinating domain for artificial intelligence (AI). From the early days of computer science to the current era of advanced deep learning systems, games have served as benchmarks for AI development. They offer structured environments with clear rules, making them ideal 4 min read
• Types of Reasoning in Artificial Intelligence In today's tech-driven world, machines are being designed to mimic human intelligence and actions. One key aspect of this is reasoning, a logical process that enables machines to conclude, make predictions, and solve problems just like humans. Artificial Intelligence (AI) employs various types of re 6 min read
• Understanding PEAS in Artificial Intelligence In Artificial Intelligence (AI), various types of agents operate to achieve specific goals. The PEAS system is a critical framework used to categorize these agents based on their performance, environment, actuators, and sensors. Understanding the PEAS system is essential for grasping how different A 7 min read
• Artificial Intelligence - Terminology Artificial Intelligence is a study to make computers, robots, generally, machines think how the intellect of humans works, think, learn when it solves any problem. This will affect software systems that are more intelligent than usual. The main objective of Artificial Intelligence is to enhance comp 2 min read
• Rationality in Artificial Intelligence (AI) Artificial Intelligence (AI) has rapidly advanced in recent years, transforming industries and reshaping the way we live and work. One of the core aspects of AI is its ability to make decisions and solve problems. This capability hinges on the concept of rationality. But what does rationality mean i 9 min read
• Artificial Intelligence(AI) in Tech Artificial Intelligence is defined as an intelligent notion that is transforming technology and reshaping how organizations initiate, progress, and communicate with their customers. AI is termed as the replication of human intelligence processes in machines to make it possible for the machines to wo 5 min read
• Characteristics of Artificial Intelligence Problems Problems in Artificial Intelligence (AI) come in different forms, each with its own set of challenges and potential for innovation. From image recognition to natural language processing, AI problems exhibit distinct characteristics that shape the strategies and techniques used to tackle them effecti 9 min read
• Emergent Properties in Artificial Intelligence Artificial intelligence (AI) has witnessed remarkable advancements in recent years, leading to the development of complex systems capable of performing tasks previously thought to be exclusive to human intelligence. One intriguing aspect of these AI systems is the emergence of properties that are no 6 min read
• Constraint Satisfaction Problems (CSP) in Artificial Intelligence Constraint Satisfaction Problems (CSP) play a crucial role in artificial intelligence (AI) as they help solve various problems that require decision-making under certain constraints. CSPs represent a class of problems where the goal is to find a solution that satisfies a set of constraints. These pr 14 min read
• Semantic Networks in Artificial Intelligence Semantic networks are a powerful tool in the field of artificial intelligence (AI), used to represent knowledge and understand relationships between different concepts. They are graphical representations that connect nodes (representing concepts) with edges (representing relationships). Semantic net 10 min read
• Era of Artificial Intelligence In the landscape of modern technology, Artificial Intelligence (AI) stands out as a transformative force, reshaping industries, enhancing human capabilities, and redefining the boundaries of what machines can achieve. From its conceptual beginnings to its current applications, AI has journeyed from 4 min read
• Mini-Max Algorithm in Artificial Intelligence The Min-Max algorithm is a foundational concept in artificial intelligence, particularly in game theory and strategic decision-making. This article delves into the Min-Max algorithm, exploring its fundamentals, working, and it's application. What is the Mini-Max Algorithm?The Mini-Max algorithm is a 8 min read
• The Real Power of Artificial Intelligence Artificial Intelligence (AI) is no longer an innovation in the technological domain; it is a revolutionary advancement affecting several industries, societies, and even the human way of thinking. AI's power lies in its efficient computation capabilities and ability to enhance and amplify human cogni 9 min read
• Types of Artificial Intelligence (AI) Artificial Intelligence refers to something which is made by humans or non-natural things and Intelligence means the ability to understand or think. AI is not a system but it is implemented in the system. There are many different types of AI, each with its own strengths and weaknesses. This article 6 min read
• Top 10 branches of Artificial Intelligence Artificial intelligence (AI) is the leading component of innovation and serves as a tool that imitates human thinking. The branches of AI encompass machine learning and auto-robots, which include self-driving cars, smart homes, virtual personal assistants, and other automated systems. These AI syste 5 min read

Improve your Coding Skills with Practice

What kind of Experience do you want to share?