Min-Max Tours for Task Allocation to Heterogeneous Agents
Amritha Prasad Han-Lim Choi Shreyas Sundaram

  
















problemProblem
conditionCondition
definitionDefinition
theoremTheorem
lemmaLemma
propositionProposition
corollaryCorollary
remarkRemark
assumptionAssumption

exampleExample



breakablealgorithm
  
   

     algorithm
     height.8pt depth0pt 2pt
     
  
     2pt
   
  
[1]▹ #1






Min-Max Tours for Task Allocation to Heterogeneous Agents
    Amritha Prasad^*, Han-Lim Choi^† and Shreyas Sundaram^*
^*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 Technology. Email: hanlimc@kaist.ac.kr

    
=========================================================================================================================================================================================================================================================================================================================================================================

empty
empty


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. 




§ 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 hazardous 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 <cit.>, 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 <cit.>. We address this problem in this paper, namely allocating tasks efficiently to heterogeneous agents while meeting task-agent compatibility constraints.

Gerkey and Mataric <cit.> gives a taxonomy of task allocation in multi-robot systems. Prorok et. al. <cit.> 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 minimized. 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 <cit.> gives an overview on 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 <cit.> extends Christofides' 3/2-approximation algorithm <cit.> for the single Traveling Salesperson Problem to the k-person Traveling Salesperson Problem (where all salespersons are identical and start at the same node). Xu and Rodrigues <cit.> provide a 3/2-approximation algorithm for multiple TSP with a fixed number of depots. Malik, Rathinam and Darbha <cit.> provide a 2-approximation algorithm for a generalized multiple depot, multiple TSP with symmetric travel costs. Yadlapalli and Rathinam <cit.> 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 <cit.> 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 <cit.> 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 <cit.> consider networks with multiple depots (or start nodes) and provide a 6-approximation factor algorithm. Even et. al. <cit.> and Arkin et. al. <cit.> provide a 4-approximation algorithm for a problem known as the min-max tree cover problem. This was improved by Khani and Salavatipour <cit.> who proposed a 3-approximation algorithm. The recent work by Sadeghi and Smith <cit.> 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 minimizing 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.



§ 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 ∑_i=1^m 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 ∪ (∪_i=1^mT_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 ≠ 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  ∪_j=1^k 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).


	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.



§ 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 ≠ 1, computes a tour on its type-specific tasks using some approximation algorithm (e.g., Christofides' algorithm). Algorithm <ref> describes this naive allocation.


	NaiveAllocation Algorithm
	
	


We provide the approximation factor of this algorithm in the following theorem.


	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).
	



	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 ≠ i and ∪_j=1^k 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 ≠ i and ∪_j=1^k 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≠1.	Let C^*(·) denote the cost to optimally tour a given set of tasks and let C_NA(·) 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_NA(S_j)/max_1 ≤ j ≤ k C^*(S^*_j) = C_NA(S_1)/max_1 ≤ j ≤ k C^*(S^*_j) = C_NA(T)/max_1 ≤ j ≤ k C^*(S^*_j)
       ≤α C^*(T)/max_1 ≤ j ≤ k C^*(S^*_j)≤α ( ∑_j=1^kC^*(S^*_j))/max_1 ≤ j ≤ k C^*(S^*_j)≤α k.

	The inequality C_NA(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) ≤∑_j=1^k 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 <ref> 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. 



§ CONSTANT FACTOR APPROXIMATION ALGORITHMS FOR THE HETEROGENEOUS TASK ALLOCATION PROBLEM




 §.§ 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_i1, T_i2, ..., T_ik} within some factor β of the optimal split (in the min-max sense). For example, Frederickson, Hecht and Kim <cit.> 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.


Min-Max Tour by CycleSplit Algorithm





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.




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_TS(R_j) and C_TS(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_TS(V_j) + C_TS(R_j)}/max_1 ≤ j ≤ k C^*(S_j^*)
       ≤max_1 ≤ j ≤ k C_TS(V_j)/max_1 ≤ j ≤ k C^*(S^*_j) + max_1 ≤ j ≤ k C_TS(R_j)/max_1 ≤ j ≤ k C^*(S^*_j)
       ≤max_1 ≤ j ≤ k C_TS(V_j)/max_1 ≤ j ≤ k C^*(V_j^*) + max_1 ≤ j ≤ k C_TS(R_j)/max_1 ≤ j ≤ k C^*(R_j^*),

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_TS(V_j) ≤βmax_1 ≤ j ≤ k C^*(V'_j).


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).


