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

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

Using Cooperative Agents to Plan Multimodal Presentations 131

staying in the event queue). Announcements are messages broadcast by a master

agent to all the agents in its group. The broadcasting mechanism is the same as

that used for forwarding urgent messages.

A message carried by a normal event may be either a request or a response to

a request. A request from one agent demands a modification of the plan generated

by another agent and specifies the type of this modification, e.g., enlargement or

reduction of a display. A response from this other agent indicates whether it is

able to comply with the request. MAGPIE uses constraints to describe how the

variables of one agent's plan are related to the variables of another agent's plan.

Hence, after receiving a request, MAGPIE's agents use constraint propagation

to obtain the requirements on their variables from the values of other agents'

variables.

When an agent picks up a normal event from an event queue, its event

handlers determine its reaction to the event, e.g., whether constraint propagation

is necessary. An agent is able to send different requests to different agents and

check their response with respect to each request. For instance, if the table

agent who generated the table in Fig. 2 wishes to ask an icon agent to reduce

the width of the icon it generated, the table agent will generate an asking-event

which contains this request (Fig. 6). When the icon agent picks up this event,

its event handler will obtain the expectation on the icon's width by propagating

the constraints pertaining to the width of the icon. The handler will then try

to reduce the icon to fit the expectation. If this modification fails due to the

absence

smaller icons, the icon agent will send a rejection-event to the table

agent on the same request. Otherwise, it will send an OK-event. The table agent's

event handler for the OK-event returns the process name of the icon agent, while

its event handler for the rejection-event returns nil. These returned values are

used in subsequent actions performed by the table agent during the presentation

planning process (Section 4.2).

ASKING-EVENT I

sender:

table agent

receiver:

icon agent

message:

reduce width of icon

/ q

REJECTION-EVEN__T

1 OK-EVENT I

sender:

icon agent

]

sender:

icon agent

receiver:

table agent

receiver:

table agent

message:

reduce width of icon

message:

reduce width of icon

Fig. 6. Events related to a request

Announcements and urgent events carry messages which require an agent's

immediate attention. They interrupt the process being carried out by an agent,

and force the agent to handle these events. An example of an announcement

is time-up, which indicates that a period of real time has elapsed. A time-up-

132 Yi Han and Ingrid Zukerman

announcement is generated by an alarm process which is set up by the system for

a particular amount of time at the beginning of the presentation planning pro-

cess. When a time-up-announcement is sent, all agents stop planning to handle

this announcement, which requires them to display the best presentation plan

generated so far.

MAGPIE has two types of urgent events: remove-agent-event and cancel-

request-event. A remove-agent-event indicates that a master agent is no longer

interested in the display being generated by a server agent, and that the server

agent should abort its presentation planning process together with that of its

own server agents (if any). A cancel-request-event is a message sent from a master

agent to a server agent in order to withdraw a previous request and reinstate the

result of the previous planning process. These two types of events are described

in more detail in Section 4.3.

Each agent must have an event handler for each type of event it may receive.

An event handler for a particular type of event may be defined for the agent-

base, which is the super-class of all agent classes. In this case, all agents inherit

the same event handler from their super-class, and they all react to this type

of event in the same way. If an agent is to react to an event in a particular

way, an event handler is defined for this agent. This event handler overrides the

event handler defined for the agent-base. For example, the event handler for

the time-up-announcement defined for the agent-base causes an agent to stop

planning when it receives a time-up-announcement, and kills this agent. However,

a different event handler is defined for the presentation planning agent, so that it

starts displaying the presentation plan upon receiving a time-up-announcement.

All agents share the same event handler for the OK-event, the rejection-event

and the remove-agent-event, but they have their own handlers for the asking-

event and the cancel-request-event in order to implement individual functions in

reaction to these two types of events.

4.2 Communication Primitives

The system provides communication primitives for each type of event. Agents call

these primitives to communicate with each other via different protocols. Normal

events are created for sending requests and receiving responses to requests. Thus,

the communication between a pair of agents via normal events is two-way; both

the sender agent and the receiver agent must be specified in a normal event. A

pair of communication primitives, make-normal-event and get-normal-event, are

provided for an agent to create a normal event and retrieve a response event

respectively.

- Make-normal-event stores a normal event in the event queue of a par-

ticular blackboard according to the master-server relationship between the

sender and the receiver. If the sender is the master agent of the receiver,

this event is stored in the local blackboard owned by the sender agent, oth-

erwise it is stored in the local blackboard owned by the receiver agent. For

example, if the table agent in Fig. 4 wants to send a message to the icon

