Mapas gráficos para la visualización de relaciones en sistemas de recomendación

La presente tesis doctoral tiene como objetivo el diseñar un modelo de inferencia visual y sencillo que permita a los usuarios no registrados en un sistema de recomendación inferir por ellos mismos las recomendaciones a partir de sus gustos. Este modelo estará basado en la representación de las relaciones de similaridad entre los ítems. Estas representaciones visuales (que llamaremos mapas gráficos), nos muestran en que lugar se encuentran los ítems más representativos y que ítems son votados de una manera más parecida en función de los votos emitidos por los usuarios del sistema de recomendación. Los mapas gráficos obtenidos, toman la forma de los árboles filogenéticos (que son árboles que muestran las relaciones evolutivas entre varias especies), que muestran la similitud numérica entre cada par de ítems que se consideran similares. Como caso de estudio se muestran en este trabajo los resultados obtenidos utilizando la base de datos de MovieLens 1M, que contiene 3900 películas (ítems). ABSTRACT The present PhD thesis has the objective of designing a visual and simple inference model that allow users, who are not registered in a recommendation system, to infer by themselves the recommendations from their tastes. This model will be based on the representation of relations of similarity between items. These visual representations (called graphical maps) show us where the most representative items are, and items are voted in a similar way based on the votes cast by users of the recommendation system. The obtained graphs maps take form of phylogenetic trees (which are trees that show the evolutionary relationships among various species), that give you an idea about the numeric similarity between each pair of items that are considered similar. As a case study we provide the results obtained using the public database Movielens 1M, which contains 3900 movies.

Cooperative Multi-robot Patrolling: A study of distributed approaches based on mathematical models of game theory to protect infrastructures

El principio de Teoría de Juegos permite desarrollar modelos estocásticos de patrullaje multi-robot para proteger infraestructuras criticas. La protección de infraestructuras criticas representa un gran reto para los países al rededor del mundo, principalmente después de los ataques terroristas llevados a cabo la década pasada. En este documento el termino infraestructura hace referencia a aeropuertos, plantas nucleares u otros instalaciones. El problema de patrullaje se define como la actividad de patrullar un entorno determinado para monitorear cualquier actividad o sensar algunas variables ambientales. En esta actividad, un grupo de robots debe visitar un conjunto de puntos de interés definidos en un entorno en intervalos de tiempo irregulares con propósitos de seguridad. Los modelos de partullaje multi-robot son utilizados para resolver este problema. Hasta el momento existen trabajos que resuelven este problema utilizando diversos principios matemáticos. Los modelos de patrullaje multi-robot desarrollados en esos trabajos representan un gran avance en este campo de investigación. Sin embargo, los modelos con los mejores resultados no son viables para aplicaciones de seguridad debido a su naturaleza centralizada y determinista. Esta tesis presenta cinco modelos de patrullaje multi-robot distribuidos e impredecibles basados en modelos matemáticos de aprendizaje de Teoría de Juegos. El objetivo del desarrollo de estos modelos está en resolver los inconvenientes presentes en trabajos preliminares. Con esta finalidad, el problema de patrullaje multi-robot se formuló utilizando conceptos de Teoría de Grafos, en la cual se definieron varios juegos en cada vértice de un grafo. Los modelos de patrullaje multi-robot desarrollados en este trabajo de investigación se han validado y comparado con los mejores modelos disponibles en la literatura. Para llevar a cabo tanto la validación como la comparación se ha utilizado un simulador de patrullaje y un grupo de robots reales. Los resultados experimentales muestran que los modelos de patrullaje desarrollados en este trabajo de investigación trabajan mejor que modelos de trabajos previos en el 80% de 150 casos de estudio. Además de esto, estos modelos cuentan con varias características importantes tales como distribución, robustez, escalabilidad y dinamismo. Los avances logrados con este trabajo de investigación dan evidencia del potencial de Teoría de Juegos para desarrollar modelos de patrullaje útiles para proteger infraestructuras. ABSTRACT Game theory principle allows to developing stochastic multi-robot patrolling models to protect critical infrastructures. Critical infrastructures protection is a great concern for countries around the world, mainly due to terrorist attacks in the last decade. In this document, the term infrastructures includes airports, nuclear power plants, and many other facilities. The patrolling problem is defined as the activity of traversing a given environment to monitoring any activity or sensing some environmental variables If this activity were performed by a fleet of robots, they would have to visit some places of interest of an environment at irregular intervals of time for security purposes. This problem is solved using multi-robot patrolling models. To date, literature works have been solved this problem applying various mathematical principles.The multi-robot patrolling models developed in those works represent great advances in this field. However, the models that obtain the best results are unfeasible for security applications due to their centralized and predictable nature. This thesis presents five distributed and unpredictable multi-robot patrolling models based on mathematical learning models derived from Game Theory. These multi-robot patrolling models aim at overcoming the disadvantages of previous work. To this end, the multi-robot patrolling problem was formulated using concepts of Graph Theory to represent the environment. Several normal-form games were defined at each vertex of a graph in this formulation. The multi-robot patrolling models developed in this research work have been validated and compared with best ranked multi-robot patrolling models in the literature. Both validation and comparison were preformed by using both a patrolling simulator and real robots. Experimental results show that the multirobot patrolling models developed in this research work improve previous ones in as many as 80% of 150 cases of study. Moreover, these multi-robot patrolling models rely on several features to highlight in security applications such as distribution, robustness, scalability, and dynamism. The achievements obtained in this research work validate the potential of Game Theory to develop patrolling models to protect infrastructures.

