Bunt H., Beun R.-J., Borghuis T. (eds.) Multimodal Human-Computer Communication. Systems, Techniques, and Experiments

Подождите немного. Документ загружается.

Using Cooperative Agents to Plan Multimodal Presentations 141

and computer32x32 is the entry code. The width and height of this icon are both

32 pixels, and the display position is set to (0,0) at this stage.

If the intended information is atomic, the

Agent-planning

procedure starts

to run from the initial planning stage (Section 5.1). That is, the

Agent-planning

procedure of icon agents starts at Step 8. Steps 14-16 are not performed by icon

agents, since these agents are not master agents.

modality:

icon

position: (0,0)

width: 32

height:

name: "computer"

bitmap: computer32x32

Fig. 11. Sample icon segment

The size of the icon is determined in Step 8 of

Agent-Planning

using the

following rules:

Rule1

If width and height are not specified, an icon of the default size, viz 48x48,

is generated. If an icon of this size is not available in the icon library, an icon

of the closest size that is larger than the default size is retrieved. For example,

in the current implementation, a box icon of size 64x64 is generated in Fig. 2

since the icon agent is unable to find a box icon of size 48x48. If an icon of

size 64x64 is not available, an icon of size 32x32 is generated.

Rule2

If width and height are specified, and the agent is able to find an icon of

the specified size or smaller, the display is generated. These parameters are

set to the icon's actual size after the icon is generated.

When an icon agent is first activated during the initial planning stage, the

width and height in its segment are unspecified. Hence,

Rule1

is used to produce

an initial icon to convey the intended object. This icon is stored in the master

agent's blackboard (e.g., BB2 in Fig. 4). The icon agent then sends an

OK-event

to its master agent (Step 9 of

Agent-planning).

During the reactive planning stage (which starts at Step 10 of

Agent-planning),

the icon agent may be activated by an

asking-event

to modify the width or height

of its icon (Step 11 of

Agent-planning).

The handler for the

asking-event

makes

a backup of the generated icon. It propagates the constraints pertaining to the

variable specified in the event, e.g., the width of the icon, in order to determine

the required value, modifies the variable accordingly, and activates

Rule2

to gen-

erate a new icon from the width specifications if possible (Step 12). The icon

agent then informs its master agent whether a satisfactory icon was generated

(Step 13).

If the planning procedure is interrupted by a

cancel-request-event

during

the reactive planning stage, the handler of this event is triggered. This handler

recovers the previously generated icon from the backup which was made by the

142 Yi Han and Ingrid Zukerman

handler of the

asking-event.

As discussed in Section 4.3, the handler locks the

blackboard while deleting any events that were sent out to the master agent by

the icon agent. Finally, the handler forces the icon agent to restart its reactive

planning stage from Step 10 of

Agent-planning.

Consequently, any unperformed

actions with respect to the previous

asking-event

are skipped.

7 Presenting Composite Information: Table Agent

A segment container is generated by agents for presenting composite information.

As stated in Section 5.1, an agent decomposes a presentation task into sub-tasks

based upon its discourse structure, and hires server agents to perform these

sub-tasks. Each agent uses its own format to convey the intended information.

Thus, specific methods are used by different agents to decompose their task.

Each segment container has a segment-list which contains the components to be

generated by the server agents. The segment container specifies the format for

the integration of these components. Modality constraints and space constraints

are imposed by the agent which creates the segment container to ensure the

integration of the components. Propagation of modality constraints is performed

during the task decomposition stage in order to obtain modalities capable of

presenting each component (Step 4 of

Agent-Planning).

In contrast, an agent

performs propagation of space constraints during the initial planning stage in

order to obtain requirements from its server agents (Step 8 of

Agent-planning),

and during the reactive planning stage in order to obtain requirements from its

master agent or its server agents (Steps 12 and 15 of

Agent-planning).

A table agent generates a table container~to present composite information

in the format of columns and rows. Figure 12 illustrates a segment container

which specifies the parameters defined by a table agent for presenting the table

in Fig. 2. These parameters are: (1) the width and height of the table (in pixels),

(2) the number of columns and rows, (3) the width of the different columns and

height of the different rows, (4) the type of column and row separator (solid-line,

which is the default, double-line, nil), (5) the alignment of each entry in each

column (left, which is the default, center or right) and row (top, which is default,

center or bottom), (6) the headings for columns and rows, and (7) the content

to be conveyed in each entry (stored in

segment-list).

A table agent determines the integration format of a table and the content

