Laplace operator on finite graphs and a network diffusion model for the progression of the Alzheimer disease

Nella tesi viene descritto il Network Diffusion Model, ovvero il modello di A. Ray, A. Kuceyeski, M. Weiner inerente i meccanismi di progressione della demenza senile. In tale modello si approssima l'encefalo sano con una rete cerebrale (ovvero un grafo pesato), si identifica un generale fattore di malattia e se ne analizza la propagazione che avviene secondo meccanismi analoghi a quelli di un'infezione da prioni. La progressione del fattore di malattia e le conseguenze macroscopiche di tale processo(tra cui principalmente l'atrofia corticale) vengono, poi, descritte mediante approccio matematico. I risultati teoretici vengono confrontati con quanto osservato sperimentalmente in pazienti affetti da demenza senile. Nella tesi, inoltre, si fornisce una panoramica sui recenti studi inerenti i processi neurodegenerativi e si costruisce il contesto matematico di riferimento del modello preso in esame. Si presenta una panoramica sui grafi finiti, si introduce l'operatore di Laplace sui grafi e si forniscono stime dall'alto e dal basso per gli autovalori. Al fine di costruire una cornice matematica completa si analizza la relazione tra caso discreto e continuo: viene descritto l'operatore di Laplace-Beltrami sulle varietà riemanniane compatte e vengono fornite stime dall'alto per gli autovalori dell'operatore di Laplace-Beltrami associato a tali varietà a partire dalle stime dall'alto per gli autovalori del laplaciano sui grafi finiti.

Graph-based analysis of brain resting-state fMRI data in nocturnal frontal lobe epileptic patients

Il lavoro che ho sviluppato presso l'unità di RM funzionale del Policlinico S.Orsola-Malpighi, DIBINEM, è incentrato sull'analisi dati di resting state - functional Magnetic Resonance Imaging (rs-fMRI) mediante l'utilizzo della graph theory, con lo scopo di valutare eventuali differenze in termini di connettività cerebrale funzionale tra un campione di pazienti affetti da Nocturnal Frontal Lobe Epilepsy (NFLE) ed uno di controlli sani. L'epilessia frontale notturna è una peculiare forma di epilessia caratterizzata da crisi che si verificano quasi esclusivamente durante il sonno notturno. Queste sono contraddistinte da comportamenti motori, prevalentemente distonici, spesso complessi, e talora a semiologia bizzarra. L'fMRI è una metodica di neuroimaging avanzata che permette di misurare indirettamente l'attività neuronale. Tutti i soggetti sono stati studiati in condizioni di resting-state, ossia di veglia rilassata. In particolare mi sono occupato di analizzare i dati fMRI con un approccio innovativo in campo clinico-neurologico, rappresentato dalla graph theory. I grafi sono definiti come strutture matematiche costituite da nodi e links, che trovano applicazione in molti campi di studio per la modellizzazione di strutture di diverso tipo. La costruzione di un grafo cerebrale per ogni partecipante allo studio ha rappresentato la parte centrale di questo lavoro. L'obiettivo è stato quello di definire le connessioni funzionali tra le diverse aree del cervello mediante l'utilizzo di un network. Il processo di modellizzazione ha permesso di valutare i grafi neurali mediante il calcolo di parametri topologici che ne caratterizzano struttura ed organizzazione. Le misure calcolate in questa analisi preliminare non hanno evidenziato differenze nelle proprietà globali tra i grafi dei pazienti e quelli dei controlli. Alterazioni locali sono state invece riscontrate nei pazienti, rispetto ai controlli, in aree della sostanza grigia profonda, del sistema limbico e delle regioni frontali, le quali rientrano tra quelle ipotizzate essere coinvolte nella fisiopatologia di questa peculiare forma di epilessia.

Entropia, contenuto informativo e network linguistici: applicazioni al manoscritto di Voynich

La tesi si propone di investigare, mediante un approccio puramente quantitativo, il contenuto informativo e la morfologia della lingua del manoscritto di Voynich (VMS), noto per essere redatto in un alfabeto sconosciuto e tuttora non decodificato. Per prima cosa, a partire dal concetto di entropia, sviluppato nel contesto della teoria della informazione, si costruisce una misura del contenuto informativo di un testo (misura di Montemurro-Zanette); quindi, si presentano diversi esperimenti in cui viene misurata l'informazione di testi sottoposti a trasformazioni linguistiche di vario genere(lemmatizzazione, traduzione, eccetera). In particolare, l'applicazione al VMS di questa misura unita ad altre tecniche, ci permette di indagare la struttura tematica del manoscritto e le relazioni tra i suoi contenuti, verificando che esiste una continuità semantica tra pagine consecutive appartenenti a una stessa sezione. La grande quantità di hapax nel manoscritto ci porta poi a considerazioni di tipo morfologico: suggerisce infatti che la lingua del manoscritto sia particolarmente flessiva. La ricerca, in particolare, di sequenze di hapax consecutivi, ci porta a identificare -verosimilmente- alcuni nomi propri. Proprio per approfondire la morfologia della lingua si costruisce infine un grafo linguistico basato sostanzialmente sulla distanza di Hamming; confrontando la topologia di questi grafi per alcune lingue e per la lingua del VMS si osserva che quest'ultimo si distingue per maggiore densità e connessione. Traendo le conclusioni, i forti indizi a favore della presenza di un contenuto informativo nel testo confermano l'ipotesi che questo sia scritto in una vera lingua. Tuttavia, data la notevole semplicità delle regole di costruzione morfologiche, a nostro parere non sembra assimilabile ad una lingua naturale conosciuta, ma piuttosto ad una artificiale, creata appositamente per questo testo.

Dimensione di un insieme parzialmente ordinato

Con questo lavoro si studia l'argomento della dimensione di un insieme parzialmente ordinato P, introdotta nel 1941 da Dushnik e Miller, tramite diagrammi di Hasse, in modo da avere una visione geometrica di un concetto algebrico. Il Teorema di Szpilrajn permette di linearizzare un qualsiasi insieme parzialmente ordinato P: questo anticipa la definizione di dimensione, siccome tutte le linearizzazioni sono realizzatori: le loro coppie comuni sono presenti anche in P. La dimensione viene definita come il minimo numero cardinale m di realizzatori per P. Vengono rivisti alcuni dei risultati già pubblicati da M. Barnabei, F. Bonetti e R. Pirastu e ripresi da M. Silimbani nella sua Tesi di Dottorato: ci si concentra sulla dimensione 2 in cui può essere definito un etichettamento doppio, che si può utilizzare per avere un algoritmo poco costoso atto a sapere se un insieme parzialmente ordinato ha dimensione 2 : esso pone le basi per una corrispondenza biunivoca tra un insieme parzialmente ordinato di cardinalità n dotato di un etichettamento doppio e l'insieme delle permutazioni su n elementi. Infine viene spiegato un altro modo per scoprire se un insieme parzialmente ordinato P ha dimensione al massimo 2 servendosi del solo diagramma di Hasse: ciò succede se e solo se il grafo di inconfrontabilità di P ammette un orientamento transitivo.

Grafi aleatori - il modello di Erdos-Rényi

Dopo aver dato una definizione formale per il modello di Erdos-Rényi, si dimostra che in un grafo ER il grado dei nodi (misura della connessione) risulta essere una variabile aleatoria con distribuzione binomiale, mentre il clustering (misura della densità di archi a livello locale) tende a zero. Successivamente si determinano le funzioni soglia per alcune proprietà monotone particolarmente significative, consentendo così di descrivere diverse configurazioni possibili per un grafo ER al variare dei suoi parametri. Infine, si mostra come si possano utilizzare i grafi ER per modellizzare la diffusione di una malattia infettiva all’interno di una popolazione numerosa.

Procesamiento y almacenamiento distribuido de imágenes basados en grafos: Aplicación para recuperación de información en imágenes muy grandes

El almacenamiento y tratamiento de señales digitales es un campo muy importante de la informática. Dichas señales contienen información valiosa que ha de ser extrada y transformada para poder ser utilizada. En la presente tesis doctoral se han creado métodos para almacenar, procesar y recuperar información de las regiones contenidas en una imagen, en especial en imágenes de gran tamaño. Como base del trabajo se ha diseñado una estructura de datos de tipo grafo para poder almacenar todas las regiones contenidas en una imagen. En esta estructura de datos se pueden guardar tanto los descriptores de bajo nivel de las regiones como las relaciones estructurales entre las distintas regiones de la imagen. En los sistemas de almacenamiento de imágenes es una práctica habitual distribuir las imágenes para mejorar el rendimiento. Más allá de este tipo de distribución, una característica distintiva y novedosa de la estructura de datos creada en la presente investigación es que puede funcionar de forma distribuida de manera que una imagen grande puede ser dividida en varias subimagenes, y dichas sub-imágenes pueden ser almacenadas de forma separada en varios servidores. También se han adaptado algunos métodos y algoritmos pertenecientes a la Morfología Matemática para trabajar directamente sobre la estructura de datos distribuida. De esta manera, se pueden procesar todas las sub-imágenes de una misma imagen sin necesidad de reconstruir la imagen inicial. Finalmente, haciendo uso de la estructura de datos y de los métodos desarrollados se ha creado un prototipo de sistema multi-agente capaz de almacenar y procesar imágenes grandes. Este prototipo permite realizar consultas para recuperar información perteneciente a regiones de una imagen almacenada en el sistema sin necesidad de volver a ser procesada. En la experimentación realizada, resumida en los resultados presentados, se muestra que la división y distribución de una imagen en varias sub-imágenes reduce los tiempos de almacenamiento, procesamiento y recuperación de la información.

Probabilistic mapping with mobile robots in structured environments

La mayor parte de los entornos diseñados por el hombre presentan características geométricas específicas. En ellos es frecuente encontrar formas poligonales, rectangulares, circulares . . . con una serie de relaciones típicas entre distintos elementos del entorno. Introducir este tipo de conocimiento en el proceso de construcción de mapas de un robot móvil puede mejorar notablemente la calidad y la precisión de los mapas resultantes. También puede hacerlos más útiles de cara a un razonamiento de más alto nivel. Cuando la construcción de mapas se formula en un marco probabilístico Bayesiano, una especificación completa del problema requiere considerar cierta información a priori sobre el tipo de entorno. El conocimiento previo puede aplicarse de varias maneras, en esta tesis se presentan dos marcos diferentes: uno basado en el uso de primitivas geométricas y otro que emplea un método de representación cercano al espacio de las medidas brutas. Un enfoque basado en características geométricas supone implícitamente imponer un cierto modelo a priori para el entorno. En este sentido, el desarrollo de una solución al problema SLAM mediante la optimización de un grafo de características geométricas constituye un primer paso hacia nuevos métodos de construcción de mapas en entornos estructurados. En el primero de los dos marcos propuestos, el sistema deduce la información a priori a aplicar en cada caso en base a una extensa colección de posibles modelos geométricos genéricos, siguiendo un método de Maximización de la Esperanza para hallar la estructura y el mapa más probables. La representación de la estructura del entorno se basa en un enfoque jerárquico, con diferentes niveles de abstracción para los distintos elementos geométricos que puedan describirlo. Se llevaron a cabo diversos experimentos para mostrar la versatilidad y el buen funcionamiento del método propuesto. En el segundo marco, el usuario puede definir diferentes modelos de estructura para el entorno mediante grupos de restricciones y energías locales entre puntos vecinos de un conjunto de datos del mismo. El grupo de restricciones que se aplica a cada grupo de puntos depende de la topología, que es inferida por el propio sistema. De este modo, se pueden incorporar nuevos modelos genéricos de estructura para el entorno con gran flexibilidad y facilidad. Se realizaron distintos experimentos para demostrar la flexibilidad y los buenos resultados del enfoque propuesto. Abstract Most human designed environments present specific geometrical characteristics. In them, it is easy to find polygonal, rectangular and circular shapes, with a series of typical relations between different elements of the environment. Introducing this kind of knowledge in the mapping process of mobile robots can notably improve the quality and accuracy of the resulting maps. It can also make them more suitable for higher level reasoning applications. When mapping is formulated in a Bayesian probabilistic framework, a complete specification of the problem requires considering a prior for the environment. The prior over the structure of the environment can be applied in several ways; this dissertation presents two different frameworks, one using a feature based approach and another one employing a dense representation close to the measurements space. A feature based approach implicitly imposes a prior for the environment. In this sense, feature based graph SLAM was a first step towards a new mapping solution for structured scenarios. In the first framework, the prior is inferred by the system from a wide collection of feature based priors, following an Expectation-Maximization approach to obtain the most probable structure and the most probable map. The representation of the structure of the environment is based on a hierarchical model with different levels of abstraction for the geometrical elements describing it. Various experiments were conducted to show the versatility and the good performance of the proposed method. In the second framework, different priors can be defined by the user as sets of local constraints and energies for consecutive points in a range scan from a given environment. The set of constraints applied to each group of points depends on the topology, which is inferred by the system. This way, flexible and generic priors can be incorporated very easily. Several tests were carried out to demonstrate the flexibility and the good results of the proposed approach.

Metodología para la generación automática de entornos virtuales en simuladores de conducción terrestre

Está Tesis refleja los trabajos de investigación que tienen como resultado el desarrollo de una metodología cuyo objetivo es la automatización optimizada en la generación de grandes entornos virtuales destinados a simulaciones de conducción terrestre guiada, es decir, sobre trayectorias predefinidas, bajo PC. En ella se aborda el ciclo completo de generación de un entorno virtual, aportando soluciones optimizadas en cada una de las fases. Para definir estas soluciones, se ha llevado a cabo un estudio en profundidad de las características y requisitos exigidos a este tipo de representaciones virtuales así como de las posibles vías resolutivas, concluyéndose con el establecimiento de tres fases constructivas. La primera fase es la del análisis perceptivo visual. La presente Tesis, tras sintetizar las características que definen a este tipo de entornos así como sus condiciones perceptivas, propone una metodología constructiva que saca el máximo partido de las mismas de una manera hasta ahora no considerada: la creación del entorno mediante el ensamblaje y repetición (instanciación) de un número finito de patrones repetitivos o módulos. Son múltiples las ventajas aportadas por este sistema modular de instanciación: disminución de las labores de modelado, reducción drástica de la memoria de almacenamiento requerida y de los tiempos de carga, facilitación de las tareas de creación y edición de los escenarios. La segunda fase es la generación geométrica y topológica del entorno. El elevado volumen y heterogeneidad de la información a manejar hace necesario el desarrollo de métodos que automaticen el procesamiento de la misma. La presente Tesis desarrolla un sistema consistente en varios criterios de organización, corrección y almacenamiento de la información de partida. Dicho sistema permite por un lado la construcción fácilmente escalable y editable de entornos que cumplan las normativas circulatorias vigentes y por otro lado garantiza un óptimo flujo de la información entre los diversos subsistemas integrantes de la simulación. Flujo que ha sido plasmado en la elaboración de diversos protocolos de comunicación. La tercera fase es la del posicionamiento 3D de la base de datos visual, su jerarquización y optimización escénica. En esta fase, la presente Tesis ha desarrollado una serie de Algoritmos de Posicionamiento modular que garantizan el correcto acoplamiento de los módulos a lo largo de una serie de líneas directrices. Dichas líneas son creadas a partir de la definición de las trayectorias circulatorias, lo que ha permitido a su vez, la definición por parte de esta Tesis de un sistema de niveles de detalle discretos pseudo-variantes con el punto de vista, que permite optimizar la carga geométrica del escenario, mediante la definición en tiempo de precarga de los posibles niveles de detalle de cada módulo en función de su distancia transversal a la trayectoria. Por otro lado, con el fin de potenciar las ventajas de este sistema de instanciación esta Tesis propone el empleo de una serie de shaders que deforman los módulos en tiempo real, lo que permite disminuir el número de módulos necesarios en tiempo de precarga y aumenta la versatilidad constructiva y realismo de los escenarios. Finalmente, esta Tesis organiza todo el escenario en un grafo de la escena (scene graph) que busca minimizar el recorrido del mismo con el fin de maximizar las velocidades de refresco y facilitar las labores de edición de los escenarios. En este punto, la construcción modular del entorno es fundamental para alcanzar dichos objetivos. Todos los planteamientos teóricos expuestos en esta Tesis se han materializado en las correspondientes aplicaciones informáticas que se han validado como herramientas de desarrollo en la creación de grandes entornos virtuales de simuladores actualmente en funcionamiento, como los de Metro de Madrid de las series 7000, 8000, 3000, 9000 y Citadis y en otros experimentales donde también se han implementado los criterios y resultados perceptivos que optimizan estos simuladores.

Construcción de redes de pequeño mundo mediante selección sesgada.

En la actualidad las redes de Pequeño Mundo están presentes en muchas aplicaciones distribuidas, pudiéndose construir estas redes añadiendo, a un grafo base, enlaces de largo alcance tomados conforme a una determinada distribución de probabiblidad. Los sistemas distribuidos actuales utilizan soluciones ad hoc específicas para calcular los enlaces de largo alcance. En este artículo proponemos un nuevo algoritmo distribuido llamado Selección Sesgada (SS), que utilizando únicamente un servicio de muestreo uniforme (que puede estar implementado mediante un protocolo gossip), es capaz de seleccionar enlaces largos conforme a cualquier distribución de probabilidad. SS es un algoritmo iterativo que dispone de un único parámetro (r) para indicar el número de iteraciones que debe ejecutarse. Se ha probado que la muestra obtenida con el algoritmo SS converge a la distribución objetivo a medida que aumenta el valor de r. También se ha calculado la cota analítica del error relativo máximo, para un determinado valor de r. Aunque este artículo se propone para el algoritmo SS como una herramienta para tomar muestras de nodos en una red, puede emplearse en cualquier contexto en el que sea necesario realizar un muestreo conforme a una determinada distribución de probabilidad, necesitando para funcionar únicamente un servicio de muestreo uniforme. Se han construido redes de Pequeño Mundo, modelo Kleinberg, utilizando SS para escoger los enlaces (vecinos) de largo alcance en estructuras de tipo toro. Hemos observado que con un número reducido de iteraciones (1) SS tiene un comportamiento muy similar a la distribución armónica de Kleinberg y (2) el número medio de saltos, utilizando enrutamiento ávido, no es peor que en una red construida con la distribución de Leinberg. También se ha observado que antes de obtener la convergencia, el número medio de saltos es menor que en las redes construidas mediante la distribución armónica de Leinberg (14% mejor en un toro de 1000 x 1000).

Arquitectura cognitiva híbrida para la navegación autónoma de UAVs mediante mapas topológicos visuales

El objetivo fundamental de la presente tesis doctoral es el diseño de una arquitectura cognitiva, que pueda ser empleada para la navegación autónoma de vehículos aéreos no tripulados conocidos como UAV (Unmanned Aerial Vehicle). Dicha arquitectura cognitiva se apoya en la definición de una librería de comportamientos, que aportarán la inteligencia necesaria al UAV para alcanzar los objetivos establecidos, en base a la información sensorial recopilada del entorno de operación. La navegación autónoma del UAV se apoyará en la utilización de un mapa topológico visual, consistente en la definición de un grafo que engloba mediante nodos los diferentes landmarks ubicados en el entorno, y que le servirán al UAV de guía para alcanzar su objetivo. Los arcos establecidos entre los nodos del mapa topológico, le proporcionarán de la información necesaria para establecer el rumbo más adecuado para alcanzar el siguiente landmark a visitar, siguiendo siempre una secuencia lógica de navegación, basada en la distancia entre un determinado landmark con respecto al objetivo final ó landmark destino. La arquitectura define un mecanismo híbrido de control, el cual puede conmutar entre dos diferentes modos de navegación. El primero es el denominado como Search Mode, el cual se activará cuando el UAV se encuentre en un estado desconocido dentro del entorno, para lo cual hará uso de cálculos basado en la entropía para la búsqueda de posibles landmarks. Se empleará como estrategia novedosa la idea de que la entropía de una imagen tiene una correlación directa con respecto a la probabilidad de que dicha imagen contenga uno ó varios landmarks. De esta forma, la estrategia para la búsqueda de nuevos landmarks en el entorno, se basará en un proceso continuo de maximización de la entropía. Si por el contrario el UAV identifica la existencia de un posible landmark entre los definidos en su mapa topológico, se considerará que está sobre un estado conocido, por lo que se conmutará al segundo modo de navegación denominado como Homing Mode, el cual se encargará de calcular señales de control para la aproximación del UAV al landmark localizado. Éste último modo implementa un control dual basado en dos tipos de controladores (FeedForward/FeedBack) que mediante su combinación, aportarán al UAV señales de control cada vez más óptimas, además de llevar a cabo un entrenamiento continuo y en tiempo real. Para cumplir con los requisitos de ejecución y aprendizaje en tiempo real de la arquitectura, se han tomado como principales referencias dos paradigmas empleados en diferentes estudios dentro del área de la robótica, como son el paradigma de robots de desarrollo (developmental robots) basado en un aprendizaje del robot en tiempo real y de forma adaptativa con su entorno, así como del paradigma de modelos internos (internal models) basado en los resultados obtenidos a partir de estudios neurocientíficos del cerebelo humano; dicho modelo interno sirve de base para la construcción del control dual de la arquitectura. Se presentarán los detalles de diseño e implementación de los diferentes módulos que componen la arquitectura cognitiva híbrida, y posteriormente, los diferentes resultados obtenidos a partir de las pruebas experimentales ejecutadas, empleando como UAV la plataforma robótica aérea de AR.Drone. Como resultado final se ha obtenido una validación completa de la arquitectura cognitiva híbrida objetivo de la tesis, cumplimento con la totalidad de requisitos especificados y garantizando su viabilidad como aplicación operativa en el mundo real. Finalmente, se muestran las distintas conclusiones a las cuales se ha llegado a partir de los resultados experimentales, y se presentan las diferentes líneas de investigación futuras que podrán ser ejecutadas.

Optimización de una energía mediante cortes de grafos. Segmentación de imágenes

La segmentación de imágenes puede plantearse como un problema de minimización de una energía discreta. Nos enfrentamos así a una doble cuestión: definir una energía cuyo mínimo proporcione la segmentación buscada y, una vez definida la energía, encontrar un mínimo absoluto de la misma. La primera parte de esta tesis aborda el segundo problema, y la segunda parte, en un contexto más aplicado, el primero. Las técnicas de minimización basadas en cortes de grafos permiten obtener el mínimo de una energía discreta en tiempo polinomial mediante algoritmos de tipo min-cut/max-flow. Sin embargo, estas técnicas solo pueden aplicarse a energías que son representabas por grafos. Un importante reto es estudiar qué energías son representabas así como encontrar un grafo que las represente, lo que equivale a encontrar una función gadget con variables adicionales. En la primera parte de este trabajo se estudian propiedades de las funciones gadgets que permiten acotar superiormente el número de variables adicionales. Además se caracterizan las energías con cuatro variables que son representabas, definiendo gadgets con dos variables adicionales. En la segunda parte, más práctica, se aborda el problema de segmentación de imágenes médicas, base en muchas ocasiones para la diagnosis y el seguimiento de terapias. La segmentación multi-atlas es una potente técnica de segmentación automática de imágenes médicas, con tres aspectos importantes a destacar: el tipo de registro entre los atlas y la imagen objetivo, la selección de atlas y el método de fusión de etiquetas. Este último punto puede formularse como un problema de minimización de una energía. A este respecto introducimos dos nuevas energías representables. La primera, de orden dos, se utiliza en la segmentación en hígado y fondo de imágenes abdominales obtenidas mediante tomografía axial computarizada. La segunda, de orden superior, se utiliza en la segmentación en hipocampos y fondo de imágenes cerebrales obtenidas mediante resonancia magnética. ABSTRACT The image segmentation can be described as the problem of minimizing a discrete energy. We face two problems: first, to define an energy whose minimum provides the desired segmentation and, second, once the energy is defined we must find its global minimum. The first part of this thesis addresses the second problem, and the second part, in a more applied context, the first problem. Minimization techniques based on graph cuts find the minimum of a discrete energy in polynomial time via min-cut/max-flow algorithms. Nevertheless, these techniques can only be applied to graph-representable energies. An important challenge is to study which energies are graph-representable and to construct graphs which represent these energies. This is the same as finding a gadget function with additional variables. In the first part there are studied the properties of gadget functions which allow the number of additional variables to be bounded from above. Moreover, the graph-representable energies with four variables are characterised and gadgets with two additional variables are defined for these. The second part addresses the application of these ideas to medical image segmentation. This is often the first step in computer-assisted diagnosis and monitoring therapy. Multiatlas segmentation is a powerful automatic segmentation technique for medical images, with three important aspects that are highlighted here: the registration between the atlas and the target image, the atlas selection, and the label fusion method. We formulate the label fusion method as a minimization problem and we introduce two new graph-representable energies. The first is a second order energy and it is used for the segmentation of the liver in computed tomography (CT) images. The second energy is a higher order energy and it is used for the segmentation of the hippocampus in magnetic resonance images (MRI).

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.

Las lecturas de Sáenz de Oíza. Desde Torres Blancas al Banco de Bilbao a través de una selección de textos hecha por el propio arquitecto.

El 29 de enero de 2000 Francisco Javier Sáenz de Oíza ofrece su última conferencia en el salón de actos del edificio sede del BBVA en el Paseo de la Castellana de Madrid. Esta conferencia inaugura el ciclo “El arquitecto enseña su obra”, organizado por el Colegio Oficial de Arquitectos de Madrid (C.O.A.M.) y la Escuela Técnica Superior de Arquitectura de Madrid (E.T.S.A.M.). Las obras en concreto que Oíza 'enseña' en este evento son Torres Blancas (Madrid, 1961- 1968) y Banco de Bilbao (Madrid, 1971-1980). Antes de la conferencia, blandiendo una carpeta, Oíza dice: Traigo aquí los textos de siempre, los que siempre he usado, (...) yo no he escrito ni una línea, solo he subrayado ciertos pasajes, en la medida de lo posible me gustaría leer alguno. Pero como aquí hay como para cinco horas, pues no se qué hacer. Citarlo sí, porque de ustedes el que quiera penetrar un poco en mi conocimiento, pues que vea las citas que yo hago aquí, qué pasajes, o qué libros o qué artículos propongo. 1 La carpeta que lleva Oíza en su mano contiene veinticuatro fichas mecanografiadas por él mismo. Las fichas son pasajes de textos; en su mayoría de textos literarios o poéticos, e incluyen una referencia bibliográfica que menciona: título de libro, edición y número de página. Además, en cada ficha están resaltados los pasajes que Oíza pretende leer. 2 Antes del comienzo de la conferencia Oíza dice: Tengo aquí citas de lecturas que le recomendaría a quien quiera enterarse de cómo es este edificio. 3 Durante la conferencia Oíza no parece hablar sobre las obras que debe enseñar; en cambio se dedica, casi exclusivamente, a leer en público. Esta tesis nace de lo sugerido por el propio Oíza. El objetivo general, siguiendo sus propias palabras, es 'penetrar un poco' en su conocimiento a partir de citas y recomendaciones de lecturas realizadas por él mismo al tratar sobre arquitectura. La hipótesis central plantea que por medio de sus lecturas Oíza sí habla de arquitectura, y sostiene también que a partir de sus textos es posible 'enterarse', al menos en parte, de cómo es un edificio, en particular Torres Blancas y Banco de Bilbao. Más aún, se plantea la hipótesis de que Oíza, maestro ágrafo y de carácter socrático, ha construido, no obstante, un 'discurso teórico' arquitectónico suficientemente sistemático. De modo que aún cuando Oíza no ha dejado una 'teoría' escrita es posible reconstruirla, en cierta medida, a partir de su elocución y a partir de la comprensión de sus 'lecturas'. Las fuentes primarias de esta tesis son: a) Las lecturas que Oíza recomienda en su conferencia de enero de 2000. b) Torres Blancas y Banco de Bilbao. c) Las lecturas en público realizadas por Oíza en conferencias, cursos, debates, mesas redondas, programas de TV, etc. El tema que se investiga es la relación entre los textos recomendados por Oíza y su arquitectura, y la pregunta guía de la investigación es cómo y en qué medida los textos pueden contribuir a la comprensión del pensamiento, del discurso y de la obra de Oíza. Torres Blancas y Banco de Bilbao son, en todo momento, las dos principales obras utilizadas para la observación y el contraste de los resultados de la investigación teórica en el desarrollo de la tesis. El soporte teórico y metodológico de la tesis está dado por la hermenéutica en tanto disciplina encargada de la interpretación y correcta comprensión de textos y obras, en particular por la filosofía hermenéutica de Hans-Georg Gadamer expuesta en Verdad y método. La relevancia, el aspecto original y la posible aportación al conocimiento de esta tesis consiste en una aproximación a Oíza y a su arquitectura, desde un punto de vista hasta ahora no investigado de forma sistemática, esto es, a partir de las lecturas de Oíza. ABSTRACT On 29th January 2000 Francisco Javier Sáenz de Oíza gave his last lecture in the Auditorium at BBVA headquarters located in Paseo de la Castellana avenue in Madrid. That lecture opened the series The Architect Shows his Work (El arquitecto enseña su obra) organised by the COAM Official College of Architects and the ETSAM Architecture School of Madrid. The specific works that Oíza 'shows' in his lecture were Torres Blancas (Madrid, 1961- 1968) and Banco de Bilbao (Madrid, 1971-1980). Before the lecture, waving a folder in his hand, Oíza says: I've got here the texts I've always used, (…) I haven't written a line, I've only underlined certain passages, I would like to read some of them to the extent possible. But I have here about five hours of reading, so I don't know what to do. I can cite them, yes, and anyone of you who want to delve a little into my knowledge can look at the citations I make here, the passages, books or articles I recommend. 1 The folder in Oíza's hand contains 24 files typed by the architect himself. The files consist of text passages -most of which are literary or poetry texts- and include the bibliographic citation with book the title, edition and page number. In addition, the passages Oíza intends to read are highlighted. Before starting his lecture Oíza says: I've got here citations of readings I'd recommend to those who want to realise how this building is. 2 During the lecture Oíza doesn't seem to be talking about the works he has to show, on the contrary, he focuses almost exclusively on reading texts to the audience. This thesis is the result of a suggestion made by Oíza himself. The broad aim is to 'delve a little into' his knowledge using citations and reading recommendations made by Oíza when dealing with the architecture subject. The main hypothesis proposes that Oíza talks about architecture through his readings and that starting from 'his' texts it is possible to 'realise', at least in part, how a building is, Torres Blancas and Banco de Bilbao in particular. Moreover, it is proposed the hypothesis that Oíza, as a Socratic teacher reluctant to write down his ideas, has nevertheless built a systematic 'theoretical discourse' on architecture. As a result, even when he has not written a 'theory', it is possible to reconstruct it to a certain degree, starting from his speech and from the understanding of his readings. The primary sources for this thesis are: a) The readings that Oíza recommends in his lecture of January 2000. b) The Torres Blancas and Banco de Bilbao. c) The readings done by Oíza in presentations, lectures, debates, panel discussions, television programmes, etc. The subject under research is the relationship between the texts that Oíza recommends and his architecture. The guiding question for the research is how and to what extent the texts can contribute to the understanding of Oíza's thoughts, discourse and work. Torres Blancas and Banco de Bilbao are the two main works considered along the thesis and they have been used for observation and to test the results of the theoretical research as it progresses. The thesis theoretical and methodological framework is based on the hermeneutics -as the discipline that deals with the interpretation and the correct understanding of texts and works-, in particular the hermeneutics philosophy of Hans-Georg Gadamer in Truth and Method. The relevance, the original element and the possible contribution of this thesis is given by the approach to Oíza and his architecture through Oíza's readings, a perspective that hasn't been yet systematically researched.

