Los Problemas de Optimización con Restricciones Distribuidos (DCOP) son utilizados para modelar problemas de coordinación multi-agente. Los DCOPs se definen con un número finito de agentes, variables y funciones de coste. El objetivo es encontrar una asignación de todas las variables cuyo coste global sea mínimo. Para lograrlo, los agentes que manejan las variables han de intercambiar información sobre el coste de sus asignaciones hasta encontrar la solución óptima. Varios algoritmos distribuidos se han propuesto para encontrar soluciones óptimas en DCOPs. En el caso centralizado, se han desarrollado técnicas para acelerar la resolución de problemas de optimización con restricciones. En particular, técnicas de arco consistencia blanda, como AC, FDAC y EDAC, las cuales identifican valores inconsistentes que pueden ser eliminados. El objetivo de esta tesis es incluir técnicas de arco consistencia blanda en la resolución de DCOPs. Esta combinación obtiene mejoras sustanciales en el rendimiento. Las arco consistencias blandas son conceptualmente iguales en el caso centralizado y distribuido. Sin embargo, mantenerlas en el caso distribuido requiere un enfoque diferente. En centralizado, todos los elementos del problema están disponibles para el único agente que realiza la búsqueda, mientras que en el caso distribuido los agentes solo conocen algunas partes del problema y deben intercambiar información para lograr el nivel de consistencia deseado. En este proceso, las estructuras del problema se deben modificar de tal manera que la información parcial del problema global permanezca coherente en cada agente. En esta tesis presentamos tres contribuciones para la resolución de DCOPs. En primer lugar, hemos estudiado el algoritmo de búsqueda BnB-ADOPT y hemos podido mejorarlo de manera significativa. Probamos que algunos de los mensajes enviados por BnB-ADOPT son redundantes y pueden ser eliminados sin afectar la optimalidad y completitud del algoritmo. Además, cuando se trabaja con restricciones de aridad mayor que dos, algunos problemas aparecen en este algoritmo. Proponemos una forma simple de solucionarlos obteniendo una nueva versión para el caso n-ario. También, presentamos el nuevo algoritmo ADOPT(k), el cual generaliza los algoritmos ADOPT y BnB-ADOPT. ADOPT(k) realiza una estrategia de búsqueda similar a ADOPT, a BnB-ADOPT, o a un híbrido de ambos dependiendo del parámetro k. En segundo lugar, introducimos técnicas de arco consistencia blanda en DCOPs, utilizando BnB-ADOPT+ como algoritmo de resolución. Durante la búsqueda mantenemos los niveles de consistencia AC y FDAC, con la limitación que solo se propagan borrados incondicionales, logrando importantes beneficios en la comunicación y en esfuerzo de cómputo. Mantenemos FDAC en varios órdenes de las variables obteniendo reducciones en la comunicación. Además, proponemos DAC por propagación de token, una nueva forma de propagar borrados durante la búsqueda distribuida. Experimentalmente, esta estrategia ha demostrado ser competitiva comparada con FDAC. En tercer lugar, exploramos la inclusión de restricciones globales blandas en DCOPs. Pensamos que las restricciones globales mejoran la expresividad de DCOP. Proponemos tres formas de incluir restricciones globales blandas en DCOP y extendemos el algoritmo BnB-ADOPT+ para incorporarlas. Además, exploramos el impacto de mantener arco consistencia en problemas con restricciones globales blandas. Experimentalmente, medimos la eficiencia de los algoritmos propuestos en varios conjuntos de datos comúnmente usados en la comunidad de DCOP. / Distributed Constraint Optimization Problems (DCOPs) can be used for modeling many multi-agent coordination problems. DCOPs involve a finite number of agents, variables and cost functions. The goal is to find a complete variable assignment with minimum global cost. This is achieved among several agents handling the variables and exchanging information about their cost evaluation until an optimal solution is found. Recently, researchers have proposed several distributed algorithms to optimally solve DCOPs. In the centralized case, techniques have been developed to speed up constraint optimization solving. In particular, search can be improved by enforcing soft arc consistency, which identifies inconsistent values that can be removed from the problem. Some soft consistency levels proposed are AC, FDAC and EDAC. The goal of this thesis is to include soft arc consistency techniques in DCOP resolution. We show that this combination causes substantial improvements in performance. Soft arc consistencies are conceptually equal in the centralized and distributed cases. However, maintaining soft arc consistencies in the distributed case requires a different approach. While in the centralize case all problem elements are available in the single agent performing the search, in the distributed case agents only knows some part of the problem and they must exchange information to achieve the desired consistency level. In this process, the operations that modify the problem structures should be done in such a way that partial information of the global problem remains coherent on every agent. In this thesis we present three main contributions to optimal DCOP solving. First, we have studied and experimented with the complete solving algorithm BnB-ADOPT. As result of this work, we have improved it to a large extent. We show that some of BnB-ADOPT messages are redundant and can be removed without compromising optimality and termination. Also, when dealing with cost functions of arity higher than two, some issues appear in this algorithm. We propose a simple way to overcome them obtaining a new version for the n-ary case. In addition, we present the new algorithm ADOPT($k$), which generalizes the algoritms ADOPT and BnB-ADOPT. ADOPT ($k$) can perform a search strategy either like ADOPT, like BnB-ADOPT or like a hybrid of both depending on the $k$ parameter. Second, we have introduced soft arc consistency techniques in DCOPs, taking BnB-ADOPT$^+$ as our base solving algorithm. During the search process, we enforce the soft arc consistency levels AC and FDAC, under the limitation that only unconditional deletions are propagated, obtaining important benefits in communication and computation. We enforce FDAC considering multiple orderings of the variables obtaining savings in communication. Also, we propose DAC by token passing, a new way to propagate deletions during distributed search. Experimentally, this strategy turned out to be competitive when compared to FDAC. Third, we explore the inclusion of soft global constraints in DCOPs. We believe that soft global constraints enhance DCOP expressivity. We propose three different ways to include soft global constraints in DCOPs and extend the solving algorithm BnB-ADOPT$^+$ to support them. In addition, we explore the impact of soft arc consistency maintenance in problems with soft global constrains. Experimentally, we measure the efficiency of the proposed algorithms in several benchmarks commonly used in the DCOP community.

