problem solving state space search in ai

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.

What Is State Space Search?

Last updated: June 5, 2024

• Artificial Intelligence

1. Overview

In this tutorial, we’ll discuss the state space search concept in detail with an example.

Furthermore, we’ll present several applications where we can use this concept.

2. State Space Search

A state space is a mathematical representation of a problem that defines all possible states that the problem can be in. Furthermore, in search algorithms, we use a state space to represent the current state of the problem, the initial state, and the goal state. Additionally, we represent each state in the state space by a set of variables.

State space search is a method used widely in artificial intelligence and computer science to find a solution to a problem by searching through the set of possible states of the problem. Furthermore, a state space search algorithm uses the state space to navigate from the initial state to the goal state. Additionally, it generates and explores possible successors of the current state until we find a solution.

The state space size can greatly affect a search algorithm’s efficiency. Hence, it’s important to choose an appropriate representation and search strategy to efficiently search the state space.

The most famous state space search algorithm is the A* algorithm . Other popular state space search algorithms are breadth-first search (BFS) , depth-first search (DFS) , hill climbing , simulated annealing , and genetic algorithms .

Now let’s discuss the steps of a typical state space search algorithm:

The first step is to initialize the search by setting the initial state as the current state. After the initialization step, we check if the current state is a goal state. Finally, if the current state is a goal state, we terminate the algorithm and return the result.

However, if the current state is not the goal state, we generate the set of possible states that can be reached from the current state. Additionally, these states are known as successor states. Furthermore, for each successor state, we check if it has been previously visited. If the state is already explored, we skip the state. If it has not been visited, we add it to the queue of states to be visited.

Moving forward, we set the next state in the queue as the current state and check if it’s a goal state. If we find the goal state, we return the result. Otherwise, we repeat the previous step until we find the goal state or finish exploring all the states. Furthermore, if all possible states have been explored and we can’t reach the target state, we return with no solution.

The specific implementation details of the algorithm depend on the problem. Additionally, the algorithm’s performance depends on the data structures we use to represent the states and keep track of the search.

The initial state represents the starting configuration of the tiles. The goal state represents the desired configuration. Furthermore, the search algorithms use the state space to find a sequence of moves that transform the initial state into the goal state.

For example, we can use the breadth-first search to explore all possible states reachable from the initial state. It explores all the states one by one in a sequence. It ensures the solution but can become very slow for large state spaces. Other algorithms, such as A* search, use heuristics to guide the search more efficiently.

We’re taking a practical example of an 8-puzzle problem. Let’s pick current and target states for this example:

Here, we aim to start from the current state and reach the target state by sliding the numbers through the bank. Furthermore, the approach is to explore all the states we can reach from the current state. For each new state, we check if it’s the target state or not. Let’s take a look at how to reach the target state from the current state:

5. Applications

State space search algorithms have a wide range of applications in various fields, including artificial intelligence, robotics, game playing, computer networks, operations research, bioinformatics, cryptography, and supply chain management.

In artificial intelligence, we can use state space search algorithms to solve problems such as pathfinding , planning , and scheduling . Additionally, we can employ space search algorithms to plan the motion of robots, determining the best sequence of actions to achieve a goal. Furthermore, we also use these algorithms in games to determine the best move for a player, given a particular game state.

In computer networks, we can take advantage of state space search algorithms to optimize routing and resource allocation in computer networks. Additionally, we also use them in operations research to solve optimization problems , such as scheduling and resource allocation. We can also apply these algorithms to find patterns in biological data and predict protein structures in bioinformatics.

In order to find solutions to cryptographic problems , such as breaking codes and finding cryptographic keys, we can employ these algorithms. Furthermore, we can use these algorithms to optimize the flow of goods and resources in logistics and supply chain management.

These are just a few examples of the many applications of state space search algorithms. The ability to efficiently search large state spaces and find solutions to complex problems makes state space search algorithms a powerful tool in a wide range of fields.

6. Conclusion

In this tutorial, we discussed the state space search concept in detail with an example. Furthermore, we explored different fields and applications where it can be extremely useful.

