In this paper, we describe a general-purpose dialogue management framework used to design SOPHIE (Standardized Online Patient for Healthcare Interaction Education). SOPHIE simulates a virtual standardized cancer patient that allows physicians to practice skills such as empathy and patient empowerment in end-of-life communication. To provide the user with an opportunity to practice these skills, SOPHIE must produce a natural, emotionally appropriate conversation, yet handle topic shifts and open-ended questions from the user. To accomplish this, our approach to dialogue management loosely followsschemas– explicit representations of thetypicalflows of dialogue in end-of-life communication – while also using flexible pattern-driven methods for interpretation and generation. We conduct a crowdsourced evaluation of conversations between medical students and SOPHIE. Our agent is judged to produce responses that are natural, emotionally appropriate, and consistent with her role as a cancer patient. Furthermore, it significantly outperforms an end-to-end neural model fine-tuned on a human standardized patient corpus, attesting to the advantages of a schema-guided approach in this domain. However, the system is currently limited in its ability to generate responses that are judged to demonstrate deep understanding of the user, suggesting that future work should place focus on integrating this framework with robust natural language understanding and commonsense reasoning methods.

Effective communication between a clinician and their patient is critical for delivering healthcare maximizing outcomes. Unfortunately, traditional communication training approaches that use human standardized patients and expert coaches are difficult to scale. Here, we present the development and validation of a scalable, easily accessible, digital tool known as the Standardized Online Patient for Health Interaction Education (SOPHIE) for practicing and receiving feedback on doctor-patient communication skills. SOPHIE was validated by conducting an experiment with 30 medical professionals. We found that participants who underwent SOPHIE condition performed significantly better than the control in overall communication, aggregate scores, empowering the patient, and showing empathy (p < 0.05 in all cases). The results presented in this paper provide early evidence of scalable and accessible virtual humans, chatbot technologies, and automated feedback generation being transformative for medical communication training by supplementing existing resources.

Many practical applications of dialogue technology require the generation of responses according to a particular developer-specified persona.While a variety of personas can be elicited from recent large language models, the opaqueness and unpredictability of these models make it desirable to be able to specify personas in an explicit form.In previous work, personas have typically been represented as sets of one-off pieces of self-knowledge that are retrieved by the dialogue system for use in generation.However, in realistic human conversations, personas are often revealed through story-like narratives that involve rich habitual knowledge -knowledge about kinds of events that an agent often participates in (e.g., work activities, hobbies, sporting activities, favorite entertainments, etc.), including typical goals, subevents, preconditions, and postconditions of those events.We capture such habitual knowledge using an explicit schema representation, and propose an approach to dialogue generation that retrieves relevant schemas to condition a large language model to generate personabased responses.Furthermore, we demonstrate a method for bootstrapping the creation of such schemas by first generating generic passages from a set of simple facts, and then inducing schemas from the generated passages.

In this article, we describe the iterative participatory design of SOPHIE, an online virtual patient for feedback-based practice of sensitive patient-physician conversations, and discuss an initial qualitative evaluation of the system by professional end users. The design of SOPHIE was motivated from a computational linguistic analysis of the transcripts of 383 patient-physician conversations from an essential office visit of late stage cancer patients with their oncologists. We developed methods for the automatic detection of two behavioral paradigms, lecturing and positive language usage patterns (sentiment trajectory of conversation), that are shown to be significantly associated with patient prognosis understanding. These automated metrics associated with effective communication were incorporated into SOPHIE, and a pilot user study identified that SOPHIE was favorably reviewed by a user group of practicing physicians.

We present a conversational agent designed to provide realistic conversational practice to older adults at risk of isolation or social anxiety, and show the results of a content analysis on a corpus of data collected from experiments with elderly patients interacting with our system. The conversational agent, represented by a virtual avatar, is designed to hold multiple sessions of casual conversation with older adults. Throughout each interaction, the system analyzes the prosodic and nonverbal behavior of users and provides feedback to the user in the form of periodic comments and suggestions on how to improve. Our avatar is unique in its ability to hold natural dialogues on a wide range of everyday topics—27 topics in three groups, developed in collaboration with a team of gerontologists. The three groups vary in “degrees of intimacy,” and as such in degrees of cognitive difficulty for the user. After collecting data from nine participants who interacted with the avatar for seven to nine sessions over a period of 3 to 4 weeks, we present results concerning dialogue behavior and inferred sentiment of the users. Analysis of the dialogues reveals correlations such as greater elaborateness for more difficult topics, increasing elaborateness with successive sessions, stronger sentiments in topics concerned with life goals rather than routine activities, and stronger self-disclosure for more intimate topics. In addition to their intrinsic interest, these results also reflect positively on the sophistication and practical applicability of our dialogue system.

