arXiv:1803.09792v1 [cs.MA] 26 Mar 2018  Min-Max Tours for Task Allocation to Heterogeneous Agents  Amritha Prasad ∗ , Han-Lim Choi †   and Shreyas Sundaram ∗∗  Abstract  We consider a scenario consisting of a set of heterogeneous mobile agents located at a depot, and a set of tasks dispersed over a geographic area. The agents are partitioned into different types.   The tasks are partitioned into specialized tasks that can only be done by agents of a certain type, and generic tasks that can be done by any agent.   The distances between each pair of tasks are specified, and satisfy the triangle inequality. Given this scenario, we address the problem of allocating these tasks among the available agents (subject to type compatibility constraints) while minimizing the maximum cost to tour the allocation by any agent and return to the depot.   This problem is NP-hard, and we give a three phase algorithm to solve this problem that provides 5-factor approximation, regardless of the total number of agents and the number of agents of each type. We also show that in the special case where there is only one agent of each type, the algorithm has an approximation factor of 4.  1   Introduction  Multi-robot systems will play a large role in a variety of modern and future applications including exploration, surveillance, search and rescue operations, cooperative control and operations in haz- ardous environments. In order to effectively utilize these multi-robot systems in such applications, it is necessary to allocate an appropriate set of tasks to each robot or agent in the system. Such problems have been widely considered in the literature [1–5], most typically for the case where all agents are the same.   However, future multi-robot systems are also projected to have a large amount of diversity in terms of the capabilities of the agents, and the applications will consist of tasks that can only be done by agents that possess certain capabilities [6–10].   We address this problem in this paper, namely allocating tasks efficiently to heterogeneous agents while meeting task-agent compatibility constraints. Gerkey and Mataric [11] gives a taxonomy of task allocation in multi-robot systems.   Prorok et.   al. [6] distributes a swarm of heterogeneous robots (of different types, with each type having different traits) among a set of tasks that require specialized capabilities in order to be completed. They optimize the transition rates for each type of robot so that the desired trait distribution is reached, but do not consider travel time between tasks. In this paper, we focus on task allocation to heterogeneous robots (of different types, with different capabilities) such that the task-agent compatibility constraints are satisfied and the maximum tour cost incurred by any agent is mini- mized. The existing literature has several works on task allocation to agents where the total tour cost (i.e., sum of tour costs incurred by all agents) is minimized. Bektas [12] gives an overview on  ∗∗ Amritha Prasad and Shreyas Sundaram are with the School of Electrical and Computer Engineering at Purdue University. Email:   { prasad20,sundara2 } @purdue.edu  † Han-Lim Choi is with the Department of Aerospace Engineering at Korea Advanced Institute of Science and Tech- nology. Email:   hanlimc@kaist.ac.kr
the work on the Traveling Salesperson Problem (TSP) with multiple (homogeneous) salespersons, where the sum of the cost of tours by all salespersons is minimized. Frieze [13] extends Christofides’  3  2   -approximation algorithm [14] for the single Traveling Salesperson Problem to the   k -person Trav- eling Salesperson Problem (where all salespersons are identical and start at the same node).   Xu and Rodrigues [15] provide a   3  2   -approximation algorithm for multiple TSP with a fixed number of depots. Malik, Rathinam and Darbha [16] provide a 2-approximation algorithm for a generalized multiple depot, multiple TSP with symmetric travel costs. Yadlapalli and Rathinam [17] provide a 3-approximation algorithm for a case where two heterogeneous vehicles with associated travel costs start from distinct initial locations and are jointly required to visit a set of targets. Bae and Rathinam [18] provide a 2-approximation algorithm for a special case of the above problem where the travel cost for one vehicle is at most that of the other. As opposed to the above works that minimize the sum of the costs of each agent, the following works focus on minimizing the maximum tour cost incurred by any agent in a group of homogeneous agents. Frederickson, Hecht and Kim [19] give tour splitting heuristics for the   k -person variants of the Traveling Salesperson Problem. Given a tour constructed (using an   F   -approximation algorithm) on a set of nodes, they provide a 1 +   F   −   1  k   factor algorithm that outputs   k   subtours such that the cost of the largest subtour is minimized. Yu and Liu [20] consider networks with multiple depots (or start nodes) and provide a 6-approximation factor algorithm.   Even et.   al. [21] and Arkin et. al. [22] provide a 4-approximation algorithm for a problem known as the min-max tree cover problem.   This was improved by Khani and Salavatipour [23] who proposed a 3-approximation algorithm.   The recent work by Sadeghi and Smith [4] give a decentralized auction based multi- robot task allocation where the objective is to minimize the total time taken to perform all tasks. They consider a case of heterogeneous robots, where the heterogeneity is captured by constraints on the motion of the robots. The above works focus either on minimizing the total cost incurred by all agents or on mini- mizing the maximum cost incurred by any agent in a set of agents, where all agents have the same functionality. In this paper, we combine the idea of heterogeneity in agent functionality with that of minimizing the maximum cost incurred by any agent. Specifically, consider a scenario where a set of tasks at different locations need to be executed; however, not all tasks can be done by all agents and certain task-agent compatibility constraints must be satisfied. Agents are partitioned into different types based on functionality of the agents.   Tasks are partitioned into sets of type- specific tasks and generic tasks, where type-specific tasks can only be performed by agents of a given type and generic tasks can be performed by any agent. To capture this scenario, we present the Heterogeneous Task Allocation Problem (HTAP) which aims to allocate a set of tasks among heterogeneous agents such that the maximum time to complete tasks by any agent is minimized.   This is an important metric, especially when the tasks to be performed are time critical or when the quality of service is characterized by maximum delays. We find tours for each agents that start and end at a start node (e.g., home base), such that the task- agent compatibility constraints are met, and approximately minimize the maximum cost incurred by any agent to complete its tour. The rest of this paper is organized as follows.   In the next section, we state our problem formulation.   We then present a naive algorithm and show that the approximation factor of this algorithm, although bounded, increases linearly with the number of agents. This motivates the need to develop better algorithms that perform well as the number of agents increase. We present two such algorithms in the subsequent section. We first develop an algorithm called   CycleSplit . We leverage insights learned from   CycleSplit   and use it as a baseline to develop an alternate algorithm which we call   HeteroMinMaxSplit .   We show that these are 5-approximation algorithms for HTAP. We also show that in the special case where each of the heterogeneous agents are distinct,
the proposed algorithms haves an approximation factor of 4.  2   Problem Statement  Consider a set of tasks   T   that are required to be completed by a set of   k   heterogeneous agents  A   =   { A 1 ,   A 2 ,...,   A k } . Each agent is one of   m   types . Let   f   :   { 1 , . . . , k } → { 1 , . . . , m }   be a function that takes an agent number as input and outputs the type of that agent. For each   i   ∈ { 1 ,   2 , . . . , m } , let   m i   be the number of agents of type   i , with   ∑ m i =1   m i   =   k .   Let   T   be composed of two broad classes of tasks: type-specific tasks and generic tasks. Type-specific tasks can be performed only by a specific type of agent, whereas generic tasks can be performed by any agent. Let   T 0   denote the set of generic tasks and   T i ,   1   ≤   i   ≤   m , denote the set of type-specific tasks that can be performed by agents of type   i . Thus,   T   =   T 0   ∪   ( ∪ m i =1 T i ). Let all agents start at a node   v s , called the start node (or home base). Consider a complete graph   G ( V, E ) with vertex set   V   =   T   ∪ { v s }   and edge set   E   =   { ( u, v ) :  u, v   ∈   V,   u   6   =   v } .   Let each edge   e   = ( u, v )   ∈   E   have a weight   d ( u, v ) given by the distance between the nodes   u   and   v . Let the direct travel cost between two nodes be the weight of the edge connecting the two nodes in   G . We assume the distances satisfy the triangle inequality. The cost of executing a task is assumed to be very small compared to travel costs and is hence neglected. A tour on a subset of nodes   V   ′   ⊆   V   is a closed path from   v s   through all nodes in   V   ′   (in some order) ending at   v s . All tours start and end at the start vertex   v s . The cost of the tour is defined as the sum of weights of all edges on that tour. Let   C ∗ ( V   ′ ) denote the tour cost of the optimal tour on set   V   ′ . The objective of the allocation problem is to partition the set of tasks   T   among the agents subject to the task-agent compatibility constraints, such that the maximum cost among all agents to tour their allocated tasks is minimized.   This is framed as the Heterogeneous Task Allocation Problem given below.  Heterogeneous Task Allocation Problem (HTAP):  min  S 1 ,S 2 ,...,S k ⊆ T   max  1 ≤ j ≤ k   C ∗ ( S j   ) subject to   ∪ k j =1   S j   =   T, S j   =   V j   ∪   R j   ,   ∀ j   ∈ { 1 ,   2 , . . . , k } , V j   ⊆   T f   ( j ) , R j   ⊆   T 0 .  In the above formulation,   S j   is the task set allocated to agent   A j   , for 1   ≤   j   ≤   k .   The first constraint implies that each task must be executed by some agent. The remaining conditions state that the task set allocated to each agent   A j   is a union of type-specific tasks   V j   (which is a subset of  T f   ( j ) , where   f   ( j ) is the type of agent   A j   ) and generic tasks   R j   (which is a subset of generic tasks  T 0 ).  Remark 1.   Although we do not explicitly specify the condition that a task cannot be performed by more than one agent, minimization of the objective function implicitly ensures that the optimal solution does not have any node appearing in multiple subsets due to the triangle inequality.  Any instance of the Traveling Salesperson Problem (TSP) can be trivially reduced to an instance of the Heterogeneous Task Allocation Problem (HTAP) by setting the number of agents   k   = 1 and all tasks to be generic. Thus, the HTAP is trivially NP-Hard, and has no polynomial time solution unless P = NP. Hence, in the rest of this paper we develop approximation algorithms for HTAP.
An   α -approximation algorithm for a problem is an algorithm that efficiently finds a solution within a factor   α   of the optimum solution for every instance of that problem.  3   A Naive Approximation Algorithm for the Heterogeneous Task Allocation Problem  We start with the following simple algorithm to solve HTAP. In this naive algorithm, we allocate all tasks in   T   to a single agent   A 1 . To every other agent, we allocate the type-specific tasks associated with that agent. Agent   A 1   computes a tour using some approximation algorithm (e.g., Christofides’ algorithm) on set   T   (which includes type-specific tasks of all agents and all the generic tasks). Each other agent   A j   , j   6   = 1, computes a tour on its type-specific tasks using some approximation algorithm (e.g., Christofides’ algorithm). Algorithm 1 describes this naive allocation.  Algorithm 1   NaiveAllocation   Algorithm  1:   procedure   NaiveAllocation ( A, T, G )  2:   Allocate type-specific tasks to each agent of that type.  3:   Allocate all generic tasks to agent   A 1 .  4:   Compute tour (starting and ending at node   v s ) for the set of tasks allocated to each agent using an approximation algorithm.  5:   Return tours for each agent.  6:   end procedure  We provide the approximation factor of this algorithm in the following theorem.  Theorem 1.   Suppose the algorithm that is used to compute the tour for each agent in line 4 of  NaiveAllocation   algorithm has approximation factor   α .   Then,   NaiveAllocation   is an   αk  approximation algorithm for the Heterogeneous Task Allocation Problem (HTAP). Proof.   For 1   ≤   j   ≤   k , let   S ∗  j   denote the set of tasks allocated to agent   A j   under the optimal allocation for HTAP. Note that   S ∗  j   ⊆   T   ∀ j ,   S ∗  j   ∩   S ∗  i   =   ∅   if   j   6   =   i   and   ∪ k j =1 S ∗  j   =   T   . The set   S ∗  j   is given by   S ∗  j   ⊆   T f   ( j )   ∪   R ∗  j   where   R ∗  j   is the subset of tasks in   T 0   allocated to agent   A j   under the optimal allocation policy. Note that   R ∗  j   ⊆   T 0   ∀ j ,   R ∗  j   ∩   R ∗  i   =   ∅   for   j   6   =   i   and   ∪ k j =1 R ∗  j   =   T 0 . For 1   ≤   j   ≤   k , let   S j   denote the set of tasks allocated to agent   A j   by   NaiveAllocation . Note that   S j   ⊆   T   ∀ j ,   S 1   =   T   and   S j   =   T f   ( j ) , j   6   = 1. Let   C ∗ ( · ) denote the cost to optimally tour a given set of tasks and let   C N A ( · ) denote the tour costs returned by the   NaiveAllocation   algorithm. The approximation ratio   R   for the   NaiveAllocation   algorithm is given by  R   = max  1 ≤ j ≤ k   C N A ( S j   )  max  1 ≤ j ≤ k   C ∗ ( S ∗  j   )   =   C N A ( S 1 )  max  1 ≤ j ≤ k   C ∗ ( S ∗  j   ) =   C N A ( T   )  max  1 ≤ j ≤ k   C ∗ ( S ∗  j   )  ≤   αC ∗ ( T   )  max  1 ≤ j ≤ k   C ∗ ( S ∗  j   )   ≤   α ( ∑ k j =1   C ∗ ( S ∗  j   ))  max  1 ≤ j ≤ k   C ∗ ( S ∗  j   )   ≤   αk.  The inequality   C N A ( T   )   ≤   αC ∗ ( T   ) follows from the fact that an   α -approximation algorithm is used to compute the tour in line 4 of   NaiveAllocation . Also,   C ∗ ( T   )   ≤   ∑ k j =1   C ∗ ( S j   ) as   S j   ,   1   ≤   j   ≤   k , form a partition of   T   and the triangle inequality holds.
The previous theorem shows that the approximation factor of even a naive algorithm as the one described by Algorithm 1 is bounded.   However, the bound grows linearly with the number of agents   k .   This motivates us to look for more efficient algorithms to solve the task allocation problem at hand, in particular, algorithms that perform well as the number of agents become large. We provide two constant factor algorithms in the following section.  4   Constant Factor Approximation Algorithms for the Heteroge- neous Task Allocation Problem  4.1   Cycle Splitting Approach  Consider an instance of HTAP. In order to find an allocation of tasks to agents, we must allocate type-specific tasks among agents of the required type and allocate generic tasks among all agents. We approach the problem by handling these two allocations separately. Given a set of tasks   T i   and a number   k , let   TaskSplitter   be any algorithm that splits the set of tasks   T i   into   k   sub-tours   { T i 1 , T i 2 , ..., T ik   }   within some factor   β   of the optimal split (in the min-max sense). For example, Frederickson, Hecht and Kim [19] give a tour splitting heuristic that takes a tour on a set of locations to be visited (first node of which is set as the start node), and a positive integer   k   as input and gives a set of   k   subtours (starting and ending at the start node) as the output. The cost of these subtours are within a factor of 1 +   F   −   1 /k   of the optimal min-max cost, where   F   is the approximation factor of the algorithm used to generate the initial tour on all input locations. Consider the following algorithm to allocate a given set of tasks   T   to a group of   k   heterogeneous agents.  Algorithm 2   Min-Max Tour by   CycleSplit   Algorithm  1:   procedure   CycleSplit ( A, T, G )  2:   for   each agent type   i , 1   ≤   i   ≤   m   do  3:   Find Christofides’ tour (starting and ending at   v s ) on the set of type-specific tasks of type   i .  4:   Use   TaskSplitter   to get   m i   subtours (starting and ending at   v s ) on set   T i .  5:   Allocate one subtour to each agent of type   i .  6:   end for  7:   Find Christofides’ tour (starting and ending at   v s ) on the set of generic tasks   T 0 .  8:   Use   TaskSplitter   to split tour on   T 0   into   k   subtours (starting and ending at   v s ), denoted by   { R 1 , R 2 , . . . , R k } .  9:   Allocate subtour   R j   to agent   A j   ,   1   ≤   j   ≤   k .  10:   Combine the type-specific task subtour and generic task subtour allocated to each agent.  11:   Return a tour for each agent.  12:   end procedure  Theorem 2.   CycleSplit   is a   2 β -approximation algorithm for the Heterogeneous Task Allocation Problem (HTAP), where   β   is the approximation factor of the algorithm TaskSplitter used in steps 4 and 8. Proof.   For 1   ≤   j   ≤   k , let   S ∗  j   be the allocation of tasks to agent   A j   under an optimal algorithm for HTAP. Then,   S ∗  j   can be expressed as   S ∗  j   =   V   ∗  j   ∪   R ∗  j   , where   V   ∗  j   is the subset of type-specific tasks allocated to agent   A j   and   R ∗  j   is the subset of generic tasks assigned to agent   A j   . Let   S j   =   V j   ∪   R j
be the allocation to agent   A j   by the   CycleSplit   algorithm, where   V j   is the subset of type-specific tasks allocated to agent   A j   and   R j   is the subset of generic tasks allocated to agent   A j   . Let   C ∗ ( · ) denote the cost to optimally tour a given set of tasks starting and ending from the node   v s . Let  C T S   ( R j   ) and   C T S   ( V j   ) denote the cost of the subtours   R j   and   V j   returned by the   TaskSplitter  algorithm in steps 4 and 8 respectively. Let   C CS   ( S j   ) denote the cost of a tour on   S j   returned by the   CycleSplit   algorithm. Thus, the approximation factor of the   CycleSplit   algorithm is given by  R   = max  1 ≤ j ≤ k   C CS   ( S j   )  max  1 ≤ j ≤ k   C ∗ ( S ∗  j   )   ≤  max  1 ≤ j ≤ k { C T S   ( V j   ) +   C T S   ( R j   ) }  max  1 ≤ j ≤ k   C ∗ ( S ∗  j   )  ≤  max  1 ≤ j ≤ k   C T S   ( V j   )  max  1 ≤ j ≤ k   C ∗ ( S ∗  j   ) + max  1 ≤ j ≤ k   C T S   ( R j   )  max  1 ≤ j ≤ k   C ∗ ( S ∗  j   )  ≤  max  1 ≤ j ≤ k   C T S   ( V j   )  max  1 ≤ j ≤ k   C ∗ ( V   ∗  j   ) + max  1 ≤ j ≤ k   C T S   ( R j   )  max  1 ≤ j ≤ k   C ∗ ( R ∗  j   )   ,   (1) where we use the facts that   S j   =   V j   ∪   R j   ,   S ∗  j   =   V   ∗  j   ∪   R ∗  j   and that the triangle inequality holds. Consider a case with the same set of type-specific tasks as above, but with no generic tasks. Let   V   ′  1   , V   ′  2   , . . . , V   ′  k   denote the set of tasks allocated to agents under an optimal allocation (in the sense of minimizing the maximum cost to tour any subset).   Since the   CycleSplit   algorithm allocates type-specific tasks independent of generic tasks, the allocation under this algorithm will be   V 1 , V 2 , . . . , V k . Since the set of tasks with only type-specific tasks is a subset of the total set of tasks (including generic tasks), min-max cost for case with only type-specific tasks cannot exceed the min-max cost for the set of total tasks. Thus, max  1 ≤ j ≤ k   C T S   ( V j   )   ≤   β   max  1 ≤ j ≤ k   C ∗ ( V   ′  j   ) .   (2) The inequality in the equation above follows from the fact that   TaskSplitter   algorithm splits a tour into subtours that are within a factor   β   of the optimal min-max cost. By the same argument as before, min-max cost to optimally tour   { V   ′  j   } ,   1   ≤   j   ≤   k   cannot exceed the min-max cost to optimally tour   { V   ∗  j   } ,   1   ≤   j   ≤   k , by the optimality of the partition   { V   ′  j   } ,   1   ≤   j   ≤   k . Thus, max  1 ≤ j ≤ k   C ∗ ( V   ′  j   )   ≤   max  1 ≤ j ≤ k   C ∗ ( V   ∗  j   ) .   (3) Combining equations (2) and (3), we get max  1 ≤ j ≤ k   C T S   ( V j   )   ≤   max  1 ≤ j ≤ k   βC ∗ ( V   ∗  j   ) .   (4) Using a similar procedure as before, this time comparing the allocation of a case with no type specific tasks against the set of all tasks, we get, max  1 ≤ j ≤ k   C T S   ( R j   )   ≤   max  1 ≤ j ≤ k   βC ∗ ( R ∗  j   ) .   (5) Substituting equations (4) and (5) in equation (1), we get  R   ≤   2 β.   (6)
Frederickson, Hecht and Kim [19] provide an algorithm   SPLITOUR 1   that splits a tour (starting and ending at a start-node) on a set of nodes into   k   subtours each starting and ending at the start node. This algorithm has an approximation factor 1 +   F   −   1  k   , where   F   is the approximation factor of the algorithm used for constructing the initial tour.  Corollary 1.   CycleSplit   algorithm using the SPLITOUR algorithm from [19] for task splitting is a   5   −   2  k   approximation algorithm for the Heterogeneous Task Allocation Problem (HTAP). Proof.   The algorithm   SPLITOUR   is a   5  2   −   1  k   factor algorithm to split a tour using Christofides’ algorithm into   k   subtours (since Christofides provides an   F   =   3  2   factor approximation for the initial tour). Equation (1) can be written as  R   ≤  (  5  2   −   1  max  1 ≤ i ≤ m   m i  )  +  (  5  2   −   1  k  )  .   (7) We can upper bound   max  1 ≤ i ≤ m   m i   with   k . Thus,  R   ≤   5   −   2  k .   (8)  Corollary 2.   In the special instance of HTAP where there is exactly one agent of each type (i.e., the heterogeneous agents are distinct),   CycleSplit   is a   4   −   1  k   approximation factor algorithm. Proof.   In this special case,   m i   = 1 ,   1   ≤   i   ≤   m .   Thus   max  1 ≤ i ≤ m   m i   = 1.   So, equation (7) can be simplified as  R   ≤  (  5  2   −   1  )  +  (  5  2   −   1  k  )  = 4   −   1  k .  Remark 2.   From Corollary 1, we see that regardless of the value of   k ,   CycleSplit   is a   5 - approximation algorithm for HTAP. Furthermore, from Corollary 2, we can see that for the special instance of HTAP where all heterogeneous agents are distinct,   CycleSplit   is a   4 -approximation algorithm.  Note that the   CycleSplit   algorithm while using   SPLITOUR   as   TaskSplitter   in lines 4 and 8, splits a TSP tour on the set of tasks into   k   subtours evenly and allocates each subtour to one of the agents. While this approach works well when all agents have same the capacity (or balanced initial load), it may not perform as well when different agents have different capacity or initial load. In a case where agents have type-specific tasks that they must perform, each agent may have different task loads prior to allocation of generic tasks.   In order to optimize the min-max tour cost, it is advantageous to take this into consideration. This motivates the formulation of an algorithm that takes into consideration the existing “load” of each agent from type-specific tasks when allocating generic tasks to agents. To address this, we propose a modified algorithm in the following section.  1 Frederickson, Hecht and Kim call the algorithm   k-SPLITOUR   in their paper; however, we refer to it as   SPLI- TOUR   in order to avoid confusing   k   with the number of agents as we use it in this paper.
4.2   Min-Max Splitting Approach for Heterogeneous Agents  Based on the intuition gained from the   CycleSplit   algorithm, we propose a modified algorithm called   HeteroMinMaxSplit . This algorithm considers the fact that agents may have different “loads” after the allocation of type-specific tasks.   Specifically, instead of splitting a tour on the set of generic tasks into nearly equal segments of a given size, the generic tasks are allocated to agents while taking into consideration the cost incurred by the agent to tour its specific tasks. In the   HeteroMinMaxSplit   algorithm, we allocate tasks to agents in three phases.  •   Phase 1 : Type-specific task allocation  •   Phase 2 : Generic task allocation (accounting for Phase 1 allocation)  •   Phase 3 : Rebalancing tasks within agents of each type. In Phase 1, type-specific tasks are allocated among agents of the associated type as in   Cy- cleSplit . The generic tasks are allocated among all agents in Phase 2. Unlike in   CycleSplit , however, the allocation during Phase 2 tries to balance the total cost incurred by agents by taking into account the existing allocation to agents after Phase 1. Phase 3 is a post-processing step aimed to further balance the load among agents. After Phase 2, all tasks allocated to agents of the same type can be done by all agents in that type. Thus, we pool all tasks allocated to agents of the type  i   into a set   T   ′  i   and re-allocate them to agents of type   i   by splitting the Christofides’ tour on   T   ′  i   into  m i   sub-tours (Algorithm   SPLITOUR   may be used for this purpose [19]).   Balancing the load in this fashion can lower the min-max tour cost by distributing the load more evenly among agents, as we will show later. We present the algorithm in two steps.   We first give an algorithm   HeteroSplit   that takes an additional input   λ , which we take to be a rational number.   This algorithm finds tours (if they exist) for each agent such that cost for each agent to complete its tour is less than   λ .   The  HeteroMinMaxSplit   algorithm then performs a binary search on   λ , running   HeteroSplit   in each iteration, to find the best set of tours for the agents.  Algorithm 3   Heterogeneous Task Split within bound   λ  ⊲   Let   λ   be a rational parameter that denotes the desired upper bound for the tour length for any agent  1:   procedure   HeteroSplit ( A, T, G, λ )  ⊲   Phase 1:   Type-specific task allocation  2:   for   each agent type   i , 1   ≤   i   ≤   m   do  3:   Find Christofides’ tour (starting and ending at   v s ) on the set of type-specific tasks of type   i .  4:   Use   TaskSplitter   to split the tour on   T i   into   m i   subtours (starting and ending at   v s ).  5:   Allocate one subtour to each agent of type   i .  6:   end for  ⊲   Phase 2:   Generic task allocation  7:   Mark all agents as free.  8:   Remove from   G , all vertices in   T i ,   1   ≤   i   ≤   m   and all edges incident on these vertices. Denote the resulting graph by   G ′ .  9:   Mark all tasks in graph   G ′   as unallocated. Find Christofides’ tour starting and ending at  v s   on nodes in   G ′ . Denote the tour by   H .
10:   Consider the next unallocated task, say   t , along   H   starting from   v s .   For each free agent  j , find cost to tour (starting and ending at   v s ) all tasks allocated to it along with   t   using Christofides’ algorithm. Select agent with the minimum cost provided the minimum cost is less than   λ . If no free agent can add the task to its tour without exceeding cost   λ , return failure.  11:   Allocate   t   to the selected free agent.   Keep allocating unallocated tasks along   H   to the selected agent as long as adding the task does not cause the agent’s tour cost to exceed   λ .  12:   Remove the tasks allocated in the previous step from the set of unallocated tasks and mark agent as busy.  13:   Go to step 10 if the set of unallocated tasks is non-empty and free agents remain.  ⊲   Phase 3:   Rebalancing within agent types  14:   for   each agent type   i , 1   ≤   i   ≤   m   do  15:   Deallocate tasks from all   m i   agents of type   i . Let   T   ′  i   denote the set of tasks deallocated from agents of type   i .  16:   Find Christofides’ tour on   T   ′  i   to get tour   H ′ .  17:   Run   TaskSplitter   on   H ′   to split it into   m i   subtours.  18:   Allocate one subtour to each agent of type   i .  19:   end for  20:   Return tours for each agent.  21:   end procedure  A binary search can be performed to find the optimal value for   λ   to be provided as a parameter to   HeteroSplit . The value cannot be less than than twice the largest edge from the start node to any task location, i.e., 2 max  t ∈ T   d ( v s , t ), where   d ( v s , t ) is the distance from the start node   v s   to the location of a task   t . Also,   λ   cannot exceed   max  1 ≤ i ≤ k   C ( T i ) +   C ( T 0 ), where   C ( · ) is the cost to do a Christofides’ tour on the given set of tasks. Hence, we can perform a binary search within this window to find the optimal value of   λ .  Algorithm 4   Min-Max Tour by   HeteroMinMaxSplit   Algorithm  1:   procedure   HeteroMinMaxSplit ( A, T, G )  2:   Do binary search in the interval [2 max  t ∈ T   d ( v s , t ) ,   max  1 ≤ i ≤ k   C ( T i ) +   C ( T 0 )] to find smallest value of   λ   for which   HeteroSplit ( A, T, G, λ ) returns a set of valid tours.  3:   Return the set of tours returned by   HeteroSplit ( A, T, G, λ ).  4:   end procedure  4.3   Bound on Approximation Ratio of HeteroMinMaxSplit Algorithm  For the purpose of applying   SPLITOUR   from Frederickson, Kim and Hecht’s work, we now provide a brief sketch of the algorithm   SPLITOUR   [19].   It takes as input a set of   n   nodes labeled   v 1  through   v n   (with the initial node as the start node) and a positive number   k . First, the algorithm constructs a Christofides’ tour on all the nodes.   Let   L   be the cost of this tour and let   c max  be the maximum direct distance of any node from the start node, i.e.,   c max   =   max  1 <i ≤ n   d ( v 1 , v n ). For 1   ≤   j < k , it finds the largest vertex   v p ( j )   along the tour such that the cost to traverse the tour from the start node to   v p ( j )   does not exceed   j  k   ( L   −   2 c max ) +   c max . It returns   k   subtours ( v 1 , . . . , v p (1) , v 1 ), ( v 1 , v p (1)+1 , . . . , v 1 ),   . . . , ( v 1 , v p ( k − 1)+1 , . . . , v n , v 1 ), each of which has cost less than  1  k   ( L   −   2 c max ) + 2 c max . Frederickson, Hecht and Kim [19] show that if the length of the subtours do
not exceed   1  k   ( L   −   2 c max ) + 2 c max , then the min-max cost of the subtours is no worse than a factor (   5  2   −   1  k   ) of the optimal min-max cost. The following proposition leverages the splitting heuristic summarized above to establish results on the performance of our algorithms.  Theorem 3.   HeteroMinMaxSplit   is a   (5   −   2  k   ) -approximation algorithm for the Heterogeneous Task Allocation Problem (HTAP). Proof.   Let   λ 1   be the maximum cost among all the subtours returned by running   SPLITOUR   on Christofides’ tours on type-specific tasks after line 6 of the   CycleSplit   algorithm, i.e.,   λ 1   = max  1 ≤ j ≤ k   C T S   ( V j   ), where   V j   denotes the set of type-specific tasks allocated to agent   A j   and   C T S   ( · ) denotes the cost associated with the subtour returned by   SPLITOUR . Note that   λ 1   is also the maximum cost after Phase 1 of the   HeteroSplit   algorithm. Running   SPLITOUR   on a Christofides’ tour on the set of generic tasks   T 0   to split it into   k  subtours will returns subtours of length (or cost) no more than   1  k   ( L   −   2 c max ) + 2 c max , where   L   is the length (or cost) of the initial Christofides’ tour on   T 0 , and   c max   is the maximum direct distance of any node in   T 0   from the start node. No matter how each of these subtours are assigned to agents (such that each agent gets one subtour), the total cost is no more than   λ 1   +   1  k   ( L   −   2 c max ) + 2 c max . Set   λ   to be   λ 1   +   1  k   ( L   −   2 c max ) + 2 c max . Consider   HeteroSplit   with this value of   λ . In Phase 1,   HeteroSplit   allocates type-specific tasks to agents, same as steps 2-6 of   CycleSplit .   The maximum cost of any agent’s tour after Phase 1 is   λ 1 . In Phase 2, the   HeteroSplit   algorithm computes a Christofides’ tour on the set of generic tasks.   The algorithm selects an agent that has minimum cost to complete its current allocated tasks in addition to the next task along the Christofides’ tour on generic tasks. The algorithm then allocates tasks along the tour to the selected agent as long as the cost does not exceed   λ . Regardless of which agent gets selected first, the set of tasks that are allocated to the selected agent in   HeteroSplit   will contain the tasks in the first subtour generated by   SPLITOUR . The allocation by   HeteroSplit   to the first selected agent may contain more tasks than the first subtour of   SPLITOUR , but not less. Thus, after allocating tasks to the first agent, the number of tasks left to be allocated to the remaining   k   −   1 agents in  HeteroSplit   is no more than the number of tasks left in the   k   −   1 subtours to be allocated to the remaining   k   −   1 agents in   SPLITOUR . In   SPLITOUR , after the allocation of the first subtour to the an agent, it is guaranteed that the remaining   k   −   1 subtours can be allocated to the remaining   k   −   1 agents, since the allocation is possible regardless of the order in which agents are selected. Given that the set of tasks left for allocation in   HeteroSplit   is no bigger than the set of tasks left to be allocated in   SPLITOUR , it is guaranteed that the remaining tasks can be allocated to other   k   −   1 agents in   HeteroSplit  algorithm for this value of   λ . Thus, by inducting on the number of agents to which tasks have been allocated along the initial tour, the   HeteroSplit   algorithm is guaranteed to return a feasible solution to HTAP for   λ   =   λ 1   +   1  k   ( L   −   2 c max ) + 2 c max . Since   HeteroSplit   checks tour cost against   λ   before further allocation of tasks to an agent, it guarantees that the tour costs for all agents is no more than   λ . Thus, the approximation factor is given by,  R   ≤   λ  max  1 ≤ j ≤ k   C ∗ ( S ∗  j   ) =   λ 1  max  1 ≤ j ≤ k   C ∗ ( S ∗  j   ) +  1  k   ( L   −   2 c max ) + 2 c max  max  1 ≤ j ≤ k   C ∗ ( S ∗  j   )  ≤  max  1 ≤ j ≤ k   C T S   ( V j   )  max  1 ≤ j ≤ k   C ∗ ( V   ∗  j   ) +  1  k   ( L   −   2 c max ) + 2 c max  max  1 ≤ j ≤ k   C ∗ ( R ∗  j   )   (9)
≤  (  5  2   −   1  max  1 ≤ i ≤ m   m i  )  +  (  5  2   −   1  k  )  (10)  ≤   5   −   2  k ,   (11) where equation (9) is given by the triangle inequality and the fact that   V   ∗  j   and   R ∗  j   are subsets of  S ∗  j   . Equation (10) is obtained from the results of Frederickson, Hecht and Kim [19], summarized prior to this theorem. The   HeteroMinMaxSplit   algorithm performs a binary search over   λ   and is thus guaranteed to find the   λ   used above by   HeteroSplit . Thus,   HeteroMinMaxSplit   is a 5 −   2  k   approximation algorithm for HTAP.  Corollary 3.   HeteroMinMaxSplit   is a   (4 −   1  k   ) -approximation algorithm for the special instance of HTAP where all agents are distinct. Proof.   In this special instance,   m i   = 1, for 1   ≤   i   ≤   m . Substituting in equation (10), we get the approximation factor   R   ≤   4   −   1  k   .  From Theorem 3, we see that   HeteroMinMaxSplit   is a 5-approximation algorithm regardless of the value of   k . In this special instance where all heterogeneous agents are distinct, we see from Corollary 3 that   HeteroMinMaxSplit   is a 4-approximation algorithm regardless of the value of  k .  4.4   Examples Illustrating HeteroMinMaxSplit and CycleSplit Algorithms  HeteroMinMaxSplit   takes into consideration the “load” from type-specific tasks while allocating generic tasks and can outperform   CycleSplit   when the type-specific tasks are not uniformly distributed among agents. We illustrate this through the following examples.  Example 1.   Consider the scenario where three agents are collectively required to do nine tasks. Agent   A 1   is a type 1 agent,   A 2   is a type 2 agent and   A 3   is a type 3 agent. All agents are located at node   v s .   The start node   v s   is located at distance   d ′   >   2   from nodes   V 1   and   V 2   as shown in Figure 1. Nodes   A ,   B   and   C   are located at unit distance from node   V 1 , and node   V 2   is located at a distance   d >   3   (such that the triangle inequality is satisfied) from node   C   as shown in Figure 1.   Distances between nodes not directly connected are defined as the sum of distances along the shortest path traversed to reach the node (the graph can be considered as a road network that the agents can traverse).  A t 1   t 2  C t 5   t 6  B t 3   t 4  V 1  t 7   t 8  V 2  t 9  v s  1  1 1   d  d ′   d ′  Figure 1: Task locations in Example 1
Tasks in set   T 0   =   { t 1 , t 2 , t 3 , t 4 , t 5 , t 6 }   are generic tasks.   Tasks   { t 1 , t 2 }   are located at node   A ,  { t 3 , t 4 }   are located at node   B , and   { t 5 , t 6 }   are located at node   C . Agent   A 1   has one type-specific task   t 7 , i.e.   T 1   =   { t 7 } . Agent   A 2   has one type-specific task   t 8 , i.e.   T 2   =   { t 8 } . Tasks   t 7   and   t 8   are located at node   V 1 . Agent   A 3   has one type-specific task   t 9 , i.e.,   T 3   =   { t 9 }   and   t 9   is located at node  V 2 . Both   CycleSplit   and   HeteroMinMaxSplit   algorithms first allocate the type-specific tasks to the respective agents. Thus, agent   A 1   is allocated task   t 7 , agent   A 2   is allocated task   t 8   and agent  A 3   is allocated task   t 9 .  CycleSplit   algorithm splits the generic tasks at nodes   A ,   B   and   C   to the three agents. Thus, agent   A 1   gets allocated tasks   { t 1 , t 2 } , agent   A 2   gets allocated tasks   { t 3 , t 4 } , and agent   A 3   gets allocated tasks   { t 5 , t 6 } . The min-max cost is thus   max { 2 d ′   + 2 ,   2 d ′   + 2 ,   2 d ′   +   d   + 1 }   = 2 d ′   +   d   + 1 . The   HeteroMinMaxSplit   algorithm allocates tasks in Phase 2 based on the allocation done in Phase 1. Thus, for   λ   = 2 d ′   + 4   <   2 d ′   +   d   + 1 ,   HeteroSplit   allocates all tasks at the nodes   A ,   B  and   C   to agents   A 1   and   A 2   (which already travel to node   V 1   to do their type-specific tasks). Thus, tasks   { t 1 , t 2 }   located at node   A   are allocated to agent   A 1 , and tasks   { t 3 , t 4 , t 5 , t 6 }   located at nodes   B  and   C   are allocated to agent   A 2 . Since only one agent of each type is present, agents retain their allocation after Phase 3. The min-max cost is thus   max { 2 d ′   + 2 ,   2 d ′   + 4 ,   2 d ′ }   = 2 d ′   + 4 . For large values of   d ′   and   d ,   HeteroMinMaxSplit   gives a factor of 2 over   CycleSplit   on the min-max tour cost.  Note that in the above example, Phase 3 does not improve the min-max cost. We illustrate the benefit of Phase 3 (rebalancing “load” between agents of a given type) of the   HeteroMinMaxS- plit   algorithm in the following example.  Example 2.   Consider a scenario with two type 1 agents   A 1   and   A 2   located at the start node   v s . Let type-specific tasks for type 1 agents   T 1   =   { t 1 , t 2 }   be located at node   A , which is at a distance of  1   unit from   v s   as shown in Figure 2. Generic tasks   T 0   =   { t 3 , t 4 }   are located at node   B   which is at a distance of   1   from   v s   as shown in Figure 2.  A t 1   t 2  B t 3   t 4  v s  1   1 Figure 2: Task locations in Example 2  In Phase 1, one type-specific task gets allocated to each of the agents, say   t 1   gets allocated to agent   A 1   and   t 2   gets allocated to agent   A 2 . In Phase 2, one generic task gets allocated to each of the agents, say   t 3   gets allocated to agent   A 1   and   t 4   gets allocated to agent   A 2 .   So at the end of Phase 2, both agents need to visit nodes   A   and   B   to complete their allocated tasks. In Phase 3, all tasks allocated in the previous phases to agents of the same type are deallocated and redistributed amongst them. In this phase, tasks   { t 1 , t 2 , t 3 , t 4 }   are pooled and the TaskSplitter algorithm SPLITOUR is run on this set of tasks. Thus, one agent, say   A 1 , gets tasks at node   A  and the other agents   A 2   gets tasks at node   B . In this example, Phase 3 reduces the tour cost from  4   to   2   for both the agents, thus reducing the min-max cost by a factor of 2.  Example 3.   Consider two agents:   A 1   of type 1 and   A 2   of type 2. Task   t 1   is of type 1 and must be performed by agent   A 1 , and tasks   t 2 , t 3   are generic tasks that can be done by either of the agents, i.e.,   T 1   =   { t 1 } , T 2   =   ∅ ,   T 0   =   { t 2 , t 3 } . Task   t 1   is located at node   A . Tasks   t 2   and   t 3   are located at node   B . Agents start from start node   v s .
A t 1  B t 2   t 3  v s  1   1 Figure 3: Task locations in Example 3  CycleSplit   algorithm allocates type-specific task   t 1   to agent   A 1   and splits generic tasks   { t 2 , t 3 }  among agents   A 1   and   A 2 .   Hence,   A 1   is allocated tasks   { t 1 , t 2 }   and   A 2   is allocated   { t 3 } .   The tour costs for agents   A 1   and   A 2   are 4 and 2 respectively, and thus, the min-max tour cost is  max { 4 ,   2 }   = 4 .  HeteroMinMaxSplit   algorithm allocates type-specific task   t 1   to agent   A 1   in Phase 1.   In Phase 2, generic tasks   { t 2 , t 3 }   are split among agents   A 1   and   A 2   based on remaining capacity. For  λ   = 2 ,   HeteroSplit   allocates   { t 1 }   to agent   A 1   and   { t 2 , t 3 }   to agent   A 2 . The min-max tour cost for the tour returned by   HeteroMinMaxSplit   is thus   max { 2 ,   2 }   = 2 .  In this example,   HeteroMinMaxSplit   algorithm gives an improvement by a factor of 2 over  CycleSplit . The following example extends it to a general case with   k   agents.  Example 4.   Consider the following generalization of the previous example for   k   agents.   Agents  { A 1 , A 2 , . . . , A k }   are located at start node   v s . Tasks   T i   =   { t i }   located at node   V i   has to performed by   A i   for   i   = 1 ,   2 , . . . , k   −   1 , and tasks   T 0   =   { t k , t k +1 , . . . , t 2 k − 1 }   located at node   V k   are generic tasks and can be completed by any agent. Let   d ( · ,   · )   denote the distance function. The distance between the start node   v s   and any other node is   1   unit, i.e.,   d ( v s , V i ) = 1 , for   1   ≤   i   ≤   k .   The distance between two nodes   V i   and   V j   is given by   d ( V i , V j   ) =   d ( V i , v s )+ d ( v s , V j   ) = 2   if   i   6   =   j   and zero if   i   =   j . In this case,   CycleSplit   algorithm allocates tasks   { t i , t k + i − 1 }   for agents   A i ,   1   ≤   i   ≤   k   −   1   and task   { t 2 k − 1 }   to agent   A k . This allocation has a min-max tour cost of   4 .   HeteroMinMaxSplit  allocates task   { t i }   to agent   A i   for   1   ≤   i   ≤   k   −   1   and tasks   { t k , t k +1 , . . . , t 2 k − 1 }   to agent   A k . This allocation brings down the min-max tour cost to   2 .  5   Summary  In this work, we considered the Heterogeneous Task Allocation Problem (HTAP) where we aim to allocate tasks to heterogeneous agents subject to agent-task compatibility while minimizing the min-max tour cost.   We provide two approximation algorithms to solve the Heterogeneous Task Allocation Problem (HTAP). We first propose a 2 β   approximation algorithm   CycleSplit , where  β   is the approximation factor of the algorithm used by   CycleSplit   to split tours.   We then use the   CycleSplit   algorithm to develop the   HeteroMinMaxSplit   algorithm which has an approximation ratio 5   −   2  k   , where   k   is the number of agents available. The   HeteroMinMaxSplit  algorithm works in three phases and allocates tasks to agents in a “balanced” way. An interesting extension to the work would be to study the case of allocation when tasks can be done by different subsets of agents (as opposed to agents of only a certain type).  References  [1] K. Sundar and S. Rathinam, “An exact algorithm for a heterogeneous, multiple depot, multiple traveling salesman problem,” in   Unmanned Aircraft Systems (ICUAS), 2015 International Conference on .   IEEE, 2015, pp. 366–371.
[2] H.-L. Choi, L. Brunet, and J. P. How, “Consensus-based decentralized auctions for robust task allocation,”   IEEE Transactions on Robotics , vol. 25, no. 4, pp. 912–926, 2009. [3] L. Bertuccelli, H.-L. Choi, P. Cho, and J. How, “Real-time multi-uav task assignment in dy- namic and uncertain environments,” in   AIAA Guidance, Navigation, and Control Conference , 2009, p. 5776. [4] A. Sadeghi and S. L. Smith, “Heterogeneous task allocation and sequencing via decentralized large neighborhood search,”   Unmanned Systems , vol. 5, no. 02, pp. 79–95, 2017. [5] F. Bullo, E. Frazzoli, M. Pavone, K. Savla, and S. L. Smith, “Dynamic vehicle routing for robotic systems,”   Proceedings of the IEEE , vol. 99, no. 9, pp. 1482–1504, 2011. [6] A. Prorok, M. A. Hsieh, and V. Kumar, “Adaptive distribution of a swarm of heterogeneous robots,”   Acta Polytechnica , vol. 56, no. 1, pp. 67–75, 2016. [7] E. G. Jones, B. Browning, M. B. Dias, B. Argall, M. Veloso, and A. Stentz, “Dynamically formed heterogeneous robot teams performing tightly-coordinated tasks,” in   Robotics and Au- tomation, 2006. ICRA 2006. Proceedings 2006 IEEE International Conference on .   IEEE, 2006, pp. 570–575. [8] T. H. Labella, M. Dorigo, and J.-L. Deneubourg, “Division of labor in a group of robots inspired by ants’ foraging behavior,”   ACM Transactions on Autonomous and Adaptive Systems (TAAS) , vol. 1, no. 1, pp. 4–25, 2006. [9] R. Kilgore, K. Harper, C. Nehme, and M. Cummings, “Mission planning and monitoring for heterogeneous unmanned vehicle teams: A human-centered perspective,” in   AIAA Infotech@ Aerospace 2007 Conference and Exhibit , 2007, p. 2788. [10] Office of Naval Research, “Autonomous systems innovation summit final report,” Office of Naval Research, Tech. Rep., 2008. [11] B. P. Gerkey and M. J. Matari ́ c, “A formal analysis and taxonomy of task allocation in multi- robot systems,”   The International Journal of Robotics Research , vol. 23, no. 9, pp. 939–954, 2004. [12] T. Bektas, “The multiple traveling salesman problem: an overview of formulations and solution procedures,”   Omega , vol. 34, no. 3, pp. 209 – 219, 2006. [13] A. M. Frieze, “An extension of Christofides heuristic to the k-person travelling salesman prob- lem,”   Discrete Applied Mathematics , vol. 6, no. 1, pp. 79–83, 1983. [14] N. Christofides, “Worst-case analysis of a new heuristic for the travelling salesman problem,” DTIC Document, Tech. Rep., 1976. [15] Z. Xu and B. Rodrigues, “A 3/2-approximation algorithm for the multiple TSP with a fixed number of depots,”   INFORMS Journal on Computing , vol. 27, no. 4, pp. 636–645, 2015. [16] W. Malik, S. Rathinam, and S. Darbha, “An approximation algorithm for a symmetric gen- eralized multiple depot, multiple travelling salesman problem,”   Operations Research Letters , vol. 35, no. 6, pp. 747–753, 2007.
[17] S. Yadlapalli, S. Rathinam, and S. Darbha, “3-approximation algorithm for a two depot, heterogeneous traveling salesman problem,”   Optimization Letters , vol. 6, no. 1, pp. 141–152, 2012. [18] J. Bae and S. Rathinam, “A primal-dual approximation algorithm for a two depot heteroge- neous traveling salesman problem,”   Optimization Letters , vol. 10, no. 6, pp. 1269–1285, 2016. [19] G. N. Frederickson, M. S. Hecht, and C. E. Kim, “Approximation algorithms for some routing problems,” in   Foundations of Computer Science, 1976., 17th Annual Symposium on .   IEEE, 1976, pp. 216–227. [20] W. Yu and Z. Liu, “Improved approximation algorithms for min-max and minimum vehicle routing problems,” in   International Computing and Combinatorics Conference .   Springer, 2015, pp. 147–158. [21] G. Even, N. Garg, J. K ̈ onemann, R. Ravi, and A. Sinha, “Min–max tree covers of graphs,”  Operations Research Letters , vol. 32, no. 4, pp. 309–315, 2004. [22] E. M. Arkin, R. Hassin, and A. Levin, “Approximations for minimum and min-max vehicle routing problems,”   Journal of Algorithms , vol. 59, no. 1, pp. 1–18, 2006. [23] M. R. Khani and M. R. Salavatipour, “Improved approximation algorithms for the min-max tree cover and bounded tree cover problems,”   Algorithmica , vol. 69, no. 2, pp. 443–460, 2014.