L'aparició de bases de dades amb un gran nombre d'imatges requereix del desenvolupament de representacions d'imatge eficients i algorismes que siguin capaços de manipular dades a gran escala de manera eficient. Avui dia, la representació d'imatges basada en la tècnica de Bagsof-Words (Bow), és l'enfocament que més ha reeixit en el context de les tasques de classificació d'objectes i d'escenes. No obstant això, el seu principal desavantatge és l'absència d'informació espacial. En aquest context, els de pirmides espacials (SP) s'ha aplicat amb èxit per incorporar la informació espacial: bàsicament es tracta de subdividir la imatge recursivament subregions al duplicar el nombre de divisions en cada direcció de la imatge, permetent l'extracció d'histogrames i altres caracterstiques en aquestes subregions. A partir del notable rendiment que s'obté amb les piràmides espacials, el seu ús s'ha generalitzat en un creixent nombre d'aplicacions i problemes de visió, pel que en aquesta Tesi hem analitzat com millorar-ne el seu ús. Dins el marc de les SP, hem estudiat la forma òptima per obtenir una representació de la imatge que sigui capaç de fer front als defectes més destacats de les SP, en concret, la seva alta dimensionalitat i la seva rigidesa de la representació de la imatge resultant. En resum, la preocupació principal d'aquesta Tesi és la recerca dels límits de les piràmides espacials al tractar de trobar solucions per als seus inconvenients. En general, aquesta Tesi explora el problema d'obtenir representacions molt compactes i adaptades a la naturalesa de la imatge que siguin molt més informatives en el context de la classificació d'objectes i escenes. / La aparición de bases de datos con un gran número de imágenes requiere del desarrollo de representaciones de imagen eficientes y algoritmos que sean capaces de manipular datos a gran escala de manera eficiente. Hoy en día, la representación de imágenes basada en la técnica de Bags-of-Words (BoW), es el enfoque más exitoso en el contexto de las tareas de clasificación de objetos y de escena. Sin embargo, su principal desventaja es la ausencia de información espacial. En este contexto, el uso de pirámides espaciales (SP) se ha aplicado con éxito para incorporar la información espacial: básicamente se trata de subdividir la imagen recursivamente subregiones al duplicar el número de divisiones en cada dirección del eje, permitiendo la extracción de histogramas y otras características en estas subregiones. A partir del notable rendimiento que se obtiene con las pirámides espaciales, su uso se ha generalizado en un creciente número de aplicaciones y problemas de visión, por lo que en esta Tesis hemos analizado cómo mejorar su uso. Dentro del marco de las SP, hemos estudiado la forma óptima para obtener una representación de la imagen que sea capaz de hacer frente a los defectos más destacados de las SP, en concreto, su alta dimensionalidad y su rigidez de la representación de la imagen resultante. En resumen, la preocupación principal de esta Tesis es la búsqueda de los límites de las pirámides y tratar de encontrar soluciones para sus inconvenientes. En general, esta Tesis explora el problema de obtener representaciones muy compactas, representaciones espaciales de adaptación que sean más informativas de la imagen en el contexto de la clasificaciónn de objetos y escenas. / Abstract The release of challenging datasets with a vast number of images, re- quires the development of efficient image representations and algorithms which are able to manipulate these largescale datasets efficiently. Nowadays the Bag- of-Words (BoW) based image representation is the most successful approach in the context of object and scene classification tasks. However, its main drawback is the absence of the important spatial information. Spatial pyramids (SP) have been successfully applied to incorporate spatial information into BoW-based im- age representation. The main SP approach, works by repeatedly sub-dividing the image into increasingly finer sub-regions by doubling the number of di- visions on each axis direction, and further computing histograms of features over the resulting sub-regions. Observing the remarkable performance of spa- tial pyramids, their growing number of applications to a broad range of vision problems, and finally its geometry inclusion, a question can be asked what are the limits of spatial pyramids. Within the SP framework, the optimal way for obtaining an image spatial representation which is able to cope with its most foremost shortcomings, concretely, its high dimensionality and the rigidity of the resulting image representation still remains an active research domain. In summary, the main concern of this thesis is to search for the limits of spatial pyramids and try to figure out solutions for them. This thesis explores the problem of obtaining compact, adaptive, yet informative spatial image repre- sentations in the context of object and scene classification tasks. In the first part of this thesis, we first analyze the implications of directly applying the state-of-the-art compression techniques for obtaining compact BoW-based im- age representation within the context of spatial pyramids. We then introduce a novel SP compression technique that works on two levels; (i) compressing the least informative spatial pyramid features, followed by, (ii) compressing the least informative SP regions for the purpose of obtaining compact, and adaptable SP. We then introduce a new texture descriptor that represents local image texture and its spatial layout. Texture is represented as a compact vector descriptor suitable for use in standard learning algorithms with kernels. Experimental re- sults show that texture information has similar classification performances and sometimes outperforms those methods using only shape or appearance informa- tion. The resulting spatial pyramid representation demonstrates significantly improved performance on challenging scene classification tasks. In the second part of this thesis, we present a novel technique for building adaptive spatial pyramids. In particular, we investigate various approaches for learning adap- tive spatial pyramids, which are specially tailored for the task at hand. To this end, we analyze the use of (i) standard generic 3D scene geometries; the geometry of a scene is measured based on image statistics taken from a sin- gle image. (ii) discriminative spatial partitionings, which are generated based on an information-theoretic approach. The proposed method is tested on sev- eral challenging benchmark object classification datasets. The results clearly demonstrated the effectiveness of using adaptive spatial representations, which are steered by the 3D scene geometry present in images. In the third part of 1 this thesis, we investigate the problem of obtaining compact spatial pyramid im- age representations for object and scene classification tasks. We present a novel framework for obtaining compact spatial pyramid image representation up to an order of magnitude without any significant reduction in accuracy. Moreover, we also investigate the optimal combination of multiple features such as color and shape within the context of our novel compact pyramid representation. Finally, we investigate the importance of using the spatial knowledge within the context of color constancy as an application. To this end, we present a novel framework for estimating the image illuminant based on spatial 3D geometry for learning the most appropriate color constancy algorithm to use for every image region. The final image illuminant is obtained based on a weighted combination of each individual illuminant-estimate obtained per region. We test and compare our performance to that of previous state-of-art methods. We will show that the set of innovations introduced here lead to a significant increase on performance on challenging color constancy datasets.

