Ebook: Artificial Intelligence Research and Development

There was a time when AI was seen by many as science fiction, i.e., the healthy endeavor of speculating about the future. Now the future is here. AI has passed from being a visionary discipline to lying at the core of many commercial enterprises. AI programs scattered through the web influence nowadays our lives: by extracting profiles and offering tailored advertisement, helping us in our searches, establishing social networks, providing entertainment... And not just in the net, but also in the physical world. In Japan there are robots that guide customers through marketplaces advising them where to find the product matching their needs, and realistic replicas of university professors allow them to teach their lectures a hundred kilometers away from the classroom. Not to speak about intelligent prostheses and remote high-precision surgery.

In the Catalan-speaking world we do not have robots in marketplaces yet, but it is coming. Recently, the first commercial humanoid robot has been built. Since AI technology is becoming reasonably mature, companies are progressively relying on it. The Catalan Association for Artificial Intelligence (ACIA

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

One of the main activities of ACIA is the organization of this annual conference (CCIA), which reaches its 11th edition here in Sant Martí d'Empúries, October 22–24, 2008. The good health of basic and applied research in the Catalan AI community and its influence area shows up in the selection of representative papers submitted to CCIA 2008, which are gathered in this volume.

The book is organized according to the different areas in which the papers were distributed for their presentation during the conference. Namely: Agents; Constraints, Satisfiability, and Search; Knowledge and Information Systems; Knowledge Representation and Logic; Machine Learning; Multidisciplinary Topics and Applications; Reasoning about Plans, Processes, and Actions; Robotics; and Uncertainty in AI. Papers appearing in this volume were subjected to rigorous blind review: two scientific committee members (or in some cases, auxiliary reviewers) reviewed each paper under the supervision of the program chairs. The scientific committee members assigned to each paper were determined based on their expertise and their expressed interest in the paper, with an eye toward coverage of the relevant aspects of each paper. This year 54 papers were submitted to CCIA, with 45 accepted for oral or poster presentation at the conference. All accepted papers appear in this volume. The quality of the papers was 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, Ricardo Baeza-Yates and Hector Geffner, for their effort in preparing very interesting lectures, and to the president of ACIA, Núria Agell, for her kind support.

Sant Martí d'Empúries, October 2008

Teresa Alsinet, Universitat de Lleida

Josep Puyol-Gruart, Institut d'Investigació en Intel·ligència Artificial, CSIC

Carme Torras, Institut de Robòtica i Informàtica Industrial, CSIC-UPC

Agent technology demands support to build complex, open and large-scale applications. Therefore, efficient, scalable and robust Multiagent Platforms are needed. The performance of current Multiagent Platforms, which are usually developed in Java, has been tested in different studies. Results presented in these studies show that the performance of these Multiagent Platforms is not as good as one could expect. We present in this paper a different approach of a Multiagent Platform closer to the Operating System level to improve the performance achieved. This platform is focused on offering the main services required by a Multiagent platform and also improving the functionality of some of them, such as the messaging service. In this sense, we extend this functionality with advanced communication mechanisms such as agent groups and predefined interaction protocols. We also present a performance evaluation of the current platform implementation.

Virtual Organizations have been recently employed as an abstraction for modelling dynamical and complex systems. The Norm concept has arisen inside the Multi-Agent Theory for avoiding conflicts and ensuring coordination and cooperation in open environments. In this work, a desing of norms that govern Virtual Organizations is proposed, which is based on a service-oriented approach. Therefore, we define a formal normative language for mainly controlling service registering and usage. Thus, a better integration of both Web Services and MAS Technology is achieved.

The allocation of resources amongst a set of autonomous entities with contradicting interests is a recurring and relevant theme in distributed domains.

In this paper we present the design, implementation and evaluation of a distributed directory service based on a bartering mechanism in order to improve robustness in data retention. A directory service maps the names of network resources to their respective network addresses. A distributed directory service maintains this information not at a single node in a network, but across many nodes. The major challenge addressed in this paper is to build a workable system which not only responds to queries from users but A) ensures that directory items are never lost in the system and B) optimizes query response time with respect to different patterns of query arrival.

The remarkable recent story of Kyle MacDonald who, by means of a sequence of bartering exchanges between July 2005 and July 2006, managed to trade a small red paperclip for a full sized house in the town of Kipling Saskatchewan has inspired interesting debates about the nature of such feats and questions as to how they might come about. While bartering is arguably the world's oldest form of trade, there are still cases such as this which surprise us. Although there are many factors to consider in Kyle's achievement, his feat raises basic questions about the nature of the trades made and to what extent they are repeatable.

In this paper we provide an intuitive model for the type of trading environment experienced Kyle and study its consequences in order to analyze in particular whether such trading phenomena require altruistic agents to be present in the environment and extending the experience with multiple goal seeking agents.

In this paper, a validation and an experimentation of the use of graded BDI agents is reported. This agent model has been proposed to specify agents capable to deal with the environment uncertainty and with graded attitudes in an efficient way. As a case study we focus on a Tourism Recommender Agent specified using this agent model. The experimentation on the case study aims at proving that this agent model is useful to develop concrete agents showing different and rich behaviours. We also show that the results obtained by these particular recommender agents using graded attitudes improve those achieved by agents using non-graded attitudes.

In Multi-Agent Systems, agents negotiate between them for coordination and collaboration, but their preferences and the autonomous behaviour of each participant agent can lead the negotiation through several steps before they find a common agreement. As every agent in a negotiation isn't aware about the other's preferences or about their decision making process, the negotiation workflow needs to go through an intense communication process that not always ends with the most desirable agreement between them.

In this paper we propose a recommender system that suggests the best moment to end a negotiation. The recommendation is made from a trust evaluation of every agent in the negotiation based on their past negotiation experiences. For this, we introduce the Trust Aware Negotiation Dissolution algorithm.

Agents are situated autonomous entities that perceive and act in their environment, and communicate with other agents. An agent usually starts a conversation by querying another agent because it needs to satisfy a specific goal. This process allocates a new goal to the agent receiving the initial query, starting new dialogs with other agents, generating a recursive interaction. The generation of this kind of dialog is interesting when the system has the possibility of generating conditional answers with imprecise and uncertain values. We consider simple deliberative rule-based agents that proactively try to satisfy their goals. The mechanism to achieve this dialogs is based in the specialization of the mental state of agents, by means of the partial deduction of rule bases.

Resource allocation problems where resources have to be assigned to tasks in such a way that no resource gets overused can be solved using recurrent auctions. In dynamic environments where unexpected changes may occur, searching the optimal solution may not be the best choice as it would be more likely to fail. In these cases a robust solution is preferable. In this paper we present a robustness mechanism for auctions, producing feasible and near optimal solutions even if non-planned events occur.

Use of multi-agent systems (MAS) in health-care domains is increasing. MAS is an appropriate technique for many medical domains due to the characteristics of the problems in this area. According to the World Health Organization (WHO) health care systems worldwide are faced with the challenge of responding to the needs of people with chronic conditions such as diabetes, heart failure and mental illness. Chronic disease management (CDM) is a systematic approach to improve health care for people with chronic disease. Electronic Institutions (EI), as agent technology, is considered a suitable paradigm for complex environments providing structured frameworks for multi-agent systems to regulate agents' interactions. In this paper we introduce the HCDMP System which is an electronic institution to improve the Hospitals Chronic Disease Management and Purchasing processes. HCDMP system provides a number of recommended services to the patients and aims to advance the self care as a well proven and highly effective means of improving the care of chronic diseases.

Social Norms proliferate in societies as a mechanism for self-organization. This kind of norms are not enforced by a central authority and the individuals of the society are those responsible for their generation and maintenance. The maintenance process is what is known as norm support and is supported by several mechanisms like for example laws, social proof, dominance, etc. We believe that agent based simulation is a suitable technique for investigating this topic. In this paper we present an overview of the work we have been developing in this area. The ‘Find and Share (and Exchange)’ game is introduced as the environment where to prove our hyphotheses on social norms. After that, we present an initial categorization on the possible social norms in our environment. Finally, some mechanisms are studied to observe its effectiveness solving the norm suport problem.

Recently, edge matching puzzles, an NP-complete problem, have received, thanks to money-prized contests, considerable attention from wide audiences. We consider these competitions not only a challenge for SAT/CSP solving techniques but also as an opportunity to showcase the advances in the SAT/CSP community to a general audience. This paper studies the NP-complete problem of edge matching puzzles focusing on providing generation models of problem instances of variable hardness and on its resolution through the application of SAT and CSP techniques. From the generation side, we also identify the phase transition phenomena for each model. As solving methods, we employ both; SAT solvers through the translation to a SAT formula, and two ad-hoc CSP solvers we have developed, with different levels of consistency, employing several generic and specialized heuristics. Finally, we conducted an extensive experimental investigation to identify the hardest generation models and the best performing solving techniques.