David L. Poole & Alan K. Mackworth

Artificial Intelligence 3E

foundations of computational agents

3.2 State Spaces

One general formulation of intelligent action is in terms of a state space . A state contains all of the information necessary to predict the effects of an action and to determine whether a state satisfies the goal. State-space searching assumes:

The agent has perfect knowledge of the state space.

At any time, it knows what state it is in; the world is thus fully observable .

The agent has a set of actions with known deterministic effects .

The agent has a goal to achieve and can determine whether a state satisfies the goal.

A solution to a search problem is a sequence of actions that will get the agent from its current state to a state that satisfies the goal.

Example 3.2 .

Consider the robot delivery domain of Figure 3.1 , where there are offices around a central lab. The only way a robot can get through a doorway is to push the door open in the direction shown. The task is to find a path from one location to another. Assuming that the agent can use a lower-level controller to get from one location to a neighboring location, the actions for the search are traveling between neighboring locations. This can be modeled as a state-space search problem, where the states are locations. Some of the locations in Figure 3.1 are named and used as exemplars.

Consider an example problem where the robot starts at location A , and the goal is to get to location G . Thus, G is the only state that satisfies the goal. A solution is a sequence of actions that moves the robot from A to G .

Example 3.3 .

Consider a video game played on a grid, where an agent can move up, down, left, or right one step as long as the move is not blocked by a wall. The agent has to collect four coins, C 1 , … , C 4 , where each coin starts at a known position. The agent uses one unit of fuel at each step, and cannot move if it has no fuel. It can get filled up (to 20 units of fuel) at the fuel station. In this case the state needs to take into account the position of the agent, the amount of fuel, and for each coin whether it has collected that coin. The state could be represented as the tuple

where ( x , y ) is the position of the agent, f ⁢ u ⁢ e ⁢ l is the amount of fuel the agent has, and c i is true when the agent has collected coin C i . True is written as t and false as f here. The goal might be for the agent to have collected all coins and be at position ( 1 , 1 ) , which is the state

where ? means what the fuel is at the end does not matter. All states where the agent is at ( 1 , 1 ) and all c i are true are goal states.

Part of the environment is shown in Figure 3.2 (a), where the agent cannot move into a blacked-out square. It could get filled up at position ( 4 , 9 ) and collect coin C 3 at position ( 5 , 7 ) .

The state where the agent, Rob, is at position ( 5 , 8 ) with 6 units of fuel, and has only collected coin C 2 , is

Figure 3.2 (b) shows part of the state space for this problem.

Example 3.4 .

The delivery robot may have a number of parcels to deliver to various locations, where each parcel has its own delivery destination. In this case, the state may consist of the location of the robot, which parcels the robot is carrying, and the locations of the other parcels. The possible actions may be for the robot to move, to pick up parcels that are at the same location as the robot, or to put down some or all of the parcels it is carrying. A goal state may be one in which some specified parcels are at their delivery destination. There may be many goal states because where the robot is or where some of the other parcels are in a goal state does not matter.

Notice that this representation has ignored many details, for example, how the robot is carrying the parcels (which may affect whether it can carry other parcels), the battery level of the robot, whether the parcels are fragile or damaged, and the color of the floor. Not having these details as part of the state space implies that they are not relevant to the problem at hand.

Example 3.5 .

In a simplified tutoring agent , a state may consist of the set of topics that the student knows, and the topics they have been introduced to, but do not know yet. The action may be teaching a lesson on a particular topic, with preconditions that the student knows any prerequisite topic, and the result that the student knows the topic of the lesson. The aim is for a student to know a particular set of topics.

If the effect of teaching also depends on the aptitude of the student, this detail must be part of the state space as well. The state does not need to include the items the student is carrying if what they are carrying does not affect the result of actions or whether the goal is achieved.

A state-space search problem consists of:

a set of states

a distinguished state called the start state

for each state, a set of actions available to the agent in that state

an action function that, given a state and an action, returns a new state

a goal specified as a Boolean function, g ⁢ o ⁢ a ⁢ l ⁢ ( s ) , that is true when state s satisfies the goal, in which case s is a goal state

