MSBLOCKS has another important kind of internal representation, which specifies the different kinds of actions which it is able to perform. In the MSBLOCKS world just four different operations are available (although this number can obviously be increased indefinitely). These operations are
[pickup ?X table] Lift a box from the table [unstack ?X ?Y] Pick up a box which is sitting on top of another box [putdown ?X table] Put the box which the robot is holding on the table [stack ?X ?Y] Stack a box on top of another box
As explained in the previous chapter, the expressions ?X and ?Y stand for pattern-matching variables. When the operations are performed the variables will be given the values of particular boxes to be moved, such as [stack boxG boxg].
When we set the robot a goal -- for example, ``Put the big green box onto the small green one'' -- the robot must choose a sequence of operations which will bring about the desired result. The process of choosing a sequence of operations is usually known as planning in AI.
In order to plan out a sequence of operations, the MSBLOCKS system has
to follow certain constraints, in the form of preconditions
that must be true in order
for a given action to be possible in a given situation, and
effects
that the operations need to produce in order to reach the goal.
For instance,
if I plan to drive from Marseilles to Paris, the preconditions are that
I must have a car, that it is in working order, that I am situated in, or
can get to, Marseilles, and so on. Similar conditions apply to the
robot. So, for example, in order to
perform the operation
[unstack boxr boxG] it must be the case that
Each operation produces effects in the form of changes to the database: entries may be deleted, or they may be added.
For example, after the operation [unstack boxr boxG] has been performed, the following changes will be made to the database:
Delete: [handempty] [cleartop boxr] [boxr on boxG]Add: [holding boxr] [cleartop boxG]
The program's knowledge of possible actions, subject to the constraints just mentioned, is encoded as a series of structures called operator schemas -- rather like simple frames, with slots which can be filled in different ways. Each operator schema represents the characteristics of a given operation and provides at least four kinds of information:
Here is how the schema for the operation [unstack ?X ?Y] might look, expressed in a list pattern form. The schema will consist of a list, with four sublists:
[ [unstack ?X ?Y] Operator specification[ [?X on ?Y] [cleartop ?X] [handempty] ] Preconditions
[ [?X on ?Y] [cleartop ?X] [handempty] ] Delete list
[ [cleartop ?Y] [holding ?X] ] ] Add list
The two middle sub-lists, the preconditions and the delete list, contain the same members. This need not always be the case, but it happens to be so for this particular operation.
In planning a sequence of operations, the program selects a series of operator schemas that move the database from its initial state to the goal state. For each stage in the plan an operator is chosen that fits both constraints; that is, its proeconditions match the current state of the database, and its effects advance the robot toward the goal. Normally there is more than one way to reach a goal, within the constraints, and just how a program plans a good series of operators is a major topic of AI, and one that is not covered further in this book. Rich (1983) and Charniak and McDermott (1985) both offer good introductions to planning techniques.
We have shown how simple data-structures can represent the fixed and changeable conditions of the robot's environment, and its available actions. Other kinds of representation are also needed. Before forming a plan the program must reduce sentences typed in English to a form that can be matched against its database of operator schemas. From the raw words of a sentence, a representation of its syntax is constructed, from which the sentence's meaning is derived. If the sentence is a command, such as ``Put the little red box on top of a green one,'' then its response will be to plan a sequence of operations and make changes to the database. If the sentence is a question, such as ``Where is the small green box?'' then it will consult the database and generate an appropriate answer.
There are some salutary lessons to be learned from SHRDLU and MSBLOCKS. A surprisingly complicated set of internal structures, as well as processes to manipulate these structures, is required in order to make the system work, to enable it to understand simple one-sentence commands or questions about blocks. Much more complex knowledge representations are likely to be needed for AI systems capable of performing more substantial or more lifelike mental tasks: tasks such as answering a tourist's questions!