A multi-robot task allocation algorithm based on universal gravity rules

Abstract

In this paper, a new multi-robot task allocation (MRTA) algorithm inspired by the Newtonian law of gravity is proposed. In the proposed method, targets and robots are considered as fixed objects and movable objects, respectively. For each target, a constant mass is assigned, which corresponds to its quality. The fixed objects (which refer to targets) apply a gravitational force to the movable objects (which are considered as robots) and change their positions in the feasible search space and therefore, the best target allocation of robots is determined by employing the law of gravity. In the proposed scenario, task allocation consists of assigning the robots to the found targets in a 2-D feasible area. The expected distribution is obtained from the targets’ qualities that are represented as scalar values. Decision-making is a distributed mechanism and robots choose their assignments, taking into account targets’ qualities and distances. Moreover, a control parameter is planned to make a remarkable balance between exploration and exploitation ability of the proposed algorithm. A self-adaptive mechanism is proposed to adjust the value of the exploration parameter automatically, aiming to maintain the balance between exploration and exploitation ability of robots. Furthermore, in order to decrease the time of reaching the target and accelerate computation, a selection memory is designed. In the experiments, we examine the scalability of the proposed method in terms of the number of robots and the number of targets and speed of algorithm to deliver robots to the desired targets with comparison to other competitors. The simulation results show the scalability of the algorithm, comparing the existing methods. Moreover, some non-parametric statistical tests are utilized to compare the results obtained in experiments. The statistical comparisons confirm the superiority of the proposed method compared over the existing methods.

1 Introduction

Multi-robot systems (MRSs) are a group of robots that are designed to perform some collective behavior. By this collective behavior, some goals that are impossible for a single robot to achieve become feasible and attainable. One of the most important reasons that the topic of MRSs has become more popular is the various future advantages of MRSs compared with single robot systems. These benefits include, but are not limited to, decreased task complexity, improving the system’s performance, decreasing the completion time for the defined tasks, improving reliability and simplicity in design (Nunes et al. 2017).

These benefits have attracted many researchers from academia and industry to investigate the applicability of MRSs in many applicable areas of industrial and commercial importance such as intelligent security, search and rescue, surveillance, and health care (Koes et al. 2006; Jahanshahi et al. 2017).

In order to develop and deploy robust MRSs in real-world applications, several challenging problems need to be solved. These problems include, but are not limited to, task allocation, group formation and self-organization, to name just a few (Schwarzrock 2018; Wang et al. 2016). In this paper, the task allocation problem as one of the challenging problems of MRSs is discussed in detail.

Multi-robot task allocation (MRTA) problem can be seen as an optimal assignment problem where the objective is to optimally assign a set of robots to a set of tasks in such a way that optimizes the overall system performance subject to a set of constraints (Lee 2018).

To study the MRS task allocation problem as an optimization problem, at first fitness function (or cost function) and the problem constraints should be defined.

Given a robot $r$ and a task $t$, if $r$ is capable of executing $t$, then one can define, the values ${Q}_{rt}$ and ${C}_{rt}$ are defined by the robot as the quality and cost of doing the task. It should be noted that the quality of a target is an application-specific scalar value that may represent the target’s priority or complexity, where a higher value requires more robots to be allocated. For example, it could represent the number of injured people in need of assistance in urban search and rescue scenarios. As another example, it could represent the richness of the mineral or water source on a planet that we want to harness. The medium by which these values are obtained is not considered in this paper. In other words, the quality values of the targets are deemed to be known and given.

Moreover, the cost of doing the task could be considered as distance or time of doing a task or the power that will be required to move and do a particular task.

Hence, we first need to express the unit definition for the fitness or utility function as follows (Gerkey and Matarić 2004):

