Multi-objective optimization scheme for static and dynamic multicast flows

Muchas de las nuevas aplicaciones emergentes de Internet tales como TV sobre Internet, Radio sobre Internet,Video Streamming multi-punto, entre otras, necesitan los siguientes requerimientos de recursos: ancho de banda consumido, retardo extremo-a-extremo, tasa de paquetes perdidos, etc. Por lo anterior, es necesario formular una propuesta que especifique y provea para este tipo de aplicaciones los recursos necesarios para su buen funcionamiento. En esta tesis, proponemos un esquema de ingeniería de tráfico multi-objetivo a través del uso de diferentes árboles de distribución para muchos flujos multicast. En este caso, estamos usando la aproximación de múltiples caminos para cada nodo egreso y de esta forma obtener la aproximación de múltiples árboles y a través de esta forma crear diferentes árboles multicast. Sin embargo, nuestra propuesta resuelve la fracción de la división del tráfico a través de múltiples árboles. La propuesta puede ser aplicada en redes MPLS estableciendo rutas explícitas en eventos multicast. En primera instancia, el objetivo es combinar los siguientes objetivos ponderados dentro de una métrica agregada: máxima utilización de los enlaces, cantidad de saltos, el ancho de banda total consumido y el retardo total extremo-a-extremo. Nosotros hemos formulado esta función multi-objetivo (modelo MHDB-S) y los resultados obtenidos muestran que varios objetivos ponderados son reducidos y la máxima utilización de los enlaces es minimizada. El problema es NP-duro, por lo tanto, un algoritmo es propuesto para optimizar los diferentes objetivos. El comportamiento que obtuvimos usando este algoritmo es similar al que obtuvimos con el modelo. Normalmente, durante la transmisión multicast los nodos egresos pueden salir o entrar del árbol y por esta razón en esta tesis proponemos un esquema de ingeniería de tráfico multi-objetivo usando diferentes árboles para grupos multicast dinámicos. (en el cual los nodos egresos pueden cambiar durante el tiempo de vida de la conexión). Si un árbol multicast es recomputado desde el principio, esto podría consumir un tiempo considerable de CPU y además todas las comuicaciones que están usando el árbol multicast serán temporalmente interrumpida. Para aliviar estos inconvenientes, proponemos un modelo de optimización (modelo dinámico MHDB-D) que utilice los árboles multicast previamente computados (modelo estático MHDB-S) adicionando nuevos nodos egreso. Usando el método de la suma ponderada para resolver el modelo analítico, no necesariamente es correcto, porque es posible tener un espacio de solución no convexo y por esta razón algunas soluciones pueden no ser encontradas. Adicionalmente, otros tipos de objetivos fueron encontrados en diferentes trabajos de investigación. Por las razones mencionadas anteriormente, un nuevo modelo llamado GMM es propuesto y para dar solución a este problema un nuevo algoritmo usando Algoritmos Evolutivos Multi-Objetivos es propuesto. Este algoritmo esta inspirado por el algoritmo Strength Pareto Evolutionary Algorithm (SPEA). Para dar una solución al caso dinámico con este modelo generalizado, nosotros hemos propuesto un nuevo modelo dinámico y una solución computacional usando Breadth First Search (BFS) probabilístico. Finalmente, para evaluar nuestro esquema de optimización propuesto, ejecutamos diferentes pruebas y simulaciones. Las principales contribuciones de esta tesis son la taxonomía, los modelos de optimización multi-objetivo para los casos estático y dinámico en transmisiones multicast (MHDB-S y MHDB-D), los algoritmos para dar solución computacional a los modelos. Finalmente, los modelos generalizados también para los casos estático y dinámico (GMM y GMM Dinámico) y las propuestas computacionales para dar slución usando MOEA y BFS probabilístico.

New Methods for Triangulation-based Shape Acquisition using Laser Scanners

