%\documentclass[runningheads]{llncs}
%In order to omit page numbers and running heads
%please use the following line instead of the first command line:
\documentclass{llncs}.
%Furthermore change the line \pagestyle{headings} to
%\pagestyle{empty}

\input{psfig.sty}

\begin{document}

%\pagestyle{headings}
%In order to omit page numbers and running heads
%please change this line to
\pagestyle{empty}
%and change the first command line too, see above.

\mainmatter

\title{Architecture of Multi-Modal \\ Dialogue System}

%\titlerunning{Lecture Notes in Computer Science}

\author{Martin Fuchs \and Petr Hejda \and Pavel Slav{\'\i}k}

\authorrunning{Petr Hejda et al.}

\institute{
	Department of Computer Science and Engineering, \\
	FEE, Czech Technical University, \\
	Karlovo n{\'a}m. 13,\\
	12 135 Praha 2, Czech Republic \\
  \email{slavik@cslab.fel.cvut.cz}\\
  \email{phejda@ra.rockwell.com}\\
  \texttt{http://www.cgg.cvut.cz}
}

\maketitle

\begin{abstract}
This article describes an architectural framework of a multi-modal dialog system. The framework is based on separation between the semantic and the syntactic parts of the dialog. The semantics of the human-computer conversation is captured using a formal language. It describes the conversation by means of sequences of dialog elements. The paper further elaborates how to derive the syntactic features of the conversation. A two-layer architecture has been proposed for the dialog system. The upper layer, called sequencer, works with the description of the whole dialog. The lower layer (driver dock) deals with individual dialog elements.

A prototype has been implemented to demonstrate the main benefits of our framework. These are adaptability and extensibility. The adaptability involves multiple modes of communication, where the modalities can be changed even during the course of a dialog. Due to layering, the applications can be easily extended to additional modes and user interface devices.
\end{abstract}

\section{Introduction}

This article describes an architecture framework of a multi-modal dialog system. In general, a multi-modal dialog system takes advantage of the multi-sensory nature of humans. It can utilize more than one sense for communication. Traditionally, applications are based on visual modes. Additional modes can be, for example, speech, gesture, and tactile input/output modes. The multi-modal approach increases the bandwidth of human-computer interaction and it may improve the interactive nature of the system. Also, it allows for deployment of the system in various environments.

Multi-modal systems may find their applications in a number of fields. To name only a few examples, they proved to be a viable aid for visually impaired users, an alternative to WIMP{\footnote{Windows, Icon, Menu, and Pointer based interfaces}} interfaces in mobile computing, or an entertaining extension of computer games. 

The functionality of a multi-modal system can be fairly extensive. We have focused on a simple, yet extensible dialog based system. The main purpose of the system is to present information to the user and to query him for data. The challenge was to build a system with the following features:
\begin{itemize}
\item {\bf Simple Architecture} The architecture should be as simple as possible. It has to specify function blocks, their roles and type of data the blocks exchange.
\item {\bf Extensible} The system should be open to new communication devices. Once there is a need to connect a new device or use a new mode, the system should {\bf not} be re-implemented.
\item {\bf Adaptive} The system should allow for changing of modalities. These changes should be possible even during the run-time of the system.
\end{itemize}

The text of this article is structured as follows. Section \ref{sec:formal} introduces formal description of a human-computer conversation utilized in our approach. This formal description is used in the architecture as described in Section \ref{sec:arch}. Section \ref{sec:proto} gives details of our system prototype. The last section summarizes our ideas and deals with the future development.

\section{Formal Description of a Dialog \label{sec:formal}}

The framework focuses on multi-modal dialog systems in which the dialog consists of a finite number of dialog element types. In our previous work, we have shown that a class of dialogs can be described via sets of predefined, parameterized dialog elements \cite{hejda:99}. These elements capture the semantics of the human-computer conversation. The elements can be divided into classes according to the type of information which is expected as the result of the conversation with the user.

An example of an element can be a simple question, such as 
{\it ``Would you like to continue?''}. It can be captured by a dialog element with following formal description{\footnote{This example uses XML, see bellow.}}:
\begin{verbatim}
    <question id="2" default="yes">
        Would you like to continue?
    </question>
\end{verbatim}

The description captures three pieces of information: 
\begin{itemize}
\item [1] The {\bf request} is a question sentence {it ``What ...''}
\item [2] The {\bf answer} {\it ``yes''} or {\it ``no''} is expected
\item [3] The {\bf default value} is {\it ``yes''}
\end{itemize}
These three pieces capture the semantics of the dialog element.

The dialog system has to add syntax of the actual conversation with the user. This may vary according to the device and mode used for the communication with the user. For example, the {\bf request} can be displayed together with a check box. The check box is initially checked to reflect the {\bf default value}. In another situation, the speech recognition and synthesis is used. In that case, the system voices the request to the user and expects one of the words {it ``yes''}, {\it ``no''}, {\it ``default''}, {\it ``whatever''}, {\it ``yep''}, {\it ``o.k.''} etc \dots As a result, the dialog system can have some freedom in interpreting the dialog elements and handling the actual conversation with the user.

As mentioned above, the dialog system receives the formalized dialog description. In our prototype, Dialog Markup Language version 2.0 (DML2.0) was used \cite{fuchs:99}. It can describe the following types of dialog elements:
\begin{itemize}
\item [1] {\bf Message.} It presents some information to the user.
\item [2] {\bf Question.} A yes/no answer is expected.
\item [3] {\bf Choice.} An array of choices. The user can chose one or several of them.
\item [4] {\bf Text.} Single-line text. Allows for editing linear text.
\item [5] {\bf TextEdit.} Multi-line text.
\item [6] {\bf Number.} A number is expected as a result.
\item [7] {\bf Program.} Any sequence of simple dialog elements.
\item [8] {\bf Dialog.} Any sequence of simple dialog elements and programs.
\end{itemize}
Each simple dialog element (elements 1--6) represents a part of a conversation focused on delivering or obtaining a basic piece of information, such as a number or a text string. Their semantics is standardized. The last two items in the list describe sequences of simple dialog elements. Their semantics is defined as a sequence of joint semantics of used elements. Hence, the structure and the semantics of the whole dialog are described in a formal way \cite{hejda:98}.

\section{Architecture of the System \label{sec:arch}}

The formal description of the dialog can be used for communication between the user interface part and the application part of the system. This creates a natural division of the application in two sub-systems. The {\bf application side} generates a dialog to obtain some data from the user, for example what to do next, name of a command or its parameters. The {\bf user side} is then responsible for effective interpretation of the formal description. This section focuses on the architecture of the user side (see Figure \ref{fig:architecture}).

\begin{figure}
\centerline{\psfig{figure=architecture.eps,height=2.2in}}
\caption{The architecture of the framwork}
\label{fig:architecture}
\end{figure}

The formalized description of the dialog is processed by the user part to work out the details of the conversation. During this process, it can be decided which modalities to use for which parts of the dialog.

The key concept of our architecture is the definition of higher and basic processing layers: the {\bf sequencer} and the {\bf low-level dock}. The sequencer transforms the DML dialog description into the description of single dialog elements. It processes the whole dialog at once, breaking it into dialog elements. This solves the counteracting nature of linear and non-linear conversation. The linear conversation requires processing of one dialog element at one time. An example can be voice-based conversation. The non-linear conversation, on the other hand, processes dialog elements in parallel, as in case of a formular. The user is free to process the elements in any order  \cite{larson}. The sequencer is the part of the dialog system responsible for making the conversation either linear or non-linear.

Figure \ref{fig:sequencer} depicts a simple dialog which is processed in two ways. In the left-hand side, there is a non-linear conversation. The user is free to choose where to start. The right-hand side shows a sequence of frames featuring the same conversation in a linear fashion. Due to limitations of the small display, the dialog is broken into small pieces. These pieces are processed one by one, in a linear fashion. The figure was rendered by our prototype \cite{fuchs:99}.

\begin{figure}
\centerline{\psfig{figure=sequencer.eps,height=3.2in}}
\caption{The effect of the sequencer on the dialog structure}
\label{fig:sequencer}
\end{figure}

Even though the whole dialog system can be based on the sequencer layer, additional benefits are gained by employing the second layer, low-level dock. It defines a plug-and-play interface for software components processing the dialog elements on various devices using various modalities. The set of plug-ins defines an interface between device independent and device dependent parts of the user part.

For example, there are two modules allowing for the output to either an LCD display (as in Figure \ref{fig:sequencer}) or to a speaker (not depicted). The LCD module breaks any output message into small pieces which can fit the size of the display. To be able to use a speaker as an output, a voice synthesis module has to be used. Its main task is to transform all messages to speech and to repeat the missed parts.

\section{The Prototype \label{sec:proto}}

To prove our ideas workable, we have implemented a working prototype of the application framework. Its structure reflects the architectural model described above. The framework is divided in two parts, the application and user sides. For testing purposes, the application side implements two applications.

The first application is a reader of e-mail. It generates dialogs for reading and sending e-mail messages. The second is an automatic teller machine (ATM) simulator. The dialogs generated by this application mirror the functionality of a real ATM.

The user side was implemented according to the two-layer architecture. Where the sequencer provides the dialog sequencing, the low-level dock and its drivers process the dialogs and allow for various modes. The capabilities of this part are crucial to the functionality of the application.

The following drivers have been implemented for both applications:
\begin{itemize}
\item Term - text-based mode only. The processing is linear.
\item HTML - text with more formatting. The processing is non-linear.
\item Applet - widget based interface. The processing is non-linear.
\item Keyboard - driver for text input.
\item MobileKeys - driver simulating phone keyboard.
\item Mouse - driver for input using a mouse.
\item X-Key - driver for a joystick-like device with two buttons.
\item SmallLCD - driver for a small alphanumeric display.
\item SmallBitmap - driver for a small bit mapped display.
\item Voice - driver for speech synthesis and recognition.
\end{itemize}

The drivers allow for mutual combination and switching during the execution of the application. This results in a highly flexible user interface, which is capable of changing modes of interaction. Although the drivers cover only a small portion of possible input/output devices, it is apparent the drivers are fairly small and easy to implement components.

The implementation of the prototype was done using the Java 1.1\footnote{See \tt{http://java.sun.com/}.} and Extensible Markup Language (XML) technologies\footnote{See \tt{http://www.w3.org/XML/}.}. The Java language brings additional benefits of portability and platform independence. Both the application and the user side were implemented as separate components connected via a data stream.

DML was implemented as an application of XML. This allowed for fast prototyping using the SAX compliant XML parser Aelfred. Speech synthesis and recognition was implemented with IBM's ViaVoice\footnote{See \tt{http://www-4.ibm.com/software/speech/}.} and SpeechForJava API\footnote{See \tt{http://www.alphaworks.ibm.com/tech/speech}.}.

\section{Summary and Future Work}

We have described an architectural framework of a multi-modal dialog system. It is based on the formal dialog description in DML. The formal description captures the semantics of the conversation using dialog elements. The syntactic features are delivered by our two-layer architecture of the dialog system. The upper layer, called sequencer, works with the description of the whole dialog. The lower layer deals with individual dialog elements. As a result, we have got an application framework which allows for changes of modalities even during the processing of a dialog. The other benefit is that the applications can be easily extended to additional modes and user interface devices.

In the future, we would like to extend the framework to cover a wider set of applications and drivers. The other issue is usability testing and evaluation of the framework.

\begin{thebibliography}{4}
%
\bibitem{fuchs:99}
Fuchs, M.:
Multi-modal user interface (in Czech).
Master thesis, Department of Computer Science and Engineering,
FEE, Czech Technical University Prague (1999)
%
\bibitem{hejda:98}
Hejda, P.:
Dialog Markup Language.
Poster99, FEE, Czech Technical University in Prague (1999) IC8
%
\bibitem{hejda:99}
Hejda, P.:
Situations in Dialogs.
In Text, Speech and Dialogue. 
Springer-Verlag, Berlin Heidelberg New York (1999) 290--295
%
\bibitem{larson}
Larson, J. A.:
Interactive Software.
Yourdon Press (1992)
%
\end{thebibliography}

\end{document}



