In science, business, and policymaking--anywhere data are used in prediction--two sorts of problems requiring very different methods of analysis often arise. The first, problems of recognition and classification, concerns learning how to use some features of a system to accurately predict other features of that system. The second, problems of causal discovery, concerns learning how to predict those changes to some features of a system that will result if an intervention changes other features. This book is about the second--much more difficult--type of problem. The contributors discuss recent research and applications using Bayes nets or directed graphic representations, including representations of feedback or "recursive" systems. The book contains a thorough discussion of foundational issues, algorithms, proof techniques, and applications to economics, physics, biology, educational research, and other areas. ISBN 0-262-57124-2 426 pp., bibliography, index Published by AAAI Press - http://www.aaai.org/Press/

In this article, we present a last-minute travel application as part of a complete virtual travel agency. Each year, a significant amount of tour packages are sold as last minute tours in Germany. It is impossible for a travel agent to keep track of all the offered tour packages. Electronic-commerce applications might present the best possible tour package for a specific customer request. Traditional database-driven applications, as used by most of the tour operators, are not sufficient enough to implement a sales process with consultation on the World Wide Web. The last-minute travel application presented here uses case-based reasoning to bridge this gap and simulate the sales assistance of a human travel agent. A case retrieval net, as an internal data structure, proved to be efficient in handling the large amount of data. Important for the acceptance by customers is also the integration into the virtual travel agency and the interconnections to other parts of this system, such as background information or the online car rental application.

Recently model checking representation and search techniques were shown to be efficiently applicable to planning, in particular to non-deterministic planning. Such planning approaches use Ordered Binary Decision Diagrams (OBDDs) to encode a planning domain as a non-deterministic finite automaton and then apply fast algorithms from model checking to search for a solution. OBDDs can effectively scale and can provide universal plans for complex planning domains. We are particularly interested in addressing the complexities arising in non-deterministic, multi-agent domains. In this article, we present UMOP, a new universal OBDD-based planning framework for non-deterministic, multi-agent domains. We introduce a new planning domain description language, NADL, to specify non-deterministic, multi-agent domains. The language contributes the explicit definition of controllable agents and uncontrollable environment agents. We describe the syntax and semantics of NADL and show how to build an efficient OBDD-based representation of an NADL description. The UMOP planning system uses NADL and different OBDD-based universal planning algorithms. It includes the previously developed strong and strong cyclic planning algorithms. In addition, we introduce our new optimistic planning algorithm that relaxes optimality guarantees and generates plausible universal plans in some domains where no strong nor strong cyclic solution exists. We present empirical results applying UMOP to domains ranging from deterministic and single-agent with no environment actions to non-deterministic and multi-agent with complex environment actions. UMOP is shown to be a rich and efficient planning system.

Stochastic sampling algorithms, while an attractive alternative to exact algorithms in very large Bayesian network models, have been observed to perform poorly in evidential reasoning with extremely unlikely evidence. To address this problem, we propose an adaptive importance sampling algorithm, AIS-BN, that shows promising convergence rates even under extreme conditions and seems to outperform the existing sampling algorithms consistently. Three sources of this performance improvement are (1) two heuristics for initialization of the importance function that are based on the theoretical properties of importance sampling in finite-dimensional integrals and the structural advantages of Bayesian networks, (2) a smooth learning method for the importance function, and (3) a dynamic weighting function for combining samples from different stages of the algorithm. We tested the performance of the AIS-BN algorithm along with two state of the art general purpose sampling algorithms, likelihood weighting (Fung & Chang, 1989; Shachter & Peot, 1989) and self-importance sampling (Shachter & Peot, 1989). We used in our tests three large real Bayesian network models available to the scientific community: the CPCS network (Pradhan et al., 1994), the PathFinder network (Heckerman, Horvitz, & Nathwani, 1990), and the ANDES network (Conati, Gertner, VanLehn, & Druzdzel, 1997), with evidence as unlikely as 10^-41. While the AIS-BN algorithm always performed better than the other two algorithms, in the majority of the test cases it achieved orders of magnitude improvement in precision of the results. Improvement in speed given a desired precision is even more dramatic, although we are unable to report numerical results here, as the other algorithms almost never achieved the precision reached even by the first few iterations of the AIS-BN algorithm.

