El problema de corte bidimensional consiste en satisfacer una demanda de objetos pequeños, piezas, a partir de un conjunto de objetos grandes, tableros, de forma que se maximice el beneficio o se minimice la pérdida del material sobrante. En esta Tesis se han abordado dos problemas concretos de corte en dos dimensiones. En ellos suponemos que las piezas a cortar y los tableros son rectangulares y que se permiten cortes que no sean de tipo guillotina. El primer problema tratado ha sido aquél en el que se dispone de un tablero del que se ha de cortar el máximo número de piezas de un solo tipo. Este problema es conocido como el Pallet Loading Problem, ya que su aplicación más habitual surge cuando un pallet rectangular se ha de llenar en la fábrica con el mayor número posible de cajas de un solo producto.. Nuestro trabajo ha consistido, en primer lugar, en el desarrollo de un algoritmo exacto, basado en procedimientos Branch and Cut, que no habían sido aplicados hasta ahora a este problema. Este algoritmo ha permitido resolver óptimamente problemas de hasta 100 cajas que no habían sido resueltos en los trabajos publicados hasta la fecha. En segundo lugar, se ha desarrollado un algoritmo heurístico basado en Tabu Search que resuelve de forma eficiente problemas de hasta 150 cajas.El segundo problema tratado es el problema en el que se dispone de un tablero, del que se ha de cortar un subconjunto de las piezas demandadas. Este problema admite, a su vez, cuatro subproblemas, dependiendo de la función objetivo (maximizar el valor de las piezas cortadas o minimizar el área no utilizada del tablero) y de la existencia o no de cotas superiores en el número de piezas a cortar de cada tipo. Se han desarrollado algoritmos heurísticos que resuelven las cuatro versiones del problema. Inicialmente se han desarrollado algoritmos constructivos rápidos, que pueden servir como subrutinas de algoritmos más complejos. En una segunda fase, se ha diseñado un algoritmo metaheurístico más complejo, GRASP, para obtener soluciones, que superan en calidad y menor tiempo de computación a las de los mejores algoritmos publicados. / The constrained two-dimensional cutting problem consists of satisfying the demands of small pieces from a set of large stock sheets with the objective of maximizing the total value of the pieces cut. In this work we have studied two particular two-dimensional cutting problems in which both pieces and stock sheets are rectangular and non-guillotine cuts are allowed. The Pallet Loading Problem (PLP) arises whenever identical rectangular boxes have to be packed on a rectangular pallet. Though the problem is initially three-dimensional, practical considerations usually mean that the boxes must be placed orthogonally with respect to the edges of the pallet, and in layers in which the vertical orientation of the boxes is fixed. With these restrictions the problem becomes the two-dimensional problem of packing a large rectangle, pallet, with the maximum number of small identical rectangles, boxes. The problem has many practical applications in distribution and logistics. We have developed a branch and cut algorithm for that problem. The 0-1 formulation proposed by Beasley for cutting problems is adapted to the problem, adding new constraints and new procedures for variable reduction. We then take advantage of the relationship between this problem and the maximum independent set problem to use the partial linear description of its associated polyhedron. Finally, we exploit the specific structure of our problem to define the solution graph and to develop efficient separation procedures. We present computational results for the complete sets Cover I (up to 50 boxes) and Cover II (up to 100 boxes) which .had not been previously solved. In a second phase, we have developed a heuristic algorithm, based on Tabu Search, that solves efficiently problems with up to 150 boxes. In the second problem studied several types of pieces can be cut from the large stock rectangle. For this problem we have developed a greedy randomized adaptive search procedure (GRASP). We investigate several strategies for the constructive and improvement phases and several choices for critical search parameters. We perform extensive computational experiments with well known instances previously reported, which show that our algorithm improves the best known results in terms of quality and computing time.