of each component on the basis of (1) the dimensions of the information to be

conveyed, (2) the dimensional focus of each dimension, and (3) the discourse

relations to be conveyed. For the Instantiations that illustrate the Comparison

between the weight of an object on Earth and its weight on the moon (Fig. 5),

the information to be conveyed has two dimensions, namely

object

and

weight.

The dimensional focus of

object

name

and

mass,

and the dimensional focus of

weight

magnitude.

This information can be conveyed either by (a) putting each

Instantiation in a row, or (b) putting each Instantiation in a column. The table

agent in MAGPIE prefers to use format (a), where the attributes to be compared

are displayed in columns, to suit our natural eye movement (Holmes, 1984). For

Using Cooperative Agents to Plan Multimodal Presentations 143

modality: table

position:

(0,0)

width: 316

height:

136

columns: 4

rows:

column-width: (76 44 102 94)

row-height:

(76 60)

column-separator: solid-line

row-separator: solid-line

column-alignment: (center center center center)

row-alignment: (center center)

row-heading:

nil

column-heading:

((object name)

(object mass)

(weight(Earth) magnitude)

(weight(moon) magnitude))

segment-list:

((name (object

Instl))

(mass (object

Instl))

(magnitude ( wezght( ( object

Instl) Earth)))

(magnitude ( weight( ( object

Instl) moon)))

(name (object

Inst2))

(mass (object

Inst2))

(magnitude ( weight( ( object

Inst2) Earth))))

(magnitude ( weight( ( object

Inst2) moon))))

Fig. 12. Sample table container: weight of objects

the discourse plan in Fig. 5, the table agent sets up two rows since there are

two Instantiations in the discourse, and four columns since four elements are

generated from filtering the intended information with the dimensional focus for

each dimension. These elements are: (1) the

name

of an object, (2) its

mass,

(3) the

magnitude

of its weight on Earth, and (4) the

magnitude

of its weight on

the moon. The resulting table is shown in Fig. 2. The table in Fig. 13 presents

the same information using format (b), where the four elements generated from

filtering each Instantiation are arranged in a column. Thus, this table contains

two columns (one for the box, and the other for the computer), and four rows

(one for each element obtained from the dimensional focus). If there are many

attributes in focus for a few Instantiations (e.g., the weight of each object on

Jupiter, Mars, etc.), format (b) is used owing to the relatively small number of

columns that can be displayed horizontally.

A table with many columns/rows illustrates a situation where the presenta-

tion violates the quality requirements of the discourse. Such a presentation is not

acceptable due to the high density of the information being presented (Holmes,

144 Yi Han and Ingrid Zukerman

Fig. 13. Sample multimodal presentation: table in a different format

1984) 3. In this case, the table agent may (1) remove rows (in format (a)) or

columns (in format (b)) which contain non-essential information so long as the

communicative goal is still achieved (Han, 1996; Zukerman and McConachy,

1995); or (2) merge the information presented in several columns (in format (a))

or rows (in format (b)) and select a modality capable of presenting the resul-

ting composite information. For example, a vector may be used to convey the

magnitude and direction of a force.

After the table agent decides how to break down the intended information

into columns and rows, it determines the content of each entry and the headings

for columns and rows (Step 2 of

Agent-planning).

For each column of the table in

Fig. 2, the table agent fills in the column heading with the name of the attribute

in focus and the class name of each item. For example,

(object name)

is used

in the first column, and

(weight(Earth) magnitude)

is used in the third column

(Fig. 12). Row headings are filled with the name of each Instantiation, which

nil

in this example. Next, the table agent extracts the content of each entry

from the values of the attributes in focus for each Instantiation. Finally, the

alignment of each column and each row is set to center, and column-separator

and row-separator are set to solid-line, which is the default value.

3 At this stage, the maximum number of columns and rows in a table in MAGPIE is

a constant. In future, this parameter should be determined from the user's abilities

represented in a user model and the type and complexity of the information.

Using Cooperative Agents to Plan Multimodal Presentations 145

Name Constraint Strength

tmcnl (unify

rnodality( entryl )

modality(entry2))

required

tmcn2 (unify modality( column-headingl )

(text)) required

tmcn3 (unify modality(entryl)

(icon number text)) required

tmcn4 (unify modality(entry2)

(icon number text)) required

Table 1. Modality constraints for a column in a table

~ame

tSCnl

tscn2

tscn3

tscn4

tscn5

tscn6

Constraint Strength