Using Cooperative Agents to Plan Multimodal Presentations 133

agent in its group, the normal event that carries this message is kept in BB2.

In contrast, if the table agent wants to send a message to the presentation

planning agent, the event is kept in BB1. Direct message exchanges between

two server agents are not allowed in MAGPIE so that the master agent can

retain control of the integration of presentations generated by different server

agents.

Get-normal-event returns a normal event sent to an agent. An agent

may receive messages from both its master agent and its server agents. The

get-normal-event primitive implements a policy whereby messages from an

agent's master agent have a higher priority than messages from its server

agents. This is performed by checking the blackboard owned by the master

agent before checking the blackboard owned by the agent itself. If no normal

event is detected while an agent is waiting for responses in order to proceed

with its process, the agent continues to wait without running its process.

Two planning strategies are implemented on top of these primitives, wait-

all-responses and wait-any-response.

Wait-all-responses - This strategy is used by an agent if its planning pro-

cess cannot proceed unless all the requests sent out by this agent are satisfied.

This strategy is implemented by calling get-normal-event and activating an

event handler to process an event detected by get-normal-event. When this

event has been processed, the agent waits for the next normal event. This

process terminates when the agent receives a rejection-event response to one

of its requests or an OK-event response to all of its requests. In the first case

this strategy returns nil, and in the second case t.

The chart agent in Fig. 4 applies this strategy with respect to a list of

requests where it asks text agents to generate the headings in the legend,

the unit of weight and the textual part of the labels, and number agents

to generate numbers 2. A failure of any request in this list results in nil

being returned by this strategy. In this case, a rejection-event is sent to the

presentation planning agent to report a failure. Otherwise, the chart agent

proceeds with its planning process.

Wait-any-response - This strategy is used if an agent requires one of its

requests to be satisfied in order to carry on with its planning process. The

implementation of this strategy is similar to that of wait-all-responses. How-

ever, this process terminates when the agent receives an OK-event response

to any of its requests or a rejection-event response to all of its requests. The

process name of the sender of the OK-event is returned in the former case,

and nil is returned in the latter case.

The presentation planning agent applies this strategy with respect to a re-

quest for the presentation of the Instantiations in Fig. 5. An OK-event from

either the table agent or the chart agent results in the termination of this

strategy. The returned value identifies the successful agent.

2 The displays presenting the magnitude and unit of mass/weight of an object are

integrated into a single entry in the final presentation (Hail, 1996).

134 Yi Han and Ingrid Zukerman

Urgent events and announcements have a higher priority than normal events.

Communication via urgent events and announcements is one-way, since an agent

sends an urgent event or an announcement to another agent or a group of agents

without waiting for feedback. A primitive called

make-urgent-event

is provided

for an agent to create an urgent event. This primitive forwards the urgent event

to its receiver, selects an event handler for the receiver according to the event

type (e.g.,

remove-agent-event),

and activates this event handler prior to the

receiving agent's normal activation when this agent is scheduled to be run. As a

result, the receiving agent is forced to interrupt its normal process and handle

the received event. Similarly, a primitive called

make-announcement

is provided

for a master agent to make an announcement to its server agents. An urgent

event must specify a receiver, but an announcement does not, as it is forwarded

to all the server agents in the master agent's group.

4.3 System Concurrency

Agents work concurrently in our system. They may work on one partial plan, like

the table agent and its server agents, or on competing plans, like the table agent

and the chart agent (Fig. 4). As a result of concurrency the system must handle

blackboard access by different agents, unexpected termination of an agent, and

cancellation of requests.

Fig. 7. Example of message passing

- Blackboard Access

- Since a group of agents share the information on a

local blackboard, more than one agent may try to write on the blackboard

at the same time. To solve this problem, the system provides a lock for each

blackboard. An agent must acquire the lock before it writes on a blackboard,

and it releases the lock when it has finished writing. If a blackboard is locked

when an agent is trying to write on it, the agent must wait until the lock is

released.

Unexpected Termination - An agent may be terminated by its master

agent before it has completed its planning process. For example, this hap-

pens when another agent completes a competing presentation plan before

the agent in question. When an agent is terminated, the system recursively

terminates all the server agents created by this agent, and clears any mes-

sages from this agent to its master agent. Figure 7 illustrates the message

Using Cooperative Agents to Plan Multimodal Presentations 135

ASKING-EVENT

sender:

receiver: a2

message:

present

Instantiations

ASKING-EVENT e3

sender:

receiver:

message:

need more screen space

REMOVE-AGENT-EVENT e5

sender:

receiver:

ASKING-EVENT

