Artificial intelligence research and development

ARTIFICIAL INTELLIGENCE RESEARCH AND

DEVELOPMENT

Frontiers in Artificial Intelligence and

Applications

FAIA covers all aspects of theoretical and applied artificial intelligence research in the form of

monographs, doctoral dissertations, textbooks, handbooks and proceedings volumes. The FAIA

series contains several sub-series, including “Information Modelling and Knowledge Bases” and

“Knowledge-Based Intelligent Engineering Systems”. It also includes the biennial ECAI, the

European Conference on Artificial Intelligence, proceedings volumes, and other ECCAI – the

European Coordinating Committee on Artificial Intelligence – sponsored publications. An

editorial panel of internationally well-known scholars is appointed to provide a high quality

selection.

Series Editors:

J. Breuker, R. Dieng-Kuntz, N. Guarino, J.N. Kok, J. Liu, R. López de Mántaras,

R. Mizoguchi, M. Musen, S.K. Pal and N. Zhong

Volume 184

Recently published in this series

Vol. 183. C. Eschenbach and M. Grüninger (Eds.), Formal Ontology in Information Systems –

Proceedings of the Fifth International Conference (FOIS 2008)

Vol. 182. H. Fujita and I. Zualkernan (Eds.), New Trends in Software Methodologies, Tools

and Techniques – Proceedings of the seventh SoMeT_08

Vol. 181. A. Zgrzywa, K. Choroś and A. Siemiński (Eds.), New Trends in Multimedia and

Network Information Systems

Vol. 180. M. Virvou and T. Nakamura (Eds.), Knowledge-Based Software Engineering –

Proceedings of the Eighth Joint Conference on Knowledge-Based Software

Engineering

Vol. 179. A. Cesta and N. Fakotakis (Eds.), STAIRS 2008 – Proceedings of the Fourth Starting

AI Researchers’ Symposium

Vol. 178. M. Ghallab et al. (Eds.), ECAI 2008 – 18th European Conference on Artificial

Intelligence

Vol. 177. C. Soares et al. (Eds.), Applications of Data Mining in E-Business and Finance

Vol. 176. P. Zaraté et al. (Eds.), Collaborative Decision Making: Perspectives and Challenges

Vol. 175. A. Briggle, K. Waelbers and P.A.E. Brey (Eds.), Current Issues in Computing and

Philosophy

Vol. 174. S. Borgo and L. Lesmo (Eds.), Formal Ontologies Meet Industry

Vol. 173. A. Holst et al. (Eds.), Tenth Scandinavian Conference on Artificial Intelligence –

SCAI 2008

Vol. 172. Ph. Besnard et al. (Eds.), Computational Models of Argument – Proceedings of

COMMA 2008

Vol. 171. P. Wang et al. (Eds.), Artificial General Intelligence 2008 – Proceedings of the First

AGI Conference

ISSN 0922-6389

Artificial Intelligence Research and

Development

Proceedings of the 11th International Conference of

the Catalan Association for Artificial Intelligence

Edited by

Teresa Alsinet

Department of Computer Science, Universitat de Lleida, Spain

Josep Puyol-Gruart

Institut d’Investigació en Intel·ligència Artificial, CSIC, Spain

and

Carme Torras

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

Amsterdam • Berlin • Oxford • Tokyo • Washington, DC

© 2008 The authors and IOS Press.

All rights reserved. No part of this book may be reproduced, stored in a retrieval system,

or transmitted, in any form or by any means, without prior written permission from the publisher.

ISBN 978-1-58603-925-7

Library of Congress Control Number: 2008936675

Publisher

IOS Press

Nieuwe Hemweg 6B

1013 BG Amsterdam

Netherlands

fax: +31 20 687 0019

e-mail: [email protected]

Distributor in the UK and Ireland Distributor in the USA and Canada

Gazelle Books Services Ltd. IOS Press, Inc.

White Cross Mills 4502 Rachael Manor Drive

Hightown Fairfax, VA 22032

Lancaster LA1 4XS USA

United Kingdom fax: +1 703 323 3668

fax: +44 1524 63232 e-mail: [email protected]

e-mail: [email protected]

LEGAL NOTICE

The publisher is not responsible for the use which might be made of the following information.

PRINTED IN THE NETHERLANDS

Conference Organization

The CCIA 2008 conference was organized by the Associació Catalana d’Intel·ligència

Artificial and the Institut d’Investigació en Intel·ligència Artificial, CSIC.