Tradicionalment, la reproducció del mon real se'ns ha mostrat a traves d'imatges planes. Aquestes imatges se solien materialitzar mitjançant pintures sobre tela o be amb dibuixos. Avui, per sort, encara podem veure pintures fetes a ma, tot i que la majoria d'imatges s'adquireixen mitjançant càmeres, i es mostren directament a una audiència, com en el cinema, la televisió o exposicions de fotografies, o be son processades per un sistema computeritzat per tal d'obtenir un resultat en particular. Aquests processaments s'apliquen en camps com en el control de qualitat industrial o be en la recerca mes puntera en intel·ligència artificial. Aplicant algorismes de processament de nivell mitja es poden obtenir imatges 3D a partir d'imatges 2D, utilitzant tècniques ben conegudes anomenades Shape From X, on X es el mètode per obtenir la tercera dimensió, i varia en funció de la tècnica que s'utilitza a tal nalitat. Tot i que l'evolució cap a la càmera 3D va començar en els 90, cal que les tècniques per obtenir les formes tridimensionals siguin mes i mes acurades. Les aplicacions dels escàners 3D han augmentat considerablement en els darrers anys, especialment en camps com el lleure, diagnosi/cirurgia assistida, robòtica, etc. Una de les tècniques mes utilitzades per obtenir informació 3D d'una escena, es la triangulació, i mes concretament, la utilització d'escàners laser tridimensionals. Des de la seva aparició formal en publicacions científiques al 1971 [SS71], hi ha hagut contribucions per solucionar problemes inherents com ara la disminució d'oclusions, millora de la precisió, velocitat d'adquisició, descripció de la forma, etc. Tots i cadascun dels mètodes per obtenir punts 3D d'una escena te associat un procés de calibració, i aquest procés juga un paper decisiu en el rendiment d'un dispositiu d'adquisició tridimensional. La nalitat d'aquesta tesi es la d'abordar el problema de l'adquisició de forma 3D, des d'un punt de vista total, reportant un estat de l'art sobre escàners laser basats en triangulació, provant el funcionament i rendiment de diferents sistemes, i fent aportacions per millorar la precisió en la detecció del feix laser, especialment en condicions adverses, i solucionant el problema de la calibració a partir de mètodes geomètrics projectius.

On intentional and social agents with graded attitudes

La principal contribución de esta Tesis es la propuesta de un modelo de agente BDI graduado (g-BDI) que permita especificar una arquitetura de agente capaz de representar y razonar con actitudes mentales graduadas. Consideramos que una arquitectura BDI más exible permitirá desarrollar agentes que alcancen mejor performance en entornos inciertos y dinámicos, al servicio de otros agentes (humanos o no) que puedan tener un conjunto de motivaciones graduadas. En el modelo g-BDI, las actitudes graduadas del agente tienen una representación explícita y adecuada. Los grados en las creencias representan la medida en que el agente cree que una fórmula es verdadera, en los deseos positivos o negativos permiten al agente establecer respectivamente, diferentes niveles de preferencias o de rechazo. Las graduaciones en las intenciones también dan una medida de preferencia pero en este caso, modelan el costo/beneficio que le trae al agente alcanzar una meta. Luego, a partir de la representación e interacción de estas actitudes graduadas, pueden ser modelados agentes que muestren diferentes tipos de comportamiento. La formalización del modelo g-BDI está basada en los sistemas multi-contextos. Diferentes lógicas modales multivaluadas se han propuesto para representar y razonar sobre las creencias, deseos e intenciones, presentando en cada caso una axiomática completa y consistente. Para tratar con la semántica operacional del modelo de agente, primero se definió un calculus para la ejecución de sistemas multi-contextos, denominado Multi-context calculus. Luego, mediante este calculus se le ha dado al modelo g-BDI semántica computacional. Por otra parte, se ha presentado una metodología para la ingeniería de agentes g-BDI en un escenario multiagente. El objeto de esta propuesta es guiar el diseño de sistemas multiagentes, a partir de un problema del mundo real. Por medio del desarrollo de un sistema recomendador en turismo como caso de estudio, donde el agente recomendador tiene una arquitectura g-BDI, se ha mostrado que este modelo es valioso para diseñar e implementar agentes concretos. Finalmente, usando este caso de estudio se ha realizado una experimentación sobre la flexibilidad y performance del modelo de agente g-BDI, demostrando que es útil para desarrollar agentes que manifiesten conductas diversas. También se ha mostrado que los resultados obtenidos con estos agentes recomendadores modelizados con actitudes graduadas, son mejores que aquellos alcanzados por los agentes con actitudes no-graduadas.