This dissertation addresses three different problems in the study of discrete dynamical systems. Firstly, this work dynamically classifies a 9−parametric family of planar birational maps f : C2 → C2 that is f(x, y) = α0 + α1x + α2y, β0 + β1x + β2y γ0 + γ1x + γ2y , where the parameters are complex numbers. This is done by finding the dynamical degree δ for the degenerate and non degenerate cases of F that is the extended map of f in projective space. The dynamical degree δ defined as δ(F) := lim n→∞ (deg(Fn)) 1 n , indicates the subfamilies which are chaotic, that is when δ > 1, and otherwise. The study of the sequence of degrees dn of F shows the degree growth rate of all the subfamilies of f. This gives the families which have bounded growth , or they grow linearly, quadratically or grow exponentially. The family f includes the birational maps studied by Bedford and Kim in [18] as one of its subfamily. The second problem includes the study of the subfamilies of f with zero entropy that is for δ = 1. These includes the families with bounded (in particular periodic), linear or quadratic growth rate. Two transverse fibrations are found for the families with bounded growth. In the periodic case the period of the families is indicated. It is observed that there exist infinite periodic subfamilies of f, depending on the parameter region. The families with linear growth rate preserve rational fibration and the quadratic growth rate families preserve elliptic fibration that is unique depending on the parameters. In all the cases with zero entropy all the mappings are found up to affine conjugacy. Thirdly, it deals with non-autonomous Lyness type recurrences of the form xn+2 = an + xn+1 xn , where {an}n is a k-periodic sequence of complex numbers with minimal period k. We treat such non-autonomous recurrences via the autonomous dynamical system generated by the birational mapping Fak ◦ Fak−1 ◦ · · · ◦ Fa1 where Fa is defined by Fa(x, y) = (y, a + y x ). For the cases k ∈ {1, 2, 3, 6} the corresponding mappings have a rational first integral. By calculating the dynamical degree we show that for k = 4 and for k = 5 generically the dynamical system is no longer rationally integrable. We also prove that the only values of k for which the corresponding dynamical system is rationally integrable for all the values of the involved parameters, are k ∈ {1, 2, 3, 6}.

Esta monografía presenta un marco de trabajo para el aprendizaje en un escenario de datos distribuidos y con control descentralizado. Hemos basado nuestro marco de trabajo en Sistemas Multi-Agente (MAS) para poder tener control descentralizado, y en Razonamiento Basado en Casos (CBR), dado que su naturaleza de aprendizaje perezoso lo hacen adecuado para sistemas multi-agentes dinámicos. Además, estamos interesados en agentes autónomos que funcionen como ensembles. Un ensemble de agentes soluciona problemas de la siguiente manera: cada agente individual soluciona el problema actual individualmente y hace su predicción, entonces todas esas predicciones se agregan para formar una predicción global. Así pues, en este trabajo estamos interesados en desarrollar estrategias de aprendizaje basadas en casos y en ensembles para sistemas multi-agente.Concretamente, presentaremos un marco de trabajo llamado Razonamiento Basado en Casos Multi-Agente (MAC), una aproximación al CBR basada en agentes. Cada agente individual en un sistema MAC es capaz de aprender y solucionar problemas individualmente utilizando CBR con su base de casos individual. Además, cada base decasos es propiedad de un agente individual, y cualquier información de dicha base de casos será revelada o compartida únicamente si el agente lo decide así. Por tanto, este marco de trabajo preserva la privacidad de los datos y la autonomía de los agentes para revelar información.Ésta tesis se centra en desarrollar estrategias para que agentes individuales con capacidad de aprender puedan incrementar su rendimiento tanto cuando trabajan individualmente como cuando trabajan como un ensemble. Además, las decisiones en un sistema MAC se toman de manera descentralizada, dado que cada agente tiene autonomía de decisión. Por tanto, las técnicas desarrolladas en este marco de trabajo consiguen un incremento del rendimiento como resultado de decisiones individuales tomadas de manera descentralizada. Concretamente, presentaremos tres tipos de estrategias: estrategias para crear ensembles de agentes, estrategias para realizar retención de casos en sistemas multi-agente, y estrategias para realizar redistribución de casos. / This monograph presents a framework for learning in a distributed data scenario with decentralized decision making. We have based our framework in Multi-Agent Systems (MAS) in order to have decentralized decision making, and in Case-Based Reasoning (CBR), since the lazy learning nature of CBR is suitable for dynamic multi-agent systems. Moreover, we are interested in autonomous agents that collaborativelywork as ensembles. An ensemble of agents solves problems in the following way: each individual agent solves the problem at hand individually and makes its individual prediction, then all those predictions are aggregated to form a global prediction. Therefore, in this work we are interested in developing ensemble case basedlearning strategies for multi-agent systems.Specifically, we will present the Multi-Agent Case Based Reasoning (MAC) framework, a multi-agent approach to CBR. Each individual agent in a MAC system is capable of individually learn and solve problems using CBR with an individual case base. Moreover, each case base is owned and managed by an individual agent, and any information is disclosed or shared only if the agent decides so. Thus, this framework preserves the privacy of data, and the autonomy to disclose data.The focus of this thesis is to develop strategies so that individual learning agents improve their performance both individually and as an ensemble. Moreover, decisions in the MAC framework are made in a decentralized way since each individual agent has decision autonomy. Therefore, techniques developed in this framework achieve an improvement of individual and ensemble performance as a result of individual decisions made in a decentralized way. Specifically, we will present three kind of strategies: strategies to form ensembles of agents, strategies to perform case retention in multi-agent systems, and strategies to perform case redistribution.

