January 18, 2000 Email: marie@ai.sri.com

People often act together with a shared purpose; they collaborate. Collaboration enables them to work more efficiently and to complete activities they could not accomplish individually. An increasing number of computer applications also require collaboration among various systems and people. Thus, a major challenge for AI researchers is to determine how to construct computer systems that are able to act effectively as partners in collaborative activity. Collaborative activity entails participants forming commitments to achieve the goals of the group activity and requires group decision making and group planning procedures. In addition, agents must be committed to supporting the activities of their fellow participants in support of the group activity. Furthermore, when conflicts arise (for example, from resource bounds), participants must weigh their commitments to various group activities against those for individual activities. This article briefly reviews the major features of one model of collaborative planning called SHARED-PLANS (Grosz and Kraus 1999, 1996). It describes several current efforts to develop collaborative planning agents and systems for human-computer communication based on this model. Finally, it discusses empirical research aimed at determining effective commitment strategies in the SHAREDPLANS context.

In the recent literature of Artificial Intelligence, an intensive research effort has been spent, for various algebras of qualitative relations used in the representation of temporal and spatial knowledge, on the problem of classifying the computational complexity of reasoning problems for subsets of algebras. The main purpose of these researches is to describe a restricted set of maximal tractable subalgebras, ideally in an exhaustive fashion with respect to the hosting algebras. In this paper we introduce a novel algebra for reasoning about Spatial Congruence, show that the satisfiability problem in the spatial algebra MC-4 is NP-complete, and present a complete classification of tractability in the algebra, based on the individuation of three maximal tractable subclasses, one containing the basic relations. The three algebras are formed by 14, 10 and 9 relations out of 16 which form the full algebra.

Multi-Agent Systems (MAS) promise to offer solutions to problems where established, older paradigms fall short. In order to validate such claims that are repeatedly made in software agent publications, empirical in-depth studies of advantages and weaknesses of multi-agent solutions versus conventional ones in practical applications are needed. Climate control in large buildings is one application area where multi-agent systems, and market-oriented programming in particular, have been reported to be very successful, although central control solutions are still the standard practice. We have therefore constructed and implemented a variety of market designs for this problem, as well as different standard control engineering solutions. This article gives a detailed analysis and comparison, so as to learn about differences between standard versus agent approaches, and yielding new insights about benefits and limitations of computational markets. An important outcome is that ``local information plus market communication produces global control''.

We investigate the problem of reasoning in the propositional fragment of MBNF, the logic of minimal belief and negation as failure introduced by Lifschitz, which can be considered as a unifying framework for several nonmonotonic formalisms, including default logic, autoepistemic logic, circumscription, epistemic queries, and logic programming. We characterize the complexity and provide algorithms for reasoning in propositional MBNF. In particular, we show that entailment in propositional MBNF lies at the third level of the polynomial hierarchy, hence it is harder than reasoning in all the above mentioned propositional formalisms for nonmonotonic reasoning. We also prove the exact correspondence between negation as failure in MBNF and negative introspection in Moore's autoepistemic logic.

Because perception-action systems are necessarily constrained by the physics of time and space, robotocists often assume they are best described using differential equations, a language that is specialized for describing the evolution of variables that represent physical quantities. However, when it comes to decision making, where the representations involved refer to goals, strategies, and preferences, AI offers a diverse range of formalisms to the modeler. However, the relationship between these two levels of representation -- signal and symbol -- are not well understood. If we are to achieve success in modeling intelligent physical agents, robotics and AI must reach a new consensus on how to integrate perception-action systems with systems designed for abstract reasoning.

Calendar of upcoming AI meetings, conferences, and other events.

An ensemble consists of a set of individually trained classifiers (such as neural networks or decision trees) whose predictions are combined when classifying novel instances. Previous research has shown that an ensemble is often more accurate than any of the single classifiers in the ensemble. Bagging (Breiman, 1996c) and Boosting (Freund & Shapire, 1996; Shapire, 1990) are two relatively new but popular methods for producing ensembles. In this paper we evaluate these methods on 23 data sets using both neural networks and decision trees as our classification algorithm. Our results clearly indicate a number of conclusions. First, while Bagging is almost always more accurate than a single classifier, it is sometimes much less accurate than Boosting. On the other hand, Boosting can create ensembles that are less accurate than a single classifier -- especially when using neural networks. Analysis indicates that the performance of the Boosting methods is dependent on the characteristics of the data set being examined. In fact, further results show that Boosting ensembles may overfit noisy data sets, thus decreasing its performance. Finally, consistent with previous studies, our work suggests that most of the gain in an ensemble's performance comes in the first few classifiers combined; however, relatively large gains can be seen up to 25 classifiers when Boosting decision trees.

The recent advances in computer speed and algorithms for probabilistic inference have led to a resurgence of work on planning under uncertainty. The aim is to design AI planners for environments where there might be incomplete or faulty information, where actions might not always have the same results, and where there might be trade-offs between the different possible outcomes of a plan. Addressing uncertainty in AI, planning algorithms will greatly increase the range of potential applications, but there is plenty of work to be done before we see practical decision-theoretic planning systems. This article outlines some of the challenges that need to be overcome and surveys some of the recent work in the area.

The "Journal of Artificial Intelligence Research (JAIR) was one of the first scientific journals distributed over the web. It has now completed over five years of successful publication. Electronic publishing is reshaping the way academic work is disseminated, and JAIR is leading the way toward a future where scientific articles are freely and easily accessible to all. This report describes how the journal has evolved, its "grassroots" philosophy, and prospects for the future.