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 g∈G. 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 ⊆ S
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.