State space search techniques are often illustrated by showing how they can be used in solving puzzles of the sort you find in intelligence tests. One such puzzle is the water jug problem [Rich &Knight, 31]:
``You are given two jugs, a 4-gallon one and a 3-gallon one. Neither has any measuring markers on it. There is a tap that can be used to fill the jugs with water. How can you get exactly 2 gallons of water into the 4-gallon jug''.
Given such a problem, we have to decide how to represent the problem state (e.g., amount of water in each jug), what the initial and final states are in this representation, and how to represent the actions available in the problem, in terms of how they change the problem state. This particular puzzle is based on a simple problem solving domain where the problem state can be represented simply as a pair of numbers giving the amount of water in each jug (e.g., [4, 3] means that there is 4 gallons in the 4-gallon jug and 3 in the 3 gallon jug). The initial state is [0,0] and the final state is [2,X] where X can take any value. There are only a small number of available actions (e.g., fill the 4-gallon jug), and these can be simple represented as rules or operators which show how the problem state changes given the different actions:
Rules such as [X, Y] [X, 0] mean that we can get from a state
where there are X gallons in the first jug and Y in the second jug to
a state where there are X gallons in the first and none in the second,
using the given action. If there is a condition such as (if X+Y < 3) this
means that we can only apply the rule if that condition holds.
We'll also only consider actions that cause a change in the current
state.
Note that in puzzles such as this we restrict our set of actions to ones that might actually be useful in solving the problem. It wont help just pouring a random amount of water onto the ground, as then we won't know where we are! The program writer has to supply most of the intelligence, in the way the problem is represented and the algorithm chosen to solve it. The action rules above are a more restricted set to those given in Rich &Knight, but are sufficient to solve the problem.
Now, how do we use our standard search techniques discussed earlier? The notion of a ``successor state'' is a little more obscure here than in the map domain. We have to look at all our actions, and find ones that apply given the current state. We can then use the rules above to find the state resulting from that action. A particular node in the search tree, rather than being just the name of a town, will now be the representation of a particular state (e.g., [2, 3]).
This should all be clear when we try and solve the problem, which I'll go through is tedious detail. We'll use depth first search first, with both open and closed node lists. (In exercise 5 we won't use a closed node list - but an agenda of partial paths, with a loop check on those paths).
Initially our jugs are both empty, so the initial state is [0, 0], and the node lists are:
open = [[0, 0]]
closed = []
Our goal state is [2, X], where X can take any value.
To start problem solving, we remove the first state from
open and look for its successors.
There are two actions that you can take from [0,0] that will change the
state of the world - filling the 3 gallon or filling the four gallon jug.
Possible succesors are [4, 0] and [0, 3], so our new lists are:
open = [[4, 0], [0, 3]]
closed = [[0, 0]]
From [4, 0] actions 2, 6 and 8 apply, and cause a change in state. Possible successor states are: [4, 3], [1, 3], [0, 0]. [0, 0] is on the closed list, so is thrown away, and our new lists are:
open = [[4, 3], [1, 3], [0, 3]]
closed = [[4, 0], [0, 0]]
Now, from [4, 3] we can apply actions 7 and 8 with change of state. 7 will get us back to [4, 0] which is on the closed list, while 8 will get us to [0, 3] which is on the open list. So neither is any good, so we put [4, 3] on our closed list and go on to look at [1, 3]. From [1, 3] we can fill the 4 gallon (action 1), but that'll get us back to [4,3]; we can empty the 3 gallon into the 4 gallon (4), but that'll get us back to [4, 0]; or we can empty either jug. Emptying the 3 gallon jug (action 7) gets us to a new state [1, 0]:
open = [[1, 0], [0, 3]]
closed = [[1, 3], [4, 3], [4, 0], [0, 0]]
From [1, 0] the only action that will result in a new state is 3 (emptying the 4 gallon into the 3 gallon jug), with new state [0, 1]. From here action 1 (filling the 4 gallon) results in a new state [4, 1], with lists now:
open = [[4, 1], [0, 3]]
closed = [[0, 1], [1, 0], [1, 3], [4, 3], [4, 0], [0, 0]]
From [4, 1] we try filling the 3 gallon from the 4 gallon jug (action 5), resulting in a state [2, 3]. Which is a solution! The portion of the search tree that we've explored is given below:
So, to solve the problem, one solution is to fill the 4 gallon jug, fill the 3 gallon from the 4 gallon, empty the 3 gallon, empty the 4 gallon into the 3 gallon, fill the 4 gallon and fill the 3 gallon from the 4 gallon again. In fact, because we carefully formulated the problem, and ruled out actions that resulted in old states or no change, there wasn't too much search involved. Problems which did involve alot of search would just be too tedious to go through! Hopefully however the example will have given an idea of how simple problems are approached using search techniques. You have to decide on a representation of the state of the world, of the available actions in the domain, and systematically going through all possible sequences to find a sequence of actions that will get you from your initial to target state.
In the water jug problem there is no real need to use a heuristic search technique - the domain is sufficiently constrained that you can go through all possibilities pretty quickly. In fact, its hard to think what a good evaluation function would be. If you want 2 gallons in the jug, does it mean you are close to a solution if you have 1 or 3 gallons? Many problems have the property that you seem to have to undo some of the apparent progress you have made if you are to eventually get to the solution (e.g., empty out the jug when you've got 1 gallon in it). Think, for example, of the Rubik's cube when you have all but one side finished. This doesn't necesarily mean that you can straightforwardly get to the final solution. Heuristic search is often useful in problem solving, but it may be better to try and carefully formulate the problem, so that the search space is small and simple search techqniques can be applied.
There are lots of other problems that have been solved using similar techniques, and which are often foundin AI text books. The ``Missionaries and cannibals'' problem, the ``Monkeys and bananas'' problem and the ``8 puzzle'' are three that are often quoted, and are described on pages 47 and 60 of Rich &Knight. I leave it as an exercise for the reader to try and work out how these problems could be represented and search techniques used in their solution.
The example above was clearly a ``toy'' problem. However, search techniques are used in many more serious AI applications, such as: language understanding, where we may search through possible syntactic structures; robotics, where we may search for a good path for the robot to take; vision, where we may search for meaningful interpretations of features of the object to be recognized. The use of search in such applications will be mentioned further in later lectures. To solve ``real'' problems you generally have to put alot more effort into representing the problem. You have to think exactly what a representation of a world state should be, what the initial and goal states are, and what the available operators/actions are that allow you to transform one state into another. You also need to decide whether or not state space search is appropriate, or whether, for example, problem reduction, described below, might be better.