Label space reduction in GMPLs and All-Optical Label Swapping networks

All-Optical Label Swapping (AOLS) es una tecnología clave para la implementación de nodos de conmutación completamente óptica de paquetes. Sin embargo, el costo de su desarrollo es proporcional al tamaño del espacio de etiquetas (label space). Debido a que los principios de funcionamiento de AOLS son casos particulares de los del MultiProtocol Label Switching (MPLS), esta tesis estudia métodos generales, aplicables a ambos, con el propósito de reducir el espacio de etiquetas tanto como sea posible. Modelos de programación lineal entera y heurísticas son propuestos para el caso en el que se permite apilar una etiqueta extra. Encontramos que cerca del 50% del espacio de etiquetas puede ser reducido, si se permite colocar una etiqueta extra en la pila. Además, particularmente para AOLS, encontramos que se puede reducir el espacio de etiquetas cerca al 25% si se duplica la capacidad de los enlaces y se permite re-encaminar el tráfico.

Manifold clustering for motion segmentation

En aquesta tesi s’estudia el problema de la segmentació del moviment. La tesi presenta una revisió dels principals algoritmes de segmentació del moviment, s’analitzen les característiques principals i es proposa una classificació de les tècniques més recents i importants. La segmentació es pot entendre com un problema d’agrupament d’espais (manifold clustering). Aquest estudi aborda alguns dels reptes més difícils de la segmentació de moviment a través l’agrupament d’espais. S’han proposat nous algoritmes per a l’estimació del rang de la matriu de trajectòries, s’ha presenta una mesura de similitud entre subespais, s’han abordat problemes relacionats amb el comportament dels angles canònics i s’ha desenvolupat una eina genèrica per estimar quants moviments apareixen en una seqüència. L´ultima part de l’estudi es dedica a la correcció de l’estimació inicial d’una segmentació. Aquesta correcció es du a terme ajuntant els problemes de la segmentació del moviment i de l’estructura a partir del moviment.

Robustness against large-scale failures in communications networks

This thesis studies robustness against large-scale failures in communications networks. If failures are isolated, they usually go unnoticed by users thanks to recovery mechanisms. However, such mechanisms are not effective against large-scale multiple failures. Large-scale failures may cause huge economic loss. A key requirement towards devising mechanisms to lessen their impact is the ability to evaluate network robustness. This thesis focuses on multilayer networks featuring separated control and data planes. The majority of the existing measures of robustness are unable to capture the true service degradation in such a setting, because they rely on purely topological features. One of the major contributions of this thesis is a new measure of functional robustness. The failure dynamics is modeled from the perspective of epidemic spreading, for which a new epidemic model is proposed. Another contribution is a taxonomy of multiple, large-scale failures, adapted to the needs and usage of the field of networking.

A formalization for multi-agent decision support in cooperative environments. A framework for situated agents

