State-Space Search

A state space consists of
A (possibly infinite) set of states
The start state represents the initial problem
Each state represents some configuration reachable from the start state
Some states may be goal states (solutions)
A set of operators
Applying an operator to a state transforms it to another state in the state space
Not all operators are applicable to all states
State spaces are used extensively in Artificial Intelligence (AI)
With certain modifications, any tree search technique can be applied to a graph
This includes depth-first, breadth-first, depth-first iterative deepening, and other types of searches
The difference is that a graph may have cycles
We don’t want to search around and around in a cycle
To avoid getting caught in a cycle, we must keep track of which nodes we have already explored
There are two basic techniques for this:
Keep a set of already explored nodes, or
Mark the node itself as having been explored
Marking nodes is not always possible (may not be allowed)
A maze can be represented as a state space
Each state represents “where you are” in the maze
The start state represents your starting position
The goal state represents the exit from the maze
Operators (for a rectangular maze) are: move north, move south, move east, and move west
Each operator takes you to a new state (maze location)
Operators may not always apply, because of walls in the maze