La comprensio automatica de les accions humanes observades en sequencies d'imatges es molt important en el area de recerca de la Vision per Computador, amb aplicacions a gran escala en la vigilancia de video, analisi del moviment huma, interficies de realitat virtual, robots de navegacio, aixi com per al reconeixement, indexacio, i recuperacio de video. Aquesta tesi presenta una serie de tecniques per resoldre el problema del reconeixement de les accions humanes en video. El nostre primer enfocament cap a aquesta tema es basa en la optimitzacio d'un model probabilistic de les parts del cos utilitzant una Hidden Markov Model (HMM). Aquest enfocament es basa en un strong model, capac de distingir entre accions similars considerant nomes les parts del cos que tenen les majors aportacions en la realitzacio de certes accions, per exemple en cames per caminar i correr, o en bracos per a accions com boxa i aplaudir. El nostre seguent enfocament es basa en l'observacio de que el reconeixement d'accions es pot realitzar usant nomes informacio visual, ii la postura humana desenvolupada durant una accio, analitzant la la informacio d'uns quants frames en lloc d'examinar la sequencia completa. En aquest metode, les accions es representen mitjançant un model Bag-of-key-poses per poder capturar la variacio de la postura humana durant el desenvolupament d'una accio. Per fer front al problema del reconeixement de l'accio en escenes complexes, tot seguit es proposa una aproximacio model free basada en l'analisi de punts d'interes espai-temporals (STIPs) que disposen de molta informacio local. Amb aquesta finalitat, s'ha desenvolupat un nou detector de STIPs que es basa en el mecanisme de inhibicio del camp receptiu utilitzat en l'escorça primaria, en particular en l'orientacio selectiva visual de les neurones. A mes, hem estes el nostre reconeixement d'accions basat en STIPs selectius a sistemes multi-camera. En aquest cas, els STIPs selectius de cada punt de vista es combinen mitjançant les dades 3D reconstruïts per formar STIPs selectius 4D (espai 3D + temps). A la part final d'aquesta tesi, ens dediquem al reconeixement continu d'esdeveniments visuals (CVER) en bases de dades de videos de seguretat enormes, amb un gran conjunt de dades. Aquest problema es extremadament difícil a causa de l'alta escalabilitat de les dades, a les dificultats de l'entorn real en que es aplcia ja una variabilitat en escena molt ampli. Per abordar aquests problemes, les regions en moviment son detectades a partir d'una tecnica anomenada max margin generalized Hough transformation, que s'utilitza per aprendre aquella distribucio de característiques voltant d'una accio per reconeixer hipotesis que despres es verifiquen per Bag-of-words mes un classificador lineal. Hem validat les nostres tecniques en diversos conjunts de dades de vídeo vigilància que constitueixen l'estat de l'art actual en aquest tema. Els resultats obtinguts demostren que hem millorat la precisio en la deteccio d'accions humanes en video. / La comprension automatica de las acciones humanas observadas en secuencias de imagenes es muy importante en el area de investigacion de la Vision por Computador, con aplicaciones a gran escala en la vigilancia de video, analisis del movimiento humano, interfaces de realidad virtual, robots de navegacion, asi como para el reconocimiento, indexacion, y recuperacion de video. Esta tesis presenta una serie de tecnicas para resolver el problema del reconocimiento de las acciones humanas en video. Nuestro primer enfoque hacia esta tema se basa en la optimizacion de un modelo probabilístico de las partes del cuerpo utilizando una Hidden Markov Model (HMM). Este enfoque se basa en un strong model, capaz de distinguir entre acciones similares considerando solo las partes del cuerpo que tienen las mayores aportaciones en la realizacion de ciertas acciones, por ejemplo en piernas para caminar y correr, o en brazos para acciones como boxeo y aplaudir. Nuestro siguiente enfoque se basa en la observacion de que el reconocimiento de acciones se puede realizar usando solo informacion visual, i.e. la postura humana desarrollada durante una accion, analizando la la informacion de unos cuantos frames en lugar de examinar la secuencia completa. En este metodo, las acciones se representan mediante un modelo Bag-of-\textit{key-poses} para poder capturar la variaci\'n de la postura humana durante el desarrollo de una accion. Para hacer frente al problema del reconocimiento de la accion en escenas complejas, a continuacion se propone una aproximacion model free basada en el analisis de puntos de interes espacio-temporales (STIPs) que disponen de mucha informacion local. Para este fin, se ha desarrollado un nuevo detector de STIPs que se basa en el mecanismo de inhibici\'{o}n del campo receptivo utilizado en la corteza primaria, en particular en la orientacion selectiva visual de las neuronas. Ademas, hemos extendido nuestro reconocimiento de acciones basado en STIPs selectivos a sistemas multi-camara. En este caso, los STIPs selectivos de cada punto de vista se combinan mediante los datos $3$D reconstruidos para formar STIPs selectivos 4D (espacio 3D + tiempo). En la parte final de esta tesis, nos dedicamos al reconocimiento continuo de eventos visuales (CVER) en bases de datos de videos de seguridad enormes, con un gran conjunto de datos. Este problema es extremadamente dificil debido a la alta escalabilidad de los datos, a las dificultades del entorno real en el que se aplcia y a una variabilidad en escena muy amplio. Para abordar estos problemas, las regiones en movimiento son detectadas a partir de una tecnica llamada max margin generalized Hough transformation, que se utiliza para aprender aquella distribucion de caracteristicas entorno a una accion para reconocer hipotesis que luego se verifican por Bag-of-words mas un clasificador lineal. Hemos validado nuestras tecnicas en varios conjuntos de datos de video vigilancia que constituyen el estado del arte actual en este tema. Los resultados obtenidos demuestran que hemos mejorado la precision en la deteccion de acciones humanas en video. / Automatic understanding of human activity and action is a very important and challenging research area of Computer Vision with wide scale applications in video surveillance, motion analysis, virtual reality interfaces, robot navigation and recognition, video indexing, content based video retrieval, HCI, health care, choreography and sports video analysis etc. This thesis presents a series of techniques to solve the problem of human action recognition in video. First approach towards this goal is based on the a probabilistic optimization model of body parts using hidden markov model (HMM). This strong model based approach is able to distinguish between similar actions by only considering the body parts having major contributions to the actions, for example legs for walking and jogging; arms for boxing and clapping. Next approach is based on the observation that the action recognition can be done using only the visual cue, i.e. human pose during the action, even with the information of few frames instead of examining the whole sequence. In this method, actions are represented by a Bag-of-key-poses model to capture the human pose variation during an action. To tackle the problem of recognizing the action in complex scenes, we propose a model free approach which is based on the Spatio-temporal interest point (STIP) and local feature. To this end, a novel STIP detector is proposed which uses a mechanism similar to that of the non-classical receptive field inhibition that is exhibited by most orientation selective neurons in the primary visual cortex. An extension of the selective STIP based action recognition is applied to the human action recognition in multi-camera system. In this case, selective STIPs from each camera view point are combined using the 3D reconstructed data, to form 4D STIPs [3D space + time] for multi-view action recognition. The concluding part of the thesis dedicates to the continuous visual event recognition (CVER) on large scale video dataset. This is an extremely challenging problem due to high scalability, diverse real environment state and wide scene variability. To address these issues, a motion region extraction technique is applied as a preprocessing step. A max-margin generalized Hough Transform framework is used to learn the feature vote distribution around the activity center to obtain an activity hypothesis which is verified by a Bag-of-words + SVM action recognition system. We validate our proposed approaches on several benchmark action recognition datasets as well as small scale and large scale activity recognition datasets. We obtain state-of-the results which shows a progressive improvement of our proposed techniques to solve human action and activity recognition in video.