Many studies focus on the generation of hard SAT instances. The hardness is usually measured by the time it takes SAT solvers to solve the instances. In this preliminary study, we focus on the generation of instances that have computational properties that are more similar to real-world instances. In particular, instances with the same degree of difficulty, measured in terms of the tree-like resolution space complexity. It is known that industrial instances, even with a great number of variables, can be solved by a clever solver in a reasonable amount of time. One of the reasons may be their relatively small space complexity, compared with randomly generated instances.

We provide two generation methods of k-SAT instances, called geometrical and the geo-regular, as generalizations of the uniform and regular k-CNF generators. Both are based on the use of a geometric probability distribution to select variables. We study the phase transition phenomena and the hardness of the generated instances as a function of the number of variables and the base of the geometric distribution. We prove that, with these two parameters we can adjust the difficulty of the problems in the phase transition point. We conjecture that this will allow us to generate random instances more similar to industrial instances, of interest for testing purposes.

Meetings are an important vehicle for human interaction. The Meeting Scheduling problem (MS) considers several agents, each holding a personal calendar, and a number of meetings which have to be scheduled among subsets of agents. MS is a naturally distributed problem with a clear motivation to avoid centralization: agents desire to keep their personal calendars as private as possible during resolution. MS can be formulated as Distributed CSP, but due to the form of its constraints the PKC model does not bring any benefit here. We take entropy as a measure for privacy, and evaluate several distributed algorithms for MS according to efficiency and privacy loss. Experiments show interesting results with respect to the kind of tested algorithms.

The Response Time Variability Problem (RTVP) is an NP-hard scheduling optimization problem that has recently appeared in the literature. This problem has a wide range of real-life applications in, for example, manufacturing, hard real-time systems, operating systems and network environments. The RTVP occurs whenever models, clients or jobs need to be sequenced to minimize variability in the time between the instants at which they receive the necessary resources. The RTVP has been already solved in the literature with a multi-start and a GRASP algorithm. We propose an improved multi-start and an improved GRASP algorithm to solve the RTVP. The computational experiment shows that, on average, the results obtained with our proposed algorithms improve on the best obtained results to date.

This paper presents a diagnosis system in which, an algorithm automatically finds all minimal structurally overdetermined (MSO) sets in a structural model of a system. It combines a first set of MSO sets to get the additional MSO sets, which were obtained after determining a complete matching between equations and unknown variables. Finding the complete set is useful for the diagnosis task increasing the fault isolability due to the fact that it can provide different signatures to each fault. The efficiency of the algorithm for finding all MSO sets is illustrated using the DAMADICS benchmark, which is a pneumatically-actuated control valve.

The goal of Knowledge Discovery is to extract knowledge from a set of data. Most common techniques used in knowledge discovery are clustering methods, whose goal is to analyze a set of objects and obtain clusters based on the similarity among these objects. A desirable characteristic of clustering results is that these should be easily understandable by domain experts. In fact, these are characteristics that exhibit the results of eager learning methods (such as ID3) and lazy learning methods when used for building lazy domain theories. In this paper we propose LazyCL, a procedure using a lazy learning method to produce explanations on clusters of unlabeled cases. The analysis of the relations among these explanations converges to a correct clustering of the data set.

We present an important improvement related to the computation and use of Mutual Information index in Pseudobagging, a technique that adapts “bagging” to unsupervised context. The Mutual Information index plays a key role in this technique, assessing the quality of a partition. We propose the use of such an index to improve the Pseudobagging voting scheme for determining the final partition of the data. Issues related to the estimation of Mutual Information index in the multivariate continuous case become crucial for the application of Pseudobagging to real data: we discuss some practical approaches to computation in this situation. Finally, experimental results are presented, related to application of new “pooled voting” scheme and to the evaluation of the impact of different computing methods for Mutual Information.

Neuropsychological rehabilitation seeks to reduce cognitive disability after acquired brain injury. However, until now, there is not enough data to allow exercise of neuropsychological rehabilitation based on scientific Class I evidence. From the medical point of view, the purpose of this work is to develop a classificatory tool to identify different populations of patients based on the characteristics of deficit and response to treatment. This Knowledge Discovery problem has been faced by using exogenous clustering based on rules, an hybrid AI and Statistics technique, which combines some Inductive Learning (from AI) with clustering (from Statistics) to extract knowledge from certain complex domains in form of typical profiles. In this paper, the results of applying this technique to a sample of patients with Traumatic Brain Injury are presented and their advantages with regards to other more classical analysis approaches are discussed.