width(column1) = width(entry1)

width (column1) = width (entry2)

width(entry1) _>

width( segmenh ) + margin_minimum

width(entry2) >_ width(segment2) + margin_minimum

width(entry1) < width(segmenh ) + margin_maximum

width(entry2) < width ( segment~ ) + margin_maximum

required

preferred

Table 2. Space constraints for a column in a table

A table agent uses the following rules to impose modality constraints on each

entry (Step 3 of

Agent-Planning):

Ruleml

If format (a) is selected to compare a list of attributes (i.e., putting

each Instantiation in a row), the same modality is used for all the entries in

a column.

Rulem2

If format (b) is selected to compare a list of attributes (i.e., putting

each Instantiation in a column), the same modality is used for all the entries

in a row.

Rulem3

Column headings and row headings must be textual.

Rulem4

Only icon, number and text may be used (at present) for presenting

the content of each entry.

Ruleml

and

Rulem2

are based on the consideration that objects that are

compared with each other should be presented in the same modality.

Rulem3

and

Rulem4

represent restrictions resulting from the implementation of MAGPIE.

Table 1 lists the modality constraints pertaining to the first column of the table

in Fig. 2. We refer to the column heading of this column as

column-heading1,

and to the entries in this column as

entry1

and

entry2.

The segments in these

entries are called

segmentl

and

segment2

respectively. The modality constraints

are specified in terms of a unification operator whose semantics are the same

as the semantics of the unification operator in Unification Grammars (see e.g.

Allen, 1994). In Table 1,

tmcnl

is generated by

Ruleml

since format (a) is used;

tmcn2

is derived from

Rulem3; and tmcn3

and

tmcn4 are

derived from

Rulem4.

Additional constraints are created by the same rules for the other columns of

the table in Fig. 2.

The mechanism discussed in Section 7.1 is then invoked to return suitable

modalities for the content of each entry and to activate server agents (Steps 4-6 of

Agent-planning).

After server agents are created, the table agent poses space con-

146 Yi Han and Ingrid Zukerman

stralnts on the modality-specific presentations generated by these server agents

(Step 7 of

Agent-planning).

Four rules are used to create space constraints:

Rules1

Entries in a column must have the same width.

Rules2

Entries in a row must have the same height.

Rules3

The minimum margin surrounding a segment in an entry must be at

least of a certain size (e.g., 12 pixels), so that the segment is not too big for

its entry.

Rules4

The maximum margin surrounding a segment in an entry should not

exceed a certain threshold (e.g., 42 pixels), so that the segment is not too

small for its entry.

Rules1

and

Rules2

restrict the width and height of each entry, while

Rules3 and

Rules4

restrict the size of the entry segments. Constraints derived from

Rulesl-

Rules3

are required, while constraints derived from

Rules4

are preferred. Table 2

shows the space constraints derived from these rules for the width of the first

column of the table in Fig. 2. Additional constraints similar to

tscnl-tscn6

Table 2 are created for the other columns of the table in Fig. 2.

7.1 Modality Constraint Satisfaction

The modality constraints in Table 1 must be satisfied when the agent generating

the table in Fig. 2 selects modalities for presenting each component of the table

(Steps 4-6 of

Agent-planning).

To this effect, for each modality constraint the

table agent must (1) calculate the alternative values for each variable in the

constraint that satisfy the constraint (Step 4); and (2) select a value from these

alternatives (Steps 5 and 6).

To calculate the alternative values for each variable in a modality constraint,

MAGPIE first obtains the possible domain values for each variable, and then

eliminates the values that do not satisfy the modality constraint. The domain

values of a variable in a modality constraint represent all the modalities capable

of presenting the information in this variable. For example, the domain values of

entry1

are the modalities capable of presenting a box, viz icon or text. These

candidate modalities are currently attached to the input. However, in future they

will be determined from the characteristics of the information being conveyed

and the capabilities of each modality (Arens, Hovy and van Mulken, 1993).

Modality constraints are non-munerical, and an instantiation of the variables

in modality constraints is a list of alternative modalities (Table 1). A unification

algorithm is used to propagate modality constraints (Allen, 1994). It is applied

to the modality constraints and a substitution of their variables, where the initial

substitution of a variable is its domain values. It returns a new substitution of

the variables so that the modality constraints are satisfied. For example,

tmcn3

is satisfied if icon is used in

entry1.

If icon and text are available for

entry2,

the result of the unification of the constraints for these entries is icon.

