En el momento de ejecutar una aplicación paralela, el programador (o el usuario) se enfrenta a decisiones importantes para reducir el tiempo de ejecución global, tales como cuántos procesadores ha de usar para ejecutar la aplicación y, dado un número de procesadores, cómo distribuir las tareas de la aplicación aprovechando al máximo su capacidad de concurrencia. Al problema de resolver la distribución de las tareas de una manera global se le conoce como el problema del mapping.En la literatura existen dos formas distintas de abordar el problema del mapping en función del conocimiento que se tiene de la aplicación. Cuando el comportamiento de la aplicación es conocido (o predecible) a priori, la asignación se realiza de forma estática (antes de la ejecución), y las tareas se ejecutan en el procesador asignado hasta que finalizan. Por el contrario, cuando el comportamiento de la aplicación no es predecible, la asignación se realiza de forma dinámica, y las tareas pueden cambiar de procesador durante la ejecución. En el presente trabajo nos centramos en el proceso de mapping estático. Para la realización de este proceso, el programa paralelo se suele representar mediante un modelo de grafo de tareas ponderado, que resume las características más relevantes estimadas del comportamiento de la aplicación. En función del tipo de aplicación, en la literatura se utilizan principalmente dos modelos de grafo. Para aplicaciones cuyas tareas se comunican únicamente por el principio y el final, el modelo, denominado TPG (Task Precedence Graph), refleja las comunicaciones y precedencias entre las tareas y el orden parcial de ejecución de las mismas. Cuando se trata de aplicaciones cuyas tareas tienen comunicaciones en cualquier punto, e incluso comunicaciones bidireccionales, en la literatura se utiliza un modelo simplificado, denominado TIG (Task Interaction Graph), en el que no se contemplan las precedencias y se asume que todas las tareas pueden ser simultáneas.Ahora bien, en los entornos actuales de paso de mensajes, el programador no está sujeto a ninguna restricción en cuanto a la ubicación de las primitivas de comunicación dentro de las tareas. Además, debido al tipo de problemas que se resuelven computacionalmente, existe en los últimos años un creciente interés en el desarrollo de aplicaciones formadas por un conjunto de tareas que realizan distintas funciones y que coordinan su ejecución mediante intercambios de información en cualquier punto dentro de las mismas.Para modelar el comportamiento de las aplicaciones con paralelismo de tareas, con un patrón de interacciones entre tareas arbitrario, se propone un nuevo modelo de grafo, denominado Temporal Task Interaction Graph (TTIG). Dicho modelo incluye un nuevo parámetro, denominado grado de paralelismo, que indica la máxima capacidad de concurrencia de las tareas que se comunican, en función de las dependencias provocadas por dichas comunicaciones.A partir del comportamiento obtenido de la aplicación, se propone un mecanismo para determinar las cotas teóricas mínima y máxima sobre el número de procesadores necesario para realizar su ejecución en un tiempo mínimo. A partir del modelo TTIG se definen nuevas políticas de mapping de distintas complejidades que realizan las asignaciones de tareas teniendo en cuenta la posibilidad de concurrencia entre las mismas que indica el grado de paralelismo.En los entornos actuales de paso de mensajes PVM y MPI, la política de mapping que se usa por defecto es una distribución de las tareas basada en el orden de activación de las mismas. Dada la simplicidad de este mecanismo, dichos entornos se mejoran integrando un proceso automático para la extracción del grafo TTIG y para aplicar una política de mapping basada en dicho modelo. / Parallel programming presents the programmers (or the users) with daunting problems when attempting to achieve efficient execution. Two of these problems are to decide how many processors are necessary to execute the application and, for a specific number of processors, how to distribute the application tasks by exploiting their ability of concurrency, also known as the mapping problem.Mapping strategies can be classified as either static or dynamic, depending on the knowledge of the application. When the application has predictable run-time behaviour (i.e. the behaviour is loosely dependent on the input values), the mapping is carried out statically before execution. However, for applications whose run-time behaviour is not deterministic or not so predictable, performing mapping only once at the beginning is insufficient. For these cases the mapping is carried out dynamically during run-time.In this work, we focus on the static mapping problem. In order to accomplish the static mapping efficiently, the characteristics of the parallel program have to be known or estimated prior to execution. In this case, the application is represented in a task graph that summarizes the application behaviour.Depending on the characteristics of the application to be modelled, two distinct task graph models have been extensively used in the literature. The Task Precedence Graph (TPG), is a directed graph where nodes and arcs represent the tasks and the task precedence constraints respectively. This is effective for applications where interactions between tasks take place only at the beginning and at the end of their execution. On the other hand, distributed applications where the executing tasks are required to communicate during their lifetime rather than just at the initiation and at the end, are usually modelled in the literature by the Task Interaction Graph (TIG). This is an undirected graph that does not include temporal information and it is normally assumed that all the tasks may run in parallel.In current message-passing environments, the programmer has no restriction about the allocation of communication primitives inside tasks. Moreover, there is growing interest in the development of applications composed of a set of tasks carrying out different functions (i.e. with task parallelism) that coordinate one to each other through message transference at any point inside them.To model these applications that have an arbitrary task interaction pattern, we propose a new task graph model, called Temporal Task Interaction Graph (TTIG), that captures temporal information about parallel programs with a new parameter called degree of parallelism. This gives information about the potential concurrency that each pair of adjacent tasks can achieve, according to their mutual dependencies.From the definition of the application behaviour, a heuristic method is proposed to determine the theoretical maximum and minimum number of processors that are necessary to execute the application in the minimum time.Starting from the TTIG model, two new mapping algorithms are defined with different complexities, that carry out the allocation according to the ability of concurrency of tasks indicated by the degree of parallelism.In current message-passing environments PVM and MPI, the processor mapping mechanism is based on simply heuristics that take decisions independently of the relationship exhibited by tasks. Thus, these environments are enhanced by integrating an automatic mechanism to extract the TTIG for a given application, and to apply a mapping heuristic based on the model.

En esta tesis se ha abordado el problema de la determinación directa del régimen permanente de circuitos no lineales autónomos con parámetros distribuidos en el dominio temporal. Con la obtención de las ecuaciones de equilibrio en el dominio transformado de Laplace, es posible escribir directamente el sistema de ecuaciones discretizado en el dominio temporal, donde las incógnitas son el periodo de oscilación y las muestras de las variables de control. Así, toda variable genérica V(s) es transformada en un vector de muestras equiespaciadas de v(t), y cada uno de los operadores, derivada y retardo, en una matriz circulante. La formulación obtenida es tal que posibilita el posterior desarrollo analítico de la sensibilidad del sistema de ecuaciones discretizado respecto al periodo de oscilación y las muestras de las variables de control, permitiendo una eficaz resolución del sistema de ecuaciones utilizando métodos globalmente convergentes basados en modificaciones del método de Newton. Además, con el método de análisis propuesto, es posible reconvertir un problema de optimización en un problema de análisis y, en consecuencia, de menor complejidad. La utilización de los aproximantes de Padé multipunto, para aproximar una línea de transmisión RLCG con elementos de parámetros concentrados y una línea de transmisión ideal, permite extender el método propuesto a los circuitos que incorporan líneas RLCG.Una vez determinadas las soluciones en régimen permanente, el siguiente problema a abordar es el estudio de la estabilidad de estas soluciones, utilizándose los resultados de este estudio para detectar bifurcaciones de Hopf, de desdoblamiento de órbitas y puntos límite. En esta tesis se describe una técnica que permite seguir a) la rama que continua tras la aparición de un punto límite y b) la rama de periodo doble existente en una bifurcación de desdoblamiento de órbitas, como se comprueba sobre el circuito de Chua retardado (TDCC),Otra aportación de esta tesis, desarrollada íntegramente en el plano teórico, ha consistido en estrechar los lazos existentes entre el estudio de la estabilidad en el dominio temporal y el dominio frecuencial. El punto de partida se encuentra en la obtención de una transformación que permite trasladar cualquier formulación de análisis del dominio frecuencial al temporal y viceversa. La extensión de estos vínculos al estudio de la estabilidad deriva en la obtención de importantes resultados. Destaca, entre éstos, la obtención de la formulación de estabilidad utilizada por el método de balance armónico (HB), partiendo de un estudio de la estabilidad realizado en el dominio temporal. Estos resultados se complementan con los obtenidos por otros autores que, partiendo de una formulación en el dominio temporal con variables de estado, obtienen una formulación en el dominio frecuencial. Con la finalidad de no avanzar en el vacío, las ideas que aparecen en esta tesis han sido siempre contrastadas, en algunos casos por más de una vía. Así, el circuito de Van der Pol se analiza con el método de HB y con el método propuesto utilizando tres formulaciones distintas. El estudio de la estabilidad de los puntos de equilibrio del TDCC se contrasta con resultados analíticos. La determinación de las regiones de funcionamiento del circuito de Van der Pol excitado y la construcción de su curva solución se comparan con los resultados obtenidos usando HB. Los resultados de análisis del TDCC con línea RLCG son contrastados con los resultados obtenidos utilizando métodos de integración. Finalmente, se realiza una validación experimental del oscilador con línea de transmisión, sobre el cual se resuelve un problema de análisis y otro de optimización. / This thesis has tackled the problem of the direct determination of the steady state analysis of autonomous circuits with transmission lines and generic nonlinear elements. With the equilibrium equations obtained in the Laplace transformed domain, it is possible to directly write the discretized system of equations in the temporal domain where the unknowns to determine are the samples of the control variables, directly in the steady state, along with the oscillation period. Thus, every generic variable V(s) is converted into a vector of equally spaced samples of v(t) and each one of the operators, derivative and delay, into a circulant matrix. The formulation obtained is such that makes it possible the subsequent analytic development of the sensibility of the system of equations discretized with respect to the oscillation period and the samples of the control variables, allowing to solve the system of equations effectively using globally convergent techniques based on modifications of the Newton method. Moreover, with the analysis method suggested here, it is possible to turn a problem of optimization into a problem of analysis and, subsequently, of a lesser complexity. Besides, the use of the multipoint Padé approximants, to approximate an RLCG transmission line with lumped elements and an ideal transmission line, makes it possible to extend the suggested method to the circuits that include RLCG transmission lines.Once the steady state solutions have been determined, the next problem to deal with is the study of the stability of these solutions. The results of this study are used to detect Hopf bifurcations, period-doubling bifurcations and limit points. In this thesis a technique is described which allows us to follow a) the branch that follows after the appearance of a limit point and b) the branch of double period that exists in a period-doubling bifurcation point, as it can be proved in the time delayed Chua's circuit (TDCC).Another contribution of this thesis, totally developed at a theoretical level, has consisted in strengthening the existing bonds between the study of the stability both in the temporal and in the frequency domain. The starting point is a transformation that makes it possible to transfer any analysis formulation from the frequency domain to the temporal one and vice versa. The extension of these links to the study of the stability leads to important results. It stands out, among them, the obtained formulation of stability used by the harmonic balance (HB) method, starting from a stability study made in the temporal domain. These results complement each other with those obtained by other authors who, starting from a formulation in the temporal domain with state variables, obtain a formulation in the frequency domain. With the purpose of validating the ideas that appear in this thesis, these have always been contrasted, in some cases in more than one way. Thus, the Van der Pol oscillator is analyzed with the HB method and with the method suggested here using three different formulations. The study of the stability of the equilibrium points of the TDCC is contrasted with analytic results. The determination of the working regions of the excited Van der Pol oscillator and the construction of its solution curve is compared with the results obtained using HB. The results of the analysis of the TDCC with RLCG line are contrasted with those obtained using integration techniques. Finally, an experimental validation of an oscillator with transmission line is made, in which a problem of analysis and another one of optimization are solved.

