Techniques in Multi-Robot Area Coverage: A Comparative Survey

Techniques in Multi-Robot Area Coverage: A Comparative Survey

Deepanwita Das (National Institute of Technology, Durgapur, India), Srabani Mukhopadhyaya (Birla Institute of Technology, Mesra, Kolkata Campus, India) and Debashis Nandi (Department of Information Technology, National Institute of Technology, Durgapur, India)
DOI: 10.4018/978-1-4666-9572-6.ch027
OnDemand PDF Download:
List Price: $37.50


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.
Chapter Preview


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).

Key Terms in this Chapter

Visibility Range: It is a range up to which a robot can view its surroundings. The area of visibility of a robot is usually assumed to be circular in which the robot is located at the center. This circle is known as the circle of visibility and the radius is known as the visibility radius.

Sensing Zone: It is a circular zone similar to the footprint of a robot in which the robot can carry out some task. The radius is known as sensing radius which is much smaller than the visibility radius of the robot. A robot can cover only its sensing region but can view up to its visibility range from its current position.

Area Exploration: A swarm of robots maps the internal environment of any given region. The robots may not necessarily reach every point of the area during exploration.

Area Coverage: Every accessible point of any given area is physically covered by at least one robot in the swarm.

Critical Point: A critical point is a point on an obstacle at which two parallel explorer robot, moving in the same lateral speed, unable to view each other due to the presence of that obstacle.

Exact Cellular Decomposition: It is a technique in which a region is divided into a number of non-overlapping cells so that every cell can be assigned to at least one robot for coverage.

Silent Communication: A passive method for communication in which the robots do not directly exchange messages among themselves; rather they observe the locations and activities of the neighbouring robots and then act accordingly.

Visibility Graph: It is a graph that represents visual connectivity among the robots. The vertices in the graph correspond to the robots in the swarm. Two vertices are connected by an edge iff the corresponding robots are mutually visible.

Complete Chapter List

Search this Book: