EUROPA :A Generic Framework for Developing
Spoken Dialogue Systems~Lf~rnehiko
SASAJIhiA,Takehide YANO, and Yaszcyrki KOlVO.
Kansai Research Center, TOSHIBA Corporation
8-6-26 Motoyama Minami, Higashi-Nada, Kobe 658-0015, JAPAN(sasa,yano,kono) @krl.toshiba.co.jp

ABSTRACT
Voice interfaces are not popular since thcy are neither
useful nor user-friendly for non-specialist users. In thispaper, EUROPA a new framework for developing
spoken dialogue systems, is introduced. In developing
EUROPA, h e authors focused on three points : (1)acceptance of spoken language, (2) portability in termsof domain and task, and (3) practical performance of the;ipplied system. The framework is applied toprototlping a car r~vigation system called MINOS.
MlNOS is built on a portable PC, can process over 700~vordsof recognition vocabulary, and is able to respondto a user's question tvithm a few seconds.
Keywords: spoken dialogue system, voice interface,
car navigation system

1. LYTRODUCTION
Rcccntly, some systems such as car navigation qstems
or information desk %stems are equippcd with a voiceinterface. Ho~ve\.er.voicc interfaces are not popularsince they arc neihcr useful nor user-friendly for nonspecialist users. To solve this problem, this paper
focuscs on the follo\\.ing three points.
First, thc yoice interface should accept spoken language.
Application of the voice interface is effective especiallywhen thc user is not able to usc hidher hands because ofarlothcr hsk, for esarnple, driving a car, cooking in akitchen. or openting a power plant. It would be difficult
for such users to conlmunicatc their intention in written
language, which involves many grammaticalconstraints.
Second, it is v e v important for voice interfaces to be
independent of task and domain as much as possible. In
developir~gvoice interfaces: the nced for modifications,such as enhancement of domain knotvledge or changcof task, frequcntl! arises. The task- and domainindcpcndcnt frame\\ork rcduccs the cost of feedingback the requests to the inferface.
Lastly, thc system ~vith the voice interface should
answer users' questions within a shon time. Somc tasks

such as car navigation or cooking require prompt
answers. Slow systems are not useful.
The authors adopted three approaches and integrated
them into a framework called EUROPA, which stands
for "Environment for building Utterance Recognizable
PAckdges." To accept spoken language, the voicerecognition module of the spoken dialogue system
based on EUROPA does keyword-spotting. A sequenceof spotted keywords represents a sentence as well as auser's intention.
Ncst, to make dialoyc systems task- and domainindependent, EUROPA separates moduleddata into thedomain-dependent
moduleddata
anddomainindependent moduleddata. To run a dialogue, thedialogue system must control a set of modules which
belong to one of the two groups. Our framework copeswith this point by adopting an interpreter for such codesthat manage dialogue.
Lastiy, to gain enough speed for the response, we havedeveloped a BTH parser[]] for parsing keyword-lattices.
Also the script for managing problem solving iscompiled beforehand into another form to be interpreted
faster.
EUROPA is applied to prototyping a car navigation
system. The system answers two types of qucstions.
One is the iocation of something such as a facility, ascnice-area; a parking lot or a shop. The other is aduntion between two locations. All necessary modules
are built on one notebook PCPentium 11 266MHz),
which accepts more than 1 million patterns of sentences
and in almost all cases answers within 2 seconds.

2. THE EUROPA FRAh1EWOR.K
2.1 Overview
We have designed EUKOPA as a generic framework for
spoken dialogue systems. Figure 1 shows thc' overall
process of man-machine dialogue in EUROPA.
The svord-spotling engine recognizes the user's utterance and it generates a kcyword lattice as a recognition
result. The obtained lattice is parsed by thc BTH parser

ESCA. Eurvspeech99. Budapesf, Hungary ISSN 1018-4074, Page 1163r;the module is depicted in Figure 2.

2.3.1 Dialogue managemml process
Firstly, it transforms the given set, into a set of representations of input intention, each of which corresponds
to a word-sequence candidate, by e~nployingIntention
Translator.
Then it resolves a usefs question by referring to theknowledge base and generates meaning representationof the query that corresponds to the most plausible
word-sequence and its answer. Obtaining the information, the Response Generator generates responding
sentences. The problem-solving process is based on
unification of feature structures.
Figure 1: Dialogue process

to generate a set of possible keyword sequences, each ofwhich is acceptable by the given grammar. The set isanalyzed and solved in terms of meaning and the mostplausible keyword-sequence in the set is selected. Finally, the reply to the user's question is played back bysynthesized voice.

