DECIDER-l: A System that Chooses Among Different Types of Acts

Introduction

The basic purpose of this paper is to examine how word-things recognized in the external environment can help trigger actions that include recognition and manipulation of other, object-things, in the same environment. To do this we must examine several issues that have scarcely been touched upon in the research literature of psychology or computer science:

How does a system recognize that a perceived input is a symbol? How does it understand the import of a structure of symbols, e.g. that it is a command, or a question? How does it understand the meaning of that structure? How does it decide what type of thing to do -whether to obey a command, and which com­ mand, or whether to continue to perceive, to respond to internal needs, or external presses from perceived objects? How do the understanding of commands and other symbolic percepts and the recognition of perceived objects interact, helping one another; e.g. how does it recognize which objects are appropriate for carrying out a command? How does a system choose and execute the appropriate response, from variety of possible responses?

1 This research has been partially supported by grants from the National Institute of Mental Health (MH12266), the National Science Fourrlation (GJ-36312), NASA (NGR-50-002-160) and the University of Wisconsin Graduate School.

manipulation are de signed to handle only sma 11 pieces of this process.

A sufficiently powerful pattern recognizer (e.g. Uhr and Vossler, 19611 7 ; Andrews et. al. 19681· Munson 8 24 --' ' ' 1968 ; zobrist, 1971 ) can correctly name many different examples of a pattern, all distorted in extremely complex, and unanticipated, non-linear ways. It can contend with very complex possible confusions between objects. In comparison, a *BANANA and an *APPLE are very different, and the symbols Premack has chosen for BANANA and for APPLE are also different enough so that the chimp has no perceptual difficulties. (This is not at all to say that the chimp and human are not sophisticated pattern recognizers, but simply to point out that the particular single-pattern problem we are examining, in which only a few very different patterns need be recognized, is simple compared to problems that programs, as well as chimps and people, can handle.) But today's pattern recognizers will not handle scenes of several things, much less compose things into structures like sentences, or sort out the words and the objects, and their interrelationships.

A sufficiently powerful language processor (e.g. Winograd, 1971 23 ; see Simmons, 196514, 197015) can handle more complex grammatical structures than the simple actor-act-object-indirect object of our example SARAH PUT BANANA BOX. But it will handle only clean, clear-cut sentences. It cannot content with sentences with misspelled words and noise that are embedded in larger scenes that include other objects.

At the very least, pattern recognizers must be extended to handle scenes of objects, and to parse word-phrases as well as characterize parts of objects (seeSauvainandUhr, 196913;Jordan, 19717;Uhr, 197218, 1973c 2 1).

Robots that are Pre-Programmed to Obey Commands

Recent work with robots, in which they deduce paths to cluster boxes, anc! stack blocks (e.g. Nilsson, 19699; Raphael, 19681 2 ;Feldmanet. al., 1969 3 ), has made some steps toward this interaction. But it has the flavor of interconnecting several separate black boxes, each performing a separate function, even though there often appears to be a great amount of overlap. Thus the reported robots input and handle commands and perceptual environment completely separately.

Today's robots use extremely complex systems of computer programs, almost always separated into four major sub-systems, to I) understand the command, 2) recognize and build up a model of the objects in the environment, 3) deduce the set of actions appropriate to carrying out the command, and 4) apply them to the environment. Each subsystem has its own subsystems:

1. The command is given through a teletype, and the system applies language "understanding" programs, to recognize . words, parse the command statement, and derive from the statement a goal state that the robot must achieve, to obey the command.
2. Separate perceptual programs are used to handle the robot's perceived spatial environment, which al­ most always includes inputs from a tv camera, and occasionally is supplemented with inputs from range finders, touch sensors, photocells, or sonar. These programs input the sensed information, take a sequence of preprocessing steps (e.g. to eliminate noise, find gradients and edges, and begin to connect short edge fragments into lines), and try to build the salient features up into something that matches some internal description of sorre object (e.g. Brice and Fennema, 1970 2 ). This results (if all goes well -which today means if objects are sufficiently simple, with enough background space between them, painted in colors that contrast sharply enough in the black-and-white tv image, and amply lighted) in the assignment of names to objects, and the assignment of these objects to their locations within the perceived environment.
3. A deductive problem-solving program (often a theorem prover) is used to generate a sequence of actions that the robot might apply to the objects it has tentatively recognized in its perceived space, in order to achieve the desired goal state (e.g. Fikes and Nilsson, I97I4).
4. This entails binding the objects (including the robot itself) to the proposed actions, so that the robot can in the real world try out an action that it has deduced would make progress toward satisfying the overall command.

Perceiving the Import of Inputs

Real-World Commands Must first be Perceived

In the real world there is no separate input channel for a command, and there is no god-given a priori signal, known to commander and slave alike, that says, "this is a command," "this is a question," "name this object," "describe this scene," and so on. A ques­ tion-answering program has built into its guts that inputs will be questions, and it is straightforwardly pre-programmed to answer them. A robot program similarly has built into it that teletype inputs are commands, and that it is to carry them out, by manipu­ lating the environment that it perceives through its sensory inputs.

But in the real world the command always comes in through sensory input channels. In fact the command is itself a complex structure of perceived objects. E.g. the command, "PUT THE BANANA IN THE BOX", is made up of a string of words that are further structured grammatically and, more importantly, semantically (in that they refer to things like bananas, relations between bananas and boxes, an understanding that bananas can go into certain boxes, and the implied action of the entity being commanded - that ll should put the banana in the box). And each word is made up of parts (letters if written, phonemes if spoken), each letter or phoneme is made up of parts, and so on.

The command may sometimes come through a separate perceptual mode channel, as when it is spoken and refers to visually perceived objects. But this is not the issue, for commands and objects often come in through the same channel, with the receiver hardly noticing. It is not the difference in channel that allows the human to infer "this is a command composed of symbols" and "that is an environment of objects". Rather, the hearer first recognizes the parts of the command as objects and only later as symbols, com­ bines them up into larger and larger structures, and recognizes that these structures have symbolic import, and are commands.

Deciding Whether to Obey Which Command

Closely related, the hearer has no built-in under­ standing that it will receive one command at a time, pointed to and surrounded by special symbols. Rather, since it must infer that parts of its perceived environ­ ment are commands, it always has the possibility of receiving more than one command. It must decide whether to obey a command, and which. And for any real-world receiver there will always be the issue of whether it should drop everything to carry out whatever command it has just received and understood, or whether it should do something else -what it was already doing, or what will best satisfy some internal need (e.g. hunger) that is arising, or what will best respond to some interesting new object (e.g. a steak).

Thus a system should be able to decide which from among a set of alternative action-sequences it wants to carry out- whether to gather more information, or to obey this command or that, or to satisfy its own needs or goals.

Key Problems Being Handled

This paper focuses on the problem of handling fields of things, some of which are symbols, where these things combine into larger structures (e.g. eyes, nose, mouth, chin combine into face; SARAH PUT BANANA BOX combines into a command; B,O, X combine into BOX), some of which imply that the system should respond with an implied action upon other things to which reference is made.

We have discussed one example of such a situa­ tion, when the environment contains something like: *CRACKER SARAH PUT APPLE PAIL *BOX *BANANA *APPLE *PAIL (or) *BOX3 ROBOT PUSH BOX2 NEXT BOX! *BOX4 *BOX! *BOX5 *BOX2

Such a system can handle a number of other problems, for example an input like: *CRACKER *BOX DESCRIBE *APPLE THIS SCENE *BOX *BANANA *PAIL (in which case it must recognize the command DESCRIBE THIS SCENE and as a result output CRACKER BOX APPLE BOX BANANA PAIL).

Or it can be given an input like: *CRACKER *BOX FIND A BOX *APPLE *BANANA *PAIL (in which case it must recognize the command FIND BOX and as a result output something to indicate the *BOX has been found.) Or it can be asked to Move an object, or to Answer a query.

A Brief Description of Decider's Behavior 1

Overall Flow

2 DECIDER-I inputs a SCENE that contains all physical objects and verbal utterances mixed together, as the above argument has shown is inevitably the case for real world intelligences. It applies two types of pattern recognition techniques to begin sensing this scene:

1. A set of primitive perceptual transforms is put onto the IDEAS list, thus initializing IDEAS to look for whatever the primitives suggest are the basics.
2. Delimiters (such as the edges, gradients and background spaces that often delineate objects and verbal utterances) are used to decompose the SCENE, giving a first tentative set of possible objects. Then DECIDER-I searches its memory for anything that these objects might imply, and, if it finds any, merges them onto the IDEAS list.

DECIDER-I applies the set of IDEAS, serially, to the input SCENE. Each idea that succeeds implies a variety of different objects, new ideas to apply, and acts. The single most highly implied idea is applied in turn to further characterize the SCENE - until it is a response act like Answer, Describe, Find, Move, or Name, in which case it is carried out, and the next SCENE is input. (Note that the particular primitives, perceptual characterizers, verbal rewrite rules, and action transforms depend upon what the programmer (or learning) has tabled into DECIDER-I, just as par­ sers or table-driven compilers depend upon th? gram­ mars given them.)

Perceiving Sensed Objects and Understanding Verbal Utterances

DECIDER-! acts much like a typical pattern recognizer vis-a-vis sensory patterns to recognize and name, and much like a typical parser vis-a-vis verbal utterances. So it can handle mixed inputs of objects and words. It handles both the recog11ition character­ izers and the parsing rewrite rules (let's call them both "transforms") in the same way: It gets the most highly implied transform from the IDEAS list, applies it to the input SCENE (which includes all previously-effected transforms), evaluates whether this transform succeeds and, if it does, merges the transforms that it implies onto the IDEAS list, and the objects that it implies onto the SCENE. (A transform looks for a configurational n-tuple, of which parsing rewrite rules are simple examples (see Uhr, 197116, 1973d22).)

The IDEAS list starts with primitive perceptual characterizers. As these transforms succeed, they will imply higher-level characterizers and, if DECIDER-! recognizes verbal utterances, verbal rewrite rules. These will continue to imply perceptual and verbal transforms, a) for still higher levels, b) to glance about at other parts of the scene in which what has so far been recognized suggests other things should be looked for, and c) to gather more information to confirm or deny the presence of tentatively implied objects (including words).