We present the design of an online social skills development interface for teenagers with autism spectrum disorder (ASD). The interface is intended to enable private conversation practice anywhere, anytime using a web-browser. Users converse informally with a virtual agent, receiving feedback on nonverbal cues in realtime, and summary feedback. The prototype was developed in consultation with an expert UX designer, two psychologists, and a pediatrician. Using the data from 47 individuals, feedback and dialogue generation were automated using a hidden Markov model and a schema-driven dialogue manager capable of handling multi-topic conversations. We conducted a study with nine high-functioning ASD teenagers. Through a thematic analysis of post-experiment interviews, identified several key design considerations, notably:

A physical blocks world, despite its relative simplicity, requires (in fully interactive form) a rich set of functional capabilities, ranging from vision to natural language understanding.In this work we tackle spatial question answering in a holistic way, using a vision system, speech input and output mediated by an animated avatar, a dialogue system that robustly interprets spatial queries, and a constraint solver that derives answers based on 3-D spatial modeling.The contributions of this work include a semantic parser that maps spatial questions into logical forms consistent with a general approach to meaning representation, a dialogue manager based on a schema representation, and a constraint solver for spatial questions that provides answers in agreement with human perception.These and other components are integrated into a multi-modal human-computer interaction pipeline.

In recent years, there has been renewed interest in the NLP community in genuine language understanding and dialogue. Thus the long-standing issue of how the semantic content of language should be represented is reentering the communal discussion. This paper provides a brief "opinionated survey" of broad-coverage semantic representation (SR). It suggests multiple desiderata for such representations, and then outlines more than a dozen approaches to SR — some long-standing, and some more recent, providing quick characterizations, pros, cons, and some comments on implementations.

We present a flexible initial framework for defining self‐motivated, self‐aware agents in simulated worlds, planning continuously so as to maximize long‐term rewards. While such agents employ reasoned exploration of feasible sequences of actions and corresponding states, they also behave opportunistically and recover from failure, thanks to their continual plan updates and quest for rewards. Our framework allows for both specific and general (quantified) knowledge and for epistemic predicates such as knowing‐that and knowing‐whether. Because realistic agents have only partial knowledge of their world, the reasoning of the proposed agents uses a weakened closed‐world assumption; this has consequences for epistemic reasoning, in particular introspection. The planning operators allow for quantitative, gradual change and side effects such as the passage of time, changes in distances and rewards, and language production, using a uniform procedural attachment method. Question answering (involving introspection) and experimental runs are shown for our particular agentMEin a simple world, demonstrating the value of continual deliberate, reward‐driven planning. Though the primary merit of agents definable in our framework is that they combine all of the aforementioned features, they can also be configured as single or multiple goal‐seeking agents and as such perform comparably with some recent experimental agents.

Fifth International Conference on Knowledge Capture (K-CAP 2009)

This paper presents a grammatical and processing framework for handling the repairs, hesitations, and other interruptions in natural human dialog.The proposed framework has proved adequate for a collection of human-human task-oriented dialogs, both in a full manual examination of the corpus, and in tests with a parser capable of parsing some of that corpus.This parser can also correct a pre-parser speech repair identifier resulting in a 4.8% increase in recall.

We propose some domain-independent techniques for bringing well-founded partial-order planners closer to practicality. The first two techniques are aimed at improving search control while keeping overhead costs low. One is based on a simple adjustment to the default A* heuristic used by UCPOP to select plans for refinement. The other is based on preferring ``zero commitment'' (forced) plan refinements whenever possible, and using LIFO prioritization otherwise. A more radical technique is the use of operator parameter domains to prune search. These domains are initially computed from the definitions of the operators and the initial and goal conditions, using a polynomial-time algorithm that propagates sets of constants through the operator graph, starting in the initial conditions. During planning, parameter domains can be used to prune nonviable operator instances and to remove spurious clobbering threats. In experiments based on modifications of UCPOP, our improved plan and goal selection strategies gave speedups by factors ranging from 5 to more than 1000 for a variety of problems that are nontrivial for the unmodified version. Crucially, the hardest problems gave the greatest improvements. The pruning technique based on parameter domains often gave speedups by an order of magnitude or more for difficult problems, both with the default UCPOP search strategy and with our improved strategy. The Lisp code for our techniques and for the test problems is provided in on-line appendices.