Aprendizaje colaborativo en enseñanza a distancia: entorno genérico para configurar, realizar y analizar actividades en grupo

En esta tesis se ha profundizado en el estudio y desarrollo de modelos de soporte para el aprendizaje colaborativo a distancia, que ha permitido proponer una arquitectura fundamentada en los principios del paradigma CSCL (Computer Supported Collaborative Learning). La arquitectura propuesta aborda un tipo de problema concreto que requiere el uso de técnicas derivadas del Trabajo Colaborativo, la Inteligencia Artificial, Interfaces de Usuario así como ideas tomadas de la Pedagogía y la Psicología. Se ha diseñado una solución completa, abierta y genérica. La arquitectura aprovecha las nuevas tecnologías para lograr un sistema efectivo de apoyo a la educación a distancia. Está organizada en cuatro niveles: el de Configuración, el de Experiencia, el de Organización y el de Análisis. A partir de ella se ha implementado un sistema llamado DEGREE. En DEGREE, cada uno de los niveles de la arquitectura da lugar a un subsistema independiente pero relacionado con los otros. La aplicación saca partido del uso de espacios de trabajo estructurados. El subsistema Configurador de Experiencias permite definir los elementos de un espacio de trabajo y una experiencia y adaptarlos a cada tipo de usuario. El subsistema Manejador de Experiencias recoge las contribuciones de los usuarios para construir una solución conjunta de un problema. Las intervenciones de los alumnos se estructuran basándose en un grafo conversacional genérico. Además, se registran todas las acciones de los usuarios para representar explícitamente el proceso completo que lleva a la solución. Estos datos también se almacenan en una memoria común que constituye el subsistema llamado Memoria Organizativa de Experiencias. El subsistema Analizador estudia las intervenciones de los usuarios. Este análisis permite inferir conclusiones sobre la forma en que trabajan los grupos y sus actitudes frente a la colaboración, teniendo en cuenta además el conocimiento subjetivo del observador. El proceso de desarrollo en paralelo de la arquitectura y el sistema ha seguido un ciclo de refinamiento en cinco fases con sucesivas etapas de prototipado y evaluación formativa. Cada fase de este proceso se ha realizado con usuarios reales y se han considerado las opiniones de los usuarios para mejorar las funcionalidades de la arquitectura así como la interfaz del sistema. Esta aproximación ha permitido, además, comprobar la utilidad práctica y la validez de las propuestas que sustentan este trabajo.---ABSTRACT---In this thesis, we have studied in depth the development of support models for distance collaborative learning and subsequently devised an architecture based on the Computer Supported Collaborative Learning paradigm principles. The proposed architecture addresses a specific problem: coordinating groups of students to perform collaborative distance learning activities. Our approach uses Cooperative Work, Artificial Intelligence and Human-Computer Interaction techniques as well as some ideas from the fields of Pedagogy and Psychology. We have designed a complete, open and generic solution. Our architecture exploits the new information technologies to achieve an effective system for education purposes. It is organised into four levels: Configuration, Experience, Organisation and Reflection. This model has been implemented into a system called DEGREE. In DEGREE, each level of the architecture gives rise to an independent subsystem related to the other ones. The application benefits from the use of shared structured workspaces. The configuration subsystem allows customising the elements that define an experience and a workspace. The experience subsystem gathers the users' contributions to build joint solutions to a given problem. The students' interventions build up a structure based on a generic conversation graph. Moreover, all user actions are registered in order to represent explicitly the complete process for reaching the group solution. Those data are also stored into a common memory, which constitutes the organisation subsystem. The user interventions are studied by the reflection subsystem. This analysis allows us inferring conclusions about the way in which the group works and its attitudes towards collaboration. The inference process takes into account the observer's subjective knowledge. The process of developing both the architecture and the system in parallel has run through a five-pass cycle involving successive stages of prototyping and formative evaluation. At each stage of that process, we have considered the users' feedback for improving the architecture's functionalities as well as the system interface. This approach has allowed us to prove the usability and validity of our proposal.