1 see Uhr, 1973d for more detailed descriptions, and the actual DECIDER-! program.

2 caps refer to major constructs in the DECIDER-! program.

Deciding to Act

DECIDER-l's decision to act is deceptively simple. Each transform on IDEAS has a type associated with it. As discus sed up to now, at first the most highly implied transforms will be of type= P (to perceptually parse)- until the system has gathered enough information about the scene to imply some response action with a high enough weight to be chosen.

DECIDER-1 chooses the single most highly im­ plied trans form from IDEAS. At first these will be perceptual and verbal transforms. But they will begin to imply various possible acts, which will be merged back into IDEAS. Thus IDEAS serves as a vehicle'for deciding among the various possible acts, at the same time that it serves to decide whether to continue looking and gathering information, or whether to respond.

When a response is chosen, as the most highly weighted transform on IDEAS, DECIDER-1 branches to effect that response - whether to Answer, Descriqe, Find, Move, or Name. Thus the response acts and the information-gathering acts are all ordered on the single IDEAS list, from which DECIDER-1 continues to choose and execute the single most highly implied act, until a response act is chosen. This serves to order the execution of each type of act, and serves to choose when to decide to respond, as well as which response to make.

Types of Response Acts

DECIDER-1 can effect a variety of acts. Since our purpose has been to examine how a system can decide to act, the acts themselves are kept as simple as possible.

