problem solving state space search and control strategies ppt

State Space Search in Artificial Intelligence

State space search is a problem-solving technique used in Artificial Intelligence (AI) to find the solution path from the initial state to the goal state by exploring the various states. The state space search approach searches through all possible states of a problem to find a solution. It is an essential part of Artificial Intelligence and is used in various applications, from game-playing algorithms to natural language processing.

Introduction

A state space is a way to mathematically represent a problem by defining all the possible states in which the problem can be. This is used in search algorithms to represent the initial state, goal state, and current state of the problem. Each state in the state space is represented using a set of variables.

The efficiency of the search algorithm greatly depends on the size of the state space, and it is important to choose an appropriate representation and search strategy to search the state space efficiently.

One of the most well-known state space search algorithms is the A algorithm. Other commonly used state space search algorithms include breadth-first search (BFS) , depth-first search (DFS) , hill climbing , simulated annealing , and genetic algorithms .

Features of State Space Search

State space search has several features that make it an effective problem-solving technique in Artificial Intelligence. These features include:

Exhaustiveness: State space search explores all possible states of a problem to find a solution.

Completeness: If a solution exists, state space search will find it.

Optimality: Searching through a state space results in an optimal solution.

Uninformed and Informed Search: State space search in artificial intelligence can be classified as uninformed if it provides additional information about the problem.

In contrast, informed search uses additional information, such as heuristics, to guide the search process.

Steps in State Space Search

The steps involved in state space search are as follows:

• To begin the search process, we set the current state to the initial state.
• We then check if the current state is the goal state. If it is, we terminate the algorithm and return the result.
• If the current state is not the goal state, we generate the set of possible successor states that can be reached from the current state.
• For each successor state, we check if it has already been visited. If it has, we skip it, else we add it to the queue of states to be visited.
• Next, we set the next state in the queue as the current state and check if it's the goal state. If it is, we return the result. If not, we repeat the previous step until we find the goal state or explore all the states.
• If all possible states have been explored and the goal state still needs to be found, we return with no solution.

State Space Representation

State space Representation involves defining an INITIAL STATE and a GOAL STATE and then determining a sequence of actions, called states, to follow.

• State: A state can be an Initial State, a Goal State, or any other possible state that can be generated by applying rules between them.
• Space: In an AI problem, space refers to the exhaustive collection of all conceivable states.
• Search: This technique moves from the beginning state to the desired state by applying good rules while traversing the space of all possible states.
• Search Tree: To visualize the search issue, a search tree is used, which is a tree-like structure that represents the problem. The initial state is represented by the root node of the search tree, which is the starting point of the tree.
• Transition Model: This describes what each action does, while Path Cost assigns a cost value to each path, an activity sequence that connects the beginning node to the end node. The optimal option has the lowest cost among all alternatives.

Example of State Space Search

The 8-puzzle problem is a commonly used example of a state space search. It is a sliding puzzle game consisting of 8 numbered tiles arranged in a 3x3 grid and one blank space. The game aims to rearrange the tiles from their initial state to a final goal state by sliding them into the blank space.

To represent the state space in this problem, we use the nine tiles in the puzzle and their respective positions in the grid. Each state in the state space is represented by a 3x3 array with values ranging from 1 to 8 , and the blank space is represented as an empty tile.

The initial state of the puzzle represents the starting configuration of the tiles, while the goal state represents the desired configuration. Search algorithms utilize the state space to find a sequence of moves that will transform the initial state into the goal state.

This algorithm guarantees a solution but can become very slow for larger state spaces. Alternatively, other algorithms, such as A search , use heuristics to guide the search more efficiently.

Our objective is to move from the current state to the target state by sliding the numbered tiles through the blank space. Let's look closer at reaching the target state from the current state.

To summarize, our approach involved exhaustively exploring all reachable states from the current state and checking if any of these states matched the target state.

Applications of State Space Search

• State space search algorithms are used in various fields, such as robotics, game playing, computer networks, operations research, bioinformatics, cryptography, and supply chain management. In artificial intelligence, state space search algorithms can solve problems like pathfinding , planning , and scheduling .
• They are also useful in planning robot motion and finding the best sequence of actions to achieve a goal. In games, state space search algorithms can help determine the best move for a player given a particular game state.
• State space search algorithms can optimize routing and resource allocation in computer networks and operations research.
• In Bioinformatics , state space search algorithms can help find patterns in biological data and predict protein structures.
• In Cryptography , state space search algorithms are used to break codes and find cryptographic keys.
• State Space Search is a problem-solving technique used in AI to find a solution to a problem by exploring all possible states of the problem.
• It is an exhaustive, complete, and optimal search process that can be classified as uninformed or informed.
• State Space Representation is a crucial step in the state space search process as it determines the efficiency of the search algorithm.
• State space search in artificial intelligence has several applications, including game-playing algorithms, natural language processing, robotics, planning, scheduling, and computer vision.

