Normalized Interactions between autonomous agents

The CEC Project GOAL (Esprit 6283) aims to develop generic software tools to support a new project management paradigm, in which projects are collaborative, decentralised and inter-organizational. To support inter-organizational interaction, communication and cooperation, we are developing a design framework for formalizing the flow of information between organizations, specifying access to and provision of project services, and defining project-wide standards and procedures. This framework is based on normalizing interactions between autonomous software agents by specifying messages and protocols for inter-agent communication and cooperation. This paper reviews the framework, and then focusses on the specification and implementation of a case study, the automation of a distributed document review procedure. This is both a successful proof of concept and a demonstration of how Artificial Intelligence technologies can support inter-organizational project management. It also points the way to agent brokering, an enhancement of object brokering in distributed open systems, where the satisfaction of service requests can be subject to negotiation.Supported by CEC Esprit Project GOAL (Esprit 6283) and CEC Esprit BRA Medlar II (Esprit 6471).Supported by CEC Esprit Project GOAL (Esprit 6283).     

Making an information system for the humanities

The Documentation Project is a cooperative project between Faculties of Arts in the Norwegian universities. It aims to produce the Norwegian universities' databases for language and culture from the paper-based archives at the participating institutions. The project has been active on a national basis since 1992. This paper describes the methodologies involved and ongoing subprojects.Christian-Emil Ore holds a dr.scient. in Computer Science from the University of Oslo, where he has also studied linguistics and Russian language and literature. Since 1991 he has been leading the Documentation Project.     

Expert-Driven Validation of Rule-Based User Models in Personalization Applications

In many e-commerce applications, ranging from dynamic Web content presentation, to personalized ad targeting, to individual recommendations to the customers, it is important to build personalized profiles of individual users from their transactional histories. These profiles constitute models of individual user behavior and can be specified with sets of rules learned from user transactional histories using various data mining techniques. Since many discovered rules can be spurious, irrelevant, or trivial, one of the main problems is how to perform post-analysis of the discovered rules, i.e., how to validate user profiles by separating good rules from the bad. This validation process should be done with an explicit participation of the human expert. However, complications may arise because there can be very large numbers of rules discovered in the applications that deal with many users, and the expert cannot perform the validation on a rule-by-rule basis in a reasonable period of time. This paper presents a framework for building behavioral profiles of individual users. It also introduces a new approach to expert-driven validation of a very large number of rules pertaining to these users. In particular, it presents several types of validation operators, including rule grouping, filtering, browsing, and redundant rule elimination operators, that allow a human expert validate many individual rules at a time. By iteratively applying such operators, the human expert can validate a significant part of all the initially discovered rules in an acceptable time period. These validation operators were implemented as a part of a one-to-one profiling system. The paper also presents a case study of using this system for validating individual user rules discovered in a marketing application.     

The Kreisel length-of-proof problem

A first-order system F has theKreisel length-of-proof property if the following statement is true for all formulas(x): If there is ak1 such that for alln0 there is a proof of(¯n) in F with at mostk lines, then there is a proof of x(x) in F. We consider this property for Parikh systems, which are first-order axiomatic systems that contain a finite number of axiom schemata (including individual axioms) and a finite number of rules of inference. We prove that any usual Parikh system formulation of Peano arithmetic has the Kreisel length-of-proof property if the underlying logic of the system is formulated without a schema for universal instantiation in either one of two ways. (In one way, the formula to be instantiated is built up in steps, and in the other way, the term to be substituted is built up in steps.) Our method of proof uses techniques and ideas from unification theory.     

Quantitative Characterization of Event Streams in Analysis of Hard Real-Time Applications

Many real-time embedded systems process event streams that are composed of a finite number of different event types. Each different event type on the stream would typically impose a different workload to the system, and thus the knowledge of possible correlations and dependencies between the different event types could be exploited to get tighter analytic performance bounds of the complete system. We propose an abstract stream model to characterize such an event stream. The model captures the needed information of all possible traces of a class of event streams. Hence, it can be used to obtain hard bounded worst-case and best-case analysis results of a system. We show how the proposed abstract stream model can be obtained from a concrete stream specification, and how it can be used for performance analysis. The applicability of our approach and its advantages over traditional worst-case performance analysis are shown in a case study of a multimedia application.Ernesto Wandeler is a Ph.D. student at the Computer Engineering and Networks Laboratory of the Swiss Federal Institute of Technology, Zurich. His research interests include models, methods and tools for system-level performance analysis of real-time embedded systems. He holds a Dipl. El.-Ing. degree from ETH Zurich. In 2003, he received the Willi Studer Price and the ETH Medal, both from the Swiss Federal Institute of Technology, Zurich. He is a student member of the IEEE and the ACM.Alexander Maxiaguine is a Ph.D. student at the Computer Engineering and Networks Laboratory of the Swiss Federal Institute of Technology, Zurich. His research interests include models and methods for system-level performance analysis and scheduling of embedded multiprocessor architectures, especially for real-time multimedia applications. Maxiaguine has an M.S. in electrical engineering from the Moscow Technical University of Communications and Informatics. He is a member of the IEEE and the ACM.Lothar Thiele is a full professor of computer engineering at the Swiss Federal Institute of Technology, Zurich. His research interests include models, methods and software tools for the design of embedded systems, embedded software and bioinspired optimization techniques. In 1986 he received the Dissertation Award of the Technical University of Munich, in 1987, the Outstanding Young Author Award of the IEEE Circuits and Systems Society, in 1988, the Browder J. Thompson Memorial Award of the IEEE, and in 2000–2001, the IBM Faculty Partnership Award. In 2004, he joined the German Academy of Natural Scientists Leopoldina.     