a criterion that specifies the quality of an acceptable solution; for example, any sequence of actions that gets the agent to the goal state may be acceptable, or there may be costs associated with actions and the agent may be required to find a sequence that has minimal total cost.

A solution that is best according to some criterion is called an optimal solution . An agent may be satisfied with any solution that is within, say, 10% of optimal.

This framework is extended in subsequent chapters to include cases where the states have structure that can be exploited, where the state is not fully observable (e.g., the robot does not know where the parcels are initially, or the teacher does not know the aptitude of the student), where the actions are stochastic (e.g., the robot may overshoot, or a student perhaps does not learn a topic that is taught), and with complex preferences in terms of rewards and punishments, not just a set of goal states.

• Part 2 Problem-solving »
• Chapter 3 Solving Problems by Searching
• Edit on GitHub

Chapter 3 Solving Problems by Searching 

When the correct action to take is not immediately obvious, an agent may need to plan ahead : to consider a sequence of actions that form a path to a goal state. Such an agent is called a problem-solving agent , and the computational process it undertakes is called search .

Problem-solving agents use atomic representations, that is, states of the world are considered as wholes, with no internal structure visible to the problem-solving algorithms. Agents that use factored or structured representations of states are called planning agents .

We distinguish between informed algorithms, in which the agent can estimate how far it is from the goal, and uninformed algorithms, where no such estimate is available.

3.1 Problem-Solving Agents 

If the agent has no additional information—that is, if the environment is unknown —then the agent can do no better than to execute one of the actions at random. For now, we assume that our agents always have access to information about the world. With that information, the agent can follow this four-phase problem-solving process:

GOAL FORMULATION : Goals organize behavior by limiting the objectives and hence the actions to be considered.

PROBLEM FORMULATION : The agent devises a description of the states and actions necessary to reach the goal—an abstract model of the relevant part of the world.

SEARCH : Before taking any action in the real world, the agent simulates sequences of actions in its model, searching until it finds a sequence of actions that reaches the goal. Such a sequence is called a solution .

EXECUTION : The agent can now execute the actions in the solution, one at a time.

It is an important property that in a fully observable, deterministic, known environment, the solution to any problem is a fixed sequence of actions . The open-loop system means that ignoring the percepts breaks the loop between agent and environment. If there is a chance that the model is incorrect, or the environment is nondeterministic, then the agent would be safer using a closed-loop approach that monitors the percepts.

In partially observable or nondeterministic environments, a solution would be a branching strategy that recommends different future actions depending on what percepts arrive.

3.1.1 Search problems and solutions 

A search problem can be defined formally as follows:

A set of possible states that the environment can be in. We call this the state space .

The initial state that the agent starts in.

A set of one or more goal states . We can account for all three of these possibilities by specifying an \(Is\-Goal\) method for a problem.

The actions available to the agent. Given a state \(s\) , \(Actions(s)\) returns a finite set of actions that can be executed in \(s\) . We say that each of these actions is applicable in \(s\) .

A transition model , which describes what each action does. \(Result(s,a)\) returns the state that results from doing action \(a\) in state \(s\) .

An action cost function , denote by \(Action\-Cost(s,a,s\pr)\) when we are programming or \(c(s,a,s\pr)\) when we are doing math, that gives the numeric cost of applying action \(a\) in state \(s\) to reach state \(s\pr\) .

A sequence of actions forms a path , and a solution is a path from the initial state to a goal state. We assume that action costs are additive; that is, the total cost of a path is the sum of the individual action costs. An optimal solution has the lowest path cost among all solutions.

The state space can be represented as a graph in which the vertices are states and the directed edges between them are actions.

3.1.2 Formulating problems 

The process of removing detail from a representation is called abstraction . The abstraction is valid if we can elaborate any abstract solution into a solution in the more detailed world. The abstraction is useful if carrying out each of the actions in the solution is easier than the original problem.

3.2 Example Problems 

