Aceleración de algoritmos intervalares de ajuste automático del lazo en QFT

Abstract

En este trabajo se aborda la aceleración de algoritmos del tipo búsqueda global intervalar que tienen por objetivo la resolución, de forma automática, del problema del ajuste del lazo en QFT. Esta técnica de diseño de controladores robustos en el dominio de la frecuencia se plantea como una sucesión de etapas. En cada una de ellas se genera la información necesaria para la siguiente, culminando todo este proceso en la fase más importante, el ajuste del lazo, donde se genera el controlador.

Disponer de algoritmos que puedan resolver de forma automática, sin intervención del usuario, el ajuste del lazo en QFT no es una tarea sencilla. Dado que constituye un problema de optimización no lineal y no convexo, las soluciones algorítmicas que se le pueden aplicar tienen dificultades inherentes de difícil solución.

A lo largo de la historia se han planteado diferentes propuestas para dar respuesta a esta necesidad, pero hasta ahora no se ha conseguido ninguna solución satisfactoria. Dada la complejidad del proceso, se ha afrontado el problema desde diversas ópticas. Una aproximación interesante son los algoritmos de búsqueda global intervalar. Este tipo de propuestas buscan asegurar el óptimo en la solución utilizando aritmética intervalar, pero tienen la problemática de que, al ser una búsqueda global, tienen un coste computacional muy alto, y con ello, lleva a una curva exponencial del tiempo de ejecución conforme el tamaño del problema aumenta.\

Este trabajo se ha centrado en analizar con detenimiento los algoritmos de este tipo, focalizando el esfuerzo en comprender donde existen más posibilidades de mejora. Una vez concluida esta tarea, se ha trabajado en el planteamiento de alternativas que mejoren las propuestas existentes, culminando en una serie de novedosas estrategias que tienen por objetivo reducir el coste computacional y el tiempo de ejecución.

Un primer grupo de estrategias tienen la finalidad de acotar el espacio de búsqueda del algoritmo, y su objetivo es detectar tanto el subrango viable como inviable de cada una de las variables del controlador, utilizando la fase y la magnitud en el plano de Nichols. De esta forma, por un lado se consigue eliminar los subrangos identificados como inviables, y por otro lado, encontrar soluciones en el subrango viable. Dentro de este mismo grupo, se plantea una estrategia que busca encontrar soluciones al problema de forma rápida, su funcionamiento es similar a las acotaciones descritas, pero tiene la capacidad de encontrar mejores soluciones, que podrán ser utilizadas para realizar podas en nodos poco prometedores.

Un segundo grupo tienen un carácter más transversal. La primera de ellas contiene varias opciones para realizar la bisección del nodo. Como opción principal se propone una bisección avanzada que utiliza la información generada del nodo actual para tomar la mejor decisión posible. Complementado a ésta, se plantean tres opciones más básicas, realizar la bisección por la variable que más influye en el área, por la que más influye en la magnitud o por la que más influye en la fase, todas ellas en el plano de Nichols, según convenga en cada momento. A continuación, se plantea una segunda estrategia que está centrada en adaptar el funcionamiento del algoritmo a la situación en la que se encuentre a lo largo de su ejecución, es decir, modifica el comportamiento del resto de estrategias y las adapta a las circunstancias concretas del algoritmo en ese momento consiguiendo, de esta forma, mejorar las prestaciones de todas las estrategias desarrolladas.

Para terminar, esta tesis propone un nuevo algoritmo de ajuste automático del lazo en QFT del tipo búsqueda global intervalar que engloba todas estas estrategias propuestas. Dicho algoritmo logra reducir el coste computacional de manera importante con respecto a las soluciones previas y, de esta forma, consigue una mejora en el tiempo de ejecución de dos órdenes de magnitud para controladores típicos.

This paper deals with the acceleration of interval analysis global search algorithms whose goal is to automatically solve the loop shaping problem in QFT. This design technique for robust controllers in the frequency domain is proposed as a succession of stages. Each step generates information for the following stage. The last stage, the most important one, is the loop shaping, where the controller is generated. Having algorithms which can automatically (without user intervention) solve the QFT loop shaping problem isn't an easy task. Given that it's a non-linear and non-convex optimization problem, the algorithmic solutions that can be applied pose several difficulties. Throughout time, different proposals have been made to solve the problem but, until now, no satisfactory solutions has been achieved. Given the complexity of the process, the problem has been faced from various perspectives. An interesting approach is interval global search algorithms. This type of proposals try to ensure an optimum solution using interval arithmetic, but they have the problem that, being a global search, they have a very high computational cost, and because of that, an exponential curve of the execution time grows exponentially with the size of the problem. This work has focused on carefully analyzing this kind of algorithms and the effort has been centered on understanding where more possibilities for improvement were. Once this task has been completed, the work has been focused on the proposal of alternatives that improve the existing algorithms and it culminates in a series of novel strategies that aim to reduce the computational cost and the execution time. A first group of strategies has the purpose of delimiting the algorithm's search space and its objective is to detect both the feasible and unfeasible subrange of each controller's variable, using the phase and magnitude in the Nichols plane. In this way, on the one hand, it's possible to eliminate the subranges identified as unfeasible, and on the other hand, to find solutions in the viable subrange. Within this same group, it's proposed a strategy which seeks to quickly find solutions to the problem and whose performance is similar to the bounding described although it has the ability to find better solutions, which can be used to prune unpromising nodes. A second group has a more transversal disposition. The first one contains several options to perform the bisection of the node. As a main option, the proposal is an advanced bisection which uses the information generated from the current node to make the best decision. Three more basic options are proposed to complement the previous one, to carry out the bisection by the most influential variable on the area, by the most influential one on the magnitude or by the most influential one on the phase, all of them in the Nichols plane, as appropiate depending on each moment’s conditions. Following, it's proposed a second strategy that aims to adapt the algorithm behaviour to every situation along the execution, in other words, it modifies the behavior of the rest of strategies and adapts them to each specific circumstance of the algorithm at any time. Thereby it improves the performance of every developed strategies. Finally, this thesis proposes a new interval global search QFT Automatic Loop Shaping algorithm which involves all these strategies. This algorithm achieves a significant reduction of the computational cost with respect to previous solutions and, in this way, it achieves a two orders of magnitude improvement in execution time for typical controllers.