State Space Search in Artificial Intelligence

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

Maze - State Space Search

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
See also  Artificial Intelligence and its Task Domains

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

Initial State of 15 Puzzle Problem
Goal State of 15 Puzzle Problem

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.

See also  Heuristic Search - Characteristics Advantages - Artificial Intelligence

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.

Leave a Comment

Your email address will not be published.