Distributed Algorithms for Swarm Robots

Distributed Algorithms for Swarm Robots

Sruti Gan Chaudhuri (Jadavpur University, India) and Krishnendu Mukhopadhyaya (Indian Statistical Institute, India)
DOI: 10.4018/978-1-4666-9572-6.ch008


A swarm of robots is a collection of tiny identical autonomous robots. The robots perform a given task, e.g., cleaning a big surface, moving a big object, guarding an area etc., in a collaborative framework. The goal of research in swarm robotics is to develop a low cost multi-robot system which will be at least as efficient as one big expensive unit. The field of swarm robotics has been addressed from various aspects such as artificial intelligence, mechanical and electrical engineering, motion control, robots' path planning etc. From theoretical point of view, designing deterministic algorithms for these robots to execute a particular job is an emerging and useful field of research. As the robots work individually but in collaboration, distributed algorithms are more appropriate than centralized ones. This chapter discusses the distributed framework for swarm robots and presents some reported research results as well as a few open problems.
Chapter Preview


One of the dreams of technology has always been to build machines which are as efficient as human beings or natural entities. Since the dawn of civilization, technological developments and popular culture have influenced each other. Around 1495 Leonardo da Vinci sketched a humanoid robot. Though the notion of robots is very old, the term “robot” was introduced in 1920 in the play “Rossum’s Universal Robots” by Karel Capek. The word “robot” comes from a Czech word “robota” or “robotnik” which means slave, servant, or forced labor. Technically, a robot is a programmable, self-controlled device, consisting of electronic, electrical and mechanical units, carrying out a complex series of actions automatically. In the modern age of automation, applications of robots span areas as diverse as space science, military or defense, education systems, health care, biological science, nano-technology etc.

The notion of robot is inspired by observing characteristics of human or natural entities in society. Cooperative behaviour is one of the basic requirements in a well-built society. This feature is also replicated in robots. Multi-robot systems can perform many complex tasks efficiently by executing them cooperatively. In hostile environments, it may be difficult or impossible to deploy a big robot. The cost of making a big robot is also high. Hence, the concept of a group of small robots working together has become a strong trend in recent robotic research. These robots are less expensive and simple to design, configure and deploy. Moreover, their cooperation capability makes them powerful to perform many complicated jobs more efficiently than an expensive machine working alone.

Many projects, like CEBOT (Kawauchi et al., 1993), ACTRESS (Asama et al., 1989), GOFER (Caloud et al., 1990), SWARM (Wang and Beni, 1990) have studied the issues of group architecture, resource conflicts, origin of cooperation, learning and geometric problems. In the literature on robotics, Cooperation is, joint collective behaviour that is directed towards some goal in which there is a common interest or reward. (Barnes et al., 1991) Many recent projects such as Kilobots (http://www.swarmanoid.org/), are approaching swarm robotics with emphasis on sub-problems like task decomposition or task allocation, learning, motion coordination etc. The field of cooperative mobile robots has been enriched by many researchers from various disciplines like robotics (Arkin, 1987; Vaughan et al., 2000), control (Bullo et al., 2009; Loo et al., 2002, Reynolds, 1987), swarm intelligence (Balch, 1998; Beni, 1988; Parker and Touzet, 2000), distributed computing (Peleg, 2005; Prencipe, 2005; Sless et al., 2014) etc.

In this chapter we focus on a group of robots called swarm robots which function under a distributed framework. All robots are identical in their configurations and appearances, and independent in their computations and actions. They can sense their surroundings through some devices. Each robot possesses a minimal capability in term of their storage and communication power. We also discuss some coordination problems and their solutions, based on cooperative behaviour of the swarm robots.

Key Terms in this Chapter

Asymmetric Pattern: If a set of patterns point are in asymmetric configuration then the pattern is called an asymmetric pattern.

Bi-Angular Configuration: In bi-angular configuration, there exists a point c and two angles a and ß such that the angle at c between any two adjacent robots is either a or ß and the angles alternate.

Asymmetric Configuration: If a set of points is not in symmetric configuration then they are in asymmetric configuration .

Orderable Set: A set of points is called an orderable , if there exists a deterministic algorithm, which produces a unique ordering of the points of the set, such that the ordering is same irrespective of the choice of origin and coordinate system.

Center of Gravity (CoG): Given a set of n points represented by their co-ordinate values as {(x 1 , y 1 ), …, (x n ,y n) }. The Center of Gravity (COG) of the points is given by (x c ,y c ) where x c = {x 1 + … + x n) }/n and y c = { y 1 + … + y n) }/n.

Symmetric Configuration: A set of points is said to be in symmetric configuration if there exists a straight line such that one half of the set is the mirror image of other half. The straight line is called the line of symmetry .

Minimum Enclosing Circle (MEC): MEC of a set of n points is the unique circle of minimum radius, which encloses all the points. All the points lie either on the circumference or inside the MEC.

Symmetric Pattern: If a set of patterns point are in symmetric configuration then the pattern is called a symmetric pattern . Example: circle, square, straight line.

Weber Point: Given a set of n points, Weber point is the point which minimizes the sum of distances between itself and all the points. This is also known as the Fermat or Torricelli point.

Complete Chapter List

Search this Book: