Swarm of mobile robots is actually a large number of small robots imitating the behavior of social insects that perform certain tasks in a group. This chapter considers the problem of area coverage by a swarm of mobile robots. Initially, the robots occupy random positions in a target area. The objective is to physically cover/scan each accessible location of that area by at least one robot of the swarm. After discussing, in brief, different models and their challenges this chapter summarizes the research works carried out to solve this problem. The existing literature is classified into two categories, namely, team based approach and individual approach. The pros and cons of both the approaches are indicated and finally a comparative study of the addressed works in terms of computational model, synchrony, characteristics of robots, etc. is presented.
TopIntroduction
Multi robot coordination is desired in many applications. A swarm of robots can perform many difficult tasks through coordination. The main aim of research related to swarm robots is to take group of relatively simple robots in different distributed computing environments and coordinate them to perform a desired task by using only local information. A system of a swarm of robots has many advantages. The component robots are usually so simple that they can be developed very easily and in a cost effective way. The system also has the other advantages of being scalable, fault-tolerant etc. Swarming is mostly found in the group of small animals (like fish, birds etc.) and the social insects (like bees, ants etc.) which may gather together at the same spot, or perhaps move or migrate together in some particular direction. A swarm can perform tasks that are beyond the capabilities of the individuals. These behaviors (flocking, shoaling, foraging etc.) are rising from a set of simple rules that are followed by each individual in an autonomous way. The members in a swarm collaboratively complete any assigned task through the continuous communication and coordination among themselves. This is also known as swarm intelligence. Beni (2005) described this kind of robots' coordination as follows:
The group of robots is not just a group. It has some special characteristics, which are found in swarms of insects, that is, decentralized control, lack of synchronization, simple and (quasi) identical members. (p. 2)
The key factors that influence the advantages of a multi robot swarm over a single robot system are miniaturization, cost and move-ability. The single robot system is not adequately equipped to deal with a complex distributed task. A Swarm of mobile robots may work either in a distributed way or under a centralized control. The task is divided among the robots and each robot autonomously and efficiently completes its own part of the job. Miniaturization is also effective in reduction of cost. Mini robots are capable of reaching many locations, like a narrow air condition duct, inside of a complex engine etc., which may not be possible for a large single powerful robot. Scalability and fault tolerance are also two features in favor of multi robot systems. A multi robot system provides a more useful alternative to a single robot system in different applications.
Inspired by these basic activities, researchers are working on designing algorithms to solve computational problems related to swarm robots which include geometric pattern formation, flocking, coverage, partitioning, spreading, searching, gathering, convergence, etc.
Among various problems related to swarm robots, the focus of this chapter is on the coverage problem. The main objective of coverage of any polygonal area by a swarm of mobile robots is that every accessible location of a target region is to be physically covered (scanned/explored/swept) by at least one robot of the swarm, with their sensors or actuators (Latimer et al., 2002; Rekleitis, Lee Shue, New, & Choset, 2004; Rekleitis, New, Rankin, & Choset, 2008). The target area to be covered may vary in shape and size. It may also be cluttered with static obstacles.
Some of the earlier works on the coverage problem considered single robot system (Hert, Tewari, & Lumelsky, 1996; Lumelsky, Mukhopadhyay, & Sun, 1990; VanderHeide, & Rao, 1995; Zelinsky, Jarvis, Byrne, & Yuta, 1993). The later works, when the coverage problem is addressed by swarm of robots, are relatively more effective as these algorithms reduce the time for completion of the task and boost the overall efficiency of the system compared to a single robot system. In the literature, two different approaches are common in case of multi robot systems. In one approach, the robots work as a team, in which the performance of an individual robot depends entirely on the performance of its other team members; decisions are also taken by teams instead of an individual robot (Latimer et al., 2002; Rekleitis et al., 2004). In these approaches, inter-robot communication is very high and plays an important role in the performance of the algorithm. In the other approach (Fazli, Davoodi, Pasquier, & Mackworth, 2010; Kong, Peng, & Rekleitis, 2006; Rekleitis et al., 2008), each robot performs its own part of the job and takes decisions autonomously. In this case, robots, in general, have only silent communication among themselves through passively observing the positions and actions of its neighbours (Das, & Mukhopadhyaya, 2012, 2013).