2.2 BTH Parser
To accept spoken language, our voice recognition module does keyword-spotting and outputs a keyword lattice. Parsing the keyword lattice, the parser extracts
plausible word-sequences. Each of the word-sequences
represents the user's intention. In the case of spoken
Japanese, misuse or loss of particles often occurs. Keyword spotting does not deal wvith them, whlch simplifies
acceptable gmmmar rules. This characteristic also
solves the problems of dealing with unnecessary terms
such as "aah or "well." Just by excluding them fromthe keyword set, wve can accept sentences wvith thesewords.
Furthermore, change of word order which also occurs inJapanese spoken dialogue can be easily dealt with. TheBTH parser is employed for efficiently parsing thekeyword lattice, which is obtained by keyword-spotting,and it is transformed into a set of possible keywordsequences. The details of the BTH parser are describedin [l].
In the case of the task, it is common for over 100 spotted words to be notified from the recognition engine,and consequently over 1 million possible word sequences can be generated by unfolding the corresponding lattice even if wordclass bi-gmm is applied to thelattice. BTH,however, is able to parse such a large lattice within a practical time.

2.3 USH1:Script-based m e t h o d for D i a l o g u emanagement
Obtaining the set of possible keyword-sequences fromthe BTH parser, the lalogue controlling module processes it to generate a reply. The overall configuration of

2.3.2 Enhancement of portability
Portability is required for the framework for building a
spoken dialogue system. In the prototyping and testing
cycle, the need for modifications, such as enhancementof domain knowledge or change of task frequently
arises, even if the domain and the task do not change.
As shown in Figure 2, EUROPA separates modules into
two groups. One consists of the domain dependent
moduleddata such as a word dictionary, grammar rules,
rules for translating user intentions, rules for generating
sentences as an answer to the user input, and domainspecific problem solvers, such as Placeexpression Resolver and Route Resolver. The other consists of domain-independent moduleddata such as a lattice parser,
an interpreter for translating user intentions, and an interpreter for generating answver sentences.

2.3.3 USHI specification
To run a dialogue. Lhe dialogue system must control aset of modules, wvhich belong to one of the two groups.
For example. a car navigation task that solves a location
specified by a user utterance, requires not only a genericparser but also a domain-specific problem solver which
resolves the location the user intended. Embcdding suchcontrol codes including domain-specific parts reduces
portability of the framework.
EUROPA solves this problem by adopting an interpreter for such codes that m 1 g e dialogue. We call tfus
interpreter the "USHI Interpreter" which stands for"Unification-based Script Handling Instruction set Interpreter." A system developer describes the process of
meaning halysis, problem-solving. and response generation in an USHI script, and the module interprets thescript
USHI script language is a Pascal-like language and has
the following three features: (1) Subset of statements forexpressing selection and looping, (2) Unary and binary
operators for calculation and comparison, and (3) Ability to invoke a fwiction dcfincd in the other part of thescript or a system enlbcddcd one iw~ittenby C++. For
dealing with featurc structures and knowlcdgc base. thescript has two more features.
(1) Unification between feature structures.
(2) Access to the knowledge base.

Page 1 164

-.
-.
E ?
52-1- 1--.-.
--.---:-------

