WHISPER: A Problem-Solving System Utilizing Diagrams and a Parallel Processing Retina

ABSTRACT

Diagrams are of substantial benefit to WHISPER, a computer problem-solving system, In testing the stability of a "blocks world" structure and predicting the event sequences which occur as that structure collapses. WHISPER's components Include a high level reasoner which knows some qualitative aspects of Physics, a simulated parallel processing "retina" to "look at" Its diagrams, and a set of re-drawing procedures for modifying these diagrams. Roughly modelled after the human eye, WHISPER's retina can fixate at any diagram location, and Its resolution decreases away from Its center. Diagrams enable WHISPER to work with objects of arbitrary shape, detect collisions and other motion discontinuities, discover coincidental alignments, and easily update Ita world model after a state change.

I. INTRODUCTION

Diagrams are very Important tools which we use dally In communication, Information storage, planning and problem­ solving. Their utility Is, however, dependent upon the existence. of the human eye and Its perceptual abilities. Since human perception involves a very sophisticated Information processing system, it can be argued that a diagram's usefulness results from Its suitability as an Input to this ·powerful visual system. Alternatively, diagrams can be vtew~d as containing Information similar to that contained In the real visual world, the canonical entity the human visual system was presumably designed through evolution to Interpret. From this latter perspective, diagrams are a natural representation of certain types of primarily visual Information, and the perceptual system sl.mply provides an appropriate set of database accessing functions. Both these viewpoints underly the work described In this paper.

The role of diagrams Is explored In a computer problem­ solving program, named WHISPER, which refers to diagrams during Its processing. A strong case for computer use of diagrams as models for Geometry has been made by Gelernter[ 1 963], and as general analogical representations by Stoman[1971]. Hayes[1974] discusses the theoretical nature of these representations. WHISPEFrs high-level reasoning component (HLR), built along the lines of traditional procedural AI problem-solving programs, has the additional option of requesting observations In a diagram. It does this by asking Ita "perceptual system" to "look at" the diagram with Its parallel processing "retina". The questions that the

perceptual system can answer are called perceptual . primitives. If necessary, the HLR can also make changes to. the current diagram.

" A major portion of this research was done at the University of British Columbia and Is fully described In the author's PhD. thests[Funt 76].

AND A PARALLEL PROCESSING RETINA

Brian V. Funt

Artificial Intelligence Laborator/ Stanford University, Stanford CA

II. MECHANISMS FOR PIAGRAM INTERACTION

The retina and perceptual primitives are designed to provide WHISPER with a new set of operations whose execution times are of the same order of magnitude as conventional machine Instructions. To achieve this a high degree of parallelism has been Incorporated Into the system. The retina Is a parallel processor, and the perceptual primitives are the algorithms It executes. (Do not be misled by the term "retina"; It refers to a general system of receptors and processors for the early stages of perceptual processing, rather than Implying any close resemblance to the human retina.) Each perceptual primitive, when executed by the retina, determines whether some particular feature Is present In the diagram. WHISPER's retina mixes parallel and sequential computation, so the features It can recognize are not subject to the same theoretical limitations that perceptrons [Minsky and Papert 1 969] are.

11 .1 The Retina

WHISPER's retina Is a software simulation of hardware which, given the rapidly advancing state of LSI technology, should soon be possible to build. It consists of a collection of processors, each processor having Its own Input device called a receptor. As with the human eye, WHISPER's retina can be shifted to fixate at a new diagram location (also a feature of a program by Dunlavey[1 975]), so that each processor's receptor receives a different Input from the diagram. This fixation facility Is Important because the resolution of the retina decreases from Its center to Its periphery. Without being able to fixate, It would be Impossible for WHISPER to examine the whole diagram In detail. Economy of receptors and processors dictates the use of decreasing resolution. (A declining resolution Is also a characteristic of the human eye.) Each receptor covers a separate segment of the diagram and transmits a single value denoting the color of that region. The geometrical arrangement of the receptors and the area each covers Is shown In Figure 1. The "circles" In the figure are called bubbles, and they are arranged In wedges (rays emanating from the center) and ~ (one of the concentric circles of bubbles). The resolution varies across the retina because a larger portion of the underlying diagram Is mapped onto a: bubble depleted by a larger circle. Since the complete group of receptors Is assumed to sense and transmit all signals In parallel, fixations are fast.