When we apply the modality selection process to tmcn2 in Table 1 for each

column heading, text is selected in Step 4 of

Agent-Planning as

the modality

Using Cooperative Agents to Plan Multimodal Presentations 147

Fig. 14. Sample multimodal presentation: table for free-fall example

for presenting the column headings, even though there may be other modalities

capable of presenting the information in the headings. The candidate modalities

for presenting the name of an object in the first column of Fig. 2 are icon

and text. Both of these modalities remain as possible candidates after applying

Step 4 of the

Agent-planning

procedure, since they unify with

tmcn3

and

tmcn4.

At present MAGPIE uses numbers only to convey numerical information, and

text to convey units of mass/weight. Hence, number and text remain as the

modalities for presenting the magnitude of mass/weight and its unit respectively

after unification with modality constraints such as those in Table 1.

MAGPIE uses heuristics to select modalities from the alternatives gener-

ated by the modality constraint propagation process (Step 6 in

Agent-planning).

These heuristics are based on a perceiver's preferences or on resource restrictions.

Currently MAGPIE has a very simple user profile which contains a perceiver's

age and literacy level. MAGPIE uses non-textual modalities, such as icons, to

present objects to perceivers with a low level of literacy. Hence, in this example

icon is selected for the entries in the first column.

Communication between agents is required to apply these selection heuristics.

For instance, if there is no icon to present an object in the first column of the table

in Fig. 2, an icon cannot be used to present the other object in this column, since

tmcnl

requires that the same modality be used for

entry1

and

entry2

(Table 1). In

this case the second alternative, i.e., text, is selected. Such a situation takes place

during the generation of the table in Fig. 14 for conveying the terminal velocity

148 Yi Han and Ingrid Zukerman

Fig. 15. Sample multimodal presentation: chart for free-fall example

of objects in free fall. The text paragraph in Fig. 14 states that (1) terminal

velocity results from the upward force caused by the air beneath; (2) it depends

on the mass and surface area of falling objects; (3) the larger the area of an object,

the more air it can trap beneath it; and (4) a parachutist uses a sheet with a

large area to slow the fall from an aircraft. The third statement is illustrated by

means of five Instantiations, each describing an object and its terminal velocity

reached in free fall. These Instantiations are presented in a table which presents

different objects in the first column, and their terminal velocity in the second

column. As discussed above, icon is selected first to present the objects in the

first column, and the

wait-all-responses

strategy is applied to ensure that the

same modality is used for all the segments in this column. MAGPIE does not

have an icon for a stone, an insect or a raindrop, hence the icon agents send a

rejection-event

to the table agent, which brings the

wait-all-responses

strategy

to an end. As a result, the table agent drops icon, and sends a

remove-agent-

event

to each of the icon agents. It then selects the second alternative, viz text,

and creates a text agent for each entry in the first column. This time, all the

agents succeed, and the objects in the first column are conveyed by means of

text (Fig. 14). The chart that conveys the same information appears in Fig. 154 .

If the perceiver has no preferences with respect to presentation modalities,

an agent is created for each alternative modality obtained from the constraint

a The actual colours of the bars in this chart are (from left to right): red, green, blue,

grey and black.

Using Cooperative Agents to Plan Multimodal Presentations 149

propagation process, and the different agents compete for the presentation of

the information. Presentations that violate the space restrictions imposed by the

discourse structure are eliminated, and a heuristic based on time consumption

is applied to select the modality of the final presentation among the remaining

alternatives. For example, since the presentations in Figs. 14 and 15 satisfy

the space restrictions, the presentation that is completed first, i.e., the chart, is

displayed. If, however, none of the presentations can satisfy these restrictions,

the last alternative, viz text, will be used to present the Instantiations.

7.2 Space Constraint

Satisfaction

Space constraints are numerical and the values which satisfy them are nondeter-

ministic (Table 2). For instance, when

width(segmentl)

is assigned a value (as

a result of a presentation generated by the icon agent for

segment1),

two new

constraints result from propagating this value:

width( columni ) >_ width(segment1) + raargin_min,

and

width(column1) <_ width( segmentl )

margin_max.

In this manner, the icon agent presenting

segraentl

can convey to the table agent

its expectation of width(column1). The table agent in turn can determine whether

its assignment of

width(column1)

or the value of

width(segment1)

assigned by the

icon agent are satisfactory.

As discussed in Section 3, constraints are distributed in the plan hierarchy.

MAGPIE uses

channels

for the propagation of space constraints from one level

