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

Artificial Intelligence, cognition, machine learning, Robotics, automation

This is not my publication just upload to help others

## RELATED PAPERS

The Knowledge Engineering Review

Lecture Notes in Computer Science

Proceedings of the 2010 Spring Simulation Multiconference on - SpringSim '10

Journal of Artificial Intelligence Research

International Journal of Scientific Research in Science, Engineering and Technology IJSRSET

GLOBAL JOURNAL OF ENGINEERING SCIENCE AND RESEARCHES

International Journal of Scientific Research in Science, Engineering and Technology

## RELATED TOPICS

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

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

## Artificial Intelligence Chapter 3: Solving Problems by Searching

- 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

## Solving problems by searching

## Presentation Transcript

Solving problems by searching Chapter 3 Blind Search

Problem-solving agents Blind Search

Example: vacuum world • Single-state, start in #5. Solution? Blind Search

Vacuum world state space graph • states? • actions? • goal test? • path cost? Blind Search

Example: The 8-puzzle • states? • actions? • goal test? • path cost? Blind Search

Tree search example Blind Search

Implementation: general tree search 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 Artiﬁcial Intelligence - Intelligent Agents Well-Deﬁned 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.