Each retinal processor has direct communication links to Ita 4 nearest neighbors plus one additional link via a common databus connecting all the processors to a supervisory

processor called the retinal supervisor. The communication. topology has been restricted In this simple way to ensure a, feasible future hardware Implementation.

The bubble processors are each small computers with Independent memory. They all simultaneously execute the same procedure; however, each bubble does not necessarily execute the same Instruction at the same time. In the current Implementation, a call to the LISP evaluator simulates a proc~ssor; and LISP mapping functions simulate the parallel control structure.

Although the bulk of the processing of the perceptual primitives Is done In parallel, there is also a small amount of sequential processing which is performed by the retinal supervisor. The retinal supervisor also directs the parallel processing by choosing which procedure the bubbles should execute next and broadcasting It to them.

11.2 The Perceptual Primitives

Each perceptual primitive detects a problem domain Independent diagram feature. The HLR assigns these features Interpretations pertinent to the problem It Is solving. The current set of Implemented perceptual primitives Include ones to: find the center of area of a shape; find the points of contact between a shape of one color and a shape of another; examine curves for abrupt slope changes; test a shape for symmetry; test the similarly of shapes; and visualize the rotation of a shape while watching for a collision · with another shape.

The center of area perceptual primitive Is an Illustrative example of the general operation of the perceptual primitives. It computes the center of area of a shape relative to the origin defined by the center of the retina. For each piece, AA, of the total area we need to compute the x and y components of Its contribution to the total area. Dividing the vector sum of these contributions by the total area yields the coordinates of the center of area. Since each retinal bubble receives Its input from a fixed sized area of the diagram and Is at a fixed location relative to the retina's center, each bubble can Independently compute the components of Its contribution to the total area. The bubbles whose receptors do not lie over any part of the shape simply do not contribute. The retinal supervisor performs the summation and the division by the total area. A separate primitive computes the total area. It simply totals the area of all the contributing bubbles. If the computed center of area Is far from the retina's center then Its accuracy can be Improved by fixating the retina on the estimated center of area and then recomputing. The decision to Iterate Is made by the retinal supervisor. The accuracy Improves because more of the central, high resolution portion of the retina Ia used.

The center of area Is used for more than simply providing the center of gravity of the objects in WHISPER's problem domain. Other primitives (symmetry, similarity, and contact finding) fixate on a shape's center of area before beginning their calculations. For example, If a shape is symmetrical Its center of area will be on Its axis of symmetry.

Another Important primitive Is visualization. What Is "visualized" Is the rigid rotation of a shape about the retinal center. While the shape · Is rotating the collision detection primitive can be called as a demon to watch whether the rotation causes the shape to overlap with another stationary shape. This Is useful both In "blocks world" environments Involving moving objects and In testing whether two shapes are equivalent under rotation. The process Is termed visualization because it does not Involve modifying the diagram, but Instead Is totally Internal to the retina Itself. It simply entails an organized and uniform exchange of Information amongst neighboring bubbles.

The geometrical arrangement of the bubble receptors Is what facilitates the visualization of rotations. From Figure 1 It can be seen that aligning the bubble centers along wedges results In a constant angular separation between bubbles of the same ring when they are from neighboring wedges, and that this constant Is Independent of the ring chosen. Thus, to rotate a shape clockwise each bubble marked by the shape simply sends a message to Its clockwise ring neighbor asking It to mark Itself. The sender then erases Its own mark. A collision Is detected If a bubble receives a message to mark when It Is already marked by a shape other than the rotating one. Although the shape Is rotated In sequential steps, the time required Is still short because (I) there are, as a maximum, only as many steps to be made as there are wedges on the retina (currently 36); and (II) all the message passing and collision checking occurs In parallel during each step.

11 .3 The Underlying Diagram

We began with the view that the retina Is a special purpose parallel processor designed to detect diagrammatic features without saying anything about the precise nature of the diagrams themselves. With the retinal processor In hand, we can now see that the representation of the diagrams Is unimportant as tong as each bubble receives Its correct Input. This Is analogous to a program which Issues a READ command without caring whether the Input Is coming from a card reader, a file, or a terminal. The method of mapping from the diagram to the retinal bubbles' Input must be fast, however, because the retina Is re-filled everytlme It Is fixated at a new diagram location.

