Abstracts of the ISI AI Seminar Series in 1998
Daphne Koller - January 30, 1998
Hiroaki Kitano -, April 3, 1998
Rina Dechter - April 17, 1998
Richard Lathrop - May 8, 1998
Stefan Schaal - May 22, 1998
Pat Langley - June 26, 1998
Jonathan Gratch - August 7, 1998
Michael Wellman - August 18, 1998
Kevin Knight - August 28, 1998
Pandurang Nayak - September 11, 1998
David Steier - September 25, 1998
Oliver Duschka - October 2, 1998
Charles Rich - October 9, 1998
Marie desJardins - October 14, 1998
Rich Goodwin - November 13, 1998
Kathleen McKeown - November 16, 1998
Jonathan Knight - December 4, 1998
Friday, January 30, 1998
Probabilistic Reasoning:Scaling Up
Daphne Koller
Computer Science Department
Stanford University
Any application where an intelligent agent interacts with the real world must deal with the problem of uncertainty. Probability theory gives us a principled and coherent methodology for reasoning under uncertainty. In recent years, Bayesian networks have emerged as the dominant technology for making probabilistic reasoning a practical tool. Bayesian networks achieve effective knowledge representation and inference capabilities by utilizing a structural property that appears in many domains: the fact that, typically, each attribute is directly affected only by very few others. Bayesian networks have been used with great success in a wide variety of medium-scale applications. However, certain fundamental limitations on the expressive power of Bayesian networks renders them inadequate for handling large and complext domains. In the talk, I describe these limitations and discuss a new approach for scaling up probabilistic reasoning.
Our new approach is based on an analogy between probabilistic modeling languages and programming languages. When viewed in this light, Bayesian networkds are analogous to logical circuits, clearly a far from optimal language for large scale applications. We show how various fundamental ideas from programming languages --- particularly function calls, encapsulation, and object-oriented programming --- can be imported into the framework of probabilistic modeling. The resulting language maintains the clean and coherent probabilistc semantics of Bayesian networks, while providing much greater expressivity. In particular, our framework allows us to deal with domains containing many objects; it also supports the representation of relations betweein objects, of hierarchically structured domains where objects can contain other objects, of classes of objects, and more. We also show that the additional structure encoded in these domain models can be exploited for inference. This property allows us to guarantee performance scalability even for very large domain models. Finally, I discuss the connection between our representation language and more traditional knowledge representaiton languages, and show that our framework bridges the long-standing gap between the two main knowledge representation formalisms: Bayesian networks and frame-based logical representation.
This talk covers joint work with Avi Pfeffer.
Friday, April 3, 1998
The Robot World Initiative
Hiroaki Kitano
Sony Computer Science Laboratory, Tokyo
President, The RoboCup Federation, Bern, Switzerland
The Robot World Cup Initiative (RoboCup) is an international initiative to foster robotics and AI technologies using soccer games. It is one of the fastest growing areas of robotics and AI research, with over 1,500 researchers and students in over 20 countries throughout the world participating. The basic idea behind the initiative is to provide a common problem for researchers so that various different approaches can be evaluated in the same domain, and technical information can be shared to promote further research. The ultimate goal of the initiative can be stated as follows:
By the mid-21st century, a team of soccer playing humanoid robots shall beat the champion of the most recent World Cup under FIFA official rules.
Building a robot to play a soccer game by itself does not generate any significant social and economic impact, but the accomplishment will certainly considered a major achievement in the field of robotics. We call this kind of project a landmark project. RoboCup is a landmark project as well as a standard problem. The successful landmark project claims to accomplish very attractive and broadly appealing goals. The most successful example is the Apollo space program. In case of the Apollo project, the U.S. committed to the goal of ``landing a man on the moon and returning him safely to earth.''
Initially, RoboCup is designed to meet the chalenge of handling real world complexities, though in a limited world, while maintaining affordable problem size and research cost. As technology progress, we will soon move to more sophisticated robotic soccer players, namely legged robots and humanoid robots. RoboCup offers an integrated research task covering the broad areas of AI and robotics. Such areas include: real-time sensor fusion, reactive behavior, strategy acquisition, learning, real-time planning, multi-agent systems, context recognition, vision, strategic decision-making, motor control, intelligent robot control, and many more.
In this talk, I will describe the current status of the initiative, illustrate some major technical challenges, and discuss the future vision of the RoboCup Initiative.
Friday, April 17, 1998
Bucket Elimination: A Unifying Framework for automated reasoning
University of California, Irvine
Bucket elimination, is an algorithmic framework that unifies many complex problem-solving and reasoning tasks. Algorithms such as directional-resolution for propositional satisfiability, adaptive-consistency for constraint satisfaction, Fourier and Gaussian elimination, for solving linear equalities and inequalities and dynamic programming for combinatorial optimization, as well as probabilistic inference such as, belief updating, finding the most probable explanation and the maximum expected utility, can all be accommodated within the bucket elimination framework. The generality of this framework encourages the transfer of heuristics and techniques across disciplines. The algorithms mentioned above share the same performance guarantees; all are time and space exponential in the tree-width embedding of the problem's interaction graph.
In this talk I will demonstrate the applicability of the framework, and will contrast bucket elimination with conditioning, another known universal method for problem solving that is time exponential, but does not suffer from the space complexity of elimination. I will then present a uniform way of combining conditioning with elimination that can be used to trade space for time and time for accuracy. Finally, I will present the mini-bucket scheme; a new approach for approximating bucket elimination which offers an adjustable level of accuracy and efficiency. Applications to medical diagnosis and decoding algorithms will be given.
Friday, May 8, 1998
Knowledge-based Avoidance of Drug-Resistant HIV Mutants
(Joint work with Mike Pazzani and Darryl See)
University of California, Irvine
We describe an artificial intelligence (AI) system (CTSHIV) that connects the scientific AIDS literature describing specific HIV drug resistances directly to the Customized Treatment Strategy of a specific HIV patient. Rules in the CTSHIV knowledge base encode knowledge about sequence mutations in the HIV genome that have been found to result in drug resistance in the HIV virus. Rules are applied to the actual HIV sequences of the virus strains infecting the specific patient undergoing clinical treatment in order to infer current drug resistance. A search through mutation sequence space identifies nearby drug resistant mutant strains that might arise. The possible drug treatment regimens currently approved by the US Food and Drug Administration (FDA) are considered and ranked by their estimated ability to avoid identified current and nearby drug resistant mutants.
The highest-ranked treatments are recommended to the attending physician. The result is more precise treatment of individual HIV patients, and a decreased tendency to select for drug resistant genes in the global HIV gene pool. The application is currently in use in human clinical trials on HIV patients. Initial results from a small clinical trial are encouraging and further clinical trials are planned. From an AI viewpoint the case study demonstrates the extensibility of knowledge-based systems because it illustrates how existing encoded knowledge can be used to support new applications that were unanticipated when the original knowledge was encoded.
Friday, May 22, 1998
Incremental Learning
University of Southern California
The ability to learn internal models about the environment is often assumed to be one of the key ingredients for intelligent information processing, be it in robotics, process control, or biological organisms. In autonomous learning systems that have a high input rate of sensory data, internal models need to be acquired by incremental learning, i.e., data points are only used once for updating the model and are then discarded. This talk will discuss the problems that need to be faced in incremental learning, in particular the problems of catastrophic interference and how to allocate sufficient resources for the learning network. By using techniques from nonparametric statistics, it will be shown how principled and fast solutions to incremental learning can be found in the framework of locally weighted regression. We will also discuss how the presented methods scale to high dimensional learning problems, a domain that has usually been assumed to be not suitable for local learning systems. The usefulness of our algorithms and the validity of their assumptions are illustrated with charts and videos for synthetic data and in applications using an actual 7 degree-of-freedom anthropomorphic robot arm that learns various dynamic manipulations tasks.
Friday, JUNE 26, 1998
Machine Learning for Adaptive User Interfaces
Adaptive Systems Group
Daimler-Benz Research and Technology Center
and
Institute for the Study of Learning and Expertise
Palo Alto, California
In this talk I examine adaptive user interfaces -- advisory systems that personalize themselves to individual users. First I review the issues that arise in developing systems that learn from experience, then draw a strong analogy with software that adapts to its users. After this, I consider some examples of adaptive interfaces, focusing on systems that we are developing. These include the Adaptive Route Advisor, which suggests routes based on a user's driving history, and INCA, an interactive aid for crisis management that proposes revisions to plans and schedules. In closing, I consider the challenges that arise in developing adaptive user interfaces and some general lessons that have emerged from work in this area.
For more information about these projects, see the ISLE web pages:
http://www.isle.org/~langley/papers/route.sss98.ps
http://www.isle.org/~gervasio/pub/cogsci98.ps
http://www.isle.org/~gervasio/pub/aaai98.ps
This talk describes work done jointly with Seth Rogers, Wayne Iba, and Melinda Gervasio.
Friday, August 7, 1998
Planning and Execution in Multi-agent Environments
Information Sciences Institute
University of Southern California
Achieving one's goals in a social environment poses several challenges not generally addressed by traditional planning methods. Astute planners can make the most of social situations by recruiting the help of others and outmaneuvering potential adversaries. Planning for such encounters, rather than simply reacting to them, demands an ability to reason about the plans of others. But this requires more than adding multiple plans to a traditional planning system. One cannot directly manipulate other peoples plans, but can can only influence them indirectly and to varying degrees depending on our access to them, and their willingness to provide help. A truly multi-agent planning system must modulate it's planning and threat resolution approaches based on properties of the multiple plans it represents: do I have the authority to tell this person what to do; will this person attempt to defeat my goals; how do I avoid the threats they are presenting, etc.
In this talk I present an extension to classical planning methods that facilitates their use in dynamic multi-agent domains. First, I discuss a technique for planing in a changing world that supports interleaving of plan generation, execution, and repair. Second, I extend this approach to support collaborative and adversarial planning. The approach implements a form of metaplanning that enables a planner to reason about properties of multiple plans in a single plan network. With this approach, a planner can simultaneously generate an individual plan, repair a second, and , together with a group, execute a third. This provides some of the key functionality of sophisticated multi-agent reasoning techniques (such as the shared plans approach of Grosz and Kraus), but within the context of better understood classical planning methods. As such, it helps bridge the gap between planning and multi-agent research.
Tuesday, August 18, 1998
Progress in Market-Oriented Programming
University of Michigan
Market-oriented programming is the construction of computational economies, where agents interact through a price system. Markets can provide effective allocation of resources for a variety of distributed environments, and economic analysis a powerful design tool for interaction mechanisms. The spread of electronic commerce puts a premium on market-aware agents, and presents a case for market awareness on the part of agent developers and AI/CS researchers as well.
In this talk, I present an overview of our approach to market-oriented programming, and highlight recent results in:
1. Market-based decentralized scheduling.
2. Market-based task allocation: bottom-up formation of supply chains in task dependency networks.
Along the way, I will mention our configurable Internet auction server (the AuctionBot), and its role in the Michigan Adaptive Resource eXchange (MARX project).
Friday, August 28, 1998
EM: the Most Used, Feared, and Respected Learning Algorithm in Natural Language Processing Today
Information Sciences Institute
University of Southern California
I'll talk about how the EM algorithm changed my life. It's well known that statistical methods can help alleviate the knowledge acquisition bottleneck in NLP and expert systems. However, we often don't have the right kind of data to (say) train a decision tree. For example, what if we want to build a disambiguator for the word "bank", but we only have raw text to train on? The EM (estimation-maximization) algorithm gives direction in such cases. EM is not really an algorithm you can look up in a textbook, unfortunately. It's more like a way of approaching problems. So I'll give examples of how EM slices into a series of NLP and other problems, including some of our own.
Friday, September 11, 1998
The New Millennium Remote Agent: To Boldly Go Where No AI System Has Gone Before
Pandurang Nayak
The New Millennium Remote Agent is an autonomous spacecraft control system being developed jointly by NASA Ames and JPL. It integrates constraint-based planning and scheduling, robust multi-threaded execution, model-based diagnosis and reconfiguration, and real-time monitoring and control. The Remote Agent will control Deep Space One (DS-1), the first of NASA's New Millennium missions launching in late 1998. As the first AI system to autonomously control an actual spacecraft, the Remote Agent will enable the establishment of a "virtual presence" in space through an armada of intelligent space probes that autonomously explore the nooks and crannies of the solar system. I will briefly describe the main components of the Remote Agent system and then focus on Livingstone. Livingstone, which provides the diagnosis and reconfiguration capabilities of the Remote Agent, is a kernel of a reactive model-based autonomous system that performs significant deduction within the reactive control loop.
Based on the IJCAI-97 Invited Talk given jointly with Nicola Muscettola, Barney Pell, and Brian Williams
Friday, September 25, 1998
Knowledge Management for the Enterprise: New Challenges for AI
David Steier
Scient Corporation
How does an organization become an expert in its business? The emerging field of knowledge management (KM) addresses this question with processes and technologies that facilitate knowledge capture and reuse. One would think that AI's techniques for developing "knowledge-based systems" would be a major resource for this new field, but so far AI has played a relatively minor role. We think the key to an increased role for AI is for AI tools to incorporate organizational task context more effectively. This talk develops this theme using examples from knowledge management in professional services firms, with a focus on meta-data and taxonomies. Given he scale of taxonomies in enterprise-wide knowledge management systems, challenges include evolution of taxonomies and interfaces between multiple taxonomies.
Note: Scient (www.scient.com) is a rapidly growing professional services firm based in San Francisco, with job openings in both professional services and core (internal) services. Our two slots for Knowledge Systems Designers will be of special interest to people with backgrounds in artificial intelligence and/or human computer interaction; see http://www.scient.com/company/jobs/core/k_designer.htm . I'll be happy to discuss opportunities in the afternoon following my talk.
Friday, October 2, 1998
QUERY PLANNING AND OPTIMIZATION IN INFORMATION INTEGRATION
Oliver Duschka
Socratix Systems, Inc.
Information integration systems, also knows as mediators, information brokers, or information gathering agents, provide uniform user interfaces to varieties of different information sources. With corporate databases getting connected by intranets, and vast amounts of information becoming available over the Internet, the need for information integration systems is increasing steadily.
This talk focuses on query planning in such systems. Query planning is the task of transforming a user query, represented in the user's interface language and vocabulary, into queries that can be executed by the information sources. Every information source might require a different query language and might use different vocabularies. The resulting answers of the information sources need to be translated and combined before the final answer can be reported to the user.
We show that query plans with a fixed number of database operations are insufficient to extract all information from the sources, if functional dependencies or limitations on binding patterns are present. Dependencies complicate query planning because they allow query plans that would otherwise be invalid. We present an algorithm that constructs query plans that are guaranteed to extract all available information in these more general cases. This algorithm is also able to handle datalog user queries.
Oliver M. Duschka is the Director of Integration Technologies at Socratix Systems, Inc., a bioinformatics start-up company based in San Diego, California providing information integration solutions for the pharmaceutical and healthcare industries. He received his M.S. and Ph.D. degrees in Computer Science from Stanford University in 1994 and 1997, respectively. His research is focused on query planning and optimization in information integration systems.
Friday, October 9, 1998
COLLAGEN: A Collaboration Manager for Software Interface Agents
MERL--A Mitsubishi Electric Research
Laboratory
Cambridge, Massachusetts
When software agents interact with people, they should be governed by the same principles that underlie natural human collaboration. These principles have been studied and formalized by computational linguists, specifically in collaborative discourse theory, which describes how people communicate and coordinate their activities in the context of shared tasks.
Collagen is an application-independent Java middleware package which implements Grosz and Sidner's SharedPlan theory of collaborative discourse. We are using Collagen to build experimental interface agents for a variety of applications, including air travel planning, email, resource allocation, and industrial control. The occasion of this visit to ISI is to initiate joint research with Lewis Johnson and Jeff Rickel (CARTE) to evaluate using Collagen to build pedagogical agents.
Interface agents built using Collagen can provide intelligent, mixed initiative assistance without requiring natural language understanding. Collagen also automatically constructs an interaction history which is hierarchically structured according to the user's and agent's goals and intentions. As well as helping the user stay oriented during complex and extended problem-solving sessions, this structured interaction history supports high-level transformations, such as returning to earlier goals and replaying segments of the history.
For more information about Collagen, please visit our project home page.
Monday, October 14, 1998
Coordinating Planning Activity and Information Flow in a Distributed Planning System
Marie desJardins
SRI International
(Joint work with Michael Wolverton, SRI International)
Distributed SIPE (DSIPE) is a distributed planning system that provides decision support to human planners in a collaborative, continuous planning environment. The key contributions of our research on DSIPE are (1) constraint-based, consistent local views of the global plan that gives each planner a view of how other planners' subplans relate to their local planning decisions; (2) methods for automatically identifying and sharing relevant information among distributed planning agents; and (3) techniques for merging subplans that leverage the shared subplan structure to generate a complete, final plan. DSIPE is a fully implemented system, and has been demonstrated to end users in the maritime (U.S. Navy and U.S. Marine Corps) planning community.
In the talk, I will describe the DSIPE architecture and the maritime planning application domain. I will also briefly discuss the continuous planning aspects of the project (connecting the distributed planning system to an execution monitoring module).
BIOGRAPHY
Marie desJardins is a senior computer scientist at SRI
International. Her current research projects are in the areas of
distributed planning and hybrid case-based/generative planning
techniques, mixed-initiative knowledge acquisition methods for
constructing Bayes nets, and performing task-based information routing
in collaborative environments. Dr. desJardins was awarded a Ph.D. in
artificial intelligence from the University of California at Berkeley
in 1992, where her dissertation presented a model for autonomous
machine learning in probabilistic domains. She received her A.B. in engineering / computer science from Harvard University in 1985. She can be reached at SRI International, 333 Ravenswood Ave., Menlo Park CA 94025; e-mail: marie@erg.sri.com; WWW: http://www.erg.sri.com/people/marie
Friday, November 13, 1998
Agent-Based Scheduling and Decision-Support for the Paper Industry
Rich Goodwin
IBM
In this talk, I'll describe a new agent-based optimization and decision-support architecture that we have successfully applied to scheduling paper manufacturing and distribution. Scheduling the production and distribution of paper is an extremely complex task requiring the consideration of numerous constraints and objectives. Problem complexity is compounded by process interactions wherein the scheduling of one stage of the production process may negatively impact downstream processes. In contrast to earlier approaches, our system considers multiple scheduling objectives and multiple stages of paper manufacturing and distribution simultaneously in a global multi-criteria optimization framework. It generates multiple scheduling alternatives by using a team of agents that employ a portfolio of algorithms, some based on traditional operations-research approaches and others based on heuristic search. The system encourages the human schedulers to work cooperatively with the system to explore alternatives and to inject their expertise to improve solution quality. By functioning as an intelligent assistant, our system relieves the schedulers of mundane computational tasks and allows them to focus on the objectives of the enterprise and decision making. Our system is in use at several paper mills in North America and has resulted in significant cost savings and improved customer satisfaction. These positive results arose from improved chedule quality and improvements in the business process that our decision-support approach has fostered.
Wednesday, November 16, 1998
Generating Multimedia Briefings: Coordinating Illustration and Language
(updated version of IJCAI-97 Invited Talk)
Kathleen R. McKeown
Columbia University
Communication can be more effective when several media (such as text, speech, or graphics) are integrated and coordinated to present information. This changes the nature of media specific generation (e.g., language generation) which must take into account the multimedia context in which it occurs. In this talk, I will present work on coordinating and integrating speech, text, static and animated 3D graphics, and stored images, as part of several systems we have developed at Columbia University. A particular focus of our work has been on the generation of presentations that brief a user on information of interest.
Friday, December 4, 1998
Fictional Characters as Models for Credible Agents
Jonathan Knight
Activision Studios
To design an autonomous agent which is indistinguishable from a human is a challenging problem, requiring an ability to evaluate the model (a human) which may not be available. If we imagine an agent which is more than expert, but less than human (i.e., one that is human-like, without being indistinguishable from a human), then we are presented with the task of finding an appropriate model upon which to base the architecture of this "credible" agent. The fictional character, because it is based upon human behavior and is human-like, turns out to be an excellent model. Using tried-and-true techniques for analyzing stories and dramatic structure, we find that fictional characters are constructed out of problems, goals, and solutions, making them fundamentally understandable. As a result, the architecture of the fictional character can be applied to agents, giving them behavior that is human-like.
[ Information Sciences
Institute | AI Seminar | Schedule for Speaker | Upcoming Seminars ]
[ About AI Seminars | Useful Information