sender:

receiver:

message:

present

Instantiations

OK-EVENT e4

sender:

receiver:

message:

present

Instantiations

Fig. 8. Events causing termination

passing sequence in such a situation, where al is the presentation planning

agent, a2 is the chart agent, and a3 is the table agent. The events appear in

Fig. 8. The presentation planning agent uses the

wait-any-response

planning

strategy when asking the chart agent and the table agent to present two In-

stantiations (events el and e2 respectively). The table agent replies with an

OK-event

(e4), while the chart agent sends a request for more screen space

(event e3). However, because the

OK-event

from the table agent brings

wait-

any-response

to an end, al decides to display the information by means of

a table (Fig. 2), and to terminate the chart agent. The termination of the

chart agent is performed by means of a

remove-agent-event

(e5), which is

an urgent event with an empty message. This event interrupts the planning

process of the chart agent. The event handler of the

remove-agent-event

for

the chart agent then clears the messages sent from the chart agent to its

master agent, and sends a

remove-agent-event

to each server agent before it

terminates itself.

Request Cancellation - A request sent to an agent may be canceled before

the agent completes the process that addresses this request. In order to

handle a cancellation, the agent needs to recover the plan that was current

before this request, and clean up all the messages it sent out while processing

this request. For instance, consider a situation where the table agent needs

to enlarge a table of two rows and two columns which contains an icon in

each entry of the first column and text in the entries of the second column.

In order to continue satisfying the space constraints, the enlargement of the

table requires that the icons in the first column be enlarged and that the font

of the text in the second column be enlarged. The message passing sequence

for the first requirement is illustrated in Fig. 7, where al is the table agent,

and a2 and a3 are icon agents presenting the two icons in the first column.

The events appear in Fig. 9. The table agent asks the two icon agents to

enlarge their presentations (event el and event e2). This request is accepted

by a2 (event e3), but rejected by a3 (event e4). Because of the rejection

136 Yi Han and Ingrid Zukerman

from a3, this requirement is dropped even though a2 hasno objection to

it. The table agent then creates a

cancel-request-event

(e5) and proceeds to

consider the second of the above requirements. Event e5 interrupts a2, and

causes a2 to abort its plan, clear the messages it sent to al, and recover

its previous presentation. This event differs from the

remove-agent-event

that no recovery takes place in the

remove-agent-event.

ASKING-EVENT

sender:

receiver:

message:

enlarge IconA

OK-EVENT e3

sender:a2

receiver: al

message:

enlarge IconA

CANCEL-REQUEST-

EVENT e5

sender:

receiver:a2

message:

enlarge IconA

ASKING-EVENT e2

sender: al

receiver:a3

message:

enlarge ICOnB

REJECTION-EVENT e4

sender:

receiver:

message: enlarge IconB

Fig. 9. Events causing a request cancellation

5 The Presentation Planning Process

Agents in MAGPIE have three basic functions: (1) task decomposition, (2) con-

straint satisfaction, and (3) event handling. A master agent capable of presenting

composite information performs task decomposition in order to divide the task

into sub-tasks. It then creates a server agent to perform each sub-task. All agents

are able to evaluate the satisfaction of constraints pertaining to their presenta-

tions and to communicate with other agents by means of events.

In MAGPIE, the structure of a multimodal presentation plan consists of

segments

and

segment containers.

A segment defines a modality-specific display

which presents atomic information, i.e., information which is not decomposable

(Section 6). A segment container is generated to convey composite information.

It includes a list of elements which in turn can be either segments or segment

containers. A segment container describes the integration format of its elements

on the basis of the semantic relations between the discourse components that

yield these elements (Sections 7 and 8). This integration format is represented by

means of constraints over the different elements, where the constraints may have

Using Cooperative Agents to Plan Multimodal Presentations 137

different strengths (required and preferred). All the components of a modality-

specific presentation are generated simultaneously and integrated into a display

format determined by the agent in charge of the presentation.

When a master agent generates a segment container, it posts constraints

which restrict the modality and space consumption of the components of the

segment container. It then hires server agents to generate these components.

These server agents generate partial plans, where each plan specifies a component

of the whole multimodai presentation. In this manner, when the master agent

assigns values to its segment container, the server agents in its agent group will

know the requirements placed on their partial plans. A server agent can then add

its own constraints if it is the master agent of another group of agents. Hence,

during the planning process, requirements of an existing plan are transferred

to server agents by means of constraint propagation. These constraints ensure

that each component segment satisfies the requirements of the overall discourse.

For instance, if the presentation planning agent in Fig. 4 wants the text to be

