Inter-diagrammatic Reasoning

1 Introduction

Humans possess a highly developed ability to reason with visual information such as diagrams. It has been shown that endowing a computer with such an ability could be of great benefit in terms of both human-computer interaction and computational efficiency through explicit representation [Larkin and Simon, 1987]. To date, research in diagram­ matic reasoning has dealt with intra-diagrammatic reasoning [Chandrasekaran eta/., 1993; Narayanan, 1992; Narayanan, 1993] almost to the exclusion of inter-diagrammatic reasoning.

Intra-diagrammatic reasoning can be defmed as a process of inference realized by the application of various operators to a given single diagram (for example, see [Furnas, 1992]). Inter-diagrammatic reasoning, on the other hand, can be defmed as a process of inference realized by the application of operators to groups of related diagrams (for example, see [Anderson, 1994; Anderson and McCartney, 1995]). Dia­ grams are related if they can be combined in ways that pro­ duce useful information. Two types of related diagram groups can be defmed, sequences and suites. These differ in

*Previously at Sacred Heart University, Fairfield, CT, U.S.A.

Robert McCartney

Computer Science and Engineering University of Connecticut 260 Glenbrook Road Storrs, Connecticut 06269-3155

U.S. A.

the way in which a single diagram within a group is related to other qiagrams in the same group.

A diagram sequence [Anderson, 1994; Anderson and McCartney, 1995] will be defmed as a meta-diagram com­ posed of a number of diagrams arranged in an order that in­ corporates some marmer of forward moving time. Often, each of the diagrams in the sequence can be considered a discrete snapshot of some continuous phenomenon de­ scribed by the sequence as a whole. Examples of such dia­ gram sequences include game notation, chordal musical notation, weather maps, assembly instructions, and instruc­ tions for a product's use.

A diagram suite will be defmed as a meta-diagram com­ posed of a number of diagrams that present different facets of a given entity at the same moment in time. Each of the diagrams of the suite can be considered as a view of the en­ tity from some single, unique perspective. When combined, the suite can present the entity as a whole. Examples of such diagram suites include architectural renderings, anatomical drawings, and cartograms.

We present a syntax and semantics of inter-diagrammatic reasoning and then introduce a number of inter­ diagrammatic operators and functions. Next, example uses of these operators and functions are provided in various do­ mains. A brief discussion of related work follows and, fi­ nally, we offer our conclusions.

2 Diagram Syntax and Semantics

Most generally, we will syntactically defme a diagram to be a tessellation of a planar area such that it is completely cov­ ered by atomic two dimensional regions or elements. The semantic domain will be defined as {v0, ··· , v1· 1 } denoting ani valued, additive gray scale incrementally increasing from a minimum value v0 ,WHITE, to a maximum value v 1 · 1 , BLACK. Intuitively, the gray scale values correspond to a discrete set of transparent gray filters that, when overlaid, combine to create a darker filter to a maximum of BLACK.

3 Diagrammatic Operators and Functions

The following primitive unary operators, binary operators, and functions provide a set of basic tools to facilitate the process of inter-diagrammatic reasoning. We have striven for simplicity and generality in the hope that these tools might be applicable in a wide variety of diagrammatic domains.

3.1 Unary operators

NOT, denoted -. d, is a unary operator taking a single dia­ gram that returns a new diagram where each element is BLACK if the corresponding element in d is WHITE, and WHITE otherwise.

3.2 Binary operators

Binary operators take two diagrams, d1 and d2, of equal di­ mension and tessellation and return a new diagram where each element has a new value that is some function of the two corresponding elements in the operands.

OR, denoted d1 v d2, returns the maximum of each pair of elements. The maximum of two corresponding elements is defined as the element whose value is closest to BLACK.

AND, denoted d1 1\ d2, returns the minimum of each pair of elements. The minimum of two corresponding elements is defmed as the element whose value is closest to WHITE.

OVERLAY, denoted d1 + d2, returns the sum of each pair of elements. The sum of values of corresponding elements is defmed as the sum of their respective values' subscripts.

PEEL, denoted d1 - d2, returns the difference of each pair of elements. The difference of values of corresponding ele­ ments is defmed as the difference of their respective values' subscripts.