Identification of logically related heap regions

This paper introduces a novel technique for identifying logically related sections of the heap such as recursive data structures, objects that are part of the same multi-component structure, and related groups of objects stored in the same collection/array. When combined withthe lifetime properties of these structures, this information can be used to drive a range of program optimizations including pool allocation, object co-location, static deallocation, and region-based garbage collection. The technique outlined in this paper also improves the efficiency of the static analysis by providing a normal form for the abstract models (speeding the convergence of the static analysis). We focus on two techniques for grouping parts of the heap. The first is a technique for precisely identifying recursive data structures in object-oriented programs based on the types declared in the program. The second technique is a novel method for grouping objects that make up the same composite structure and that allows us to partition the objects stored in a collection/array into groups based on a similarity relation. We provide a parametric component in the similarity relation in order to support specific analysis applications (such as a numeric analysis which would need to partition the objects based on numeric properties of the fields). Using the Barnes-Hut benchmark from the JOlden suite we show how these grouping methods can be used to identify various types of logical structures allowing the application of many region-based program optimizations.

Space-time Measurements of Oceanic Sea States

Stereo video techniques are effective for estimating the space–time wave dynamics over an area of the ocean. Indeed, a stereo camera view allows retrieval of both spatial and temporal data whose statistical content is richer than that of time series data retrieved from point wave probes. We present an application of the Wave Acquisition Stereo System (WASS) for the analysis of offshore video measurements of gravity waves in the Northern Adriatic Sea and near the southern seashore of the Crimean peninsula, in the Black Sea. We use classical epipolar techniques to reconstruct the sea surface from the stereo pairs sequentially in time, viz. a sequence of spatial snapshots. We also present a variational approach that exploits the entire data image set providing a global space–time imaging of the sea surface, viz. simultaneous reconstruction of several spatial snapshots of the surface in order to guarantee continuity of the sea surface both in space and time. Analysis of the WASS measurements show that the sea surface can be accurately estimated in space and time together, yielding associated directional spectra and wave statistics at a point in time that agrees well with probabilistic models. In particular, WASS stereo imaging is able to capture typical features of the wave surface, especially the crest-to-trough asymmetry due to second order nonlinearities, and the observed shape of large waves are fairly described by theoretical models based on the theory of quasi-determinism (Boccotti, 2000). Further, we investigate space–time extremes of the observed stationary sea states, viz. the largest surface wave heights expected over a given area during the sea state duration. The WASS analysis provides the first experimental proof that a space–time extreme is generally larger than that observed in time via point measurements, in agreement with the predictions based on stochastic theories for global maxima of Gaussian fields.

Use of Feynman diagrams in large-scale neural networks with nonlinear behaviour

A new proposal to the study of large-scale neural networks is reported. It is based on the use of similar graphs to the Feynman diagrams. A first general theory is presented and some interpretations are given. A propagator, based on the Green's function of the neuron, is the basis of the method. Application to a simple case is reported.

Hierarchical graph maps for visualization of collaborative recommender systems

In this paper we provide a method that allows the visualization of similarity relationships present between items of collaborative filtering recommender systems, as well as the relative importance of each of these. The objective is to offer visual representations of the recommender system?s set of items and of their relationships; these graphs show us where the most representative information can be found and which items are rated in a more similar way by the recommender system?s community of users. The visual representations achieved take the shape of phylogenetic trees, displaying the numerical similarity and the reliability between each pair of items considered to be similar. As a case study we provide the results obtained using the public database Movielens 1M, which contains 3900 movies.

Using ecological niche models to support tree species selection for forest restoration planning in largely deforested regions

Species selection for forest restoration is often supported by expert knowledge on local distribution patterns of native tree species. This approach is not applicable to largely deforested regions unless enough data on pre-human tree species distribution is available. In such regions, ecological niche models may provide essential information to support species selection in the framework of forest restoration planning. In this study we used ecological niche models to predict habitat suitability for native tree species in "Tierra de Campos" region, an almost totally deforested area of the Duero Basin (Spain). Previously available models provide habitat suitability predictions for dominant native tree species, but including non-dominant tree species in the forest restoration planning may be desirable to promote biodiversity, specially in largely deforested areas were near seed sources are not expected. We used the Forest Map of Spain as species occurrence data source to maximize the number of modeled tree species. Penalized logistic regression was used to train models using climate and lithological predictors. Using model predictions a set of tools were developed to support species selection in forest restoration planning. Model predictions were used to build ordered lists of suitable species for each cell of the study area. The suitable species lists were summarized drawing maps that showed the two most suitable species for each cell. Additionally, potential distribution maps of the suitable species for the study area were drawn. For a scenario with two dominant species, the models predicted a mixed forest (Quercus ilex and a coniferous tree species) for almost one half of the study area. According to the models, 22 non-dominant native tree species are suitable for the study area, with up to six suitable species per cell. The model predictions pointed to Crataegus monogyna, Juniperus communis, J.oxycedrus and J.phoenicea as the most suitable non-dominant native tree species in the study area. Our results encourage further use of ecological niche models for forest restoration planning in largely deforested regions.

An abstract machine for restricted and-parallel execution of logic programs