displayed to the right of the table in the same window, it will create constraints

on the width and height of the gable and the text in relation to the window size

(Han and Zukerman, 1995). These constraints are then propagated to the table

agent, and hence restrict the expansion of the table. In this case, the space left for

the text must be wide enough for the longest word in the text and must exceed

a certain proportion of the window. Otherwise, the text is displayed below the

table, and a different set of constraints is created.

A variable is defined as a parameter or an element of a parameter in a partial

plan, e.g., the width of a column in a table. Each agent in the system is in charge

of a subset of the variables and instantiates these variables while designing its

partial plan for a modaiity-specific component. Constraints may exist between

variables of different agents, and the instantiations of the variables must satisfy

these inter-agent constraints. Consequently, the constraint satisfaction problem

in multimodal presentation planning is a Distributed Constraint Satisfaction

Problem (DCSP). ~-Sarther, due to the hierarchical task decomposition process

performed in MAGPIE, the constraints pertaining to the presentation plans of

the different agents are distributed in the plan hierarchy formed during this pro-

cess (Section 3). For instance, the presentation planning agent poses constraints

on the width and height of the table and the text in Fig. 2, so that they can

fit in the window. Similarly, the table agent restricts the space occupied by the

entry components generated by the icon, number and text agents.

5.1 The Generic Planning Process

In order to cope with the DCSP, each agent in MAGPIE maintains the local

consistency of a subset of the constraints, and cooperates with other agents with

respect to the global consistency of all the constraints. In addition, an agent

attempts the satisfaction of required constraints first, and then the satisfaction of

additional preferred constraints if possible. The presentation planning procedure

receives as input an agent to be activated, which initially is the presentation

planning agent, and a discourse structure annotated with the features of the

138 Yi Han and Ingrid Zukerman

Procedure Agent-planning (agent, discourse-struct)

Task Decomposition

1If the information in discourse-struct is composite then

2. Determine the format of integration and the content of each component.

3. Post constraints to restrict the modalities to be used for each component.

4. Propagate modality constraints to obtain candidate modalities for

presenting each component.

5. For each component do

6. Use heuristics to select modalities from the candidates and activate

Agent-planning with the selected agents.

7. Post space constraints to restrict the size of each component.

Initial Planning

8Instantiate plan variables to satisfy the required space constraints

pertaining to the variables.

9Inform the parent agent of the completion of the variable instantiation

process.

Reactive Planning

10Wait until a normal event is received

11. If agent is required to modify a variable then

12. Review the local consistency of the constraints, modify the relevant

variables accordingly, and update the presentation if necessary.

13. Report to the agent which demanded the modification.

14. If time permits and agent is a master agent then

15. Modify variables to satisfy additional preferred constraints if possible.

16. Ask relevant server agents to modify their plan variables accordingly.

Fig. 10. Presentation planning procedure

information to be conveyed. It generates a presentation by recursively activating

modaiity-specific agents. When multiple agents are created, several processes run

simultaneously, one for each agent. The generic version of this procedure, which

is called Agent-planning, appears in Fig. 10. Refinements of this procedure for

icon agents, table agents and chart agents are described in Sections 6, 7 and 8

respectively.

The presentation planning procedure is divided into three stages: (1) task

decomposition, (2) initial planning, and (3) reactive planning.

Task Decomposition (Steps 1-7) - In this stage a master agent, such as a

table agent or a chart agent, distributes its task to several server agents. This

task consists of the presentation of composite information. Since different in-

tegration formats are adopted by different master agents, individual methods

are used by each type of agent to decompose the information (Step 2). Fur-

thermore, specific modality constraints are imposed on the components by

each integration format (Step 3).

Modalities are selected during Steps 4-6 of Agent-planning, where modality

constraint propagation is invoked to obtain alternative modalities for presen-

Using Cooperative Agents to Plan Multimodal Presentations 139

ting each component (Section 7.1). Following this process, a master agent is

able to activate server agents (Steps 5-6). Finally, space constraints pertain-

ing to a specific integration format are created to restrict the components

generated by each server agent (Step 7). These constraints are imposed after

the agent activation process so that parameters of a segment or segment

container can be referred to in the constraints.

Initial Planning (Steps 8-9) - In this stage an agent seeks the satisfaction

of required constraints. In Step 8, a master agent propagates the variables

instantiated by the server agents that are activated in Step 6 in order to

instantiate its own variables which pertain to the format of the integration,

e.g., the width of each column in a table (Section 7). If the task of an agent

is to convey atomic information, its procedure starts to run from Step 8.