Esta tesis aboga por el uso de los mundos virtuales como una tecnología de futuro en el dominio de los mundos virtuales serios, en particular en aplicaciones e-­‐* (e-­‐learning, e-­‐commerce, e-­‐ government) y en simulaciones sociales. En estas aplicaciones, el entorno virtual 3D está poblado por un gran número de habitantes que pueden ser humanos o avatares controlados por agentes virtuales inteligentes que se involucran en interacciones complejas con su entorno y con los demás participantes. Un problema importante que impide la adopción generalizada de la tecnología de mundos virtuales en estos dominios es que, en general, los mundos virtuales son difíciles de construir y se tiene que emplear un gran esfuerzo en el diseño del entorno virtual 3D y en la programación de los agentes virtuales; pero es aún más difícil asegurar la validez de las interacciones de forma que se prevengan comportamientos no permitidos. Para abordar este problema, hemos desarrollado una solución integral que automatiza el diseño de estos mundos virtuales y de su población. Nuestro enfoque se basa en la utilización de las instituciones virtuales, que son mundos virtuales que regulan las interacciones de sus participantes. El enfoque principal de esta tesis está en explicar cómo los métodos existentes de especificación formal de las instituciones virtuales se pueden extender para traducir automáticamente la especificación institucional en un entorno interactivo 3D utilizando el enfoque de las gramáticas de formas (Shape Grammars) y para poblar, de forma también automática, este tipo de entornos con agentes virtuales. Las gramáticas de formas son una técnica visual potente para la generación de diseños 2D y 3D, pero el trabajo realizado hasta el momento en esta área no se adecua a las características de nuestro problema. Por lo tanto, en esta tesis hemos extendido los trabajos realizados en este campo y hemos desarrollado el framework “Shape Grammar Interpreter”, que se ocupa de las limitaciones de las soluciones existentes. Hemos utilizado este framework para el desarrollo del concepto de Virtual World Grammar, que es un subconjunto de las gramáticas de formas dirigido a la generación automática de mundos virtuales normativos. Como resultado de esta tesis, la Virtual World Grammar ha sido formalizada e implementada en un entorno de desarrollo que no sólo permite la generación automática de mundos virtuales normativos, sino también su implementación independiente de la plataforma (utilizando VIXEE, la infraestructura que se ha desarrollado como una parte importante de esta tesis). Otra contribución de esta tesis es el desarrollo de un mecanismo de generación automática de un gran número de agentes de software. Estos agentes son capaces de realizar interacciones inteligentes con objetos 3D dentro del entorno. Además, estos agentes son capaces de colaborar con avatares controlados por humanos, facilitar la resolución de sus problemas y asegurar que todas sus acciones se adhieren de forma estricta a las normas sociales de la institución. Para ello, hemos desarrollado un modelo general de agente virtual que permite situar a un agente en un mundo virtual normativo, generar sus propios objetivos en función de sus necesidades fisiológicas y psicológicas, así como generar dinámicamente los planes para satisfacer estos objetivos mediante la especificación institucional subyacente. Para ilustrar la utilidad de los métodos y técnicas desarrolladas en esta tesis, hemos aplicado éstas al campo de la simulación histórica, recreando la vida de la ciudad de Uruk. Hemos mostrado cómo nuestro enfoque permite crear un gran número de agentes diversos tanto en aspectos visuales como de comportamiento, así como la generación dinámica de los alimentos, herramientas y otros elementos que se utilizan para satisfacer sus objetivos, mientras actúan de forma correcta, históricamente hablando. / This thesis advocates the use of non-­‐gaming virtual worlds as a significant future technology for the domain of ``serious games’’ and in particular e-­‐* applications (e-­‐ learning, e-­‐commerce, e-­‐government) and social simulations. In such systems, a 3D virtual environment is populated by a large number of inhabitants that can be either human-­‐ controlled avatars or intelligent virtual agents who engage in complex interactions with their virtual environment and other participants. One significant problem that impedes wide adoption of the virtual worlds technology for these problem domains is that virtual worlds in general are difficult to build, and significant effort has to be put into designing the 3D virtual environment and programming virtual agents; but it is even harder to ensure the validity of participant so that unauthorized behavior can be prevented. To address this problem, we have developed a comprehensive technological solution that automates the design of such virtual worlds and its population with virtual agents. Our approach is based on the utilization of virtual institutions, which are virtual worlds with normative regulation of participant interactions. The key focus of the thesis is on explaining how existing methods of formal specification of virtual institutions can be extended to automatically translate the institutional specification into an interactive 3D environment using the shape grammars approach and automatically populating such environments with virtual agents. Shape grammars represent a powerful visual technique for creating procedural 2D and 3D designs, but existing work was not immediately suitable for our problem. Thus, we have extended existing work and developed the Shape Grammar Interpreter framework, which addresses the limitations of existing solutions. This framework was further utilized for developing the concept of Virtual World Grammar, which is a sub-­‐set of shape grammars targeting automatic generation of normative virtual worlds. As the result of this dissertation, Virtual Worlds Grammars constitute a strong formalization and a development environment not only enabling automatic generation of normative virtual worlds, but also their platform independent deployment (using the VIXEE infrastructure that has been developed as an important part of this dissertation). Another significant contribution of this thesis is developing a mechanism of automatic population of the generated environments with large numbers of software agents, which are capable of intelligent interactions with 3D objects placed in the environment. Moreover, these agents are able to collaborate with human-­‐controlled avatars, facilitate their problem-­‐solving and ensure that all their actions strictly adhere to social norms of the given institution. For this purpose, we have developed a general-­‐purpose virtual agent model that enables an agent to be situated within any normative virtual world, generate its own goals based on its current physiological and psychological needs, as well as to dynamically generate plans for satisfying these goals using the underlying institutional specification. To illustrate the usefulness of the developed technology, we have applied it to the domain of historical simulation, where we show how virtual world grammars and automatically generated virtual agents can be used for re-­‐enacting everyday life of ancient people in one of humanity's first cities, the city of Uruk. We showed how our approach allows to create a large number of visually and behaviorally diverse agents, as well as dynamically generating food, tools and other items that they can utilize to satisfy their goals, while acting in a historically correct way.

