Design of multimodal dialogue-based systems

Multimodal dialogue systems integrate advanced (often spoken) language technologies within human-computer interaction methods. Such complex systems cannot be designed without extensive human expertise and systematic design guidelines taking into account the limitations of the underlying technologies. Therefore, this thesis aims at reducing the time and effort needed to build such systems by creating application-independent techniques, tools and algorithms that automate the design process and make it accessible for non-expert application developers. The thesis proposes an interactive system prototyping methodology, which (together with its software implementation) allows for rapid building of multimodal dialogue-based information seeking systems. When designed with our methodology, even partially implemented system prototypes can immediately be tested with users through Wizard of Oz simulations (which are integrated into the methodology) that reveal user behavior and modality use models. Involving users in early development phases increases the chances for the targeted system to be well accepted by end-users. With respect to dialogue system design, we propose a two-layered dialogue model as a variant of the standard frame-based approach. The two layers of the proposed dialogue model correspond to local and global dialogue strategies. One of the important findings of our research is that the two-layered dialogue model is easily extendable to multimodal systems. The methodology is illustrated in full detail through the design and implementation of the Archivus system – a multimodal (mouse, pen, touchscreen, keyboard and voice) interface that allows users to access and search a database of recorded and annotated meetings (the Smart Meeting Room application). The final part of the thesis is dedicated to an overall qualitative evaluation of the Archivus system (user's performance, satisfaction, analysis of encountered problems) and to a quantitative evaluation of all the implemented dialogue strategies. Our methodology is intended (1) for designers of multimodal systems who want to quickly develop a multimodal system in their application domain, (2) for researchers who want to better understand human-machine multimodal interaction through experimenting with working prototypes, (3) for researchers who want to test new modalities within the context of a complete application, and (4) for researchers interested in new approaches to specific issues related to multimodal systems (e.g. the multimodal fusion problem).

Error handling in multimodal voice-enabled interfaces of tour-guide robots using graphical models

Plamen Prodanov

Mobile service robots are going to play an increasing role in the society of humans. Voice-enabled interaction with service robots becomes very important, if such robots are to be deployed in real-world environments and accepted by the vast majority of potential human users. The research presented in this thesis addresses the problem of speech recognition integration in an interactive voice-enabled interface of a service robot, in particular a tour-guide robot. The task of a tour-guide robot is to engage visitors to mass exhibitions (users) in dialogue providing the services it is designed for (e.g. exhibit presentations) within a limited time. In managing tour-guide dialogues, extracting the user goal (intention) for requesting a particular service at each dialogue state is the key issue. In mass exhibition conditions speech recognition errors are inevitable because of noisy speech and uncooperative users of robots with no prior experience in robotics. They can jeopardize the user goal identification. Wrongly identified user goals can lead to communication failures. Therefore, to reduce the risk of such failures, methods for detecting and compensating for communication failures in human-robot dialogue are needed. During the short-term interaction with visitors, the interpretation of the user goal at each dialogue state can be improved by combining speech recognition in the speech modality with information from other available robot modalities. The methods presented in this thesis exploit probabilistic models for fusing information from speech and auxiliary modalities of the robot for user goal identification and communication failure detection. To compensate for the detected communication failures we investigate multimodal methods for recovery from communication failures. To model the process of modality fusion, taking into account the uncertainties in the information extracted from each input modality during human-robot interaction, we use the probabilistic framework of Bayesian networks. Bayesian networks are graphical models that represent a joint probability function over a set of random variables. They are used to model the dependencies among variables associated with the user goals, modality related events (e.g. the event of user presence that is inferred from the laser scanner modality of the robot), and observed modality features providing evidence in favor of these modality events. Bayesian networks are used to calculate posterior probabilities over the possible user goals at each dialogue state. These probabilities serve as a base in deciding if the user goal is valid, i.e. if it can be mapped into a tour-guide service (e.g. exhibit presentation) or is undefined – signaling a possible communication failure. The Bayesian network can be also used to elicit probabilities over the modality events revealing information about the possible cause for a communication failure. Introducing new user goal aspects (e.g. new modality events and related features) that provide auxiliary information for detecting communication failures makes the design process cumbersome, calling for a systematic approach in the Bayesian network modelling. Generally, introducing new variables for user goal identification in the Bayesian networks can lead to complex and computationally expensive models. In order to make the design process more systematic and modular, we adapt principles from the theory of grounding in human communication. When people communicate, they resolve understanding problems in a collaborative joint effort of providing evidence of common shared knowledge (grounding). We use Bayesian network topologies, tailored to limited computational resources, to model a state-based grounding model fusing information from three different input modalities (laser, video and speech) to infer possible grounding states. These grounding states are associated with modality events showing if the user is present in range for communication, if the user is attending to the interaction, whether the speech modality is reliable, and if the user goal is valid. The state-based grounding model is used to compute probabilities that intermediary grounding states have been reached. This serves as a base for detecting if the the user has reached the final grounding state, or wether a repair dialogue sequence is needed. In the case of a repair dialogue sequence, the tour-guide robot can exploit the multiple available modalities along with speech. For example, if the user has failed to reach the grounding state related to her/his presence in range for communication, the robot can use its move modality to search and attract the attention of the visitors. In the case when speech recognition is detected to be unreliable, the robot can offer the alternative use of the buttons modality in the repair sequence. Given the probability of each grounding state, and the dialogue sequence that can be executed in the next dialogue state, a tour-guide robot has different preferences on the possible dialogue continuation. If the possible dialogue sequences at each dialogue state are defined as actions, the introduced principle of maximum expected utility (MEU) provides an explicit way of action selection, based on the action utility, given the evidence about the user goal at each dialogue state. Decision networks, constructed as graphical models based on Bayesian networks are proposed to perform MEU-based decisions, incorporating the utility of the actions to be chosen at each dialogue state by the tour-guide robot. These action utilities are defined taking into account the tour-guide task requirements. The proposed graphical models for user goal identification and dialogue error handling in human-robot dialogue are evaluated in experiments with multimodal data. These data were collected during the operation of the tour-guide robot RoboX at the Autonomous System Lab of EPFL and at the Swiss National Exhibition in 2002 (Expo.02). The evaluation experiments use component and system level metrics for technical (objective) and user-based (subjective) evaluation. On the component level, the technical evaluation is done by calculating accuracies, as objective measures of the performance of the grounding model, and the resulting performance of the user goal identification in dialogue. The benefit of the proposed error handling framework is demonstrated comparing the accuracy of a baseline interactive system, employing only speech recognition for user goal identification, and a system equipped with multimodal grounding models for error handling.

EPFL2006

Object-oriented approach for dynamic system modelling and simulation

Adel Besrour

Software engineering always cares to provide solutions for building applications as close as possible to what they should be, according to the requirements and the final users needs. Systems behavior simulation is a very common application to virtually reproduce and often predict the real-world behavior. Simulation is one of the most operational research tool in a large variety of engineering and scientific domains: Transport, telecommunication, medicine, chemical processes, physics, etc. The complexity of such application is relative to the increasing complexity of the systems. In this context, it is relevant to bring together different tools and formalisms such as markovian chain, Petri nets, etc., to improve the existent approaches and so to answer the simulations performances needs. The principle objective of this thesis is to bring together techniques from software engineering and safety engineering in order to improve the state of the art of modeling and simulation of dynamic systems in the industrial context. In addressing this objective, this work initially involves defining the essential limitations of the used formalisms, methods and tools regarding from one hand the software engineering modeling and simulation techniques and from the other hand the existent risk analysis methodologies. This work is conducted with respect to the problem of danger identification, considering the context of the complex systems behavior and their interaction with the human operator. In software engineering, it is well known that Petri/high-level nets have attractive characteristics to be used in systems simulation and behavior prediction such as the natural graphical representation, and their well-defined semantic. They are well-suited for the description of complex situations with concurrency (interleaving and true concurrency depending on the underlying semantics), conflict and confusion. However, the absence of structuring capabilities has been one of the main criticisms raised against Petri nets/high-level nets. Thus, there have been many attempts to introduce structuring principles in nets of this kind [BCM88] [Kie89] [JR91]. The attractive characteristics of Petri/high-level nets have prompted researchers to enrich these formalisms with object-oriented features. CO-OPN (Concurrent Object-Oriented Petri Net) approach, brings together the power of both Petri/high-level nets and object-orientation techniques, it has been devised so as to offer an adequate framework for the specification and design of large scale concurrent system [BG91]. CO-OPN, as a powerful modeling tool, has been used in a limited way to simulate systems. This work aims to provide a CO-OPN extension to allow a more realistic systems' simulation. Actually, its simulator semantic uses to be a suitable approach for modeling near closed systems and software components, because they need to loose coupling with external world. But, when we model more realistic problems like industrial processes, where human interaction is a relevant event, this approach is not sufficient to catch all system activity attributes. Moreover, the CO-OPN interpretation process does not allow interaction with the object internal states. This work provides a new solution to overcome CO-OPN simulation limitations and a set of prototypes to assist dynamic systems simulations. Furthermore, this work has been conducted in a Risk Analysis (RA) context, a domain where computer-based simulations research are of utmost interest. Actually, classical approaches used to address complex workplace hazard in a limited way, using checklists or sequence models. Moreover, the use of single oriented methods, such as AEA (man-oriented), FMEA (machine oriented) or HAZOP (process oriented), is not satisfactory to overcome the increasing sophistication of industrial processes. The automation of a part of the analysis process as well as the multiple-oriented approach allowed by dynamic modeling may indeed enhance significantly the analysis completeness and reduce the time analyzing time. This work, based on Object Oriented Petri net formalism (CO-OPN), propose an alternative multi-oriented approach where existent methods limitations have been criticized to develop a dynamic model, MORM (Man-machine Occupational Risk Modeling). A real industrial system (metal wire making process) has been specified to implement the different approach steps (system identification, model application, system simulation, system analysis).

EPFL2005

Model Checking of Distributed Algorithm Implementations

Maysam Yabandeh

It is notoriously difficult to develop reliable, high-performance distributed systems that run over asynchronous networks. Even if a distributed system is based on a well-understood distributed algorithm, its implementation can contain errors arising from complexities of realistic distributed environments or simply coding errors. Many of these errors can only manifest after the system has been running for a long time, has developed a complex topology, and has experienced a particular sequence of low-probability events such as node resets. Model checking or systematic state space exploration, which has been used for testing of centralized systems, is also not effective for testing of distributed applications. The aim of these techniques is to exhaustively explore all the reachable states and verify some user-specified invariants on them. Although effective for small software systems, for more complex systems such as distributed systems the exponential increase in number of explored states, manifests itself as a problem at the very early stages of search. This phenomenon, which is also known as exponential state space explosion problem, prevents the model checker from reaching the potentially erroneous states at deeper levels, in a realistic time frame. This thesis proposes Dervish, a new approach in testing that makes use of a model checker in parallel with the running distributed system. Before the model checker performance gets hampered by the exponential explosion problem, the model checker restarts form the current live state of the system, instead of the initial state. The continuously running model checker at each node predicts the possible future inconsistencies, before they actually manifest. This approach, not only helps in testing by checking more relevant states that could occur in a real run, but also enables the application to steer the execution away from the predicted inconsistencies. We identified new bugs in mature Mace implementations of RandTree, Bullet', Paxos, and Chord distributed systems. Furthermore, we show that if the bug is not corrected during system development, Dervish is effective in steering the execution away from the inconsistent states at runtime. To be feasible in practice, the state exploration algorithm in Dervish should be efficient enough to explore some useful states in the period between each two restarts. Our default implementation of this approach benefits from a new search heuristic effective for distributed algorithms with short communications, termed consequence prediction, which selectively explores future event chains of the system. For consensus algorithms, however, which are known to be one of the most complex of distributed algorithms, the exploration algorithms built upon principles of model checking centralized systems are not scalable enough to be installed in Dervish. Those approaches reduce the problem of model checking distributed systems to that of centralized systems, by using the global state, which also includes the network state, as the model checking state. This thesis introduces LMC, a novel model checking algorithm designed specifically for distributed algorithms. The key insight in LMC is to treat the local nodes' states separately, instead of keeping track of the global states. We show how Dervish equipped with LMC enables us to find bugs in some complex consensus algorithms, including PaxosInside, the first consensus algorithm proposed and implemented for manycore environments. A modern manycore architecture can be viewed as a distributed system with explicit message passing to communicate between cores. Yet, doing this efficiently is very challenging given the non-uniform latency in inter-core communication and the unpredicted core response time. This thesis explores, for the first time, the feasibility of implementing a (non-blocking) consensus algorithm in a manycore system. We present PaxosInside, a new consensus algorithm that takes up the challenges of manycore environments, such as limited bandwidth of interconnect network as well as the consensus leader. A unique characteristic of PaxosInside is the use of a single acceptor role in steady state, which in our context, significantly reduces the number of exchanged messages between replicas.

EPFL2011