Usando la descomposición de un grafo Halin para el diseño de algoritmos autoestabilizantes

Using Halin graph decomposition for the design of self-stabilizing algorithm

Daniel Uriel Orozco Lomelí (2023, [Tesis de maestría])

Sea G = (V, E) un grafo no dirigido. El problema de encontrar un conjunto independiente fuerte en G, es identificar un conjunto S ⊆ V , tal que dados dos vértices arbitrarios de S, éstos estén separados entre sí por el menos tres aristas. Encontrar un conjunto S de tamaño máximo pertenece a la clase NP-Difícil. Por otro lado, el problema de encontrar un conjunto dominante total en G es identificar un conjunto D ⊆ V , tal que cualquier vértice en V tenga al menos un vecino que pertenezca a D. Encontrar un conjunto D de tamaño mínimo también pertenece a la clase NP-Difícil. En este trabajo de tesis se diseñaron dos algoritmos, uno que resuelve el problema de encontrar un conjunto independiente fuerte maximal y otro que resuelve el problema de encontrar un conjunto dominante total minimal. Estos dos problemas son menos restrictivos que las versiones de optimización descritas al principio de este texto y se sabe que pertenecen a la clase P. Los algoritmos diseñados corren en un sistema distribuido, son autoestabilizantes, son tolerantes a fallas transitorias y funcionan para grafos Halin. Los grafos Halin pertenecen a la clase de grafos 2-outerplanares y tienen la propiedad de que se pueden partir en dos subgrafos muy conocidos, un árbol y un ciclo. Los algoritmos propuestos aprovechan la propiedad anterior para disminuir la complejidad de los mismos. Hasta donde tenemos conocimiento, los algoritmos propuestos, que corren en tiempo lineal en el número de vértices, son los algoritmos más rápidos existentes para los problemas del conjunto independiente fuerte maximal y el conjunto dominante total minimal.

Let G = (V, E) be an undirected graph. The problem of finding a strong stable set in G, is to identify a set S ⊆ V , such that given two arbitrary vertices of S, they are separated from each other by at least three edges. Finding a set S of maximum size belongs to the class NP-Hard. On the other hand, the problem of finding a total dominanting set in G is to identify a set D ⊆ V , such that any vertex in V has at least one neighbor belonging to D. Finding a set D of minimum size also belongs to the class NP-Hard. In this thesis work, two algorithms were designed, one that solves the problem of finding a maximal strong stable set and one that solves the problem of finding a minimal total dominanting set. These two problems are less restrictive than the optimization versions described at the beginning of this text and are known to belong to the P class. The designed algorithms run on a distributed system, are self-stabilizing, are transient fault tolerant, and work for Halin graphs. Halin graphs belong to the 2-outerplanar class of graphs and have the property that they can be split into two well-known subgraphs, a tree and a cycle. The proposed algorithms take advantage of the above property to decrease the complexity of the algorithms. To the best of our knowledge, the proposed algorithms, which run in linear time in the number of vertices, are the fastest existing algorithms for the maximal strong stable set and minimal total dominating set problems.

Grafo Halin, Sistemas Distribuidos, Autoestabilización, Conjunto Independiente Fuerte, Conjunto Dominante Total Halin Graph, Distributed Systems, Self-stabilizing, Strong Stable Set, Total Dominating Set INGENIERÍA Y TECNOLOGÍA CIENCIAS TECNOLÓGICAS TECNOLOGÍA DE LOS ORDENADORES LENGUAJES ALGORÍTMICOS LENGUAJES ALGORÍTMICOS

Control de sistemas usando aprendizaje de máquina

Systems control using machine learning

Jesús Martín Miguel Martínez (2023, [Tesis de maestría])