La tesis propone un marco de trabajo para el soporte de la toma de decisiones adecuado para soportar la ejecución distribuida de acciones cooperativas en entornos multi-agente dinámicos y complejos. Soporte para la toma de decisiones es un proceso que intenta mejorar la ejecución de la toma de decisiones en escenarios cooperativos. Este proceso ocurre continuamente en la vida diaria. Los humanos, por ejemplo, deben tomar decisiones acerca de que ropa usar, que comida comer, etc. En este sentido, un agente es definido como cualquier cosa que está situada en un entorno y que actúa, basado en su observación, su interpretación y su conocimiento acerca de su situación en tal entorno para lograr una acción en particular.Por lo tanto, para tomar decisiones, los agentes deben considerar el conocimiento que les permita ser consientes en que acciones pueden o no ejecutar. Aquí, tal proceso toma en cuenta tres parámetros de información con la intención de personificar a un agente en un entorno típicamente físico. Así, el mencionado conjunto de información es conocido como ejes de decisión, los cuales deben ser tomados por los agentes para decidir si pueden ejecutar correctamente una tarea propuesta por otro agente o humano. Los agentes, por lo tanto, pueden hacer mejores decisiones considerando y representando apropiadamente tal información. Los ejes de decisión, principalmente basados en: las condiciones ambientales, el conocimiento físico y el valor de confianza del agente, provee a los sistemas multi-agente un confiable razonamiento para alcanzar un factible y exitoso rendimiento cooperativo.Actualmente, muchos investigadores tienden a generar nuevos avances en la tecnología agente para incrementar la inteligencia, autonomía, comunicación y auto-adaptación en escenarios agentes típicamente abierto y distribuidos. En este sentido, esta investigación intenta contribuir en el desarrollo de un nuevo método que impacte tanto en las decisiones individuales como colectivas de los sistemas multi-agente. Por lo tanto, el marco de trabajo propuesto ha sido utilizado para implementar las acciones concretas involucradas en el campo de pruebas del fútbol robótico. Este campo emula los juegos de fútbol real, donde los agentes deben coordinarse, interactuar y cooperar entre ellos para solucionar tareas complejas dentro de un escenario dinámicamente cambiante y competitivo, tanto para manejar el diseño de los requerimientos involucrados en las tareas como para demostrar su efectividad en trabajos colectivos. Es así que los resultados obtenidos tanto en el simulador como en el campo real de experimentación, muestran que el marco de trabajo para el soporte de decisiones propuesto para agentes situados es capaz de mejorar la interacción y la comunicación, reflejando en un adecuad y confiable trabajo en equipo dentro de entornos impredecibles, dinámicos y competitivos. Además, los experimentos y resultados también muestran que la información seleccionada para generar los ejes de decisión para situar a los agentes, es útil cuando tales agentes deben ejecutar una acción o hacer un compromiso en cada momento con la intención de cumplir exitosamente un objetivo colectivo. Finalmente, algunas conclusiones enfatizando las ventajas y utilidades del trabajo propuesto en la mejora del rendimiento colectivo de los sistemas multi-agente en situaciones tales como tareas coordinadas y asignación de tareas son presentadas.

A proposal for the diagnosis of uncertain dynamic systems based on interval models

The performance of a model-based diagnosis system could be affected by several uncertainty sources, such as,model errors,uncertainty in measurements, and disturbances. This uncertainty can be handled by mean of interval models.The aim of this thesis is to propose a methodology for fault detection, isolation and identification based on interval models. The methodology includes some algorithms to obtain in an automatic way the symbolic expression of the residual generators enhancing the structural isolability of the faults, in order to design the fault detection tests. These algorithms are based on the structural model of the system. The stages of fault detection, isolation, and identification are stated as constraint satisfaction problems in continuous domains and solved by means of interval based consistency techniques. The qualitative fault isolation is enhanced by a reasoning in which the signs of the symptoms are derived from analytical redundancy relations or bond graph models of the system. An initial and empirical analysis regarding the differences between interval-based and statistical-based techniques is presented in this thesis. The performance and efficiency of the contributions are illustrated through several application examples, covering different levels of complexity.

Dynamic task allocation and coordination in cooperative multi-agent environments

La coordinació i assignació de tasques en entorns distribuïts ha estat un punt important de la recerca en els últims anys i aquests temes són el cor dels sistemes multi-agent. Els agents en aquests sistemes necessiten cooperar i considerar els altres agents en les seves accions i decisions. A més a més, els agents han de coordinar-se ells mateixos per complir tasques complexes que necessiten més d'un agent per ser complerta. Aquestes tasques poden ser tan complexes que els agents poden no saber la ubicació de les tasques o el temps que resta abans de que les tasques quedin obsoletes. Els agents poden necessitar utilitzar la comunicació amb l'objectiu de conèixer la tasca en l'entorn, en cas contrari, poden perdre molt de temps per trobar la tasca dins de l'escenari. De forma similar, el procés de presa de decisions distribuït pot ser encara més complexa si l'entorn és dinàmic, amb incertesa i en temps real. En aquesta dissertació, considerem entorns amb sistemes multi-agent amb restriccions i cooperatius (dinàmics, amb incertesa i en temps real). En aquest sentit es proposen dues aproximacions que permeten la coordinació dels agents. La primera és un mecanisme semi-centralitzat basat en tècniques de subhastes combinatòries i la idea principal es minimitzar el cost de les tasques assignades des de l'agent central cap als equips d'agents. Aquest algoritme té en compte les preferències dels agents sobre les tasques. Aquestes preferències estan incloses en el bid enviat per l'agent. La segona és un aproximació d'scheduling totalment descentralitzat. Això permet als agents assignar les seves tasques tenint en compte les preferències temporals sobre les tasques dels agents. En aquest cas, el rendiment del sistema no només depèn de la maximització o del criteri d'optimització, sinó que també depèn de la capacitat dels agents per adaptar les seves assignacions eficientment. Addicionalment, en un entorn dinàmic, els errors d'execució poden succeir a qualsevol pla degut a la incertesa i error de accions individuals. A més, una part indispensable d'un sistema de planificació és la capacitat de re-planificar. Aquesta dissertació també proveeix una aproximació amb re-planificació amb l'objectiu de permetre als agent re-coordinar els seus plans quan els problemes en l'entorn no permeti la execució del pla. Totes aquestes aproximacions s'han portat a terme per permetre als agents assignar i coordinar de forma eficient totes les tasques complexes en un entorn multi-agent cooperatiu, dinàmic i amb incertesa. Totes aquestes aproximacions han demostrat la seva eficiència en experiments duts a terme en l'entorn de simulació RoboCup Rescue.