In this case, the variables of its plan are instantiated based on the current

space constraints. If no constraints have been posted, default settings are

used (Section 6).

Reactive Planning (Steps 10-16) - In this stage an agent modifies plan

variables to repair a constraint. To this effect, an agent waits until it re-

ceives a normal event, and performs the actions defined in the handler of

this event. The agent stays in this stage after the event has been processed

until a

remove-agent-event

or a

time-up-announcement

terminates its process

(Section 4.1). Steps 11-13 handle a request from a parent agent to modify

a variable, e.g., reduce the width of an icon. Since the satisfaction of a re-

quest for the modification of a variable (e.g., the width of an icon) may

cause modifications with respect to other variables (e.g., the height of this

icon), constraint propagation is used to evaluate the local consistency of the

constraints pertaining to this modification. Steps 14-16 activate agents with

requests pertaining to the satisfaction of additional preferred constraints in

order to improve a presentation plan if time permits. Only the presentation

planning agent can generate the normal event which carries such a request,

and only agents which present composite information, i.e., the table agent

and the chart agent, can be activated by such a request. Further, each of

these agents has individual methods and heuristics for repairing violations

of preferred constraints (Han, 1996). For instance, a table agent attempts to

repair violations of preferred constraints pertaining to the width of columns

(if any) prior to those pertaining to the height of rows, since the elements in

columns tend to be of more uniform size than the elements in rows. This is

because the table agent demands that the same modality be used to present

the elements in a column (Section 7).

Communication between agents is necessary at different stages of this pro-

cess. Firstly, since the modality which is suitable for presenting a component may

be relevant to other components, the modality selected in Step 6 must be agreed

on by the agents presenting related components. For instance, all the agents

presenting the entries in a table column must agree on a presentation modality,

since, as stated above, the table agent demands that the same modality be used

to present the elements in a column. In addition, if a modality is dropped from

140 Yi Han and Ingrid Zukerman

consideration due to the violation of a modality constraint, the agents in charge

of it must be removed. Space constraints restrict the size of a presentation com-

ponent in relation to the size of others. Hence, communication between agents is

also required for agents to satisfy space constraints cooperatively. In addition, if

these components are generated by different agents, each agent must ensure the

local consistency of constraints pertaining to its variables (Steps 8, 12 and 15).

Finally, upon completion of the plan generation process, an agent reports back

to the agent in charge of the presentation (Steps 9 and 13): an

OK-event

reports

the success of the plan generation process, and a

rejection-event

reports its fail-

ure. In the former case, the effect of the modified variables on the presentation

plan is determined by means of constraint propagation. Consequently, the agents

in charge can evaluate their constraints and modify their variables accordingly.

Each time an agent produces a presentation component either during the

initial planning stage or during the reactive planning stage, it saves the com-

ponent in the blackboard owned by its master agent. Thus, a master agent can

gather from the blackboard the components generated by its server agents, and

integrate them into a particular format. For instance, the initial presentation of

the text paragraph in Fig. 2 is generated at the same time as the table in a

format that fits the width of the window, and allows the text to be presented

either above or below the table. However, MAGPIE prefers to present the text

next to the table because our eyes naturally move from left to right (Holmes,

1984). Hence, upon completion of the generation of the table, the presentation

planning agent asks the text agent to re-format the text and place it next to

the table (Fig. 2). If time is restricted or there is not enough room next to the

table, the text is displayed below the table (Han and Zukerman, 1995).

As indicated in Section 4.1, the presentation planning procedure may be in-

terrupted at any stage by an urgent event or an announcement. A

remove-agent-

event

or a

time-up-announcement

brings this procedure to an end. In addition,

an agent may receive a

cancel-request-event

while it is handling a request, e.g.,

while it is modifying a plan variable during the reactive planning stage. When

this urgent event interrupts the planning process, the handler of this event aborts

any action that is being carried out, reinstates the previous presentation on the

blackboard, and restarts the process from Step 10 to wait for another event.

6 Presenting Atomic Information: Icon Agent

Agents presenting atomic information generate segments which specify parame-

ters such as the font, color and size of a modality-specific display. In this section,

we describe the planning process of the icon agents in MAGPIE.

An icon agent in MAGPIE generates an icon segment which specifies the

width and the height of an icon (in pixels), and the entry of its bitmap in the

icon library. At present, icons of different sizes are pre-stored in the icon library

and retrieved using an entry code (Han, 1996). For instance, the computer icon

in Fig. 2 is specified in the segment in Fig. 11, where name specifies the object

to be conveyed, i.e., the name of the icon to be retrieved from the icon library,