Quantified real constraint solving using modal intervals with applications to control

Les restriccions reals quantificades (QRC) formen un formalisme matemàtic utilitzat per modelar un gran nombre de problemes físics dins els quals intervenen sistemes d'equacions no-lineals sobre variables reals, algunes de les quals podent ésser quantificades. Els QRCs apareixen en nombrosos contextos, com l'Enginyeria de Control o la Biologia. La resolució de QRCs és un domini de recerca molt actiu dins el qual es proposen dos enfocaments diferents: l'eliminació simbòlica de quantificadors i els mètodes aproximatius. Tot i això, la resolució de problemes de grans dimensions i del cas general, resten encara problemes oberts. Aquesta tesi proposa una nova metodologia aproximativa basada en l'Anàlisi Intervalar Modal, una teoria matemàtica que permet resoldre problemes en els quals intervenen quantificadors lògics sobre variables reals. Finalment, dues aplicacions a l'Enginyeria de Control són presentades. La primera fa referència al problema de detecció de fallades i la segona consisteix en un controlador per a un vaixell a vela.

Representació qualitativa asíncrona de senyals per a la supervisió de sistemes dinàmics

L'objectiu general d'aquest treball és trobar i mostrar una eina que permeti obtenir una representació dels senyals procedents de sistemes dinàmics adequada a les necessitats dels sistemes de Supervisió Experta de processos. Aquest objectiu general es pot subdividir en diverses parts, que són tractades en els diferents capítols que composen el treball i que es poden resumir en els següents punts: En primer lloc, cal conèixer les necessitats dels sistemes de Supervisió: La gran quantitat de dades que provenen dels processos fa necessari el tractament d'aquestes dades per obtenir-ne d'altres, més elaborades, amb un nivell més elevat de representació. La utilització de raonament qualitatiu, pròpia dels éssers humans, comporta la necessitat de representar simbòlicament els senyals, de traduir les dades numèriques en símbols. La Supervisió de sistemes dinàmics comporta que el temps sigui una variable fonamental, la asincronia dels esdeveniments significatius per a la Supervisió fa que les representacions més adequades i útils dels senyals siguin asíncrones. Finalment,l'ús dels coneixements experimentals en la Supervisió dels processos comporta que les representacions més naturals siguin les més útils. Aquestes necessitats fan de la representació dels senyals mitjançant episodis l'eina amb més possibilitats per assolir els objectius que es volen assolir. Per això, es presenta un formalisme que permet descriure i incloure-hi la formalització i les diferents aproximacions a aquest tipus de representació ja existents i, al mateix temps, augmentar-ne la significació a través de característiques dels senyals que no es tenen en compte en les aproximacions ja existents. El següent pas és aprofitar el nou formalisme per obtenir una nova representació amb un grau més gran de significació, cosa que s'aconsegueix representant explícitament les discontinuïtats i els períodes estacionaris o d'estabilitat, molt significatius en Supervisió de processos. Un problema sempre present en el tractament de senyals és el soroll que els afecta. Per aquest motiu es presenta un mètode que permet filtrar el soroll de manera que les representacions resultants quedin afectades el mínim possible per aquest tractament. Finalment, es presenta l'aplicació en línia de les eines descrites. La representació en línia dels senyals comporta el tractament de la incertesa inherent al coneixement parcial del senyal (un episodi no pot ser determinat i caracteritzat completament fins que no s'acaba). L'obtenció de resultats amb determinats graus de certesa és perfectament coherent amb la seva utilització posterior mitjançant Sistemes Experts o altres eines de la IA. Totes les aportacions del treball vénen acompanyades d'exemples i/o aplicacions que permeten observar-ne la utilitat i les limitacions.

Robust Control of Systems Subjected to Uncertain Disturbances and Actuator Dynamics

Esta tesis está enfocada al diseño y validación de controladores robustos que pueden reducir de una manera efectiva las vibraciones structurales producidas por perturbaciones externas tales como terremotos, fuertes vientos o cargas pesadas. Los controladores están diseñados basados en teorías de control tradicionalamente usadas en esta area: Teoría de estabilidad de Lyapunov, control en modo deslizante y control clipped-optimal, una técnica reciente mente introducida : Control Backstepping y una que no había sido usada antes: Quantitative Feedback Theory. La principal contribución al usar las anteriores técnicas, es la solución de problemas de control estructural abiertos tales como dinámicas de actuador, perturbaciones desconocidas, parametros inciertos y acoplamientos dinámicos. Se utilizan estructuras típicas para validar numéricamente los controladores propuestos. Especificamente las estructuras son un edificio de base aislada, una plataforma estructural puente-camión y un puente de 2 tramos, cuya configuración de control es tal que uno o mas problemas abiertos están presentes. Se utilizan tres prototipos experimentales para implementar los controladores robustos propuestos, con el fin de validar experimentalmente su efectividad y viabilidad. El principal resultado obtenido con la presente tesis es el diseño e implementación de controladores estructurales robustos que resultan efectivos para resolver problemas abiertos en control estructural tales como dinámicas de actuador, parámetros inciertos, acoplamientos dinámicos, limitación de medidas y perturbaciones desconocidas.

Studies of dynamics of physical agent ecosystems

This thesis addresses the problem of learning in physical heterogeneous multi-agent systems (MAS) and the analysis of the benefits of using heterogeneous MAS with respect to homogeneous ones. An algorithm is developed for this task; building on a previous work on stability in distributed systems by Tad Hogg and Bernardo Huberman, and combining two phenomena observed in natural systems, task partition and hierarchical dominance. This algorithm is devised for allowing agents to learn which are the best tasks to perform on the basis of each agent's skills and the contribution to the team global performance. Agents learn by interacting with the environment and other teammates, and get rewards from the result of the actions they perform. This algorithm is specially designed for problems where all robots have to co-operate and work simultaneously towards the same goal. One example of such a problem is role distribution in a team of heterogeneous robots that form a soccer team, where all members take decisions and co-operate simultaneously. Soccer offers the possibility of conducting research in MAS, where co-operation plays a very important role in a dynamical and changing environment. For these reasons and the experience of the University of Girona in this domain, soccer has been selected as the test-bed for this research. In the case of soccer, tasks are grouped by means of roles. One of the most interesting features of this algorithm is that it endows MAS with a high adaptability to changes in the environment. It allows the team to perform their tasks, while adapting to the environment. This is studied in several cases, for changes in the environment and in the robot's body. Other features are also analysed, especially a parameter that defines the fitness (biological concept) of each agent in the system, which contributes to performance and team adaptability. The algorithm is applied later to allow agents to learn in teams of homogeneous and heterogeneous robots which roles they have to select, in order to maximise team performance. The teams are compared and the performance is evaluated in the games against three hand-coded teams and against the different homogeneous and heterogeneous teams built in this thesis. This section focuses on the analysis of performance and task partition, in order to study the benefits of heterogeneity in physical MAS. In order to study heterogeneity from a rigorous point of view, a diversity measure is developed building on the hierarchic social entropy defined by Tucker Balch. This is adapted to quantify physical diversity in robot teams. This tool presents very interesting features, as it can be used in the future to design heterogeneous teams on the basis of the knowledge on other teams.

Texture recognition under varying imaging geometries