Egalitarian behaviour in multi unit combinatorial auctions

En entornos donde los recursos son precederos y la asignación de recursos se repite en el tiempo con el mismo conjunto o un conjunto muy similar de agentes, las subastas recurrentes pueden ser utilizadas. Una subasta recurrente es una secuencia de subastas donde el resultado de una subasta puede influenciar en las siguientes. De todas formas, este tipo de subastas tienen problemas particulares cuando la riqueza de los agentes esta desequilibrada y los recursos son precederos. En esta tesis se proponen algunos mecanismos justos o equitativos para minimizar los efectos de estos problemas. En una subasta recurrente una solución justa significa que todos los participantes consiguen a largo plazo sus objetivos en el mismo grado o en el grado más parecido posible, independientemente de su riqueza. Hemos demostrado experimentalmente que la inclusión de justicia incentiva a los bidders en permanecer en la subasta minimizando los problemas de las subastas recurrentes.

Introspection on control-grounded capabilities. An agent inspired approach for control

Introspecció sobre la dinàmica dels agents té un important impacte en decisions individuals i cooperatives en entorns multi-agent. Introspecció, una habilitat cognitiva provinent de la metàfora "agent", permet que els agents siguin conscients de les seves capacitats per a realitzar correctament les tasques. Aquesta introspecció, principalment sobre capacitats relacionades amb la dinàmica, proporciona als agents un raonament adequat per a assolir compromisos segurs en sistemes cooperatius. Per a tal fi, les capacitats garanteixen una representació adequada i explícita de tal dinàmica. Aquest enfocament canvia i millora la manera com els agents poden coordinar-se per a portar a terme tasques i com gestionar les seves interaccions i compromisos en entorns cooperatius. L'enfocament s'ha comprovat en escenaris on la coordinació és important, beneficiosa i necessària. Els resultats i les conclusions són presentats ressaltant els avantatges de la introspecció en la millora del rendiment dels sistemes multi-agent en tasques coordinades i assignació de tasques.

Prediction of postprandial blood glucose under intra-patient variability and uncertainty and its use in the design of insulin dosing strategies for type 1 diabetic patients

In this thesis I propose a novel method to estimate the dose and injection-to-meal time for low-risk intensive insulin therapy. This dosage-aid system uses an optimization algorithm to determine the insulin dose and injection-to-meal time that minimizes the risk of postprandial hyper- and hypoglycaemia in type 1 diabetic patients. To this end, the algorithm applies a methodology that quantifies the risk of experiencing different grades of hypo- or hyperglycaemia in the postprandial state induced by insulin therapy according to an individual patient’s parameters. This methodology is based on modal interval analysis (MIA). Applying MIA, the postprandial glucose level is predicted with consideration of intra-patient variability and other sources of uncertainty. A worst-case approach is then used to calculate the risk index. In this way, a safer prediction of possible hyper- and hypoglycaemic episodes induced by the insulin therapy tested can be calculated in terms of these uncertainties.

Robustness on resource allocation problems