$$U_{rt} = \left\{ {\begin{array}{*{20}c} {Q_{rt} - C_{rt}\, if \, the\, robot\, r\, has\, the\, ability\, to\, perform \,the\, task t } \\ { - \infty\, otherwise} \\ \end{array} } \right.$$

(1)

where ${{U}_{rt}=Q}_{rt}-{C}_{rt}$ if the robot can perform the task $t$. Otherwise, the value of $-\infty$ is attributed to the fitness function (Gerkey and Matarić 2004).

In order to solve the optimization problem, different methods have been proposed that can be categorized in general terms into three groups of the mathematical methods (Ren 2017), the use of game theory (Jang et al. 2018; Tang and Parker 2007), and using of heuristic search algorithms (Jang et al. 2018).

Most of the mathematical methods use the set theory principle to solve MRTA problems. Because of computational complexity, the mathematical problems have been less welcomed. The second one is based on game theory, which can be referred to as a distributed market-based approach (Kanakia et al. 2016). From another perspective, the use of heuristic or meta-heuristic algorithms is utilized considering the simplicity and acceptable accuracy of solving problems, and somewhat due to the similarity to multi-robot systems.

Each MRTA method has its advantages and disadvantages in task allocation of different types of problems. Therefore, many MRTA methods have been proposed to rectify the disadvantages of these algorithms. Also, some researchers tried to suggest new algorithms inspired by nature. In this paper, a nature inspired MRTA algorithm is introduced by employing the Newtonian law of gravity. In the following, the related works are reviewed.

1.1 Related works

By reviewing the literature, it was found that different optimization approaches have been used in order to solve the general task allocation problems and MRTA problem.

Gerkey and Mataric (Gerkey and Matarić 2004) provide a taxonomy for MRTA problems based on the number of tasks, the number of robot, and the schedule for allocation. Based on Gerkey and Matarić (2004), there is some group such as Single-Task or Multiple-Task (ST-MT) robots, Single-Robot or Multiple-Robot (SR-MR) Tasks, and Instantaneous or Time extended Allocation (IA-TA).

Authors in Khamis et al. (2015) describe three of the most commonly used MRTA approaches: namely game theory-based approaches, mathematical optimization-based approaches, and heuristic-based approaches. Market-based approach as a game theory approach gained considerable attention within the robotics research community because of several desirable features, such as efficiency in satisfying the objective function, robustness, and scalability (Jang et al. 2018; Zlot and Stentz 2006). The market-based approach, which can be considered as a game theory approach, is an economically inspired approach that provides a way to coordinate the activities between robots/agents. Market-based approach is mainly based on the concept of auctions. Based on economic theory principles, an auction is defined by any mechanism of trading rules for exchange (Lagoudakis, et al. 2006; Guerrero and Oliver 2003). In other words, an auction can be considered a process of assigning a set of goods or services to a set of bidders according to their bids and the auction criteria. It can be concluded that auctions are simple and conventional ways of performing resource allocation in a multi-agent system.

It is worth mentioning that although market-based approaches have many advantages, they are not without their disadvantages. The lack of formalization in designing appropriate cost and revenue functions to capture design requirements can be considered the biggest drawback of market-based approaches (Korsah et al. 2013; Zlot et al. 2002).

Mathematical optimization-Based Approaches are the branch of applied mathematics focusing on solving a specific problem to find the optimum solution for this problem out of a set of possible solutions (Parker and Tang 2006). A set of possible solutions is restricted by a set of constraints, and the optimum solution is chosen within these constrained solutions according to specific criteria. This criterion defines the objective function of the problem that quantitatively describes the system (Lerman 2002). There is a wide variety of optimization approaches available, and the use of these approaches depends on the nature and the degree of complexity of the problem to be optimized (Lenagh 2013). Deterministic techniques include numerical and classical methods such as graphical methods, gradient, and Hessian based methods, derivative-free approaches, quadratic programming, sequential quadratic programming, penalty methods, etc. (Balas and Padberg 1976). In Atay and Bayazit (2006), a mixed-integer linear programming optimization approach was used in order to allocate heterogeneous robots for maximizing the coverage area of the regions of interest. Also, in Darrah et al. (2005), a mixed-integer linear programming approach was used for solving the task allocation problem in the context of UAV cooperation.

More and more attention has been given to using nature-based inspired algorithms to solve MRTA problems (Mosteo 2010). Moreover, many MRTA methods have been made by hybridizing different types of evolutionary algorithms (Yi 2017).

Heuristic search algorithms always have some randomness. These techniques can be classified into trajectory-based and population-based algorithms. A trajectory-based meta-heuristic algorithm, such as Simulated Annealing (SA) uses a single agent or solution which moves through the design space or search space in a piece-wise style. On the other hand, population-based algorithms such as Genetic Algorithms (Gas), Ant Colony Optimization (ACO), Particle Swarm Optimization (PSO), Gravitational Search Algorithm (GSA) and Immune Optimization Algorithm (IOA) use multiple agents to search for an optimal or near-optimal solution (Benabderrahmane 2017). In Mosteo and Montano (2006), SA approach was used to solve the allocation of MRS through formulating the MRTA problem as a Travel Salesman Problem (TSP). In Juedes et al. (2004) and Kmiecik et al. (2010), SA incorporated with other heuristic approaches was used to allocate a set of tasks to several processors in computer system problems.

The GA was used in Shea et al. (2003) to provide a feasible solution for group tracking, which is capable of tracking several targets rather than individual targets. GA was also used in Jones et al. (2011) to provide a solution for the time extended task allocation of multi-robots in an application of simulated disaster scenarios. ACO algorithm as another technique of the population-based optimization approaches was used in Zlot and Stentz (2006) to solve the task allocation problem of MRSs. In Ding et al. (2003), ACO was used in the context of multi-robot cooperation to solve the task allocation problem. The task allocation problem was also solved using hybrid optimization approaches such as tabu search with random search method in Liu and Kulatunga (2007). In Liu and Kulatunga (2007), a simultaneous approach for solving the path planning and task allocation problems for an MRS is proposed, where SA and ACO approaches were investigated and applied for solving the problem. In Huang et al. (2018), a niching immune-based optimization algorithm based on Softmax regression (sNIOA) is presented to handle MRTA problem. Furthermore, a guiding mutation operator inspired by the base pair in the theory of gene mutation is introduced into sNIOA to strengthen its search ability.

In Jevtic et al. (2011), the Distributed Bee Algorithm (DBA) has been used to solve MRTA. In Jevtic et al. (2011), a scenario consisting of a community of homogeneous robots in terms of hardware and software (or some distinct groups of robots), the number of targets and their location in the environment are identified for robots. Also, each robot is unaware of the size of the community and the distribution of other robots, and each robot at any moment can perform a maximum of one of the tasks. In Tkach et al. (2018) the Modified Distributed Bee Algorithm (MDBA) has been used to solve MRTA problem for the general problem of heterogeneous robots and target quality.

In summary, the scenario can be defined as finding targets with the least energy loss due to the unnecessary rotation of robots in the environment and the absorption of robots in proportion to the target's values.

1.2 Challenges and motivation

Some of the significant challenges in MRTA algorithms are the ability to deal with the variable number of robots and targets as well as imbalanced targets qualities i.e. the scalability of the algorithm. The aim of this paper is to propose a nature-inspired MRTA algorithm, which can overcome some problems like imbalanced targets qualities, different numbers of robots and sensitivity to the initial position of robots. In the proposed MRTA algorithm, we consider the targets as fixed celestial objects with the pre-determined mass (based on quality of target) to apply a gravitational force to movable objects (robots) and change their positions in the feasible search space. The aim is to find the best allocation of robots where each robot is modeled by a movable agent with the unity mass. The robots move around the feasible search space in the influence of the gravitational force exerted by the celestial objects to find the best position. One can expect that the robots assign optimally to the targets. Moreover, in order to decrease time of delivering robots to targets and accelerate procedure of algorithm, selection memory is designed.

The rest of the paper is organized as follows. In the next Section, the basic concepts of multi-robot task allocation and the Newton's law of universal gravitation are reviewed and their properties are discussed. Section 3 is devoted to describing the proposed gravity algorithm. A comparative experimental study is given in Sect. 4. Finally, we conclude the paper in Sect. 5.

2 Basic concepts

2.1 Problem definition

Based on the represented taxonomy in Gerkey and Matarić (2004), the multi-robot system, which is used in this paper, is categorized as homogeneous and distributed, using broadcast communication. In other words, we tend to address the problem of single-task robots, multi-robot tasks and instantaneous assignment (ST-MR-IA) (Gerkey and Matarić 2004). In the utilized task allocation scenario, the setting that contains variety of tasks is considered that could be of same or completely different importance and robots that are equally capable of performing each task but each one can only be assigned to one at any given time. It should be noted that the quality of a target is a scalar value that represents the target’s priority or complexity, where a higher value requires more robots to be allocated. In this paper, we do not consider how these values are obtained. The proposed scenario in this paper is found under the following assumptions:

• All the targets are made accessible to all the robots. To reach this aim, the broadcast communication range setting of the robots cover the entire feasible search space.

• Robots make decisions among all the targets in the feasible area simultaneously. The total number of targets and the positions of the targets are saved in robots’ internal memory and they are changed based on the experimental setup.

• Reallocation to a different target is not allowed for each time step of the robot’s movement.

Note that the above assumptions are considered for simplicity and can be modified based on problem definition.

Consider a population of $R$ robots to be allocated among $T$ targets. Let $Q \in \{{q}_{1}, . . . , {q}_{T}\}$ represents the set of normalized qualities of all accessible targets, ${{n}_{t}}^{itr},$ $t \in \{1, . . . , T\}$ as a nonnegative integer shows the number of robots allocated to target $t$ in iteration of $itr$ (i.e. time slot of robot movement).

Note that, the normalized qualities of all targets are evaluated as follows:

$${q}_{t}=\frac{{Q}_{t}}{\sum_{t=1}^{T}{Q}_{t}}$$

(2)

where ${Q}_{t}$ is the quality of $t$-th target and $T$ is the number of targets.

It should be considered that for the proposed scenario, the combined utilities of the robots are unknown as robots have no knowledge of the decisions taken by other robots, therefore, the system optimization based on the maximum utility cannot be applied.

2.2 Newton’s law of universal gravitation

The gravitation is the tendency of masses to accelerate toward each other. Newtonian law of universal gravity is one of the most important laws in all scientific subjects. Newtonian law of universal gravity states that any two objects in the universe attract each other with a force that is directly proportional to the product of their objectives and inversely proportional to the square of the distance between them (Benabderrahmane 2017; Rashedi et al. 2009). This is a general physical law derived from empirical observations by what Newton called induction. Every point mass attracts every single other point mass by a force pointing along the line intersecting both points as follows:

$$F\left({m}_{1},{m}_{2}\right)=G\frac{{m}_{1}{m}_{2}}{{d}^{2}}$$

(3)

where $F$ is the gravitational force between two point objects, ${m}_{1}$ and ${m}_{2}$ are the masses of two objects, $d$ is the Euclidean distance between ${m}_{1}$ and ${m}_{2}$, and $G$ is the gravitational constant.

3 Gravity based MRTA algorithm: GBMRTA

In order to start the basic idea of paper, consider a population of $R$ movable robots to be allocated among $T$ fixed targets. Let $Q \in \{{q}_{1}, . . . , {q}_{T}\}$ denotes the set of normalized qualities of all available targets. Moreover, it is assumed that each individual robot is located at position ${P}_{r}$, in a 2-dimensional search space. The main idea in the proposed algorithm is to consider a movable gravity object (robot) as a movable mass and each target as a fixed gravity object. In this gravity system, the fixed objects (i.e. targets) apply the gravitational force to the movable objects (i.e. robots) and change their positions in the feasible search space. The proposed algorithm is able to deal with different numbers of robots and targets without any sensitivity to their initial distributions and it has an excellent performance to handle unbalanced targets. This is due to the nature of Newton's gravity law in which the gravitational force between two objects is inversely proportional to the distance between them. Therefore, the initial distributions of robots and targets have no significant effects on the final allocation of robots to targets. Furthermore, the comprehensive description of the problem definition is depicted in Fig. 1.

Fig. 1

Applied gravitational force to each agent, circles show targets and stars show robots

In this figure, two types of objects are shown in stars, and circles instances for the robots (or movable objects/agents) and targets (fixed objects/masses), respectively. Arcs out of the star also represent gravitational forces that are applied by fixed objects. Decision making of each robot is proportional to the value of the total force exerted on the agent (robot) by the fixed objects (targets). It is expected that agents move towards the fixed mass of gravity and stop in an area where the robot reaches the selected target. It should be noted that targets as fixed objects are not allowed to apply force to each other.

The proposed MRTA algorithm is explained with the following steps:

Step 1: Initialize the algorithm parameters including the number of robots ($R$), the number of targets ($T$), mass of targets (${m}_{t})$, maximum number of iteration ($ITR$) (total time), parameters used in the law of gravity (${G}_{0}$) and robot position $P=\{{P}_{1},\dots , {P}_{R}\}$.

Step 2: Generate randomly positions initial of $R$ robots $P=\{{P}_{1},\dots , {P}_{R}\}$ and set mass values of these objects to one. In other words, the robots positions $\left\{{P}_{1},\dots , {P}_{R}\right\}$ are randomly initialized where ${P}_{r}$ is a 2-dimensional parameter in search space which is shown by (${x}_{r}, {y}_{r})$.

Step 3: Repeat the following until the maximum number of iterations is reached.

3-1: The gravitational force applied to the robot $r$ from targets $t$ is computed as follows:

$$F_{r}^{t} = G_{t} \frac{{m_{t} m_{r} }}{{(d_{r}^{t} )^{\varphi } + \varepsilon }}$$

(4)

$$d_{r}^{t} = \sqrt {\left( {x_{t} - x_{r} } \right)^{2} + \left( {y_{t} - y_{r} } \right)^{2} }$$

(5)

where $({x}_{t},{y}_{t})$ and $({x}_{r},{y}_{r})$ represent target’s and robot’s coordinates in the arena, respectively, and ${m}_{t}$ and ${m}_{r}$ present mass values of the fixed object $t$ (target) and robot $r$, respectively; ${m}_{t}$ is normalized target quality and ${m}_{r}$ is set to 1 for $r=1,\dots , R$, ${d}_{r}^{t}$ is the Euclidean distance between agent $r$ and target $t$ defined as Eq. (5) and $\varphi$ is a parameter of the algorithm which tunes the effect of distance on the calculation of the force. Moreover ${G}_{t}$ is a parameter of the algorithm which tunes the exploration/exploitation of algorithm. Therefore, in our proposed algorithm, the gravitational parameter ${G}_{t}$ is considered as an adaptive controlling parameter of exploration and exploitation. To design an acceptable gravitational parameter ${G}_{t}$ two ways are proposed which is explained later.

3-2: All calculated forces to each robot $r$ from targets in step 3–1 (Eq. 4) is normalized as follows:

$$f_{r}^{t} = \frac{{F_{r}^{t} }}{{\mathop \sum \nolimits_{t = 1}^{T} F_{r}^{t} }}$$

(6)

3-3: The wheel-selection rule is applied as a decision-making mechanism of the proposed GBMRTA.

In wheel-selection rule, as in all selection methods, ${f}_{r}^{t}$ assigns probability value to possible targets. This fitness level is used to associate a probability of selection with each individual target. In other words, If ${F}_{r}^{t}$ is the effected force of target $t$ to robot $r$ then the probability of being selected for target $t$ is ${f}_{r}^{t}$.

It should be considered that if selection procedure is done in each iteration, it will confuse the robot and increases the number of iterations that is needed to reach the target. To solve this issue, the selection procedure is applied every $\Phi$ iteration which named selection memory of algorithm. Note that in order to increase the performance of selection memory approach, $\Phi$ is considered as an adaptive value and evaluate as follow:

$$\Phi = round\left( {\Phi i*\left( {\frac{\Phi f}{{\Phi i}}} \right)^{{\frac{itr}{{ITR}}}} } \right)$$

(7)

where $\Phi i$ and $\Phi f$ illustrate the selection memory of algorithm in the first iteration and in the last iteration respectively (by the condition of $\Phi i\ll \Phi f$) and $itr$ and $ITR$ show the current iteration and the maximum number of iteration, respectively. Based on simulation results, the selection memory approach causes a significant decrement in iterations which is needed to reach the desired target. It can be concluded that the computational procedure can be accelerated through the way of decreasing the time through the selection memory approach.

3-4: Then, each agent (robot) $r$ must move toward selected target ${ST}_{r}$ based on its determined speed.

3-5: repeat the above steps until the stopping criterion is met.

Output of GBMRTA algorithm: optimal partitions $ST\{{ST}_{1},\dots , {ST}_{R}\}$.

In this algorithm, if premature convergence happens, there will not be any recovery for the algorithm. In other words, after becoming converged, the algorithm loses its ability to explore and then becomes inactive.

Heuristic algorithms must have an acceptable balance between exploration and exploitation (also termed diversification/ intensification) to achieve both efficient global and local searches. In this way, they can efficiently solve optimization problems. As another point of view, losing the balance between exploration and exploitation may lead to premature convergence. Exploration is the ability to investigate the search space for finding new and better solutions, and exploitation is the ability to look for the optimal solution near a good one. The abilities of exploration and exploitation in every heuristic algorithm are applied with specific operators. Since each operator has its abilities of exploration and exploitation, the operators should be artfully hybridized together for a good trade-off between exploitation and exploration.

In simple words, all robots are randomly distributed in a feasible environment in the first iteration. In the following, based on the position and the quality of each target and also by applying the proposed GBMRTA algorithm, each robot selects a target. In the next iteration, all robots move one step toward the selected target and send the report to the selected targets. By collecting the information of robot in the targets, the ${c}_{t}$ as a percent of the selected target $t\in \{1, . . . , T\}$ by robots is calculated for each target. Moreover, the control parameter of ${G}_{t}$ is evaluated.

By applying the new control parameter of ${G}_{t}$ the applying force by targets are modified in order to decrease the difference between ${m}_{t}$ (expected percent of the selected target) and ${c}_{t}$.

In can be concluded that, ${G}_{t}$ is the control parameter that allows us to bias the decision-making mechanism toward the quality of the solution or its cost, respectively.

In this paper, to find the best definition of ${G}_{t}$ parameter two main approaches are proposed that are discussed in Appendix A. Fractional and Exponential definition are two proposed approach to have a balance between exploration and exploitation. Based on experimental results in Appendix A, fractional formulation has better performance in comparison with exponential formulation. Consequently, ${G}_{t}={(\frac{{m}_{t}}{{c}_{t}+\varepsilon })}^{1.35}$ is considered as the adaptive formulation of gravitational parameter, $\varepsilon$ is a small positive number to avoid dividing by zero, ${c}_{t}$ is the percent of selected target or the resulting robots’ distribution and ${\mathrm{m}}_{\mathrm{t}}$ is expected percent of selected target or expected robots’ distribution.

In simple words, if ${c}_{t}>{m}_{t}$ which means that target $t$ attract robots more than it’s requiring. Then ${G}_{t}={(\frac{{m}_{t}}{{c}_{t}+\varepsilon })}^{1.35}$ is decreased in order to decrease the discrepancy between the expected (${m}_{t}$) and the resulting robots’ distribution (${c}_{t}$). Moreover, if ${c}_{t}<{m}_{t}$ which means that target $t$ attract robots less than it’s requirement. Then ${G}_{t}={(\frac{{m}_{t}}{{c}_{t}+\varepsilon })}^{1.35}$ is increased in order to attract more robot to target $t$.

Algorithm1 illustrate the pseudo code of proposed GBMRTA algorithm.

Some notes regarding the proposed algorithm should be mentioned as below:

• The final robots’ distribution and target selection depend on their initial distribution in the feasible search space, i.e. their distances from each target prior to the target allocation.

• Due to the distributed nature of scenario, combined robots utility cannot be computed, as a result, the quality of the targets is used as the only measure for the expected robots’ distribution.

• Due to the force applying to each agent (robot) from its neighborhood fixed points (targets), it can attract space around itself.

• To compute the force acting on the agent (robot) in Eq. (4), a control term ${G}_{t}$, has been adjusted. We use this parameter to control the balance between exploration and exploitation of the algorithm. This will helps the algorithm to escape from a local optimum, so the dependency on the initial robots’ distribution is reduced.

• Control parameter of ${G}_{t}$ adjusts the accuracy of the search. In other words, this parameter tries to help the algorithm to reach the determined quality of targets.

• In order to avoid collision between robots, a communication range is considered for each robot. The main idea of the proposed target search algorithm is that if two or more robots be in the communication range of each other, the nearest robot to the target position will get the highest priority. Moreover, when two or more robots have the same distance with their selected target position, one of them will get the highest priority randomly. It should be added that the non-prioritized robot will be idle until the prioritized robot passes away from its communication range. If the idle time is equal to an iteration, the robot rediscovers the target during this iteration; otherwise, it moves toward the allocated target in the current iteration.

• We assume that a robot is able to check for collisions between its own planned path and another robot’s path. To facilitate this, we assume all their clocks are synchronized. Messaging delay can be accommodated; however, it must be negligible with respect to robot dynamics. We assume that robot detections are always happened when they come into communication range.

3.1 Fault handling

Each of the local and global activities in MRS might suffer from different faults, which disrupts the entire MRS. Some faults which an MRS might encounter can be defined as individual robot malfunctions, local perspectives that are globally incoherent, inter-robot interference, software errors or incompleteness, and communications failures.

In this paper, we focus on two fundamental types of faults, which are at the core of the “multi” aspect of multi-robot systems: the global fault and local fault.

• Global fault handling.

  In the global scope, all robots are randomly distributed in a feasible environment in the first iteration. Based on the position and the quality of each target and by applying the proposed GBMRTA algorithm, each robot selects a target. In the next iteration, all robots move one step toward the selected target and send the report to the selected targets. By collecting the information of robot in the targets, the ${\mathrm{c}}_{\mathrm{t}}$ as a percent of the selected target $\mathrm{t}\in \{1, . . . ,\mathrm{ T}\}$ by robots is calculated for each target.

  It should be noted that ${\mathrm{c}}_{\mathrm{t}}$ and ${\mathrm{m}}_{\mathrm{t}}$ (expected percent of the selected target) are not the same, which causes the global fault in the MRS. To solve this issue, a control parameter of ${\mathrm{G}}_{\mathrm{t}}$ is proposed in this paper.

  By applying the control parameter of ${\mathrm{G}}_{\mathrm{t}}$ the applying force by targets are modified in order to decrease the difference between ${\mathrm{m}}_{\mathrm{t}}$ (expected percent of the selected target) and ${\mathrm{c}}_{\mathrm{t}}$.

• Local fault handling.

As a local scope in MRS, for a variety of reasons, there exists the probability of collision between robots. In order to avoid collision between robots and based on practical considerations, a communication range is considered for each robot. The main idea of the proposed target search algorithm is that if two or more robots are in the communication range of each other, the nearest robot to the target position will get the highest priority. Moreover, when two or more robots have the same distance with their selected target position, each robot will randomly get the highest priority.

Nonetheless, to some extent, the general elements of fault handling depicted in the following figure (Fig. 2).

Fig. 2

The general elements of fault handling in the proposed method

In the following section the performance of proposed algorithm is evaluated.

4 Experimental evaluation

In the following, we describe the evaluation criteria, simulation environment and experimental results.

4.1 Evaluation criteria

The following performance measures were analyzed to compare the different allocation algorithms:

• Tasks completion time or average iteration to reach target ($\mathrm{AIT}$).

The overall task completion time $\Gamma$ is defined as an average of the individual tasks completion iterations:

$$\Gamma = \frac{1}{R}\mathop \sum \limits_{r = 1}^{R} \gamma_{r}$$

(8)

where ${\gamma }_{r}$ is the number of iteration that robot $r$ is needed to reach the selected target. In simple words, the task completion time is derived by the average amount of time elapsed from robots that arrive at the selected target. From another point of view, the average iteration to reach the target (AIT) has a direct relation with the number of fitness function evaluations.

The number of fitness function evaluations (FEs) can be considered as an evaluation criterion for heuristic search algorithms. This practice has been advocated in a number of competitions to compare the performance of population-based algorithms and has been used in many articles that contain empirical comparisons of algorithms. In this paper, average FEs or AIT is considered as a computational criterion for comparing different methods.

• Mean absolute error ($MAE$) of the final robots’ distribution

As mentioned before due to distributed nature of scenario, it is impossible to define the combined robots utility. Therefore, we define the mean absolute error ($MAE$) of the final robots’ distribution, which is given by:

$$MAE = \frac{1}{T}\mathop \sum \limits_{t = 1}^{T} |c_{t} - m_{t} |$$

(9)

As the name suggests, the mean absolute error is the average value of the absolute distribution error (per target) that is the result of discrepancy between the expected (${m}_{t}$) and the resulting robots’ distribution (${c}_{t}$).

4.2 Simulation environment and experimental results

Without loss of generality, our simulation platform is a specialized multi-robot simulator for the e-puck robots described in Jevtic et al. (2011). The e-puck is a small cylindrical wheeled mobile robot that holds eight IR¹ proximity sensors distributed around the body. The e-puck can be modeled as a cylindrical object of 3.5 cm in radius. Based on IR proximity sensors, the communication range of the e-puck Range was set to cover the whole feasible search space. Note that the feasible search space is considered as a rectangle-shaped 1.5 × 2.125 m² simulation area, but it can be easily extended to relatively complicated geometries.

In order to have a thorough comparison on the performance of algorithm, the proposed GBMRTA is compared to the original DBA (Jevtic et al. 2011), MDBA (Tkach et al. 2018), LRDBA, ERDBA, TBDBA, a Greedy Algorithm (GrA) (Broadcast of Local Eligibility for Multi-Target Observation 2002), a Market-Based Algorithm (Zlot et al. 2002) and NIOA (Huang et al. 2018) which were implemented to fix the task allocation problem, as described in Appendix B.

In Table 1, the feasible search space and the experimental duration are defined.

Table 1 Parameters describing the feasible search space and the experimental duration in Experiments

It should be mentioned that in the proposed GBMRTA algorithm the initial and final selection memories are set as $\varphi i=10$ and $\varphi f=1000$ respectively; moreover gravitational parameter of algorithm is evaluated by power formulation as follows ${G}_{t}={(\frac{{m}_{t}}{{c}_{t}+\varepsilon })}^{1.35}$.

Additional experimental setups are explained as follows:

In the DBA algorithm the control parameters α and β are same ($\alpha =\beta =1$). As the homogeneous property of robots in this paper, ${V}_{ik}^{\chi }$ = 1 for all robots in MDBA method and the deadline for doing a task is evaluated based on quality ${\Delta }_{i}=\frac{1}{{q}_{i}}$. In the tournament based selection strategy of TBDBA, the tournament size is defined by $K=round (T/2)$, where $T$ is the number of targets (tasks).

The control parameter of MBA is defined as $\delta =0.5$ and the experimental parameters of sNIOA are set based on Huang et al. (2018).

Three different experimental setups have been chosen to compare and study the performance and scalability of the proposed algorithm. The setups were carried out in the same feasible search space where the number of robots, the number of targets and target’s quality are different.

Fifty experiments were performed for each of the following swarm sizes. For all figures, the number of robots is set as 20 robots, 60 robots and 100 robots.

Figure 3 illustrates the radar chart comparison MAE of different methods on two targets with the same quality values. It should be noted that the utilized axis is designed in “reverse order” as a result of $MAE$ minimization function.

Fig. 3

Radar (spider) chart illustrates the MAE comparison for the task allocation problem of two targets with the same quality values

We can notice that effectiveness of the algorithm increases as the size of the robot swarm increases. This was expected because of the probabilistic target allocation mechanism applied in the proposed algorithm. Moreover, in all scenarios which are plotted in Fig. 3 the proposed method has a superior performance compared to other algorithms.

In Fig. 4, the radar chart comparison MAE of different methods on two targets with different quality values (0.3 and 0.7) is illustrated.

Fig. 4

Radar (spider) chart illustrates the MAE comparison between 8 methods and proposed GBMRTA method for the task allocation problem of two targets with different quality values.

Based on Fig. 4, the proposed method has a superior performance compared to other algorithms due to the ability of gravity rules for solving the task allocation problem and tuning parameter of ${G}_{t}$.

Moreover, in Fig. 5, MRTA for two unbalance targets with different quality values (0.1 and 0.9) is discussed.

Fig. 5

Radar (spider) chart illustrates the MAE comparison between 9 methods [two targets with different quality values (0.1 and 0.9)]

Figure 5 confirms the ability of the algorithm for unbalance targets, which as a result of using the control parameter of ${G}_{t}$. It can be verified that by increasing the difference between the qualities of targets, the performance of the proposed method is significant in comparison with other methods.

Figure 6 illustrates the radar chart MAE comparison on four targets of same quality values. The results show that the performance of algorithm increased for larger swarms in case of four targets of the same quality.

Fig. 6

Radar (spider) chart illustrates the MAE comparison between 9 methods for MRTA of four targets with same quality

In order to test the ability of the robot swarm to conform to a nonuniform distribution of “tasks” in the feasible search space, the experiments were performed for four targets with different quality values. To reach this aim, the qualities of 4 targets are considered 0.1, 0.2, 0.3 and 0.4. The robots’ distribution changed according to a new set of targets’ quality values, as shown in Fig. 7. In the same, figure we can also notice that for the DBA algorithm, the resulting robots’ distribution, with respect to the expected distribution, is slightly in favor of the less valuable targets which happen as a result of non-adaptive parameters of DBA algorithm. In comparison, the proposed method has the ability to confront by non-uniform distribution of targets as a result of the control parameter of ${G}_{t}$.

Fig. 7

Radar (spider) chart illustrates the MAE comparison between 8 method and proposed GBMRTA method for MRTA of four non-uniform quality targets

Figure 8 illustrates the radar chart comparison of $\Gamma$ which is named as Average Iteration to reach Target ($AIT$) (Eq. 8) of different methods on two targets with different quality values (0.3 and 0.7). It should be noted that the utilized axis is designed in reverse order as a result of $AIT$ minimization function.

Fig. 8

Radar (spider) chart illustrates the AIT comparison the task allocation problem of two targets with different quality values

We can notice that MBA, GrA, sNIOA, and proposed method have the ability to deliver robots to the desired targets in fewer numbers of iterations in comparison with other methods. It should be noted that based on Eqs. (15) and (21) MBA and GrA select the target based on a greedy approach which cause decreasing in the time of arrival to the target and as a drawback causes increasing in MAE value. Achieving a less $AIT$ in sNIOA algorithm is a result of selection in the first iteration and not to change it during the process of algorithm which causes the increment in MAE value similar to MBA and GrA as a main drawback of the algorithm.

As mentioned before, the proposed approach in AIT comparison has a similar behavior as MBA, GrA, sNIOA which is a result of the selection memory parameter. Note that selection memory approach has a significant effect on decreasing iterations which is needed to deliver robots to the desired targets.

Experiment results that are discussed above show that the proposed method achieves a lower average MAE rate in the vast majority of experiment cases. However, this observation-based evaluation does not reflect whether or not the differences among the methods are significant. To solve this issue, the statistical test is used to make sure that the difference is significant, that is, very unlikely to be caused by chance—the so-called p-value of the test (Sheskin 2007). To evaluate the performance of the proposed method, Friedman test is applied which is a non-parametric statistical analysis based on multiple comparisons procedures. In order to perform multiple comparisons, it is necessary to check whether all results obtained by the algorithms present any inequality. Friedman test ranks the algorithms for each data set separately, the best performing algorithm obtaining the rank of 1, the second-best rank 2, and so on. In case of ties, the average ranks are assigned. Under the null-hypothesis, it is stated that all the algorithms are equivalent, so a rejection of this hypothesis implies the existence of differences among the performance of all the algorithms studied. In simple words, Friedman test can be considered as a hypothesis testing procedure.

According to statistic principles, hypothesis testing can be used to obtain inferences about one or more algorithms from the given sample. This can be achieved by defining two types of hypothesis, the null hypothesis ${H}_{0}$ and the alternative hypothesis ${H}_{1}$. The null hypothesis is a statement of no effect or no difference, whereas the alternative hypothesis represents a significant difference between algorithms. Friedman’s test is a comprehensive test which can be used to carry out these types of comparison. It allows us to detect differences, considering the global set of algorithms. Table 2 contains the results of Friedman Aligned test. The average ranks obtained by each method in the Friedman test are presented in Table 2.

Table 2 Average rankings of the compared algorithms (Friedman)

Note that Friedman test is applied to MAE comparison data. It should be noted that in Friedman test, achieving a lower-ranking value reflects the superiority of the algorithm. As Table 2 shows, the proposed algorithm attains the lowest ranking value among other competitors.

In addition, the comparison of the proposed method vs. other algorithms by Holm post–hoc procedure for Friedman Aligned test is described in Table 3. Table 3 shows the p-value with the Holm post-hoc test on a performance measure, which determines the validity of the corresponding ranks in Table 2.

Table 3 The proposed method vs. other algorithms by Post Hoc comparison table for $\alpha$ = 0.05 (Friedman test)

Holm Post–Hoc procedure is a multiple comparison procedure that can work with the best algorithm (which is the best, according to Friedman rankings computation) and is compared with the remaining methods.

It should be mentioned that the proposed method is considered as the best algorithm according to Table 2.

Note that, a p-value smaller than 0.05 indicates that the null-hypothesis can be rejected. In other words, Post-Hoc comparison procedure verifies that the proposed method performs better than all other approaches, because most approaches have a p-value $\le 0.05$. Moreover, $\mathrm{Li}$’s procedure rejects those hypotheses that have a $\mathrm{p}-\mathrm{value }\le$ 0.029549.

This test also verifies the effectiveness of the proposed method. It is clearly shown in Table 3 that our proposed method can reject the other algorithms with most of the time significant difference.

In Friedman Aligned test, the proposed method achieved the best ranking with the obvious differences with other methods. The Friedman Aligned test emphasizes that the proposed method of this paper can outperform other compared algorithms in the defined multi-robot task allocation scenario.

5 Conclusion

In this paper, a new nature inspired multi-robot task allocation algorithm based on Newtonian law of gravity was presented. Various applications for large MRS require efficient task allocation in terms of individual and combined robots’ utilities. The quality of the solution is analyzed using a defined performance metrics, which in our case was MAE (a mean absolute error of the resulting robots’ distribution with respect to the qualities of the available targets in the robot feasible search space) and AIT (Average Iteration to reach Target). In the case of large, autonomous, multi-robot systems, the scalability and the ability to adapt to different environments are the features of utmost importance. Our experiments through simulation showed that the proposed GBMRTA provides the robot swarm with scalability in terms of the number of robots and the number of targets. The proposed GBMRTA has an acceptable exploration and exploitation ability. The importance of the control parameter, ${G}_{t}$ is that it provides a mechanism to adjust the robot swarm behavior depending on the quality of tasks. Furthermore, the proposed selection memory approach has the ability of decreasing time of reaching target and accelerating computation. It can be concluded that simulation results clearly demonstrated the high performance and efficiency of our proposed method. Moreover, this claim was confirmed by the results of Friedman test as a nonparametric comparison approach.

Appendices

Appendix A

1.1 Performance evaluation of two proposed gravitational parameters

In order to find the best definition of ${G}_{t}$ parameter two main approaches are proposed that are discussed in detail:

(A) Fractional definition

To strive for a balance between exploration and exploitation in the optimization process of the proposed method, we propose a self-adaptive mechanism which can get feedback from the current population to control the value of ${G}_{t}$. ${G}_{t}$ is the control parameter that allows us to bias the decision-making mechanism toward the quality of the solution or its cost, respectively.

To evaluate adaptive, firstly, $c_{{\text{t}}} { }$ as a percent of the selected target $t \in { }\left\{ {1,{ }.{ }.{ }.{ },{ }T} \right\}$ by robots is calculated as follows:

$$c_{t} = \frac{{n_{t} }}{R}\quad t{ } \in { }\left\{ {1,{ }.{ }.{ }.{ },{ }T} \right\}$$

(10)

where $n_{{\text{t}}}$ present the number of robots which select the target $t$ and $R$ is the total number of robots.

It should be explained that based on MRTA problems, MAE is one of the most crucial criterion. In order to decrease the MAE value, the difference between $c_{t}$(percent of selected target or the resulting robots’ distribution) and ${\text{m}}_{{\text{t}}}$ (expected percent of selected target or expected robots’ distribution) should be decreased.

To reach this aim in our proposed algorithm, the gravitational parameter $G_{t}$ is considered as an adaptive controlling parameter which is evaluated as follows:

$$G_{t} = \left( {\frac{{m_{t} }}{{c_{{\text{t}}} + \varepsilon }}} \right)^{\alpha }$$

(11)

where $\varepsilon$ is a small positive number to avoid dividing by zero and $\alpha$ is a parameter of the algorithm which tunes the effect of $G_{t}$ on the calculation of the force.

(B) Exponential definition

$$G_{t} = \beta^{{c_{t} - m_{t} }}$$

(12)

In the following, the performance of two proposed gravitational parameters are evaluated. To reach this aim, Figs. 2 and 3 illustrate the MAE versus variable value of alpha for gravitational constant 1 and 2 when the number of robot is 100.

Fig. 9

MAE versus varying value of alpha for fractional formulation of gravitational parameter

Fig. 10

MAE versus varying value of beta for power formulation of gravitational parameter

It can be concluded from Figs. 9 and 10 that the best values of $\alpha$ and $\beta$ occur in 1.35 and 0.74, respectively. Moreover, the MAE value of fractional formulation is less than power formulation. To have a more precise investigation, the average and the maximum values of MAE obtained for setup 1 (number of targets is two with similar qualities) and setup 2 (four targets with same qualities) from the experiments are presented in Table. Based on Table 4, the performance of $G_{t}$ based on fractional formulation is better than power formulation.

Table 4 Comparison of two proposed gravitational parameters

As a result power formulation $G_{t} = \left( {\frac{{m_{t} }}{{c_{t} + \varepsilon }}} \right)^{1.35}$ is considered as the gravitational parameter of algorithm.

Appendix B

4.1 Discussion of algorithms for comparison

4.1.1 Distributed bees algorithm (DBA)

In Jevtic et al. (2011), the task allocation problem is solved with a swarm-based meta-heuristic technique named DBA algorithm which is inspired by the intelligent behavior of the “bees” to optimize their search for “food” resources. In this algorithm, each robot is represented as a ‘bee’, and task utility, $p_{ik}$, is defined as a probability that the task $k$ is allocated to the task $i$ and depends on both target’s quality and the distance of the task from the robot:

$$p_{ik} = \frac{{q_{i}^{\alpha } \left( {\frac{1}{{D_{ik} }}} \right)^{\beta } }}{{\mathop \sum \nolimits_{j = 1}^{M} q_{j}^{\alpha } \left( {\frac{1}{{D_{jk} }}} \right)^{\beta } }}$$

(13)

where $q_{i}$ and $D_{ik} { }$ shows the quality or priority of target $i$ and distance between target $i$ and robot $k$, respectively. Moreover, $\alpha$ and $\beta$ are control parameters that bias importance of the priority and distance, respectively, ($\alpha$, $\beta > 0$; $\alpha$, $\beta \in R$).

In DBA algorithm, roulette wheel selection method is chosen in which a target with a probabilistic procedure is selected by each robot. In other words, in DBA the selection probability of target is proportional to their fitness value.

The probabilities $p_{ik}$ are normalized, and it is easy to show that:

$$\mathop \sum \limits_{i = 1}^{M} p_{ik} = 1$$

(14)

4.1.2 Modified distributed bees algorithm (MDBA)

In the MDBA, the original DBA robot utility function is modified to take advantage of heterogeneous robots or targets with different performances aiming to improve system performance by correlating the robot’s utility with their performances. In order to apply MDBA to heterogeneous robots or targets, a control parameter was defined in Tkach et al. (2018) as a function of the robot’s performance on a target. In simple words, when a robot receives information about an available target, it calculates its performance for that task. The robot’s utility function is updated accordingly, and depends on the target quality, the distance from the task and the robot’s performance on that task:

$$p_{ik} = \frac{{q_{i}^{\alpha } \left( {\frac{1}{{D_{ik} }}} \right)^{\beta } V_{ik}^{\chi } }}{{\mathop \sum \nolimits_{j = 1}^{M} q_{j}^{\alpha } \left( {\frac{1}{{D_{jk} }}} \right)^{\beta } V_{jk}^{\chi } }}\quad if\,\Delta_{i} > 0$$

(15)

where ${\upchi }$ is a control parameter that biases the importance of the robots performance and $V_{ik}$ is the performance of robot $k$ on task $i$. Moreover, each task has a time limit, or a deadline which is evaluated as follows:

$$\Delta_{i} = \frac{1}{{q_{i} }} > 0,\quad q_{i} > 0$$

(16)

The MDBA decision-making mechanism applies the same wheel-selection rule that is used in DBA to choose from a set of available tasks.

4.1.3 Linear ranking for distributed bees algorithm (LRDBA)

LRDBA shows a linear ranking selection for DBA. In order to do linear ranking selection, each target is defined by its fitness score which is named as "rank of target". In other words, the selection probability of each target ($Prob_{i}$) in linear ranking selection is evaluated as follows:

$$Prob_{i} = q - \left( {q - q_{0} } \right) \times \frac{{R_{i} - 1}}{T - 1}$$

(17)

where $q$ and $q_{0}$ are probability of selection of the best target and the worst target. Moreover $R_{i}$ is the rank of target $i$ and $T$ shows the total number of targets.

4.1.4 Exponential ranking for distributed bees algorithm (ERDBA)

In ERDBA an exponential ranking selection for DBA is utilized. This technique is different from linear ranking selection technique in a way that the probabilities of ERDBA are exponentially weighted as follows:

$$Prob_{i} = q\left( {1 - q} \right)^{{R_{i} - 1}}$$

(18)

4.1.5 Tournament based for distributed bees algorithm (TBDBA)

TBDBA is a tournament based selection strategy for DBA. Tournament Selection is a selection procedure used for selecting the fittest candidates from the current generation. These selected candidates are then passed on to the next generation. In a $K$-way tournament selection, $k$-individuals are selected and run a tournament among them. Only the fittest candidate among those selected candidates is chosen and is passed on to the next generation. In this way many such tournaments take place and the final selection of candidates who move on to the next generation are given.

4.1.6 Market-based algorithm (MBA)

A market-based algorithm used in Zlot et al. (2002) for distributed system was applied with application specific modifications. In this approach, the bid of robot $k$ to task $i$ is defined as (19):

$$Bid_{ik} = q_{ik} + \delta \left( {\frac{{V_{ik} }}{{D_{ik} }} - q_{ik} } \right)$$

(19)

where $q_{ik}$ serves as the reservation price of task $i$, and $\delta$ is a control parameter with values between 0 and 1. A task $i$ is selected by robot $k$ if it maximizes its bid value:

$$select = {\text{max}}(Bid_{ik} )$$

(20)

4.1.7 Greedy algorithm (GrA)

A greedy algorithm that was used previously for a multi target observation problem with broadcast messaging (Broadcast of Local Eligibility for Multi-Target Observation 2002) was modified to fit the described problem. The greedy algorithm was set to perform task allocation based on the best possible allocation of each individual robot to task that maximizes $\frac{{V_{ik} }}{{D_{ik} }}$, where $V_{ik}$ is the $k$-th robot’s performance on the $i$-th task and $D_{ik}$ is the Euclidean distance between the robot and the task:

$$task_{k} = {\text{max}}\left( {\frac{{V_{ik} }}{{D_{ik} }}} \right)\quad i \in Z$$

(21)

where $task_{k}$ is the task chosen by the $k$-th robot, $i$ shows the index of task, and $Z$ is the set of tasks within $k$-th robot range. Note that $Z$ is a subset of all $M$ available tasks.

4.1.8 Niching immune-based optimization algorithm based on softmax regression (sNIOA)

The sNIOA presents a niching immune-based optimization algorithm based on Softmax regression (sNIOA) to handle it (Huang et al. 2018). A pre-judgment of population is done before entering an evaluation process to reduce the evaluation time and to avoid unnecessary computation. Furthermore, a guiding mutation operator inspired by the base pair in theory of gene mutation is introduced into sNIOA to strengthen its search ability. It should be mentioned that in Huang et al. (2018), a discrete version of immune optimization algorithm is used in which each antibodies is utilized to present the allocated robot to defined tasks.