Describes some simple domain-independent improvements to plan refinement strategies for well-founded partial order planning that promise to bring this style of planning closer to practicality. One suggestion concerns the strategy for selecting plans for refinement among the current (incomplete) candidate plans. We propose an A* heuristic that counts only steps and open conditions, while ignoring "unsafe conditions" (threats). A second suggestion concerns the strategy for selecting open conditions (goals) to be established next in a selected incomplete plan. We propose a variant of a strategy suggested by Peot and Smith (1993) and studied by Joslin and Pollack (1994); the variant gives top priority to unmatchable open conditions (enabling the elimination of the plan), second-highest priority to goals that can only be achieved uniquely and otherwise uses LIFO (last-in, first-out) prioritization. The preference for uniquely achievable goals is a "zero-commitment" strategy in the sense that the corresponding plan refinements are a matter of deductive certainty, involving no guesswork. In experiments based on modifications of UCPOP (Unsafe Conditions Partial Order Planner), we have obtained improvements by factors ranging from 5 to more than 600 for a variety of problems that are nontrivial for the unmodified version. Crucially, the hardest problems give the greatest improvements.

Reasoning about temporal information is an important task in many areas of Artificial Intelligence. In this paper we address the problem of scalability in temporal reasoning by providing a collection of new algorithms for efficiently managing large sets of qualitative temporal relations. We focus on the class of relations forming the Point Algebra (PA-relations) and on a major extension to include binary disjunctions of PA-relations (PA-disjunctions). Such disjunctions add a great deal of expressive power, including the ability to stipulate disjointness of temporal intervals, which is important in planning applications. Our representation of time is based on timegraphs, graphs partitioned into a set of chains on which the search is supported by a metagraph data structure. The approach is an extension of the time representation proposed by Schubert, Taugher and Miller in the context of story comprehension. The algorithms herein enable construction of a timegraph from a given set of PA-relations, querying a timegraph, and efficiently checking the consistency of a timegraph augmented by a set of PA-disjunctions. Experimental results illustrate the efficiency of the proposed approach.

We analyze the problem of computing the minimal labels for a network of temporal relations in point algebra. Van Beek proposes an algorithm for accomplishing this task, which takes O(max(n3, n2 m)) time (for n points and m ≠‐relations). We show that the proof of the correctness of this algorithm given by van Beek and Cohen is faulty, and we provide a new proof showing that the algorithm is indeed correct.

The TRAINS project is an effort to build a conversationally proficient planning assistant. A key part of the project is the construction of the TRAINS system, which provides the research platform for a wide range of issues in natural language understanding, mixed-initiative planning systems, and representing and reasoning about time, actions and events. Four years have now passed since the beginning of the project. Each year a demonstration system has been produced that focused on a dialogue that illustrates particular aspects of the research. The commitment to building complete integrated systems is a significant overhead on the research, but it is considered essential to guarantee that the results constitute real progress in the field. This paper describes the goals of the project, and the experience with the effort so far.

We describe two domain-independent temporal reasoning systems called TimeGraph I and II which can be used in AI-applications as tools for efficiently managing large sets of relations in the Point Algebra, in the Interval Algebra, and metric information such as absolute times and durations. Our representation of time is based on timegraphs, graphs partitioned into a set of chains on which the search is supported by a metagraph data structure. TimeGraph I was originally developed by Taugher, Schubert and Miller (1990) in the context of story comprehension. TimeGraph II provides useful extensions, including efficient algorithms for handing inequations, and relations expressing point-interval exclusion and interval disjointness. These extensions make the system much more expressive in the representation of qualitative information and suitable for a large class of applications.>

Explanation closure (EC) axioms were previously introduced as a means of solving the frame problem. This paper provides a thorough demonstration of the power of EC combined with action closure (AC) for reasoning about dynamic worlds, by way of Sandewall's test suite of 12-or-so problems. Sandewall's problems range from the ‘Yale turkey shoot’ (and variants) to the ‘stuffy room’ problem, and are intended as a test and challenge for non-monotonic logics of action. The EC/AC-based solutions for the most part do not resort to non-monotonic reasoning at all, yet yield the intuitively warranted inferences in a direct, transparent fashion. While there are good reasons for ultimately employing non-monotonic or probabilistic logics—e.g. pervasive uncertainty and the qualification problem—this does show that the scope of monotonic methods has been underestimated. Subsidiary purposes of the paper are to clarify the intuitive status of EC axioms in relation to action effect axioms; and to show how EC, previously formulated within the situation calculus, can be applied within the framework of a temporal logic similar to Sandewall's ‘discrete fluent logic’, with some gains in clarity.

