What are the state space and the state transition function in AI?

Question

I'm studying for my AI final exam, and I'm stuck in the state space representation. I understand initial and goal states, but what I don't understand is the state space and state transition function. Can someone explain what are they with examples?

For example, one of the questions was this on my previous exam:

Given $k$ knights on an infinite (in all directions) chessboard and k selected squares of the board. Our task to move the knights to these selected squares obeying the following simple rules:

• All knights move parallel, following their movement rule (L-shape jump)
• No knights can move to a square on which a knight stood anytime before

Give the state space of the problem, the starting and goal states, and the state transition function!

Answer 1

Initial state

How things are at first.

In your particular example, it would be where your k knights are placed on the board initially. Your problem doesn't precisely state this, so you could either place them at the bottom or at random.

Goal state

The board with the k knights placed on the target squares.

State transition function

A function that takes actions (bound presumably by rules) and returns a new state.

In the k knight problem, the legal actions are moving parallel and in L shape movements, after which the knight will be in a new position and the board in a new state.

State space

The set of all states reachable from the initial state by any sequence of actions.

So, in the case of the k knight problem, your state space would start at the top with your initial state followed down by each individual movement of the k knights and the resulting new state. A graph where lines are actions and nodes are new states or a table are common representations of state space.

---

Reference

Artificial Intelligence: A Modern Approach, by S. Russell and P. Norvig.