Response threshold models, stochastic learning automata and ant colony optimization-based decentralized self-coordination algorithms for heterogeneous multi-tasks distribution in multi-robot systems

In recent decades, there has been an increasing interest in systems comprised of several autonomous mobile robots, and as a result, there has been a substantial amount of development in the eld of Articial Intelligence, especially in Robotics. There are several studies in the literature by some researchers from the scientic community that focus on the creation of intelligent machines and devices capable to imitate the functions and movements of living beings. Multi-Robot Systems (MRS) can often deal with tasks that are dicult, if not impossible, to be accomplished by a single robot. In the context of MRS, one of the main challenges is the need to control, coordinate and synchronize the operation of multiple robots to perform a specic task. This requires the development of new strategies and methods which allow us to obtain the desired system behavior in a formal and concise way. This PhD thesis aims to study the coordination of multi-robot systems, in particular, addresses the problem of the distribution of heterogeneous multi-tasks. The main interest in these systems is to understand how from simple rules inspired by the division of labor in social insects, a group of robots can perform tasks in an organized and coordinated way. We are mainly interested on truly distributed or decentralized solutions in which the robots themselves, autonomously and in an individual manner, select a particular task so that all tasks are optimally distributed. In general, to perform the multi-tasks distribution among a team of robots, they have to synchronize their actions and exchange information. Under this approach we can speak of multi-tasks selection instead of multi-tasks assignment, which means, that the agents or robots select the tasks instead of being assigned a task by a central controller. The key element in these algorithms is the estimation ix of the stimuli and the adaptive update of the thresholds. This means that each robot performs this estimate locally depending on the load or the number of pending tasks to be performed. In addition, it is very interesting the evaluation of the results in function in each approach, comparing the results obtained by the introducing noise in the number of pending loads, with the purpose of simulate the robot's error in estimating the real number of pending tasks. The main contribution of this thesis can be found in the approach based on self-organization and division of labor in social insects. An experimental scenario for the coordination problem among multiple robots, the robustness of the approaches and the generation of dynamic tasks have been presented and discussed. The particular issues studied are: Threshold models: It presents the experiments conducted to test the response threshold model with the objective to analyze the system performance index, for the problem of the distribution of heterogeneous multitasks in multi-robot systems; also has been introduced additive noise in the number of pending loads and has been generated dynamic tasks over time. Learning automata methods: It describes the experiments to test the learning automata-based probabilistic algorithms. The approach was tested to evaluate the system performance index with additive noise and with dynamic tasks generation for the same problem of the distribution of heterogeneous multi-tasks in multi-robot systems. Ant colony optimization: The goal of the experiments presented is to test the ant colony optimization-based deterministic algorithms, to achieve the distribution of heterogeneous multi-tasks in multi-robot systems. In the experiments performed, the system performance index is evaluated by introducing additive noise and dynamic tasks generation over time.

Response threshold models and stochastic learning automata for self-coordination of heterogeneous multi-task distribution in multi-robot systems.

This paper focuses on the general problem of coordinating multiple robots. More specifically, it addresses the self-selection of heterogeneous specialized tasks by autonomous robots. In this paper we focus on a specifically distributed or decentralized approach as we are particularly interested in a decentralized solution where the robots themselves autonomously and in an individual manner, are responsible for selecting a particular task so that all the existing tasks are optimally distributed and executed. In this regard, we have established an experimental scenario to solve the corresponding multi-task distribution problem and we propose a solution using two different approaches by applying Response Threshold Models as well as Learning Automata-based probabilistic algorithms. We have evaluated the robustness of the algorithms, perturbing the number of pending loads to simulate the robot’s error in estimating the real number of pending tasks and also the dynamic generation of loads through time. The paper ends with a critical discussion of experimental results.

Estrategias innovadoras para la gestión del riesgo de sequía en sistemas ganaderos extensivos