En problemes d'assignació de recursos, normalment s'han de tenir en compte les incerteses que poden provocar canvis en les dades inicials. Aquests canvis dificulten l'aplicabilitat de les planificacions que s'hagin fet inicialment. Aquesta tesi se centra en l'elaboració de tècniques que consideren la incertesa alhora de cercar solucions robustes, és a dir solucions que puguin continuar essent vàlides encara que hi hagi canvis en l'entorn. Particularment, introduïm el concepte de robustesa basat en reparabilitat, on una solució robusta és una que pot ser reparada fàcilment en cas que hi hagi incidències. La nostra aproximació es basa en lògica proposicional, codificant el problema en una fórmula de satisfactibilitat Booleana, i aplicant tècniques de reformulació per a la generació de solucions robustes. També presentem un mecanisme per a incorporar flexibilitat a les solucions robustes, de manera que es pugui establir fàcilment el grau desitjat entre robustesa i optimalitat de les solucions.

Semiactive control strategies for vibration mitigation in adaptronic structures equipped with magnetorheological dampers

Los sistemas tales como edificios y veh¨ªculos est¨¢n sujetos a vibraciones que pueden causar mal funcionamiento, incomodidad o colapso. Para mitigar estas vibraciones, se suelen instalar amortiguadores. Estas estructuras se convierten en sistemas adaptr¨®nicos cuando los amortiguadores son controlables. Esta tesis se enfoca en la soluci¨®n del problema de vibraciones en edificios y veh¨ªculos usando amortiguadores magnetoreol¨®gicos (MR). Estos son unos amortiguadores controlables caracterizados por una din¨¢mica altamente no lineal. Adem¨¢s, los sistemas donde se instalan se caracterizan por la incertidumbre param¨¦trica, la limitaci¨®n de medidas y las perturbaciones desconocidas, lo que obliga al uso de t¨¦cnicas complejas de control. En esta tesis se usan Backstepping, QFT y H2/H¡Þ mixto para resolver el problema. Las leyes de control se verifican mediante simulaci¨®n y experimentaci¨®n.

Desenvolupament d'un sistema expert com a eina per a una millor gestió de la qualitat de les aigües fluvials

Avui en dia no es pot negar el fet que els humans són un component més de les conques fluvials i que la seva activitat afecta enormement la qualitat de les aigües. A nivell europeu, l'elevada densitat de població situada en les conques fluvials ha comportat un increment de la mala qualitat de les seves aigües fluvials. En les darreres dècades l'increment de les càrregues de nutrients en els sistemes aquàtics ha esdevingut un problema prioritari a solucionar per les administracions competents en matèria d'aigua. La gestió dels ecosistemes fluvials no és una tasca fàcil. Els gestors es troben amb què són sistemes molt complexos, donada l'estreta relació existent entre els ecosistemes fluvials i els ecosistemes terrestres que drenen. Addicionalment a la complexitat d'aquests sistemes es troba la dificultat associada de la gestió o control de les entrades de substàncies contaminants tant de fonts puntuals com difoses. Per totes aquestes raons la gestió de la qualitat de les aigües fluvials esdevé una tasca complexa que requereix un enfocament multidisciplinar. Per tal d'assolir aquest enfocament diverses eines han estat utilitzades, des de models matemàtics fins a sistemes experts i sistemes de suport a la decisió. Però, la major part dels esforços han estat encarats cap a la resolució de problemes de reduïda complexitat, fent que molts dels problemes ambientals complexos, com ara la gestió dels ecosistemes fluvials, no hagin estat vertaderament tractats. Per tant, es requereix l'aplicació d'eines que siguin de gran ajuda en els processos de presa de decisions i que incorporin un ampli coneixement heurístic i empíric: sistemes experts i sistemes de suport a la decisió. L'òptima gestió de la qualitat de l'aigua fluvial requereix una aproximació integrada i multidisciplinar, que pot ésser aconseguida amb una eina intel·ligent construïda sobre els conceptes i mètodes del raonament humà. La present tesi descriu la metodologia desenvolupada i aplicada per a la creació i construcció d'un Sistema Expert, així com el procés de desenvolupament d'aquest Sistema Expert, com el principal mòdul de raonament d'un Sistema de Suport a la Decisió Ambiental. L'objectiu principal de la present tesi ha estat el desenvolupament d'una eina d'ajuda en el procés de presa de decisions dels gestors de l'aigua en la gestió de trams fluvials alterats antròpicament per tal de millorar la qualitat de la seva aigua fluvial. Alhora, es mostra el funcionament de l'eina desenvolupada a través de dos casos d'estudi. Els resultats derivats del Sistema Expert desenvolupat, implementat i presentat en la present tesi mostren que aquests sistemes poden ésser eines útils per a millorar la gestió dels ecosistemes fluvials.

