Distributed Task Allocation in Swarms of Robots

Introduction

The initial purpose of swarm intelligence algorithms was to solve optimization problems. However, in recent years, these algorithms have shown their full potential in terms of flexibility and autonomy when it comes to design and control of complex systems that consist of a large number of autonomous agents. In more general terms, these can be referred to as systems of autonomous systems (Jamshidi, 2009). What distinguishes swarm intelligence algorithms in the broad field of soft-computing is that they exploit the decentralizing property of natural swarms in order to create autonomous, scalable, and adaptive multi-agent systems.

Swarm robotics emerged as a straight-forward application domain for swarm intelligence due to resemblance of large robot teams to animal swarms (Dorigo & Sahin, 2004; Trianni, Nolfi & Dorigo, 2008; Correll, Cui, Gao & Gross, 2010). In nature, swarming behavior has been studied in ant and bee colonies, bird flocks and fish schools, among others (Engelbrecht, 2005). However, the biological plausibility of swarm intelligence algorithms, and swarm-based systems in general, is not a must; in computer science and engineering researchers are guided by efficiency, flexibility, robustness and cost as main criteria.

In applications that require area coverage, swarms of mobile robots can use their ability to quickly deploy within a large area. Some of the possible applications include planetary exploration, urban search and rescue, communication networks, monitoring, surveillance, cleaning, maintenance, and so forth. In order to efficiently perform their tasks, robots require high level of autonomy and cooperation. They use their sensing abilities to explore an unknown environment and deploy on the sites of interest, i.e. targets. However, the coordination of a robot swarm is not an easy problem, especially when the resources for the deployment task are limited. Such a large group of robots, if organized in a centralized manner, could experience information overflow that can lead to the overall system failure (Gazi, Jevtić, Andina & Jamshidi, 2010). For this reason, the communication between the robots can be realized through local interactions, either directly with one another or indirectly via environment (Beni & Wang, 1989).

As a result of the growing interest in the coordination of swarms of robots, multi-robot task allocation (MRTA) has become an important research topic (Dudek, Jenkin & Milios, 2002; Gerkey & Matarić, 2004). The goal is to assign tasks to robots in a way that, through cooperation, the global objective is achieved more efficiently. In the scenario proposed in this work, tasks are represented by targets defined with their qualities and their location in the robot arena. For distributed task allocation the Distributed Bees Algorithm (DBA) was proposed (Jevtić, Gazi, Andina & Jamshidi, 2010), which was inspired by the foraging behavior of colonies of bees in nature. In the context of mobile multi-robot systems, scalability refers to the overall system’s performance if the number of robots increases in relation to the number of tasks at hand (Rana & Stout, 2000). The resulting effect on the system’s performance can be determined in terms of metrics associated with a particular platform or an operating environment, which in this work refers to dispatching a robot to a remote site marked as a target.

The objectives of this chapter are manifold. The following section describes the problem of MRTA and provides a summary of the related work. The Distributed Bees Algorithm (DBA) is then proposed as a solution to distributed MRTA. The DBA’s performance is subsequently validated through experiments with physical robots. Moreover, simulator was developed to test the DBA’s scalability in terms of number of robots and number of targets. The last experiments present analysis of DBA’s performance through optimization of its control parameters. Finally, this chapter provides perspectives on future research directions and gives concluding remarks.