A standardized problem is intended to illustrate or exercise various problem-solving methods. It can be given a concise, exact description and hence is suitable as a benchmark for researchers to compare the performance of algorithms. A real-world problem , such as robot navigation, is one whose solutions people actually use, and whose formulation is idiosyncratic, not standardized, because, for example, each robot has different sensors that produce different data.

3.2.1 Standardized problems 

A grid world problem is a two-dimensional rectangular array of square cells in which agents can move from cell to cell.

Vacuum world

Sokoban puzzle

Sliding-tile puzzle

3.2.2 Real-world problems 

Route-finding problem

Touring problems

Trveling salesperson problem (TSP)

VLSI layout problem

Robot navigation

Automatic assembly sequencing

3.3 Search Algorithms 

A search algorithm takes a search problem as input and returns a solution, or an indication of failure. We consider algorithms that superimpose a search tree over the state-space graph, forming various paths from the initial state, trying to find a path that reaches a goal state. Each node in the search tree corresponds to a state in the state space and the edges in the search tree correspond to actions. The root of the tree corresponds to the initial state of the problem.

The state space describes the (possibly infinite) set of states in the world, and the actions that allow transitions from one state to another. The search tree describes paths between these states, reaching towards the goal. The search tree may have multiple paths to (and thus multiple nodes for) any given state, but each node in the tree has a unique path back to the root (as in all trees).

The frontier separates two regions of the state-space graph: an interior region where every state has been expanded, and an exterior region of states that have not yet been reached.

3.3.1 Best-first search 

In best-first search we choose a node, \(n\) , with minimum value of some evaluation function , \(f(n)\) .

3.3.2 Search data structures 

A node in the tree is represented by a data structure with four components

\(node.State\) : the state to which the node corresponds;

\(node.Parent\) : the node in the tree that generated this node;

\(node.Action\) : the action that was applied to the parent’s state to generate this node;

\(node.Path\-Cost\) : the total cost of the path from the initial state to this node. In mathematical formulas, we use \(g(node)\) as a synonym for \(Path\-Cost\) .

Following the \(PARENT\) pointers back from a node allows us to recover the states and actions along the path to that node. Doing this from a goal node gives us the solution.

We need a data structure to store the frontier . The appropriate choice is a queue of some kind, because the operations on a frontier are:

\(Is\-Empty(frontier)\) returns true only if there are no nodes in the frontier.

\(Pop(frontier)\) removes the top node from the frontier and returns it.

\(Top(frontier)\) returns (but does not remove) the top node of the frontier.

\(Add(node, frontier)\) inserts node into its proper place in the queue.

Three kinds of queues are used in search algorithms:

A priority queue first pops the node with the minimum cost according to some evaluation function, \(f\) . It is used in best-first search.

A FIFO queue or first-in-first-out queue first pops the node that was added to the queue first; we shall see it is used in breadth-first search.

A LIFO queue or last-in-first-out queue (also known as a stack ) pops first the most recently added node; we shall see it is used in depth-first search.

3.3.3 Redundant paths 

A cycle is a special case of a redundant path .

As the saying goes, algorithms that cannot remember the past are doomed to repeat it . There are three approaches to this issue.

First, we can remember all previously reached states (as best-first search does), allowing us to detect all redundant paths, and keep only the best path to each state.

Second, we can not worry about repeating the past. We call a search algorithm a graph search if it checks for redundant paths and a tree-like search if it does not check.

Third, we can compromise and check for cycles, but not for redundant paths in general.

3.3.4 Measuring problem-solving performance 

COMPLETENESS : Is the algorithm guaranteed to find a solution when there is one, and to correctly report failure when there is not?

COST OPTIMALITY : Does it find a solution with the lowest path cost of all solutions?

TIME COMPLEXITY : How long does it take to find a solution?

SPACE COMPLEXITY : How much memory is needed to perform the search?

To be complete, a search algorithm must be systematic in the way it explores an infinite state space, making sure it can eventually reach any state that is connected to the initial state.