in the plan hierarchy to the next. A channel consists of a set of constraints

(usually one or two). It is a path for propagating the values of variables in an

agent's plan to the variables of another agent's plan. Among the constraints in

Table 2,

tscnl

and

tscn3

form a channel since the right-hand side of

tscnl

con-

tains the variable on the left-hand side of

tscn3.

Other channels can be formed

from

tscnl

and

tscn5, tscn2

and

tscn4,

and

tscn2

and

tscn 6.

Hence, four value

ranges for

width(column1)

can be obtained from the propagation of constraints

through these channels (Han and Zukerman, 1996b). A value from the inter-

section of these four ranges satisfies

tscnl

tscn6

and therefore can be as-

signed to

width(column1)

by the table agent (Step 8 of

Agent-planning).

Since

the agents presenting

segmenh

and

segment2

are independent processes, they

generate constraints which affect simultaneously width(column1). MAGPIE does

not allow these agents to write directly to

width(column1)

when they advise the

table agent of the value of

width(columnl)

in order to prevent this value from

being overwritten in unpredictable ways. Value binding is used when propagat-

ing space constraints through channels. Consequently, the two icon agents can

advise the table agent of

width(column1)

independently.

As stated above, agents satisfy required space constraints during the initial

planning stage (Step 8 of

Agent-Planning)

and when they receive a request for

the modification of a variable during the reactive planning stage (Steps 11-13). If

time permits, they repair the violation of preferred constraints while maintain-

ing the satisfaction of the required constraints (Steps 14-16). The satisfaction

150 Yi Han and Ingrid Zukerman

of required constraints and preferred constraints is achieved through coopera-

tion between agents. To illustrate the agent cooperation process for satisfying

required constraints, consider a situation where the table in Fig. 2 has addi-

tional columns, and the two icons generated initially for

column1

are such that

segment1

is much bigger than

segmenb2.

In addition, the presentation planning

agent has posted constraints which ensure that the table can fit into the display

window (Han, 1996). These constraints are propagated through channels formed

between the table agent and the presentation planning agent. The constraint

that restricts the table width to be less than the window width prevents the

expansion of

column1,

yielding an empty intersection of the ranges which spec-

ify the width of

column1.

Since this constraint is posted by the master of the

table agent, it is given priority over constraints posted by its server agents. To

satisfy this constraint, the table agent sets

width(column1)

to a value that fits

segment2

(Step 8 of

Agent-planning).

However, this causes the violation of

tscn3,

therefore the table agent asks the icon agent to reduce the width of

segment1

fit in the column. When the icon agent receives this message in its own process

(Step 11 of

Agent-Planning),

it propagates

width(column1)

through the channels

formed by

tscnl-tscn3

and

tscnl-tscn5

(Table 2), and calculates the new value

width(segment1)

that satisfies the constraints resulting from the propagation

(Step 12). If the icon agent can retrieve a smaller icon that fits the column width,

then the constraints pertaining to

width(segment1)

are satisfied (Step 12), and

the icon agent reports this fact to the table agent (Step 13). In contrast, if the

current icon size is the only available size for

segment1,

failure is reported to

the table agent, and the table agent tries to reduce the width of other columns.

The process of asking server agents to modify their presentations is repeated

until the space constraints pertaining to the table are satisfied, or until the table

agent determines that these constraints cannot be satisfied. When the width and

height of the table satisfy these constraints, the table agent sends an

OK-event

to the presentation planning agent to report the completion of the table (Step 9

Agent-planning).

Otherwise, it sends a

rejection-event.

If time permits, during the reactive planning stage the table agent tries to

repair preferred constraints which were violated during the initial planning stage

(Steps 14-16 of

Agent-planning).

To this effect, it asks its server agents to modify

their presentations so that a non-empty intersection is produced from propagat-

ing the constraints pertaining to their presentations. For example, if one of the

generated icons is too small for its entry, the table agent sends an

asking-event

to the agent which generated this icon, requesting this agent to enlarge the icon.

If the icon agent can comply without violating any of the required constraints,

then the improved presentation is retained. The above discussed procedure for

the satisfaction of required constraints is applied to implement this process.

In general, arranging an unordered set of objects into a layout format that

occupies a minimum space is strongly NP-complete. Even with constraints such

as those described in Table 2, it is expensive to find all the means of modifying

entry segments for the satisfaction of preferred constraints. Thus, time restric-

tions are used to guide the constraint satisfaction process in MAGPIE. If time