La vulnerabilidad de los sistemas ganaderos de pastoreo pone en evidencia la necesidad de herramientas para evaluar y mitigar los efectos de la sequía. El avance en la teledetección ha despertado el interés por explotar potenciales aplicaciones, y está dando lugar a un intenso desarrollo de innovaciones en distintos campos. Una de estas áreas es la gestión del riesgo climático, en donde la utilización de índices de vegetación permite la evaluación de la sequía. En esta investigación, se analiza el impacto de la sequía y se evalúa el potencial de nuevas tecnologías como la teledetección para la gestión del riesgo de sequía en sistemas de ganadería extensiva. Para ello, se desarrollan tres aplicaciones: (i) evaluar el impacto económico de la sequía en una explotación ganadera extensiva de la dehesa de Andalucía, (ii) elaborar mapas de vulnerabilidad a la sequía en pastos de Chile y (iii) diseñar y evaluar el potencial de un seguro indexado para sequía en pastos en la región de Coquimbo en Chile. En la primera aplicación, se diseña un modelo dinámico y estocástico que integra aspectos climáticos, ecológicos, agronómicos y socioeconómicos para evaluar el riesgo de sequía. El modelo simula una explotación ganadera tipo de la dehesa de Andalucía para el período 1999-2010. El método de Análisis Histórico y la simulación de MonteCarlo se utilizan para identificar los principales factores de riesgo de la explotación, entre los que destacan, los periodos de inicios del verano e inicios de invierno. Los resultados muestran la existencia de un desfase temporal entre el riesgo climático y riesgo económico, teniendo este último un periodo de duración más extenso en el tiempo. También, revelan que la intensidad, frecuencia y duración son tres atributos cruciales que determinan el impacto económico de la sequía. La estrategia de reducción de la carga ganadera permite aminorar el riesgo, pero conlleva una disminución en el margen bruto de la explotación. La segunda aplicación está dedicada a la elaboración de mapas de vulnerabilidad a la sequia en pastos de Chile. Para ello, se propone y desarrolla un índice de riesgo económico (IRESP) sencillo de interpretar y replicable, que integra factores de riesgo y estrategias de adaptación para obtener una medida del Valor en Riesgo, es decir, la máxima pérdida esperada en un año con un nivel de significación del 5%.La representación espacial del IRESP pone en evidencia patrones espaciales y diferencias significativas en la vulnerabilidad a la sequía a lo largo de Chile. Además, refleja que la vulnerabilidad no siempre esta correlacionada con el riesgo climático y demuestra la importancia de considerar las estrategias de adaptación. Las medidas de autocorrelación espacial revelan que el riesgo sistémico es considerablemente mayor en el sur que en el resto de zonas. Los resultados demuestran que el IRESP transmite información pertinente y, que los mapas de vulnerabilidad pueden ser una herramienta útil en el diseño de políticas y toma de decisiones para la gestión del riesgo de sequía. La tercera aplicación evalúa el potencial de un seguro indexado para sequía en pastos en la región de Coquimbo en Chile. Para lo cual, se desarrolla un modelo estocástico para estimar la prima actuarialmente justa del seguro y se proponen y evalúan pautas alternativas para mejorar el diseño del contrato. Se aborda el riesgo base, el principal problema de los seguros indexados identificado en la literatura y, que está referido a la correlación imperfecta del índice con las pérdidas de la explotación. Para ello, se sigue un enfoque bayesiano que permite evaluar el impacto en el riesgo base de las pautas de diseño propuestas: i) una zonificación por clúster que considera aspectos espacio-temporales, ii) un período de garantía acotado a los ciclos fenológicos del pasto y iii) umbral de garantía. Los resultados muestran que tanto la zonificación como el periodo de garantía reducen el riesgo base considerablemente. Sin embargo, el umbral de garantía tiene un efecto ambiguo sobre el riesgo base. Por otra parte, la zonificación por clúster contribuye a aminorar el riesgo sistémico que enfrentan las aseguradoras. Estos resultados han puesto de manifiesto que un buen diseño de contrato puede tener un doble dividendo, por un lado aumentar su utilidad y, por otro, reducir el coste del seguro. Un diseño de contrato eficiente junto con los avances en la teledetección y un adecuado marco institucional son los pilares básicos para el buen funcionamiento de un programa de seguro. Las nuevas tecnologías ofrecen un importante potencial para la innovación en la gestión del riesgo climático. Los avances en este campo pueden proporcionar importantes beneficios sociales en los países en desarrollo y regiones vulnerables, donde las herramientas para gestionar eficazmente los riesgos sistémicos como la sequía pueden ser de gran ayuda para el desarrollo. The vulnerability of grazing livestock systems highlights the need for tools to assess and mitigate the adverse impact of drought. The recent and rapid progress in remote sensing has awakened an interest for tapping into potential applications, triggering intensive efforts to develop innovations in a number of spheres. One of these areas is climate risk management, where the use of vegetation indices facilitates assessment of drought. This research analyzes drought impacts and evaluates the potential of new technologies such as remote sensing to manage drought risk in extensive livestock systems. Three essays in drought risk management are developed to: (i) assess the economic impact of drought on a livestock farm in the Andalusian Dehesa, (ii) build drought vulnerability maps in Chilean grazing lands, and (iii) design and evaluate the potential of an index insurance policy to address the risk of drought in grazing lands in Coquimbo, Chile. In the first essay, a dynamic and stochastic farm model is designed combining climate, agronomic, socio-economic and ecological aspects to assess drought risk. The model is developed to simulate a representative livestock farm in the Dehesa of Andalusia for the time period 1999-2010. Burn analysis and MonteCarlo simulation methods are used to identify the significance of various risk sources at the farm. Most notably, early summer and early winter are identified as periods of peak risk. Moreover, there is a significant time lag between climate and economic risk and this later last longer than the former. It is shown that intensity, frequency and duration of the drought are three crucial attributes that shape the economic impact of drought. Sensitivity analysis is conducted to assess the sustainability of farm management strategies and demonstrates that lowering the stocking rate reduces farmer exposure to drought risk but entails a reduction in the expected gross margin. The second essay, mapping drought vulnerability in Chilean grazing lands, proposes and builds an index of economic risk (IRESP) that is replicable and simple to interpret. This methodology integrates risk factors and adaptation strategies to deliver information on Value at Risk, maximum expected losses at 5% significance level. Mapping IRESP provides evidence about spatial patterns and significant differences in drought vulnerability across Chilean grazing lands. Spatial autocorrelation measures reveal that systemic risk is considerably larger in the South as compared to Northern or Central Regions. Furthermore, it is shown that vulnerability is not necessarily correlated with climate risk and that adaptation strategies do matter. These results show that IRESP conveys relevant information and that vulnerability maps may be useful tools to assess policy design and decision-making in drought risk management. The third essay develops a stochastic model to estimate the actuarially fair premium and evaluates the potential of an indexed insurance policy to manage drought risk in Coquimbo, a relevant livestock farming region of Chile. Basis risk refers to the imperfect correlation of the index and farmer loses and is identified in the literature as a main limitation of index insurance. A Bayesian approach is proposed to assess the impact on basis risk of alternative guidelines in contract design: i) A cluster zoning that considers space-time aspects, ii) A guarantee period bounded to fit phenological cycles, and iii) the triggering index threshold. Results show that both the proposed zoning and guarantee period considerably reduces basis risk. However, the triggering index threshold has an ambiguous effect on basis risk. On the other hand, cluster zoning contributes to ameliorate systemic risk faced by the insurer. These results highlighted that adequate contract design is important and may result in double dividend. On the one hand, increasing farmers’ utility and, secondly, reducing the cost of insurance. An efficient contract design coupled with advances in remote sensing and an appropriate institutional framework are the basis for an efficient operation of an insurance program. The new technologies offer significant potential for innovation in climate risk managements. Progress in this field is capturing increasing attention and may provide important social gains in developing countries and vulnerable regions where the tools to efficiently manage systemic risks, such as drought, may be a means to foster development.

