Keywords

1 Introduction

Swarm robotics is a scientific discipline to collective robotics, inspired from the behaviours of social animals. Multi-agent systems, considered to be aggregations of autonomous agents, resembles swarm robotics concept in a certain way (Brambilla et al. 2013). Accordingly, both concepts will be considered together in this study. Collective behaviours of multi-agent systems can be classified into three main groups namely, collective decision making, navigation behaviours and spatially organizing behaviours (Brambilla et al. 2013). Aggregation is one of the fundamental and critical spatial organization that allows a group of robots to get close one other, providing interaction and collective movements (Camazine et al. 2001).

Aggregation behaviour can be observed in nature frequently, such as bacteria, bees, fish and etc. (Camazine et al. 2001; Jeanson et al. 2005). Probabilistic finite state machines (PFSMs) are the main methodology used in aggregation ensuring that finally only a sole aggregate is formed. Each robot starts exploring the environment so as to find other robots. Once other robots are found, it decides whether to join or leave the aggregate in a stochastic manner (Garnier et al. 2005; Soysal and Şahin 2005, 2007). Alternatively, artificial evolution approach has been employed to automatically select aggregation behaviour (Soysal et al. 2007). Coordinated motion, flocking, is a navigation behaviour inspired from fish or flock of birds (Kaminka et al. 2008). In multi-agent system, coordinated motion approach provides safer navigation for a group of robots while keeping a constant distance from one another based on virtual physic-based design. One of the popular studies in this area proposes a virtual heading sensor allowing each robot to be able to sense the heading direction of the other robots without requiring a goal direction. Within this sensor, the swarm could provide coordinated motion while avoiding obstacles (Turgut et al. 2008). This study was extended and revealed that it is possible to insert some “informed” robots, knowing the goal direction, in the swarm so as to lead the other “non-informed” robots towards the goal direction (Ferrante et al. 2010). A novel and recent study in coordinated motion field allows robots to change both angular and forward speed according to the computed vector without requiring an explicit alignment rule (Ferrante et al. 2012).

This paper proposes a novel approach based on PFSMs and Virtual physics-based design to assign each robot into a group and allocate a leader for each group in a decentralized manner. This is different from the conventional aggregation behaviour of social animals that instead of forming a single aggregate, robots are grouped according to their distance to each other and a leader is selected in a complete decentralized manner. Besides, each group relies on a centre of gravity (COG) based algorithm and navigates in a coordinated motion towards a specific goal while avoiding obstacles placed on their paths.

This paper is organized as follows. In Sect. 2, the proposed framework and corresponding algorithms for multi-agent systems are presented, whereas Sect. 3 focuses on implementation and evaluation of the system. The study is concluded in Sect. 4.

2 Collective Behavior Framework

This section details the features of the proposed framework used for collective behaviour of multi-agent systems in a decentralized manner that comprises a generic grouping algorithms and a leader assignment procedure, followed by a coordinated navigation strategy. Flowchart of the proposed collective behaviour framework is illustrated in Fig. 1. As it can be seen from the corresponding figure, the framework consists of three main modules and two sub-modules, which will be detailed in the following sections. Essentially each robot possesses a map based navigation strategy that each robot has the 2-D map of the environment and can navigate individually towards a specific goal using a local navigation strategy. Nevertheless, robots are not allowed to communicate each other while performing grouping, leader selection and coordinated motion behaviors. Accordingly, all these tasks are achieved in a decentralized manner.

Fig. 1
figure 1

Flowchart of the collective behaviour framework

Full size image

2.1 Forces Applied to Robots

It is assumed that all robots in the swarm are randomly located and there is no direct communication between robots during the execution of the algorithm. Each robot is equipped with a standard range finder, which has 360° field of view. Newton’s law of universal gravitation (1) is calculated for all robots in the swarm so as to estimate attractive force applied to each of them. According to the law, it is stated that there occurs a force between two agents that is proportional to the product of their masses and inversely proportional to the square of the distance between them as illustrated in (1).

$$F = G \times \frac{{m_{1} \times m_{2} }}{{r^{2} }}$$
(1)

