Multi-robot sensor networks for thermosolar power plants

Abstract

Esta tesis, enmarcada dentro del proyecto OCONTSOLAR, aborda la gestión de una flota de robots heterogénea, compuesta tanto por robots aéreos como terrestres (UAVs y UGVs respectivamente por sus siglas en inglés), con el objetivo de obtener un mapa estimado de irradiación solar a lo largo y ancho de una planta termosolar. En la primera parte de esta tesis nos centramos en afrontar el problema de la asignación de tareas en sistemas multirobot (MRTA por sus siglas en inglés) en el contexto de una planta termosolar, que se caracteriza generalmente, además de por sus grandes dimensiones, por constituir un entorno estructurado con obstáculos conocidos. Para ello, se asume que una capa superior es capaz de generar tareas consistentes en ir a un determinado punto de la planta y tomar una medición, y que dichas tareas deberían ser asignadas a los robots sólo en función de su posición y diversas variables como su nivel de energía. También se asume la posible imposición de una penalización arbitraria a cada robot en función de si queremos utilizarlo más o menos, lo que tiene sentido si consideramos que las tareas pueden tener distintas urgencias y duraciones y queremos reservar los UAVs para misiones más relevantes y urgentes. Para resolver el MRTA atendiendo a un equilibrio entre la distancia recorrida por los robots (y por tanto la energía que gastan) y el tiempo necesario para realizar las tareas, se han desarrollado varios algoritmos. En primer lugar, un algoritmo de subastas donde se ha introducido un postor extra que puja por dejar las tareas sin asignar en función del tiempo que lleven en espera. Este nuevo postor se resiste inicialmente a dejar las tareas sin asignar a no ser que éstas ya lleven mucho tiempo en espera, y únicamente las libera pronto si hay un robot relativamente cercano a las mismas. Sin embargo, tratar de enfrentar los antes citados objetivos con estrategias de asignación instantánea resulta ser una estrategia muy limitada, y por eso proponemos unas variables discretas para describir la asignación extendida en el tiempo y desarrollamos un algoritmo de ramificación y poda y un algoritmo genético adaptados a dichas variables. En cualquier caso, el algoritmo de ramificación y poda sólo es viable ante problemas con poca cantidad de robots y tareas, y el algoritmo genético, aunque es capaz de abordar problemas algo más grandes dada su naturaleza metaheurística, tampoco resulta eficaz con problemas demasiado grandes. Con el objetivo de dividir estos grandes problemas en pequeños problemas en los que aplicar alguno de los algoritmos antes comentados, no atendiendo únicamente a la distancia entre robots y tareas, sino también a sus parámetros intrínsecos, proponemos un algoritmo basado en teoría de juegos cooperativos y más concretamente en el valor de Shapley. Este algoritmo se basa en estimar el valor de Shapley, tanto de los robots como de las tareas y luego crear coaliciones que tengan un valor de Shapley agregado equilibrado. Por último, para tratar con grandes problemas también se ha propuesto una serie de asunciones para convertirlo en un problema de programación lineal (LP por sus siglas en inglés). La ventaja de los problemas LP es que se pueden resolver de una forma mucho más rápida, por lo que se puede resolver iterativamente. Por este motivo, se ha aplicado a problemas dinámicos con tareas en movimiento utilizando una estrategia basada en el control predictivo con horizonte deslizante, es decir, recalculando el problema en cada tiempo de control y aplicando la primera de las asignaciones. En la segunda parte de esta tesis nos centramos en la estimación del mapa de irradiación solar. Para ello, partimos de la inferencia bayesiana, asumiendo que en cada punto de la planta termosolar tenemos una distribución de probabilidad de la irradiación y que esta distribución puede ser modificada por nuevas medidas cercanas. Además, se consideramos que la distribución tiene una tendencia natural a recuperar la forma de la distribución uniforme, es decir, total incertidumbre. De esta forma, aplicando un filtro que hace uso de dos parámetros que se pueden obtener de la distribución de probabilidad, en concreto del valor esperado y de la entropía de la información de Shannon, se puede obtener el mapa estimado de irradiación. Es más, a partir del valor esperado o de la entropía de Shannon, se pueden obtener distintas capas que representen el interés que tiene visitar cada punto de la planta desde el punto de vista de la irradiación que tenemos en un instante y de la certidumbre que tenemos a lo largo y ancho de la planta. Por lo tanto, superponiendo estas capas, y otras que podemos crear para modificar el resultado (como una capa que de más valor a los puntos por los que pueden aparecer nuevas sombras), y asignando un peso a cada una, podemos generar nuevas tareas para nuestra flota de robots. Por último, también con el objetivo de obtener una estimación distribuida de la irradiación solar, se propone una malla de pirheliómetros de bajo coste utilizando la técnica del krigeage espacio- temporal, ampliamente utilizada en la literatura en otras variables ambientales. Esta técnica hace uso de un variograma espacio-temporal para asignar distintos pesos a las medidas cercanas a un punto donde se quiere hacer una estimación. La principal contribución de este trabajo consiste en proponer un variograma espacio-temporal dinámico y anisotrópico en la dirección del viento. Bajo esta premisa, una medida en la dirección de la que proviene el viento es más relevante si fue tomada en un cierto momento, aunque este efecto se atenúa con el tiempo. El siguiente paso es unir los dos trabajos realizados en torno a la creación de un mapa estimado de irradiación, puesto que utilizando el krigeage espacio-temporal también podemos obtener un mapa de incertidumbre, y por tanto se puede emular la estrategia basada en capas para generar nuevas tareas.