Induction and deduction are two opposite operations in data-mining applications. Induction extracts knowledge in the form of, say, rules or decision trees from existing data, and deduction applies induction results to interpret new data. An intelligent learning database (ILDB) system integrates machine-learning techniques with database and knowledge base technology. It starts with existing database technology and performs both induction and deduction. The integration of database technology, induction (from machine learning), and deduction (from knowledge-based sys-tems) plays a key role in the construction of ILDB systems, as does the design of efficient induction and deduction algorithms. This article presents a system structure for ILDB systems and discusses practical issues for ILDB applications, such as instance selection and structured induction.

The CMUNITED-99 simulator team became the 1999 RoboCup simulator league champion by winning all 8 of its games, outscoring opponents by a combined score of 110-0. CMUNITED-99 builds on the successful CMUNITED-98 implementation but also improves on it in many ways. This article gives an overview of CMUNITED-99's improvements over CMUNITED-98.

This work deals with designing simple behaviors to allow quadruped robots to play soccer. The robots are fully autonomous; they cannot exchange messages between each other. They are equipped with a charge-coupled-device camera that allows them to detect objects in the scene. In addition to vision problems such as changing lighting conditions and color confusion, legged robots must cope with "bouncing images" because of successive legs hitting the ground. When defining task-driven strategies, the designer has to take into account the influences of the locomotion and vision systems on the behavior. Locomotion and vision skills should be made as reliable as possible. Because it is not always possible to simulate the problems encountered in real situations, the behavior strategy should anticipate them. In this article, we describe all the behaviors used to play soccer games on a soccer field surrounded with landmarks. Experiments were carried out at the 1999 RoboCup in Stockholm using the Sony quadruped robots (Fujita 2000).

RoboCup is an initiative designed to promote the full integration of AI and robotics research. Following the success of the first RoboCup in 1997 at Nagoya (Kitano 1998; Noda et al. 1998) and the second RoboCup in Paris in 1998, the Third Robot World Cup Soccer Games and Conferences, RoboCup-99, were held in Stockholm from 27 July to 4 August 1999 in conjunction with the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI-99). There were four different leagues: (1) the simulation league, (2) the small-size real robot league, (3) the middle-size real robot league, and (4) the Sony legged robot league. RoboCup-2000, the Fourth Robot World Cup Soccer Games and Conferences, will take place in Melbourne, Australia, in August 2000.

We investigate the space efficiency of a Propositional Knowledge Representation (PKR) formalism. Intuitively, the space efficiency of a formalism F in representing a certain piece of knowledge A, is the size of the shortest formula of F that represents A. In this paper we assume that knowledge is either a set of propositional interpretations (models) or a set of propositional formulae (theorems). We provide a formal way of talking about the relative ability of PKR formalisms to compactly represent a set of models or a set of theorems. We introduce two new compactness measures, the corresponding classes, and show that the relative space efficiency of a PKR formalism in representing models/theorems is directly related to such classes. In particular, we consider formalisms for nonmonotonic reasoning, such as circumscription and default logic, as well as belief revision operators and the stable model semantics for logic programs with negation. One interesting result is that formalisms with the same time complexity do not necessarily belong to the same space efficiency class.

We order its events and find meaning in them by assimilating them to more or less familiar narratives. Temporal A wide variety of systems were presented: 1999, at the Sea Crest Oceanfront and modal logics have been used to story generation, interactive Resort and Conference Center. The reason about time, action, and adaptive fiction (including the first public titles of the five symposia were change and to program and verify demonstration from Joseph Bates's networked systems. How can we create characters from specifications of service quality in which interactive narrative emerges? The symposium focused mainly on a single, comprehensive theoretical framework, Clark's grounding model.