There are at least two different types of representing media for the underlying diagram. The first Is the conventional medium of visible marks on a two-dimensional surface, usually paper. The map from diagram to human retina Is accomplished by the lens of the eye focusing the Incoming light. Since there Is simultaneous stimulation of the receptors, It Is a very fast process.

The second possible type of diagram representation Is similar to that used In generating computer graphics. The diagram Is specified as a list of primitive . elements (In graphics applications, usually line segment equations). In a similar vein, Kosslyn [1 976] proposes that human visual Imagery Is In some ways analogous to the storage and display of graphics Images. The parallel processing capacity of WHISPER's retina can be used to quickly map each primitive element Into the proper bubble Inputs. To mark all bubbles lying on line segment, S, the retinal supervisor directs every bubble to determine Independently If It Is on S, and If so, to mark Itself. Since this simple test -- do a circle and a line segment Intersect? -- Is performed by all bubbles simultaneously, the time required Is Independent of the length of S. The same method can mark all bubbles within any simple shape such as a circle, square or triangle In time Independent of Its area. Regardless of the type of primitive element, the time taken to "draw" the diagram on the retina Is, however, proportional to the number of primitives In Its description. ·They must be processed sequentially. With the fast parallel processing of each primitive this should only pose a problem for very detailed diagrams.

Due to the lack of true parallel processing, neither of the above two types of diagram representations Is used In WHISPER. Instead, the diagram Is Implemented as a square array. Ea.ch array cell denotes a point on a real world, pencil and paper diagram.

11.4 The Re-drawing Transformations

The re-drawing transformations are the procedures the HLR can call to change the underlying diagram. In WHISPER there are transformations for adding and removing lines, and for rigidly translating and rotating shapes. Other non-linear transformations could be added If required. These re­ drawing procedures are of course dependent upon the representation of the diagram they modify, and the ease and efficiency with which they can be Implemented could affect the choice of diagram representation.

Ill. WHISPER IN OPERATION

With the ·basic mechanisms for Interaction with the dlagr~m now understood, It Is appropriate to see how they are used In the course of solving a problem. We will consider problems of the type: predict the sequence of events occurlng during the collapse of a "blocks world" structure. The structure will be a piled group of arbitrarily shaped objects of uniform density and thickness. If the structure Is stable, there are no events to describe; If It Is unstable, then the events Involve rotations, slides, falls, and collisions. WHISPER accepts a diagram of the Initial problem state, and produces a sequence of diagrams, called snapshots, as Its qualitative solution. A quantitative solution specifying precise locations, velocltltes, and times Is not found; however, deriving one from a qualitative solution should not be too difficult [deKieer 1976].

Figure 2 Is a typical example of WHISPER's Input diagrams. They all depict a side view of the structure. Each object Is shaded a different "color" (alphanumeric value) so It can be easily distinguished and Identified. Objects' boundaries are also distinctly colored. The diagram depicts a problem, called the "chain-reliction problem", which Is particularly Interesting because the ·causal connection between objects B and 0 must be discovered.