Combining equations (<ref>) and (<ref>), we get 

    max_1 ≤ j ≤ k C_TS(V_j) ≤max_1 ≤ j ≤ kβ C^*(V_j^*) .


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_TS(R_j) ≤max_1 ≤ j ≤ kβ C^*(R_j^*) .


Substituting equations (<ref>) and (<ref>) in equation (<ref>), we get

    R ≤ 2 β.



Frederickson, Hecht and Kim <cit.> provide an algorithm SPLITOUR[Frederickson, Hecht and Kim call the algorithm k-SPLITOUR in their paper; however, we refer to it as SPLITOUR in order to avoid confusing k with the number of agents as we use it in this paper.] 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.


	CycleSplit algorithm using the SPLITOUR algorithm from <cit.> for task splitting is a 5-2/k approximation algorithm for the Heterogeneous Task Allocation Problem (HTAP).




	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 (<ref>) can be written as
	
    R ≤(5/2 - 1/max_1 ≤ i ≤ m m_i) + (5/2 - 1/k).

	
	We can upper bound max_1 ≤ i ≤ m m_i with k. Thus, 
	
    R ≤ 5 - 2/k.




	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.




	In this special case, m_i = 1, 1≤ i ≤ m. Thus max_1 ≤ i ≤ m m_i = 1. So, equation (<ref>) can be simplified as 
	
    R ≤(5/2 - 1 ) + (5/2 - 1/k) = 4 -1/k.




	From Corollary <ref>, we see that regardless of the value of k, CycleSplit is a 5-approximation algorithm for HTAP. Furthermore, from Corollary <ref>, 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.



 §.§ 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 CycleSplit. 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 <cit.>). 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.


	Heterogeneous Task Split within bound λ
	
	


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 ∈ Td(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 λ.


	Min-Max Tour by HeteroMinMaxSplit Algorithm
	
	




 §.§ 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 <cit.>. 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-2c_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-2c_max)+2c_max. Frederickson, Hecht and Kim <cit.> show that if the length of the subtours do not exceed 1/k (L-2c_max)+2c_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.


	HeteroMinMaxSplit is a (5-2/k)-approximation algorithm for the Heterogeneous Task Allocation Problem (HTAP).
	



	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_TS(V_j), where V_j denotes the set of type-specific tasks allocated to agent A_j and C_TS(·) 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-2c_max) + 2c_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-2c_max) + 2c_max. 
	
	Set λ to be λ_1 + 1/k(L-2c_max) + 2c_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-2c_max) + 2c_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-2c_max) + 2c_max/max_1 ≤ j ≤ k C^*(S^*_j)
       ≤max_1 ≤ j ≤ k C_TS(V_j)/max_1 ≤ j ≤ k C^*(V^*_j)+ 1/k(L-2c_max) + 2c_max/max_1 ≤ j ≤ k C^*(R^*_j)
       ≤(5/2 - 1/max_1 ≤ i ≤ m m_i) + (5/2 - 1/k) 
       ≤ 5 - 2/k,

	where equation (<ref>) is given by the triangle inequality and the fact that V^*_j and R^*_j are subsets of S^*_j. Equation (<ref>) is obtained from the results of Frederickson, Hecht and Kim <cit.>, 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. 



	HeteroMinMaxSplit is a (4-1/k)-approximation algorithm for the special instance of HTAP where all agents are distinct.
	



	In this special instance, m_i = 1, for 1≤ i ≤ m. Substituting in equation (<ref>), we get the approximation factor R ≤ 4 - 1/k. 


From Theorem <ref>, 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 <ref> that HeteroMinMaxSplit is a 4-approximation algorithm regardless of the value of k.



 §.§ 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.


	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 <ref>. 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 <ref>. 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).
	
	
	
	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{2d'+2, 2d'+2, 2d'+d+1} = 2d'+d+1.
	
	The HeteroMinMaxSplit algorithm allocates tasks in Phase 2 based on the allocation done in Phase 1. Thus, for λ = 2d'+ 4 < 2d'+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{2d'+2, 2d'+4, 2d'} = 2d'+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 HeteroMinMaxSplit algorithm in the following example. 


	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 <ref>. 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 <ref>.
	
	
	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.
	



	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. 
	
	
	
	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.


	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_2k-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 ≠ 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_2k-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_2k-1} to agent A_k. This allocation brings down the min-max tour cost to 2.




§ 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).

IEEEtran


