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

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

Using Cooperative Agents to Plan Multimodal Presentations 151

is running out, the best presentation generated so far (which satisfies all the re-

quired constraints and the highest number of preferred constraints) is displayed.

If a presentation that satisfies M1 the required constraints cannot be generated

in time, an alternative modality is selected (Section 7.1). Text presentations can

normally be generated faster than visual presentations. Hence, in the worst case,

the intended information is presented in text.

8 Presenting Composite Information: Chart Agent

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

each component based upon the same factors as those considered by a table

agent (Step 2 of

Agent-planning).

For the two dimensions of the Instantiations

that illustrate the weight of objects, namely

object

and

weight

(Fig. 5), the

discourse compares the difference between the weight of an object on Earth and

its weight on the moon. The relevant information is extracted by filtering the

Instantiations with the dimensional focus. The communicative goal may then

be achieved by presenting the same attribute of different Instantiations, e.g.,

the weight of each instantiated object on Earth, either (a) in one type of bar

(Fig. 3), or (b) in different types of bars (Fig. 16). The considerations applied

for selecting a particular presentation format are described in (Han, 1996).

The chart container for generating the chart in Fig. 3 appears in Fig. 17. The

chart agent sets groups to 2 since there are two Instantiations, one for the box

and another for the computer. For the two attributes in focus for the dimension

object,

viz

name

and

mass,

the Jabels parameter is filled with the values of these

attributes obtained from each Instantiation. There are two elements in each

group, hence two types of bars are required. The weight of each object on Earth

is presented in red bars, and the weight of each object on the moon is presented

in green bars. This is indicated in the legend of the chart in Fig. effig:cht-tx2eg.

The legend of a chart is treated as a small table without column headings, row

headings or separators. Hence, the chart agent creates a table container of two

columns and two rows. The first column contains a sample of each type of bar,

and the second column contains the headings.

To extract the data for the bars in the chart, the chart agent filters the

Instantiations with the dimensional focus of

weight,

viz the magnitude of weight.

Hence, the first Instantiation produces the values 19.6 and 3.2, and the second

Instantiation produces the values 98 and 16. These values are stored in segment-

list in the order in which they were extracted. The unit is set to the unit of weight,

viz

Weight(Newton).

Two constants are specified in the chart container, namely

