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
Artificial Intelligence: Session 3 Problem Solving Agent and searching for solutions
2023, Asst.Prof.M. Gokilavani
Related Papers
Hassan Sebak
Artificial Intelligence, cognition, machine learning, Robotics, automation
Diego Villa
Othar Hansson
This dissertation describes several advances to the theory and practice of artificial intelligence scheduling and constraint-satisfaction techniques. I have developed and implemented these techniques during the construction of DTS, the Decision-Theoretic Scheduler, and its successor, SchedKit, a toolkit of scheduling algorithms and data structures. The dissertation describes and analyzes the three orthogonal approaches to improving a scheduler's performance. These are: (1) reducing the size of the state space to be searched, (2) reducing the per state cost of state generation and evaluation, and (3) reducing the number of states examined by selective search. To reduce the size of the state space. I have developed several new preprocessing algorithms designed to exploit resource constraints, including resource capacity and resource/task compatibility. Experiments show that it is possible to exploit resource capacity constraints efficiently despite their inherently disjunctive nat...
Saniya Ali Khan
This is not my publication just upload to help others
Sdiwc Conferences
Antim Deshwal
Solving a problem mean looking for a solution, which is best among others. Finding a solution to a problem in Computer Science and Artificial Intelligence is often thought as a process of search through the space of possible solutions. On the other hand in Engineering and Mathematics it is thought as a process of optimization i.e. to find a best solution or an optimal solution for a problem. These reduce search space and improve its efficiency. At each and every step of search,it select which have the least futility. In this paper ,We categorize the different AI search and optimization techniques in a tabular form on the basis of their merits and demerits to make it easy to choose a technique for a particular problem.
Rana Umar Draz
DIRECTORATE OF DISTANCE EDUCATION B. Com. FIRST YEAR S. NO. PAPER CODE PAPER NO. PAPER NAME 1. 1DBCOM1 I FUNDAMENTALS OF MAHARISHI VEDIC SCIENCE (MAHARISHI VEDIC SCIENCE –I) FOUNDATION COURSE 2. 1DBCOM2 II HINDI LANGUAGE 3. 1DBCOM3 III ENGLISH LANGUAGE 4. 1DBCOM4 IV DEVELOPMENT OF ENTREPRENEURSHIP ACCOUNTING GROUP 5. 1DBCOM5 V FINANCIAL ACCOUNTING 6. 1DBCOM6 VI BUSINESS MATHEMATICS BUSINESS MANAGEMENT 7. 1DBCOM7 VII BUSINESS COMMUNICATION 8. 1DBCOM8 VIII BUSINESS REGULATORY FRAMEWORK APPLIED ECONOMICS 9. 1DBCOM9 IX BUSINESS ECONOMICS 10. 1DBCOM10 X BUSINESS ENVIRONMENT
RELATED PAPERS
Thiên Nguyễn Bá
Shamsul Arefin
The Knowledge Engineering Review
Miguel Salido
Dietmar Seipel
Lecture Notes in Computer Science
Vitor Nogueira
Luís Moniz Pereira
Procs. 18th Intl. Conf. on Applications of Declarative Programming and Knowledge Management (INAP’09)
Salvador Abreu
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
… on Principles and …
Federico Barber
Moura Pires
Proceedings of the 2010 Spring Simulation Multiconference on - SpringSim '10
Shouhuai Xu
Journal of Artificial Intelligence Research
Shaul Markovitch
Marco Bottalico
israel carlos
SDIWC Organization
Stefano Bistarelli
Garima Srivastava
Knowledge-Based Systems
Victoria López
International Journal of Scientific Research in Science, Engineering and Technology IJSRSET
PRASHANT KUMAR
GLOBAL JOURNAL OF ENGINEERING SCIENCE AND RESEARCHES
Edmund Durfee
International Journal of Scientific Research in Science, Engineering and Technology
Haissam El-aawar
PriyAanshH Gupta
samir tetouani
RELATED TOPICS
- We're Hiring!
- Help Center
- Find new research papers in:
- Health Sciences
- Earth Sciences
- Cognitive Science
- Mathematics
- Computer Science
- Academia ©2023
- 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.
Solving problems by searching
Solving problems by searching. Chapter 3. Outline. Problem-solving agents Problem types Problem formulation Example problems Basic search algorithms. Problem-solving agents. Example: Romania. On holiday in Romania; currently in Arad. Flight leaves tomorrow from Bucharest
- tree search
- tree search algorithms
- single state problem formulation
- More by User
Presentation Transcript
Solving problems by searching Chapter 3 Blind Search
Outline • Problem-solving agents • Problem types • Problem formulation • Example problems • Basic search algorithms Blind Search
Problem-solving agents Blind Search
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: • sequence of cities, e.g., Arad, Sibiu, Fagaras, Bucharest Blind Search
Example: Romania Blind Search
Problem types • Deterministic, fully observablesingle-state problem • Agent knows exactly which state it will be in; solution is a sequence • Non-observable sensorless problem (conformant problem) • Agent may have no idea where it is; solution is a sequence • Nondeterministic and/or partially observable contingency problem • percepts provide new information about current state • often interleave} search, execution • Unknown state space exploration problem Blind Search
Example: vacuum world • Single-state, start in #5. Solution? Blind Search
Example: vacuum world • Single-state, start in #5. Solution?[Right, Suck] • Sensorless, start in {1,2,3,4,5,6,7,8}e.g., Right goes to {2,4,6,8} Solution? Blind Search
Example: vacuum world • Sensorless, start in {1,2,3,4,5,6,7,8}e.g., Right goes to {2,4,6,8} Solution?[Right,Suck,Left,Suck] • Contingency • Nondeterministic: Suck may dirty a clean carpet • Partially observable: location, dirt at current location. • Percept: [L, Clean], i.e., start in #5 or #7Solution? Blind Search
Example: vacuum world • Sensorless, start in {1,2,3,4,5,6,7,8}e.g., Right goes to {2,4,6,8} Solution?[Right,Suck,Left,Suck] • Contingency • Nondeterministic: Suck may dirty a clean carpet • Partially observable: location, dirt at current location. • Percept: [L, Clean], i.e., start in #5 or #7Solution?[Right, if dirt then Suck] Blind Search
Single-state problem formulation A problem is defined by four items: • initial state e.g., "at Arad" • actions or successor functionS(x) = set of action–state pairs • e.g., S(Arad) = {<Arad Zerind, Zerind>, … } • goal test, can be • explicit, e.g., x = "at Bucharest" • implicit, e.g., Checkmate(x) • path cost (additive) • e.g., sum of distances, number of actions executed, etc. • c(x,a,y) is the step cost, assumed to be ≥ 0 • A solution is a sequence of actions leading from the initial state to a goal state Blind Search
Selecting a state space • Real world is absurdly complex state space must be abstracted for problem solving • (Abstract) state = set of real states • (Abstract) action = complex combination of real actions • e.g., "Arad Zerind" represents a complex set of possible routes, detours, rest stops, etc. • For guaranteed realizability, any real state "in Arad“ must get to some real state "in Zerind" • (Abstract) solution = • set of real paths that are solutions in the real world • Each abstract action should be "easier" than the original problem Blind Search
Vacuum world state space graph • states? • actions? • goal test? • path cost? Blind Search
Vacuum world state space graph • states?integer dirt and robot location • actions?Left, Right, Suck • goal test?no dirt at all locations • path cost?1 per action Blind Search
Example: The 8-puzzle • states? • actions? • goal test? • path cost? Blind Search
Example: The 8-puzzle • states?locations of tiles • actions?move blank left, right, up, down • goal test?= goal state (given) • path cost? 1 per move [Note: optimal solution of n-Puzzle family is NP-hard] Blind Search
Example: robotic assembly • states?: real-valued coordinates of robot joint angles parts of the object to be assembled • actions?: continuous motions of robot joints • goal test?: complete assembly • path cost?: time to execute Blind Search
Tree search algorithms • Basic idea: • offline, simulated exploration of state space by generating successors of already-explored states (a.k.a.~expanding states) Blind Search
Tree search example Blind Search
Implementation: general tree search Blind Search
Implementation: states vs. nodes • A state is a (representation of) a physical configuration • A node is a data structure constituting part of a search tree includes state, parent node, action, path costg(x), depth • The Expand function creates new nodes, filling in the various fields and using the SuccessorFn of the problem to create the corresponding states. Blind Search
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 ∞) Blind Search
Uninformed search strategies • Uninformed search strategies use only the information available in the problem definition • Breadth-first search • Uniform-cost search • Depth-first search • Depth-limited search • Iterative deepening search Blind Search
Breadth-first search • Expand shallowest unexpanded node • Implementation: • fringe is a FIFO queue, i.e., new successors go at end Blind Search
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) Blind Search
Uniform-cost search • Expand least-cost unexpanded node • Implementation: • fringe = queue ordered by path cost • Equivalent to breadth-first if step costs all equal • Complete? Yes, if step cost ≥ ε • Time? # of nodes with g ≤ cost of optimal solution, O(bceiling(C*/ ε)) where C* is the cost of the optimal solution • Space? # of nodes with g≤ cost of optimal solution, O(bceiling(C*/ ε)) • Optimal? Yes – nodes expanded in increasing order of g(n) Blind Search
Depth-first search • Expand deepest unexpanded node • Implementation: • fringe = LIFO queue, i.e., put successors at front Blind Search
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 Blind Search
Depth-limited search = depth-first search with depth limit l, i.e., nodes at depth l have no successors • Recursive implementation: Blind Search
Iterative deepening search Blind Search
Iterative deepening search l =0 Blind Search
Iterative deepening search l =1 Blind Search
Iterative deepening search l =2 Blind Search
Iterative deepening search l =3 Blind Search
IMAGES
VIDEO
COMMENTS
CPE/CSC 580-S06 Artificial Intelligence - Intelligent Agents Well-Defined Problems exact formulation of problems and solutions initial state current state / set of states, or the state at the beginning of the problem-solving process must be known to the agent operator description of an action state space set of all states reachable from the ...
Outline Problem-solving agents Problem types Problem formulation Example problems Basic search algorithms Problem-solving agents Problem solving agents are Goal-based Agents. Goal Formulation set of (desirable) world states. ... PowerPoint Presentation Last modified by: Carla Gomes Created Date: 1/1/1601 12:00:00 AM
14 Jan 2004 CS 3243 - Blind Search Solving problems by searching Chapter 3 Outline Problem-solving agents Problem types Problem formulation Example problems Basic search algorithms Problem-solving agents Example: Romania On holiday in Romania; currently in Arad. Flight leaves tomorrow from Bucharest Formulate goal: be in Bucharest
Problem solving agents. problem solving agents 9 Problem Solving An import application of Artificial Intelligence is Problem Solving. Define problem statement first. Generating the solution by keeping the different condition in mind. Searching is the most commonly used technique of problem solving in artificial intelligence.; Problem Solving Agents: A problem-solving agent is a goal-driven ...
Problem-Solving Agents This is a kind of goal-based agents that decide what to do by finding sequences of actions that lead to desirable states. Formulating problems Example problems Searching for solutions A simple problem-solving agent Goal formulation - limiting the objectives A goal is a set of world states in which the goal is satisfied. ...
Problem-Solving Agents This is a kind of goal-based agents that decide what to do by finding sequences of actions that lead to desirable states. Some problems cannot be solved by reflex agents Formulating problems Example problems Searching for solutions A simple problem-solving agent Goal formulation - limiting the objectives (for any task, we ...
Problem Solving agents. Formulate Goal Search for a solution Execute the solution. Formulation problems. Knowledge and problem types Single State problem Multiple State problem Contingency problem Interleaving Exploration problem Well-defined problems Initial state Uploaded on Sep 02, 2014 Fraley Keagan + Follow search goal state
A problem solving agent is one which decides what actions and states to consider in completing a goal Examples: Finding the shortest path from one city to another 8-puzzle. Problem Solving Agents. 8-Puzzle Action: Move blank square up, down, left, or right Uploaded on Jul 16, 2014 Elwyn Green + Follow time complexity agents possible belief states
SRI SHAKTHI INSTITUTE OF ENGINEERING & TECHNOLOGY Problem-solving agent • Problem-solving agent • A kind of goal-based agent - Choose their actions in order to achieve Goals. • This Allows the Agent to a way of Choosing among Multiple Possibilities, selecting the one which reaches a Goal states.
1 / 77 Problem Solving Agents 113 Views Download Presentation Solving Problems by Searching (Blindly) R&N: Chap. 3 (many of these slides borrowed from Stanford's AI Class). Problem Solving Agents. Decide what to do by finding a sequence of actions that lead to desirable states. Example: Romania On holiday in Romania; currently in Arad.
Bayesian problem-solving applied to scheduling 1998 • Othar Hansson This dissertation describes several advances to the theory and practice of artificial intelligence scheduling and constraint-satisfaction techniques.
Disciple approach: Develop learning and problem solving agents that can be taught by subject matter experts to become knowledge-based assistants. The agent learns from the expert, building, verifying and improving its knowledge base. ... PowerPoint Presentation Author: Learning Agents Laboratory Last modified by: GheorgheTecuci Created Date: 10 ...
Solving Problems by Searching Reflex agent is simple base their actions on a direct mapping from states to actions but cannot work well in environments which this mapping would be too large to store and would take too long to learn Hence, goal-based agent is used Problem-solving agent Problem-solving agent A kind of goal-based agent It solves ...
Problem Solving 1 of 173 Problem Solving Jan. 21, 2019 • • 7,942 views Download to read offline Engineering In which we see how an agent can find a sequence of actions that achieves its goals, when no single action will do.
Problem Solving Agents Description: Sometimes reflex fails because the world is complex. ... On holiday in Romania; currently in Arad. Flight leaves tomorrow from Bucharest. Formulate goal: ... - PowerPoint PPT presentation Number of Views:108 Avg rating:3.0/5.0 Slides: 31 Provided by: systema178 Category: Tags:agents| problem| solving moreless
Title: Solving problems by searching Last modified by: Diane Litman Document presentation format: On-screen Show Other titles: Times New Roman Tahoma Arial Unicode MS Wingdings Arial Courier New r MS Pゴシック Comic Sans MS Default Design Default Design Solving problems by searching Outline Goal-based Agents Goal-based Agents Goal-based Agents Problem Solving as Search Problem-solving ...
Download 1 / 131 UNIT 2 : AI Problem Solving 1098 Views Download Presentation 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.
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) 3 Goal Based Agent
Artificial Intelligence 3. Search in Problem Solving. Course V231 Department of Computing Imperial College, London Jeremy Gow. Problem Solving Agents. Looking to satisfy some goal Wants environment to be in particular state Have a number of possible actions An action changes environment. Updated on Apr 05, 2019. Teige Fox.
with Problem Solving in the Moment There are five steps to enhance problem-solving skills: 1. Anticipate—plan ahead 2. Proximity—be close to prompt children through problem-solving steps 3. Support—without solving the problem for the children, use tools to remind 4. Encourage—good solutions don't always work, encourage to keep trying 5.
While downloading, if for some reason you are not able to download a presentation, the publisher may have deleted the file from their server. Solving Problems by Searching - . cps 4801-01. outline. problem-solving agents example problems basic search algorithms.