Lecture 2: Problem Solving using State Space Representation

Nov 19, 2014

270 likes | 498 Views

Lecture 2: Problem Solving using State Space Representation. CS 271: Fall, 2008. Problem-Solving Agents. Intelligent agents can solve problems by searching a state-space State-space Model the agent’s model of the world usually a set of discrete states

Share Presentation

• state space
• traveling salesperson
• problem abstraction
• 8 puzzle problem
• state space search framework

Presentation Transcript

Lecture 2: Problem Solving using State Space Representation CS 271: Fall, 2008

Problem-Solving Agents • Intelligent agents can solve problems by searching a state-space • State-space Model • the agent’s model of the world • usually a set of discrete states • e.g., in driving, the states in the model could be towns/cities • Goal State(s) • a goal is defined as a desirable state for an agent • there may be many states which satisfy the goal test • e.g., drive to a town with a ski-resort • or just one state which satisfies the goal • e.g., drive to Mammoth • Operators (actions, successor function) • operators are legal actions which the agent can take to move from one state to another

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

Example: Romania

Problem types • Static / Dynamic Previous problem was static: no attention to changes in environment • Observable / Partially Observable / Unobservable Previous problem was observable: it knew its initial state. • Deterministic / Stochastic Previous problem was deterministic: no new percepts were necessary, we can predict the future perfectly • Discrete / continuous Previous problem was discrete: we can enumerate all possibilities

State-Space Problem Formulation A problem is defined by four items: initial statee.g., "at Arad“ actions or successor functionS(x) = set of action–state pairs • e.g., S(Arad) = {<Arad  Zerind, Zerind>, … } goal test, (or goal state) e.g., x = "at Bucharest”, 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

Defining Search Problems • A statement of a Search problem has 4 components • 1. A set of states • 2. A set of “operators” which allow one to get from one state to another • 3. A start state S • 4. A set of possible goal states, or ways to test for goal states • 4a. Cost path • A solution consists of • a sequence of operators which transform S into a goal state G • Representing real problems in a State-Space search framework • may be many ways to represent states and operators • key idea: represent only the relevant aspects of the problem (abstraction)

Abstraction/Modeling Process of removing irrelevant detail to create an abstract representation: ``high-level”, ignores irrelevant details • Definition of Abstraction: • Navigation Example: how do we define states and operators? • First step is to abstract “the big picture” • i.e., solve a map problem • nodes = cities, links = freeways/roads (a high-level description) • this description is an abstraction of the real problem • Can later worry about details like freeway onramps, refueling, etc • Abstraction is critical for automated problem solving • must create an approximate, simplified, model of the world for the computer to deal with: real-world is too detailed to model exactly • good abstractions retain all important details

Robot block world • Given a set of blocks in a certain configuration, • Move the blocks into a goal configuration. • Example : • (c,b,a)  (b,c,a) A A Move (x,y) B C C B

Operator Description

The state-space graph • Graphs: • nodes, arcs, directed arcs, paths • Search graphs: • States are nodes • operators are directed arcs • solution is a path from start to goal • Problem formulation: • Give an abstract description of states, operators, initial state and goal state. • Problem solving activity: • Generate a part of the search space that contains a solution

C B A D F E The Traveling Salesperson Problem (a touring problem) • Find the shortest tour that visits all cities without visiting any city twice and return to starting point. • States: sequence of cities visited • S0 = A • SG = a complete tour

Example: 8-queen problem

Example: 8-Queens • states?-any arrangement of n<=8 queens -or arrangements of n<=8 queens in leftmost n columns, 1 per column, such that no queen attacks any other. • initial state? no queens on the board • actions?-add queen to any empty square -or add queen to leftmost emptysquare such that it is not attacked by other queens. • goal test?8 queens on the board, none attacked. • path cost? 1 per move

The sliding tile problem 8-puzzle: 181,440 states 15-puzzle: 1.3 trilion 24-puzzle: 10^25

The Sliding Tile Problem Up Down Left Right

The “8-Puzzle” Problem Start State 1 2 3 4 6 7 5 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 Goal State