General Chair

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

Organizing Chair

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

Program Committee Chair

Teresa Alsinet, Universitat de Lleida

Scientific Committee

Núria Agell, Universitat Ramon Llull

Josep Aguilar, Laboratoire d’Architecture et d’Analyse des Systèmes, CNRS

Guillem Alenyà, Institut de Robòtica i Informàtica Industrial, CSIC-UPC

René Alquézar, Universitat Politècnica de Catalunya

Cecilio Angulo, Universitat Politècnica de Catalunya

Carlos Ansótegui, Universitat de Lleida

Eva Armengol, Institut d’Investigació en Intel·ligència Artificial, CSIC

Ester Bernardó-Mansilla, Universitat Ramon Llull

Xavier Binefa, Universitat Autònoma de Barcelona

Vicent Botti, Universidad Politécnica de Valencia

Miguel Ángel Cazorla, Universitat d’Alacant

Jesús Cerquides, Universitat de Barcelona

Carlos Iván Chesñevar, Universidad Nacional del Sur, Argentina

Ulises Cortés, Universitat Politècnica de Catalunya

Josep Lluís de la Rosa, Universitat de Girona

Teresa Escrig, Universitat Jaume I

Marc Esteva, Institut d’Investigació en Intel·ligència Artificial, CSIC

Francesc Ferri, Universitat de València

Josep Maria Garrell, Universitat Ramon Llull

Héctor Geffner, Universitat Pompeu Fabra

Lluís Godo, Institut d’Investigació en Intel·ligència Artificial, CSIC

Elisabet Golobardes, Universitat Ramon Llull

Jordi Levy, Institut d’Investigació en Intel·ligència Artificial, CSIC

Chu Min Li, Université de Picardie

Angeles López, Universitat Jaume I

Beatriz López, Universitat de Girona

Ramon López de Mántaras, Institut d’Investigació en Intel·ligència Artificial, CSIC

Maite López-Sánchez, Universitat de Barcelona

v

Gábor Lugosi, Universitat Pompeu Fabra

Felip Manyà, Institut d’Investigació en Intel·ligència Artificial, CSIC

Rodrigo Martínez, Universidad de Murcia

David Masip, Universitat Oberta de Catalunya

Joaquim Meléndez, Universitat de Girona

Violeta Migallón, Universitat d’Alacant

Bernardo Morcego, Universitat Politècnica de Catalunya

Antonio Moreno, Universitat Rovira i Virgili

Pablo Noriega, Institut d’Investigació en Intel·ligència Artificial, CSIC

Jordi Planes, Universitat de Lleida

Enric Plaza, Institut d’Investigació en Intel·ligència Artificial, CSIC

Monique Polit, Université de Perpignan ‘Via Domitia’

Oriol Pujol, Universitat de Barcelona

Petia Radeva, Universitat Autònoma de Barcelona

Jordi Recasens, Universitat Politècnica de Catalunya

David Riaño, Universitat Rovira i Virgili

Juan Antonio Rodríguez, Institut d’Investigació en Intel·ligència Artificial, CSIC

Horacio Rodríguez, Universitat Politècnica de Catalunya

Ignasi Rodríguez-Roda, Universitat de Girona

Jordi Sabater-Mir, Institut d’Investigació en Intel·ligència Artificial, CSIC

Miquel Sànchez-Marrè, Universitat Politècnica de Catalunya

Sandra Sandri, Institut d’Investigació en Intel·ligència Artificial, CSIC

Vicenç Torra, Institut d’Investigació en Intel·ligència Artificial, CSIC

Aïda Valls, Universitat Rovira i Virgili

Llorenç Valverde, Universitat de les Illes Balears

Maria Vanrell, Universitat Autònoma de Barcelona

Wamberto Vasconcelos, University of Aberdeen

Glòria Vázquez, Universitat de Lleida

Jordi Vitrià, Universitat Autònoma de Barcelona

Additional Referees

Josep Argelich, Fernando de la Rosa, Isabela Drummond, Pere Garcia-Calvés

Organizing Committee

Lluís Godo, Institut d’Investigació en Intel·ligència Artificial, CSIC

Eva Armengol, Institut d’Investigació en Intel·ligència Artificial, CSIC

Joaquim Meléndez, Universitat de Girona

Organizing Institutions

Associació Catalana Institut d’Investigació

d’Intel·ligència Artificial en Intel·ligència Artificial

vi