SISTEMAS DE INSERCIÓN Y BORRADO: COMPLEJIDAD Y CAPACIDAD DE MODELADO El objetivo central de la tesis es el estudio de los sistemas de inserción y borrado y su capacidad computacional. Más concretamente, estudiamos algunos modelos de generación de lenguaje que usan operaciones de reescritura de dos cadenas. También consideramos una variante distribuida de los sistemas de inserción y borrado en el sentido de que las reglas se separan entre un número finito de nodos de un grafo. Estos sistemas se denominan sistemas controlados mediante grafo, y aparecen en muchas áreas de la Informática, jugando un papel muy importante en los lenguajes formales, la lingüística y la bio-informática. Estudiamos la decidibilidad/ universalidad de nuestros modelos mediante la variación de los parámetros de tamaño del vector. Concretamente, damos respuesta a la cuestión más importante concerniente a la expresividad de la capacidad computacional: si nuestro modelo es equivalente a una máquina de Turing o no. Abordamos sistemáticamente las cuestiones sobre los tamaños mínimos de los sistemas con y sin control de grafo. / COMPLEXITY AND MODELING POWER OF INSERTION-DELETION SYSTEMS The central object of the thesis are insertion-deletion systems and their computational power. More specifically, we study language generating models that use two string rewriting operations: contextual insertion and contextual deletion, and their extensions. We also consider a distributed variant of insertion-deletion systems in the sense that rules are separated among a finite number of nodes of a graph. Such systems are refereed as graph-controlled systems. These systems appear in many areas of Computer Science and they play an important role in formal languages, linguistics, and bio-informatics. We vary the parameters of the vector of size of insertion-deletion systems and we study decidability/universality of obtained models. More precisely, we answer the most important questions regarding the expressiveness of the computational model: whether our model is Turing equivalent or not. We systematically approach the questions about the minimal sizes of the insertiondeletion systems with and without the graph-control.