Els mètodes de verificació formal s'estan usant cada vegada més en la indústria per establir la correctessa i trobar els errors en models de sistemes; per exemple la descripció de hardware, protocols, programes distribuïts, etc. En particular, els verificadors de models ho fan automàticament per sistemes d'estats finits, per-o estan limitats degut al problema de l'explosió d'estats; i la verificació formal interactiva, l'àrea d'aquesta tesi, es necessita.L'enfocament de la verificació automàtica treballa sobre el sistema de transicions del model, el qual defineix la seva semàntica. Aquest sistema de transicions té sovint molts estats, i sempre una mida gran comparada amb la mida del model del sistema, el qual és sempre infinit. Aquestes consideracions suggereixen un enfocament de verificació estàtica com els d'aquesta tesi, evitant els sistemes de transicions, treballant directament sobre el model del sistema, en principi, la complexitat computacional hauria de ser menor. L'enfocament estàtic d'aquest treball es fa sobre models de sistemes expressats en notació imperativa amb paral·lelisme explícit, sentències de comunicacions síncrones i variables d'emmagatzematge locals.Els raonaments d'equivalència són molt empleats per números, matrius i altres camps. Tanmateix, per programes imperatius amb paral·lelisme, comunicacions i variables, encara que potencialment sigui un mètode de verificació molt intuïtiu, no han estat massa explorats. La seqüencialització formal via l'eliminació de comunicacions internes, l'àrea d'aquesta tesi, és una demostració basada en el raonament estàtic d'equivalències que, donat que disminueix la magnitud del vector d'estats, pot complementar altres mètodes de demostració. Es basa en l'aplicació d'un conjunt de lleis , apropiades per tal propòsit, com reduccions de reescriptura del model del sistema. Aquestes depenen de la noció d'equivalència i de les suposicions de justícia.Aquesta tesi contribueix a la quasi inexplorada àrea de l'eliminació de comunicacions formal i seqüencialització de models de sistema. Les lleis estan definides sobre una equivalència feble: equivalència d'interfície. L'eliminació de comunicacions est-a limitada a models sense seleccions, per exemple models en els quals les comunicacions internes no estan dins de l'àmbit de sentències de selecció. Aplicacions interessants existeixen dins d'aquest marc. Les lleis són vàlides només per justícia feble o sense justícia. Aquesta ha estat desenvolupada seguint la semàntica proposada per Manna i Pnueli per a sistemes reactius [MP91, MP95]. S'han formulat les condicions d'aplicabilitat per les lleis de la pròpia eliminació de comunicacions. A més a més, es proposa un procediment de construcció de demostracions per l'eliminació de comunicacions, el qual intenta aplicar automàticament les lleis de la eliminació. També s'ha dissenyat un conjunt de procediments de transformació, els quals garanteixen que la transformació equivalent sempre correspon a l'aplicació d'una seqüència de lleis. Degut a que la construcció de les demostracions és impracticable, normalment impossible, sense l'ajuda d'una eina, s'ha desenvolupat un demostrador interactiu per la construcció semiautomàtica de la seqüencialització de models de sistemes i demostracions d'eliminació. Tant els procediments de transformació com els de l'eliminació de comunicacions estan integrats en l'eina. Amb l'ajuda del demostrador s'ha construït la demostració de seqüencialització d'un model, no trivial, de processador pipeline. Per aquest exemple s'ha assolit una reducció, respecte del model original, de la cota superior del nombre d'estats de 2−672.Malgrat l'enorme quantitat d'esforç dedicat a l'àrea, abans i durant la tesi, encara queda molt treball per a que l'eliminació de comunicacions i la seqüencialització sigui realment un mètode pràctic. No obstant els resultats d'aquesta tesi han establert els fonaments i han donat l'estímul necessari per continuar l'esforç. / Los métodos de verificación formal se están usando cada vez más en la industria para establecer la corrección y encontrar los errores en modelos de sistemas; por ejemplo, la descripción de hardware, protocolos, programas distribuidos, etc. En particular, los verificadores de modelos lo hacen automáticamente para sistemas de estados finitos, pero están limitados debido al problema de la explosión de estados; y la verificación formal interactiva, el área de esta tesis, es necesaria.El enfoque de la verificación automática trabaja sobre el sistema de transiciones del modelo, el cual define su semántica. Este sistema de transiciones tiene a menudo muchos estados, y siempre un tamaño grande comparado con el tamaño del modelo del sistema, el cual es siempre infinito. Estas consideraciones sugieren un enfoque de verificación estática como los de esta tesis, evitando los sistemas de transiciones, trabajando directamente sobre el modelo del sistema, en principio, la complejidad computacional tendría que ser menor. El enfoque estático de este trabajo se lleva a cabo sobre modelos de sistemas expresados en notación imperativa con paralelismo explícito, sentencias de comunicaciones síncronas y variables de almacenamiento locales.Los razonamientos de equivalencia son muy empleados para números, matrices y otros campos. Sin embargo, para programas imperativos con paralelismo, comunicaciones y variables, aún teniendo la potencialidad de ser un método de verificación muy intuitivo, no han sido muy explorados. La secuencialización formal vía la eliminación de comunicaciones internas, el área de esta tesis, es una demostración basada en el razonamiento estático de equivalencias que, ya que disminuye la magnitud del vector de estados, puede complementar otros métodos de demostración. Se basa en la aplicación de un conjunto de leyes, apropiadas para tal propósito, como reducciones de reescritura del modelo del sistema. Éstas dependen de la noción de equivalencia y de las suposiciones de justicia.Esta tesis contribuye a la casi inexplorada área de la eliminación de comunicaciones formal y secuencialización de modelos de sistema. Las leyes están definidas sobre una equivalencia débil: equivalencia de interfaz. La eliminación de comunicaciones está limitada a modelos sin selecciones, por ejemplo modelos en los cuales las comunicaciones internas no están dentro del ámbito de sentencias de selección. Aplicaciones interesantes existen dentro de este marco. Las leyes son válidas sólo para justicia débil o sin justicia. Ésta ha sido desarrollada siguiendo la semántica propuesta por Manna y Pnueli para sistemas reactivos [MP91, MP95]. Se han formulado las condiciones de aplicabilidad para las leyes de la propia eliminación de comunicaciones. Además, se propone un procedimiento de construcción de demostraciones para la eliminación de comunicaciones, el cual intenta aplicar automáticamente las leyes de la eliminación. También se ha diseñado un conjunto de procedimientos de transformación, los cuales garantizan que la transformación equivalente siempre corresponde a la aplicación de una secuencia de leyes. Debido a que la construcción de las demostraciones es impracticable, normalmente imposible, sin la ayuda de una herramienta, se ha desarrollado un demostrador interactivo para la construcción semiautomática de la secuencialización de modelos de sistemas y demostraciones de eliminación. Tanto los procedimientos de transformación como los de la eliminación de comunicaciones están integrados en la herramienta. Con la ayuda del demostrador se ha construido la demostración de secuencialización de un modelo, no trivial, de procesador pipeline. Para este ejemplo se ha logrado una reducción, respecto del modelo original, de la cota superior del número de estados de 2−672.A pesar de la enorme cantidad de esfuerzo dedicado al área, antes y durante esta tesis, todavía queda mucho trabajo para que la eliminación de comunicaciones y la secuencialización sea realmente un método práctico. Sin embargo los resultados de esta tesis han establecido los cimientos y han dado el estímulo necesario para continuar el esfuerzo. / Formal verification methods are increasingly being used in industry to establish the correctness of, and to find the flaws in, system models; for instance, descriptions of hardware, protocols, distributed programs, etc. In particular, model checking does that automatically for finite-state systems, but it is limited in scope due to the state explosion problem; and interactive formal verification, the broad area of this thesis, is needed.Automatic verification approaches work on the transition system of the model, which defines its semantics. This transition system has often infinitely many states, and always a large size compared to the size of the system model, which is always finite. These considerations suggest that static verification approaches such as those of this thesis, avoiding the transition system, working directly on the system model would have less computational complexity, in principle. The static approach of this work is carried out on system models expressed in imperative notations with explicit parallelism and synchronous communication statements, and with local storage variables.Equivalence reasoning is heavily used for numbers, matrices, and other fields. However, for imperative programs with parallelism, communications, and variables, although having the potentiality of being a very intuitive verification method, it has not been much explored. Formal sequentialization via internal communication elimination, the area of this thesis, is a static equivalence reasoning proof that, since it decreases the size of the state vector, could complement other proof methods. It is based on the application of a set of laws, suitable for that purpose, as rewriting reductions to a system model. These proofs need both proper communication elimination laws and auxiliary basic laws. These depend on the notion of equivalence and on the fairness assumptions.This thesis contributes to the almost unexplored area of formal communication elimination and system model sequentialization. The laws are defined over a weak equivalence: interface equivalence. Communication elimination is confined to selection-free models, i.e. models none of whose inner communications are within the scope of selection statements. Interesting applications already exist within this framework. The laws are valid only with weak fairness or no fairness. It has been developed following the same semantics as Manna and Pnueli for reactive systems [MP91, MP95]. Applicability conditions for the proper communication elimination laws are derived. In addition, a communication elimination proof construction procedure, which attempts to apply the elimination laws automatically is proposed. A set of transformation procedures, guaranteeing that the equivalence transformation always corresponds to the application of a sequence of laws have been designed as well. Since the construction of elimination proofs is impractical, even impossible, without a tool, an interactive prover for semi-automatic construction of system model sequentialization and elimination proofs has been developed. Both transformation and communication elimination procedures are integrated within the tool. As a non-trivial example, a sequentialization proof of a pipelined processor model, has been constructed with the help of the prover. Areduction, with respect to the original model, of 2−672 on the upper bound on the number of states has been achieved in this example.In spite of the huge amount of effort already devoted to the area, before and during this thesis, much work still needs to be done until communication elimination and sequentialization become a practical method. Nevertheless the results of this thesis have established its foundations and given the necessary encouragement for continuing the effort.

