# A Comparative Study between Optimization and Market-Based Approaches to Multi-Robot Task Allocation

Authors: Mohamed Badreldin; Ahmed Hussein; Alaa Khamis
Journal: Advances in Artificial Intelligence
 (2013)

---

## Abstract

This paper presents a comparative study between optimization-based and market-based approaches used for solving the Multirobot task allocation (MRTA) problem that arises in the context of multirobot systems (MRS). The two proposed approaches are used to find the optimal allocation of a number of heterogeneous robots to a number of heterogeneous tasks. The two approaches were extensively tested over a number of test scenarios in order to test their capability of handling complex heavily constrained MRS applications that include extended number of tasks and robots. Finally, a comparative study is implemented between the two approaches and the results show that the optimization-based approach outperforms the market-based approach in terms of optimal allocation and computational time.


---

## Body

## 1. Introduction

In the last few years, the field of research in mobile robotics has encountered a significant shift as the researchers in this field have recently started focusing on MRS rather than single-robot systems. This increased interest in the community of mobile robotics research towards MRS comes from the significant advantages and higher potential provided by MRS than single-robot systems. The advantages of a robot team are many; some examples of these advantages include, but are not limited to, resolving task complexity, increased system reliability, increased system performance, and finally easier and simpler design [1].One of the main areas of research in this field is the task allocation problem in MRS, where the mapping of robots to tasks is done in order to increase the overall performance of the system. The task allocation problem is a major issue in MRS as it focuses on the proper utilization of the available resource. In MRS, the available resources are the robots which are used to solve a problem or to perform a certain task. Thus, in order to increase the performance of the system, one must efficiently utilizes the available robots in order to solve the required tasks. Since the decision of which robot will do which task has a significant effect on the performance of the system, the allocation of the tasks to the proper robots strongly affects the performance of the system [2]. The task allocation problem is proved to be one of the toughest problems especially when it comes to complex heterogeneous robot teams that are required to solve and execute complex problems and tasks. The heterogeneity of the robots simply indicates that the robot team consists of robots that have different features such as different capabilities and skills, different navigational velocities, different energy levels, different efficiency, and many other differences in the features between the different robots in the same team [3].The first objective of this paper is to present a framework that is efficiently capable of modeling any instance of the MRTA problem and to provide a suitable solution to the given problem. The framework will generate a solution in which the given robots are efficiently allocated to the given tasks in such a way to maximize the overall performance and minimize the total cost of the allocation. The framework will take into consideration the real-world constraints of the system, the requirements of the tasks, and the capabilities of the robots. The second objective of this paper is to conduct a comparative study between two main solving approaches for the MRTA problem which are the optimization-based approach and the market-based approach.The remainder of this paper is organized as follows. Section2 introduces the multi-robot task allocation problem describing multiple traveling salesman problem (mTSP) as problem formulation and the objective function used in this study. Section 3 discusses the metaheuristic optimization-based approach to solve the MRTA problem followed by presenting market-based approach in Section 4. Section 5 presents and discusses the experimental results of the comparative study. Finally, conclusion and future work are summarized in Section 6.


## 2. Multirobot Task Allocation

Over the last few years, several MRS problems were addressed, and since the MRS have a higher potential of solving complex and sophisticated problems, the complexity of the addressed problem increased with time. Therefore, the complexity of the MRS had to increase to accommodate the complexity of the addressed problems. As more research was done on MRS, the researchers have encountered the question “Which robot will execute which task?” In order to answer this question, more focus was directed towards the task allocation problem in MRS.The MRTA problem is a problem that arises in MRS where a number of robots are working together in the aim of achieving a common goal or task which is subdivided into a number of subtasks. The problem can be formulated as follows.(1)
Given a set of available robots,R={R1,R2,…Rn}.(2)
Given a set of available tasks,T={T1,T2,…Tm}.(3)
Allocation of the available tasks to the robots occurs,A:T→R.(4)
The output setS is the optimal allocation of the tasks to the available robots
(1)S={(R1T1)(R2T2)⋯(TkRk)}for1≤k≤m.(5)
This allocationS minimizes or maximizes a certain objective function in order to get the best performance of the system.


### 2.1. Problem Formulation