Formulating Problems;another angle • Problem types • Satisficing: 8-queen • Optimizing: Traveling salesperson • Object sought • board configuration, • sequence of moves • A strategy (contingency plan) • Satisfying leads to optimizing since “small is quick” • For traveling salesperson • satisficing easy, optimizing hard • Semi-optimizing: • Find a good solution • In Russel and Norvig: • single-state, multiple states, contingency plans, exploration problems

Searching the State Space • States, operators, control strategies • The search space graph is implicit • The control strategy generates a small search tree. • Systematic search • Do not leave any stone unturned • Efficiency • Do not turn any stone more than once

Tree search example

State space of the 8 puzzle problem

Why Search can be difficult • At the start of the search, the search algorithm does not know • the size of the tree • the shape of the tree • the depth of the goal states • How big can a search tree be? • say there is a constant branching factor b • and one goal exists at depth d • search tree which includes a goal can havebd different branches in the tree (worst case) • Examples: • b = 2, d = 10: bd = 210= 1024 • b = 10, d = 10: bd = 1010= 10,000,000,000

Summary • Intelligent agents can often be viewed as searching for problem solutions in a discrete state-space • Space obtained through a problem abstraction process. • Search consists of • state space • operators • start state • goal states • A Search Tree is an efficient way to represent a search • There are a variety of general search techniques, including • Depth-First Search • Breadth-First Search • we will look at several others in the next few lectures • Assigned Reading: Nillson chapter 7 chapter 8 • R&N Chapter 3

• More by User

Problem Solving Techniques

Problem Solving Techniques. MST326 lecture 3. Outline of lecture. Brainstorming Mind maps Cause-and-Effect diagrams Failures Mode and Effects Analysis Fault Tree Analysis Design of Experiments. Brainstorming. proposed by Alex Osborn “for the sole purpose of producing checklists of ideas”

1.78k views • 37 slides

SP 215 Small Group Communication Structured and Creative Problem Solving in Groups

SP 215 Small Group Communication Structured and Creative Problem Solving in Groups. Problem Solving -A process in which groups analyze a problem and develop a plan of action for solving the problem or reducing its harmful effects. Decision Making

1.47k views • 62 slides

PROBLEM SOLVING WITH THE MCKINSEY METHOD

PROBLEM SOLVING WITH THE MCKINSEY METHOD. MCKINSEY PROBLEM SOLVING APPROACH. Focus of today’s discussion. Managing Team Client Self. Leadership Vision Inspiration Delegation. Business Need Competitive Organizational Financial Operational. Implementation Dedication

3.57k views • 23 slides

Clinical Problem Solving Strategies

Clinical Problem Solving Strategies. Placebo effects. Placebo is Latin for “I will please” Refers to any type of treatment that is inert Used in research trials to objectively test the efficacy of new treatments

1.28k views • 88 slides

Problem-Solving/RtI: Implementing an Intervention Data Collection System with Integrity

Problem-Solving/RtI: Implementing an Intervention Data Collection System with Integrity. NASP Annual Convention New Orleans, LA George M. Batsche Professor and Co-Director Institute for School Reform Florida Problem-Solving RtI Statewide Project Jose’ M. Castillo PS/RtI Project Evaluator

1.2k views • 104 slides

Primary 3/4 Mathematics Workshop For Parents

Primary 3/4 Mathematics Workshop For Parents. 14 April 2012. Workshop Outline. Introduction to Problem-Solving Model Method 3 Different types of Models 4 different Heuristics Format of assessment. Problem-solving Approach . Understand the Problem (Understand) Devise a Plan (Plan)

1.26k views • 112 slides

Collaborative Problem Solving

Collaborative Problem Solving. An Approach to Helping Explosive Students with Challenging Behaviour. By Ron Teffaine, M.Ed., CSC. Agenda for Today. 9:00 am - 10:15 am CPS (theory, research, tools) 10:15 am - 10:20 am Nutrition Break 10:20 am - 11:30 am CPS (Plan A, C, B)

1.72k views • 67 slides

Complex problem solving (CPS) definition

Latent Problem Solving Analysis (LPSA): A computational theory of representation in complex, dynamic problem solving tasks. Complex problem solving (CPS) definition.

1.36k views • 113 slides

Splash Screen