Sustainability of irrigated farming systems in a Tunisian region: A recursive stochastic programming analysis

The aim of this study was to evaluate the sustainability of farm irrigation systems in the Cébalat district in northern Tunisia. It addressed the challenging topic of sustainable agriculture through a bio-economic approach linking a biophysical model to an economic optimisation model. A crop growth simulation model (CropSyst) was used to build a database to determine the relationships between agricultural practices, crop yields and environmental effects (salt accumulation in soil and leaching of nitrates) in a context of high climatic variability. The database was then fed into a recursive stochastic model set for a 10-year plan that allowed analysing the effects of cropping patterns on farm income, salt accumulation and nitrate leaching. We assumed that the long-term sustainability of soil productivity might be in conflict with farm profitability in the short-term. Assuming a discount rate of 10% (for the base scenario), the model closely reproduced the current system and allowed to predict the degradation of soil quality due to long-term salt accumulation. The results showed that there was more accumulation of salt in the soil for the base scenario than for the alternative scenario (discount rate of 0%). This result was induced by applying a higher quantity of water per hectare for the alternative as compared to a base scenario. The results also showed that nitrogen leaching is very low for the two discount rates and all climate scenarios. In conclusion, the results show that the difference in farm income between the alternative and base scenarios increases over time to attain 45% after 10 years.

Linear Bayes policy for learning in contextual-bandits

Machine and Statistical Learning techniques are used in almost all online advertisement systems. The problem of discovering which content is more demanded (e.g. receive more clicks) can be modeled as a multi-armed bandit problem. Contextual bandits (i.e., bandits with covariates, side information or associative reinforcement learning) associate, to each specific content, several features that define the “context” in which it appears (e.g. user, web page, time, region). This problem can be studied in the stochastic/statistical setting by means of the conditional probability paradigm using the Bayes’ theorem. However, for very large contextual information and/or real-time constraints, the exact calculation of the Bayes’ rule is computationally infeasible. In this article, we present a method that is able to handle large contextual information for learning in contextual-bandits problems. This method was tested in the Challenge on Yahoo! dataset at ICML2012’s Workshop “new Challenges for Exploration & Exploitation 3”, obtaining the second place. Its basic exploration policy is deterministic in the sense that for the same input data (as a time-series) the same results are obtained. We address the deterministic exploration vs. exploitation issue, explaining the way in which the proposed method deterministically finds an effective dynamic trade-off based solely in the input-data, in contrast to other methods that use a random number generator.

