Toy Example Problems

State Space Search: The Chaperone Problem

Lord Lovely had arranged a picnic for his daughter, Lavinia, and two of the local talent, viz, one Victor Vile and one Hon. Simon Simple, all to be chaperoned by Dr Gertrude Gooseberry. Now Vile has wicked designed on Ms Lovely, while she has the hots for Simple, who himself is oblivious to everything except the propriety of his dress. All went well until the party, arriving at the bush-lined river bank of the River Cam at Grantchester, found only a two-man person punt to take them across to the meadow beyond, the problem being that only Gertrude could punt, leaving space for only one passenger. But if left alone together, Vile would make advances to Lavinia, while if Lavinia is left with Simple, goodness knows what in the line of sartorial misdemeanour might occur. Golly, what is Gooseberry to do?

The Solution:

START:     GLSV=       ->
             SV=GL     ->
            GSV=L      ->
              V=GLS    ->
            GLV=S      ->
              L=GSV    ->
             GL=SV     ->
GOAL:          =GLSV

What Gooseberry did was to set the problem up a journey through the problem's state space. This approach is common to almost every AI problem. Look at the state space (all 16 states) in the diagram and ask yourself what did her search entail?

It involved:

Consideration of the state-space containing all possible configurations of objects. (NB this need not be explicit!)

Specifying initial and goal states. (Other problems can have multiple initial and goal states.)

Making up rules describing operations (Eg G always changes state.)

Matching rules that can be applied to a state (this will be more obvious in the next example).

Applying the rules in some order in the search for a goal.

In more general terms, the approach couples

specific problem-dependent rules, with the

general techniques of search.

We tackle the issue of search more thoroughly in the next section.

<<<Previous Next>>>