ART: A Hybrid Classification Model

This paper presents a new family of decision list induction algorithms based on ideas from the association rule mining context. ART, which stands for Association Rule Tree, builds decision lists that can be viewed as degenerate, polythetic decision trees. Our method is a generalized Separate and Conquer algorithm suitable for Data Mining applications because it makes use of efficient and scalable association rule mining techniques.     

Optimal multilayer channel routing with overlap

This paper presents algorithms for multiterminal net channel routing where multiple interconnect layers are available. Major improvements are possible if wires are able to overlap, and our generalized main algorithm allows overlap, but only on everyKth (K 2) layer. Our algorithm will, for a problem with densityd onL layers,L K + 3,provably use at most three tracks more than optimal: (d + 1)/L/K + 2 tracks, compared with the lower bound of d/L/K. Our algorithm is simple, has few vias, tends to minimize wire length, and could be used if different layers have different grid sizes. Finally, we extend our algorithm in order to obtain improved results for adjacent (K = 1) overlap: (d + 2)/2L/3 + 5 forL 7.This work was supported by the Semiconductor Research Corporation under Contract 83-01-035, by a grant from the General Electric Corporation, and by a grant at the University of the Saarland.     

Interval routing schemes

In this paper the problem of routing messages along shortest paths in a distributed network without using complete routing tables is considered. In particular, the complexity of deriving minimum (in terms of number of intervals) interval routing schemes is analyzed under different requirements. For all the cases considered NP-hardness proofs are given, while some approximability results are provided. Moreover, relations among the different cases considered are studied.This work was supported by the EEC ESPRIT II Basic Research Action Program under Contract No. 7141 Algorithms and Complexity II, by the EEC Human Capital and Mobility MAP project, and by the Italian MURST 40% project Algoritmi, Modelli di Calcolo e Strutture Informative.     

CLSS: An Intelligent Crane Lorry Scheduling System

Companies that provide crane-lorry services are faced with the daily need to perform vehicle and driver allocation and scheduling. Many companies still do this manually due to the lack of suitable technologies. This manual approach is both time consuming and inaccurate and most probably will not lead to an optimized plan that can reduce operational costs. In this paper, we describe the design of a system called Crane Lorry Scheduling System (CLSS) that we have developed for the largest crane lorry company in Hong Kong. A crane lorry company is a company that provides lorries with different types of mounted crane equipment and drivers to service different types of moving and lifting jobs. CLSS is a Web-based application that streamlines communication with customers, subcontractors and employees/lorry drivers. We modeled the lorry-assignment problem as a constraint-satisfaction problem (CSP) algorithm, which we call the Crane Lorry Optimizing Engine (CLOE). CLOE was designed to be easily customizable to match the needs and requirements of different crane lorry companies. We experimented with two versions of CLOE, regular CLOE that finds best solutions and X-CLOE that finds optimal solutions. Results from our tests show that CLOE is faster and generates better quality plans than the manual approach.     

Connectionism,explicit rules,and symbolic manipulation

At present, the prevailing Connectionist methodology forrepresenting rules is toimplicitly embody rules in neurally-wired networks. That is, the methodology adopts the stance that rules must either be hard-wired or trained into neural structures, rather than represented via explicit symbolic structures. Even recent attempts to implementproduction systems within connectionist networks have assumed that condition-action rules (or rule schema) are to be embodied in thestructure of individual networks. Such networks must be grown or trained over a significant span of time. However, arguments are presented herein that humanssometimes follow rules which arevery rapidly assignedexplicit internal representations, and that humans possessgeneral mechanisms capable of interpreting and following such rules. In particular, arguments are presented that thespeed with which humans are able to follow rules ofnovel structure demonstrates the existence of general-purpose rule following mechanisms. It is further argued that the existence of general-purpose rule following mechanisms strongly indicates that explicit rule following is not anisolated phenomenon, but may well be a common and important aspect of cognition. The relationship of the foregoing conclusions to Smolensky's view of explicit rule following is also explored. The arguments presented here are pragmatic in nature, and are contrasted with thekind of arguments developed by Fodor and Pylyshyn in their recent, influential paper.     