Answer outputs the piece of information (e.g., a fact, or a document name) that is stored in the Answer transform that was chosen from the IDEAS list.

Describe outputs the names of all objects that have been recognized and placed on the SCENE with a sufficiently high weight to exceed a CHOOSE para­ meter.

Find searches for and brackets (in order to indi­ cate where it is) an object of the class specified by the particular Find transform chosen.

Move finds an object of the first class specified, and moves it from its original location in the SCENE, so that it is next to an object of the second class specified.

Name gets and outputs the single most highly implied thing that is the name of an object in the SCENE.

The Flow of Processes is Multi-Determined

Any transform that succeeds can imply any potential act of any type. Characterizing transforms can be im­ plied by what has been found so far about the input. A recognized and understood command can imply the act that obeys it. But an object can also imply an act (e.g. to Name, or Firrl it). And internal needs can im­ ply acts (e.g. hunger can imply Find an object of the class = food).

Thus, e.g., when DECIDER-1 chooses to Name this can be because a) a number of nameable objects have been perceived, and each implies the act of naming with a low weight, b) a command like "NAME THIS" or a query like "WHAT IS THIS" has been recognized, as implying the act of Naming, and/or c) an internal need implies that the act of naming may lead to its satisfaction. I should emphasize again, because it is a subtle point, that an act like Naming is not built in, but must be decided upon.

