Wednesday, August 15, 2012

Elementary Discussion About State Space Search (Part I)

State space search
            • Formulate a problem as a state space search by showing the legal problem states, the legal operators, and the initial and goal states.
            • A state is defined by the specification of the values of all attributes of interest in the world
            • An operator changes one state into the other; it has a precondition which is the value of certain attributes prior to the application of the operator, and a set of effects, which are the attributes altered by the operator
            • The initial state is where you start
            • The goal state is the partial description of the solution 

State Space Search Notations
Let us begin by introducing certain terms.
An initial state is the description of the starting configuration of the agent
An action or an operator takes the agent from one state to another state which is called a successor state. A state can have a number of successor states.
A plan is a sequence of actions. The cost of a plan is referred to as the path cost. The path cost is a positive number, and a common path cost may be the sum of the costs of the steps in the path.
Now let us look at the concept of a search problem.
Problem formulation means choosing a relevant set of states to consider, and a feasible set of operators for moving from one state to another.
Search is the process of considering various possible sequences of operators applied to the initial state, and finding out a sequence which culminates in a goal state.

Search Problem
We are now ready to formally describe a search problem.
A search problem consists of the following:
            • S: the full set of states
            • s0 : the initial state
            • A:S→S is a set of operators
            • G is the set of final states. Note that G S

These are schematically depicted in Figure 1.

Figure 1
The search problem is to find a sequence of actions which transforms the agent from the initial state to a goal state gG. A search problem is represented by a 4-tuple {S, s0, A, G}.
S: set of states
s0 S: initial state
A: S -> S operators/ actions that transform one state to another state
G: goal, a set of states. G

This sequence of actions is called a solution plan. It is a path from the initial state to a goal state. A plan P is a sequence of actions. 
Searching process
The generic searching process can be very simply described in terms of the following steps:

Do until a solution is found or the state space is exhausted.
                        1. Check the current state
                        2. Execute allowable actions to find the successor states.
                        3. Pick one of the new states.
                        4. Check if the new state is a solution state
                        If it is not, the new state becomes the current state and the process is repeated


 
Illustration of a search process
We will now illustrate the searching process with the help of an example. Consider the problem depicted in Figure 2.

Figure 2
s0 is the initial state.
The successor states are the adjacent states in the graph.
There are three goal states. 

Figure 3
The two successor states of the initial state are generated.

Figure 4
The successors of these states are picked and their successors are generated. Initial State Initial State

Figure 5
Successors of all these states are generated. 

Figure 6
The successors are generated. Initial State

Figure 7
A goal state has been found.
The above example illustrates how we can start from a given state and follow the successors, and be able to find solution paths that lead to a goal state. The grey nodes define the search tree. Usually the search tree is extended one node at a time. The order in which the search tree is extended depends on the search strategy.
We will now illustrate state space search with one more example – the pegs and disks problem. We will illustrate a solution sequence which when applied to the initial state takes us to a goal state. 

This topic will be continued in the next Part. Feel free to discuss about the topic. 



 



No comments:

Post a Comment

Note: Only a member of this blog may post a comment.