ASSIGNMENT, denoted d1 ¢: d2, modifies d1 such that each element has the value of the corresponding element in d2· (Note that non-diagrammatic assignment will be symbolized as := and the equality relation as=.)

3.3 Functions over diagrams

NONNULL, denoted NONNULL(d), is a one place Boolean function taking a single diagram that returns FALSE if all elements of dare WHITE else it returns TRUE.

3.4 Functions over sets of diagrams

ACCUMULATE, denoted ACCUMULATE (d, ds, o), is a three place function taking an initial diagram, d, a set of diagrams of equal dimension and tessellation, ds, and the name of a binary diagrammatic operator, o, that returns a new diagram which is the accumulation of the results of successively ap­ plying o to d and each diagram in ds .

MAP, denoted MAP(f, ds), is a two place function taking a function f and a set of diagrams of equal dimension and tes­ sellation, ds, that returns a new set of diagrams comprised of all diagrams resulting from application of f to each dia­ gram in ds.

FILTER, denoted FIL TER(f, ds), is a two place function tak­ ing a Boolean function, f and a set of diagrams of equal di­ mension and tessellation, ds, that returns a new set of diagrams comprised of all diagrams in ds for which f returns TRUE.

CARDINALITY, denoted CARDINALITY(s), is a one place function taking a fmite set that returns the number of ele­ ments in s.

4 Example Domains

As example uses of the previously postulated inter­ diagrammatic operators and functions, we 1) develop a heu­ ristic for a game, 2) infer the correct fmgering of a sequence of instrumental chord diagrams, and, 3) infer the quality of precipitation in a suite of cartograms.

4.1 Battleship

We have chosen the simple game of Battleship as one do­ main in which to test the diagrammatic operators and func­ tions. The domain and its constraints are described first followed by a description of the inference goal and a de­ tailed account of a working system based on this domain.

Battleship, Figure 1, is a game for two in which both players place ships (groups of two, three, or five contiguous blocks- a block being the atomic element of this domain) diagonally, horizontally, or vertically on a indexed, ten by ten grid. Each player then tries to sink the other player's ships by shooting them (marking all of the blocks compris­ ing the ship) without ever seeing the grid on which they are placed. This feat is accomplished by the currently attacking player sending a salvo of shots (announcing the coordinates of seven blocks) and the other player providing a damage report that details the number of hits sustained by each of his/her ships but not the indices of each hit. The wirmer is the player who sinks the other player's ships first.

We are interested in applying the proposed diagrammatic operators and functions to the end of predicting the best shots a player might take given the progress of the game so far. To clarify this process, we will discuss it in terms of a subset of Battleship. The subset will consist of the game as described limited to only a single ship, namely the battle­ ship (a five block group). Further, we will consider the placement of the battleship as being completely random. Within these constraints, it is possible to construct a dia­ gram via the proposed diagrammatic operators that displays the entire set of possible battleship positions and, by simple inspection, discover the blocks that are most likely to be in­ cluded in the battleship being sought. The intuition is that we would like to combine information from each possible configuration of a battleship onto a single diagram. The "darkness" of a given block in this diagram indicates the number of possible battleships it could be a part of and, hence, its likelihood of being a good candidate for a next shot. This is equivalent to numerically calculating the prob­ abilities for each cell.

·

In the next section, we describe the process of displaying all possible positions of a ship on a single diagram. An ex­ ample is then provided that details the diagrammatic reason­ ing required to develop a heuristic from a sequence of battleship shot boards.

Displaying a set

Figure 2 details the process by which an entire set of ships can be displayed on a single diagram. A diagram with only WHITE blocks (denoted D1) is OVERLAYed with another dia­ gram (denoted D 2 ) . D 2 has one possible position of a battle­ ship on it, represented as a contiguous five block region containing the first level of gray above WHITE (GRAY,) . OVERLAYing produces another diagram that, after this single step, happens to be identical to 0 2· This newly created dia­ gram becomes the new D1 which, in tum, is OVERLAYed with another diagram that has a different possible position of the battleship on it. Yet another diagram is produced that con­ tains a representation of both of the ship positions so far in­ cluded. This is due to the additive nature of the domain values previously defmed combined with the semantics of the OVERLAY operator. The effect on the diagram is that ships that overlap each other make blocks they have in com­ mon darker than the blocks they don't have in common. In the example, the common blocks will now have the value of GRAY 2 (GRAY, + GRAY,) whereas the other blocks will have the value GRAY, (WHITE+ GRAY,}. This process is repeated until all possible positions of a ship have been overlayed onto a single diagram.

