The main operations in Inductive Logic Programming (ILP) are generalization and specialization, which only make sense in a generality order. In ILP, the three most important generality orders are subsumption, implication and implication relative to background knowledge. The two languages used most often are languages of clauses and languages of only Horn clauses. This gives a total of six different ordered languages. In this paper, we give a systematic treatment of the existence or non-existence of least generalizations and greatest specializations of finite sets of clauses in each of these six ordered sets. We survey results already obtained by others and also contribute some answers of our own. Our main new results are, firstly, the existence of a computable least generalization under implication of every finite set of clauses containing at least one non-tautologous function-free clause (among other, not necessarily function-free clauses). Secondly, we show that such a least generalization need not exist under relative implication, not even if both the set that is to be generalized and the background knowledge are function-free. Thirdly, we give a complete discussion of existence and non-existence of greatest specializations in each of the six ordered languages.

Clustering is often used for discovering structure in data. Clustering systems differ in the objective function used to evaluate clustering quality and the control strategy used to search the space of clusterings. Ideally, the search strategy should consistently construct clusterings of high quality, but be computationally inexpensive as well. In general, we cannot have it both ways, but we can partition the search so that a system inexpensively constructs a `tentative' clustering for initial examination, followed by iterative optimization, which continues to search in background for improved clusterings. Given this motivation, we evaluate an inexpensive strategy for creating initial clusterings, coupled with several control strategies for iterative optimization, each of which repeatedly modifies an initial clustering in search of a better one. One of these methods appears novel as an iterative optimization strategy in clustering contexts. Once a clustering has been constructed it is judged by analysts -- often according to task-specific criteria. Several authors have abstracted these criteria and posited a generic performance task akin to pattern completion, where the error rate over completed patterns is used to `externally' judge clustering utility. Given this performance task, we adapt resampling-based pruning strategies used by supervised learning systems to the task of simplifying hierarchical clusterings, thus promising to ease post-clustering analysis. Finally, we propose a number of objective functions, based on attribute-selection measures for decision-tree induction, that might perform well on the error rate and simplicity dimensions.

Inductive theorem provers often diverge. This paper describes a simple critic, a computer program which monitors the construction of inductive proofs attempting to identify diverging proof attempts. Divergence is recognized by means of a ``difference matching'' procedure. The critic then proposes lemmas and generalizations which ``ripple'' these differences away so that the proof can go through without divergence. The critic enables the theorem prover Spike to prove many theorems completely automatically from the definitions alone.

Termination of logic programs with negated body atoms (here called general logic programs) is an important topic. One reason is that many computational mechanisms used to process negated atoms, like Clark's negation as failure and Chan's constructive negation, are based on termination conditions. This paper introduces a methodology for proving termination of general logic programs w.r.t. the Prolog selection rule. The idea is to distinguish parts of the program depending on whether or not their termination depends on the selection rule. To this end, the notions of low-, weakly up-, and up-acceptable program are introduced. We use these notions to develop a methodology for proving termination of general logic programs, and show how interesting problems in non-monotonic reasoning can be formalized and implemented by means of terminating general logic programs.

Thirteenth International Distributed AI Workshop

The University of Chicago's robot, CHIP, is part of the Animate Agent Project, aimed at understanding the software architecture and knowledge representations needed to build a general-purpose robotic assistant. CHIP's strategy for the Office Cleanup event of the 1995 Robot Competition and Exhibition was to scan an entire area systematically and, as collectible objects were identified, pick them up and deposit them in the nearest appropriate receptacle. This article describes CHIP and its various systems and the ways in which these elements combined to produce an effective entry to the robot competition.

The 1994 Workshop on Case-Based Reasoning (CBR) focused on the evaluation of CBR theories, models, systems, and system components. The CBR community addressed the evaluation of theories and implemented systems, with the consensus that a balance between novel innovations and evaluations could maximize progress.

The goal of the Workshop on Adaptation and Learning in Multiagent Systems was to focus on research that addresses unique requirements for agents learning and adapting to work in the presence of other agents. Recognizing the applicability and limitations of current machine-learning research as applied to multiagent problems and developing new learning and adaptation mechanisms particularly targeted to this class of problems were the primary research issues that we wanted the authors to address. This article outlines the presentations that were made at the workshop and the success of the workshop in meeting the established goals. Issues that need to be better understood are also presented.

Woody was one of the founders of AI, making early contributions in pattern recognition and automated reasoning. He continued to make significant contributions to AI throughout his long career. His legacy consists not only of his scientific work but also of several generations of scientists who learned from Woody the joy of scientific research and the way to go about it. Woody's enthusiasm, his perpetual sense of optimism, his can-do attitude, and his deep sense of duty to humanity offered those who knew him the hope and comfort that truly good and great men do exist.

The 1995 Robot Competition and Exhibition was held in Montreal, Canada, in conjunction with the 1995 International Joint Conference on Artificial Intelligence. The competition was designed to demonstrate state-of-the-art autonomous mobile robots, highlighting such tasks as goal-directed navigation, feature detection, object recognition, identification, and physical manipulation as well as effective human-robot communication. The competition consisted of two separate events: (1) Office Delivery and (2) Office Cleanup. The exhibition also consisted of two events: (1) demonstrations of robotics research that was not related to the contest and (2) robotics focused on aiding people who are mobility impaired.