Multiple Traveling Salesman Problem (mTSP) can be considered as the generalization of the original TSP which is used as a platform for the study of general methods that can be applied to a wide range of discrete optimization problems. In TSPn cities are given and a traveling salesman must visit these n cities and return back home, making a loop (round-trip). He would like to travel in the most efficient way (cheapest way, fastest route, shortest route, or some other criterion). Similar to the TSP, in the mTSP a number of nodes are given and the distances between these nodes are also given, but the main difference in the mTSP is that, instead of a single salesman, a number of salesmen are given. The salesmen are required to cover all the available nodes and return back to their starting node. A number of variations of the original mTSP were introduced by different researchers to accommodate the mTSP to their problems. These variations included and one not restricted to the following [4]. (i)
Salesmen starting node: the salesmen may all start from a single depot node and then all of them must return back to the same node or every salesman can start from a certain node, and thus each salesman must return back to his starting node.(ii)
Number of salesmen: the number of salesmen used in different applications varied according to the type and requirements of the application itself. In some applications, the number of salesmen was dynamic such that after each iteration the number of salesman may or may not change.(iii)
City time frame: in some applications the task of the salesman was not only to visit the city, but also to stay in the city for a certain time in order to move to the next city.(iv)
Fair division of salesmen: another variation of the general mTSP is the addition of constraints that specifies the maximum number of cities or the maximum distance that can be traveled by a single salesman. This variation was used in applications that are concerned with the fair division of the available resources (salesmen).In the literature, various researchers have used the mTSP as a solution model for the MRTA due to the strong analogy between the two problems. In [5] the authors proposed to solve the MRTA for heterogeneous robots simultaneously with the path planning problem using a general mTSP problem formulation model. Simulated annealing metaheuristic approach was proposed as the optimization technique for solving the MRTA problem. The objective function used to evaluate the performance of the system was the MinMax strategy where the role of the applied algorithm was to minimize the worst-case allocation for each robot. In the simulation phase, two algorithms were compared, the simulated annealing approach and a previously implemented auction based approach. In [6], the task allocation problem in MRS was addressed when the authors proposed a solution to the assignment of multiple UAVs to multiple targets in a military application scenario. The proposed solution uses Ant-colony algorithm to solve an instance of the mTSP problem which is the formulation model used for solving the addressed task allocation problem. The mTSP was also used in [7] as a formulation for the MRTA problem. The author of this work proposed an auction-based approach to solve the MRTA problem after formulating the problem as an instance of the mTSP. In [8], a set of heterogeneous UAVs is required to be used in surveillance mission, where a set of targets should be observed by these UAVs. The problem can be considered a MRTA problem and can be modeled as a heterogeneous multiple depot, multiple UAV routing problem which is a another variation of the mTSP. Another approach is used to solve this problem which is to model this problem as a TSP where each target is modeled as a city to be visited only once by the traveling salesman (one of the UAVs) and then any known or novel approach can be used or developed to solve the TSP model in the aim of minimizing the traveling cost (distance) of the UAVs to cover all targets. The authors in this paper proposed a transformation method to transform the mTSP into an instance of the asymmetric TSP in order to use previously developed solving approaches to solve the Asymmetric TSP problem and thus solve the addressed MRTA problem. Also, [9] used the mTSP to propose a framework to solve dynamic task allocation scheme for MRS.In the mTSP, a number of nodesn and the distances between them are given and a number of salesmen m are also given. The salesmen are required to cover all the available nodes and return back to their starting node such that each salesman makes a round trip. The mTSP can be formally defined on a graph G=(V,A) where V is the set of n nodes and A is the set of arcs. Let C=(cij) be the distance matrix associated with A. Assuming the more general case which is an asymmetric mTSP, thus cij≠cji∀(i,j)∈A. The mTSP can be formulated as follows [4]:
(2)xij={1ifarc(i,j)isusedinthetour0otherwise,(3)minimize∑i=1n‍∑j=1n‍cij×xij,(4)∑j=2n‍x1j=m,(5)∑j=2n‍xj1=m,(6)∑i=1n‍xij=1,j=2,…,n,(7)∑j=1n‍xij=1,i=2,…,n,(8)∑i∈S‍∑j∈S‍xij≤|SubTour|-1,xij∈{0,1},∀(i,j)∈A,(9)∀SubTour⊆V∖{1},SubTour≠ϕ,
where (3) represents the objective function which is the summation of the total distance traveled and (4) and (5) ensure that exactly m salesmen departed their starting node and returned back. Equations (6), (7), and (8) are the usual assignment constraints. Finally, (9) is the subtour elimination constraint.Since the proposed approach mainly aims to solve the task allocation problem of MRS in real-world applications, through the different phases of the development of the introduced approach, the central target was to introduce a generic approach that is capable of solving various MRTA problems of different features and challenges. This target had to be taken into consideration during the formulation of the problem and therefore the use of the mTSP formulation previously presented was not suitable enough to solve the task allocation problem in real-world MRS applications. Therefore, the previously presented formulation had to be extended and adapted in order to be used as a formulation for the MRTA problem. In order to appropriately adapt the mTSP formulation to be used as a formulation for the MRTA problem, one must properly categorize the MRTA problem in interest.In this work, the solving approaches intends to solve MRTA problems that include heterogeneous single task robots, heterogeneous single-robot tasks, and instantaneous as well as time extended task assignment. After the categorization of the MRTA problem in interest, the mTSP formulation must be adapted to be used for solving the MRTA problems. This adaption is done through extending the mTSP formulation and the addition of extra features to the forming ingredients of the mTSP. Figure1 explains the extension of the mTSP formulation to accommodate the requirements of the MRTA problem.Figure 1
Extending mTSP formulation for MRTA.Since most real MRS applications require heterogeneous robots of different capabilities, it was a must to consider the heterogeneity of the robot in the proposed approach. Four main features of the robot were considered and thus were added to the traveling salesman in the implementation phase. The four features are as follows:(i)
velocity of the robot,(ii)
robot capabilities,(iii)
energy level of the robot,(iv)
aging factor (efficiency).In the same manner, the mTSP formulation for solving the MRTA problem needed to be adapted to handle the heterogeneity of the tasks and therefore it was a must to add extra features to the cities. The added features to the cities are as follows:(i)
task requirements,(ii)
minimum time required to finish the task.


### 2.2. Objective Function

Although the MRTA problem is formulated as an instance of the mTSP, the same objective function of the mTSP previously explained in (3) cannot be straightforwardly used as the objective function for the MRTA problem. Therefore, some variations had to be introduced to the objective function of the mTSP in order to be effectively used for the MRTA problem.There are three main variations of the MRTA problem objective function than the mTSP objective function. The three proposed variations are:(i)
a multiobjective function instead of a single-objective function.(ii)
the variable to be minimized is the time rather than the distance.(iii)
minimizing the time of the maximum subtour (MinMax) rather than minimizing the total time.Then, fork subtours and t tasks in each subtour, the total traveling time is calculated as follows:
(10)A=∑i=1t-1distancebetween(subtourji,subtourji+1)‍VelocityofRobotj,B=∑i=1ttaskexecutiontime(subtourji)AgingfactorofRobotj,f(x)=arg maxj∈{1,2,…k}(A+B).


## 2.1. Problem Formulation

Multiple Traveling Salesman Problem (mTSP) can be considered as the generalization of the original TSP which is used as a platform for the study of general methods that can be applied to a wide range of discrete optimization problems. In TSPn cities are given and a traveling salesman must visit these n cities and return back home, making a loop (round-trip). He would like to travel in the most efficient way (cheapest way, fastest route, shortest route, or some other criterion). Similar to the TSP, in the mTSP a number of nodes are given and the distances between these nodes are also given, but the main difference in the mTSP is that, instead of a single salesman, a number of salesmen are given. The salesmen are required to cover all the available nodes and return back to their starting node. A number of variations of the original mTSP were introduced by different researchers to accommodate the mTSP to their problems. These variations included and one not restricted to the following [4]. (i)
Salesmen starting node: the salesmen may all start from a single depot node and then all of them must return back to the same node or every salesman can start from a certain node, and thus each salesman must return back to his starting node.(ii)
Number of salesmen: the number of salesmen used in different applications varied according to the type and requirements of the application itself. In some applications, the number of salesmen was dynamic such that after each iteration the number of salesman may or may not change.(iii)
City time frame: in some applications the task of the salesman was not only to visit the city, but also to stay in the city for a certain time in order to move to the next city.(iv)
Fair division of salesmen: another variation of the general mTSP is the addition of constraints that specifies the maximum number of cities or the maximum distance that can be traveled by a single salesman. This variation was used in applications that are concerned with the fair division of the available resources (salesmen).In the literature, various researchers have used the mTSP as a solution model for the MRTA due to the strong analogy between the two problems. In [5] the authors proposed to solve the MRTA for heterogeneous robots simultaneously with the path planning problem using a general mTSP problem formulation model. Simulated annealing metaheuristic approach was proposed as the optimization technique for solving the MRTA problem. The objective function used to evaluate the performance of the system was the MinMax strategy where the role of the applied algorithm was to minimize the worst-case allocation for each robot. In the simulation phase, two algorithms were compared, the simulated annealing approach and a previously implemented auction based approach. In [6], the task allocation problem in MRS was addressed when the authors proposed a solution to the assignment of multiple UAVs to multiple targets in a military application scenario. The proposed solution uses Ant-colony algorithm to solve an instance of the mTSP problem which is the formulation model used for solving the addressed task allocation problem. The mTSP was also used in [7] as a formulation for the MRTA problem. The author of this work proposed an auction-based approach to solve the MRTA problem after formulating the problem as an instance of the mTSP. In [8], a set of heterogeneous UAVs is required to be used in surveillance mission, where a set of targets should be observed by these UAVs. The problem can be considered a MRTA problem and can be modeled as a heterogeneous multiple depot, multiple UAV routing problem which is a another variation of the mTSP. Another approach is used to solve this problem which is to model this problem as a TSP where each target is modeled as a city to be visited only once by the traveling salesman (one of the UAVs) and then any known or novel approach can be used or developed to solve the TSP model in the aim of minimizing the traveling cost (distance) of the UAVs to cover all targets. The authors in this paper proposed a transformation method to transform the mTSP into an instance of the asymmetric TSP in order to use previously developed solving approaches to solve the Asymmetric TSP problem and thus solve the addressed MRTA problem. Also, [9] used the mTSP to propose a framework to solve dynamic task allocation scheme for MRS.In the mTSP, a number of nodesn and the distances between them are given and a number of salesmen m are also given. The salesmen are required to cover all the available nodes and return back to their starting node such that each salesman makes a round trip. The mTSP can be formally defined on a graph G=(V,A) where V is the set of n nodes and A is the set of arcs. Let C=(cij) be the distance matrix associated with A. Assuming the more general case which is an asymmetric mTSP, thus cij≠cji∀(i,j)∈A. The mTSP can be formulated as follows [4]:
(2)xij={1ifarc(i,j)isusedinthetour0otherwise,(3)minimize∑i=1n‍∑j=1n‍cij×xij,(4)∑j=2n‍x1j=m,(5)∑j=2n‍xj1=m,(6)∑i=1n‍xij=1,j=2,…,n,(7)∑j=1n‍xij=1,i=2,…,n,(8)∑i∈S‍∑j∈S‍xij≤|SubTour|-1,xij∈{0,1},∀(i,j)∈A,(9)∀SubTour⊆V∖{1},SubTour≠ϕ,
where (3) represents the objective function which is the summation of the total distance traveled and (4) and (5) ensure that exactly m salesmen departed their starting node and returned back. Equations (6), (7), and (8) are the usual assignment constraints. Finally, (9) is the subtour elimination constraint.Since the proposed approach mainly aims to solve the task allocation problem of MRS in real-world applications, through the different phases of the development of the introduced approach, the central target was to introduce a generic approach that is capable of solving various MRTA problems of different features and challenges. This target had to be taken into consideration during the formulation of the problem and therefore the use of the mTSP formulation previously presented was not suitable enough to solve the task allocation problem in real-world MRS applications. Therefore, the previously presented formulation had to be extended and adapted in order to be used as a formulation for the MRTA problem. In order to appropriately adapt the mTSP formulation to be used as a formulation for the MRTA problem, one must properly categorize the MRTA problem in interest.In this work, the solving approaches intends to solve MRTA problems that include heterogeneous single task robots, heterogeneous single-robot tasks, and instantaneous as well as time extended task assignment. After the categorization of the MRTA problem in interest, the mTSP formulation must be adapted to be used for solving the MRTA problems. This adaption is done through extending the mTSP formulation and the addition of extra features to the forming ingredients of the mTSP. Figure1 explains the extension of the mTSP formulation to accommodate the requirements of the MRTA problem.Figure 1
Extending mTSP formulation for MRTA.Since most real MRS applications require heterogeneous robots of different capabilities, it was a must to consider the heterogeneity of the robot in the proposed approach. Four main features of the robot were considered and thus were added to the traveling salesman in the implementation phase. The four features are as follows:(i)
velocity of the robot,(ii)
robot capabilities,(iii)
energy level of the robot,(iv)
aging factor (efficiency).In the same manner, the mTSP formulation for solving the MRTA problem needed to be adapted to handle the heterogeneity of the tasks and therefore it was a must to add extra features to the cities. The added features to the cities are as follows:(i)
task requirements,(ii)
minimum time required to finish the task.


## 2.2. Objective Function

Although the MRTA problem is formulated as an instance of the mTSP, the same objective function of the mTSP previously explained in (3) cannot be straightforwardly used as the objective function for the MRTA problem. Therefore, some variations had to be introduced to the objective function of the mTSP in order to be effectively used for the MRTA problem.There are three main variations of the MRTA problem objective function than the mTSP objective function. The three proposed variations are:(i)
a multiobjective function instead of a single-objective function.(ii)
the variable to be minimized is the time rather than the distance.(iii)
minimizing the time of the maximum subtour (MinMax) rather than minimizing the total time.Then, fork subtours and t tasks in each subtour, the total traveling time is calculated as follows:
(10)A=∑i=1t-1distancebetween(subtourji,subtourji+1)‍VelocityofRobotj,B=∑i=1ttaskexecutiontime(subtourji)AgingfactorofRobotj,f(x)=arg maxj∈{1,2,…k}(A+B).


## 3. Optimization-Based Approach

Optimization is the branch of applied mathematics focusing on solving a certain problem in the aim of finding the optimum solution for this problem out of a set of available solutions. In other words, optimization techniques are applied in order to maximize the profit (maximization problem) or reduce the damage (minimization problem) of a certain problem. The set of available solutions is restricted by a set of constraints, and the optimum solution is chosen within these constrained solutions according to a certain criteria. These criteria define the objective function of the problem, where the objective function is a mathematical expression combining some variables in order to describe the goal of the system [10]. 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.By reviewing the literature, it was found that different optimization approaches have been used in order to solve the general task allocation problem and was also used in order to solve the MRTA problem. In [11], 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 [12], a mixed integer linear programming approach was used for solving the task allocation problem in the context of UAV cooperation. In [13, 14], a simulated annealing approach was used to solve the allocation of multirobot system through formulating the MRTA problem as mTSP. In [15, 16], simulated annealing incorporated with other heuristic approaches was used to allocate a set of tasks to a number of processors in computer system problems.Another different optimization approaches were also used for solving the task allocation problem. For example, population-based approaches such as the genetic algorithm was used in [17] for providing a feasible solution for a group tracking system which is capable of tracking several targets rather than individual targets. Genetic algorithm was also used in [18] to provide a solution for the time extended task allocation of multirobots in a simulated disaster scenario. Ant colony optimization, another technique of the population-based optimization approaches, was used in [19] to solve the task allocation problem of MRS. In [20], ant algorithm was used in the context of multi-robot cooperation for the aim of solving the task allocation problem.The task allocation problem was also solved using hybrid optimization approaches such as the tabu search with random search method in [16] and tabu search with noising method in [21]. In [22], a simultaneous approach for solving the path planning and task allocation problems for a MRS is proposed, where simulated annealing and ant colony optimization approaches were investigated and applied for solving the problem.The following subsections present a trajectory-based metaheuristic approach and a population-based metaheuristic approach to solve the MRTA problem.


### 3.1. Trajectory-Based Metaheuristic Approach

The first introduced algorithm is the SA algorithm which is a metaheuristic algorithm of the trajectory-based approaches family. The trajectory-based family of metaheuristic algorithms is the family of algorithms that uses a single solution throughout the algorithm in order to find the optimal solution. The neighboring operator used in the proposed algorithm is randomly chosen at each iteration for the sake of diversity from one of the following operators:(i)
swapping,(ii)
deletion and insertion,(iii)
inversion,(iv)
scrambling.Algorithm1 is the proposed algorithm used to solve the MRTA problem in this paper using the SA metaheuristic algorithm.Algorithm 1:SA-based MRTA.
Input: Tasks list tasks, Robots list robots,
Distances between tasksdistances
Output: Optimal allocation optAlloc
(1)Define: Initial temperature inTemp, Final
temperaturefinTemp, Iterations per temperature
iterTemp, Current temperature currTemp,
Geometric coefficientα, Transition probability
transProb, Current allocation currAlloc,
Neighbor allocationneighborAlloc, Current cost
currCost, Neighbor cost neighborCost, Optimal
costoptCost
(2)currAlloc← generateValidSolution (tasks, robots,
distances)
(3)currCost← getAllocationCost (currAlloc)
(4)optCost←currCost
(5)while  currTemp<finTemp  do
(6)for  i←1  to  iterTemp  do
(7)neighborAlloc←
generateNeighborSolution (currAlloc)
(8)neighborCost←
getAllocationCost (neighborAlloc)
(9)if  neighborCost<currCost  then
(10)currAlloc←neighborAlloc
(11)currCost←neighborCost
(12)if  neighborCost<optCost  then
(13)optAlloc←neighborAlloc
(14)optCost←neighborCost
(15)end
(16)else
(17)Generate: A random number
randNum
(18)transProb =
exp(-neighborCost-currCostcurrTemp)
(19)if  transProb>randNum  then
(20)currAlloc←neighborAlloc
(21)currCost←neighborCost
(22)end
(23)end
(24)end
(25)currTemp = currTemp*α
(26)end


### 3.2. Population-Based Metaheuristic Approach

The second introduced algorithm is the GA which is an evolutionary algorithm of the population-based family of metaheuristic algorithms. Population-based algorithms is the family of algorithms that iteratively transforms a population of solutions throughout the algorithm in order to generate a new population of solutions in the aim of finding the optimal solution.The mutation operators used in the proposed algorithms are(i)
swapping,(ii)
deletion and insertion,(iii)
inversion,(iv)
scrambling,while the crossover operators used are(i)
partially mapped crossover,(ii)
order crossover.Algorithm2 is the proposed algorithm used to solve the MRTA problem in this paper using the GA.Algorithm 2:GA-based MRTA.
Input: Tasks list tasks, Robots list robots,
Distances between tasks distances
Output: Optimal allocation optAlloc
(1)Define: Parents list, parentList, Children list
childList, Next generation list nxtGenList,
Number of iterationsnumIter, Elitism percent
elitismPerc, Population size popuSize, Current
allocationcurrAlloc, Optimal allocation optAlloc
(2)for  i←1  to  popuSize  do
(3)parentList← generateValidSolution (tasks,
robots, distances)
(4)end
(5)currAlloc← Minimum (parentList)
(6)for  i←1  to  numIter  do
(7)if  i< 25% ofnumIter  then
(8)elitismPerc = 20%
(9)else if  i< 50% ofnumIterANDi> 25% of
numIter  then
(10)elitismPerc = 30%
(11)else if  i< 75% ofnumIterANDi> 50% of
numIter  then
(12)elitismPerc = 40%
(13)else
(14)elitismPerc = 50%
(15)end
(16)childList← crossover (The minimum 10% of
parentList)
(17)childList← mutation (The maximum 90% of
parentList)
(18)nxtGenList← The minimum elitismPerc of
parentList
(19)nxtGenList← The minimum elitismPerc of
childList
(20)for  j←1  to  (100%-elitismPerc×2) of
numIter  do
(21)nxtGenList←
generateValidSolution (tasks, robots,
distances)
(22)end
(23)if  Minimum (parentList) <currAlloc  then
(24)  currAlloc← Minimum (parentList)
(25)end
(26)parentList←nxtGenList
(27)end
(28)optAlloc←currAlloc


## 3.1. Trajectory-Based Metaheuristic Approach

The first introduced algorithm is the SA algorithm which is a metaheuristic algorithm of the trajectory-based approaches family. The trajectory-based family of metaheuristic algorithms is the family of algorithms that uses a single solution throughout the algorithm in order to find the optimal solution. The neighboring operator used in the proposed algorithm is randomly chosen at each iteration for the sake of diversity from one of the following operators:(i)
swapping,(ii)
deletion and insertion,(iii)
inversion,(iv)
scrambling.Algorithm1 is the proposed algorithm used to solve the MRTA problem in this paper using the SA metaheuristic algorithm.Algorithm 1:SA-based MRTA.
Input: Tasks list tasks, Robots list robots,
Distances between tasksdistances
Output: Optimal allocation optAlloc
(1)Define: Initial temperature inTemp, Final
temperaturefinTemp, Iterations per temperature
iterTemp, Current temperature currTemp,
Geometric coefficientα, Transition probability
transProb, Current allocation currAlloc,
Neighbor allocationneighborAlloc, Current cost
currCost, Neighbor cost neighborCost, Optimal
costoptCost
(2)currAlloc← generateValidSolution (tasks, robots,
distances)
(3)currCost← getAllocationCost (currAlloc)
(4)optCost←currCost
(5)while  currTemp<finTemp  do
(6)for  i←1  to  iterTemp  do
(7)neighborAlloc←
generateNeighborSolution (currAlloc)
(8)neighborCost←
getAllocationCost (neighborAlloc)
(9)if  neighborCost<currCost  then
(10)currAlloc←neighborAlloc
(11)currCost←neighborCost
(12)if  neighborCost<optCost  then
(13)optAlloc←neighborAlloc
(14)optCost←neighborCost
(15)end
(16)else
(17)Generate: A random number
randNum
(18)transProb =
exp(-neighborCost-currCostcurrTemp)
(19)if  transProb>randNum  then
(20)currAlloc←neighborAlloc
(21)currCost←neighborCost
(22)end
(23)end
(24)end
(25)currTemp = currTemp*α
(26)end


## 3.2. Population-Based Metaheuristic Approach

The second introduced algorithm is the GA which is an evolutionary algorithm of the population-based family of metaheuristic algorithms. Population-based algorithms is the family of algorithms that iteratively transforms a population of solutions throughout the algorithm in order to generate a new population of solutions in the aim of finding the optimal solution.The mutation operators used in the proposed algorithms are(i)
swapping,(ii)
deletion and insertion,(iii)
inversion,(iv)
scrambling,while the crossover operators used are(i)
partially mapped crossover,(ii)
order crossover.Algorithm2 is the proposed algorithm used to solve the MRTA problem in this paper using the GA.Algorithm 2:GA-based MRTA.
Input: Tasks list tasks, Robots list robots,
Distances between tasks distances
Output: Optimal allocation optAlloc
(1)Define: Parents list, parentList, Children list
childList, Next generation list nxtGenList,
Number of iterationsnumIter, Elitism percent
elitismPerc, Population size popuSize, Current
allocationcurrAlloc, Optimal allocation optAlloc
(2)for  i←1  to  popuSize  do
(3)parentList← generateValidSolution (tasks,
robots, distances)
(4)end
(5)currAlloc← Minimum (parentList)
(6)for  i←1  to  numIter  do
(7)if  i< 25% ofnumIter  then
(8)elitismPerc = 20%
(9)else if  i< 50% ofnumIterANDi> 25% of
numIter  then
(10)elitismPerc = 30%
(11)else if  i< 75% ofnumIterANDi> 50% of
numIter  then
(12)elitismPerc = 40%
(13)else
(14)elitismPerc = 50%
(15)end
(16)childList← crossover (The minimum 10% of
parentList)
(17)childList← mutation (The maximum 90% of
parentList)
(18)nxtGenList← The minimum elitismPerc of
parentList
(19)nxtGenList← The minimum elitismPerc of
childList
(20)for  j←1  to  (100%-elitismPerc×2) of
numIter  do
(21)nxtGenList←
generateValidSolution (tasks, robots,
distances)
(22)end
(23)if  Minimum (parentList) <currAlloc  then
(24)  currAlloc← Minimum (parentList)
(25)end
(26)parentList←nxtGenList
(27)end
(28)optAlloc←currAlloc


## 4. Market-Based Approach

Throughout time, humans have dealt with coordination and allocation problems for thousands of years with sophisticated market economies in which the individual pursuit of profit leads to the redistribution of resources and an efficient production of output. The principles of a market economy can be applied to multi-robot coordination [23]. Market-based multi-robot coordination approaches have received noteworthy attention within the robotics research community in recent years. They have been successfully implemented in a variety of domains ranging from mapping and exploration to robot soccer. Market-based approaches are focused on the concept of utility functions, which can represent the ability of the agents to measure their interest in specific tasks for trading. In MRTA systems, the utility functions show how the robots skills can match the tasks requirements. A lot of market-based approaches were developed for multiagent coordination [24–26]. Moreover, several surveys are completed on the same topic [23, 27].In general, auctions are scalable, computationally cheap and have reduced communication requirements. They can be performed centrally, by an auctioneer or by the robots themselves, in a distributed way. Therefore, market-based coordination approaches have been studied in countless multi-agent systems [28–32]. The market-based approach is mainly based on the auctions systems. Auctions have mainly two general categories: simple auctions and combinatorial auctions. MRTA problem are solved using both categories to reach an optimal allocation and results were acceptable [33–35]. Depending on the how the winner determination strategy is implemented, market-based approach can be centralized or decentralized. Fully centralized approaches can be computationally intractable, brittle, and unresponsive to change. However, for applications where teams are small and the environment is static or global state information is easily available, centralized approaches are the best-suited solution. Khamis el al. studied in [36] both centralized and hierarchical allocations as winner determination strategies for different levels of allocation and for static and dynamic search tree structures. Nowadays, new architectures are being implemented as enhancement to the traditional methods, such as Murdoch [24], Trader Bots [37], and many others [38, 39].For the market-based approach, the proposed algorithm was designed to follow the sealed-bid closed-cry auctions and the selected auction design is contract net protocol (CNP). The algorithm was tested over several sets of experiments and the results were not promising enough and thus it was suggested to add enhancements for the market-based approach. The first attempted enhancement is the relinquishing process enhancement, where the robot relinquishes a random task from its assigned tasks to explore more solutions. The second enhancement was to apply an optimization technique such as simulated annealing (SA) to optimize the final subtour of the allocation as single traveling salesman problem [40].The first enhancement process is presented in Algorithm3 which is the relinquishing process enhancement. The optimization enhancement was done through applying the previously discussed simulated annealing approach presented in Algorithm 1 over the market-based algorithm.Algorithm 3:Relinquishing process.
Input: Best allocation bestAlloc, Available tasks
availTasks
Output: Relinquished tasks relTasks
(1) Number of robotsn
(2) Sub-tours listsubTours
(3) Relinquished taskrelTask Random number rand
(4)subTours← getSubTours (bestAlloc)
(5)for  i←1 to n  do
(6)rand← getRandomNumber (subTours(i))
(7)relTask← removeTask (bestAlloc, rand)
(8)availTasks← add (relTask)
(9)endThe final market-based approach with both enhancements, the relinquishing and the optimization enhancements, is presented in Algorithm4 where this algorithm is the algorithm used in this paper to solve the MRTA problem.Algorithm 4:Market-based approach with relinquishing and optimization.
Input: Tasks list tasks, Robots list robots,
Distances between tasks distances, Number
of Iterations n
Output: Best allocation bestAlloc
(1) Best costbestCost
(2) Available tasksavailTasks
(3) Bidding listbiddingList
(4) Minimum bidminBid
(5) Current allocationcurAlloc
(6) Current costcurCost
(7) User define percentagero
(8)availTasks←tasks
(9)for  i←1 to n  do
(10)while  isEmpty (availTasks)   do
(11)biddingList← getBids (robots,
availTasks, distances)
(12)minBid← getMin (biddingList)
(13)curAlloc← subTour (robots, availTasks,
minBid)
(14)end
(15) availTasks← relinquish (curAlloc,
availTasks) // Algorithm 3
(16) r← getRandomNumber (1)
(17) if  curCost<bestCost  then
(18)bestAlloc←curAlloc
(19) else
(20)if  ro>r  then
(21)bestAlloc←curAlloc
(22)end
(23)end
(24)end
(25)optiAlloc← optimize (bestAlloc) // refer to
Algorithm 1


## 5. Results and Discussion

The following subsections present the experiment setup, the emulation metrics, and a comparative study between the two proposed approaches.


### 5.1. Experiment Setup

All experiments are conducted on a Microsoft Windows operating system on a device whose specifications are presented in Table1.Table 1
System specifications.
Processor
1.70 GHz
Installed memory (RAM)
6.00 GB
System type
64-bit operating system


### 5.2. Evaluation Metrics

The proposed algorithms, both the market-based and the metaheuristic-based, are tested both qualitatively and quantitatively. A number of test scenarios that include different instances of the MRTA problem were proposed. The different proposed scenarios were used to test the algorithms qualitatively. However, in order to be able to quantitatively test the quality of the proposed algorithms, two evaluation metrics were proposed. Therefore, each algorithm was used to solve the MRTA problem in each qualitative test scenario and then the results and the quality of the solution provided were evaluated through the two quantitative evaluation metrics. The two quantitative metrics used to test both algorithms are as follows:(i)
the best allocation found in terms of the objective function [OptAllocCost],(ii)
computational time taken to best allocation [AvgTime].The first evaluation metric is the cost of the best allocation found which is the best solution in terms of the objective function previously discussed in (10). The second evaluation metric is the average computational time required by the algorithm until finishing the total number of iterations.Since one of the main sources of complexity of MRS applications is the size of the robot team as well as the number of tasks to be executed, it was essential to qualitatively test the proposed algorithms for their capability of handling complex MRTA problems of large number of tasks and robots. Analysis of the scalability of the proposed algorithms is done through applying each algorithm over a number of scenarios at which the number of tasks and the number of used robots increase over each scenario. It must be mentioned that in these scenarios there are no constraints applied on the domain of the problems being solved. The main reason of eliminating the constraints is to eliminate any other source of complexity to the problem rather than the increased number of robots and tasks, where eliminating other sources of complexity to the problem enables the adequate testing of only the scalability of the proposed algorithms with no other factors affecting the problem.In the scalability test three scenarios were proposed which are as follows:(i)
small-scale problem, five tasks, and three robots,(ii)
medium-scale problem, fifteen tasks, and five robots,(iii)
large-scale problem, fifty tasks, and fifteen robots.Another significant cause of complexity of the newly tackled MRS applications is that the problems are highly constrained. The constraints of MRS applications mainly arise because of two main reasons. The first source of constraints is the introduction of the heterogeneous robots in the multirobot team as well as the heterogeneity of the tasks being executed. The second source of constraints is the amount of energy level of the used robots and the time requirements of the tasks to be executed. Therefore, it was a must to qualitatively test the capability of the proposed algorithms in this paper to solve constrained instances of the MRTA problem.In the constraints test three scenarios were proposed which are as follows:(i)
capabilities matching scenario,(ii)
time matching scenario,(iii)
heavily constrained scenario.


### 5.3. Comparative Study

In this subsection, a comparative study is implemented in order to test the performance of the three proposed algorithms in this paper on different test scenarios. The performance of each algorithm is illustrated through plotting the values of the two evaluation metrics of each algorithm for each test scenario, where thex-axis refers to the computational time taken to best allocation [AvgTime] which is time in seconds while the y-axis refers to the best allocation found in terms of the objective function [OptAllocCost] which is time taken to complete the allocated tasks in minutes.


#### 5.3.1. Small-Scale MRTA Scenario

Figure2 illustrates the difference in the performances of the three approaches in comparison SA, GA, and the market-based approach versus time when used to solve the small-scale MRTA scenario.Figure 2
Small-scale MRTA scenario comparative study.The three approaches were capable of converging to the same allocation cost in the small-scale scenario. GA was the fastest to reach the best allocation followed by SA and then the market-based approach.


#### 5.3.2. Medium-Scale MRTA Scenario

Figure3 illustrates the difference in the performances of the three approaches in comparison SA, GA, and the market-based approach versus time when used to solve the medium-scale MRTA scenario.Figure 3
Medium-scale MRTA scenario comparative study.The performance of SA and GA in Figure3 shows that SA was capable of converging to better allocation cost than GA at the end of both algorithms. However, GA was faster in converging to better allocations than SA at the beginning of the algorithms and thus if both algorithms are stopped early before reaching the total number of iterations, the results of the GA are expected to be better than the results of SA. Finally, both the SA and GA provided better allocation costs than the market-based approach.


#### 5.3.3. Large-Scale MRTA Scenario

Figure4 illustrates the difference in the performances of the three approaches in comparison between SA, GA, and the market-based approach versus time when used to solve the large-scale MRTA scenario.Figure 4
Large-scale MRTA scenario comparative study.The results in Figure4 show that the performance of SA is better than GA in terms of allocation cost. Also, the results in the figure shows that GA is capable of converging FASTER to better results than SA. However, as more time is given for both algorithms, SA converges to better allocations than GA. Finally, comparing the results of SA and GA with the market-based approach results shows that the metaheuristic approaches SA and GA significantly outperformed the market-based approach in terms of allocation cost provided for the large-scale problem. This major difference in the allocation cost between the metaheuristic approaches and the market-based approach in solving the large-scale MRTA scenario indicates that market-based approaches might not be the suitable approach for MRS applications with extended number of tasks and robots. On the other hand, the metaheuristic approaches have proven to provide acceptable results in medium and large-scale MRTA scenarios with extended number of tasks and robots.


#### 5.3.4. Capabilities Matching MRTA Scenario

Figure5 illustrates the difference in the performances of the three approaches in comparison between SA, GA, and the market-based approach versus time when used to solve the capabilities matching MRTA scenario.Figure 5
Capabilities matching MRTA scenario comparative study.The performance curves of SA and GA in Figure5 demonstrate that at the end of both algorithms the allocations found are of the same cost for both algorithms. On the other hand, GA algorithm was capable of converging to better allocations of lower costs earlier than SA. Thus, if there was no enough time for both algorithms to reach the total number of iterations, the GA would be the suitable algorithm and is expected to provide better results than SA. Although, in this MRTA scenario, the metaheuristic approaches converged earlier than the market-based approach, the market-based approach eventually provided better allocation costs than both metaheuristic algorithms.


#### 5.3.5. Time Matching MRTA Scenario

Figure4 illustrates the difference in the performances of the three approaches in comparison between SA, GA, and the market-based approach versus time when used to solve the time matching MRTA scenario.Figure6 shows that SA provides slightly better allocations than GA; however, the total time consumed by SA is significantly lower than total time consumed by GA. Moreover, the performance curves show that GA converges to better solutions faster than SA; however, SA provided better results than GA at the end of each algorithm. The reported results in Figure 6 demonstrate that both metaheuristic approaches provided slightly better allocation costs than the market-based approach. Also, the metaheuristic approaches converged faster than the market-based approach.Figure 6
Time matching MRTA scenario comparative study.


#### 5.3.6. Heavily Constrained MRTA Scenario

Figure7 illustrates the difference in the performances of two approaches in comparing SA and the market-based approach versus time when used to solve the time matching MRTA scenario. There were no reported results for the GA as it consumed a large amount of time to provide one solution and thus was not practical.Figure 7
Heavily constrained MRTA scenario comparative study.The reported results in Figure7 show that SA provided better results than the market-based approach although the difference between the two approaches in terms of allocation cost is minimal. However, SA converged much faster than the market-based approach.


## 5.1. Experiment Setup

All experiments are conducted on a Microsoft Windows operating system on a device whose specifications are presented in Table1.Table 1
System specifications.
Processor
1.70 GHz
Installed memory (RAM)
6.00 GB
System type
64-bit operating system


## 5.2. Evaluation Metrics

The proposed algorithms, both the market-based and the metaheuristic-based, are tested both qualitatively and quantitatively. A number of test scenarios that include different instances of the MRTA problem were proposed. The different proposed scenarios were used to test the algorithms qualitatively. However, in order to be able to quantitatively test the quality of the proposed algorithms, two evaluation metrics were proposed. Therefore, each algorithm was used to solve the MRTA problem in each qualitative test scenario and then the results and the quality of the solution provided were evaluated through the two quantitative evaluation metrics. The two quantitative metrics used to test both algorithms are as follows:(i)
the best allocation found in terms of the objective function [OptAllocCost],(ii)
computational time taken to best allocation [AvgTime].The first evaluation metric is the cost of the best allocation found which is the best solution in terms of the objective function previously discussed in (10). The second evaluation metric is the average computational time required by the algorithm until finishing the total number of iterations.Since one of the main sources of complexity of MRS applications is the size of the robot team as well as the number of tasks to be executed, it was essential to qualitatively test the proposed algorithms for their capability of handling complex MRTA problems of large number of tasks and robots. Analysis of the scalability of the proposed algorithms is done through applying each algorithm over a number of scenarios at which the number of tasks and the number of used robots increase over each scenario. It must be mentioned that in these scenarios there are no constraints applied on the domain of the problems being solved. The main reason of eliminating the constraints is to eliminate any other source of complexity to the problem rather than the increased number of robots and tasks, where eliminating other sources of complexity to the problem enables the adequate testing of only the scalability of the proposed algorithms with no other factors affecting the problem.In the scalability test three scenarios were proposed which are as follows:(i)
small-scale problem, five tasks, and three robots,(ii)
medium-scale problem, fifteen tasks, and five robots,(iii)
large-scale problem, fifty tasks, and fifteen robots.Another significant cause of complexity of the newly tackled MRS applications is that the problems are highly constrained. The constraints of MRS applications mainly arise because of two main reasons. The first source of constraints is the introduction of the heterogeneous robots in the multirobot team as well as the heterogeneity of the tasks being executed. The second source of constraints is the amount of energy level of the used robots and the time requirements of the tasks to be executed. Therefore, it was a must to qualitatively test the capability of the proposed algorithms in this paper to solve constrained instances of the MRTA problem.In the constraints test three scenarios were proposed which are as follows:(i)
capabilities matching scenario,(ii)
time matching scenario,(iii)
heavily constrained scenario.


## 5.3. Comparative Study

In this subsection, a comparative study is implemented in order to test the performance of the three proposed algorithms in this paper on different test scenarios. The performance of each algorithm is illustrated through plotting the values of the two evaluation metrics of each algorithm for each test scenario, where thex-axis refers to the computational time taken to best allocation [AvgTime] which is time in seconds while the y-axis refers to the best allocation found in terms of the objective function [OptAllocCost] which is time taken to complete the allocated tasks in minutes.


### 5.3.1. Small-Scale MRTA Scenario

Figure2 illustrates the difference in the performances of the three approaches in comparison SA, GA, and the market-based approach versus time when used to solve the small-scale MRTA scenario.Figure 2
Small-scale MRTA scenario comparative study.The three approaches were capable of converging to the same allocation cost in the small-scale scenario. GA was the fastest to reach the best allocation followed by SA and then the market-based approach.


### 5.3.2. Medium-Scale MRTA Scenario

Figure3 illustrates the difference in the performances of the three approaches in comparison SA, GA, and the market-based approach versus time when used to solve the medium-scale MRTA scenario.Figure 3
Medium-scale MRTA scenario comparative study.The performance of SA and GA in Figure3 shows that SA was capable of converging to better allocation cost than GA at the end of both algorithms. However, GA was faster in converging to better allocations than SA at the beginning of the algorithms and thus if both algorithms are stopped early before reaching the total number of iterations, the results of the GA are expected to be better than the results of SA. Finally, both the SA and GA provided better allocation costs than the market-based approach.


### 5.3.3. Large-Scale MRTA Scenario

Figure4 illustrates the difference in the performances of the three approaches in comparison between SA, GA, and the market-based approach versus time when used to solve the large-scale MRTA scenario.Figure 4
Large-scale MRTA scenario comparative study.The results in Figure4 show that the performance of SA is better than GA in terms of allocation cost. Also, the results in the figure shows that GA is capable of converging FASTER to better results than SA. However, as more time is given for both algorithms, SA converges to better allocations than GA. Finally, comparing the results of SA and GA with the market-based approach results shows that the metaheuristic approaches SA and GA significantly outperformed the market-based approach in terms of allocation cost provided for the large-scale problem. This major difference in the allocation cost between the metaheuristic approaches and the market-based approach in solving the large-scale MRTA scenario indicates that market-based approaches might not be the suitable approach for MRS applications with extended number of tasks and robots. On the other hand, the metaheuristic approaches have proven to provide acceptable results in medium and large-scale MRTA scenarios with extended number of tasks and robots.


### 5.3.4. Capabilities Matching MRTA Scenario

Figure5 illustrates the difference in the performances of the three approaches in comparison between SA, GA, and the market-based approach versus time when used to solve the capabilities matching MRTA scenario.Figure 5
Capabilities matching MRTA scenario comparative study.The performance curves of SA and GA in Figure5 demonstrate that at the end of both algorithms the allocations found are of the same cost for both algorithms. On the other hand, GA algorithm was capable of converging to better allocations of lower costs earlier than SA. Thus, if there was no enough time for both algorithms to reach the total number of iterations, the GA would be the suitable algorithm and is expected to provide better results than SA. Although, in this MRTA scenario, the metaheuristic approaches converged earlier than the market-based approach, the market-based approach eventually provided better allocation costs than both metaheuristic algorithms.


### 5.3.5. Time Matching MRTA Scenario

Figure4 illustrates the difference in the performances of the three approaches in comparison between SA, GA, and the market-based approach versus time when used to solve the time matching MRTA scenario.Figure6 shows that SA provides slightly better allocations than GA; however, the total time consumed by SA is significantly lower than total time consumed by GA. Moreover, the performance curves show that GA converges to better solutions faster than SA; however, SA provided better results than GA at the end of each algorithm. The reported results in Figure 6 demonstrate that both metaheuristic approaches provided slightly better allocation costs than the market-based approach. Also, the metaheuristic approaches converged faster than the market-based approach.Figure 6
Time matching MRTA scenario comparative study.


### 5.3.6. Heavily Constrained MRTA Scenario

Figure7 illustrates the difference in the performances of two approaches in comparing SA and the market-based approach versus time when used to solve the time matching MRTA scenario. There were no reported results for the GA as it consumed a large amount of time to provide one solution and thus was not practical.Figure 7
Heavily constrained MRTA scenario comparative study.The reported results in Figure7 show that SA provided better results than the market-based approach although the difference between the two approaches in terms of allocation cost is minimal. However, SA converged much faster than the market-based approach.


## 5.3.1. Small-Scale MRTA Scenario

Figure2 illustrates the difference in the performances of the three approaches in comparison SA, GA, and the market-based approach versus time when used to solve the small-scale MRTA scenario.Figure 2
Small-scale MRTA scenario comparative study.The three approaches were capable of converging to the same allocation cost in the small-scale scenario. GA was the fastest to reach the best allocation followed by SA and then the market-based approach.


## 5.3.2. Medium-Scale MRTA Scenario

Figure3 illustrates the difference in the performances of the three approaches in comparison SA, GA, and the market-based approach versus time when used to solve the medium-scale MRTA scenario.Figure 3
Medium-scale MRTA scenario comparative study.The performance of SA and GA in Figure3 shows that SA was capable of converging to better allocation cost than GA at the end of both algorithms. However, GA was faster in converging to better allocations than SA at the beginning of the algorithms and thus if both algorithms are stopped early before reaching the total number of iterations, the results of the GA are expected to be better than the results of SA. Finally, both the SA and GA provided better allocation costs than the market-based approach.


## 5.3.3. Large-Scale MRTA Scenario

Figure4 illustrates the difference in the performances of the three approaches in comparison between SA, GA, and the market-based approach versus time when used to solve the large-scale MRTA scenario.Figure 4
Large-scale MRTA scenario comparative study.The results in Figure4 show that the performance of SA is better than GA in terms of allocation cost. Also, the results in the figure shows that GA is capable of converging FASTER to better results than SA. However, as more time is given for both algorithms, SA converges to better allocations than GA. Finally, comparing the results of SA and GA with the market-based approach results shows that the metaheuristic approaches SA and GA significantly outperformed the market-based approach in terms of allocation cost provided for the large-scale problem. This major difference in the allocation cost between the metaheuristic approaches and the market-based approach in solving the large-scale MRTA scenario indicates that market-based approaches might not be the suitable approach for MRS applications with extended number of tasks and robots. On the other hand, the metaheuristic approaches have proven to provide acceptable results in medium and large-scale MRTA scenarios with extended number of tasks and robots.


## 5.3.4. Capabilities Matching MRTA Scenario

Figure5 illustrates the difference in the performances of the three approaches in comparison between SA, GA, and the market-based approach versus time when used to solve the capabilities matching MRTA scenario.Figure 5
Capabilities matching MRTA scenario comparative study.The performance curves of SA and GA in Figure5 demonstrate that at the end of both algorithms the allocations found are of the same cost for both algorithms. On the other hand, GA algorithm was capable of converging to better allocations of lower costs earlier than SA. Thus, if there was no enough time for both algorithms to reach the total number of iterations, the GA would be the suitable algorithm and is expected to provide better results than SA. Although, in this MRTA scenario, the metaheuristic approaches converged earlier than the market-based approach, the market-based approach eventually provided better allocation costs than both metaheuristic algorithms.


## 5.3.5. Time Matching MRTA Scenario

Figure4 illustrates the difference in the performances of the three approaches in comparison between SA, GA, and the market-based approach versus time when used to solve the time matching MRTA scenario.Figure6 shows that SA provides slightly better allocations than GA; however, the total time consumed by SA is significantly lower than total time consumed by GA. Moreover, the performance curves show that GA converges to better solutions faster than SA; however, SA provided better results than GA at the end of each algorithm. The reported results in Figure 6 demonstrate that both metaheuristic approaches provided slightly better allocation costs than the market-based approach. Also, the metaheuristic approaches converged faster than the market-based approach.Figure 6
Time matching MRTA scenario comparative study.


## 5.3.6. Heavily Constrained MRTA Scenario

Figure7 illustrates the difference in the performances of two approaches in comparing SA and the market-based approach versus time when used to solve the time matching MRTA scenario. There were no reported results for the GA as it consumed a large amount of time to provide one solution and thus was not practical.Figure 7
Heavily constrained MRTA scenario comparative study.The reported results in Figure7 show that SA provided better results than the market-based approach although the difference between the two approaches in terms of allocation cost is minimal. However, SA converged much faster than the market-based approach.


## 6. Conclusion

This paper presented a comparative study between two well-known approaches, metaheuristic-based and market-based approaches, that are used extensively to solve the MRTA problem. The main intention in this paper was to propose generic approaches for solving the MRTA problem. The developed approaches were responsible for providing a solution that is not only a feasible solution but also an optimized one which enabled the appropriate use of the available resources and thus increasing the overall system performance and decreasing the costs. Another objective was to propose an approach that is capable of handling real-world application constraints such as time constraints, robot capabilities, and task requirements matching constraints. The proposed approaches were able to handle robotics applications where the number of robots and number of tasks are overextended. The analysis of the experimental and the comparative study that was conducted between the metaheuristic-based and the market-based approaches in this paper results showed that metaheuristic approach outperformed the market-based approach in a number of aspects such as the optimality of the found allocations as well as the total time taken to reach the optimal allocation. The results also demonstrated the better performance of the metaheuristic approaches relative to the market-based approach in the scalability scenarios while both approaches provided nearly similar results in the constraints handling scenarios.In order to sum up the results of this research work, Table2 was constructed to conclude the suitability of each approach as function of application domain and requirements of the MRTA problem. For each algorithm, the stars evaluate the algorithm's efficiency in handling the application scenario; that is, more stars mean better algorithm.Table 2
MRTA approaches applicability results.
Algorithm
Market-based
SA
GA
Small scale
∗
∗
∗
Medium scale
∗
(∗∗∗)
∗∗
Large scale
∗
(∗∗∗)
∗∗
Capabilities matching
(∗∗)
∗
∗
Time matching
∗
∗
∗
Heavily constraints
∗
∗As a future work, more aspects of MRTA will be investigated such as the reallocation capability of the approach to handle the robot failure and the communication burden required to execute the task allocation. The proposed MRTA approaches will be also tested using Khepera III real robots in a newly built tested arena for MRS simulations and experiments in the robotics and autonomous systems (RAS) laboratory.



---

*Source: 256524-2013-11-12.xml*