Transformations of structures: An algebraic approach

This paper introduces a new mathematical approach to transformations of structures, where the concept of structure is extremely general. Many structures and transformations that arise in biology as well as computer science are special cases of our concepts. A structure may be changed by finding an occurrence of a pattern and replacing it by another pattern as specified by a rule. To prove theorems about long sequences of applications of complicated rules, we need precise and tractable mathematical definitions of rules and how to apply them. This paper presents such definitions and three fundamental theorems, together with brief remarks on applications to control flow analysis, record handling, and evaluation of recursively defined functions. Unlike some previous efforts toward a rigorous theory of transformations of structures, this paper uses ideas and results from abstract algebra to minimize the need for elaborate constructions.A condensation of an earlier version of this paper was presented as [9] at the 7th Symposium on Mathematical Foundations of Computer Science, September 1978, Zakopane, Poland. Work by Ehrig was partially supported by IBM Germany and IBM World Trade Corp. Work by Rosen and Maggiolo-Schettini was partially supported by the Laboratorio di Cibernetica del C.N.R.     

A fuzzy theoretical approach to case-based representation and inference in CISG

In a legal expert system based on CBR (Case-Based Reasoning), legal statute rules are interpreted on the basis of precedents. This interpretation, because of its vagueness and uncertainty of the interpretation cannot be handled with the means used for crisp cases. In our legal expert system, on the basis of the facts of precedents, the statute rule is interpreted as a form of case rule, the application of which involves the concepts of membership and vagueness. The case rule is stored in a data base by means of fuzzy frames. The inference based on a case rule is made by fuzzy YES and fuzzy NO, and the degree of similarity of cases. The system proposed here will be used for legal education; its main area of application is contract, especially in relation to the United Nations Convention on Contracts for the International Sale of Goods (CISG).     

The Emotional Wardrobe

Since the industrial revolution, fashion and technology have been linked through the textile and manufacturing industries, a relationship that has propelled technical innovation and aesthetic and social change. Today, a new alliance is emerging through the integration of electronic technology and smart materials on the body. This study addresses the integration of technology with clothing from a fashion perspective, and examines its expressive and interactive potential. It proposes the concept of The Emotional Wardrobe: clothing that represents and stimulates emotional response through the interface of technology. It asks if fashion can offer a more personal and provocative definition of self, which actively involves the wearer in a mutable aesthetic identity. A multi-disciplinary framework combines fashion, material science and the real-time, affective computing platform, called AffectiveWare. By merging technology and fashion, The Emotional Wardrobe becomes a poetic interface, shifting emphasis from human–computer interaction to computer-aided, human–human communication.     

Some Considerations on the Reason for Bloat

A representation-less model for genetic programming is presented. The model is intended to examine the mechanisms that lead to bloat in genetic programming (GP). We discuss two hypotheses (fitness causes bloat and neutral code is protective) and perform simulations to examine the predictions deduced from these hypotheses. Our observation is that predictions from both hypotheses are realized in the simulated model.     

Methods for the Reduction of Odometry Errors in Over-Constrained Mobile Robots

This paper presents an analysis of odometry errors in over-constrained mobile robots, that is, vehicles that have more independent motors than degrees of freedom. Examples of over-constrained vehicles are the various 6-wheeled Mars Rovers like Rocky-7, Rocky-8, or Fido.Based on our analysis we developed two novel measures aimed at reducing odometry errors. We also developed a novel method that serves as a framework for the implementation of the two new measures, as well as for other, conventional error reducing measures.One of the two new measures, called Fewest Pulses Measure, makes use of the observation that most terrain irregularities, as well as wheel slip, result in an erroneous overcount of encoder pulses. The second new measure, called Cross-coupled Control Measure, optimizes the motor control algorithm of the robot to reduce synchronization errors that would otherwise result in wheel slip with conventional controllers.The novel method that serves as a framework for other measures is based on so-called Expert Rules. In this paper we formulate three expert rules aimed at reducing dead-reckoning errors. Two of these expert rules are related to the foregoing discussion on error reducing measures. The third expert rule adds a gyroscope to the system and we re-examine the effectiveness of the odometry error-reducing measures in the context of this addition.In the work described in this paper we modified a Pioneer AT skid-steer platform by providing it with four independent drive motors and encoders. We implemented our error-reducing measures and the expert rule method on this over-constrained platform and present experimental results.     

Visualization of rhythm, time and metre

