The AI/NL/KR group at Rochester is attempting to (a) understand intelligent thought, planning, and communication, and (b) build computer systems that think, behave, and communicate intelligently. Our research along these lines spans the history of Artificial Intelligence, from core issues in knowledge representation, planning, and search, through natural language understanding and uncertain inference, to cutting-edge research in areas such as speech recognition, multi-modal interaction, data mining, machine learning, and assistive technologies.

We are not really a single group with a unified purpose. Rather, we are pursuing a wide variety of problems individually, as a group, with other members of the Computer Science Department, and in collaborations with other departments at Rochester and beyond. We have strong connections to the Linguistics, Philosophy, and Brain and Cognitive Sciences Departments, as well as an active role in the University's Center for Language Sciences. We see intelligence as fundamentally multi-faceted, and therefore pursue connections to related research as often as we can.

Current Research in the AI/NL/KR Group

• Intelligent Collaborative Agents: We are combining natural language understanding and dialogue management with AI planning and scheduling technology to create intelligent planning assistants. The goal is to make the system's interaction with the user as intuitive as possible by treating it as a dialogue between the participants, each of whom bring different skills and objectives to the table. TRIPS, The Rochester Interactive Planning System, is an end-to-end prototype of such a system in a logistics domain.
• Spoken Language Systems: We are studying the use of speech as a primary modality for human-computer interaction. One of the foci of this work has been the need for robustness in the light of phenomena such as speech recognition errors, casual speech, speech repairs, interruptions, and so on, that do not occur in written language.
• Machine Translation: Current work focuses on adding syntactic knowledge to statistical systems for translating text from one language to another, modeling systematic differences in the grammar of the two languages.
• Language Modelling: We are using probabilistic methods for modelling natural languages, in particular to support automatic speech recognition and understanding. We are working on models that attempt to exploit the deeper structure of language rather than simply relying on n-gram models of context. Also, we are interested in language model adaptation to new domains, and optimizing the use of training data.
• Multi-modal Interaction: In addition to speech, we are studying the use of multiple modalities to improve the effectiveness of human-computer interaction. This work includes such things as coordinated graphical and spoken display, use of multiple display surfaces, gestural and visual input, and dynamic use of different modalities as the user's environment changes (for example, if they move around). We are also extending the discourse framework from two-party to multi-party interactions.
• Expressive, Language-like Logics: We wish to capture the content of ordinary language and commonsense reasoning as directly as possible. The most recent such logic is called Episodic Logic, and is implemented in the EPILOG system, which has been used to make complex inferences about fairy tale fragments, aircraft maintenance reports, and other domains.
• Natural Language Semantics: For events/situations, tense/aspect, reference, affixes, mass terms, generic sentences, belief, questions, vagueness, etc. Our recent and current work is concerned not only with formal theories of these phenomena, but also with ways of extracting semantic information automatically from large text corpora.
• Computational Models of Belief: We are developing a formal computational model of belief, one that meets traditional philosophical requirements and can also serve in practical reasoning about beliefs by ``simulative inference,'' i.e., inference about another agent's beliefs by introspection about the conclusions one would draw if one held the other agent's beliefs.
• Efficient, specialized inference techniques: For taxonomies, part-structure, temporal relations, and other classes of relations that pervade commonsense knowledge and are handled effortlessly by people.
• Natural Language Parsing: The emphasis is on human-like, error-tolerant strategies for parsing and disambiguation, and for mapping syntactic structure to a representation of the underlying meaning (allowing for context).
• Reasoning About Plans and Actions: This work supports both language understanding (e.g., conversation planning and inferring the goals and plans of story characters) and domain reasoning (e.g., formulating transportation plans in the TRAINS/TRIPS domains). We are pursuing several approaches to this problem. First, we are developing planning formalisms and algorithms based on Interval Temporal Logic to represent and reason about complex plans in realistic domains. Second, we are pursuing the use of ``Explanation Closure'' as an intuitive and effective solution to the Frame Problem. Finally, we are also developing ways of speeding up recent domain-independent planning algorithms (based on regression, plan graphs, satisfiability testing, etc.), for instance by better search control or by automatic inference of state constraints that can be used to limit search.
• Task-Oriented Discourse: An emphasis in this work is, first, the representation and use of the context of the dialogue to solve problems in semantic interpretations and, second, the recognition of the intentions underlying the speakers' utterances. Work in this area has included the development of the first computational model of speech acts, the development of a multi-level plan-based analysis involving discourse-level plans as well as domain-level plans, and the development of several different discourse-plan recognition algorithms that can support complex reasoning about plans and actions.
• Context Management for Dialogue Systems: We are developing a model of discourse context management for use by dialogue systems. A key issue here is keeping track of objects that have been mentioned in the dialogue and what has been said about them. We are investigating how to adapt existing knowledge-poor models, such as centering, to dialogue, as well as developing our own knowledge-rich model. This research is being used to make the TRIPS system understand a wider range of referential expressions from the user and to make its own utterances more natural and coherent.
• Pronominal Reference Corpus: This is a data collection effort to develop a corpus of discourses in which the antecedents of pronouns have been annotated. Despite the crucial role of pronominalization in language, there is very little such data within the scientific community. The data is being drawn from task-oriented dialogues, radio news stories, and fictional stories and annotated by members of the group. The results will be used for evaluating pronoun resolution algorithms and as training data for new statistical or learning-based algorithms.
• Philosophical Foundations of Uncertain Inference: Many of the same questions (and many of the same answers) are raised (and given) in philosophy and artificial intelligence. To provide philosophically satisfying answers is also to provide answers that are also practically useful, and that can enlighten scientific disputes about evidential support. This research has lately moved in two directions: toward the relation between inductive or statistical or probabilistic support, and the tentative support provided by nonmonotonic logics; and, since there is tension between statistical support and deductive closure, toward the paraconsistent logics that allow sensible inferences from ``inconsistent'' databases.
• Uncertain Inference Using Reference Classes: This line of research aims at extending evidential probability in a number of directions. In cases where the selection principles are inadequate, we need to revise the principles and/or provide new ones that are more suited to the task of identifying the most appropriate reference class, thus enabling us to establish a well founded theory of probability based on statistical knowledge. We also seek to identify restricted parts of the theory that admit tractable computation yet are expressive enough for use in practical applications.
• Prototype Framework for Various Formalisms: We are working on constructing a prototype framework in which we can characterize both the generic uncertain reasoning process and a wide spectrum of specific formalisms. This provides a common platform on which we can translate the various pieces of information, originally encoded using different formalisms, into a knowledge base with a standard syntax and semantics. This step ensures that different portions of the combined knowledge base are treated uniformly, and that they are allowed to interact in a well understood manner. We are then able to evaluate the behaviors and results of the combined system against a clearly defined semantics.
• Intelligent Datamining: A relatively recent area of research involves mining large datasets for patterns of information and reasoning about the causes and effects of the discovered patterns. For example, we are looking at using fast simulators to provide large numbers of execution traces of a plan, from which likely errors and their causes can be extracted and used to improve the plan before it is executed. A central issue here is dealing with the fact that large databases are practically always inconsistent. Work on intelligent datamining is being undertaken by a group involving Systems and Theory faculty as well as members of the AI/NL/KR group.

Faculty in the AI/NL/KR Group

• James Allen: James' research interests span a range of issues covering natural language understanding, discourse, knowledge representation, common-sense reasoning, and planning. He has joint appointments in the Brain and Cognitive Sciences and Linguistics departments, holds the Dessauer Chair in Computer Science, and is a Fellow of the AAAI. He is the author of the definitive graduate-level textbook Natural Language Understanding, 2nd ed. (Benjamin Cummings, 1994).
• George Ferguson: George is a Research Scientist in the department. His interests are in the development and application of AI, NL, and KR techniques in the construction of intelligent, collaborative computer systems. This includes applying or extending existing theories, such as for temporal reasoning or planning, to new problems, developing and implementing new theories where traditional ones break down, and creating frameworks in which such ``systems of systems'' can come together to support intelligent behaviour. George is the principal architect of TRIPS, The Rochester Interactive Planning System, and is the founding chair of the Intelligent Systems Demonstrations Program at AAAI.
• Daniel Gildea: Dan is interested in statistical approaches to natural language processing, in particular language understanding and machine translation. He has also worked on language and pronunciation modeling for speech recognition and computational approaches to phonology.
• Henry Kautz: Henry's research is concerned with fundamental questions of efficiency and scalability of knowledge representation and reasoning systems. Examples include using new randomized algorithms to solve logical representations of planning problems, and using machine learning techniques to optimize the performance of solvers on distributions of problem instances. Other work includes investigating the formal complexity of clause-learning system, and exploring the connections between work in AI on logic and search and work in verification. A major new initiative called Assisted Cognition aims to create computer systems to help people suffering from cognitive disorders, such as the effects of Alzheimer's disease. This involves fundamental and applied research ranging over topics such probabilistic reasoning, plan recognition, ubiquitous computing, data fusion, user interfaces, and cognitive psychology.
• Lenhart Schubert: Len's research interests center around language, knowledge representation, inference and planning. These interests are tied together by the general goal of developing agents with common sense and the ability to converse and acquire knowledge through language. Len is a Professor of Computer Science, a former member of the editorial boards of the Journal of AI Research and Computational Intelligence, past chair of several AI conferences, and a Fellow of the AAAI.