·n"'"''"''"'"n'''"''"'"""""'"'''"'""''"'"'"'""'"''''"''""'"'"""""'

Figure 2

111.1 The Qualitative HLR

The HLR Is the top level of the WHISPER system. It Is solely responsible for solving each problem; the diagram and retina are simply tools at Its disposal. It consists of procedural specialists which know about stability, about the outcome of different varieties of Instability, how to Interpret each perceptual primitive, and how to call the transformation procedures to produce the solution snapshots. There are two types of lnstabllltes - rotational and sliding. For clarity, sliding Instabilities will not be discussed for the present. Operation of the system follows the steps:

• ( 1 ) determine all Instabilities
• pick the dominant Instability
• find pivot point for rotation of unstable object
• find termination condition of rotation using retinal visualization
• call transformation procedure to modify diagram as determined In step (4)
• output modified diagram as a solution snapshot
• use snapshot from step (6) as Input and restart from step (1 ).

In what follows we elaborate on each of these steps.

The diagram and retina are an Invaluable aid to the HLR In discovering what stops an object's motion, and In accomplishing the necessary state change. The chain reaction problem demonstrates this. The stability specialist directs the retina to fixate at numerous locations while perusing the diagram, and from an analysis (discussed below) of the visible support relationships determines that B Is the only unstable object. B will pivot about the support point closest to Its center of gravity. The retina Is fixated there (the top right corner of A), so B's rotation can be visualized. As the object rotates, two events are possible. It may collide with another object, or It may begin to fall freely. The conditions under which either of these occur are monitored during the visualization. From this simulation of B's rotation, Its collision with 0 Is discovered, and Its angle of rotation and location of first contact with D are found. Because of the coarseness of the retinal resolution, this angle of rotation Is only approximate. This approximate value Is used In conjunction with feedback from the diagram to refine the angle of rotation as follows. First the re-drawing transformations are called to produce a new diagram In which ·a Is rotated by slightly less than the estimated value. The rotation Is made on the short side so that B will not overshoot. The retina Is then fixated on the anticipated point of collision so that the gap between the two objects can be examined. If there Is none, then the update Is complete; however, If there Is, then B Is rotated again until the gap Is closed. The resulting diagram Is output as WHISPER's first snapshot of the solution sequence.

111.2 Motion Discontinuities and Experimental Feedback

There are, several Important observations to be made at this point. One Is that discovering the reason for the Interruption of an object's motion, accomplished so simply here for B through visualization, Is generally found to be a very difficult p,roblem. Physics provides equations for object motions, but these equations describe a condition which theoretically lasts Indefinitely. They do not Indicate when new boundary conditions should take effect. Certainly It Is possible to design a set of special heuristics specifying when and where collisions are most likely to occur (e.g. below the rotating object). However, It Is quite probable that the collision occurlng In Figure 3 would be overlooked, whereas WHISPER's visualization process would definitely detect it.

WHISPER relies on experimental feedback to successfully update Its diagram In Its method of visualization followed by· gap closure. This method Is basically a pragmatic equivalent to the unfeasible experiment of rotating the object In the diagram by very small Increments until a collision occurs ·. . Usually feedback Is thought of In terms of a robot Immersed In a real world environment. In WHISPER's case, however, the feedback Is from a situation analogous to that In the real world - the diagram and diagram transformations · rather than from observation of actual falling objects (Funt 1 976). Using this feedback WHISPER Is able to find when and where discontinuous changes In an object's motion occur without being forced to use sophisticated, time-consuming, "number· crunching" algorithms for touch tests [Fahlman 1 973) (for arbitrary shapes), and avoids considering every object In the

·universe as a·posslble candidate for a collision.

Once WHISPER has produced the first snapshot, It Is ready to compute the next one. All the Information the HLR needs for this Is contained In the first snapshot diagram. Thus to produce the next snapshot, the HLR takes Its last output snapshot as Input, and begins processing exactly as If It were working on a fresh problem. Although some results derived while working on the previous snapshot remain valid (e.g. some contact relationships will still hold), many will be Inapplicable to the new problem. It Is easier to disregard this old Information than to sort It out and update It, since the retina provides a fast and efficient method of. fetching It from the new diagram.

111.3 Subseauent Snapshots of the Chain Reaction Problem

The analysis producing the second and third snapshots Is very similar to that for the first. In Figure 4, B's weight on 0 causes D to be unstable. Its rotation Is visualized with the' retina fixated at the peak of C leading to the discovery of Its collision with the table. The diagram is updated to produce the second snapshot, Figure 5, which Is again Input for further ·analysis. B now lacks sufficient support, and topples to hit D again as shown In Figure 6. The complexity of the problem rises sharply at this point, and WHISPER's analysis ends, as, I believe, would most peoples'.

B and D could be shown to fall simultaneously (WHISPER currently does not) by rotating D only part of the way to the table before allowing B to catch up, and then Iterating this process a few times until D reaches the table.

.. 'J .. 'J'J'J · ., ........... "."'".""'''"'"'"''"'...,'"''"'

Figure 6

......................... .,.,, .................... .

.. ,..,.,,,.,., .... ,,..,_,.,.,,., ... ,""'"'"'"'""'' '"n"" '""'"'""''"'"""'"""""""'""""'"~'"'"''"'"

111.4 Slide Problems

Unstable objects may also slide. Although the basic outline of the solution process -- test stability, find termination point of motion, update diagram, output snapshot, restart with the output as Input -- Is the same, there are some essential differences In handling sliding objects. The most Important arises because It Is not possible to VIsualize the slide of an object down an arbitrary curve. What WHISPER's does Instead Is examine the curve Itself with Its retina.

A variety of conditions can terminate an object's slide. For example, there may be a sharp rise (a bump), a sharp fall (a cliff), or a hill which Is higher than the starting point. Also the object may slide Into another object resting on or near the surface. WHISPER tests for these conditions by fixating at regular Intervals along the curve. At each point It Invokes the perceptual primitives relevant to eacti of the above conditions. There are some cases, for example when a plank slides off a box, when WHISPER examines the surface of the underside of the sliding object.

When It finds the endpoint of a slide, WHISPER updates the diagram using the re-drawing transformations In a two step process. First, It translates the object to the new point, and then, If necessary, rotates it. A rotation Is usually required, because If the curve Is a not simple straight Incline, the orientation of the object changes as It moves. WHISPER determines the magnitude of this corrective rotation by re­ establishing, via rotation visualization, the contact relationships which existed between the object and the surface prior to the start of the slide.

111.6 Benefit of the Diagram During Slide Analysis

In the curve examination and diagram update process, the diagram Is very useful to the HLR In the course of curve following, as well as providing feedback as It did In the case of rotations. The main pitfall In curve following Is the possibility that two objects will coincidentally align so that a smooth curve Is formed across them both. An object could then begin Its slide on one object and continue sliding along the other as shown In Figure 7. This emergent property of the curve must be noticed, and the two curve segments appended. In a system relying on an Independent description of each object, this would pose a significant problem because one would require: (I) that It have a built In expectation that the situation might arise; (II) that It continually check for the situation; (Ill) that Its check Involve testing whether the first object touches any other object In the universe; and (lv) that It know how to amalgamate the· two separate curve segment descriptions Into a new curve description. For WHISPER there Is no problem because two aligned surfaces of neighboring objects form a continuous curve In the diagram; WHISPER only has to look at this curve, rather than, In a sense, discover or const~ct it.

111 .6 The Stability Test

A full discussion of WHISPER's stability testing routines cannot be given In the limited space of this paper; however, we shall give an Impressionistic view. Rather than solve the problem with a sophisticated general method, as Fahlman [1973) did In his BUILD system, WHISPER seeks qualitative solutions using rules corresponding to those a person untrained In Physics might apply. The HLR has specialists which express rules like: "If an object hangs over too far, It will topple"; and "If an object and one of Its supporters make contact along a surface (rather than at a single point) and If this surface Is not horizontal, then the object will slide." A frictionless environment Is assumed.

Overall organization of the stability test ·Is based on the observation that a complete structure Is stable If each of Its Independent subparts Is stable whenever their supporters are stable. An Independent subpart Is any connected group of objects which Is not supporting anything. For example, In Figure 2 of the chain reaction problem the Independent subparts are objects B, D, AB, and DC, but not A and C. Thus the Initial structure Is broken down Into smaller sub­ structures whose stability as Individual units Is easier to test than the stability of the structure as a whole. When their stability ls tested, B and AB are found to be rotationally unstable, while D and DC are found to be stable. Since B Is a subpart of AB, It Is the dominantly unstable object, and .therefore It Is the one rotated. If AB were unstable, but B stable, then AB would be rotated (I.e. objects A an·d B would be ro~ated together as If they were a single object).

Incidentally, treating two objects like A and B as a single object AB Is another example of a situation In which two descriptions must be amalgamated. It Is a trivial · task for WHISPER to amalgamate two object descriptions, since all It need do Is Interpret their two color codings as the same color.

The stability test uses the diagram and retina to find contact relationships, centers of area, and slopes of contacting surfaces. The symmetry perceptual primitive Is used to accurately establish that D In the chain reaction problem will balance.

IV. CONCLUSION

WHISPER demonstrates the advantages and feasibility of using diagrams as an aid In problem-solving. A fundamental component of the system Is a retina which blends sequential and parallel processing while limiting the quantity of processors and processor Interconnections to a fixed, not too large number. By asking questions of the retina, the HLR Is able to obtain the type of experimental feedback from the diagram which Is normally expected only as a result of Interaction with the real world.

ACKNOWLEDGMENT

I have benefitted from the Inspiration of Raym()nd Reiter, Alan K. Mackworth, Richard S. Rosenberg, and Gordon McCalla.

This research was supported by the National Research Council of Canada under grant A7642, and through the author's NRC Postdoctora! Fellowship.