User modelling in interactive explanations

In this paper I consider how user modelling can be used to improve the provision of complex explanations, and discuss in detail the user modelling component of the EDGE explanation system. This allows a user model to be both updated and used in an explanatory dialogue with the user. The model is updated based on the interactions with the user, relationships between concepts and a reviseable expertise level. The model in turn influences the planning of the explanation, allowing a more understandable explanation to be generated. I argue that both user modelling and an interactive style of presentation are important for explanations to be acceptable and understandable, and that each reinforces the other.     

New approaches for understanding the asymptotic complexity of A* tree searching

Previous studies of A^* tree-searching have modeled heuristics as random variables. The average number of nodes expanded is expressed asymptotically in terms of distance to goal. The conclusion reached is that A^* complexity is an exponential function of heuristic error: Polynomial error implies exponential complexity and logarithmic accuracy is required for polynomial complexity.This paper eliminates simplifying assumptions of earlier studies. Error is replaced by a concept called discrepancy, a measure of the relative attractiveness to A^* of a node for expansion when that node is compared with competing nodes on the solution path. According to our model, in order to have polynomial A^* complexity, it is not necessary to have the logarithmic accuracy described in previous studies. Another way is for a heuristic's values to vary, or cluster, near a central function which grows at least as fast as distance to goal. Generally, logarithmic variation or less is adequate. For one class of heuristics considered, the faster this central function grows, the more is variation from it tolerated.This research has been funded by NCR Corporation.This research has been partially funded by a grant from NCR Corporation.     

Optimal component-insertion sequenceplanning methodology for the semiautomatic assembly of printed circuit boards

One of the primary concerns in the manufacturing of printed circuit boards (PCBs) is the definition of optimum component-insertion sequences for manual and automated operations. The problem is dynamic and multiple feasible solutions can be found. The research work described in this paper has developed a component-insertion sequencing methodology and a proof-of-concept expert system for printed circuit boards. This system solves the component-insertion sequencing problem for semi-automated work cells which utilize a light guiding system to identify for the operator where to assemble the next component. The innovation of the methodology is the application of Artificial Intelligence and Expert Systems techniques to represent the human reasoning involved in semi-automated PCB assembly planning. Based on established assembly criteria, sequencing decision rules and data available from a CAD system, the methodology leads to optimum component-insertion sequences.     

Sarcasm,Deception, and Stating the Obvious: Planning Dialogue without Speech Acts

This paper presents an alternative to the speech acts with STRIPS approach to implementing dialogue a fully implemented AI planner which generates and analyses the semantics of utterances using a single linguistic act for all contexts. Using this act, the planner can model problematic conversational situations, including felicitous and infelicitous instances of bluffing, lying, sarcasm, and stating the obvious. The act has negligible effects, and its precondition can always be proved. Speaker maxims enable the speaker to plan to deceive, as well as to generate implicatures, while hearer maxims enable the hearer to recognise deceptions, and interpret implicatures. The planner proceeds by achieving parts of the constructive proof of a goal. It incorporates an epistemic theorem prover, which embodies a deduction model of belief, and a constructive logic.     

User-Tailored Planning of Mixed Initiative Information-Seeking Dialogues

Intelligent dialogue systems usually concentrate on user support at the level of the domain of discourse, following a plan-based approach. Whereas this is appropriate for collaborative planning tasks, the situation in interactive information retrieval systems is quite different: there is no inherent plan-goal hierarchy, and users are known to often opportunistically change their goals and strategies during and through interaction. We need to allow for mixed-initiative retrieval dialogues, where the system evaluates the user's individual dialogue behavior and performs situation-dependent interpretation of user goals, to determine when to take the initiative and to change the control of the dialogue, e.g., to propose (new) problem-solving strategies to the user. In this article, we present the dialogue planning component of a concept- oriented, logic-based retrieval system (MIRACLE). Users are guided through the global stages of the retrieval interaction but may depart, at any time, from this guidance and change the direction of the dialogue. When users submit ambiguous queries or enter unexpected dialogue control acts, abductive reasoning is used to generate interpretations of these user inputs in light of the dialogue history and other internal knowledge sources. Based on these interpretations, the system initiates a short dialogue offering the user suitable options and strategies for proceeding with the retrieval dialogue. Depending on the user's choice and constraints resulting from the history, the system adapts its strategy accordingly.     