In the last decades, significant theoretical advances have been made on the field of distributed mulit-agent control theory. One of the most common systems that can be modelled as multi-agent systems are the so called formation control problems, in which a network of mobile agents is controlled to move towards a desired final formation. These problems additionally pose practical challenges, namely limited access to information about the global state of the system, which justify the use distributed and localized approaches for solving the control problem. The problem is further complicated if partial or no information is known about the dynamic model of the system. A widely used fundamental challenge of this approach in this setting is that the state-action space size scales exponentially with the number of agents, rendering the problem intractable for a large networks. This thesis presents a scalable and localized reinforcement learning approach to a traditional multi-agent formation control problem, with collision avoidance. A scalable reinforcement learning advantage actor critic algorithm is presented, based on previous work in the literature. Sub-optimal bounds are calculated for the accumulated reward and policy gradient localized approximations. The algorithm is tested on a two dimensional setting, with a network of mobile agents following simple integrator dynamics and stochastic localized policies. Neural networks are used to approximate the continuous value functions and policies. The formation control with collisions avoidance formulation and the algorithm presented show good scalability properties, with a polynomial increase in the number of function approximations parameters with number of agents. The reduced number of parameters decreases learning time for bigger networks, although the efficiency of computation is decreased compared to state of the art machine learning implementations. The policies obtained achieve probably safe trajectories although the lack of dynamic model makes it impossible to guarantee safety. / Under de senaste decennierna har betydande framsteg gjorts inom området för distribuerad mulit-agent reglerteori. Ett av de vanligaste systemen som kan modelleras som multiagentsystem är de så kallade formationskontrollproblemen, där ett nätverk av mobila agenter styrs för att röra sig mot en önskad slutlig formation. om systemets globala tillstånd, vilket motiverar användningen av distribuerade och lokaliserade tillvägagångssätt för att lösa det reglertekniska problemet. Problemet kompliceras ytterligare om delvis eller ingen information är känd om systemets dynamiska modell. Ett allmänt använt tillvägagångssätt för modellfri kontroll är reinforcement learning (RL). En grundläggande utmaning med detta tillvägagångssätt i den här miljön är att storleken på state-action utrymmet skalas exponentiellt med antalet agenter, vilket gör problemet svårlöst för ett stort nätverk. Detta examensarbete presenterar en skalbar och lokaliserad reinforcement learning metod på ett traditionellt reglertekniskt problem med flera agenter, med kollisionsundvikande. En reinforcement learning advantage actor critic algoritm presenteras, baserad på tidigare arbete i litteraturen. Suboptimala gränser beräknas för den ackumulerade belönings- och policygradientens lokaliserade approximationer. Algoritmen testas i en tvådimensionell miljö, med ett nätverk av mobila agenter som följer enkel integratordynamik och stokastiska lokaliserade policyer. Neurala nätverk används för att approximera de kontinuerliga värdefunktionerna och policyerna. Den presenterade formationsstyrningen med kollisionsundvikande formulering och algoritmen visar goda skalbarhetsegenskaper, med en polynomisk ökning av antalet funktionsapproximationsparametrar med antalet agenter. Det minskade antalet parametrar minskar inlärningstiden för större nätverk, även om effektiviteten i beräkningen minskar jämfört med avancerade maskininlärningsimplementeringar. De erhållna policyerna uppnår troligen säkra banor även om avsaknaden av dynamisk modell gör det omöjligt att garantera säkerheten. / En las últimas décadas, se han realizado importantes avances teóricos en el campo de la teoría del control multiagente distribuido. Uno de los sistemas más comunes que se pueden modelar como sistemas multiagente son los llamados problemas de control de formación, en los que se controla una red de agentes móviles para alcanzar una formación final deseada. Estos problemas plantean desafíos prácticos como el acceso limitado a la información del estado global del sistema, que justifican el uso de algoritmos distribuidos y locales para resolver el problema de control. El problema se complica aún más si solo se conoce información parcial o nada sobre el modelo dinámico del sistema. Un enfoque ampliamente utilizado para el control sin conocimiento del modelo dinámico es el reinforcement learning (RL). Un desafío fundamental de este método en este entorno es que el tamaño de la acción y el estado aumenta exponencialmente con la cantidad de agentes, lo que hace que el problema sea intratable para una red grande. Esta tesis presenta un algoritmo de RL escalable y local para un problema tradicional de control de formación con múltiples agentes, con prevención de colisiones. Se presenta un algoritmo “advantage actor-”critic, basado en trabajos previos en la literatura. Los límites subóptimos se calculan para las aproximaciones locales de la función Q y gradiente de la política. El algoritmo se prueba en un entorno bidimensional, con una red de agentes móviles que siguen una dinámica de integrador simple y políticas estocásticas localizadas. Redes neuronales se utilizan para aproximar las funciones y políticas de valor continuo. La formulación de del problema de formación con prevención de colisiones y el algoritmo presentado muestran buenas propiedades de escalabilidad, con un aumento polinómico en el número de parámetros con el número de agentes. El número reducido de parámetros disminuye el tiempo de aprendizaje para redes más grandes, aunque la eficiencia de la computación disminuye en comparación con las implementaciones de ML de última generación. Las politicas obtenidas alcanzan trayectorias probablemente seguras, aunque la falta de un modelo dinámico hace imposible garantizar la completa prevención de colisiones. / A les darreres dècades, s'han realitzat importants avenços teòrics en el camp de la teoria del control multiagent distribuït. Un dels sistemes més comuns que es poden modelar com a sistemes multiagent són els anomenats problemes de control de formació, en els què es controla una xarxa d'agents mòbils per assolir una formació final desitjada. Aquests problemes plantegen reptes pràctics com l'accés limitat a la informació de l'estat global del sistema, que justifiquen l'ús d'algorismes distribuïts i locals per resoldre el problema de control. El problema es complica encara més si només es coneix informació parcial sobre el model dinàmic del sistema. Un mètode àmpliament utilitzat per al control sense coneixement del model dinàmic és el reinforcement learning (RL). Un repte fonamental d'aquest mètode en aquest entorn és que la mida de l'acció i l'estat augmenta exponencialment amb la quantitat d'agents, cosa que fa que el problema sigui intractable per a una xarxa gran. Aquesta tesi presenta un algorisme de RL escalable i local per a un problema tradicional de control de formació amb múltiples agents, amb prevenció de col·lisions. Es presenta un algorisme “advantage actor-”critic, basat en treballs previs a la literatura. Els límits subòptims es calculen per a les aproximacions locals de la funció Q i gradient de la política.’ Lalgoritme es prova en un entorn bidimensional, amb una xarxa ’dagents mòbils que segueixen una dinàmica ’dintegrador simple i polítiques estocàstiques localitzades. Xarxes neuronals s'utilitzen per aproximar les funcions i les polítiques de valor continu. La formulació del problema de formació amb prevenció de col·lisions i l'algorisme presentat mostren bones propietats d'escalabilitat, amb un augment polinòmic en el nombre de paràmetres amb el nombre d'agents. El nombre reduït de paràmetres disminueix el temps d'aprenentatge per a les xarxes més grans, encara que l'eficiència de la computació disminueix en comparació amb les implementacions de ML d'última generació. Les polítiques obtingudes aconsegueixen trajectòries probablement segures, tot i que la manca d'un model dinàmic fa impossible garantir la prevenció completa de col·lisions.