Ebook: Artificial Intelligence Research and Development
For almost twenty years the Catalan Association of Artificial Intelligence (ACIA) has been promoting cooperation between researchers in artificial intelligence within the Catalan speaking community.
This book presents the proceedings of the 16th International Conference (CCIA 2013), held at the University of Vic (UVIC), Catalonia, Spain, in October 2013. This annual conference aims to foster discussion of the latest developments in artificial intelligence within the community of Catalan countries, as well as amongst members of the AI community worldwide.
The book contains the 26 full papers, 5 short papers and 12 poster presentations from the conference, which are grouped under the following topics: relational learning, planning; satisfiability and constraints; perception and image processing; preprocessing; patterns extraction and learning; post-processing, model interpretability and decision support; recommenders, similarity and CBR; and multiagent systems.
The Catalan Association of Artificial Intelligence (ACIA, http://www.acia.org) was founded in September 1994 as a non-profit association for the development and dissemination of Artificial Intelligence (AI) in Catalan society. ACIA's main goal is to support communication between the persons and organizations involved in AI as well as to promote social, cultural, scientific, economic and governmental awareness of AI. Today, ACIA is the backbone of the Catalan AI community, which is quite active at both a local and international level and from the academic to the corporate sector. ACIA is a member of the European Coordinating Committee for Artificial Intelligence (ECCAI).
The first meetings of ACIA were created in 1995 with the aim of becoming the forum of the Catalan AI community. The first meetings were local and informal, but soon the association held their meetings in the form of Conferences. In 1998 the first International Conference of the Catalan Association for Artificial Intelligence (the CCIA), took place in Tarragona, with an open approach to the international community. From then onwards, every year the CCIA has been organized in all the Catalan lands, including many cities in Catalonia, but also in the Balearic Islands and Valencian provinces, in Spain, and main cities in foreign countries retaining the Catalan culture, like Perpignan, in Catalunya-Nord (Southern France), Andorra or l'Alghero in Sardegna (Italy).
The CCIA'2013 is the 16th edition of the conference and it is held in the city of Vic, placed in the geographical center of Catalonia, with an ancient Iberian origin (Fourth Century BC), a roman settlement dating back to the Third Century BC, and playing a central role in Catalan history from the middle ages to the Eighteenth Century. This edition of the conference is organized by the Digital Technologies Group of Universitat the Vic, with the help of the Knowledge Engineering and Machine Learning Group (KEMLG) of the Universitat Politècnica de Catalunya-BarcelonaTech and the Grup de Tecnologia Informàtica i Intel.ligència Artificial (GTI-IA) of the Computer Systems and Computation Department of the Universitat Politècnica de València.
The CCIA is today consolidated as the annual meeting point of the Catalan AI community, which can be seen as a strong community, with a lot of scientific activity and a good level of internationalization. Most of the institutions in the Catalan territory support the conference by participating in the scientific committee or by submitting contributions. The number of submissions and the wide range of AI topics addressed reflects the good health of this community. A 17.5 authors sharing authorship in the contributed papers reflect the internationalization of the Catalan AI community. Also, a non-neglectable number of researchers formed in the Catalan AI community are now developing their scientific activities in international research centers and some of them have been supporting CCIA as invited speakers in past editions.
In this edition, we are very honored to have been supported by a Scientific Committee, including members from all the Catalan, Balearic and Valencian universities, both public and private, from the main AI research institutes in Catalonia, the Basque Country, Southern France and international members from Australia, Austria, Germany, France, Italy, Romania, Switzerland and Venezuela.
As was said before, it is a great pleasure to realize that most of the members of the community participate in the conference by sending their contributions. In the current edition, CCIA'2013 received 50 original contributions from Catalonia (involving 100 authors), Valencia (7 authors), the rest of Spain (5), Belgium (1), Canada (1), Germany (2), Italy (2), Jamaica (1), Mexico (2), Ukraine (1), United Kingdom (4), United States (1). Submitted contributions were carefully reviewed by two or three members of the Scientific Committee. Because in CCIA single track is preferred over parallel sessions, the 26 papers with the best evaluation for their relevance to CCIA topics, originality, technical validity, relevance of conclusions, and for their potential to raise interesting discussions, were accepted as regular full papers; 5 were accepted as short papers with oral presentation and 12 as posters.
The papers have been organized around different topics, with a good coverage of the different AI branches and specializations, from more theoretical to more applied issues and from more cognitive to more perceptive approaches, which shows the good health of AI in the Catalan community. Topics include Relational Learning; Planning, Satisfiability and Constraints; Perception and Image Processing; Preprocessing; Patterns extraction in general (including Data Mining, Modelling, Learning, Soft-Computing and hybrid approaches); Post-processing, Model Interpretability and Decision Support; Recommenders, Similarity and CBR; and Multiagent Systems. The sessions of the conference are organized according to these topics, as are the sections of this book.
Accordingly, the two invited speakers for CCIA'2013 cover different aspects of AI. Carme Torras, from the Institut de Robòtica i Informàtica Industrial, CSIC-UPC, will speak about the advances of AI in robotics. Vladimir Estivill, from Griffith University, Australia, will talk about model-driven development by integrating planning and reasoning. From the local research institute (IRI) with international projection, to a foreign researcher linked to a Catalan university (UPF); from the most perceptive to the most cognitive AI approach, we hope that this CCIA provides a rich and fruitful forum for discussion, updating, networking and continues to strengthen the quality of the Catalan AI community and its related researchers.
We would like to express our gratitude to all the authors who supported this edition of CCIA by sending their contributions, to all members of the scientific and organizing committees who worked hard to make this conference a success. Special thanks to the invited speakers Carme Torras and Vladimir Estivill, for bringing interesting lectures to the conference, and to Vicenç Torra, president of ACIA, for his kind support and involvement.
Vic, Catalunya, October 2013
Karina Gibert, Chair of Scientific Committee, Universitat Politècnica de Catalunya
Vicent Botti, General Chair, Universitat Politècnica de València
Ramon Reig-Bolaño, Local Organizing Committee Chair, Universitat de Vic
Logic-labeled finite-state machines are a formal mechanisms to represent behavior. These models have several advantages over event-driven finite-state machines. They have a formal semantics that enables model-checking; that is, formal verification. More importantly, they can be executed concurrently and produce simple behaviors for embedded systems, or more advanced behaviors for robotic systems (like feedback-loop control). We illustrate their potential to integrate high level capabilities like reasoning and planing and cover the spectrum of reactive architectures to deliberative architectures. Examples of these approach will be presented ranging from ubiquitous cases in requirements engineering to the realm of robots interacting, like RoboCup. Finally, we show we can use these logic-labeled finite-state machines to model dynamic objects in an environment and use traditional planing to guide robots in even potentially non-deterministic environments.
The Turing test (1950) sought to distinguish whether a speaker engaged in a computer talk was a human or a machine . Science fiction has immortalized several humanoid robots full of humanity, and it is nowadays speculating about the role the human being and the machine may play in this “pas à deux” in which we are irremissibly engaged . Where is current robotics research heading to? Industrial robots are giving way to social robots designed to aid in healthcare, education, entertainment and services. In the near future, robots will assist disabled and elderly people, do chores, act as playmates for youngsters and adults, and even work as nannies and reinforcement teachers. This poses new requirements to robotics research, since social robots must be easy to program by non-experts , intrinsically safe , able to perceive and manipulate deformable objects [2, 8], tolerant to inaccurate perceptions and actions [4, 7] and, above all, they must be endowed with a strong learning capacity [1, 9] and a high adaptability  to non-predefined and dynamic environments. Taking as an example projects developed at the Institut de Robòtica i Informàtica Industrial (CSIC-UPC), some of the scientific, technological and ethical challenges [5, 11, 13] that this robotic evolution entails will be showcased.
We present a new approach lo learn from relational data based on re-representation of the examples. This approach, called property-based re-representation is based on a new analysis of the structure of refinement graphs used in ILP and relational learning in general. This analysis allows the characterization of relational examples by a set of multi-relational patterns called properties. Using them, we perform a property-based re-representation of relational examples that facilitates the development of relational learning techniques.
In many real-world applications we have at our disposal a limited number of inputs in a theoretical database with full information, and another part of experimental data with incomplete knowledge for some of their features. These are cases that can be addressed by a label propagation process. It is a widely studied approach that may acquire complexity if new constraints in the new unlabeled data that should be taken into account are found. A kernel embedding process together with a simple label propagation algorithm will be the main tools to propagate labels by the use of all types of available information. An experimental study of biofilm development in drinking water pipes propagated through pipes belonging to a complete water supply network is approached. As a result, the proposal is a suitable and efficient way to deal with practical data, based on previous theoretical studies by the constrained label propagation process introduced.
Hierarchical graphs are a frequent solution for capturing symbolic data due the importance of hierarchies for defining knowledge. In these graphs, relations among elements may contain large portions of the element's semantics. However, knowledge discovery based on analyzing the patterns of hierarchical relations is rarely used. We outline four inference based algorithms exploiting semantic properties of hierarchically represented knowledge for producing new links, and test one of them on a generalization of Cyc's KB. Finally, we argue why such algorithms can be useful for unsupervised learning and supervised analysis of a KB.
The hide-and-seek game is considered an excellent domain for studying the interactions between mobile robots and humans. Prior to the implementation and test in our mobile robots TIBI and DABO, we have been devising different models and strategies to play this game and comparing them extensively in simulations. We propose the use of MOMDP (Mixed Observability Markov Decision Processes) models to learn a good policy to be applied by the seeker. For two players the amount of states is quadratic in the number of discrete map cells. The number of cells were reduced by using a two-level MOMDP, where the policy is computed on-line at the top level with a reduced number of states independent of the grid size. In this paper, we also introduce a new fast heuristic method for the seeker and compare its performance to both off-line and on-line MOMDP approaches. We show simulation results in maps of different sizes against two types of automated hiders.
In this paper we present FLAP, a forward-chaining planner which works with partial-order plans. Unlike similar planners like OPTIC, FLAP follows the least-commitment principle of the traditional partial-order planning algorithm without establishing additional ordering constraints among actions during the search. This leads to the generation of more general plans, with more flexible executions, that can be easily adapted to temporal planning or multi-agent planning. Despite the overhead caused by working with partial-order plans, experimental results show that FLAP outperforms OPTIC in many domains.
This paper investigates a new exact method for constructing optimal covering arrays based on first encoding the problem as a Partial MaxSAT instance, and then solving the resulting instance with a state-of-the-art MaxSAT solver. To this end, we define an original MaxSAT encoding for covering arrays, and report on the experimentation performed to evaluate our MaxSAT-based approach. The obtained results indicate that MaxSAT is a good alternative for constructing optimal covering arrays, and it is worth to further investigate this new research direction in the area of combinatorial designs.
The Routing and Wavelength Assignment (RWA) problem is an optical networking problem aiming to improve data transmission by eliminating optoelectronic conversions through the network. RWA problem is in the set of NP-complete problems  and thus is also an interesting problem form a computational point of view. It can be solved in different flavours, being the Static Lightpath Establishment (SLE) the one we consider here. In this work we present ASP encodings for the problem. Then, we solve them with ASP solvers and we empirically compare them with previous approaches.
Screening programs in high-risk populations constitute a major asset in the struggle against Breast Cancer. Currently, screening programs focus in the task of analyzing digital mammography images. In this sense, computer vision techniques are suitable to provide decisive help in this task. In particular, computer-based texture image analysis is an important discipline that is able to gather some evidences oriented to the early diagnosis of breast cancer, such as the analysis of mammographic density. In order to extract textural features, Gabor Filters have been extensively used. The image is filtered with a set of Gabor Filters having different frequencies, resolutions and orientations. In this paper, we address the problem of mammogram images analysis by means of a Gabor Filter bank. Specifically, we analyze the texture features provided by the Gabor Filter bank in three regions, namely: tumor region, tumor-border region, and normal tissue region. An important objective is to reach a suitable subset of Gabor Filters that produce a collection of texture features sufficiently different to distinguish among the three regions. In this work, we have used the Choquet integral operator in order to score each filter in the bank, giving thus the possibility to select the most appropriate Gabor Filters to face the task of identifying relevant features for each of the three regions mentioned above. A learning procedure based on optimization is used to find the appropriate parameters for the Choquet integral, taking into account some training examples and constraints.
Qualitative image descriptors are combined with domain knowledge (object feature detectors and qualitative definitions) for generating narratives which provide cognitive interpretations of images in a specific domain. This approach is tested and analysed in two study cases: (i) a robot navigating through the corridors of the TI building at Universitat Jaume I (Spain) and (ii) a ambient intelligent system in corporated at Cartesium building at Universitäat Bremen (Germany).
Many techniques to reduce the cost at test time in large-scale problems involve a hierarchical organization of classifiers, but are either too expensive to learn or degrade the classification performance. Conversely, in this work we show that using ensembles of randomized hierarchical decompositions of the original problem can both improve the accuracy and reduce the computational complexity at test time. The proposed method is evaluated in the ImageNet Large Scale Visual Recognition Challenge'10, with promising results.
Detecting hands in multi-modal RGB-Depth visual data has become a challenging Computer Vision problem with several applications of interest. This task involves dealing with changes in illumination, view point variations, the articulated nature of the human body, the high flexibility of the wrist articulation, and the deformability of the hand itself. In this work, we propose an accurate and efficient automatic hand detection scheme to be applied in Human-Computer Interaction (HCI) applications in which the user is seated at the desk and, thus, only the upper body is visible. Our main hypothesis is that hand landmarks remain at a nearly constant geodesic distance from an automatically located anatomical reference point. In a given frame, the human body is segmented first in the depth image. Then, a graph representation of the body is built in which the geodesic paths are computed from the reference point. The dense optical flow vectors on the corresponding RGB image are used to reduce ambiguities of the geodesic paths' connectivity, allowing to eliminate false edges interconnecting different body parts. Finally, we are able to detect the position of both hands based on invariant geodesic distances and optical flow within the body region, without involving costly learning procedures.
Gait Recognition is a biometric application that aims to identify a person by analyzing his/her gait. Common methods for gait recognition rely on supervised machine learning techniques and step detection methods. However, the latter has been showed to provide poor performances in ambulatory conditions . In this paper, a Granular Computing approach that does not require to detect steps is applied to the accelerometers signals obtained from gait. This approach involves information granules, based on density measures and collected from a reconstructed attractor, that can be obtained at different granularity levels and hence gather information at different scales. The performance of the method is evaluated on the task of recognizing 12 people by his/her gait.
Oral communication competence is defined on the top of relevant skills for professional and personal life. Because of the importance of communication in our daily activities it is crucial to study methods to improve our communication capability and therefore learn how to express ourselves better. In this paper, we propose a multi-modal RGB, depth, and audio data description and fusion approach in order to recognize behavioral cues and train classifiers able to predict the quality of oral presentations. The system is tested on real defenses from Bachelor's thesis presentations and presentations from an 8th semester Bachelor's class at Universitat de Barcelona. Using as ground truth the scores assigned by the teachers, our system achieved high classification rates categorizing and ranking the quality of presentations into different groups.
The quantitative analysis of shapes is required in some research fields, such as taxonomy, agronomy, ecology, medicine, among others. The quantification of an object shape, or a biological entity shape as extension, is usually performed on its closed contour data. Normally, the closed contours are automatically extracted from digital images. In these fields, the most used contour descriptors are the Elliptical Fourier Descriptors (EFD). In this paper we propose a new contour descriptor based on the Discrete Hartley Transform (DHT) that uses only half of the coefficients required by EFD to obtain a contour approximation with similar error measure. The proposed closed contour descriptors provide an excellent capability of contour information compression being suitable to be applied as input parameters of any shape classifier. The proposed parameterization can represent all kinds of closed curves and also it has the advantage that both the parameterization and the reconstructed shape from a reduced amount of them can be computed very efficiently by the fast Discrete Hartley Transform (DHT) algorithm.
Unsupervised feature selection is a dificult task because a reference partition is not available to evaluate the relevance of the features. Different consensus clustering methods have proposed to use external validity indices to assess the agreement of partitions obtained by clustering algorithms with difierent parameter values. Theses indices are independent of the characteristics of the attributes describing the data, the way the partitions are represented or the shape of the clusters. This independence allows to assess the similarity of partitions with different subsets of attributes.
The hypothesis of this paper is that the clustering of a dataset with all the attributes, even of poor quality, can be used as the basis for the exploration of the space of feature subsets. The proposal is to use external validation indices as the measure used to assess how well this information is preserved by a subset of the original attributes.
This paper focuses on an experimental feature selection for the images of otoliths in order to validate their effectiveness in a multiclass classifier used to resolve an automatic otolith identification process. Otoliths are calcareus structures found in the inner ear of fishes and are used to identifie species, populations, age and can be used in other ecological studies. The most relevant result confirms the importance of high order EFD coefficients to discriminate close shape specimens or populations.
The vector space model is a document set representation widely used in information retrieval and text mining. When we are dealing with confidential documents the use of this model should be restricted in order to preserve the confidentiality and anonymity of the original documents. Following this idea, we introduce a method to anonymize the document vector space, allowing thus the use of analytic techniques without disclosing private information. The proposed method is inspired by microaggregation, a popular technique used in statistical disclosure control, which ensures privacy by the satisfaction of the k-anonymity principle.