Uno de los principales objetivos de la Estadística es la comparación de variables aleatorias. Estas comparaciones están principalmente basadas en mediadas asociadas a dichas variables como las medias, medianas o varianzas. En muchas situaciones, estas comparaciones no resultan muy informativas, por lo que sería de interés establecer criterios de comparación más elaborados, lo que ha motivado el desarrollo de la teoría de ordenaciones estocásticas. Dicha teoría esta formada por diversos criterios que comparan distintas características asociadas a las variables, las cuáles se miden mediante funciones de interés en fiabilidad, riesgos y economía. Estas funciones están definidas en términos de ciertas integrales incompletas de las funciones cuantiles o de supervivencia. Desafortunadamente, dichas integrales no siempre tiene expresión explícita, lo cuál dificulta el estudio. A pesar de poder verificar otras ordenaciones, así como condiciones más fuertes, hay muchos casos que no están cubiertos por ninguna herramienta existente en la literatura, puesto que todas las ordenaciones son parciales. Por esta razón, una de las principales líneas de investigación dentro de este tópico es el estudio de condiciones suficientes para los distintos criterios que sean fáciles de verificar cuando las variables no se ordenen en ningún criterio más fuerte. Por ejemplo, el conocido orden creciente convexo se verifica cuando las integrales incompletas de las funciones de supervivencia están ordenadas. Sin embargo, existen muchas situaciones en las que estas integrales no tiene expresión analítica. En este caso, se puede verificar el orden estocástico, que es el criterio de comparación de localización más fuerte, el cuál se cumple cuando se ordenan las funciones de supervivencia. Este criterio es fácil de verificar siempre que las funciones de supervivencia tengan expresión explícita, pero incluso en los casos en los que no la tienen, existen condiciones suficientes en términos de las funciones de densidad. El problema es que, como ya hemos dicho, las variables no tienen por qué estar ordenadas estocásticamente. Afortunadamente, para el orden creciente convexo existen las conocidas condiciones de Karlin-Novikov que siempre se pueden verificar, ya que se establecen en términos de los puntos de corte entre las funciones de supervivencia, cuantiles o de densidad. Nuestro principal objetivo es continuar esta línea de investigación para algunos de los órdenes más importantes en la literatura: el vida media residual, el total time on test transform, el excess wealth y el expected proportional shortfall. En detalle, lo que hacemos es estudiar condiciones suficientes para estos criterios en aquellas situaciones en las que no se verifican los órdenes más fuertes (el razón de fallo, el estocástico, el dispersivo y el estrella). Menos el estocástico, como ya hemos mencionado, estos criterios más fuertes están definidos en términos de la monotonía del cociente (o la diferencia) de las funciones de supervivencia (o cuantiles). Nuestro objetivo es establecer condiciones suficientes para los criterios mencionados en términos de los extremos relativos de dichas funciones, lo cuál es menos restrictivo que la monotonía de las mismas. Otro logro es la ordenación de distintas familias paramétricas conocidas de interés en fiabilidad, riesgos y economía, las cuáles se ordenan aplicando los distintos resultados establecidos en la tesis. Por otro lado, la comparación estocástica de datos ordenados es también un área de investigación importante dentro de este tópico y establecemos varios resultados en esta línea. Por último, trabajamos en los órdenes estocásticos conjuntos. Estos criterios tienen en cuenta la estructura de dependencia entre las variables, lo cuál es de interés, por ejemplo, en situaciones en las que se quieren comparar los tiempos de vida de dos individuos o mecanismos que envejecen en el mismo ambiente y además dependen de dicho ambiente. También hacemos aportaciones en este área. / One of the main objectives of statistics is the comparison of random quantities. These comparisons are mainly based on measures associated to these random quantities, like the means, medians or variances. In some situations, the comparisons based only on two single measures are not very informative. The necessity of providing more elaborate comparisons of two random quantities has motivated the development of the theory of the stochastic orders. This theory is composed of different criteria which compare different characteristics measured by several functions of interest in reliability, risks and economy. Such functions are defined in terms of certain incomplete integrals of the survival or quantile functions. Unfortunately, these integrals can not be given in an explicit way in most cases, therefore we can not check directly these orders by their definitions. Even though we can verify some stronger orders or conditions, there are lots of cases which are not covered by any tool in the literature. Due to this fact, one of the main direction of research on this topic is the exploration of sufficient conditions, easy to verify, for these orders when the strongest ones do not hold. For instance, the well-known increasing convex order holds when the incomplete integrals of the survival functions are ordered. However, there are loads of situations where this integrals do not have analytical expression, which makes difficult to verify the order. In this case, we can check the stochastic order, since it is widely known that it is the strongest order to compare location and holds when the survival functions are ordered, which is a simple condition to verify, as long as the survival functions have an explicit expression; but also if this does not occurs, there exists a sufficient condition in terms of the density functions. However, there are lots of situations where the random variables are not ordered in the stochastic order. Luckily, to check the increasing convex order in this cases, there exist the renowned Karlin-Novikov conditions established in terms of the crossing among the survival, quantile and density functions, therefore these conditions can be always verified. Our main purpose in this thesis is to continue this line of research for some of the main orders in the literature: the mean residual life, the total time on test transform, the excess wealth and the expected proportional shortfall order. Down to the last detail, we consider the situation where the strongest orders are not verified (the hazard rate, the stochastic, the dispersive and the star shaped orders, respectively), which are mainly defined in terms of the monotonicity of the ratio (or the difference) of the survival or the quantile functions. We seek an intermediate condition between the strongest order and the corresponding weaker order. Principally, we consider the situations where they have a relative extreme, a property less restrictive than being monotone, to establish several sets of sufficient conditions. Furthermore, a relevant goal of this thesis is to apply the provided results to order several well-known parametric families, which have particular interest to fit data in reliability, risks and economy. The stochastic comparison of ordered data is another of the most important areas of research in this topic and we also provide some results in this direction. Finally, we work on the joint stochastic orders, which take into account the dependence structure among the random variables. This is of interest, for example, if we are interested in comparing two units which are aging in the same environment and both depend on this environment. We also provide some contributions to this area.