In more formal terminology, the function ACCUMULATE( 0, ShipPositions, +) is applied where 0 (null diagram) is the diagram initialized to WHITE and ShipPositions is a domain specific set of all diagrams of possible single battleship po­ sitions. In each of these diagrams, the blocks that are part of the battleship take the value v1 while all other blocks take the value v0· The fmal result of this application of ACCUMU­ LATE is a diagrammatic representation of all possible ship positions with those blocks most likely to be included in a ship being the darkest and those that are least likely, the lightest.

Developing the heuristic

Figures 3 and 4 detail an example of the process by which the set of possible ships is constrained as the game pro­ gresses and a diagrammatic representation of the heuristi­ cally best shots is developed. First, a new salvo of shots is placed on the previous game board as BLACK blocks. At the start of the game, the board will contain only WHITE blocks but, as each tum is taken, this board will fill with shots from each tum. To differentiate between previous and new shots, the previous board (denoted PreviousBoard) is NEGATEd and ANDed with the current board (denoted CurrentBoard) giving the current salvo (denoted CurrentSalvo) of shots. Formally:

Current Salvo <= --, PreviousBoard 1\ CurrentBoard

Next, the number of hits (denoted Hits) scored by the salvo is determined. This is accomplished diagrammatically by ANDing the diagram containing the current salvo of shots with the diagram that contains the battleship in its actual po­ sition represented as GRAY1 blocks (denoted Actual­ Battleship). Since ANDing is defmed as taking the minimum of each block of a diagram, the resulting diagram will con­ tain GRAY1 blocks for each hit in the current salvo and WHITE blocks everywhere else. Hits can then be counted, diagrammatically, by ANDing the resulting diagram with each member of a predefmed set of inspection diagrams - diagrams used to isolate elements . In the current domain, the set of inspection diagrams is comprised of all possible diagrams containing a single BLACK block (denoted Single­ Blocks). As each of these are ANDed with the diagram con­ taining GRAY1 blocks for each hit in the current salvo, only those that have their single BLACK block in the element cor­ responding with the GRAY1 block will yield a new non-null diagram. The result of each operation is tested with the Boolean NONNULL function and its successes are counted thus producing the number of hits. The entire process can be formally, and more compactly, stated using the diagram­ matic operators and functions (A. is used in the standard way to denote function abstraction):

Hits :=

CARDINALITY(

FIL TER(NONNULL,

MAP(A(y) (y 1\ CurrentSalvo 1\ ActuaiBattleship), SingleBiocks)))

The First Salvo

In the example, the first salvo, Figure 3, results in no shot hitting the battleship as placed in Figure I. This information is then reflected on a diagram by a process of overlaying similar to that previously described. Every possible instance of the battleship is overlayed as a contiguous five block re­ gion of GRAY1 onto a diagram initialized to WHITE. Now, however, a possible instance of a battleship must also con­ form to the number of hits specified. That is, in order to be considered possible, each five block region must overlap the number of hits (BLACK blocks on the current salvo diagram)

·-

exactly. In the current example, since there were no hits, a five block region that overlaps any BLACK block is not con­ sidered possible and, therefore, will not become part of the new set when displayed.

This effect is achieved by ANDing a given instance of a battleship, represented with GRAY1 blocks, with the diagram representing the current salvo. The resulting diagram will contain GRAY1 blocks for each hit that the given instance of a battleship overlaps and WHITE blocks everywhere else. These GRAY1 blocks are counted via the inspection dia­ grams as previously detailed and this count compared with the number of hits needed. If these numbers are equal, the given battleship instance is OVERLAYed on the accumulated result otherwise it is discarded. When all such battleship in­ stances have been so OVERLAYed, the resulting diagram rep­ resents the current set of possible battleships newly constrained by the information in the damage report con­ veyed by the defending player. This process can be more formally stated using the diagrammatic operators and func­ tions as:

ACCUMULATE( 0 , FIL TER(A. (x) (Hits = CARDINALITY( FIL TER(NONNULL, MAP(A(y) ( y 1\ CurrentSalvo 1\ x), SingleB/ocks))) ), ShipPositions), +)