Planning as Propositional CSP: From Walksat to Local Search Techniques for Action Graphs

Graphplan-style of planning can be formulated as an incremental propositional CSP where the (boolean) variables correspond to operator instantiations (actions) that are or are not scheduled at certain time steps. In this paper we present a framework for solving this class of propositional CSPs using local search in planning graphs. The search space consists of particular subgraphs of a planning graph corresponding to (complete) variable assignments, and representing partial plans. The operators for moving from one search state to the next one are graph modifications corresponding to revisions of the current variable assignment (partial plan), or to an extension of the represented CSP.Our techniques are implemented in a planner called LPG using various types of heuristics based on a parametrized objective function, where the parameters weight different constraint violations, and are dynamically evaluated using Lagrange multipliers. LPG's basic heuristic was inspired by Walksat, which in Kautz and Selman's Blackbox can be used to solve the SAT-encoding of a planning graph. An advantage of LPG is that its heuristics exploit the structure of the planning graph, while Blackbox relies on general heuristics for SAT-problems, and requires the translation of the planning graph into propositional clauses. Another major difference is that LPG can handle action execution costs to produce good quality plans. This is achieved by an anytime process minimizing an objective function based on the number of constraint violations in a plan and on its overall cost. Experimental results illustrate the efficiency of our approach, showing, in particular, that LPG is significantly faster than Blackbox and other planners based on planning graphs.     

μ C/OS-II在车桥总成配置数据管理系统终端中的应用

基于Cortex-M3内核的ARM芯片STM32F107构建的车桥总成数据远程传输终端,包括了CAN通信、串口通信、人机接口、状态指示、电源等单元。CAN驱动芯片MCP2551实现CAN通信驱动,PS2键盘用于数据的录入与修改,LCM屏提供了人机接口对话。软件上嵌入μC/OS-II实时操作系统,建立CAN总线通信、串口通信、人机接口等多任务。实验表明,车桥总成配置数据的录入与修改操作简便,人机对话界面友好,CAN总线数据传输实时准确。     

A knowledge-based inspection process planning system for coordinate measuring machines

The coordinate measuring machine (CMM) is one of the most effective geometry inspection facilities used in manufacturing industry. To fully utilize its capabilities in a computer-integrated manufacturing (CIM) environment, we should integrate CMM with other systems and facilities. This paper presents the development of a knowledge-based inspection planner based on the fundamental principles of AI planning to integrate computer-aided design systems and CMMs. The issues involved in CAD-directed inspection process planning are examined; the task of inspection process planning is decomposed into a number of sub-tasks. According to the task decomposition, a knowledge-based planning system was designed with several modules. Each of these modules consists of a knowledge base, a control operator, a context and a communication interface. The knowledge base is the local knowledge source for problem solving; the control operator determines when and where the knowledge is applied; the context contains the initial planning state which is essential input part information, the intermediate planning states which result from the tentative decision made by the modules, and the goal state. The module interfacing was realized by directly calling procedures defined in other modules to pass the planning tasks and decisions. Examples are included to explain the planning knowledge and strategy.     

Script visualization (ScriptViz): a smart system that makes writing fun

We have built the first version of ScriptViz v.1.0 that allows users to visualize their screenplays in real time via animated graphics. Our system consists of a text understanding module, a high-level planning module and a scene generator. The user can input a screenplay as a set of well-formed english sentences via a graphic user interface. The text understanding module interprets the input sentences and triggers the high-level planner to construct a plan of actions for the appropriate agents. Then the agents execute the plans, and the scene generator renders the scene as the story evolves. Our system provides the user with a powerful tool to visualize his screenplays (stories) in the form of computer graphics, which makes writing story fun for students as well as for screenplay writers.

Constructing and Utilizing a Model of User Preferences in Collaborative Consultation Dialogues