Resum pendent

This thesis addresses the development of techniques to build fully-automatic tools for analyzing sequential programs written in imperative languages like C or C++. In order to do the reasoning about programs, the approach taken in this thesis follows the constraint-based method used in program analysis. The idea of the constraint-based method is to consider a template for candidate invariant properties, e.g., linear conjunctions of inequalities. These templates involve both program variables as well as parameters whose values are initially unknown and have to be determined so as to ensure invariance. To this end, the conditions on inductive invariants are expressed by means of constraints (hence the name of the approach) on the unknowns. Any solution to these constraints then yields an invariant. In particular, if linear inequalities are taken as target invariants, conditions can be transformed into arithmetic constraints over the unknowns by means of Farkas' Lemma. In the general case, a Satisfiability Modulo Theories (SMT) problem over non-linear arithmetic is obtained, for which effective SMT solvers exist. One of the novelties of this thesis is the presentation of an optimization version of the SMT problems generated by the constraint-based method in such a way that, even when they turn out to be unsatisfiable, some useful information can be obtained for refining the program analysis. In particular, we show in this work how our approach can be exploited for proving termination of sequential programs, disproving termination of non-deterministic programs, and do compositional safety verification. Besides, an extension of the constraint-based method to generate universally quantified array invariants is also presented. Since the development of practical methods is a priority in this thesis, all the techniques have been implemented and tested with examples coming from academic and industrial environments. The main contributions of this thesis are summarized as follows: 1. A new constraint-based method for the generation of universally quantified invariants of array programs. We also provide extensions of the approach for sorted arrays. 2. A novel Max-SMT-based technique for proving termination. Thanks to expressing the generation of a ranking function as a Max-SMT optimization problem where constraints are assigned different weights, quasi-ranking functions -functions that almost satisfy all conditions for ensuring well-foundedness- are produced in a lack of ranking functions. Moreover, Max-SMT makes it easy to combine the process of building the termination argument with the usually necessary task of generating supporting invariants. 3. A Max-SMT constraint-based approach for proving that programs do not terminate. The key notion of the approach is that of a quasi-invariant, which is a property such that if it holds at a location during execution once, then it continues to hold at that location from then onwards. Our technique considers for analysis strongly connected subgraphs of a program's control flow graph and thus produces more generic witnesses of non-termination than existing methods. Furthermore, it can handle programs with unbounded non-determinism. 4. An automated compositional program verification technique for safety properties based on quasi-invariants. For a given program part (e.g., a single loop) and a postcondition, we show how to, using a Max-SMT solver, an inductive invariant together with a precondition can be synthesized so that the precondition ensures the validity of the invariant and that the invariant implies the postcondition. From this, we build a bottom-up program verification framework that propagates preconditions of small program parts as postconditions for preceding program parts. The method recovers from failures to prove validity of a precondition, using the obtained intermediate results to restrict the search space for further proof attempts. / Esta tesis se centra en el desarrollo de técnicas para construir herramientas altamente automatizadas que analicen programas secuenciales escritos en lenguajes imperativos como C o C++. Para realizar el razonamiento sobre los programas, la aproximación tomada en esta tesis se basa en un conocido método basado en restricciones utilizado en análisis de progamas. La idea de dicho método consiste en considerar plantillas que expresen propiedades invariantes candidatas, p.e., conjunciones de desigualdades lineales. Estas plantillas contienen tanto variables del programa como parámetros cuyos valores son inicialmente desconocidos y tienen que ser determinados para garantizar la invariancia. Para este fin, las condiciones sobre invariantes inductivos son expresadas mediante restricciones sobre los valores desconocidos. Cualquier solución a estas restricciones llevan a un invariante. En particular, si desigualdades lineales son los invariantes objetivo, las condiciones pueden ser transformadas en restricciones aritméticas sobre los valores desconocidos mediante el lema de Farkas. En el caso general, un problema de Satisfactibilidad Modulo Teorías (SMT) sobre aritmética no-lineal es obtenido, para el cual existen resolvedores eficientes. Una de las novedades de esta tesis es la presentación de una versión de optimización de los problemas SMT generados por el método tal que, incluso cuando son insatisfactibles, se puede obtener cierta información útil para refinar el análisis del programa. En particular, en este trabajo se muestra como la aproximación tomada puede usarse para probar terminación de programas, probar la no terminación de programas y realizar verificación por partes de la corrección de programas. Además, también se describe una extensión del método basado en restricciones para generar invariantes universalmente cuantificados sobre arrays. Debido a que el desarrollo de métodos prácticos es una prioridad en esta tesis, todas las técnicas han sido implementadas y probadas con ejemplos extraídos del entorno académico e industrial. Las principales contribuciones de esta tesis pueden resumirse en: 1. Un nuevo método basado en restricciones para la generación de invariantes universalmente cuantificados sobre arrays. También se explica extensiones del método para aplicarlo a arrays ordenados. 2. Un técnica novedosa basada en Max-SMT para probar terminación. Gracias a expresar la generación de funciones de ranking como problemas de optimización Max-SMT, donde a las restricciones se les asigna diferentes pesos, se generan cuasi-funciones de ranking, funciones que casi satisfacen todas las condiciones que garantizan la existencia de una relación bien fundada, en ausencia de funciones de ranking. Además, Max-SMT facilita la combinación del proceso de construcción de un argumento de terminación con la tarea habitualmente necesaria de generar invariantes de apoyo. 3. Un método basado en restricciones y Max-SMT para probar que un programa no termina. El concepto clave del método es el de cuasi-invariante, que es una propiedad tal que si se cumple una vez en un punto del programa durante la ejecución, entonces continúa cumpliendose en ese punto desde entonces en adelante. Nuestra técnica considera en su análisis subgrafos fuertemente conexos del grafo de control de flujo del programa y produce testigos de no terminación más genéricos que otros métodos existentes. Además, es capaz de tratar programas con no determinismo. 4. Una técnica automatizada de verificación por partes de propiedades de corrección de un programa basada en cuasi-invariantes. Dado una parte de un programa (p.e., un único bucle) con una postcondición, se muestra como, usando Max-SMT, puede sintetizarse un invariante inductivo junto a una precondición que garantiza la validez del invariante y que el invariante implica la postcondición. Apartir de esto, se describe una infraestructura de verificación de programas de abajo a arriba que propaga precondiciones.