Although the sequential execution speed of logic programs has been greatly improved by the concepts introduced in the Warren Abstract Machine (WAM), parallel execution represents the only way to increase this speed beyond the natural limits of sequential systems. However, most proposed parallel logic programming execution models lack the performance optimizations and storage efficiency of sequential systems. This paper presents a parallel abstract machine which is an extension of the WAM and is thus capable of supporting ANDParallelism without giving up the optimizations present in sequential implementations. A suitable instruction set, which can be used as a target by a variety of logic programming languages, is also included. Special instructions are provided to support a generalized version of "Restricted AND-Parallelism" (RAP), a technique which reduces the overhead traditionally associated with the run-time management of variable binding conflicts to a series of simple run-time checks, which select one out of a series of compiled execution graphs.

Estructura espacial y dinámica del bosque montano del sur del Ecuador. Interacciones bióticas y limitaciones abióticas

Muchos estudios han descrito la composición y diversidad de los bosques montanos tropicales, pero los patrones espaciales y las diferentes tipos de relaciones de estos, entre especies o entre grupos funcionales ha sido poco documentada. El presente trabajo se realizó en tres parcelas completamente censadas del bosque de la Estación Biológica “Chamusquin” (Zamora Chinchipe, Ecuador), y se plantea como objetivo principal conocer la estructura espacial y dinámica del bosque montano tropical del sur del Ecuador, así como las interacciones bióticas y limitaciones abióticas que influyen en esta dinámica, para ello se planteó cuatro objetivos de estudio que son: conocer los patrones espaciales de los gremios ecológicos dentro de la zona de estudio; conocer la influencia de la dependencia negativa de la densidad sobre dos especies de helechos arborescentes (Cyatheaceae); conocer si existen especies o grupos ecológicos acumuladoras o repulsoras de diversidad en el área de estudio; y conocer cómo influyen la diversidad filogenética y la densidad del vecindario en la incidencia de herbivoría y parasitismo sobre las fases iniciales del establecimiento forestal (brinzales) así como en la supervivencia de los mismos Como paso previo para el análisis del resto de objetivos, dentro de cada parcela se marcaron todos los individuos con DAP ≥5 cm y se tomaron sus coordenadas (X, Y). Además se tomaron datos de variables superficiales y muestras del suelo. Las especies encontradas se clasificaron de acuerdo a sus características biológicas, asignándolas a cada uno de los cuatro gremios forestales usualmente distinguidos en los bosques tropicales: tolerantes a la sombra (TS), tolerantes parciales a la sombra (TPS), pioneras de vida larga (PVL) y pioneras de vida corta (PVC). Para el estudio del primer objetivo tas se emplearon funciones K de Ripley inhomogéneas, ajustando la heterogeneidad en base a la variación espacial de las variables ambientales registradas . Los resultados demostraron que tanto la frecuencia relativa como el patrón espacial de las diferentes estrategias funcionales varían a lo largo de la sucesión y que éste además está influido por la variación ambiental. En adición, tanto el patrón espacial como la respuesta a la variación ambiental de los diferentes gremios es distinta entre adultos y juveniles. Todo ello sugiere que el ensamblaje de la diversidad en los bosque montanos andinos está controlado por procesos deterministas más que por procesos neutrales. Para responder el segundo objetivo se estudiaron los efectos de la dependencia negativa de la densidad (DND) y la heterogeneidad ambiental en las poblaciones de dos especies de helechos arborescentes abundantes, Cyathea caracasana y Alsophila engelii, y cómo estos efectos cambian a través de un gradiente sucesional. Los patrones de especies albergan información sobre procesos tales como la competencia que puede ser revelado fácilmente utilizando técnicas de análisis de patrones punto. Sin embargo, su detección puede ser difícil debido a los efectos de factores de confusión heterogeneidad del hábitat. Aquí, empleamos funciones K y funciones de correlación de par homogéneas y no homogéneas para cuantificar el cambio en el patrón espacial de diferentes clases de tamaño con un diseño de casos-controles para estudiar las asociaciones entre helechos arborescentes jóvenes y adultos. Usando estimaciones espaciales de la biomasa de los cuatro tipos de gremios ecológicos (PVC, PVL, TPS, TS) como covariables, hemos ajustado modelos de Poisson heterogéneos a los patrones de puntos de de los helechos juveniles y los adultos y hemos explorado además la existencia de dependencia del hábitat en estos patrones. Nuestro estudio reveló efectos de la DND para C. caracasana y un fuerte filtrado ambiental que subyace al patrón de A. engelii. Encontramos también que las poblaciones de adultos y juveniles de ambas especies respondieron de manera diferente a la heterogeneidad del hábitat y en la mayoría de los casos esta heterogeneidad se asoció con la distribución espacial de la biomasa de los cuatro tipos de gremios. Estos resultados muestran la eficacia de controlar los efectos de la heterogeneidad ambiental para evitar su confusión con los patrones derivados de interacciones biológicas cuando se estudia la DND y demuestran la utilidad de los mapas de covariables derivados de comunidades biológicas como resumen de la heterogeneidad ambiental. Para nuestro tercer objetivo nos centramos en explorar cómo influyen las especies más abundantes en la organización espacial de la diversidad a lo largo de un gradiente sucesional en el bosque montano del sur del Ecuador. Para ello utilizamos la función ISAR (Individual Species Area Relationship). Encontramos que la frecuencia de especies neutras, repulsoras y acumuladoras de diversidad taxonómica varía dependiendo del grado de sucesión. Además se comprobó que la mayoría de los gremios forestales se comportó de forma neutral, pero la proporción de acumuladores, aumentó al avanzar la sucesión hacia estados más maduros, lo que indica el establecimiento de fuertes procesos competitivos a medida que avanza la sucesión y la mayor importancia del papel de las especies individuales en dichos estados. Finalmente, examinamos el efecto de la vecindad taxonómica y filogenética, así como la estrategia de vida, sobre la incidencia de la herbivoría y el parasitismo en las poblaciones de brinzales de tres fragmentos forestales en una secuencia sucesional del bosque montano húmedo. Evaluamos además los efectos de herbivoría, parasitismo, estrategia de vida y diferentes indicadores de la vecindad sobre la supervivencia de los brinzales. Por último contrastamos la posible existencia de una tendencia compensatoria de la comunidad (CCT) a nivel de fragmento forestal. Nuestros análisis no consiguieron detectar una CCT pero si pusieron de manifiesto la existencia de efectos locales de dependencia negativa de la densidad. Por ejemplo, la presencia de herbivoría y parasitismo sobre los brinzales se relacionó significativamente con una menor supervivencia de estos. Por otro lado, indicadores del efecto de la vecindad como la densidad de brinzales del mismo género y el área basal de árboles vecinos del mismo género incrementaron la prevalencia de la herbivoría o el parasitismo en los brinzales. El incremento de la incidencia de la herbivoría o el parasitismo no está exclusivamente ligado a tener una vecindad taxonómicamente idéntica (vecinos de la misma especie) sino que categorías taxonómicas más laxas como el "género" o simplemente relaciones de semejanza filogenética son capaces de predecir los efectos negativos de la vecindad. Los efectos detectados variaron en los diferentes grupos funcionales distinguidos. Los resultados que hemos obtenido en este trabajo parecen indicar que el funcionamiento de las comunidades de brinzales del bosque montano tropical no difiere mucho del reportado para comunidades de plántulas en otros bosques tropicales y cumple las predicciones de la hipótesis de Janzen y Connell, aunque matizadas por la mayor resistencia de los brinzales al efecto de herbivoría y parasitismo. ABSTRACT Many studies have described the composition and diversity of tropical montane forests, but the different spatial patterns and types of relationships between species or between functional groups has been poorly documented. This work was made in three completely surveyed forest plots at Biological Station "Chamusquin" (Zamora Chinchipe, Ecuador). Our main objective was to know the spatial structure and dynamics of the tropical montane forest in southern Ecuador, as well as the biotic interactions and abiotic constraints affecting this dynamic. More specifically, we aimed to understand the spatial patterns of ecological guilds; to explore the influence of negative density dependence on two species of tree ferns (Cyatheaceae); to determine whether some species or ecological groups structure spatially plant diversity in these forests; and to test the effects of biological neighborhood on the incidence of herbivory and parasitism and on the survival of saplings. We mapped within each plot all trees with DBH ≥5 cm. Besides, surface data variables and soil samples they were taken. The species found were classified according to their biological characteristics in four forest guilds: shade-tolerant (ST), partial shade tolerant (PST), long-lived pioneer (LLP) and short-lived pioneer (SLP). To analyze the spatial patterns of the ecological guilds, we employed the inhomogeneous version of Ripley's K-function and adjusted heterogeneity surfaces based on the spatial variation of the measured environmental variables. The results showed that both the relative frequency of each functional guild as well as their spatial pattern varied throughout succession and that the spatial pattern is explained by environmental variation. In addition, both spatial pattern and the response to spatial variation of each guild varied throughout ontogeny. All in all suggest that diversity assembly in the studied forests is ruled by deterministic instead of neutral processes. We also addressed the negative effects of density dependence (NDD) and environmental heterogeneity in populations of two species of abundant tree ferns, Cyathea caracasana and Alsophila engelii, and how these effects change across a successional gradient.. Here, we used homogeneous and inhomogeneous K and pair-correlation functions to quantify the change in the spatial pattern of different size classes with a case-control design to study associations between young and adult tree ferns. Using spatial estimates of the biomass of the four types of ecological guilds (SLP, LLP, PST, ST) as co-variables, we fitted heterogeneous Poisson models to juvenile and adult tree fern point patterns and explored the existence of habitat dependence. Our study revealed NDD effects for C. caracasana and strong environmental filtering underlying the pattern of A. engelii. We found that adult and juvenile populations of both species responded differently to habitat heterogeneity and in most cases this heterogeneity was associated with the spatial distribution of biomass of the four functional tree types. These findings show the effectiveness of factoring out environmental heterogeneity to avoid confounding factors when studying NDD and demonstrate the usefulness of covariate maps derived from mapped communities. For our third objective we focused on exploring how the most abundant species influence the spatial organization of tree diversity in these forests. For this, we used the individual species-area relationship function (ISAR). We found that the proportion of accumulator, repeller and neutral species, varied depending on the degree of succession. We found also that most guilds behaved neutrally but the proportion of accumulator guilds increased as succession advanced to more mature stages. This point, to the existence of strong competitive effects mediated by individual species in these mature forests. Finally, we examined the effects of life strategies and taxonomic and phylogenetic neighborhood on the incidence of herbivory and parasitism in the communities of saplings in the same forest fragments. We evaluated also the effects of life strategies, herbivory, parasitism and some indicators of neighborhood on sapling survival. Finally we tested for the existences of a compensatory community trend at plot scale. We did not found a CCT but we found proof of local NND effects. For instance, the prevalence of herbivory and parasitism were related to lower sapling survival. On the other hand the density of con-generic saplings and the basal area of neighbor con-generic trees were related to a higher prevalence of herbivory or parasitism in the saplings. We demonstrated that the increase in the prevalence of herbivory or parasitism it s not exclusive of a conspecific neighborhood but instead larger taxonomic categories such as "genus" or simple phylogenetic relationships are also able to predict NND effects. The NND effects varied among functional guilds. Our results show that the dynamic of sapling communities in Ecuadorian montane forests is similar to seedling dynamics in other tropical forest and follows the predictions of Janzen-Connell hypothesis, although softened by the strong resilience of saplings in comparison to seedlings.

Application of Deadlock Risk Evaluation of Architectural Models

Software architectural evaluation is a key discipline used to identify, at early stages of a real-time system (RTS) development, the problems that may arise during its operation. Typical mechanisms supporting concurrency, such as semaphores, mutexes or monitors, usually lead to concurrency problems in execution time that are difficult to be identified, reproduced and solved. For this reason, it is crucial to understand the root causes of these problems and to provide support to identify and mitigate them at early stages of the system lifecycle. This paper aims to present the results of a research work oriented to the development of the tool called ‘Deadlock Risk Evaluation of Architectural Models’ (DREAM) to assess deadlock risk in architectural models of an RTS. A particular architectural style, Pipelines of Processes in Object-Oriented Architectures–UML (PPOOA) was used to represent platform-independent models of an RTS architecture supported by the PPOOA –Visio tool. We validated the technique presented here by using several case studies related to RTS development and comparing our results with those from other deadlock detection approaches, supported by different tools. Here we present two of these case studies, one related to avionics and the other to planetary exploration robotics. Copyright © 2011 John Wiley & Sons, Ltd.

Análisis estático de sistemas de membranas para la determinación de reglas activas

Esta tesis doctoral se enmarca dentro de la computación con membranas. Se trata de un tipo de computación bio-inspirado, concretamente basado en las células de los organismos vivos, en las que se producen múltiples reacciones de forma simultánea. A partir de la estructura y funcionamiento de las células se han definido diferentes modelos formales, denominados P sistemas. Estos modelos no tratan de modelar el comportamiento biológico de una célula, sino que abstraen sus principios básicos con objeto de encontrar nuevos paradigmas computacionales. Los P sistemas son modelos de computación no deterministas y masivamente paralelos. De ahí el interés que en los últimos años estos modelos han suscitado para la resolución de problemas complejos. En muchos casos, consiguen resolver de forma teórica problemas NP-completos en tiempo polinómico o lineal. Por otra parte, cabe destacar también la aplicación que la computación con membranas ha tenido en la investigación de otros muchos campos, sobre todo relacionados con la biología. Actualmente, una gran cantidad de estos modelos de computación han sido estudiados desde el punto de vista teórico. Sin embargo, el modo en que pueden ser implementados es un reto de investigación todavía abierto. Existen varias líneas en este sentido, basadas en arquitecturas distribuidas o en hardware dedicado, que pretenden acercarse en lo posible a su carácter no determinista y masivamente paralelo, dentro de un contexto de viabilidad y eficiencia. En esta tesis doctoral se propone la realización de un análisis estático del P sistema, como vía para optimizar la ejecución del mismo en estas plataformas. Se pretende que la información recogida en tiempo de análisis sirva para configurar adecuadamente la plataforma donde se vaya a ejecutar posteriormente el P sistema, obteniendo como consecuencia una mejora en el rendimiento. Concretamente, en esta tesis se han tomado como referencia los P sistemas de transiciones para llevar a cabo el estudio de dicho análisis estático. De manera un poco más específica, el análisis estático propuesto en esta tesis persigue que cada membrana sea capaz de determinar sus reglas activas de forma eficiente en cada paso de evolución, es decir, aquellas reglas que reúnen las condiciones adecuadas para poder ser aplicadas. En esta línea, se afronta el problema de los estados de utilidad de una membrana dada, que en tiempo de ejecución permitirán a la misma conocer en todo momento las membranas con las que puede comunicarse, cuestión que determina las reglas que pueden aplicarse en cada momento. Además, el análisis estático propuesto en esta tesis se basa en otra serie de características del P sistema como la estructura de membranas, antecedentes de las reglas, consecuentes de las reglas o prioridades. Una vez obtenida toda esta información en tiempo de análisis, se estructura en forma de árbol de decisión, con objeto de que en tiempo de ejecución la membrana obtenga las reglas activas de la forma más eficiente posible. Por otra parte, en esta tesis se lleva a cabo un recorrido por un número importante de arquitecturas hardware y software que diferentes autores han propuesto para implementar P sistemas. Fundamentalmente, arquitecturas distribuidas, hardware dedicado basado en tarjetas FPGA y plataformas basadas en microcontroladores PIC. El objetivo es proponer soluciones que permitan implantar en dichas arquitecturas los resultados obtenidos del análisis estático (estados de utilidad y árboles de decisión para reglas activas). En líneas generales, se obtienen conclusiones positivas, en el sentido de que dichas optimizaciones se integran adecuadamente en las arquitecturas sin penalizaciones significativas. Summary Membrane computing is the focus of this doctoral thesis. It can be considered a bio-inspired computing type. Specifically, it is based on living cells, in which many reactions take place simultaneously. From cell structure and operation, many different formal models have been defined, named P systems. These models do not try to model the biological behavior of the cell, but they abstract the basic principles of the cell in order to find out new computational paradigms. P systems are non-deterministic and massively parallel computational models. This is why, they have aroused interest when dealing with complex problems nowadays. In many cases, they manage to solve in theory NP problems in polynomial or lineal time. On the other hand, it is important to note that membrane computing has been successfully applied in many researching areas, specially related to biology. Nowadays, lots of these computing models have been sufficiently characterized from a theoretical point of view. However, the way in which they can be implemented is a research challenge, that it is still open nowadays. There are some lines in this way, based on distributed architectures or dedicated hardware. All of them are trying to approach to its non-deterministic and parallel character as much as possible, taking into account viability and efficiency. In this doctoral thesis it is proposed carrying out a static analysis of the P system in order to optimize its performance in a computing platform. The general idea is that after data are collected in analysis time, they are used for getting a suitable configuration of the computing platform in which P system is going to be performed. As a consequence, the system throughput will improve. Specifically, this thesis has made use of Transition P systems for carrying out the study in static analysis. In particular, the static analysis proposed in this doctoral thesis tries to achieve that every membrane can efficiently determine its active rules in every evolution step. These rules are the ones that can be applied depending on the system configuration at each computational step. In this line, we are going to tackle the problem of the usefulness states for a membrane. This state will allow this membrane to know the set of membranes with which communication is possible at any time. This is a very important issue in determining the set of rules that can be applied. Moreover, static analysis in this thesis is carried out taking into account other properties such as membrane structure, rule antecedents, rule consequents and priorities among rules. After collecting all data in analysis time, they are arranged in a decision tree structure, enabling membranes to obtain the set of active rules as efficiently as possible in run-time system. On the other hand, in this doctoral thesis is going to carry out an overview of hardware and software architectures, proposed by different authors in order to implement P systems, such as distributed architectures, dedicated hardware based on PFGA, and computing platforms based on PIC microcontrollers. The aim of this overview is to propose solutions for implementing the results of the static analysis, that is, usefulness states and decision trees for active rules. In general, conclusions are satisfactory, because these optimizations can be properly integrated in most of the architectures without significant penalties.

