The local search algorithm WSat is one of the most successful algorithms for solving the satisfiability (SAT) problem. It is notably effective at solving hard Random 3-SAT instances near the so-called `satisfiability threshold', but still shows a peak in search cost near the threshold and large variations in cost over different instances. We make a number of significant contributions to the analysis of WSat on high-cost random instances, using the recently-introduced concept of the backbone of a SAT instance. The backbone is the set of literals which are entailed by an instance. We find that the number of solutions predicts the cost well for small-backbone instances but is much less relevant for the large-backbone instances which appear near the threshold and dominate in the overconstrained region. We show a very strong correlation between search cost and the Hamming distance to the nearest solution early in WSat's search. This pattern leads us to introduce a measure of the backbone fragility of an instance, which indicates how persistent the backbone is as clauses are removed. We propose that high-cost random instances for local search are those with very large backbones which are also backbone-fragile. We suggest that the decay in cost beyond the satisfiability threshold is due to increasing backbone robustness (the opposite of backbone fragility). Our hypothesis makes three correct predictions. First, that the backbone robustness of an instance is negatively correlated with the local search cost when other factors are controlled for. Second, that backbone-minimal instances (which are 3-SAT instances altered so as to be more backbone-fragile) are unusually hard for WSat. Third, that the clauses most often unsatisfied during search are those whose deletion has the most effect on the backbone. In understanding the pathologies of local search methods, we hope to contribute to the development of new and better techniques.

Decision theory formally solves the problem of rational agents in uncertain worlds if the true environmental prior probability distribution is known. Solomonoff's theory of universal induction formally solves the problem of sequence prediction for unknown prior distribution. We combine both ideas and get a parameterless theory of universal Artificial Intelligence. We give strong arguments that the resulting AIXI model is the most intelligent unbiased agent possible. We outline for a number of problem classes, including sequence prediction, strategic games, function minimization, reinforcement and supervised learning, how the AIXI model can formally solve them. The major drawback of the AIXI model is that it is uncomputable. To overcome this problem, we construct a modified algorithm AIXI-tl, which is still effectively more intelligent than any other time t and space l bounded agent. The computation time of AIXI-tl is of the order tx2^l. Other discussed topics are formal definitions of intelligence order relations, the horizon problem and relations of the AIXI theory to other AI approaches.

Normal forms play an important role in computer science. Examples of areas where normal forms have proved fruitful include logic, where normal forms of formulae are used both for the proof of theoretical results and in automated theorem proving, and relational databases [7], where normal forms have been the driving force in the development of database theory and principles of good data modelling. In computer science, usually normal forms are supported by transformations, operational procedures that transform initial objects (such as programs or logical theories) to their normal form. Such transformations are important for two main reasons: 1. They support the understanding and assimilation of new concepts because they allow one to concentrate on certain forms and key features only. Thus transformations can be useful as theoretical tools.

1999 Bar Illan Symposium on the Foundations of Artificial Intelligence

A Review of Reinforcement Learning

The Robot World Cup Soccer Games and Conferences (RoboCup) are a series of competitions and events designed to promote the full integration of AI and robotics research. Following the first RoboCup, held in Nagoya, Japan, in 1997, RoboCup-98 was held in Paris from 2-9 July, overlapping with the real World Cup soccer competition. RoboCup-98 included competitions in three leagues: (1) the simulation league, (2) the real robot small-size league, and (3) the real robot middle-size league. Champion teams were cmunited-98 in both the simulation and the real robot small-size leagues and cs-freiburg (Freiburg, Germany) in the real robot middle-size league.

The AAAI-99 Workshop Program (a part of the sixteenth national conference on artificial intelligence) was held in Orlando, Florida. Each workshop was limited to approximately 25 to 50 participants. Participation was by invitation from the workshop organizers. The workshops were Agent-Based Systems in the Business Context, Agents' Conflicts, Artificial Intelligence for Distributed Information Networking, Artificial Intelligence for Electronic Commerce, Computation with Neural Systems Workshop, Configuration, Data Mining with Evolutionary Algorithms: Research Directions (Jointly sponsored by GECCO-99), Environmental Decision Support Systems and Artificial Intelligence, Exploring Synergies of Knowledge Management and Case-Based Reasoning, Intelligent Information Systems, Intelligent Software Engineering, Machine Learning for Information Extraction, Mixed-Initiative Intelligence, Negotiation: Settling Conflicts and Identifying Opportunities, Ontology Management, and Reasoning in Context for AI Applications.

The CMUNITED-98 simulator team became the 1998 RoboCup simulator league champion by winning all 8 of its games, outscoring opponents by a total of 66-0. CMUNITED-98 builds on the successful cmunited-97 implementation but also improves on it in many ways. This article gives an overview of the cmunited-98 agent skill and multiagent coordination strategies, emphasizing the recent improvements.

The Workshop on Intelligent Information Integration (III), organized in conjunction with the Sixteenth International Joint Conference on Artificial Intelligence, was held on 31 July 1999 in Stockholm, Sweden. Approximately 40 people participated, and nearly 20 papers were presented. This packed workshop schedule resulted from a large number of submissions that made it difficult to reserve discussion time without rejecting an unproportionately large number of papers. Participants included scientists and practitioners from industry and academia.

Robotic soccer is an ideal task to demonstrate new techniques and explore new problems. Our intention in building a robotic soccer team and participating in RoboCup-98 was, first, to demonstrate the usefulness of the self-localization methods we have developed. Second, we wanted to show that playing soccer based on an explicit world model is much more effective than other methods. Third, we intended to explore the problem of building and maintaining a global team world model.