A unified framework for linear function approximation of value functions in stochastic control

This paper contributes with a unified formulation that merges previ- ous analysis on the prediction of the performance ( value function ) of certain sequence of actions ( policy ) when an agent operates a Markov decision process with large state-space. When the states are represented by features and the value function is linearly approxi- mated, our analysis reveals a new relationship between two common cost functions used to obtain the optimal approximation. In addition, this analysis allows us to propose an efficient adaptive algorithm that provides an unbiased linear estimate. The performance of the pro- posed algorithm is illustrated by simulation, showing competitive results when compared with the state-of-the-art solutions.

Assessing the impact of adaptive accessibility on the optimal transport policy implementation by using an integrated land-use/transport model for Madrid

Accessibility is an essential concept widely used to evaluate the impact of land-use and transport strategies in transport and urban planning. Accessibility is typically evaluated by using a transport model or a land-use model independently or successively without a feedback loop, thus neglecting the interaction effects between the two systems and the induced competition effects among opportunities due to accessibility improvements. More than a mere methodological curiosity, failure to account for land- use/transport interactions and the competition effect may result in large underestimation of the policy effects. With the recent development of land-use and transport interaction (LUTI) models, there is a growing interest in using these models to adequately measure accessibility and evaluate its impact. The current study joins this research stream by embedding an accessibility measure in a LUTI model with two main aims. The first aim is to account for adaptive accessibility, namely the adjustment of the potential accessibility due to the effect of competition among opportunities (e.g., workplaces) as a result of improved accessibility. LUTI models are particularly suitable for assessing adaptive accessibility because the competition factor is a function of the number of jobs, which is related to land-use attractiveness and the number of workers which is related, among other factors, to the transport demand. The second aim is to identify the optimal implementation scenario of policy measures on the basis of the potential and adaptive accessibility and analyse the results in terms of social welfare and accessibility. The metropolitan area of Madrid is used as a case-study and two transport policy instruments, namely a cordon toll and bus frequency increase, have been chosen for the simulation study in order to present the usefulness of the approach to urban planners and policy makers. The MARS model (Metropolitan Activity Relocation Simulator) calibrated for Madrid was employed as the analysis tool. The impact of accessibility is embedded in the model through a social welfare function that includes not only costs and benefits to both road users and transport operators, but also costs and benefits for the government and society in general (external costs). An optimisation procedure is performed by the MARS model for maximizing the value of objective function in order to find the best (optimal) policy imp lementations intensity (i.e., price, frequency). Last, the two policy strategies are evaluated in terms of their accessibility. Results show that the accessibility with competition factor influences the optimal policy implementation level and also generates different results in terms of social welfare. In addition, mapping the difference between the potential and the adaptive accessibility indicators shows that the main changes occur in areas where there is a strong competition among land-use opportunities.

Assessing the accessibility impact of transport policy by a land-use and transport interaction model - The case of Madrid

Accessibility is an essential concept widely used to evaluate the impact of transport and land-use strategies in urban planning and policy making. Accessibility is typically evaluated by using separately a transport model or a land-use model. This paper embeds two accessibility indicators (i.e., potential and adaptive accessibility) in a land use and transport interaction (LUTI) model in order to assess transport policies implementation. The first aim is to define the adaptive accessibility, considering the competition factor at territorial level (e.g. workplaces and workers). The second aim is to identify the optimal implementation scenario of policy measures using potential and adaptive accessibility indicators. The analysis of the results in terms of social welfare and accessibility changes closes the paper. Two transport policy measures are applied in Madrid region: a cordon toll and increase bus frequency. They have been simulated through the MARS model (Metropolitan Activity Relocation Simulator, i.e. LUTI model). An optimisation procedure is performed by MARS for maximizing the value of the objective function in order to find the optimal policy implementation (first best). Both policy measures are evaluated in terms of accessibility. Results show that the introduction of the accessibility indicators (potential and adaptive) influence the optimal value of the toll price and bus frequency level, generating different results in terms of social welfare. Mapping the difference between potential and adaptive accessibility indicator shows that the main changes occur in areas where there is a strong competition among different land-use opportunities.