Abstract
In the last decades, studies on swarm robotics have grown significantly, with different implementation details becoming of interest in research works. Although the first idea in swarm robotics should be the application or the task that robots should perform, other aspects can be studied. In a robotic swarm, it may be necessary to select the robots that will perform a given task, which is a division of labor among the members. A similar problem is that of robot recruitment, required when a specific robot needs assistance to execute some tasks and starts recruiting other robots of the swarm. In this chapter, a distributed algorithm, termed the wave algorithm, is exploited to perform the recruitment based on robot message passing to neighboring robots. The intended task to be done is the coordinated motion of the recruited robots that must follow the robot that starts the recruitment.
TopIntroduction
In a robotic swarm, a group of mobile robots works together to achieve a collective behavior (Şahin, 2005). In such systems, the agents are autonomous robots that follow simple rules and have only local capabilities of sensing and communication. The swarm has no central control or global information sharing. At the microscopic level, even individual robots are not aware of the complete behavior of system. In fact, the swarm behavior emerges from the interaction of the robots or between robots and the environment. In general, the concept of swarm is more intuitive at macroscopic level, when the group of robots perform a given task collectively.
The non-centralized approach of robotic swarm is classically inspired in the observation of social animals, like ants, bees, birds and fishes. Social animals exhibit some kind of swarm intelligence (Bonabeau et al., 1999), where a successful collective behavior emerges from interactions between individuals. It is robust, flexible and scalable, characteristics that are desired in multi-agent systems (Camazine et al., 2001). The robustness can be defined as the capability of continuity of work in presence of failures. A swarm system is said robust if it can continue to operate even if one or more swarm members stops to work due to internal failures or if the environment is changing dynamically. This is achieved in the nature by the redundancy of the individuals and the absence of leaders. The scalability of the system means that the swarm can work if different number of members. An individual can work in the same mode in a swarm with a large or with a small number of members without a significant change in its performance. And the flexibility is defined as the possibility of change in swarm behavior. In a flexible system, the internal parameters of individuals can be adjusted in presence of changes of the environment. All these three concepts are related to a single main idea: a swarm system can be able to perform the proposed task under different conditions.
Swarm robots are devices with limited capabilities of computational processing, sensing, communication and movement. The task done by the swarm is usually achieved by the execution of algorithms in each robot. This kind of system has many similarities with the execution of distributed algorithms by a multiprocessor system. In this chapter, the behavior of an individual robot is defined by an algorithm, that takes advantage of basic concepts of distributed systems, such as direct communication, allowing the transmission of explicit messages among processes. However, typical swarm robotic systems may also use indirect communication, sensing other robots or interacting with the environment (Cao et al., 1997).
A mobile robot is an agent able to move in the environment. In the context of this chapter, a robot is characterized having two movement engines, allowing it to go forward and backward, but with no direct right-to-left displacements. Robots with this movement are called non-holonomic. An individual robot is dotted with some computational capabilities. Furthermore, it may sense the environment via some built-in sensors. The main sensory capability allows distance measurement to robots in the swarm. This is a local knowledge, because a robot can only sense robots in a small neighborhood. Robots may also have some kind of wireless communication, allowing message passing among the swarm members. It may be a local broadcast message, where a robot broadcasts some information to all robots in the neighborhood, or a direct message, identifying both the sender and the receiver.
Different kinds of problems collectively solved or executed by swarm robotics are studied in literature. In this chapter, the term behavior is used to designate a complex activity performed by a group of robots. Usually, the behavior describes, in a high level of abstraction, the work of swarm as a whole. This complex job may be divided in sub-jobs. The term task designates these sub-jobs. In this chapter, the complete behavior is the spatial division of swarm in groups. This behavior is divided in four sequential tasks:
Key Terms in this Chapter
Father-Child Dependency: The relation among neighbor robots. A non-initiator robot must send a feedback message to a single robot, known as father node. In other hand, this robot may also receive feedback messages from other neighbors; these are called child nodes. Some non-initiator robots may have no child nodes. The initiator robot has child nodes, but no father node.
Wave Algorithm: Distributed algorithm which works by the propagation of messages through the network nodes.
Message: Information transmitted between two robots. In the real Kilobot, the message is a sequence of bits transmitted by local broadcast through infrared communication. This message can be directed to a specific neighbor if the individual identification of the receiver is included.
Recruitment Task: The process when a robot request its neighbors to form a group. In this chapter, the recruitment is performed by the propagation of messages in the execution of a wave algorithm. The recruiter is the initiator, and the recruited robots are the non-initiator robots.
Group: The group of robots including an initiator and the recruited robots. A group is associated to each initiator in the swarm.
Node: The processing unit in a network. In the context of this chapter, the robots are nodes. Having some processing capabilities and an infrared communication, connected robots are able to execute distributed algorithms.
Coordinated Motion Task: The movement of a robot based on its position relative to the father node. This movement keeps the a formation, with the pattern information distributed among the swarm members.
Dynamic Neighborhood: Capacity of work with any initial configuration of the robots position. The swarm members which are in the range of communication of a specific robot define its neighborhood. In the execution of the wave algorithm, all robots must know their neighborhood, since the algorithm is not restrict to a single topology. The neighborhood discovering task provides this information, being performed before the execution of the wave.
Alignment Task: Rotation process of the child robots to keep the same direction of its father node. The complete alignment of the swarm is achieved when all robots point to a same direction. The alignment task requires that each robot has a front side.