where F is the attractive force, m1 and m2 are the masses of each agent, G is the constant and r is the distance between centres of two masses. Total attractive force applied on the ith robot (R i A) in the swarm is defined as follows:

$$R_{i} A = \sum\limits_{j = 1}^{n} {\vec{F}_{j} }$$
(2)

2.2 Generic Grouping Algorithm

Randomly located robots in the swarm apply force and attract each other based on (2), as illustrated in Fig. 2. Afterwards, robots start moving in the direction of resultant force in order to approach each other that each robot continues moving until the applied attractive force exceeds a certain limit, as shown in Figs. 2 and 3. Stationary robots wait other robots to approach them until the predefined grouping number, ‘3’ for this example, is reached. This, in essence, provides a decentralized aggregation and grouping behaviour for robots without requiring any direct communication. Once the robots get close each other as request, the proposed algorithm achieves leader assignment in a decentralized manner. According to which, first, each robot calculates the relative position of each of the surrounding robots using range finder sensor. Next, each robot considers itself as the origin of its local coordinate system and observes other robots’ location to estimate at which quadrants they are placed in the coordinated system. Consequently, a robot is accepted as the leader of its group once other members are located in the same quadrants. An example scenario is shown in Figs. 4 and 5a, illustrating the leader assignment procedure. According to scenario shown in Fig. 4, each robot applies the given algorithm to select a leader for the group without performing any direct communication or employing a central decision mechanism. The decision mechanism of the algorithm for the given scenario works as follows:

Fig. 2
figure 2

Resultant force vectors of robots

Full size image
Fig. 3
figure 3

Robots approach to each other using force vectors

Full size image
Fig. 4
figure 4

Example scenario for grouping algorithm: a initial scenario illustrating applied forces, b generic grouping algorithm

Full size image
Fig. 5
figure 5

Example scenario for COG based navigation: a leader is calculated for the group, b coordinated motion of swarm based on COG

Full size image

  • For the first robot (shown in Fig. 5a), the second robot is at 1st quadrant but the third one is placed at the 4th quadrant.

  • For the second robot (shown in Fig. 5a), the first robot is at the 3rd quadrant but the third one is placed at the 4th quadrant.

  • For the third robot (shown in Fig. 5a), the first and the second robots are shown at the 2nd quadrant.

The results of the algorithm indicate that the third robot is the only one to be able to detect other robots at the same quadrant (shown in Fig. 5a), which makes it the leader of the group according to the aforementioned algorithm; whereas the first and the second robots realise that they cannot be the leader. In addition, the algorithm also enables members (other robots in the swarm) to directly detect the location of the leader. Accordingly, once the leader assignment algorithm is executed, each robot realises other robots’ role and location in a decentralized approach. The only exception to this algorithm occurs when all robots lie on the same line. In order to prevent this, an assumption is made that robots cannot be located initially on the same line.

2.3 Coordinated Motion of Swarm

A centre of gravity based navigation approach is addressed to execute the coordinated motion of the robots, from an initial position to the goal position. Once the leader assignment task is completed, the leader robot moves towards a specific goal while avoiding obstacles based on the potential field method (Khatib 1985). The method proposes an elegant solution to the challenging path finding problem. The attractive potential is assigned for the goal, whereas a repulsive potential is assigned for each of the obstacles in the environment. In general the scalar potential field P can be defined as:

$$P = P_{att} + P_{rep}$$
(3)

where P att and P rep represent attractive and repulsive forces correspondingly. The vector field of forces F(q) is given by the gradient of U:

$$F_{q} = -{\nabla}P_{att} + {\nabla}P_{rep}$$
(4)

The details of the potential filed method used in this study can be seen in Koren and Borenstein (1991) and Tang et al. (2010). As it is expected, one of the most critical issues in this framework is to be able to move robots in a coordinated manner.

As soon as the leader is selected, it is steered towards a specific goal according to the potential field method as aforementioned. Member robots, on the other hand, tend to stay in the group while the leader moves to a goal. Consequently, a simple but efficient method was proposed. According to which, the point referring the centre of gravity of the group is calculated by member robots, allowing them to both stay in the group and navigate along the direction of the leader.