La visió és probablement el nostre sentit més dominant a partir del qual derivem la majoria d'informació del món que ens envolta. A través de la visió podem percebre com són les coses, on són i com es mouen. En les imatges que percebem amb el nostre sistema de visió podem extreure'n característiques com el color, la textura i la forma, i gràcies a aquesta informació som capaços de reconèixer objectes fins i tot quan s'observen sota unes condicions totalment diferents. Per exemple, som capaços de distingir un mateix objecte si l'observem des de diferents punts de vista, distància, condicions d'il·luminació, etc. La Visió per Computador intenta emular el sistema de visió humà mitjançant un sistema de captura d'imatges, un ordinador, i un conjunt de programes. L'objectiu desitjat no és altre que desenvolupar un sistema que pugui entendre una imatge d'una manera similar com ho realitzaria una persona. Aquesta tesi es centra en l'anàlisi de la textura per tal de realitzar el reconeixement de superfícies. La motivació principal és resoldre el problema de la classificació de superfícies texturades quan han estat capturades sota diferents condicions, com ara distància de la càmera o direcció de la il·luminació. D'aquesta forma s'aconsegueix reduir els errors de classificació provocats per aquests canvis en les condicions de captura. En aquest treball es presenta detalladament un sistema de reconeixement de textures que ens permet classificar imatges de diferents superfícies capturades en diferents condicions. El sistema proposat es basa en un model 3D de la superfície (que inclou informació de color i forma) obtingut mitjançant la tècnica coneguda com a 4-Source Colour Photometric Stereo (CPS). Aquesta informació és utilitzada posteriorment per un mètode de predicció de textures amb l'objectiu de generar noves imatges 2D de les textures sota unes noves condicions. Aquestes imatges virtuals que es generen seran la base del nostre sistema de reconeixement, ja que seran utilitzades com a models de referència per al nostre classificador de textures. El sistema de reconeixement proposat combina les Matrius de Co-ocurrència per a l'extracció de característiques de textura, amb la utilització del Classificador del veí més proper. Aquest classificador ens permet al mateix temps aproximar la direcció d'il·luminació present en les imatges que s'utilitzen per testejar el sistema de reconeixement. És a dir, serem capaços de predir l'angle d'il·luminació sota el qual han estat capturades les imatges de test. Els resultats obtinguts en els diferents experiments que s'han realitzat demostren la viabilitat del sistema de predicció de textures, així com del sistema de reconeixement.

Time misalignments in fault detection and diagnosis

El desalineamiento temporal es la incorrespondencia de dos señales debido a una distorsión en el eje temporal. La Detección y Diagnóstico de Fallas (Fault Detection and Diagnosis-FDD) permite la detección, el diagnóstico y la corrección de fallos en un proceso. La metodología usada en FDD está dividida en dos categorías: técnicas basadas en modelos y no basadas en modelos. Esta tesis doctoral trata sobre el estudio del efecto del desalineamiento temporal en FDD. Nuestra atención se enfoca en el análisis y el diseño de sistemas FDD en caso de problemas de comunicación de datos, como retardos y pérdidas. Se proponen dos técnicas para reducir estos problemas: una basada en programación dinámica y la otra en optimización. Los métodos propuestos han sido validados sobre diferentes sistemas dinámicos: control de posición de un motor de corriente continua, una planta de laboratorio y un problema de sistemas eléctricos conocido como hueco de tensión.

VLSI architecture for motion estimation in underwater imaging

El treball desenvolupat en aquesta tesi aprofundeix i aporta solucions innovadores en el camp orientat a tractar el problema de la correspondència en imatges subaquàtiques. En aquests entorns, el que realment complica les tasques de processat és la falta de contorns ben definits per culpa d'imatges esborronades; un fet aquest que es deu fonamentalment a il·luminació deficient o a la manca d'uniformitat dels sistemes d'il·luminació artificials. Els objectius aconseguits en aquesta tesi es poden remarcar en dues grans direccions. Per millorar l'algorisme d'estimació de moviment es va proposar un nou mètode que introdueix paràmetres de textura per rebutjar falses correspondències entre parells d'imatges. Un seguit d'assaigs efectuats en imatges submarines reals han estat portats a terme per seleccionar les estratègies més adients. Amb la finalitat d'aconseguir resultats en temps real, es proposa una innovadora arquitectura VLSI per la implementació d'algunes parts de l'algorisme d'estimació de moviment amb alt cost computacional.

O peixe de Babel

Descrevem-se alguns testes simples de tradução e retroversão a que submetemos um programa de tradução automática disponível online. As soluções obtidas permitem analisar e estimar a sua fiabilidade. Conclui-se que o referido programa tem um desempenho sofrível, não sendo aconselhável a sua utilização como auxiliar no processo de tradução ou retroversão de textos.

O mito de Francesca da Rimini em Portugal (sécs. XIX-XX) : a tradução como testemunho da evolução do cânone - efeitos estranhantes da domesticação e efeitos aculturantes do estranhamento