Game Theory Models for Multi-Robot Patrolling of Infraestructures

Abstract This work is focused on the problem of performing multi‐robot patrolling for infrastructure security applications in order to protect a known environment at critical facilities. Thus, given a set of robots and a set of points of interest, the patrolling task consists of constantly visiting these points at irregular time intervals for security purposes. Current existing solutions for these types of applications are predictable and inflexible. Moreover, most of the previous centralized and deterministic solutions and only few efforts have been made to integrate dynamic methods. Therefore, the development of new dynamic and decentralized collaborative approaches in order to solve the aforementioned problem by implementing learning models from Game Theory. The model selected in this work that includes belief‐based and reinforcement models as special cases is called Experience‐Weighted Attraction. The problem has been defined using concepts of Graph Theory to represent the environment in order to work with such Game Theory techniques. Finally, the proposed methods have been evaluated experimentally by using a patrolling simulator. The results obtained have been compared with previous available

Impact attribution models to evaluate drought effects: economic impacts, risk analyses and management strategies in Spain and Chile

La sequía es un fenómeno natural que se origina por el descenso de las precipitaciones con respecto a una media, y que resulta en la disponibilidad insuficiente de agua para alguna actividad. La creciente presión que se ha venido ejerciendo sobre los recursos hídricos ha hecho que los impactos de la sequía se hayan visto agravados a la vez que ha desencadenado situaciones de escasez de agua en muchas partes del planeta. Los países con clima mediterráneo son especialmente vulnerables a las sequías, y, su crecimiento económico dependiente del agua da lugar a impactos importantes. Para reducir los impactos de la sequía es necesaria una reducción de la vulnerabilidad a las sequías que viene dada por una gestión más eficiente y por una mejor preparación. Para ello es muy importante disponer de información acerca de los impactos y el alcance de este fenómeno natural. Esta investigación trata de abarcar el tema de los impactos de las sequías, de manera que plantea todos los tipos de impactos que pueden darse y además compara sus efectos en dos países (España y Chile). Para ello se proponen modelos de atribución de impactos que sean capaces de medir las pérdidas económicas causadas por la falta de agua. Los modelos propuestos tienen una base econométrica en la que se incluyen variables clave a la hora de evaluar los impactos como es una variable relacionada con la disponibilidad de agua, y otras de otra naturaleza para distinguir los efectos causados por otras fuentes de variación. Estos modelos se adaptan según la fase del estudio en la que nos encontremos. En primer lugar se miden los impactos directos sobre el regadío y se introduce en el modelo un factor de aleatoriedad para evaluar el riesgo económico de sequía. Esto se hace a dos niveles geográficos (provincial y de Unidad de Demanda Agraria) y además en el último se introduce no solo el riesgo de oferta sino también el riesgo de demanda de agua. La introducción de la perspectiva de riesgo en el modelo da lugar a una herramienta de gestión del riesgo económico que puede ser utilizada para estrategias de planificación. Más adelante una extensión del modelo econométrico se desarrolla para medir los impactos en el sector agrario (impactos directos sobre el regadío y el secano e impactos indirectos sobre la Agro Industria) para ello se adapta el modelo y se calculan elasticidades concatenadas entre la falta de agua y los impactos secundarios. Por último se plantea un modelo econométrico para el caso de estudio en Chile y se evalúa el impacto de las sequías debidas al fenómeno de La Niña. iv Los resultados en general muestran el valor que brinda el conocimiento más preciso acerca de los impactos, ya que en muchas ocasiones se tiende a sobreestimar los daños realmente producidos por la falta de agua. Los impactos indirectos de la sequía confirman su alcance a la vez que son amortiguados a medida que nos acercamos al ámbito macroeconómico. En el caso de Chile, su diferente gestión muestra el papel que juegan el fenómeno de El Niño y La Niña sobre los precios de los principales cultivos del país y sobre el crecimiento del sector. Para reducir las pérdidas y su alcance se deben plantear más medidas de mitigación que centren su esfuerzo en una gestión eficiente del recurso. Además la prevención debe jugar un papel muy importante para reducir los riesgos que pueden sufrirse ante situaciones de escasez. ABSTRACT Drought is a natural phenomenon that originates by the decrease in rainfall in comparison to the average, and that results in water shortages for some activities. The increasing pressure on water resources has augmented the impact of droughts just as water scarcity has become an additional problem in many parts of the planet. Countries with Mediterranean climate are especially vulnerable to drought, and its waterdependent economic growth leads to significant impacts. To reduce the negative impacts it is necessary to deal with drought vulnerability, and to achieve this objective a more efficient management is needed. The availability of information about the impacts and the scope of droughts become highly important. This research attempts to encompass the issue of drought impacts, and therefore it characterizes all impact types that may occur and also compares its effects in two different countries (Spain and Chile). Impact attribution models are proposed in order to measure the economic losses caused by the lack of water. The proposed models are based on econometric approaches and they include key variables for measuring the impacts. Variables related to water availability, crop prices or time trends are included to be able to distinguish the effects caused by any of the possible sources. These models are adapted for each of the parts of the study. First, the direct impacts on irrigation are measured and a source of variability is introduced into the model to assess the economic risk of drought. This is performed at two geographic levels provincial and Agricultural Demand Unit. In the latter, not only the supply risk is considered but also the water demand risk side. The introduction of the risk perspective into the model results in a risk management tool that can be used for planning strategies. Then an extension of the econometric model is developed to measure the impacts on the agricultural sector (direct impacts on irrigated and rainfed productions and indirect impacts on the Agri-food Industry). For this aim the model is adapted and concatenated elasticities between the lack of water and the impacts are estimated. Finally an econometric model is proposed for the Chilean case study to evaluate the impact of droughts, especially caused by El Niño Southern Oscillation. The overall results show the value of knowing better about the precise impacts that often tend to be overestimated. The models allow for measuring accurate impacts due to the lack of water. Indirect impacts of drought confirm their scope while they confirm also its dilution as we approach the macroeconomic variables. In the case of Chile, different management strategies of the country show the role of ENSO phenomena on main crop prices and on economic trends. More mitigation measures focused on efficient resource management are necessary to reduce drought losses. Besides prevention must play an important role to reduce the risks that may be suffered due to shortages.