The resulting diagram is a collection of blocks with values ranging from WHITE to BLACK. If the placement of the bat­ tleship is random, BLACK blocks are most likely to be con­ tained in the battleship given the hit information so far with lighter shades of gray becoming decreasingly less likely. Further, given the damage report information, WHITE blocks are guaranteed not to be included as part of the battleship a player is seeking. This result (denoted HeuristicDiagram ), then, can be considered a diagrammatic heuristic that indi­ cates the probabilistically best shots for the next salvo.

The Second Salvo

The second salvo, Figure 4, uses the information previously derived by including within it the seven darkest blocks on the heuristic diagra.m. First, the previous board is NEGATEd and ANDed with the current board giving the current salvo of shots. The number of hits is determined as described O·A·-· Figure 4: Battleship, the second salvo previously and results in a count of one. The set of possible ships, ShipPositions, is updated so as not to include any ship instances that were deemed impossible by the previous salvo and the remaining possible ship instances are then OVERLAYed as before.

Lastly, since blocks of the salvo itself will be included in the heuristic diagrams generated from damage reports of one or more hits, these blocks need to be removed from the final diagrammatic heuristic as they are not available for fu­ ture salvos. This is accomplished by ANDing the negation of the current board with the heuristic diagram developed so far. Thus the entire process of developing a heuristic dia­ gram for the constrained game of Battleship can be formal­ ized as:

-, CurrentBoard 1\ ACCUMULATE( 0, ShipPositions := FIL TER{A(x) Hits= CARDINALITY( +). FIL TER(NONNULL, ShipPositions), MAP(A(y) (y 1\ CurrentSalvo 1\ x), SingleB/ocks)),

In summary, this heuristic diagram is computed from in­ formation about where ships cannot be from previous salvos (in the previous heuristic diagram) and the hit information from the current salvo. It provides guidance for the aggres­ sor's next shots and provides information for the next heu­ ristic diagram in the sequence.

4.2 Guitar Chord Notation

Guitar chord notation attempts to denote positions of fmgers for a given chord by diagrammatically representing strings and frets of a fmgerboard along with dots to represent fmger positions. Syntactically, vertical lines represent the strings of a guitar whereas horizontal lines represent its frets. A dot on a string represents where some fmger is placed to pro­ duce a desired pitch. Semantically, a fingering is a specification of exactly which of four fmgers to use to real­ ize the dots of the diagram. For example, given that num­ bers 1 through 4 represent the index fmger to the little fmger, the following is a chord diagram complete with a Chord diagrams are superior to standard musical notation for inferring fmgering information since the fmgerboard po­ sitioning of the chord is explicitly shown on the diagram but must be inferred from standard musical notation. Even so, semantic ambiguity arises in guitar chord diagrams because 1) fmgerings are often not specified and 2) there exists a one-to-many mapping between the dots and possible fmger­ ings. A given chord can sometimes be fmgered many ways with the preferred way often being context dependent. That is, the preferred fmgering of a chord will often depend on one or both of the chords preceding and following it in the diagram sequence. For example, when there is no dot in common between them and, therefore, the fmgering for the second chord defaults to its least demand­ ing state as shown. If, however, there is a dot in common and the fmgering for the second chord attempts to conserve fmger movement by leaving the fourth fmger in place as shown.

The atomic element in this domain is represented as dots. Each dot can either be black or white; no intermediate gray values are necessary for this domain. Applications of simple diagrammatic operators to sequences of chord diagrams ( C1 and C2) produce useful information.

ANDing two such diagrams will yield a new diagram that is comprised of all black dots these diagrams have in com­ mon, more formally C, " C2 ~ CommonFingers. For exmnpllim A EHHl o>ffim.

ANDing the sequentially frrst diagram with the negation of the second will yield a new diagram that is comprised of only those black dots that were removed over time, more fonnallyM: :lij: m··

ANDing the negation of the sequentially frrst diagram with the second will yield a new diagram that is comprised of only those black dots that were introduced over time, more fonn·:Ym~:m:m;··

(Note that a background grid of strings and frets must also be merged to the above in order to produce the indicated results.)

Inferring a Chord Fingering

