Stigmergy-based mapping of indoor hazardous environments

Motivation

In recent years there has been a rapidly growing interest in using teams of mobile robots for automatically monitoring/surveillance of environments of different type and complexity. This interest is mainly motivated by the broad spectrum of potential civilian, industrial and military applications of multi-robot monitoring systems.

Examples of such applications are the protection of safety critical technical infrastructures, the safeguarding of country borders, and the monitoring of high-risk regions and danger zones which cannot be entered by humans in the case of a nuclear incident, a biohazard or a military conflict. In these cases, information about the environment needs to be collected and processed so that, for example, emergency and protection services can take appropriate actions.

Despite the remarkable progress made on robotic automated surveillance so far, there is still a huge gap between theory and practice of multi-robot surveillance systems and as a consequence there are still only very few on-field deployments. The reason for this is that many basic questions about coordination among mobile robots are not yet answered in a satisfactory way. In particular, currently available theoretical and algorithmic approaches are typically based on unrealistic assumptions and/or are of a computational complexity, which excludes their usage in non-trivial application scenarios. Examples of such unrealistic assumptions are idealized sensors, convexity of the environment, and the availability of direct communication links. In addition, most available formal approaches ignore critical practical issues such as sensor failures or breakdown of individual robots. Finally, several applications (e.g. monitoring of a nuclear plant) require not only surveillance of the environment, but also mapping of physical data (e.g. radioactivity maps). For these reasons, there is a strong need for approaches to multi-robot surveillance which do not suffer from these deficiencies and enable practical surveillance applications with robot teams of different size.

Research proposal

The proposed project addresses this need and wants to explore a novel perspective on surveillance multi-robot systems, which is based on an established coordination principle known as stigmergy.

According to this principle, which was first observed in biological systems such as ant and termite colonies, natural entities improve their collective performance by influencing one another in their individual performance through local messages they deposit in their shared environment. In computer science, and especially in the field of ant algorithms, a number of computational variants of stigmergy have been developed and it has been shown that they allow for very efficient distributed control and optimization in a variety of problem domains. In addition to efficiency and distribution, stigmergy-based coordination has several other properties that are also essential to multi-robot surveillance, including robustness, scalability, adaptability and simplicity.

Specifically, a main advantage of stigmergy-based coordination is its suitability for small as well as large teams of robots operating in environments with limited, intermittent or unavailable network connectivity. This is particularly important for applications involving complex unknown environments where human operators cannot gather information. Examples include spatial and radioactivity mapping of a nuclear plant and inspection of devastated area after an earthquake.

Objective

Development of an integrated mathematical, algorithmic and technical framework for robotic stigmergy-based complex environment monitoring. The framework shall allow for handling realistic surveillance conditions and shall be analysed and evaluated theoretically and experimentally through simulations and with multiple physical robots in non-trivial real-world settings. This will avoid the major deficiencies of existing robotic monitoring approaches.

In pursuing the project’s objective, we want to address the following three complementary general research questions, which concern mathematical (RQ1), algorithmic (RQ2) and technological (RQ3) foundations of stigmergy-based surveillance.

Relevance of RQ1: Due to the nature of stigmergy, stigmergy-based multi-robot surveillance means that surveillance is achieved through multiple robots, which communicate only indirectly and locally by depositing and transmitting messages in their environment. This constitutes a main difference to most conventional multi-robot surveillance systems, which rely on direct and non-local (long-range) robot-robot communication. While multi-robot surveillance has a broad range of potential applications, there is still a need for a profound mathematical model which allows (i) to formally analyse qualitative and quantitative properties of stigmergy-based surveillance (e.g., with respect to convergence, robustness, scalability and costs) and (ii) to formally compare stigmergy-based and conventional multi-robot surveillance.

Relevance of RQ2: Exploration and coverage are key components of every surveillance mission. What is therefore needed are algorithms which realize in an appropriate way these two components and the basic activities underlying both of them - localization, map building, environmental partitioning, path planning and intruder detection/tracking - on the basis of stigmergy-based communication. Thereby, “appropriateness” has to be evaluated theoretically and experimentally in simulation and robot studies w.r.t. different forms of exploration (deliberative vs. reactive) and coverage (full vs. barrier).

Relevance of RQ3: A conclusive evaluation of the developed algorithms requires - in addition to their theoretical and simulation-based study - to apply and test them with real robots (more precisely, robot teams of different size), because this is the only way to find out what exactly the technical demands are which are raised by stigmergy-based surveillance. Research question RQ3 addresses these technical issues and ensures that important hardware aspects and realistic constraints on robot-robot coordination are appropriately treated. We believe that our work on RQ3 can also contribute to a better understanding of the demands induced by stigmergy-based surveillance on next-generation technical communication devices.

Centre for Doctoral Training in Quantification and Management of Risk & Uncertainty in Complex Systems & Environments is funded by EPSRC and ESRC.