Ebook: Artificial Intelligence Research and Development

“We propose that a 2 month, 10 man study of artificial intelligence be carried out during the summer of 1956 at Dartmouth College in Hanover, New Hampshire. The study is to proceed....” Last year we celebrated the 50th anniversary of the Dartmouth AI project proposal by McCarthy, Minsky, Rochester and Shannon. Years later, and following similar traditions of a number of AI associations, a call was launched in 1997 by the Catalan Association for Artificial Intelligence (ACIA

ACIA, the Catalan Association for Artificial Intelligence, is member of the European Coordinating Committee for Artificial Intelligence (ECCAI). http://www.acia.org.

We are very glad to celebrate this year the 10th anniversary of the International Conference of the ACIA (CCIA'07) in Sant Julià de Lòria (Andorra), October 25–26th, 2007. The good health of the Catalan AI community and its influence area is witnessed by the representative selection of papers gathered in this book and which were presented at CCIA'07.

The book is organized according to the different areas in which the papers were distributed for their presentation during the conference. Namely: Constraint Satisfaction, Agents, Data Processing, Case-Based Reasoning, Computer Vision, Natural Language Processing, Uncertainty and Fuzziness, Robotics, and Applications. Papers have been selected after a double blind review process in which distinguished AI researchers from all over Europe participated. Among the 54 papers received, 23 were selected as oral presentations and 23 as posters. The quality of the papers was very high in average, and the selection between oral or poster presentation was only based on the potential degree of discussion that a paper we thought could generate. We believe that all the papers collected in this volume can be of interest to any computer scientist or engineer interested in AI.

We would like to express our sincere gratitude to all the authors and members of the scientific and organizing committees that have made this conference a success. Our special thanks go also to the plenary speakers, Gábor Lugosi and Jordi Vitrià, for their effort in preparing very interesting lectures, and to the president of the ACIA, Núria Agell, for her kind support.

Sant Julià de Lòria, October 2007

Cecilio Angulo, Technical University of Catalonia (UPC)

Lluís Godo, AI Research Institute (IIIA), CSIC

We survey various variants of the randomized sequential forecasting problem when the forecaster has limited access to the past outcomes of the sequence to be predicted. This problem has various applications in on-line learning, learning in games, and information theory.

Social cognition is the main channel through which human beings access the social world, very much like vision and hearing are channels through which people access the physical world. For a long time, researchers have addressed the computational implementation of vision and hearing in domains like computer vision and speech recognition, but only early attempts have been made to do the same with social cognition. In other words: machines are beginning to be effective in handling perceptual aspects of the physical world, but up to now are devoid of social context.

In this paper we explain an estimation function for the crew scheduling problem in the coach transportation domain. Thanks to this function we obtain an estimation that is very close to the real cost of the solution and we can efficiently prune the search space with a branch and bound approach. Consequently we find the optimal solution in less time than with other estimations such as the Russian doll method.

Frequently, in the SAT and CSP communities, people talk about real-world problems, without any formal or precise definition of what “real-world” means. This notion is used as opposed to randomly generated problems and theoretical combinatorial principles, like the pigeonhole. People agree that modern SAT and CSP solvers perform well in these real-world problems with a hidden structure, and more so as more intelligent are the strategies used on them.

Here we define a formal notion, called the Strahler number, that measures the degree of structure of an unsatisfiable SAT instance. We argue why this notion corresponds to the informal idea of real-world problem. If a formula has an small Strahler number, then it has a lot of structure, and it is easy to prove it, even if it has many variables. We prove that there is a SAT solver, the Beame-Pitassi algorithm [2], that works on time O(n^s), being n the number of variables, and s the Strahler of the formula. We also show that Horn and 2-SAT unsatisfiable formulas, that can be solved in polynomial time, have Strahler number 1 and 2 respectively.

We compare the Strahler number with other notions defined with the same purpose like backdoors [15], and prove that the Strahler number can be arbitrarily smaller than the size of strong backdoors. We show the same relation for the size of cycle-cutsets and the treewidth in tree decompositions. Finally, we compare with the space of resolution calculus, defined for a different purpose.

With the arrival of high throughput genotyping techniques, the detection of likely genotyping errors is becoming an increasingly important problem. In this paper we are interested in errors that violate Mendelian laws. The problem of deciding if Mendelian error exists in a pedigree is NP-complete [1]. Existing tools dedicated to this problem may offer different level of services: detect simple inconsistencies using local reasoning, prove inconsistency, detect the source of error, propose an optimal correction for the error. All assume that there is at most one error. In this paper we show that the problem of error detection, of determining the minimum number of error needed to explain the data (with a possible error detection) and error correction can all be modeled using soft constraint networks. Therefore, these problems provide attractive benchmarks for weighted constraint network (WCN) solvers. Because of their sheer size, these problems drove us into the development of a new WCN solver toulbar2¹ which solves very large pedigree problems with thousands of animals, including many loops and several errors. This paper is a summary of an extended version to appear [17].

Meetings are an important vehicle for human communication. The Meeting Scheduling problem (MS) is a decision-making process affecting several people, in which it is necessary to decide when and where several meetings could be scheduled. MS is a naturally distributed problem which has a clear motivation to be tried using distributed techniques: people may desire to preserve the already planned meetings in their personal calendars during resolution. In this paper, we evaluate three distributed algorithms for MS according to efficiency and privacy loss. Two of these algorithms view MS as a Distributed Constraint Satisfaction problem.

The analysis of societies demonstrates the recurrent nature of small world topology in the interactions of elements in such worlds. The small world topology proves to have beneficial properties for system's performance in many cases, however there are also scenarios where the small world topology's properties negatively affect the system's outcome; thus in depth knowledge on the small world weaknesses is needed in order to develop new generations of artificial societies and new models of economic systems. In this paper, a multi-agent system based on request for proposal protocol and coalition formation organisational paradigm is used to analyse properties of small world social networks of agents. Experiments center on nodes in the network with high betweenness and in particular the distribution of agents in the population across these nodes. Results show that small world topology scenarios lose their beneficial properties when non-competitive agents are positioned as high betweeness nodes in the network.

We introduce Multimodal Logics of Normative Systems as a contribution to the development of a general logical framework for reasoning about normative systems over logics for Multi-Agent Systems. Given a multimodal logic L, with standard Kripke semantics, for every modality □_i and normative system η, we expand the language adding a new modality □_i^η with the intended meaning of □_i^ηφ, being “φ is obligatory in the context of the normative system η over the logic L”. In this expanded language we define the Multimodal Logic of Normative Systems over L, for any given set of normative systems N, and give a sound and complete axiomatisation for this logic, proving transfer results in the case that L and N are axiomatised by sets of Sahlqvist or shallow modal formulas.

Medical ontologies are developed to solve problems such as the demand for reusing, sharing and transmitting data. The unambiguous communication of complex and detailed medical concepts is a crucial feature in current medical information systems. In these systems, several agents must interact in order to share their results and, thus, they must use a medical terminology with a clear and non-confusing meaning. The paper presents the inclusion of an especially designed medical ontology in the HECASE2 multi-agent system. HECASE2 has been developed to help doctors in applying clinical guidelines to their patients in a semi-automatic fashion. In addition, it shows how intelligent agents may take profit from the modelled medical knowledge to coordinate their activities in the enactment of clinical guidelines.

This paper proposes to create a monitor of digital business ecosystems so that it provides agents with information to improve the behaviour of the ecosystem in terms of stability. This work proposes that, in digital ecosystems, monitor techniques can provide fundamental services and information. The final goal is to run the monitor algorithms, generate recommendation strategies and test them. A set of evaluation metrics must be defined as well. We want to provide an outline of some global indicators, such as heterogeneity and diversity, and establish relationships between agent behaviour and these global indicators of system performance.

In this article a possible solution to the problem of confidence management in multi-agent systems based on the FIPA specification, and containing both autonomous and mobile agents, is presented. Through ensuring unique original agent representation, using a Public Key Infrastructure and validating agent actions, the validity and uniqueness of actors and interactions is demonstrated.

Electronic Institutions are regulated environments populated by autonomous software agents that perform tasks on behalf of users. 3D Electronic Institutions extend EI with 3D Virtual Worlds, which provide an inmersive user interface so that humans can observe their agents' behaviors. In this manner, they represent a virtual analogy to real institutions. We propose to gain on realism on this analogy by adding intelligent objects to these institutions. Intelligent institutional objects (iObjects) exhibit autonomous and reactive behaviors. Furthermore, they present a limited level of proactivity such as self-configuration. Their inclusion has the advantage of improving the 3D Electronic Institutions architecture and both agent and user interactions within the institution.

Trust modelling is widely recognized as an aspect of essential importance in the construction of agents and multi agent systems (MAS). As a consequence, several trust formalisms have been developed over the last years. All of them have, in our opinion a limitation: they can determine the trustworthiness or untrustworthiness of the assertions expressed by a given agent, but they don't supply mechanisms for correcting this information in order to extract some utility from it. In order to overcome this limitation, we introduce the concept of reliability as a generalization of trust, and present Fuzzy Contextual Corrective Filters (FCCF) as reliability modeling methods loosely based on system identification and signal processing techniques. In order to prove their usefulness, we study their applicability to the appraisal variance estimation problem in the Agent Reputation and Trust (ART) testbed.

This paper studies the problem of adapting punishment policies in traffic scenarios. It focuses on a two-road junction scenario simulated by means of Simma, a Multi-Agent Based Simulation Tool. Adaptation is based on an adaptive neuro-fuzzy inference system (ANFIS) together with a hybrid learning algorithm (HLA). Basic punishment policy is provided through a knowledge base that specifies the conditions that must hold in order to assign different punishments. The aim of this paper is to show how the ANFIS system can improve this policy unsupervisedly.

Congresses and journals (CJ) can be like displays which can be used as a publishing medium of scholarly works when space is a scarce resource, and it is desirable to expose many papers, posters and communications (adverts of scientific work) to as wide a scientific audience as possible who will eventually cite them. Although the efficiency of such publishing systems can be improved if the CJ are aware of the identity and interests of the audience, this knowledge is difficult to acquire when users are not previously identified or inscribed in the CJ. To this end, we present Scholar Agent, an intelligent public agent, which helps CJ to select and display papers, posters and communications in response to scientists inscribed to particular sessions or tracks in the audience. Here, scientists are identified and their CJ review history tracked. Within Scholar Agent we have designed an agent system that utilises a new currency and an auction-based marketplace to efficiently select papers for the display. We show, by means of an empirical evaluation, that the performance of this auction-based mechanism when used with bidding strategy, efficiently selects the best paper in response to the audience presence (inscribed). This may have utility both presential or on-line CJ. We show how our scholarly publishing agents (Scholar Agents) will behave accordingly the private value of the paper by the scientist and how to link this initial private value with the own private value of the agents that are bench-marked with two other commonly applied selection methods for displaying papers in CJ.

This paper presents a methodology to transform a problem to make it suitable for classification methods, while reducing its complexity so that the classification models extracted are more accurate. The problem is represented by a dataset, where each instance consists of a variable number of descriptors and a class label. We study dataset transformations in order to describe each instance by a single descriptor with its corresponding features and a class label. To analyze the suitability of each transformation, we rely on measures that approximate the geometrical complexity of the dataset. We search for the best transformation minimizing the geometrical complexity. By using complexity measures, we are able to estimate the intrinsic complexity of the dataset without being tied to any particular classifier.

Record Linkage (RL) is an important component of data cleaning and integration and data processing in general. For years, many efforts have focused on improving the performance of the RL process, either by reducing the number of record comparisons or reducing the number of attribute comparisons, which reduces the computational time, but increases the amount of error. However, the real bottleneck of RL is the post-process, where the results have to be reviewed by experts that decide which pairs or groups of records are real links and which are false hits.

In this paper we show that exploiting the semantic relationships (e.g. foreign key), established between one or more data sources, makes it possible to find a new sort of semantic blocking method that improves the number of hits and reduces the amount of review effort.

One of the key issues in Case-Based Reasoning (CBR) is the efficient retrieval of cases when the case base is huge. In this paper we propose a case memory organization in two steps: 1) the case memory is organized using an unsupervised clustering technique, and 2) explanations for each cluster are constructed using all the cases associated to each one. The role of the explanations is twofold. On one hand they index the memory and allow CBR to do a selective retrieval. On the other hand, the explanation provide to the user additional information about why the cases have been both clustered together and retrieved.

Case-Based Reasoning (CBR) is a learning approach that solves current situations by reusing previous solutions that are stored in a case base. In the CBR cycle the reuse step plays an important role into the problem solving process, since the solution for a new problem is based in the available solutions of the retrieved cases. In classification tasks a trivial reuse method is commonly used, which takes into account the most frequently solution proposed by the set of retrieved cases. We propose an alternative reuse process; we call confidence-reuse method, which make a qualitative assessment of the information retrieved. This approach is focused on measuring the solution accuracy, applying some confidence predictors based in a k-NN classifier with the aim of analyzing and evaluating the information offered by the retrieved cases.