A natural language collaborative consultation system must take user preferences into account. A model of user preferences allows a system to appropriately evaluate alternatives using criteria of importance to the user. Additionally, decision research suggests both that an accurate model of user preferences could enable the system to improve a user's decision-making by ensuring that all important alternatives are considered, and that such a model of user preferences must be built dynamically by observing the user's actions during the decision-making process. This paper presents two strategies: one for dynamically recognizing user preferences during the course of a collaborative planning dialogue and the other for exploiting the model of user preferences to detect suboptimal solutions and suggest better alternatives. Our recognition strategy utilizes not only the utterances themselves but also characteristics of the dialogue in developing a model of user preferences. Our generation strategy takes into account both the strength of a preference and the closeness of a potential match in evaluating actions in the user's plan and suggesting better alternatives. By modeling and utilizing user preferences, our system is able to fulfill its role as a collaborative agent.     

CAMPS: a constraint-based architecturefor multiagent planning and scheduling

A new integrated architecture for distributed planning and scheduling is proposed that exploits constraints for problem decomposition and coordination. The goal is to develop an efficient method to solve densely constrained planning/scheduling problems in a distributed manner without sacrificing solution quality. A prototype system (CAMPS) was implemented, in which a set of intelligent agents try to coordinate their actions for satisfying planning/scheduling results by handling several intra- and inter-agent constraints. The repair-based methodology for distributed planning/scheduling is described, together with the constraint-based mechanism of dynamic coalition formation among agents.     

Seamless User-Level Handoff in Ubiquitous Multimedia Service Delivery

Advancing mobile computing technologies are enabling ubiquitous personal computing environment. In this paper, we focus on an important problem in such environment: user mobility. In the case of user mobility, a user is free to access his/her personalized service at anytime, anywhere, through any possible mobile/fixed devices. Providing mobility support in this scenario poses a series of challenges. The most essential problem is to preserve the user's access to the same service despite changes of the accessing host or service provider. Existing system-level mobility solutions are insufficient to address this issue since it is not aware of the application semantics. On the other hand, making each application to be mobility-aware will greatly increase the development overhead. We argue that the middleware layer is the best place to address this problem. On one hand, it is aware of application semantics. On the other hand, by building application-neutral mobility functions in the middleware layer, we eliminate the need to make each application mobility-aware. In this paper, we design a middleware framework to support user mobility in the ubiquitous computing environment. Its major mobility functions include user-level handoff management and service instantiation across heterogeneous computing platforms. We validate the major mobility functions using our prototype middleware system, and test them on two multimedia applications (Mobile Video Player and Mobile Audio Player). To maximally approximate the real-world user-mobility scenario, we have conducted experiments on a variety of computing platforms and communication paradigms, ranging from T1-connected high-end PC to handheld devices with wireless networks. The results show that our middleware framework is able to provide efficient user mobility support in the heterogeneous computing environment.     

Decentralized Motion Planning for Multiple Mobile Robots: The Cocktail Party Model

This paper presents an approach for decentralized real-time motion planning for multiple mobile robots operating in a common 2-dimensional environment with unknown stationary obstacles. In our model, a robot can see (sense) the surrounding objects. It knows its current and its target's position, is able to distinguish a robot from an obstacle, and can assess the instantaneous motion of another robot. Other than this, a robot has no knowledge about the scene or of the paths and objectives of other robots. There is no mutual communication among the robots; no constraints are imposed on the paths or shapes of robots and obstacles. Each robot plans its path toward its target dynamically, based on its current position and the sensory feedback; only the translation component is considered for the planning purposes. With this model, it is clear that no provable motion planning strategy can be designed (a simple example with a dead-lock is discussed); this naturally points to heuristic algorithms. The suggested strategy is based on maze-searching techniques. Computer simulation results are provided that demonstrate good performance and a remarkable robustness of the algorithm (meaning by this a virtual impossibility to create a dead-lock in a random scene).     

Shaping user input: a strategy for natural language dialogue design

Traditional approaches to natural language dialogue interface design have adopted ordinary human-human conversation as the model for online human-computer interaction. The attempt to deal with all the subtleties of natural dialogues, such as topic focus, coherence, ellipsis, pronominal reference, etc. has resulted in prototype systems that are enormously complex and computationally expensive.

In a series of experiments^†, we explored ways of minimizing the processing burden of a dialogue system by channeling user input towards a more tractable, though still natural, form of Englishlanguage questions. Through linking a pair of terminals, we presented subjects with two different dialogue styles as a framework for online help in the domain of word-processing. The first dialogue style involved ordinary conversational format. The second style involved a simulation of an automated dialogue system, including apparent processing restrictions and ‘system process messages’ to inform the subject of the steps taken by the system during query analysis. In both cases human tutors played the role of the help system. After each dialogue session, subjects were interviewed to determine their assessments of the naturalness and usability of the dialogue interface.