El aprendizaje por refuerzo es un paradigma del aprendizaje de máquina con un amplio desarrollo y una creciente demanda en aplicaciones que involucran toma de decisiones y control. Es un paradigma que permite el diseño de controladores que no dependen directamente del modelo que describe la dinámica del sistema. Esto es importante ya que en aplicaciones reales es frecuente que no se disponga de dichos modelos de manera precisa. Esta tesis tiene como objetivo implementar un controlador óptimo en tiempo discreto libre de modelo. La metodología elegida se basa en algoritmos de aprendizaje por refuerzo, enfocados en sistemas con espacios de estado y acción continuos a través de modelos discretos. Se utiliza el concepto de función de valor (Q-función y función V ) y la ecuación de Bellman para resolver el problema del regulador cuadrático lineal para un sistema mecánico masa-resorte-amortiguador, en casos donde se tiene conocimiento parcial y desconocimiento total del modelo. Para ambos casos las funciones de valor son definidas explícitamente por la estructura de un aproximador paramétrico, donde el vector de pesos del aproximador es sintonizado a través de un proceso iterativo de estimación de parámetros. Cuando se tiene conocimiento parcial de la dinámica se usa el método de aprendizaje por diferencias temporales en un entrenamiento episódico, que utiliza el esquema de mínimos cuadrados con mínimos cuadrados recursivos en la sintonización del crítico y descenso del gradiente en la sintonización del actor, el mejor resultado para este esquema es usando el algoritmo de iteración de valor para la solución de la ecuación de Bellman, con un resultado significativo en términos de precisión en comparación a los valores óptimos (función DLQR). Cuando se tiene desconocimiento de la dinámica se usa el algoritmo Q-learning en entrenamiento continuo, con el esquema de mínimos cuadrados con mínimos cuadrados recursivos y el esquema de mínimos cuadrados con descenso del gradiente. Ambos esquemas usan el algoritmo de iteración de política para la solución de la ecuación de Bellman, y se obtienen resultados de aproximadamente 0.001 en la medición del error cuadrático medio. Se realiza una prueba de adaptabilidad considerando variaciones que puedan suceder en los parámetros de la planta, siendo el esquema de mínimos cuadrados con mínimos cuadrados recursivos el que tiene los mejores resultados, reduciendo significativamente ...

Reinforcement learning is a machine learning paradigm with extensive development and growing demand in decision-making and control applications. This technique allows the design of controllers that do not directly depend on the model describing the system dynamics. It is useful in real-world applications, where accurate models are often unavailable. The objective of this work is to implement a modelfree discrete-time optimal controller. Through discrete models, we implemented reinforcement learning algorithms focused on systems with continuous state and action spaces. The concepts of value-function, Q-function, V -function, and the Bellman equation are employed to solve the linear quadratic regulator problem for a mass-spring-damper system in a partially known and utterly unknown model. For both cases, the value functions are explicitly defined by a parametric approximator’s structure, where the weight vector is tuned through an iterative parameter estimation process. When partial knowledge of the dynamics is available, the temporal difference learning method is used under episodic training, utilizing the least squares with a recursive least squares scheme for tuning the critic and gradient descent for the actor´s tuning. The best result for this scheme is achieved using the value iteration algorithm for solving the Bellman equation, yielding significant improvements in approximating the optimal values (DLQR function). When the dynamics are entirely unknown, the Q-learning algorithm is employed in continuous training, employing the least squares with recursive least squares and the gradient descent schemes. Both schemes use the policy iteration algorithm to solve the Bellman equation, and the system’s response using the obtained values was compared to the one using the theoretical optimal values, yielding approximately zero mean squared error between them. An adaptability test is conducted considering variations that may occur in plant parameters, with the least squares with recursive least squares scheme yielding the best results, significantly reducing the number of iterations required for convergence to optimal values.

aprendizaje por refuerzo, control óptimo, control adaptativo, sistemas mecánicos, libre de modelo, dinámica totalmente desconocida, aproximación paramétrica, Q-learning, iteración de política reinforcement learning, optimal control, adaptive control, mechanical systems, modelfree, utterly unknown dynamics, parametric approximation, Q-learning, policy iteration INGENIERÍA Y TECNOLOGÍA CIENCIAS TECNOLÓGICAS TECNOLOGÍA DE LOS ORDENADORES INTELIGENCIA ARTIFICIAL INTELIGENCIA ARTIFICIAL