La tasca de dissenyar el mecanisme de presa de decisions d'un equip de robots és un gran repte, no només per la complexitat de l'entorn en el qual els robots realitzen les seves tasques, que comporta incertesa, dinamicitat i imprecisió, sinó també perquè la coordinació entre els robots s'ha de tenir en compte a l'hora de dissenyar el mecanisme. Els robots han de ser conscients de les accions dels altres robots per tal de cooperar i assolir satisfactòriament els objectius de l'equip. Aquesta tesi doctoral presenta una novedosa aproximació basada en casos per la selecció d'accions i la coordinació de tasques cooperatives en equips de robots. Aquesta aproximació s'ha aplicat i avaluat en un domini molt representatiu, com és el del futbol robòtic, tot i que les idees presentades són aplicables a altres dominis com les operacions de rescat, l'exploració d'entorns desconeguts i la vigilància submarina, entre d'altres. El procés de selecció proposa un cas per reutilitzar, avaluant els casos candidats amb una sèrie de criteris per tal de tenir en compte les característiques d'un entorn real, incloent-hi la presència d'adversaris, que és un factor clau en el domini del futbol robòtic. A diferència dels sistemes de raonament basats en casos clàssics, la reutilització del cas consisteix en l'execució d'un conjunt d'accions per part d'un equip de robots. Per tant, des de la perspectiva multi- robot, el sistema ha d'incloure un mecanisme per tal de decidir qui fa què i com. En aquesta tesi, es presenta una arquitectura multi-robot juntament amb un mecanisme de coordinació per tal d'atacar aquests reptes. Hem validat experimentalment l'aproximació tant en simulació com amb robots reals. L'experimentació ha permès comprovar que l'aproximació presentada assoleix els objectius de la tesi, és a dir, el disseny de comportaments d'un equip de robots cooperatius. Així mateix, els resultats obtinguts també mostren els avantatges d'utilitzar una estratègia col·laborativa en entorns en els quals el component adversari juga un paper important, en contrast amb comportaments individualistes. / Designing the decision-making engine of a team of robots is a challenging task, not only due to the complexity of the environment where the robots usually perform their task, which include uncertainty, dynamism and imprecision, but also because the coordination of the team must be included in this design. The robots must be aware of other robots' actions to cooperate and to successfully achieve their common goal. Besides, decisions must be made in real-time and with limited computational resources.This thesis contributes a novel case-based approach for action selection and coordination in joint multi-robot tasks in real environments. This approach has been applied and evaluated in the representative domain of robot soccer, although the ideas presented are applicable to domains such as disaster rescue operations, exploration of unknown environments and underwater surveillance, among others. The retrieval process proposes a case to reuse, evaluating the candidate cases through different measures to overcome the real world characteristics, including the adversarial component which is a key ingredient in the robot soccer domain. Unlike classical case- based reasoning engines, the case reuse consists in the execution of a set of actions through a team of robots. Therefore, from the multi- robot perspective, the system has to include a mechanism for deciding who does what and how. In this thesis, we propose a multi- robot architecture along with a coordination mechanism to address these issues. We have validated the approach experimentally both in a simulated environment and with real robots. The results showed that our approach achieves the expected goals of the thesis, i.e. designing the behavior of a cooperative team of robots. Moreover, the experimentation also showed the advantages of using collaborative strategies in contrast to individualistic ones, where the adversarial component plays an important role.