Some Examples of DECIDER-l's Behaviorl

Recognizing, Parsing, "Understanding" and Naming

DECIDER-1 is given input SCENEs that contain mixtures of words and objects. (These should be two-, or even three-dimensional scenes that extend over time. Then a written or spoken word like "APPLE" would extend in two dimensions just as does the perceived apple. We reduce these to !-dimensional strings, to keep DECIDER-l's characterizing processes from getting cumbersome. But see Uhr, 1973b, 1973c for the relatively straightforward extensions that allow a system to handle two-dimensional scenes that extend over a third time dimension.)

When given an input like: NAME THIS ((along with the representation of an object))

DECIDER-1 will (if it has been given, or has learned, the needed transforms) output that object's name, e.g. "APPLE" or "TABLE". Todothis itapplieswhatever perceptual transforms have been given it as primitives, and continues to apply linguistic rewrite transforms until the Name transform is triggered. By that time enough perceptual transforms have already been applied to imply object names, and DECIDER-1 chooses and outputs the name of the most highly implied thing that belongs to the class of "OBJECT "·s.

The objects might be represented at any level desired - from a linearized 2-dimensional matrix of

light and dark, e.g.: 000111000,001000100,010000010,001000100, 000111000,000010000, ((9 x 6 apple)) to a set of characteristics: STEM APPLE-COLOR RED ROUND ((apple character­ istics))

to a template-like representation: OBJECT87 ((an encoded name for "apple" objects))

1 see Uhr, 1973d for a more detailed development of a wider variety of examples, showing the transforms used and the ways these process inputs.

Note that words can similarly be given at any of these levels.

Edges (e.g. 01, or 0011) of objects and spaces after words, characteristics, or templates, are used to delimit things. And the primitives that are initially put on the IDEAS list (e.g. the letters of the alphabet, and simple edges, angles, or other pattern recognition characterizers that are commonly useful) begin to recognize parts of the input. Thus the letters, and then words like "NAME" and "THIS", and the edges of objects·, and then the objects themselves, will all be implied.

These in turn imply still other transforms that build compounds like "NAME THIS" or larger objects. These in turn imply response acts. This means that char­ acterizers will imply an apple (and probably some other objects, e.g. a pear and a face), and the implied objects may themselves imply the act of naming - at the same time that the verbal utterance NAME THIS also implies the act of naming, with a very high weight, so that it is very likely to be chosen.

Describing

An input of the sort: DESCRIBE THIS ((representation of one or more objects)) will get DECIDER-! to output a simple description, of the names of all things belonging to the "OBJECT" class the objects implied above a CHOOSE level, e.g. "APPLE TABLE CHAIR BANANA". The recognition of objects is much as for Naming, but additional linguistic transforms will recognize the word "DESCRIBE" and the import of the phrase "DESCRIBE THIS" -as implying the Describing act.

Any number of variants can be handled, e.g.: WHAT IS HERE ((objects)) SAY WHAT YOU SEE ((objects)) so long as the needed rewrite rules are in DECIDER-l's memory.

Finding Objects

If tiE verbal utterances within the scene (and/or internal needs) are recognized as implying the act of Finding, DECIDER -1 will branch to the Find routine. This searches for an implied object that has been put into the transformed SCENE that is of the class designated by the particular Find transform being executed. If the object is found, success is indicated by the placement of brackets, as though pincers, around it.

Acts are Multi-Determined, by Words, Things and Internal Needs

The verbal utterance can be a command, e.g.: FIND FOOD ((a scene of objects)) ((or)) WHERE IS FOOD ((a scene of objects)) or a request:

IS ANY FOOD AROUND ((a scene of objects)) or any other kind of utterance that, when parsed and understood, implies that a food object be found.

But remember that an act like Finding can be im­ plied not only by verbal utterances, but also by objects in the scene, and by internal needs. Thus, e.g., the recognition of a valued object, li.J<e a banana, or the partial recognition of several food objects, like apples, bananas, and crackers, can serve to imply, and, possibly, lead to the choice of, the act ·of finding (that is, getting, cr grasping) the banana, or the food object. Similarly, an internal need-state of hunger can imply the getting of a food object that will satisfy that hunger.

Moving and Manipulating Objects

An input like: MOVE BOXl TO BOX2 ((a scene of objects)) · will lead to the recognition of the particular objects to be manipulated and the overall action desired. When Move is chosen as response act, because it has be­ come the most highly implied transform on IDEAS, DECIDER-! will look for the specific objects or class members involved in the action, and actually change the SCENE, as specified.

DECIDER-! assumes that the action will not be triggered until all the neec;led objects have been recognized. So the perceptual characterizers must be implied with high weights, so they are merged onto IDEAS with higher weights than are the response actions. But it would be quite easy to extend DECIDER-! so that it continued to try to perceive objects not yet recognized, but needed to effect an act that it had decided to do (see Uhr, 197 3c 2 1).

Answering Queries

DECIDER-! can output internall y stored informa­ tion in response to an input. Thus we see it a) talk about parts of the scene (Naming, Describing), b) manipulating parts of the scene (Finding, Moving), and c) Answering, by accessing information stored in its memory in response to questions, either direct or implied, in the scene. Thus, e.g.: WHO IS THE PRESIDENT might lead to the response "NIXON".

Now the scene is treated as a purely verba l utterance, simply because only verbal rewrite trans­ forms succeed on it. But note how similar this is to the situation in which a request like: WHAT IS THIS ((scene of objects)) is intermingled with objects in a scene, in which case the act refers to information that has been extracted and recognized from that scene, rather than to informa­ tion that has been stored in memory .

Further Examples and Future Extensions

DECIDER-! is described more fully, with a number of examples worked out in detail, in Uhr, 1973d 22 . The actual program is presented, explained, and dis­ cussed. It is coded to EASEy, an English-like pro­ gramming language (a variant of SNOBOL) designed to be easy to understand (Uhr, 1973al 9).

DECIDER-! is presently being extended to handle scenes that continue over time. In this extension, perceiving, responding, and problem-solving all go on in parallel. The system decides when to respond. But to respond it may need to perceive further objects appropriate to its response. Or it may need to solve problems, to deduce a sequence of actions appropriate to the chosen response. Or it may output a request for needed objects, or for help. Thus perceiving, problem-solving, and acting are all intermingled. Each may call upon, and depend upon the other.