Developments in the theory of auditory processing of rhythmic signals have enabled the construction of a robust algorithm for recovery of rhythmic grouping structure. This algorithm appears to be effective for both speech and music signals. The theory upon which the algorithm was based was inspired by the theory of edge detection in vision. The output of the algorithm can be visualised in the form of a rhythmogram, examples of which are shown for a variety of speech signals. The relationship between rhythm, time perception and metre is discussed in the light of a recent auditory-motor theory of beat induction.     

The input/output complexity of transitive closure

Suppose a directed graph has its arcs stored in secondary memory, and we wish to compute its transitive closure, also storing the result in secondary memory. We assume that an amount of main memory capable of holdings values is available, and thats lies betweenn, the number of nodes of the graph, ande, the number of arcs. The cost measure we use for algorithms is theI/O complexity of Kung and Hong, where we count 1 every time a value is moved into main memory from secondary memory, or vice versa.In the dense case, wheree is close ton ², we show that I/O equal toO(n ³/s) is sufficient to compute the transitive closure of ann-node graph, using main memory of sizes. Moreover, it is necessary for any algorithm that is standard, in a sense to be defined precisely in the paper. Roughly, standard means that paths are constructed only by concatenating arcs and previously discovered paths. For the sparse case, we show that I/O equal toO(n ²e/s) is sufficient, although the algorithm we propose meets our definition of standard only if the underlying graph is acyclic. We also show that(n ²e/s) is necessary for any standard algorithm in the sparse case. That settles the I/O complexity of the sparse/acyclic case, for standard algorithms. It is unknown whether this complexity can be achieved in the sparse, cyclic case, by a standard algorithm, and it is unknown whether the bound can be beaten by nonstandard algorithms.We then consider a special kind of standard algorithm, in which paths are constructed only by concatenating arcs and old paths, never by concatenating two old paths. This restriction seems essential if we are to take advantage of sparseness. Unfortunately, we show that almost another factor ofn I/O is necessary. That is, there is an algorithm in this class using I/OO(n ³e/s) for arbitrary sparse graphs, including cyclic ones. Moreover, every algorithm in the restricted class must use(n ³e/s/log³ n) I/O, on some cyclic graphs.The work of this author was partially supported by NSF grant IRI-87-22886, IBM contract 476816, Air Force grant AFOSR-88-0266 and a Guggenheim fellowship.     

Mobile asynchronous communication: Exploring the potential for converged applications

Trends in technological development show that devices of personal communication and information management are converging and penetrating to new user segments. Therefore, it is a question of interest how the convergence of applications should be managed. This article explores the current use of email and SMS, focussing on the differences in the ways they are used and understood among their users. It is argued that, since the systems are different and have been in use for some time, established practices in using them as well as systems applied to understanding them are different. Based on analysis of interview data, it is conluded that this is the case, and that the future converged systems should not be considered as replacements of the current ones, but rather that the systems need to supplement each other. For example, the need for a quick and dirty instant asynchronous media such as SMS seems to remain, and therefore it cannot be replaced simply by implementing email to mobile phones. The need for email and SMS seems to be different, and thus the development should be towards a better understanding of these needs rather than simple technological convergence.     

Parallel complexity of logical query programs

We consider the parallel time complexity of logic programs without function symbols, called logical query programs, or Datalog programs. We give a PRAM algorithm for computing the minimum model of a logical query program, and show that for programs with the polynomial fringe property, this algorithm runs in time that is logarithmic in the input size, assuming that concurrent writes are allowed if they are consistent. As a result, the linear and piecewise linear classes of logic programs are inN C. Then we examine several nonlinear classes in which the program has a single recursive rule that is an elementary chain. We show that certain nonlinear programs are related to GSM mappings of a balanced parentheses language, and that this relationship implies the polynomial fringe property; hence such programs are inN C Finally, we describe an approach for demonstrating that certain logical query programs are log space complete forP, and apply it to both elementary single rule programs and nonelementary programs.Supported by NSF Grant IST-84-12791, a grant of IBM Corporation, and ONR contract N00014-85-C-0731.     

An application of artificial intelligence to the choreography of dance

This paper describes an experimental computer program that applies the techniques of artificial intelligence to the creation of dance. Specifically, a user expresses a set of dance rules (in a special English-like rule language) which describes some of the dynamic aspects of a dance. These rules are applied nondeterministically by a rule driver program. The rules themselves are similar to those that form the knowledge base of expert systems. The rule driver embodies a heuristic algorithm of the type found in many artificial intelligence programs.James H. Bradford is an Associate Professor of Computer Science at Brock University. He is an active researcher in the area of Human/Computer Interaction with particular interests in the analysis of speech and the representation of dance.Paulette Côté-Laurence is an Associate Professor of Physical Education at Brock University. Her research interests are in the areas of motor control and the acquisition of dance skills, psychology of rhythm, and dance technology.