A receção portuguesa da Divina Comédia de Dante Alighieri entre os séculos XIX e XX pode ser considerada um exemplo da ideia segundo a qual as traduções são testemunhos da mudança dos cânones estéticos-literários que involve o microssistema cultural. Através da análise de algumas soluções tradutórias do tema do v Canto do Inferno, não só mostrar-se-á este princípio de influência, como também a natureza híbrida das traduções, que leva a uma parcial reformulação dos processos de primarização e secundarização propostos pela teoria polissistémica de Itamar Even-Zohar.

Tecnologia de iplex massarray aplicado ao diagnóstico de miocardiopatia hipertrófica

A miocardiopatia hipertrófica (MH) é a doença cardíaca genética mais comum, afectando 1:500 indivíduos, apresentando um padrão de transmissão autossómico dominante, com mutações associadas a genes sarcoméricos e não sarcoméricos. A MH apresenta uma variedade de manifestações clínicas, desde indivíduosassintomáticos a indivíduos que manifestam uma progressão da severidade dos sintomas, podendo nalguns casos ocorrer morte súbita. O diagnóstico clínico é realizado por Electrocardiograma e Ecocardiograma. O diagnóstico genético baseia-se na Sequenciação Automática (SA) dos 5 principais genes sarcoméricos MYBPC3, MYH7, TNNT2, TNNI3 e MYL2, sendo considerada uma metodologia bastante dispendiosa e demorada e que não permite a identificação de mutações em cerca de 1/3 dos individuos. A Genotipagem por iPLEX MassARRAY revela-se uma boa alternativa à SA no diagnóstico genético de MH, uma vez que permite a análise de várias amostras em simultâneo, para um elevado número de mutações, num único ensaio, com uma maior rentabilidade de tempo e recursos. Este trabalho teve como objectivo a optimização e a validação desta metodologia, na detecção de 541 mutações em 33 genes, tendo-se verificado que 29 % das reacções multiplex necessitam de ser revistas, quer pelo desenho de novos conjuntos de primers, quer pela sua relocalização no chip.

O culto a Serápis e a coexistência helénico-egípcia na Alexandria ptolomaica

O estabelecimento do culto ao deus Serápis na antiga cidade cosmopolita de Alexandria, capital dos Ptolomeus, em torno de uma imagem única e híbrida, respondeu à necessidade de harmonização intercultural dos dois mais importantes agrupamentos populacionais de Alexandria (os autóctones egípcios e os imigrantes greco-macedónios) e constituiu um factor de superação de anteriores e antigas antíteses e diferenças que os opunham, desenvolvidas com a ocupação grega do Egipto, e que eram,na viragem do séc. IV a.C., um dos maiores problemas e desafios colocados ao novo poder político, geneticamente oriundo da Macedónia, mas residente no Egipto.

El método de reducción en Teoría de la Computabilidad

La Teoría de la Computabilidad es una disciplina encuadrada en la Informática Teórica que tiene como objetivo establecer los límites lógicos que presentan los sistemas informáticos a la hora de resolver problemas mediante el diseño de algoritmos. Estos resultados proporcionan importantes herramientas que se utilizan para demostrar tanto la computabilidad como la incomputabilidad de muchas funciones relevantes. Los primeros problemas incomputables que se encontraron lo fueron allá por la década de los años 30. El problema de parada es el primer y más conocido ejemplo de problema no resoluble mediante técnicas algorítmicas: ningún ordenador, por muy potente que sea, puede anticipar el comportamiento de los programas en ejecución, y decidir de antemano si terminarán o no. Este problema nos proporciona un soporte intuitivo para anticipar la incomputabilidad de otros problemas relacionados y un procedimiento para resolverlos: el método de diagonalización. Sin embargo para determinados problemas también incomputables hay que recurrir a otros métodos. Este texto incluye una descripción de otra técnica básica de Teoría de la Computabilidad: la Reducción. La base del método estriba en demostrar que ciertos pares de problemas están fuertemente relacionados de modo que si el segundo tiene solución algorítmica entonces el primero debe tenerla necesariamente también. Esta relación se establece por medio de funciones transformadoras computables, que permiten convertir de manera automática las instancias positivas del primer problema en instancias positivas del segundo. Esta técnica se utiliza muy a menudo porque resulta comparativamente más sencilla que la diagonalización, ya que en general requiere menos esfuerzo para demostrar la incomputabilidad de un mismo problema.