The reasoning goal in this domain is to infer a fmgering for a chord in a sequence of chord diagrams given a fmgering for the chord immediately preceding it. For example, given a fmgering for m, a fmgering for EHHl can

be inferred via diagrams generated by the postulated opera­ tions in concert with two simple, domain specific rules: 1) whenever possible keep fmgers in the same position, and 2) when a new fmger is needed, use next numerically available fmger.

Since there can only be one significant fmger on any given string, we can represent a fmgering for a given chord by a fingering vector, [s6, s5, s4, s3, s2, sJl, where each s; is a fmger number 0 through 4 signifying which (if any) fmger is to be placed on the string i. (The strings on a guitar are numbered from lowest pitch to highest pitch as 6 through 1.) The fmgering that will be used for the frrst chord in this example will be represented as [0,3,2,0,1,0]. A list of avail­ able fmgers can be represented by an available finger set that contains the numbers of all fmgers not currently in use by a chord. This can be generated for any given chord by inspecting its fmgering vector. Thus, the fmgers not in use by the frrst chord in the example is represented as { 4} .

The frrst step to inferring a fmgering for the second chord is to update the available fmger set with newly available fm­ gers. These can be found by inspecting RemovedFingers. Any finger that was used to realize a dot that was removed from the frrst chord is now available. To accomplish this inspec­ tion, six lnspectionDiagrams , id; , are defmed, each associated with one string in the diagram:

When each of these are individually ANDed with a given dia­ gram, a background grid devoid of dots (Nul/Chord) will re­ sult whenever there is no dot on the string associated with the inspection diagram in the diagram under inspection. Further, whenever there does exist a dot on the currently in­ spected string, such ANDing will infer a diagram comprised of the background grid with that dot in place. Formally stated: FILTER (NONNULL, MAP( A.(x) (RemovedFingers 1\ x), lnspectionDiagrams)) In the example,

Since the only inference that produces anything other than the background grid is the one involving the fifth string's inspection diagram, the fmger that was used on s 5 in the fm­ gering vector (namely, finger number three) is now avail­ able. The available fmger set is then updated to {3,4}.

A similar approach is taken to fmd which fmgers (if any) should remain in the positions they occupied in the first chord diagram. Each inspection diagram is ANDed, in tum, to CommonFingers. The inferences that do not produce an empty background grid are exactly those made with inspec­ tion diagrams associated with the strings that should main­ tain the same fmgering. These fmgers are then transferred to the new fmgering under development. Formally stated: FIL­ TER (NONNULL, MAP( A.(x) (CommonFingers 1\ x), lnspectionDiagrams)) . In the example,

therefore, since the first and second fmgers were used on the second and fourth strings, respectively, the partial fm­ gering for the next chord that keeps these fmgers the same is [0,0,2,0, I ,0] given a fmgering vector that is initialized to all zeros.

Next, lntroducedFingers is used to fmd which strings re­ quire new fmgers (if any). Again, the inspection diagrams are used to fmd which diagrams have dots in this result. Those that do need to have fmgers placed on their associ­ ated strings. Formally stated: FILTER (NON NULL, MAP( A. (x) (lntroducedFingers 1\ x), lnspectionDiagrams)). In the example,

is the only inference that results in more than a background grid, so a new fmger is needed on the third string. This fm­ ger is retrieved from the available fmger set via a minimum function that returns the smallest fmger number in the set, in the example, 3. This fmger number is then placed in the vector at the place corresponding to the string that needs a fmger, s 3 · The fmal fmgering vector for the second chord diagram in the example is [0,0,2,3,1,0] .

This example shows how diagrammatic representations can be combined with other knowledge representations to infer new knowledge. The indices associated with each in­ spection diagram serve as the intersection between the dia­ grammatic inferences and the symbolic inferences. It is our expectation that diagrammatic representations will prove to be useful in many instances of such multimodal reasoning.

4.3 Cartograms

Another application of the postulated diagrammatic opera­ tors is in the domain of cartograms, in particular, ch/orop­ leths- maps that present data as areas of different colors or gray-level intensities. When such maps depict different data for the same geographic location, they are related in pre­ cisely the marmer needed to perform diagrammatic inference.

The TemperatureMap and PrecipitationMap chloropleths de­ picted in Figure 5 comprise a diagram suite in that they are two different aspects of a geographic location that occur si­ multaneously. TemperatureMap is a map in which tempera­ tures are denoted by different gray scale intensities- darker signifying higher temperatures and lighter signifying lower temperatures. PrecipitationMap is a map that denotes by some gray value where it is currently precipitating.

Inferring a New Chloropleth

Figure 5 details how the proposed diagrammatic operators can be used to infer a new chloropleth that represents where it is likely to be snowing within the given geographic loca­ tion by fmding the intersection of the area where it is thirty degrees or below and the area where it is precipitating. A cartogram covered with the gray value that represents the thirty degree range (denoted 30DegreelntensityMap) is PEELed from TemperatureMap, forcing all gray values representing the thirty degree range and below to WHITE while only light­ ening other grays. The result of this operation is then ne­ gated forcing all non-WHITE areas to WHITE and the thirty degree and below area to BLACK. Finally, this is ANDed with PrecipitationMap producing a new chloropleth that represents the area within the given geographic location in which it is in the thirties or below and is precipitating- by defmition the most likely area for snow. Formally, this process can be represented as:

-,(Temperature Map- 30DegreelntensityMap) 1\ PrecipitationMap. There are many similar inferences that can be made with such maps. Further, other questions could be asked of a sys­ tem that dealt with this type of data. For instance, given a set of inspection diagrams representing the states, questions such as "In which states is it precipitating?" , "How many states currently have temperatures below thirty degrees?", or "Is it likely to be snowing in Connecticut?" can be easily answered diagrammatically. We envision a geographic data­ base of diagrammatic data with queries presented diagrammatically and resolved by diagrammatic inferencing as a reasonable goal of our research.

5 Related Work

As previously stated, little work has been done with dia­ gram sequences and suites per se. One notable exception is the work done by Bieger and Glock [1985; 1986]. Beside attempting a taxonomy of categories of information pre­ sented in what they term "picture-text instructions", they performed rigorous experimentation with actual subjects and monitored their use of such instructions to the end of identifying the most critical categories. The direction of their work is not towards automating diagrammatic reason­ ing but towards understanding human use of such informa­ tion as is work by Willows and Houghton [1987].

Furnas [1992] postulates a logic that deals with diagrams via BITPICT rule mappings that can be used to transform one diagram into another and, therefore, allows reasoning from diagrams to diagrams. Interesting as this reasoning is, these explicit rule mappings can be subsumed by the opera­ tors and functions currently proposed. Further, Furnas' work does not attempt to reason about diagrams in se­ quences but, rather, its crux is the generation of sequences of diagrams to accomplish some reasoning goal pertaining to a single diagram.

Lastly, Chapman [ 1991] posits a number of primitive vis­ ual operators that are used as building blocks of various task-specific visual routines. These operators process infor­ mation about single frames of a video game; no reasoning about sequences of frames takes place. Interestingly, though, two main operations of his work have analogs in the inter-diagrammatic operators we have postulated. Visual at­ tention, focusing on a subset of a scene, can be seen as analogous to the PEELing and negating of a cloropleth to concentrate on one particular gray-level intensity. Visual search, fmding particular elements in a scene, is analogous to our use of inspection diagrams.

6 Conclusion

We have postulated a number of diagrammatic operators and functions and have shown how they can be useful in reasoning with sequences and suites of related diagrams. In particular, we have used them in the domains of game play­ ing, musical notation, and cartograms. These operators and functions provide a clear and concise means of describing diagrammatic manipulations in an important subset of dia­ gram groupings, namely, those in which objects are identifi­ able by their positions within diagrams. This is a first step in an attempt to endow a system with full diagrammatic rea­ soning capabilities that we believe will prove extensible to other, less constrained groupings of diagrams.

In general, we believe that a diagrammatic reasoning ap­ proach that deals with diagrammatic representations directly will often prove beneficial because it will avoid the difficult problems of 1) generating exhaustive textual or other representations that specify all objects and their relation­ ships and 2) focussing attention on only pertinent objects and relationships. Further, when viewed at the pixel level, the postulated diagrammatic reasoning operators are closely related to raster graphics operators and, therefore, it is possible that hardware optimized for such . graphics opera­ tors could efficiently perform diagrammatic operations.