We found that user input became more tractable to parsing and query analysis as the dialogue style became more formalized, yet the subjective assessment of naturalness and usability remained fairly constant. This suggests that techniques for channeling user input in a dialogue system may be effectively employed to reduce processing demands without compromising the benefits of a natural language interface. Theoretically, this data lends support to the hypothesis that unrestricted human-human conversation is not the most appropriate model for the design of human-computer dialogue interfaces.     

Exploiting user feedback to compensate for the unreliability of user models

Natural Language is a powerful medium for interacting with users, and sophisticated computer systems using natural language are becoming more prevalent. Just as human speakers show an essential, inbuilt responsiveness to their hearers, computer systems must tailor their utterances to users. Recognizing this, researchers devised user models and strategies for exploiting them in order to enable systems to produce the best answer for a particular user.Because these efforts were largely devoted to investigating how a user model could be exploited to produce better responses, systems employing them typically assumed that a detailed and correct model of the user was available a priori, and that the information needed to generate appropriate responses was included in that model. However, in practice, the completeness and accuracy of a user model cannot be guaranteed. Thus, unless systems can compensate for incorrect or incomplete user models, the impracticality of building user models will prevent much of the work on tailoring from being successfully applied in real systems. In this paper, we argue that one way for a system to compensate for an unreliable user model is to be able to react to feedback from users about the suitability of the texts it produces. We also discuss how such a capability can actually alleviate some of the burden now placed on user modeling. Finally, we present a text generation system that employs whatever information is available in its user model in an attempt to produce satisfactory texts, but is also capable of responding to the user's follow-up questions about the texts it produces.Dr. Johanna D. Moore holds interdisciplinary appointments as an Assistant Professor of Computer Science and as a Research Scientist at the Learning Research and Development Center at the University of Pittsburgh. Her research interests include natural language generation, discourse, expert system explanation, human-computer interaction, user modeling, intelligent tutoring systems, and knowledge representation. She received her MS and PhD in Computer Science from the University of California at Los Angeles, and her BS in Mathematics and Computer Science from the University of California at Los Angeles. She is a member of the Cognitive Science Society, ACL, AAAI, ACM, IEEE, and Phi Beta Kappa. Readers can reach Dr. Moore at the Department of Computer Science, University of Pittsburgh, Pittsburgh, PA 15260.Dr. Cecile Paris is the project leader of the Explainable Expert System project at USC's information Sciences Institute. She received her PhD and MS in Computer Science from Columbia University (New York) and her bachelor's degree from the University of California in Berkeley. Her research interests include natural language generation and user modeling, discourse, expert system explanation, human-computer interaction, intelligent tutoring systems, machine learning, and knowledge acquisition. At Columbia University, she developed a natural language generation system capable of producing multi-sentential texts tailored to the users level of expertise about the domain. At ISI, she has been involved in designing a flexible explanation facility that supports dialogue for an expert system shell. Dr. Paris is a member of the Association for Computational Linguistics (ACL), the American Association for Artificial Intelligence (AAAI), the Cognitive Science Society, ACM, IEEE, and Phi Kappa Phi. Readers can reach Dr. Paris at USC/ISI, 4676 Admiralty Way, Marina Del Rey, California, 90292     

Software ergonomics: effects of computer application design parameters on operator task performance and health

Abstract

Evidence is reviewed that the operating characteristics of computer application systems, in addition to physical characteristics of display units (CRTs), are the cause of many observed effects on operator health and task effectiveness. These effects are hypothesized to occur through changes in task structure, and the man-machine redivision of labour that results when computer application systems are introduced into work setting. First, the association between task dimensions and models of operator performance effectiveness and well-being are reviewed. Second, application system design parameters that affect task structure are identified. Then, empirical evidence supporting this three-part causal linkage—application system parameters to task characteristics to operator effectiveness and health—is presented. The findings suggest that by improving dialogue quality, taking advantage of two-way communication to reduce uncertainty, using smaller and less integrated systems and matching system performance to operator needs a job can be created that is likely to improve both operator well-being and effectiveness.