Recent Graduates of the AI/NL/KR Group

• Hao Zhang, Handling Complexity of Synchronous Grammars, 2008.
• Ellen Campana, Natural versus Standardized Approaches to Spoken System Design: A Comparison Using the Dual-Task Paradigm, 2007.
• Proshanto Mukherji, Discovering Laws as Anomalies in Logical Worlds, 2007.
• Nathan J. Blaylock, Towards Tractable Agent-Based Dialogue, 2005.
• Joel R. Tetreault, Empirical Evaluations of Pronoun Resolution, 2005.
• David D. Ahn, The Role of Situations and Presuppositions in Restricting Adverbial Quantification, 2004.
• Myroslava Dzikovska A Practical Semantic Representation for Natural Language Parsing, 2004.
• Lucian Galescu, Hierarchical Statistical Language Models for Unlimited Vocabularies, 2003.
• Teresa Zollo, Detecting and Correcting Speech Recognition Errors during Natural Language Understanding, 2003.
• Donna K. Byron, Resolving Pronominal Reference to Abstract Entities, 2002.
• Gregory R. Wheeler (Joint Philosophy and CS), Non-Monotonicity and Paraconsistency, 2002.
• Amanda J. Stent, Dialogue Systems as Conversational Partners: Applying Conversation Acts Theory to Natural Language Generation for Task-Oriented Mixed-Initiative Spoken Dialogue, 2001.
• Mark G. Core, Dialog Parsing: From Speech Repairs to Speech Acts, 2000.
• Aaron N. Kaplan, A Computational Model of Belief, 2000.
• Eric K. Ringger, Correcting Speech Recognition Errors, 2000.
• Amon B. Seagull, Well-Foundedness and Reliability in Statistical Natural Language Parsing, 2000.
• Choh Man Teng, Non-Monotonic Inference: Characterization and Combination, 1998.
• Bulent Murtezaoglu, Uncertain Inference and Learning with Reference Classes, 1998.
• Louis J. Hoebel, A Practical Temporal Reasoning System, 1998, now at GE Research.
• Peter A. Heeman, Speech Repairs, Intonational Boundaries and Discourse Markers: Modeling Speakers' Utterances in Spoken Dialog, 1997, now at Oregon Graduate Institute.
• Marc N. Light, Morphological Cues for Lexical Semantics, 1996, now at MITRE Corp.
• David R. Traum, A Computational Theory of Grounding in Natural Language Conversation, 1995, now at University of Maryland.
• George M. Ferguson, Knowledge Representation and Reasoning for Mixed-Initiative Planning, 1995, now at University of Rochester.
• Massimo Poesio, Discourse Interpretation and the Scope of Operators, 1994, now at University of Edinburgh.