Interpretación geométrica de redes neuronales recurrentes discretas mediante grafos completos

El objetivo del presente trabajo de investigación es explorar nuevas técnicas de implementación, basadas en grafos, para las Redes de Neuronas, con el fin de simplificar y optimizar las arquitecturas y la complejidad computacional de las mismas. Hemos centrado nuestra atención en una clase de Red de Neuronas: las Redes de Neuronas Recursivas (RNR), también conocidas como redes de Hopfield. El problema de obtener la matriz sináptica asociada con una RNR imponiendo un determinado número de vectores como puntos fijos, no está en absoluto resuelto, el número de vectores prototipo que pueden ser almacenados en la red, cuando se utiliza la ley de Hebb, es bastante limitado, la red se satura rápidamente cuando se pretende almacenar nuevos prototipos. La ley de Hebb necesita, por tanto, ser revisada. Algunas aproximaciones dirigidas a solventar dicho problema, han sido ya desarrolladas. Nosotros hemos desarrollado una nueva aproximación en la forma de implementar una RNR en orden a solucionar estos problemas. La matriz sináptica es obtenida mediante la superposición de las componentes de los vectores prototipo, sobre los vértices de un Grafo, lo cual puede ser también interpretado como una coloración de dicho grafo. Cuando el periodo de entrenamiento se termina, la matriz de adyacencia del Grafo Resultante o matriz de pesos, presenta ciertas propiedades por las cuales dichas matrices serán llamadas tetraédricas. La energía asociada a cualquier estado de la red es representado por un punto (a,b) de R2. Cada uno de los puntos de energía asociados a estados que disten lo mismo del vector cero está localizado sobre la misma línea de energía de R2. El espacio de vectores de estado puede, por tanto, clasificarse en n clases correspondientes a cada una de las n diferentes distancias que puede tener cualquier vector al vector cero. La matriz (n x n) de pesos puede reducirse a un n-vector; de esta forma, tanto el tiempo de computación como el espacio de memoria requerido par almacenar los pesos, son simplificados y optimizados. En la etapa de recuperación, es introducido un vector de parámetros R2, éste es utilizado para controlar la capacidad de la red: probaremos que lo mayor es la componente a¡, lo menor es el número de puntos fijos pertenecientes a la línea de energía R¡. Una vez que la capacidad de la red ha sido controlada mediante este parámetro, introducimos otro parámetro, definido como la desviación del vector de pesos relativos, este parámetro sirve para disminuir ostensiblemente el número de parásitos. A lo largo de todo el trabajo, hemos ido desarrollando un ejemplo, el cual nos ha servido para ir corroborando los resultados teóricos, los algoritmos están escritos en un pseudocódigo, aunque a su vez han sido implamentados utilizando el paquete Mathematica 2.2., mostrándolos en un volumen suplementario al texto.---ABSTRACT---The aim of the present research is intended to explore new specifícation techniques of Neural Networks based on Graphs to be used in the optimization and simplification of Network Architectures and Computational Complexhy. We have focused our attention in a, well known, class of Neural Networks: the Recursive Neural Networks, also known as Hopfield's Neural Networks. The general problem of constructing the synaptic matrix associated with a Recursive Neural Network imposing some vectors as fixed points is fer for completery solved, the number of prototype vectors (learning patterns) which can be stored by Hebb's law is rather limited and the memory will thus quickly reach saturation if new prototypes are continuously acquired in the course of time. Hebb's law needs thus to be revised in order to allow new prototypes to be stored at the expense of the older ones. Some approaches related with this problem has been developed. We have developed a new approach of implementing a Recursive Neural Network in order to sob/e these kind of problems, the synaptic matrix is obtained superposing the components of the prototype vectors over the vértices of a Graph which may be interpreted as a coloring of the Graph. When training is finished the adjacency matrix of the Resulting Graph or matrix of weights presents certain properties for which it may be called a tetrahedral matrix The energy associated to any possible state of the net is represented as a point (a,b) in R2. Every one of the energy points associated with state-vectors having the same Hamming distance to the zero vector are located over the same energy Une in R2. The state-vector space may be then classified in n classes according to the n different possible distances firom any of the state-vectors to the zero vector The (n x n) matrix of weights may also be reduced to a n-vector of weights, in this way the computational time and the memory space required for obtaining the weights is optimized and simplified. In the recall stage, a parameter vectora is introduced, this parameter is used for controlling the capacity of the net: it may be proved that the bigger is the r, component of J, the lower is the number of fixed points located in the r¡ energy line. Once the capacity of the net has been controlled by the ex parameter, we introduced other parameter, obtained as the relative weight vector deviation parameter, in order to reduce the number of spurious states. All along the present text, we have also developed an example, which serves as a prove for the theoretical results, the algorithms are shown in a pseudocode language in the text, these algorithm so as the graphics have been developed also using the Mathematica 2.2. mathematical package which are shown in a supplementary volume of the text.