An abstract machine based execution model for computer architecture design and efficient implementation of logic programs in parallel.

The term "Logic Programming" refers to a variety of computer languages and execution models which are based on the traditional concept of Symbolic Logic. The expressive power of these languages offers promise to be of great assistance in facing the programming challenges of present and future symbolic processing applications in Artificial Intelligence, Knowledge-based systems, and many other areas of computing. The sequential execution speed of logic programs has been greatly improved since the advent of the first interpreters. However, higher inference speeds are still required in order to meet the demands of applications such as those contemplated for next generation computer systems. The execution of logic programs in parallel is currently considered a promising strategy for attaining such inference speeds. Logic Programming in turn appears as a suitable programming paradigm for parallel architectures because of the many opportunities for parallel execution present in the implementation of logic programs. This dissertation presents an efficient parallel execution model for logic programs. The model is described from the source language level down to an "Abstract Machine" level suitable for direct implementation on existing parallel systems or for the design of special purpose parallel architectures. Few assumptions are made at the source language level and therefore the techniques developed and the general Abstract Machine design are applicable to a variety of logic (and also functional) languages. These techniques offer efficient solutions to several areas of parallel Logic Programming implementation previously considered problematic or a source of considerable overhead, such as the detection and handling of variable binding conflicts in AND-Parallelism, the specification of control and management of the execution tree, the treatment of distributed backtracking, and goal scheduling and memory management issues, etc. A parallel Abstract Machine design is offered, specifying data areas, operation, and a suitable instruction set. This design is based on extending to a parallel environment the techniques introduced by the Warren Abstract Machine, which have already made very fast and space efficient sequential systems a reality. Therefore, the model herein presented is capable of retaining sequential execution speed similar to that of high performance sequential systems, while extracting additional gains in speed by efficiently implementing parallel execution. These claims are supported by simulations of the Abstract Machine on sample programs.