Chapter 9 Percent Click the mouse or press the space bar to continue. Splash Screen. Percent. 9. Lesson 9-1 Percents and Fractions Lesson 9-2 Circle Graphs Lesson 9-3 Percents and Decimals Lesson 9-4 Problem-Solving Strategy: Solve a Simpler Problem Lesson 9-5 Estimating with Percents

2.14k views • 191 slides

Solving problems by searching

Solving problems by searching. Chapter 3 in AIMA. Problem Solving. Rational agents need to perform sequences of actions in order to achieve goals. Intelligent behavior can be generated by having a look-up table or reactive policy that tells the agent what to do in every circumstance, but:

1.29k views • 105 slides

Outline: Problem solving and search

Outline: Problem solving and search. Introduction to Problem Solving Complexity Uninformed search Problem formulation Search strategies: depth-first, breadth-first Informed search Search strategies: best-first, A* Heuristic functions. 9 l. 5 l. 3 l. Example: Measuring problem!.

1.77k views • 145 slides

Solution Strategies 1. PROGRAMMING WITH MATLAB

Solution Strategies 1. PROGRAMMING WITH MATLAB. MATLAB Fundamentals. MATLAB. Matrix Laboratory. Problem-Solving Methodology. State the problem clearly Describe the Input/Output (I/O) Work the problem by hand Algorithm - Numerical Method Develop a MATLAB Solution Debugging and Testing

1.43k views • 121 slides

The TEAM FOCUS Framework for Team Problem Solving

The TEAM FOCUS Framework for Team Problem Solving. Confidential material from the book: The McKinsey Engagement: A Powerful Toolkit for More Efficient and Effective Team Problem Solving. Introduction to TEAM FOCUS. Table of Contents. The Framework (TEAM FOCUS)

1.34k views • 82 slides

PROBLEM-SOLVING

PROBLEM-SOLVING. GENERAL GUIDELINES. GENERAL PROBLEM SOLVING STRATEGY Solving problems require three major steps: Prepare Solve Assess. PREPARE

1.21k views • 94 slides

Basics Menu

Basics Menu. Learning Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . page 2 Problem Solving Steps in the Problem Solving Process . . . . . . . . . . . . . . . . . . page 3

951 views • 85 slides

Chapter 8. Three-Dimensional Object Representations

Chapter 8. Three-Dimensional Object Representations. Solid objects representation scheme. Boundary representation (B-reps) three-dimensional objects 를 , 물체의 내부와 외부를 분리하는 surface 의 집합으로 표현하는 것 전형적인 예로 polygon facets 와 spline patches 가 있음 Space-Partitioning representation

1.01k views • 74 slides

Chapter 2 Measurement and Problem Solving

Chapter 2 Measurement and Problem Solving. Book Ch 03 Scientific measurement. 2009, Prentice Hall. What Is a Measurement?. Quantitative observation. Comparison to an agreed upon standard. Every measurement has a number and a unit. A Measurement.

1.6k views • 96 slides

1.34k views • 23 slides

• 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.

Problems, Problem Spaces and Search. Contents Defining the problem as a State Space Search Production Systems Control Strategies Breadth First Search.

Published by Holly Lambert Modified over 8 years ago

Similar presentations

Presentation on theme: "Problems, Problem Spaces and Search. Contents Defining the problem as a State Space Search Production Systems Control Strategies Breadth First Search."— Presentation transcript:

Problems and Search Chapter 2.

Review: Search problem formulation

Heuristic Search techniques

Presentation on Artificial Intelligence

AI Pathfinding Representing the Search Space

1 State-Space representation and Production Systems Introduction: what is State-space representation? What are the important trade-offs? (E.Rich, Chapt.2)

Ch 4. Heuristic Search 4.0 Introduction(Heuristic)

PROBLEM SOLVING AND SEARCH

Types of Algorithms.

ICS-171:Notes 4: 1 Notes 4: Optimal Search ICS 171 Summer 1999.

Part2 AI as Representation and Search

CSC 423 ARTIFICIAL INTELLIGENCE

1 Pertemuan 2 PROBLEMS, PROBLEM SPACES, AND SEARCH Matakuliah: T0264/Inteligensia Semu Tahun: 2005 Versi: 1/0.

Best-First Search: Agendas

Problem Solving and Search in AI Part I Search and Intelligence Search is one of the most powerful approaches to problem solving in AI Search is a universal.

Algorithm Strategies Nelson Padua-Perez Chau-Wen Tseng Department of Computer Science University of Maryland, College Park.

Using Search in Problem Solving

State-Space Searches.

About project

© 2024 SlidePlayer.com Inc. All rights reserved.