In theoretical computer science, the typical measure of time and space complexity is the size of the state-space graph, \(|V|+|E|\) , where \(|V|\) is the number of vertices (state nodes) of the graph and \(|E|\) is the number of edges (distinct state/action pairs). For an implicit state space, complexity can be measured in terms of \(d\) , the depth or number of actions in an optimal solution; \(m\) , the maximum number of actions in any path; and \(b\) , the branching factor or number of successors of a node that need to be considered.

3.4 Uninformed Search Strategies 

3.4.1 breadth-first search .

When all actions have the same cost, an appropriate strategy is breadth-first search , in which the root node is expanded first, then all the successors of the root node are expanded next, then their successors, and so on.

Breadth-first search always finds a solution with a minimal number of actions, because when it is generating nodes at depth \(d\) , it has already generated all the nodes at depth \(d-1\) , so if one of them were a solution, it would have been found.

All the nodes remain in memory, so both time and space complexity are \(O(b^d)\) . The memory requirements are a bigger problem for breadth-first search than the execution time . In general, exponential-complexity search problems cannot be solved by uninformed search for any but the smallest instances .

3.4.2 Dijkstra’s algorithm or uniform-cost search 

When actions have different costs, an obvious choice is to use best-first search where the evaluation function is the cost of the path from the root to the current node. This is called Dijkstra’s algorithm by the theoretical computer science community, and uniform-cost search by the AI community.

The complexity of uniform-cost search is characterized in terms of \(C^*\) , the cost of the optimal solution, and \(\epsilon\) , a lower bound on the cost of each action, with \(\epsilon>0\) . Then the algorithm’s worst-case time and space complexity is \(O(b^{1+\lfloor C^*/\epsilon\rfloor})\) , which can be much greater than \(b^d\) .

When all action costs are equal, \(b^{1+\lfloor C^*/\epsilon\rfloor}\) is just \(b^{d+1}\) , and uniform-cost search is similar to breadth-first search.

3.4.3 Depth-first search and the problem of memory 

Depth-first search always expands the deepest node in the frontier first. It could be implemented as a call to \(Best\-First\-Search\) where the evaluation function \(f\) is the negative of the depth.

For problems where a tree-like search is feasible, depth-first search has much smaller needs for memory. A depth-first tree-like search takes time proportional to the number of states, and has memory complexity of only \(O(bm)\) , where \(b\) is the branching factor and \(m\) is the maximum depth of the tree.

A variant of depth-first search called backtracking search uses even less memory.

3.4.4 Depth-limited and iterative deepening search 

To keep depth-first search from wandering down an infinite path, we can use depth-limited search , a version of depth-first search in which we supply a depth limit, \(l\) , and treat all nodes at depth \(l\) as if they had no successors. The time complexity is \(O(b^l)\) and the space complexity is \(O(bl)\)

Iterative deepening search solves the problem of picking a good value for \(l\) by trying all values: first 0, then 1, then 2, and so on—until either a solution is found, or the depth- limited search returns the failure value rather than the cutoff value.

Its memory requirements are modest: \(O(bd)\) when there is a solution, or \(O(bm)\) on finite state spaces with no solution. The time complexity is \(O(bd)\) when there is a solution, or \(O(bm)\) when there is none.

In general, iterative deepening is the preferred uninformed search method when the search state space is larger than can fit in memory and the depth of the solution is not known .

3.4.5 Bidirectional search 

An alternative approach called bidirectional search simultaneously searches forward from the initial state and backwards from the goal state(s), hoping that the two searches will meet.

3.4.6 Comparing uninformed search algorithms 

3.5 Informed (Heuristic) Search Strategies 

An informed search strategy uses domain–specific hints about the location of goals to find colutions more efficiently than an uninformed strategy. The hints come in the form of a heuristic function , denoted \(h(n)\) :

\(h(n)\) = estimated cost of the cheapest path from the state at node \(n\) to a goal state.

3.5.1 Greedy best-first search 

Greedy best-first search is a form of best-first search that expands first the node with the lowest \(h(n)\) value—the node that appears to be closest to the goal—on the grounds that this is likely to lead to a solution quickly. So the evaluation function \(f(n)=h(n)\) .