We present a new compositional tense-aspect deindexing mechanism that makes use of tense trees as components of discourse contexts. The mechanism allows reference episodes to be correctly identified even for embedded clauses and for discourse that involves shifts in temporal perspective, and permits deindexed logical forms to be automatically computed with a small number of deindexing rules.

Temporal reasoning is essential for many artificial intelligence applications. To date, most research has concentrated on temporal inference in isolation without considering the role it can play in a more general reasoning environment. This paper takes an efficient temporal reasoner and extends its inferential capabilities to handle both strict and nonstrict relations. The resulting temporal specialist is incorporated into a system intended for low‐level reasoning in natural language understanding. The specialist assists the resolution‐based theorem prover in function evaluation, literal evaluation, and generalized resolving and factoring. The combined system can do some proofs in just a few steps that would normally require many. An example from the fully operational hybrid system is included. Le raisonnement temporel est essentiel dans de nombreuses applications relatives àľ intelligence artificielle. Jusqu’à présent, la plupart des travaux de recherche ont porté sur ľ inférence temporelle dans ľ isolation sans tenir compte du rǒle qu'elle peut jouer dans un environnement de raisonnement plus général. Cet article traite ? un raisonneur temporel ef ficace dont les capacityés inférentielles ont été augmentée afin de pouvoir traiter les relations strides et non strides. Le spécialiste temporel qui en résulte est intégréà un système conçu pour le raisonnement bas‐niveau en langage naturel. Le spécialiste assiste le démonstratur de théorèmes basé sur la résolution dans ľévaluation des fonctions, ľévaluation littérale et la fonction fadorielle généralisée. Le système combine peut vérifier des preuves en quelques étapes seulement au lieu ? un grand nombre. Un exemple ? un système hybride entièrement opérationnel est fourni. Mots clés: raisonnement temporel, methodes ? inférence spéciales, résolution de théories, représentation des connaissances.

In this paper, we first define a new Voronoi diagram for the endpoints of a set of line segments in the plane which do not intersect (except possibly at their endpoints), which is called a bounded Voronoi diagram. In this Voronoi diagram, the line segments themselves are regarded as obstacles. We present an optimal Θ(n log n) algorithm to construct it, where n is the number of input line segments.

There are various difficulties in accomodating the traditional mass/count distinction into a grammar for English which has a goal the production of "logical form" semantic translations of the initial English sentences. The present paper surveys some of these difficulties. One puzzle is whether the distinction is a syntactic one or a semantic one, i.e., whether it is a well-formedness constraint or whether it is a description of the semantic translations produced. Another puzzle is whether it should be applied to simple words (as they occur in the lexicon) or whether it should apply only to longer units (such as entire NPs). Of the wide variety of possible theories, only two seem to produce the required results (having to do with plausible inferences and intuitively satisfying semantic representations). These two theories are developed and compared.

It is argued that syntactic preference principles such as Right Association and Minimal Attachment are unsatisfactory as usually formulated. Among the difficulties are: (1) dependence on ill-specified or implausible principles of parser operation; (2) dependence on questionable assumptions about syntax; (3) lack of provision, even in principle, for integration with semantic and pragmatic preference principles; and (4) apparent counterexamples, even when discounting (1)--(3). A possible approach to a solution is sketched.

The general problem of finding minimal programs realizing given “program descriptions” is considered, where program descriptions may be of finite or infinite length and may specify arbitrary program properties. The problem of finding minimal programs consistent with finite or infinite input-output lists is a special case (for infinite input-output lists, this is a variant of E. M. Gold's function identification problem). Although most program minimization problems are not recursively solvable, they are found to be no more difficult than the problem of deciding whether any given program realizes any given description, or the problem of enumerating programs in order of nondecreasing length (whichever is harder). This result is formulated in terms of k -limiting recursive predicates and functionals, defined by repeated application of Gold's limit operator. A simple consequence is that the program minimization problem is limiting recursively solvable for finite input-output lists and 2-limiting recursively solvable for infinite input-output lists, with weak assumptions about the measure of program size. Gold regarded limiting function identification (more generally, “black box” identification) as a model of inductive thought. Intuitively, iterated limiting identification might be regarded as higher-order inductive inference performed collectively by an ever-growing community of lower order inductive inference machines.