Sponsoring Institutions

vii

This page intentionally left blank

Preface

There was a time when AI was seen by many as science fiction, i.e., the healthy en￾deavor 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 of￾fering 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 tech￾nology is becoming reasonably mature, companies are progressively relying on it. The

Catalan Association for Artificial Intelligence (ACIA1) tries to promote synergies within

the research community and also between the different actors playing a role in the de￾velopment of AI: from universities to industry, from governmental departments to the

information society, from entertainment enterprises to citizen services.

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 Represen￾tation and Logic; Machine Learning; Multidisciplinary Topics and Applications; Rea￾soning about Plans, Processes, and Actions; Robotics; and Uncertainty in AI. Papers ap￾pearing in this volume were subjected to rigorous blind review: two scientific committee

members (or in some cases, auxiliary reviewers) reviewed each paper under the super￾vision 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 aver￾age, and the selection between oral or poster presentation was only based on the poten￾tial 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.

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

Artificial Intelligence Research and Development

T. Alsinet et al. (Eds.)

IOS Press, 2008

© 2008 The authors and IOS Press. All rights reserved.

ix

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

x

Contents

Conference Organization v

Preface ix

Teresa Alsinet, Josep Puyol-Gruart and Carme Torras

Invited Talks

Web Mining or the Wisdom of the Crowds 3

Ricardo Baeza-Yates

AI at 50: From Programs to Solvers – Models and Techniques for General

Intelligence 4

Hector Geffner

Agents

Scalable and Efficient Multiagent Platform Closer to the Operating System 7

Juan M. Alberola, Jose M. Such, Agustin Espinosa, Vicent Botti and

Ana Garcia-Fornes

Designing Norms in Virtual Organizations 16

E. Argente, N. Criado, V. Julián and V. Botti

Distributed Barter-Based Directory Services 24

David Cabanillas, Steven Willmott and Ulises Cortés

Trading Paper Clips – An Analysis of “Trading Up” in Artificial Societies

Without Altruists 33

David Cabanillas, Steven Willmott and Ulises Cortés

Validation and Experimentation of a Tourism Recommender Agent Based

on a Graded BDI Model 41

Ana Casali, Lluís Godo and Carles Sierra

Agent Negotiation Dissolution 51

Nicolás Hormazábal, Josep Lluis de la Rosa i Esteve and Silvana Aciar

On Partial Deduction and Conversational Agents 60

Mariela Morveli-Espinoza and Josep Puyol-Gruart

Robustness in Recurrent Auctions for Resource Allocation 70

Victor Muñoz and Dídac Busquets

Using Electronic Institutions for Hospitals Chronic Disease Management and

Purchasing System 80

Ashkan Musavi, Maite Lopez-Sanchez, Jordi Campos and Marc Esteva

Categorization and Social Norms Support 88

Daniel Villatoro and Jordi Sabater-Mir

xi

Constraints, Satisfiability, and Search

How Hard Is a Commercial Puzzle: The Eternity II Challenge 99

Carlos Ansótegui, Ramon Béjar, Cèsar Fernández and Carles Mateu

Random SAT Instances à la Carte 109

Carlos Ansótegui, Maria Luisa Bonet and Jordi Levy

Privacy in Distributed Meeting Scheduling 118

Ismel Brito and Pedro Meseguer

Solving the Response Time Variability Problem by Means of Multi-Start and

GRASP Metaheuristics 128

Albert Corominas, Alberto García-Villoria and Rafael Pastor

An Algorithm Based on Structural Analysis for Model-Based Fault Diagnosis 138

Esteban R. Gelso, Sandra M. Castillo and Joaquim Armengol

Knowledge and Information Systems

Knowledge Discovery with Explained Case-Based Reasoning 151

Eva Armengol

Improving Pseudobagging Techniques 161

Angela Chieppa, Karina Gibert, Ignasi Gómez-Sebastià and

Miquel Sànchez-Marrè

Knowledge Discovery on the Response to Neurorehabilitation Treatment of

Patients with Traumatic Brain Injury Through an AI&Stats and Graphical

Hybrid Methodology 170

Karina Gibert, Alejandro García-Rudolph, Alberto García-Molina,

Teresa Roig-Rovira, Montserrat Bernabeu and José María Tormos

Using Ensemble-Based Reasoning to Help Experts in Melanoma Diagnosis 178

Ruben Nicolas, Elisabet Golobardes, Albert Fornells, Sonia Segura,