Contribution to the study of alliances in graphs.ResumenEn este trabajo se estudian propiedades matemáticas de las alianzas (defensivas, ofensivas y duales) en grafos. Entre los temas tratados se destacan los siguientes:· Se estudian las alianzas en grafos producto. Específicamente, se obtienen relaciones entre las alianzas en grafos producto Cartesiano y las alianzas en los factores. · Se estudia las particiones de un grafo en alianzas. En particular, se hacen estimaciones del número máximo de conjuntos pertenecientes a una partición del grafo en k-alianzas. Además, se estudian las relaciones existentes entre dicho número y otros invariantes del grafo, tales como el orden, la medida, el número cromático, el número isoperimétrico y la medida de bipartición. · Se estudian las propiedades matemáticas de los conjuntos libres de alianzas y los cubrimientos de alianzas. En particular, se obtienen cotas tensas para la cardinalidad máxima de un conjunto libre de alianzas y la cardinalidad mínima de un cubrimiento de alianzas. Además, se caracterizan grafos que son libres de k-alianzas defensivas.· Se introduce el concepto de alianza frontera y se estudian algunas de sus propiedades. Entre los resultados obtenidos se destaca una condición necesaria para la existencia de una partición de un grafo regular en dos alianzas fronteras. · Se estudian las alianzas ofensivas globales y sus relaciones con algunos conjuntos característicos en grafos, tales como conjuntos dominantes, t-dominantes y r-dependientes.· Se estudian las alianzas de cardinal mínimo. En particular, se hacen estimaciones de dicho cardinal en función de diversos invariantes del grafo.

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. / A Quantified Real Constraint (QRC) is a mathematical formalism that is used to model many physical problems involving systems of nonlinear equations linking real variables, some of them affected by logical quantifiers. QRCs appear in numerous contexts, such as Control Engineering or Biology. QRC solving is an active research domain for which two radically different approaches are proposed: the symbolic quantifier elimination and the approximate methods. However, solving large problems within a reasonable computational time and solving the general case, still remain open problems. This thesis proposes a new approximate methodology based on Modal Interval Analysis (MIA), a mathematical theory that allows solving in an elegant way, problems involving logical quantifiers over real variables.Finally, two control engineering applications are presented. The first refers to the problem of fault detection and the second consists of the realization of a controller for a sailboat.

