Coordination of swarms of robots in target search: from bio-inspired heuristics to hyper-heuristics

In recent years, the problem of target search has received much attention in the research community due to the wide range of applications domains involved, such as environmental monitoring, precision agriculture, surveillance, or search and rescue. Essentially, it concerns the search for stationary or dynamic targets in unstructured environments, aiming to minimize the overall discovery time. In order to tackle this problem, solutions based on collective search are currently of great interest in robotics. However, coordinating a multi-robot system is a challenging problem, particularly in unstructured areas, as for example hazardous and post-disaster scenarios where direct communication is limited. Swarm robotics is a new and disruptive research field that studies how to manage and coordinate large groups (swarms) of mostly simple physical robots, getting inspiration from swarm intelligence to model the behavior of the robots. For centuries, the concept of intelligence has been linked exclusively to human beings. However, a simple observation of nature shows that other creatures can also develop behaviors that are sophisticated enough to be considered intelligent. The mysterious dance of honeybees to communicate the location of promising food sources, the amazing floating shapes drawn in the sky by a flock of birds while foraging, the creation of impressive cathedral mounds by termites, the trail followed by ants to quickly reach the nest from a food source are all good examples of complex collective behaviors, unknown to individual members of the swarm. These sophisticated collective behaviors emerge from a relatively small set of rather simple rules, where single individuals exploit only low-level local interactions with each other and with the environment to gain decentralized control and self-organization. For example, in ant societies, a key factor of self-organization is the indirect communication between individuals through changes in the environment, a process known as stigmergy. Specifically, at the beginning the ants search for new food sources moving randomly. However, when an ant finds a potential food source, it takes a piece and returns to the nest, leaving pheromone trails on the way back. Other ants, while perceiving the pheromones, follow the trail until the food source and come back to the nest, releasing themselves new pheromones, thus reinforcing the specific route. On the other hand, these pheromone trails evaporate over time, reducing their attractive strength. Obviously, shorter paths are less affected by this evaporation process in short term, so they are more likely to be eventually visited more frequently than the longer ones. In this way, nature provide a solution to the problem of finding the shortest path between two points: the ant colony and the food source. This and other biological mechanisms have been the inspiration for efficient optimization methods (bio-inspired heuristics). In the context of swarm robotics, a virtual representation of the pheromone can be used to steer the swarms towards the most favorable areas of an application scenario, e.g. the regions with the highest probability of the presence of targets. The main drawbacks of bio-inspired heuristics are related to the selection of the most suitable algorithm for the specific scenario and the parametrization costs to adapt it to new type of missions. In fact, the hypothesis space of a bio-heuristic, i.e. the space in which to search for a good algorithm configuration, is constrained by models of biological species. In order to generate more adaptable logics, in this thesis it is proposed a novel design approach based on hyper-heuristics. For a given application domain, hyper-heuristics aim to provide more generalized solutions to optimization problems, rather than deriving techniques that perform well for just a few problem instances. In order to achieve this result, they either select or generate low-level heuristics, which are used to solve the problem at hand. In this thesis, two fundamental components are considered as constructive low-level heuristics for building decentralized and self-organized robot swarm coordination logics, i.e. stigmergy and flocking. Moreover, Differential Evolution is used to optimize the aggregation and tuning of these modular heuristics over realistic real-world scenarios. The experimental results acquired from extensive simulations are promising and show the convenience of using hyper-heuristics as a novel design methodology compared to simple bio-inspired heuristics.