Susana Puig, Cristina Carrera, Joseph Palou and Josep Malvehy

Ergonomic Advice Through Case-Based Reasoning to Avoid Dangerous

Positions Adopted Using the Computer 186

Fernando Orduña Cabrera, Miquel Sànchez-Marrè,

Jesús Miguel García Gorrostieta and Samuel González López

Knowledge Representation and Logic

Probabilistic Dynamic Belief Logic for Image and Reputation 197

Isaac Pinyol, Jordi Sabater-Mir and Pilar Dellunde

Aggregation Operators and Ruled Surfaces 206

J. Recasens

New Challenges: Group Decision Systems by Means of Entropy Defined

Through Qualitative Reasoning Structures 215

Llorenç Roselló, Francesc Prats, Mónica Sánchez and Núria Agell

xii

Machine Learning

Voltage Sag Source Location from Extracted Rules Using Subgroup Discovery 225

Víctor Barrera, Beatriz López, Joaquim Meléndez and Jorge Sánchez

Statistical Monitoring of Injection Moulds 236

Xavier Berjaga, Joaquim Melendez and Alvaro Pallares

On the Dimensions of Data Complexity Through Synthetic Data Sets 244

Núria Macià, Ester Bernadó-Mansilla and Albert Orriols-Puig

Can Evolution Strategies Improve Learning Guidance in XCS? Design and

Comparison with Genetic Algorithms Based XCS 253

Sergio Morales-Ortigosa, Albert Orriols-Puig and Ester Bernadó-Mansilla

Intersection and Signed-Intersection Kernels for Intervals 262

Francisco J. Ruiz, Cecilio Angulo and Núria Agell

Multidisciplinary Topics and Applications

Representation of Discrete Quasi-Copulas Through Non-Square Matrices 273

Isabel Aguiló, Jaume Suñer and Joan Torrens

A System to Extract Social Networks Based on the Processing of Information

Obtained from Internet 283

Xavi Canaleta, Pablo Ros, Alex Vallejo, David Vernet and Agustín Zaballos

A Negotiation Styles Recommenders Approach Based on Computational Ecology 293

Josep Lluis de la Rosa, Gabriel Lopardo, Nicolás Hormazábal and

Miquel Montaner

CABRO: Winner Determination Algorithm for Single-Unit Combinatorial

Auctions 303

Víctor Muñoz and Javier Murillo

Nearest Neighbor Technique and Artificial Neural Networks for Short-Term

Electric Consumptions Forecast 313

Van Giang Tran, Stéphane Grieu and Monique Polit

Pattern Discovery in Melanoma Domain Using Partitional Clustering 323

David Vernet, Ruben Nicolas, Elisabet Golobardes, Albert Fornells,

Carles Garriga, Susana Puig and Josep Malvehy

Reasoning About Plans, Processes, and Actions

Using Ant Colony Systems with Pheromone Dispersion in the Traveling

Salesman Problem 333

José Carlos Becceneri, Sandra Sandri and E.F. Pacheco da Luz

Building Policies for Scrabble 342

Alejandro Gonzalez-Romero and René Alquezar

xiii

Robotics

Monocular Object Pose Computation with the Foveal-Peripheral Camera of

the Humanoid Robot Armar-III 355

Guillem Alenyà and Carme Torras

The SLAM Problem: A Survey 363

Josep Aulinas, Yvan Petillot, Joaquim Salvi and Xavier Lladó

An Approach for Mail-Robot Navigation Using a CBR Technique 372

Martí Navarro, Stella Heras and Vicente Julián

Representing Qualitative Trajectories by Autonomous Mobile Robots 380

J.C. Peris, J. Plana and M.T. Escrig

Object-Based Place Recognition for Mobile Robots Using Panoramas 388

Arturo Ribes, Arnau Ramisa, Ramon Lopez de Mantaras and Ricardo Toledo

Motion Segmentation: A Review 398

Luca Zappella, Xavier Lladó and Joaquim Salvi

Uncertainty in AI

On Fuzzy Description Logics 411

Àngel García-Cerdaña and Francesc Esteva

An Interval-Based Approach for Fault Isolation and Identification in Continuous

Dynamic Systems 421

Esteban R. Gelso, Sandra M. Castillo and Joaquim Armengol

Effects of Orness and Dispersion on WOWA Sensitivity 430

Vicenç Torra

Keyword Index 439

Author Index 441

xiv

Invited Talks