Para obtener una ventaja competitiva en el mercado global, los fabricantes tienen que adaptarse rápidamente sus sistemas para responder a las fluctuantes demandas de los clientes en virtud de factores de servicio de alta calidad. La alta inversión de capital en los sistemas de fabricación flexible (SFFs), junto con los desafíos de las condiciones de mercado que cambian rápidamente se ha convertido en esencial la utilización eficiente de los recursos. Para maximizar los beneficios de un SFF, se necesita una implantación de técnicas de programación e planificación adecuadas para aprovechar plenamente las flexibilidades de fabricación. El objetivo global de esta tesis es establecer un marco de programación basado en el modelado de redes de Petri coloreadas temporales (RdPCT) para optimizar el rendimiento de los SFF mediante el desarrollo de herramientas y métodos de búsqueda eficientes basados en el análisis del espacio de estados (EdE). El análisis del espacio del estado es una herramienta potente que se puede utilizar para automatizar la actividad de toma de decisiones en problemas de programación mediante el seguimiento de todos los posibles comportamientos del sistema modelado. Sin embargo, adolece del problema de explosión de espacio de estado debido a la complejidad computacional de los problemas de programación de la producción en SFFs. Lo que ha limitado su aplicabilidad a problemas de tamaño pequeño. En la metodología de la programación propuesta, la generación de un plan de producción óptimo consiste en la construcción y el recorrido del espacio de estados con un algoritmo de búsqueda. Además, se requiere un simulador para la ejecución del modelo de RdPCT. Es muy natural utilizar el gráfico algoritmos de búsqueda ya que el método de análisis subyacente se basa en el EdE. La estrategia de búsqueda gráfica es una técnica interdisciplinaria que atraviesa los campos de la inteligencia artificial (IA), la investigación operativa (OR), e Informática. Esta tesis se centra en los métodos de búsqueda heurística basados en IA que se utilizan para simular solamente los mejores escenarios (como un problema de búsqueda del camino más corto). En este método, la exploración de los EdE son guiados con funciones heurísticas que se basan en el conocimiento de los planes de producción. La contribución de esta tesis es cuádruple. La primera ofrece la plataforma en que se implementan las otras tres contribuciones: una herramienta para soporte de decisión automatizada y de uso especial llamado TIMed State space Performance Analysis Tool (TIMSPAT). En segundo lugar, se desarrolló un enfoque de memoria eficiente para aliviar el problema de escalabilidad que aparece en la exploración de EdE de problemas de programación FMS. En tercer lugar, se presenta dos algoritmos de búsqueda heurística a cualquier hora, desarrollados para superar las desventajas de los algoritmos de búsqueda heurística convencionales. Finalmente, la última contribución presenta un enfoque basado en RdPCT a la programación simultánea de máquinas y vehículos guiados automáticamente (AGV) con enrutamiento libre de conflictos. / To gain competitive advantage in the global market, manufacturers have to quickly adapt their systems to respond to fluctuating customer demands under high-quality service factors. The high capital investment in flexible manufacturing systems (FMSs) together with the challenges of the rapidly changing market conditions has made efficient resource utilization become essential. To maximize the benefits of an FMS, appropriate scheduling techniques must be put in place to fully exploit the manufacturing flexibilities. The overall objective of this thesis is to establish a scheduling framework based on timed colored Petri net (TCPN) modeling for optimizing the performance of FMSs through the development of tools and efficient search methods based on the reachability graph (or state space) analysis. In the proposed TCPN-based scheduling methodology, the generation of an optimal production schedule involves the construction and traversal of the state space with a search algorithm. Also, a simulator is required for executing the TCPN model. It is quite natural to use graph search algorithms since the underlying analysis method relies on the reachability graph. Graph search strategy is an interdisciplinary technique that spans across the fields of Artificial intelligence (AI), Operations research (OR), and Computer science. This thesis focuses on AI-based heuristic search methods used in simulating only the best scenarios (as a shortest-path search problem). In this method, the exploration of reachability graphs are guided with heuristic functions that rely on the knowledge of the production plans. The contribution of this thesis is fourfold. The first provides the platform called TIMSPAT in which the other three contributions are implemented. Because of the complex data structure, TCPN-based scheduling using reachability graph analysis has been merely looked at in the literature. Thanks to the common data structure of the heuristic search methods, TIMSPAT is capable of incorporating different search algorithms in a single executable tool. So far, nine algorithms have been implemented, which includes the search algorithms proposed in this thesis and those by other authors. Second, a memory-efficient approach is developed to alleviate the scalability problem that appears in the state space exploration of FMS scheduling problems. The approach tackles the research questions: Is it necessary to store all the generated states to guarantee an optimal solution without revisiting states? and how can one reduce the number of states to be stored so that larger problems can be solved without forgoing optimality? It assumes that the state space graphs of a system with increasing problem size may contain repetitive patterns while the underlying model structure remains as constant as possible. The proposed solution is based on the notion that the structural behavior captured in the state space of a solvable smaller problem size can be extended to explore a larger size if the two problems share a certain kind of similarity. The third contribution presents two anytime heuristic search algorithms developed to overcome the drawbacks of conventional heuristic search algorithms. The first anytime algorithm adapts and improves an existing anytime algorithm to TCPN-based scheduling, while the second proposes a new algorithm that combines two heuristic search algorithms making them anytime for deadlock-free scheduling. The algorithms are suitable for both off-line and on-line scheduling purposes due to their effectiveness in adapting to different CPU constraints. The last contribution presents a TCPN-based approach to the simultaneous scheduling of machines and automated guided vehicles (AGVs) with conflict-free routing. Unlike the existing approaches that employ a decomposition framework, the entire scheduling problem is described in a single model. Two simultaneous scheduling models are proposed and evaluated using an event-driven vehicle assignment solution as opposed to the traditional dispatching rules.