The main idea lying behind the proposed navigation strategy is to assign an artificial mass to the COG point that applies a gravitational force to member robots. The COG point is updated continuously during the navigation behaviour of the leader robot, as illustrated in Fig. 5. The COG point is updated in each iteration of leader’s search procedure, resulting in instant change in applied gravitational force on member robots. Member robots are eager to move the direction of the COG point so as to keep the force applied on them at the limit value. This COG based navigation strategy allows member robots to stay in the group and prevent them colliding with obstacle. Coordination motion strategy is also designed in a decentralized manner. However it is assumed that robots’ known each other’s mass, which is the only limitation of the algorithm. Results of preliminary experiments revealed that assigning smaller mass to member robots than the leader provides more accurate coordinated motion behavior.

3 Evaluation of the System

In order to estimate the capability of the proposed work, the system has been evaluated using a simulator. The simulator was implemented by authors based on the Matlab toolbox. A series of simulations has been conducted to verify that the robots are able to navigate towards a goal in a coordinated and safe manner. The interface of the simulator allows users to add robots, obstacles and goals deliberately or randomly into the working environment. Algorithms of the proposed system can be visualized as a whole or individually. Table 1 summarizes the parameters employed for experiments that include initial parameters assigned for grouping and coordinated motion behaviors respectively. For instance, ‘G l ’ refers attraction force, applied between robots whereas ‘G bg ’, ‘O mass ’ and ‘R ’ mass refer mass values employed during the grouping behavior. On the other hand, ‘A mass ’ is considered as the most critical parameter for coordinated motion behavior, which denotes repulsive force applied between robots. This is in essence responsible from preventing collision between robots in the same group and allows those robots to move in a coordinated manner. Initial mass value, assigned to calculate COG is also given in the corresponding table that the mass of the leader and member robots are adjusted for the coordinated motion behavior.

Table 1 Parameter table for experiments
Full size table

A comprehensive example is shown and detailed in this section. Figures 6, 7 and 8 illustrate this example where there exists 9 robots, 5 obstacles and 3 goals in the corresponding scenario, as shown in Fig. 7, which also illustrates the critical grouping and leader selection behaviours for this example. Once the leader is assigned to each group, COG point is calculated (see Fig. 7) based on the parameters, shown in Table 1. Afterwards, the leader starts moving towards the goal with the potential field method. Shortly after the leader starts navigation, member robots are enabled and starts following the COG point which is modified continuously within the maneuver of the leader as illustrated in Fig. 8. This figure also demonstrates the paths followed by each robot that all robots achieve to reach the goal while avoiding collision with obstacles.

Fig. 6
figure 6

Grouping and leader assignment task

Full size image
Fig. 7
figure 7

COG are calculated for each group

Full size image
Fig. 8
figure 8

Groups achieve to reach the goal while preventing collision

Full size image

4 Conclusions

Decentralized control of multi-agent systems is a critical engineering field and has recently gained a lot of attention from researchers. In this manner, this paper proposes a new framework for aggregation and coordinated motion of swarm robots in a decentralized manner. The framework presents a generic grouping approach that groups robots in a hierarchical manner and allocates a leader for the group. The approach does not require any direct communication between robots and is designed using virtual physic-based algorithms. The leader robot of each group, possessing a map based navigation strategy, tends to move towards a specific goal while avoiding obstacles placed on its path. On the other hand, member robots, utilizing a COG based algorithm, move the direction of the leader while keeping themselves in the group with a safe and coordinated motion.

Simulation experiments reveal that the proposed framework achieves high degree of accuracy in complex scenarios. These results encouraged authors to conduct real word experiments with the proposed framework in order to assess the overall performance of the framework. Besides, an intelligent patter recognition module will be integrated into the proposed framework to separate obstacles from robots during the grouping and leader selection tasks. This will allow robots to ignore obstacles at the initial state and enhance the overall performance of the grouping algorithm.