State Space Search in Artificial Intelligence
In Artificial Intelligence a state space consists of the following elements,
1. A (possibly infinite) set of states
1.1. Out of the possible states, one state represents the start state that is the initial state of the problem.
1.2. Each state represents some configuration reachable from the start state
1.3. Out of the possible states, some states may be goal states (solutions)
2. A set of rules,
2.1. Applying a rule to the current state, transforms it to another or a new state in the state space
2.2 All operators may not be applicable to all states in the state space
State spaces are used extensively in Artificial Intelligence (AI) to represent and solve problems.
State Space Search Examples:
Example 1. Maze
A maze problem can be represented as a state-space
- Each state represents “where you are” that is the current position in the maze
- The start state or initial state represents your starting position
- The goal state represents the exit from the maze
Rules (for a rectangular maze) are: move north, move south, move east, and move west
- Each rule takes you to a new state (maze location)
- Rules may not always apply, because of walls in the maze
Example 2. The 15 Puzzle
The start state is some (almost) random configuration of the tiles and the goal state is as shown.
State Space Search Rules are
- Move empty space up
- Move empty space down
- Move empty space right
- Move empty space left
These Rules apply if empty space is not against the edge.
General Process followed in solving problem using State Space Search
1. First, select some way to represent states in the given problem in an unambiguous way.
2. Next, formulate all actions or operators that can be performed in states, including their preconditions and effects.
- Actions or operates are called PRODUCTION RULES
3. Represent the initial state or states of the problem.
4. Formulate precisely when a state satisfies the goal of our problem.
5. Activate the production rules on the initial state and its descendants, until a goal state is reached.
Summary
This article discusses State-Space Search in Artificial Intelligence. If you like the material share it with your friends. Like the Facebook page for regular updates and YouTube channel for video tutorials.