Example problems:

Toy and real world problems.

A toy problem is intended to illustrate or exercise various problem solving methods. It can be given a concise, exact description. This means it can be used easily by different researchers to compare the performance of algorithms.

A real world problem is one whose solutions people actually care about, they tend not to have a single agreed upon description, but we will attempt to give the general flavor of their formulations.

Toy problems:

1] vacuum world. This can be formulated as a problem as follows:

State: The agent is in one of the two locations, each of which might or might not contain dirt. Thus, there are $2 \times 2^2 = 8$ possible world standard.

Initial state: Any state can be designated as the initial state.

Successor function: This generates the legal states that result from trying the three actions (left, right and suck). The complete state space is shown in figure (3).

Goal test: This checks whether all the squares are clean.

Path cost: Each step costs 1, so the path cost, is the number of step in the path.

Figure (3), the state space for the vacuum world. Arcs denote actions: L = Left, R = Right, S = Suck. Compared with the real world, this toy problem has discrete locations, discrete dirt, reliable cleaning and it never gets messed up once cleaned. One important thing to note is that the state is determined by both the agent location and the dirt locations. A larger environment with n locations has $h_2^2$ states.