Molts problemes de la vida quotidiana estan plens de decisions multi-classe. En l'àmbit del Reconeixement de Patrons, s'han proposat moltes tècniques d'aprenentatge que treballen sobre problemes de dos classes. No obstant, la extensió de classificadors binaris al cas multi-classe és una tasca complexa. En aquest sentit, Error-Correcting Output Codes (ECOC) han demostrat ser una eina potent per combinar qualsevol nombre de classificadors binaris i així modelar problemes multi-classe. No obstant, encara hi ha molts punts oberts sobre les capacitats del framework d'ECOC. En aquesta tesis, els dos estats principals d'un disseny ECOC són analitzats: la codificació i la decodificació. Es presenten diferents alternatives de dissenys dependents del domini del problema. Aquests dissenys fan ús del coneixement del domini del problema per minimitzar el nombre de classificadors que permeten obtenir un alt rendiment de classificació. Per altra banda, l'anàlisi de la codificació de dissenys d'ECOC es emprada per definir noves regles de decodificació que prenen total avantatja de la informació provinent del pas de la codificació. A més a més, com que classificacions exitoses requereixen rics conjunts de característiques, noves tècniques de detecció/extracció de característiques es presenten i s'avaluen en els nous dissenys d'ECOC. L'avaluació de la nova metodologia es fa sobre diferents bases de dades reals i sintètiques: UCI Machine Learning Repositori, símbols manuscrits, senyals de trànsit provinents de sistemes Mobile Mapping, imatges coronàries d'ultrasò, imatges de la Caltech Repositori i bases de dades de malats de Chagas. Els resultats que es mostren en aquesta tesis mostren que s'obtenen millores de rendiment rellevants tant a la codificació com a la decodificació dels dissenys d'ECOC quan les noves regles són aplicades. / Many real problems require multi-class decisions. In the Pattern Recognition field, many techniques have been proposed to deal with the binary problem. However, the extension of many 2-class classifiers to the multi-class case is a hard task. In this sense, Error-Correcting Output Codes (ECOC) demonstrated to be a powerful tool to combine any number of binary classifiers to model multi-class problems. But there are still many open issues about the capabilities of the ECOC framework. In this thesis, the two main stages of an ECOC design are analyzed: the coding and the decoding steps. We present different problem-dependent designs. These designs take advantage of the knowledge of the problem domain to minimize the number of classifiers, obtaining a high classification performance. On the other hand, we analyze the ECOC codification in order to define new decoding rules that take full benefit from the information provided at the coding step. Moreover, as a successful classification requires a rich feature set, new feature detection/extraction techniques are presented and evaluated on the new ECOC designs. The evaluation of the new methodology is performed on different real and synthetic data sets: UCI Machine Learning Repository, handwriting symbols, traffic signs from a Mobile Mapping System, Intravascular Ultrasound images, Caltech Repository data set or Chaga's disease data set. The results of this thesis show that significant performance improvements are obtained on both traditional coding and decoding ECOC designs when the new coding and decoding rules are taken into account.