Aquesta tesi tracta d'algoritmes i fenòmens complexos en xarxes.En la primera part s'estudia un model de neurones estocàstiques inter-comunicades mitjançant potencials d'acció. Proposem una tècnica de modelització a escala mesoscòpica i estudiem una transició de fase en un acoblament crític entre les neurones. Derivem una regla de plasticitat sinàptica local que fa que la xarxa s'auto-organitzi en el punt crític.Seguidament tractem el problema d'inferència aproximada en xarxes probabilístiques mitjançant un algorisme que corregeix la solució obtinguda via belief propagation en grafs cíclics basada en una expansió en sèries. Afegint termes de correcció que corresponen a cicles generals en la xarxa, s'obté el resultat exacte. Introduïm i analitzem numèricament una manera de truncar aquesta sèrie.Finalment analizem la interacció social en una comunitat d'Internet caracteritzant l'estructura de la xarxa d'usuaris, els fluxes de discussió en forma de comentaris i els patrons de temps de reacció davant una nova notícia. / This thesis is about algorithms and complex phenomena in networks.In the first part we study a network model of stochastic spiking neurons. We propose a modelling technique based on a mesoscopic description level and show the presence of a phase transition around a critical coupling strength. We derive a local plasticity which drives the network towards the critical point.We then deal with approximate inference in probabilistic networks. We develop an algorithm which corrects the belief propagation solution for loopy graphs based on a loop series expansion. By adding correction terms, one for each "generalized loop" in the network, the exact result is recovered. We introduce and analyze numerically a particular way of truncating the series.Finally, we analyze the social interaction of an Internet community by characterizing the structure of the network of users, their discussion threads and the temporal patterns of reaction times to a new post.