diff and mini: dif[ represents the smallest visible difference between bars, and

mini specifies the minimum width of each bar so that bars will not be reduced to

thick lines. The height and width specify the size of a chart, which is calculated

from the values being compared and the size of each component.

Once a chart agent determines the content of each component, it poses con-

straints on the modalities to be used for presenting the components (Step 3 of

Agent-planning).

Units of measurement must be presented in textual modalities,

152 Yi Hail and Ingrid Zukerman

Fig. 16. Sample multimodal presentation: chart in a different format

and at this stage, labels and legend headings are restricted to textual modalities.

In future, chart agents will be extended to allow icons for legend headings and

labels.

Next, in Steps 4-6 of the Agent-planning procedure, two text agents and

two number agents are activated to present the labels ("box(2kg)" and "com-

puter(10kg)"), two additional text agents are activated to present the legend

headings ("weight on Earth" and "weight on the moon"), and another text

agent is activated to convey the unit of weight. The wait-all-responses strategy

is used to process the responses from these agents since they present necessary

components of the chart.

To ensure the integration of the chart components, space constraints are

imposed in Step 7 of the Agent-planning procedure (Table 3). MAGPIE requires

a chart to be big enough to attract a perceiver's attention (Holmes, 1984), hence

cscnl and cscn2 are created to restrict the minimum width and height of the

chart. The maximum size of the chart is restricted by the size of its components.

These restrictions are reflected in constraints cscn3-cscn 7.

For the data set v in segment-list, {vl,v2,va,v4} are the values of v in as-

cending order. Constraint cscn3 is imposed on the height of the chart to ensure

that the smallest difference between bars is visible on the screen. The height

of the first label on the X axis is added since the same font is used by all the

agents presenting the labels; and diff is added since the chart must display at

least the top of the smallest bar. The minimum difference between two values of

Using Cooperative Agents to Plan Multimodal Presentations 153

modality:

chart

position: (0,0)

width: 450

height: 250

groups: 2

mini: 15

diff: 5

unit:

Weight(Newton)

labels:

(((name (object

Instl))

(mass (object

Instl)))

((name (object

Inst2))

(mass (object

Inst2))))

legend:

((weight

(Earth))

(weight

(moon)))

segment-list: (19.6 3.2 98 16)

Fig. 17. Sample chart container: weight of objects

Name

C8C77,1

c8cn2

C8Cn3

C8C~4

CSC-~ 5

escn6

c8cn7

width(chart)

height(chart)

width(chart)

width(legend)

Constraint Strength

>_ Threshold

> diff x a ~-~ -I- diff

-- min =l {[Vi+ l--villvi+ l >vl }

-I- height(label1) -I- height(unit)

> 4

x mini +

width(legend)

+ width(v4) +

offset

_> groups x max {

width(labeh), width(labele) }

+ width(legend) +

width(v4) -I-

offset

_> mini -t- 2 •

margin_rain

-F max { width(heading1), width(heading2) }

<_ Threshold x width(chart)

required

preferred

Table 3. Space constraints on a chart

v is considered only when this difference is greater than zero (it is possible that

two bars in a chart are of the same height).

The width of a chart is restricted by either the width of the bars or the length

of the labels. Constraint

cscn4

in Table 3 pertains to the width of the bars, where

mini is the minimum width of each bar, and 4 is the number of bars in the chart.

The value of width(va) is added to account for the space required to label the

scale on the Y axis, and the

offset

is added to account for the markers on the

Y axis. Constraint

cscn5

pertains to the length of the labels. All the groups

contain the same number of bars, and hence have the same width. This width is

constrained by the longest label on the X axis, since one of the groups must be

able to accommodate this label. Finally, the width of the legend is constrained by

cscn6 and csen7,

where

cscn6

is based on the width of the legend's components,

while

cscn7

is based on the width of the chart. For each type of bar, a sample

block is generated in the first column of the legend using the minimum width

allowed for bars, hence mini is added to

cscn6;

each type of bar is described

by a heading in the second column of the legend, thus the width of the longest

heading is added;

margin_min

is the minimum margin required in each column

154 Yi Han and Ingrid Zukerman

of the legend. Constraint

cscn7

stipulates that the width of the legend should

not exceed a certain proportion (Threshold) of the width of the entire chart.

During the initial planning stage (Steps 8-9 of

Agent-planning),

the chart

agent propagates

cscnl-cscn7

in order to determine the width and height of the

chart. If the resulting width and height satisfy the constraints imposed by the

presentation planning agent, the chart agent informs the presentation planning

agent of the successful completion of the chart presentation process. Otherwise,

a failure is reported.

During the reactive planning stage (Steps 10-16 of

Agent-planning),

the chart

agent may be activated by an event demanding a modification of its plan vari-

ables or an event demanding the satisfaction of additional preferred constraints.

For example, in the second case, the chart agent determines whether the width

of the legend is too wide in proportion to the size of the chart. If so, the chart

agent asks the text agents presenting the headings in the legend to reduce the

font of the text (Step 16).

9 Conclusion

We have described a multi-agent planning mechanism for the generation of mul-

timodal presentations which is based on a hierarchical blackboard architecture.

Our mechanism combines blackboard events with constraint propagation to sup-

port communication between agents. The hierarchical architecture enables our

mechanism to take into account the overall structure of the discourse; while

constraint propagation supports the transfer of plan constraints from one level

of the presentation plan hierarchy to the next, and enables our mechanism to

take into consideration the consumption of resources. Our approach has been

used for generating multimodal presentations for several discourse plans, which

require the activation of up to 32 agents. Although a large number of agents

slows down the presentation generation process, particularly when additional

preferred constraints are satisfied, our results still demonstrate the flexibility of

our approach.

The system presented in this paper may be enhanced along several dimen-

sions. The existing agents of MAGPIE may be extended to offer more functions

and format varieties. For example, chart agents should be able to relocate the

legend and labels of a chart to save screen space, or allow icons to be used for

the legend and the labels. In addition, table agents should be able to use modal-

ities such as vectors to present composite information, and thereby reduce the

number of columns required for the attributes in focus. Finally, MAGPIE may

be extended to provide additional modalities, such as line charts and images.

This requires the development of new agents and algorithms in order to handle

non-linear constraints that restrict the position of different components in an

image using trigonometric relations.

Future research on the constraint satisfaction mechanism of MAGPIE per-

tains to two interesting issues. The first issue involves using constraints to repre-

sent time restrictions on multimodal presentations, and developing a mechanism

Using Cooperative Agents to Plan Multimodal Presentations 155

for the propagation of time constraints. This would allow the system to manipu-

late the time required to generate a discourse component, e.g., the time available

to the table agent or the chart agent to improve a presentation. To do this, the

constraint propagation mechanism must be able to propagate time intervals, and

each agent must provide estimations of the time required for the generation of

a component. Thus, on one hand, these estimations could be propagated from

the lower level to the higher level of the presentation plan hierarchy, so that a

master agent knows the minimum time required for generating each component.

On the other hand, time restrictions could be propagated from the higher level

to the lower level, so that an agent can ensure the generation of a component in

the required time.

The second issue concerns the satisfaction of distributed constraints. In MAG-

PIE, these constraints are divided into several groups, and the satisfaction of each

group of constraints is handled by a group of agents. Thus, MAGPIE attempts

to achieve the global satisfaction of all constraints through the local satisfaction

of each group of constraints. However, the latter does not always lead to the

former, since agents may get stuck in a local optimum. Although the communi-

cation between agents increases the likelihood of reaching the global satisfaction

of all the constraints, more efficient algorithms for the satisfaction of distributed

constraints are required.

Acknowledgments

This research was supported in part by a research grant from the Faculty of

Computing and Information Technology and by a Small ARC grant. The authors

would like to thank Tun Heng Chiang for his work on the implementation of the

display modules, and Damian Conway for his advice regarding the improvement

of several tables and figures.

References

Allen, J.F. (1983) Maintaining Knowledge About Temporal Intervals.

Communication

of the ACM,

26(11), 832-843.

Allen, J.F. (1994)

Natural Language Understanding

Redwood City, CA: Benjamin-

Cummings.

Andr@, E., Finkler, W., Graf, W., Rist, T., Schauder, A., and Wahlster, W. (1993)

WIP:

The Automatic Synthesis of Multimodal Presentations.

Intelligent Multime-

dia Interfaces,

Maybury, M.T., (ed.) AAAI Press, 75-93.

Andr@, E., Miiller, J., and Rist, T. (1996) The PPP Persona: A Multipurpose Animated

Presentation Agent. To appear in

Proc. of Advanced Visual Interfaces,

ACM Press.

Arens, Y. and Hovy, E. (1994) The Design of a Model-Based Multimedia Interaction

Manager.

Artificial Intelligence Review,

8(3), 95-188.

Arens, Y., Hovy, E., and van Mulken, S. (1993) Structure and Rules in Automated

Multimedia Presentation Planning.

Proc. IJCAI-93,

1253-1259.

Arens, Y., Hovy, E., and Vossers, M. (1993) On the Knowledge Underlying Multime-

dia Presentations.

Intelligent Multimedia Interfaces,

Maybury, M.T., (ed.), AAAI

Press, 280-305.

156 Yi Han and Ingrid Zukerman

Borning, A., Freeman-Benson, B., and Wilson, M. (1992) Constraint Hierarchies. Lisp

and Symbolic Computation 5(3), p. 223-270.

Bourdot, P., Krus, M., and Gherbi, R. (1995) Management of Non-Standard Devices

for Multimodal User Interfaces under UNIX/Xll. In: H. Bunt, R.J. Beun and T.

Borghuis (eds.) Proc. CMC/95, Intern. Conf. on Cooperative Multimodal Commu-

nication, Eindhoven, The Netherlands, 49-61.

Bunt, H., Ahn, R., Beun, R.J., Borghuis, T., and van Overveld, K. (1995) Cooper-

ative Multimodal Communication in the DenK Project. In: H. Bunt, R.J. Beun

and T. Borghuis (eds.) Proc. CMC/95, Intern. Conf. on Cooperative Multimodal

Communication, Eindhoven, The Netherlands, 79-102.

Cheyer, A. and Julia, L. (1995) Multimodal Maps: An Agent-based Approach. In: H.

Bunt, R.J. Beun and T. Borghuis (eds.) Proc. CMC/95, Intern. Conf. on Cooper-

ative Multimodal Communication, Eindhoven, The Netherlands, 103-113.

Engelmore, R.S. and Morgan, A.J. (1988) Blackboard Systems New York: Addison-

Wesley.

Feiner, S.K. and McKeown, K.R. (1990) Coordinating Text and Graphics in Explana-

tion Generation. Proc. AAAI-90, Boston, MA, 442-449.

Feiner, S.K., Litman, D.J., McKeown, K.R., and Passonneau, R.J. (1993) Towards Co-

ordinated Temporal Multimedia Presentations. Intelligent Multimedia Interfaces,

Maybury, M.T., (ed.), AAAI Press, 139-147.

Finin, T., Fritzson, R., McKay, D., and McEntire, R. (1994) KQML as an Agent Com-

munication Language. Proc. CIKM'94, Third Intern. Con]. on Information and

Knowledge Management, New York, ACM Press.

Ghedira, K. (1994) Dynamic Partial Constraint Satisfaction by a Multi-Agent-

Simulated Annealing Approach. ECAI-94 Workshop on Constraint Satisfaction

Issues Raised by Practical Applications, Thomas Schiex (ed.), Amsterdam.

Graf, W. (1992) Constraint-based Graphical Layout of Multimodal Presentations. Proc.

A VI'92, Intern. Workshop on Advanced Visual Interfaces, Rome, 365-385.

Han, Y. (1996) Cooperative Agents for Multimodal Presentation Planning. Doctoral

Dissertation, Dept. of Computer Science, Monash University, Victoria, Australia

(in prep.).

Han, Y. and Zukerman, I. (1995) A Cooperative Approach for Multimodal Presentation

Planning. In: H. Bunt, R.J. Beun and T. Borghuis (eds.) Proc. CMC/95, Intern.

Conf. on Cooperative Multimodal Communication, Eindhoven, The Netherlands,

145-159.

Han, Y. and Zukerman, I. (1996a) Constraint Propagation in a Cooperative Ap-

proach for Multimodal Presentation Planning. In W. Wahlster (ed.) Proc. ECAI-96,

Twelfth European Conference on Artificial Intelligence Budapest, New York: John

Wiley, 256-260.

Han, Y. and Zukerman, I. (1996b) A Mechanism for Multimodal Presentation Planning

Based on Agent Cooperation and Negotiation. Technical Report No. 96/257, Dept.

of Computer Science, Monash University, revised July 1996.

Holmes, N. (1984) Designer's Guide to Creating Charts ~ Diagrams New York: Watson-

Guptill.

Maybury, M. (1993) Planning Multimedia Explanations Using Communicative Acts.

In M. Maybury (ed.) Intelligent Multimedia Interfaces, AAAI Press, 59-74.

Mackinlay, J. (1986) Automating the Design of Graphical Presentation of Relational

Information. ACM Transaction on Graphics, 5(2), 110-141.

Minton, S. Johnston, M., Philips, A., and Laird, P. (1990) Solving Large-Scale Con-

straint Satisfaction and Scheduling Problems Using a Heuristic Repair Method.

Using Cooperative Agents to Plan Multimodal Presentations 157

Proc. AAAI-90, Eighth National Conference on Artificial Intelligence,

Boston, MA,

17-24.

Roth, S. and Mattis, J. (1991) Automating the Presentation of Information.

Proc.

IEEE Conference on AI Applications,

Miami Beach, FL, 90-97.

Wahlster, W., Andre, E., Finkler, W., Profitlich, H., and Rist, T. (1993) Plan-based

Integration of Natural Language and Graphics Generation.

Artificial Intelligence

63(1-2), 387-427.

Zukerman, I. and MeConachy, R. (1993) Generating Concise Discourse that Addresses

a User's Inferences.

Proc. IJCAI-9S, Thirteenth Intern. Joint Conf. on Artificial

Intelligence,

ChambeIT, France, 1202-1207.

Zukerman, I. and MeConachy, R. (1995) Generating Discourse across Several User

Models: Maximizing Belief while Avoiding Boredom and OverLoad.

Proc. IJCAI-95

Fifteenth Intern. Joint Conf. on Artificial Intelligence,

Montreal, Canada, 1251-

1257.

Developing Multimodal Interfaces:

A Theoretical Framework and Guided

Propagation Networks

J. C. Martin, R. Veldman, and D. B@roule

LIMSI-CNRS, B. P. 133, 9143 Orsay Cedex, France

martin@limsi, fr

Abstract. In this paper we propose an approach for the design of re-

lated theoretical and software tools for developing multimodal interfaces.

A theoretical framework is described based on the notion of types of coop-

eration between modalities It forms the basis of a specification language

that we used for developing multimodal interfaces to three test applica-

tions. This specification language is interpreted by a multimodal module

made of Guided Propagation Networks.

1 Introduction

Human-computer interfaces face several requirements such as the need to be fast

and robust to recognition errors, unexpected events and mistakes made by the

user. The goal of our work is to study how multimodality can bring solutions to

these problems and to provide tools for the development of multimodal interfaces.

As a matter of fact, the development of a multimodal interface addresses

several issues (see Maybury, 1991): content selection ('what to say'), modality

allocation ('in which modality to say it'), modality realization ('how to say it

in that modality') and modality combination. Our work deals with the 'modal-

ity combination' issue. A multimodal interface developer has to know how to

combine modalities and why this combination may improve the interaction. Al-

though several multimodal interfaces have already been developed (see Bunt et

al. (1995), Lee, 1995), there is still a lack of coherent theoretical and software

tools.

In the first part of this paper, we propose a theoretical framework for analyz-

ing modality combinations. We discuss existing frameworks in Human-Computer

Interaction (HCI) and explain why our framework might be useful. The second

part details two software tools based on the framework: a specification language

and a multimodal module using Guided Propagation Networks. Illustrative ex-

amples are taken from a test application that we have developed.

2 A Framework for Analyzing Modality Combinations

The space of interfaces can be viewed from different standpoints, and several

frameworks have already been proposed (see Bos, 1993 for a review). Such frame-

works can be used for categorizing a particular interface, comparing different

Developing Multimodal Interfaces 159

interfaces, inspiring designers in creating new interfaces or tools, arriving at a

consensus about HCI terminology or finally for evaluating interfaces. In this

section, we present some of these frameworks and explain why we believe that

a framework devoted to multimodality is needed. After this, we describe a new

framework and show how several multimodal interfaces and experimental results

are represented within this framework.

2.1 Existing Frameworks

The framework described by Hutchins et al. (1986) considers whether the user

has the feeling to converse with an intermediary performing the task. Two di-

mensions are proposed: 'engagement' and 'distance'. The 'engagement' dimen-

sion can take two values: 'conversation' (the user has the feeling that there is an

intermediary performing the task) and 'model world' (the user has the feeling

that he can manipulate artifacts directly). The 'distance' dimension can take two

values ('small' or 'large') depending on the amount of cognitive effort it takes to

manipulate and evaluate the system. The combination of these two dimensions

produces four types of systems (see Table 1).

Table

1. Types of interactive systems

Engagement Distance Type of

system

conversation small high-level language

conversation large low-level language

model world small direct manipulation

model world large low-level world

This space does not take into account the possible use of several devices or

media of interaction. According to the semantic analysis of the design space of

input devices given by Mackinlay et al. (1990), input devices are 'transducers of

any combination of linear and rotary, absolute or relative, position and force, in

any of the six spatial degrees of freedom'. Such input devices can be formalized

and composed to describe more complex devices. The description of a mouse in

such a framework is given in Fig. 1.

Instead of focusing on devices, the classification of Frohlich (1991) links modes

(language or action), channels (audio, visual, haptic/kinesthetic), media (speech,

text, gesture, sound, graphics, motion) and styles (programming language, com-

mand language, menu selection...). The combination of one mode, one channel

and one medium enables a limited set of interaction styles. As an example, the

combination of the language mode, the audio channel and the speech medium

enables the following styles: programming language, command language, natural

language, field filling and menu selection. Although this classification considers

several media, it does not focus on the combination of these media.

160 J, C. Martin, R. Veldman, and D. B4roule

o =

Lln~ar

Yl z

O J--O"

Rotary

rx ~ rY rz

...... 1 ...... 1 ...... i1 ..... 1 ...... 1 ......

Measure

Fig. 1. Representation of a mouse with three buttons in the 'semantic analysis of input

devices' proposed by Mackinlay et al. (1990). A mouse with three buttons is depicted

as a circle on X movement, a circle on Y movement and a circle containing the number

3 on Z positioning. It means that a mouse is a layout combination (dotted line) of four

devices: three simple buttons and one device that is itself the merge composite (bold

horizontal line) of two elementary devices sensing changes in X and Y. The placement of

the X and Y circles to the right of their column indicates nearly continuous resolution

(Measure = Inf). The location of the '3' button circle to the left of the Z column

indicates control with only two states. (Modified from Mackiniay et al. 1990.)

Nigay and Coutaz (1993) describe one of the few frameworks dedicated to

multimodality. It is composed of two dimensions. The 'fusion' dimension consid-

ers whether or not the events detected on several modalities have to be merged.

Thus, this dimension can take two values: 'combination' or 'independence'. The

'use of modality' dimension can also take two values: 'sequential' or 'parallel',

depending on whether the modalities are active at the same time or not. Com-

bining these dimensions, four types of multimodality appear, shown in Table 2.

Table

2. Types of multimodality

Fusion Use of modality Type of multimodality

combination sequential alternate

combination parallel synergistic

independence sequential exclusive

independence parallel concurrent

This framework is focusing on the use of temporal criteria (coincidence or

sequence) to decide whether or not to merge multimodal pieces of information.

It aims at classifying systems more than helping HCI designers to make a ap-

propriate use of multimodality.