La utilització d'agents mòbils en sistemes distribuïts comporta diverses avantatges. Les avantatges més freqüentment citades inclouen: reducció de la càrrega de la xarxa, decrement de la latència de les comunicacions, adaptació dinàmica, i millor suport per dispositius mòbils amb connexions intermitents, entre d'altres. No obstant, els beneficis oferts pels agents mòbils no han estat suficients per estimular el seu ús generalitzat. La raó principal per la qual els agents mòbils no han estat àmpliament adoptats encara, a pesar dels seus avantatges tecnològics, és que aquesta tecnologia comporta certs riscos de seguretat. S'han dut a terme molts avenços en la seguretat, la fiabilitat i la eficiència dels agents mòbils, però hi ha problemes de seguretat que encara romanen sense solució.El treball principal d'aquesta tesi gira en torn a la protecció dels agents mòbils contra els hostes maliciosos. Per tal de proporcionar una solució a alguns dels problemes de seguretat actuals, en primer lloc, s'ha presentat un protocol de protecció d'itineraris que suporta agents que viatgen lliurament. Els protocols de protecció d'itineraris proposats fins ara limiten la capacitat de l'agent de migrar a voluntat. Per tant, aquesta tesi presenta un protocol que permet als agents descobrir noves plataformes en temps d'execució, de tal manera que les aplicacions poden aprofitar tots els avantatges proporcionats per la tecnologia dels agents mòbils.En segon lloc, s'ha presentat un protocol que protegeix els agents mòbils d'atacs de re-execució externs. Els atacs de re-execució externs estan basats en tornar a enviar l'agent a la seva plataforma destí, per tal de forçar-lo a re-executar part del seu itinerari. El protocol proposat evita aquest tipus d'atacs sense limitar la capacitat de l'agent de visitar certes plataformes repetidament.Les solucions de seguretat presentades en aquesta tesi es basen en el fet que en molts, si no en la majoria, dels escenaris basats en agents mòbils podem trobar plataformes de confiança. Mitjançant la incorporació de plataformes de confiança en l'itinerari de l'agent, les solucions proposades proporcionen un compromís equilibrat entre seguretat i flexibilitat.Per tal de promoure el desenvolupament d'aplicacions basades en agents mòbils segurs, aquesta tesi també presenta un entorn de desenvolupament que facilita la implementació dels protocols de protecció d'agents proposats, així com altres solucions de seguretat. / Several advantages have been identified in using mobile agents in distributed systems. The most frequently cited advantages include: reduction of network load, decrease in communication latency, dynamic adaptation, and better support for mobile devices with intermittent connections, among others. However, the benefits offered by mobile agents have not been sufficient to stimulate their widespread deployment. The main reason why mobile agents have not been widely adopted yet, despite their technological benefits, is their inherent security risks. Many breakthroughs have been achieved in the security, reliability and efficiency of mobile agents, but there are security issues still remaining unsolved.The core work of this thesis revolves around the protection of mobile agents against malicious hosts. In order to provide a solution to some of the current security issues, first of all, an itinerary protection protocol is presented that supports free-roaming agents. Itinerary protection protocols proposed to date limit the agent's ability to migrate at will. Therefore, this thesis presents a protocol that allows agents to discover new platforms at runtime, so that applications can take full advantage of the benefits provided by mobile agent itineraries.Second, a protocol is presented that protects mobile agents against external replay attacks. External replay attacks are based on resending the agent to another platform, so as to force the reexecution of part of its itinerary. The proposed protocol counters this kind of attacks without limiting the agent's ability to visit certain platforms repeatedly.The security solutions presented in this thesis are based on the fact that trusted platforms can be found in many, if not most, mobile agent-based scenarios. By incorporating trusted platforms in the agent's itinerary, the proposed solutions provide a balanced trade-off between security and flexibility.In order to promote the development of secure mobile agent-based applications, this thesis also presents a development environment that facilitates the implementation of the proposed agent protection protocols as well as other security solutions.