No description available.

La presente memoria describe el trabajo desarrollado en el diseño y evaluación de un coprocesador para la migración vertical dinámica en tiempo de ejecución, para sistemas microprogramados. Esta memoria ha sido estructurada en cuatro capítulos cuyos contenidos resumimos a continuación. CAPÍTULO 1. Se presenta una introducción sobre el tema de la migración vertical, primero desde su vertiente clásica de implementación "off-line", y más tarde desde el punto de vista on-line (en tiempo de ejecución). En este capítulo, se expone en líneas generales el trabajo que ha sido desarrollado, describiendo las características básicas de la estrategia presentada, la estructura del sistema y su modo de funcionamiento, así como su simulación y aplicación a un ejemplo concreto. CAPÍTULO 2. Este capítulo ha sido dedicado a la descripción detallada de la estructura del sistema, así como de su modo de funcionamiento, analizando cada una de las partes del coprocesador por separado, y su papel en el funcionamiento del mismo. El funcionamiento del sistema es analizado en las dos situaciones que se pueden presentar al ejecutar una introducción_ a- que deba realizarse su migración. b- que esta ya se encuentre migrada (versión en lenguaje intermedio o "J+1/2". Esto permite estudiar posteriormente los parámetros que influyen en la aceleración de la ejecución de un programa. CAPITULO 3. Se realiza un estudio comparativo de los métodos clássicos (off-line) con el método propuesto en este trabajo (on-line). El desarrollo de un programa simulador, para un sistema que incorpore el coprocesador para la migración vertical cen tiempo de ejecución, nos ha permitido analizar el comportamiento de dicho sistema y la incidencia de los parámetros fundamentales, tales como el tamaño de la Memoria de Interconexión, su participación, algoritmos de reemplazamiento, etc... Por último, a partir de los resultados obtenidos con el programa simulador, ha sido posible elaborar un modelo algorítmico que permite la evaluación de la ganancia que se puede obtener en un sistema con el coprocesador, para una configuración de parámetros dada y un programa determinado. CAPÍTULO 4. La estrategia de adaptación propuesta, coprocesador para migración en tiempo de ejecución, ha sido aplicada a un ejemplo concreto, el microprocesador "R6502". Inicialmente se ha procedido a su emulación del R6502 sobre una simulación de un sistema microprogramado, para posteriormente incluir el coprocesador propuesto y generar el intérprete del lenguaje intermedio definido.