Diseño, optimización y análisis de sistemas basados en técnicas láser, para el modelado geométrico, registro y documentación, aplicados a entidades de interés patrimonial.

El objetivo de la presente tesis doctoral es el desarrollo e implementación de un sistema para mejorar la metodología de extracción de la información geométrica necesaria asociada a los procesos de documentación de entidades de interés patrimonial, a partir de la información proporcionada por el empleo de sensores láser, tanto aéreos como terrestres. Para ello, inicialmente se realiza una presentación y justificación de los antecedentes y la problemática en el registro de información geométrica para el patrimonio, detallando todos aquellos sistemas de registro y análisis de la información geométrica utilizados en la actualidad. Este análisis permitirá realizar la comparación con los sistemas de registro basados en técnicas láser, aportando sugerencias de utilización para cada caso concreto. Posteriormente, se detallan los sistemas de registro basados en técnicas láser, comenzando por los sensores aerotransportados y concluyendo con el análisis pormenorizado de los sensores terrestres, tanto en su aplicación en modo estático como móvil. Se exponen las características técnicas y funcionamiento de cada uno de ellos, así como los ámbitos de aplicación y productos generados. Se analizan las fuentes de error que determinan la precisión que puede alcanzar el sistema. Tras la exposición de las características de los sistemas LiDAR, se detallan los procesos a realizar con los datos extraídos para poder generar la información necesaria para los diferentes tipos de objetos analizados. En esta exposición, se hace hincapié en los posibles riesgos que pueden ocurrir en algunas fases delicadas y se analizarán los diferentes algoritmos de filtrado y clasificación de los puntos, fundamentales en el procesamiento de la información LiDAR. Seguidamente, se propone una alternativa para optimizar los modelos de procesamiento existentes, basándose en el desarrollo de algoritmos nuevos y herramientas informáticas que mejoran el rendimiento en la gestión de la información LiDAR. En la implementación, se han tenido en cuenta características y necesidades particulares de la documentación de entidades de interés patrimonial, así como los diferentes ámbitos de utilización del LiDAR, tanto aéreo como terrestre. El resultado es un organigrama de las tareas a realizar desde la nube de puntos LiDAR hasta el cálculo de los modelos digitales del terreno y de superficies. Para llevar a cabo esta propuesta, se han desarrollado hasta 19 algoritmos diferentes que comprenden implementaciones para el modelado en 2.5D y 3D, visualización, edición, filtrado y clasificación de datos LiDAR, incorporación de información de sensores pasivos y cálculo de mapas derivados, tanto raster como vectoriales, como pueden ser mapas de curvas de nivel y ortofotos. Finalmente, para dar validez y consistencia a los desarrollos propuestos, se han realizado ensayos en diferentes escenarios posibles en un proceso de documentación del patrimonio y que abarcan desde proyectos con sensores aerotransportados, proyectos con sensores terrestres estáticos a media y corta distancia, así como un proyecto con un sensor terrestre móvil. Estos ensayos han permitido definir los diferentes parámetros necesarios para el adecuado funcionamiento de los algoritmos propuestos. Asimismo, se han realizado pruebas objetivas expuestas por la ISPRS para la evaluación y comparación del funcionamiento de algoritmos de clasificación LiDAR. Estas pruebas han permitido extraer datos de rendimiento y efectividad del algoritmo de clasificación presentado, permitiendo su comparación con otros algoritmos de prestigio existentes. Los resultados obtenidos han constatado el funcionamiento satisfactorio de la herramienta. Esta tesis está enmarcada dentro del proyecto Consolider-Ingenio 2010: “Programa de investigación en tecnologías para la valoración y conservación del patrimonio cultural” (ref. CSD2007-00058) realizado por el Consejo Superior de Investigaciones Científicas y la Universidad Politécnica de Madrid. ABSTRACT: The goal of this thesis is the design, development and implementation of a system to improve the extraction of useful geometric information in Heritage documentation processes. This system is based on information provided by laser sensors, both aerial and terrestrial. Firstly, a presentation of recording geometric information for Heritage processes is done. Then, a justification of the background and problems is done too. Here, current systems for recording and analyzing the geometric information are studied. This analysis will perform the comparison with the laser system techniques, providing suggestions of use for each specific case. Next, recording systems based on laser techniques are detailed. This study starts with airborne sensors and ends with terrestrial ones, both in static and mobile application. The technical characteristics and operation of each of them are described, as well as the areas of application and generated products. Error sources are also analyzed in order to know the precision this technology can achieve. Following the presentation of the LiDAR system characteristics, the processes to generate the required information for different types of scanned objects are described; the emphasis is on the potential risks that some steps can produce. Moreover different filtering and classification algorithms are analyzed, because of their main role in LiDAR processing. Then, an alternative to optimize existing processing models is proposed. It is based on the development of new algorithms and tools that improve the performance in LiDAR data management. In this implementation, characteristics and needs of the documentation of Heritage entities have been taken into account. Besides, different areas of use of LiDAR are considered, both air and terrestrial. The result is a flowchart of tasks from the LiDAR point cloud to the calculation of digital terrain models and digital surface models. Up to 19 different algorithms have been developed to implement this proposal. These algorithms include implementations for 2.5D and 3D modeling, viewing, editing, filtering and classification of LiDAR data, incorporating information from passive sensors and calculation of derived maps, both raster and vector, such as contour maps and orthophotos. Finally, in order to validate and give consistency to the proposed developments, tests in different cases have been executed. These tests have been selected to cover different possible scenarios in the Heritage documentation process. They include from projects with airborne sensors, static terrestrial sensors (medium and short distances) to mobile terrestrial sensor projects. These tests have helped to define the different parameters necessary for the appropriate functioning of the proposed algorithms. Furthermore, proposed tests from ISPRS have been tested. These tests have allowed evaluating the LiDAR classification algorithm performance and comparing it to others. Therefore, they have made feasible to obtain performance data and effectiveness of the developed classification algorithm. The results have confirmed the reliability of the tool. This investigation is framed within Consolider-Ingenio 2010 project titled “Programa de investigación en tecnologías para la valoración y conservación del patrimonio cultural” (ref. CSD2007-00058) by Consejo Superior de Investigaciones Científicas and Universidad Politécnica de Madrid.