7
5
r-USHl InQudn-cCJ.(.I

CotltrdDarmn rndcpmdcnt

Dialogue Controlling Module

USHI:UniiiiaIim4urdWipl Hmw lnrmma aFigure 2: Dialogue controlling modules
Furthermore, to gain enough speed for the response, theUSHI script for managing problem solving is compiled
beforehand into another form to be interpreted faster, as
shown in Figure 2.
2.3.4 Dialogue management example
For example, a car navigation task which solves theuser's query about the location of an interchange is controlled by the USHI interpreter and an USHI script which includes a procedure consisting of two steps.
Stepl: If the user's intention is to seek for a place thatsatisfies some conditions, then call a function which resolves the uscr's expression about a place.
Step2: If the uscr's expression is resolved, then call thercsponse generator to generate an answer sentence which includes the user's original expression and the answer.

When a word-sequence "Where is the next interchange?"~ input, the Intention Translator translates it
into a data structure called "user intention." A user intention is a form of typed feature structure. Translator isa domain independent module and has a knowledge
base whch is initialized by Intention templates thatspecifies mapping rules among utterance patterns andthe user intentions. The utterance of this example istranslated into the follo~vingstructure I . Leners lefthand side of the sign of aggregation "(" means the typesymbol, left-hand side of the ":" means a feature, andthe right-hand side of the ":" means the value of thefeature.

,' The structure implemented on MINOS has more features,and unbound features are not printcd hae.

Next, the USHl interpreter interprets the USHI script
Stepl, and calls the Place-expression resolver with anargument which specifies the condition of the location

The Place-expression resolver utilizes the Knowledgebase Manager and accesses the route data set by the user,
data about geographcal features, location of objects
such as shops or gas-stations, and so on.
If the Place-expression is resolved, the USHI interpreter
proceeds to the Step2. For esample, if the resolved answer is "Suita Interchange," then an answer sentence"The next interchange is Suita Interchange." is generated. The sentence in the form of text is input to theI T S module, which is a former version of the TOS
Drive TTS[2],and output.

2.4 MINOS: an application of EUROPA
EUROPA is applied to prototyping a car navigation
system, called MMOS. Figure 3 shows a view of thesystem. A sample screen copy of MINOS is shown in
Figure 4.
The system answers two types of question One is thelocation of something such as a facility, a service-area,

Page 1165

Figure 4: A screen copy of i\fIXOS
Figure 3: View oJl\./I.YOSa parking lot or a shop. The olher is the duration between two locations. AII modules including the voicerecognition, the dialogue control, and thc text to speechengine are built on one notebook PC (Pcntium I1266MHz), which acccpts more than 1 million pattcrns
of setltences and in alrnost all cascs answers within 2seconds.
MINOS is able to respond to queries with respcct to locations made by a user while dnving a car. Modules inMINOS run collabontively. communicating with eachotller via socket-bascd messaging. As shown in Figure 4,
the application module of MINOS has a map-based appcardncc. which is based on ProAtlas, a map sortware
dcvclopcd by ALPS Mapping Co., Ltd. It simulates car
driving by replaying prcrccorded position data obtained
from the Global Positioning Satellite (GPS) system.
Thc applic;~tion nlodule sin~ulatesdriving a car andco~ilinuouslynotifics thc di:tlog~emodule of the simulated current position at rcgular intervals of time. Whcna uscr asks a question in Japanese, e.g., "Deguclii-nomae-no-saigo-no-semicc-arca-ha-doko?(Where is thelast service area before the exit?)", the word-spotting
engine recognizes Uie utterance and notifies Ihe dialogue controlling module of a keyword latticc. MINOS
can process over 700 words of recognition vocabulary.
Next, MINOS analyzes the keyword lattice by employing the BTH parser and obtains a set of canddate wordscqucnces, referring to tllc over 1 million sentence patterns. The word-sequences are sorted in the dcscending
ordcr of thc initial score of each candidate, which is calculated from phonetic scorcs of the canddate's words.
Each uord-sequence candidate is converted into a user'sintention in the fonn of a typed feature structure, and isrcsolvcd by using current position infornlation and theknonledge base. The knowledge base is a semantic
network that contains all the kno\\lcdgc rcquired lo solve questions about locations on the displayed map.
The scorc of cach candidate is rcvised in terms of phonetic value and meaning. which is the cost of problem
solving. and thc list of the candidates is reordered. As aresult, the candidate with lhc best score is selected andthe text of the answer corresponding to the question isgenerated, e.g., "Amagasaki Sewice Area is the last
service area bcfore Nishinomiya Intcrchangc" and the
dialogue controlling module notifies thc lTS engine ofit.
One more function of EUROPA is asking back to theuser when the score of the sentence is lower than agiven threshold, such as "Did you ask about a restaurant
just before the dcstination?''

3. CONCLUSION
We have developed EUROPA, a gencric framework for
spoken dialoguc systems. Aiming at enhancement of thesclilc of the task and portability in tenns of task anddomain, it employs an cllicicnt keyword lattice-parser,
BTH[I] and script-based mcthod for dialogue management, USHI. EUROPA was applied to protolyping aPC-based spontaneous spccch interface for car navigation tasks, MINOS.
The result shows promise with respect to implementation of the runction of a spontaneous s+ech interface innest-generation car navigation qstcms equipped with
RISC MPUs of about 7OMIPS.
Currently, MINOS is a question-answcr system, andfuture work will consider about more interactive dialogue and the resolution of the reference such as usageof pronouns.

4. REFERENCES[ l ] Kono, Y., Yano, T., and Sasajima, M.(1998), BTH:An Efficient Parsing Algorithm for Word-Spotting.
Proceedings o/ICSLP '98, pp. 2067-2070.
[2] Akamine, M. and Kagoshima, ~.(1398),Anid??ic
Generation of Synthesis Units by Closed Loop
Training for Totally Speaker Driven Test to Speech
Systcm (TOS Drive ITS). Proceetlirrgs of lCSIJP'9S, pp. 1927-1930.

Page 11 66