The Classic Farmer,Wolf,Goat,Cabbage Production System Construction
Im trying to learn the producttion system for the FWGC Artificial Intelligence problem.More details https://www.cs.unm.edu/~luger/ai-final2/CH4_Depth-.%20Breadth-,%20and%20Best-first%20Search.pdf
I have a problem in understanding how the graph is constructed.I understand upto this figure and how the state is represented based on the location.
How is this graph constructed? Can someone explain?
According to the document, describing the diagram:
The "graph" is a state transition diagram showing you what possible states you can go to from any other given state, starting at state(w,w,w,w) as the initial state. How a transition is determined is by considering the logic of the described problem. Such a graph could be automatically generated in Prolog if you have all the correct Prolog rules set up for the problem, or it could be generated manually as an aid to figure out how you wish to write the rules. The document doesn't say exactly how they generated it, but they only say that it's a partial description of the possible state transitions, and without regard to whether any given state is "safe", which means that the diagram contains some states which you would want your Prolog solution to rule out. Given it's place in the document and the context, I believe it's manually generated as an aid to coming up with a reasonable data representation and design for the Prolog program.
To take an example, the initial state is that all 4 things (farmer, wolf, goat, cabbage) are on the West bank. That's state state(w,w,w,w) representing location of F,W,G,C, respectively. The possible states that a single move can take you from there are, since the farmer can only take at most one item at a time across the river:
West East State
---- ---- -----
G, C F, W state(e, e, w, w)
W, C F, G state(e, w, e, w)
W, G F, C state(e, w, w, e)
W, G, C F state(e, w, w, w)
This is figured out by thinking about the rules and the possible choices. In each of the above new states, the farmer either took one item across the river, or went across themselves with nothing else. That's 4 possible moves. The arrows in the diagram indicate which states you can transition to. So the diagram indicates that the state transitions are reflexive (that is, if you go from state A to state B, you can also go from B to A).
As another example, when at state(e, e, w, w):
West East State
---- ---- -----
G, C F, W state(e, e, w, w)
From here, there are only two possible moves: the farmer takes the wolf back across the river (goes back to state(w, w, w, w), or the farmer goes back across the river on their own, which would be state(w, e, w, w) and is what's shown in the state transition diagram.