This thesis, in the framework of the OCONTSOLAR project, deals with the management of a heterogeneous robot fleet, composed of aerial and ground robots (UAVs and UGVs respectively), with the aim of obtaining an estimated solar irradiance map across the whole extent of a solar thermal power plant. In the first part of this thesis we focus on addressing the multi-robot task allocation (MRTA) problem in the context of a solar thermal power plant, which is generally characterized, in addition to its large size, by a structured environment with known obstacles. For this purpose, it is assumed that an upper layer is able to generate tasks consisting of going to a certain point of the plant and taking a measurement, and that these tasks should be allocated to the robots only according to their position and various variables such as their energy level. The possible application of an arbitrary penalty to each robot depending on whether we want to use it more or less is also assumed, which makes sense if we consider that tasks may have different urgencies and durations and we want to reserve UAVs for more relevant and urgent missions. To solve the MRTA attending to both the distance traveled by the robots (and therefore the energy they spent) and the time required to perform the tasks, several algorithms are developed. First, an auction algorithm with an extra bidder who bids to leave the tasks unallocated based on the time they have been queued. This new bidder is initially reluctant to leave tasks unallocated unless they have already been active for a long time, and only allocates them promptly if there is a robot relatively close to the task. However, trying to address the above objectives with a instantaneous assignment approach is a very limited strategy, and therefore we propose discrete variables to describe the time-extended assignment and develop a branch and bound algorithm and a genetic algorithm adapted to these variables. In any case, the branch and bound algorithm is only feasible for problems with a small number of robots and tasks, and the genetic algorithm, although capable of addressing larger problems given its metaheuristic nature, is also ineffective with very large problems. In order to divide these large problems into small problems where to apply some of the above mentioned algorithms, not only attending to the distance between robots and tasks, but also to their intrinsic parameters, we propose an algorithm based on cooperative game theory and more specifically on the Shapley value. This algorithm is based on estimating the Shapley value of both robots and tasks and then creating coalitions that have a balanced aggregate Shapley value. Finally, to deal with large problems, some assumptions have also been proposed in order to convert the problem into a linear programming (LP) problem. The advantage of LP problems is that they can be solved much faster. Thus, they can be solved iteratively. For this reason, it has been applied to dynamic problems with moving tasks using a strategy based on predictive control with sliding horizon, i.e., recalculating the problem at each control time and applying the first of the assignments. In the second part of this thesis we focus on the estimation of the solar irradiance map. For that, we start from Bayesian inference, assuming that at each point of the solar thermal plant we have a probability distribution of the irradiance and that this distribution can be modified by new measurements nearby. Furthermore, we consider that the distribution has a natural tendency to recover the shape of the uniform distribution, i.e., total uncertainty. Thus, by applying a filter that makes use of two parameters that can be obtained from the probability distribution, namely the expected value and the Shannon information entropy, the estimated irradiance map can be obtained. Moreover, from the expected value or the Shannon entropy, different layers can be obtained that represent the interest of visiting each point of the plant from the point of view of the irradiance that we have at an instant and the certainty that we have throughout the plant. Therefore, by superimposing these layers, and others that we can create to modify the result (such as a layer that gives more value to the points where new shadows may appear), and assigning a weight to each one, we can generate new tasks for our fleet of robots. Finally, also with the objective of obtaining a distributed estimation of solar irradiance, a low-cost pyrheliometer grid is proposed using the spatio-temporal kriging technique, widely used in the literature for other environmental variables. This technique makes use of a spatio-temporal variogram to assign different weights to the measurements near a point where an estimate is to be made. The main contribution of this work consists of proposing a dynamic and anisotropic spatio- temporal variogram in the wind direction. Under this premise, a measurement in the direction from which the wind comes is more relevant if it was taken at a certain moment, although this effect attenuates with time. The next step is to merge the two works done around the creation of an estimated irradiance map, since using the spatio-temporal kriging we can also obtain an uncertainty map, and therefore the layer-based strategy can be emulated to generate new tasks.