Entorno virtual para el aprendizaje y la evaluación automática en bases de datos

La enseñanza y evaluación automática a través de un sistema Computer Based Assessment (CBA) requiere de software especializado que se adapte a la tipología de actividades a tratar y evaluar. En esta tesis se ha desarrollado un entorno CBA que facilita el aprendizaje y evaluación de los principales temas de una asignatura de bases de datos. Para ello se han analizado las herramientas existentes en cada uno de estos temas (Diagramas Entidad/Relación, diagramas de clases, esquemas de bases de datos relacionales, normalización, consultas en álgebra relacional y lenguaje SQL) y para cada uno de ellos se ha analizado, diseñado e implementado un módulo de corrección y evaluación automática que aporta mejoras respecto a los existentes. Estos módulos se han integrado en un mismo entorno al que hemos llamado ACME-DB.

Optimization of inverse reflector design

Aquesta tesi presenta un nou mètode pel disseny invers de reflectors. Ens hem centrat en tres temes principals: l’ús de fonts de llum reals i complexes, la definició d’un algoritme ràpid pel càlcul de la il•luminació del reflector, i la definició d’un algoritme d’optimització per trobar més eficientment el reflector desitjat. Les fonts de llum estan representades per models near-field, que es comprimeixen amb un error molt petit, fins i tot per fonts de llum amb milions de raigs i objectes a il•luminar molt propers. Llavors proposem un mètode ràpid per obtenir la distribució de la il•luminació d’un reflector i la seva comparació amb la il•luminació desitjada, i que treballa completament en la GPU. Finalment, proposem un nou mètode d’optimització global que permet trobar la solució en menys passos que molts altres mètodes d’optimització clàssics, i alhora evitant mínims locals.

Visibility and proximity on triangulated surfaces

En aquesta tesi es solucionen problemes de visibilitat i proximitat sobre superfícies triangulades considerant elements generalitzats. Com a elements generalitzats considerem: punts, segments, poligonals i polígons. Les estrategies que proposem utilitzen algoritmes de geometria computacional i hardware gràfic. Comencem tractant els problemes de visibilitat sobre models de terrenys triangulats considerant un conjunt d'elements de visió generalitzats. Es presenten dos mètodes per obtenir, de forma aproximada, mapes de multi-visibilitat. Un mapa de multi-visibilitat és la subdivisió del domini del terreny que codifica la visibilitat d'acord amb diferents criteris. El primer mètode, de difícil implementació, utilitza informació de visibilitat exacte per reconstruir de forma aproximada el mapa de multi-visibilitat. El segon, que va acompanyat de resultats d'implementació, obté informació de visibilitat aproximada per calcular i visualitzar mapes de multi-visibilitat discrets mitjançant hardware gràfic. Com a aplicacions es resolen problemes de multi-visibilitat entre regions i es responen preguntes sobre la multi-visibilitat d'un punt o d'una regió. A continuació tractem els problemes de proximitat sobre superfícies polièdriques triangulades considerant seus generalitzades. Es presenten dos mètodes, amb resultats d'implementació, per calcular distàncies des de seus generalitzades sobre superfícies polièdriques on hi poden haver obstacles generalitzats. El primer mètode calcula, de forma exacte, les distàncies definides pels camins més curts des de les seus als punts del poliedre. El segon mètode calcula, de forma aproximada, distàncies considerant els camins més curts sobre superfícies polièdriques amb pesos. Com a aplicacions, es calculen diagrames de Voronoi d'ordre k, i es resolen, de forma aproximada, alguns problemes de localització de serveis. També es proporciona un estudi teòric sobre la complexitat dels diagrames de Voronoi d'ordre k d'un conjunt de seus generalitzades en un poliedre sense pesos.