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 = {A1, A2,..., Ak}. 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 mi be the number of agents of type i, with Pm
i=1 mi = 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 T0 denote the
set of generic tasks and Ti, 1 ≤i ≤m, denote the set of type-specific tasks that can be performed
by agents of type i. Thus, T = T0 ∪(∪m
i=1Ti). Let all agents start at a node vs, called the start
node (or home base).
Consider a complete graph G(V, E) with vertex set V = T ∪{vs} 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 vs through all nodes in V ′ (in some order)
ending at vs. All tours start and end at the start vertex vs. 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
S1,S2,...,Sk⊆T
max
1≤j≤k C∗(Sj)
subject to
∪k
j=1 Sj = T,
Sj = Vj ∪Rj, ∀j ∈{1, 2, . . . , k},
Vj ⊆Tf(j), Rj ⊆T0.
In the above formulation, Sj is the task set allocated to agent Aj, 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 Aj is a union of type-specific tasks Vj (which is a subset of
Tf(j), where f(j) is the type of agent Aj) and generic tasks Rj (which is a subset of generic tasks
T0).
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 A1. To every other agent, we allocate the type-specific tasks associated
with that agent. Agent A1 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 Aj, j ̸= 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 A1.
4:
Compute tour (starting and ending at node vs) 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 Aj under the optimal
allocation for HTAP. Note that S∗
j ⊆T ∀j, S∗
j ∩S∗
i = ∅if j ̸= i and ∪k
j=1S∗
j = T. The set S∗
j is
given by S∗
j ⊆Tf(j) ∪R∗
j where R∗
j is the subset of tasks in T0 allocated to agent Aj under the
optimal allocation policy. Note that R∗
j ⊆T0 ∀j, R∗
j ∩R∗
i = ∅for j ̸= i and ∪k
j=1R∗
j = T0.
For 1 ≤j ≤k, let Sj denote the set of tasks allocated to agent Aj by NaiveAllocation. Note
that Sj ⊆T ∀j, S1 = T and Sj = Tf(j), j ̸= 1. Let C∗(·) denote the cost to optimally tour a given
set of tasks and let CNA(·) 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 CNA(Sj)
max
1≤j≤k C∗(S∗
j ) =
CNA(S1)
max
1≤j≤k C∗(S∗
j ) =
CNA(T)
max
1≤j≤k C∗(S∗
j )
≤
αC∗(T)
max
1≤j≤k C∗(S∗
j ) ≤
α(Pk
j=1 C∗(S∗
j ))
max
1≤j≤k C∗(S∗
j )
≤αk.
The inequality CNA(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) ≤Pk
j=1 C∗(Sj) as Sj, 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 Ti and a number k, let TaskSplitter be any algorithm that splits the set of
tasks Ti into k sub-tours {Ti1, Ti2, ..., Tik} 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 vs) on the set of type-specific tasks of
type i.
4:
Use TaskSplitter to get mi subtours (starting and ending at vs) on set Ti.
5:
Allocate one subtour to each agent of type i.
6:
end for
7:
Find Christofides’ tour (starting and ending at vs) on the set of generic tasks T0.
8:
Use TaskSplitter to split tour on T0 into k subtours (starting and ending at vs), denoted
by {R1, R2, . . . , Rk}.
9:
Allocate subtour Rj to agent Aj, 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 Aj 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 Aj and R∗
j is the subset of generic tasks assigned to agent Aj. Let Sj = Vj ∪Rj
be the allocation to agent Aj by the CycleSplit algorithm, where Vj is the subset of type-specific
tasks allocated to agent Aj and Rj is the subset of generic tasks allocated to agent Aj. Let C∗(·)
denote the cost to optimally tour a given set of tasks starting and ending from the node vs. Let
CTS(Rj) and CTS(Vj) denote the cost of the subtours Rj and Vj returned by the TaskSplitter
algorithm in steps 4 and 8 respectively. Let CCS(Sj) denote the cost of a tour on Sj returned by
the CycleSplit algorithm. Thus, the approximation factor of the CycleSplit algorithm is given
by
R =
max
1≤j≤k CCS(Sj)
max
1≤j≤k C∗(S∗
j ) ≤
max
1≤j≤k{CTS(Vj) + CTS(Rj)}
max
1≤j≤k C∗(S∗
j )
≤
max
1≤j≤k CTS(Vj)
max
1≤j≤k C∗(S∗
j ) +
max
1≤j≤k CTS(Rj)
max
1≤j≤k C∗(S∗
j )
≤
max
1≤j≤k CTS(Vj)
max
1≤j≤k C∗(V ∗
j ) +
max
1≤j≤k CTS(Rj)
max
1≤j≤k C∗(R∗
j) ,
(1)
where we use the facts that Sj = Vj ∪Rj, 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 V1, V2, . . . , Vk. 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 CTS(Vj) ≤β 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 CTS(Vj) ≤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 CTS(Rj) ≤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 SPLITOUR1 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 mi
!
+
 
5
2 −1
k
!
.
(7)
We can upper bound max
1≤i≤m mi 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, mi = 1, 1 ≤i ≤m. Thus max
1≤i≤m mi = 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.
1Frederickson, 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
mi 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 vs) on the set of type-specific tasks of
type i.
4:
Use TaskSplitter to split the tour on Ti into mi subtours (starting and ending at vs).
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 Ti, 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
vs on nodes in G′. Denote the tour by H.
10:
Consider the next unallocated task, say t, along H starting from vs. For each free agent
j, find cost to tour (starting and ending at vs) 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 mi 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 mi 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(vs, t), where d(vs, t) is the distance from the start node vs to
the location of a task t. Also, λ cannot exceed max
1≤i≤k C(Ti) + C(T0), 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(vs, t),
max
1≤i≤k C(Ti) + C(T0)] 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 v1
through vn (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 cmax
be the maximum direct distance of any node from the start node, i.e., cmax = max
1<i≤n d(v1, vn).
For 1 ≤j < k, it finds the largest vertex vp(j) along the tour such that the cost to traverse
the tour from the start node to vp(j) does not exceed j
k(L −2cmax) + cmax. It returns k subtours
(v1, . . . , vp(1), v1), (v1, vp(1)+1, . . . , v1), . . ., (v1, vp(k−1)+1, . . . , vn, v1), each of which has cost less than
1
k(L −2cmax) + 2cmax. Frederickson, Hecht and Kim [19] show that if the length of the subtours do
not exceed 1
k(L −2cmax) + 2cmax, 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 CTS(Vj), where Vj denotes the set of type-specific tasks allocated to agent Aj and CTS(·)
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 T0 to split it into k
subtours will returns subtours of length (or cost) no more than 1
k(L −2cmax) + 2cmax, where L is
the length (or cost) of the initial Christofides’ tour on T0, and cmax is the maximum direct distance
of any node in T0 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 −2cmax) + 2cmax.
Set λ to be λ1 + 1
k(L −2cmax) + 2cmax. 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 −2cmax) + 2cmax.
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 −2cmax) + 2cmax
max
1≤j≤k C∗(S∗
j )
≤
max
1≤j≤k CTS(Vj)
max
1≤j≤k C∗(V ∗
j ) +
1
k(L −2cmax) + 2cmax
max
1≤j≤k C∗(R∗
j)
(9)
≤
 
5
2 −
1
max
1≤i≤m mi
!
+
 
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, mi = 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 A1 is a type 1 agent, A2 is a type 2 agent and A3 is a type 3 agent. All agents are located
at node vs. The start node vs is located at distance d′ > 2 from nodes V1 and V2 as shown in
Figure 1. Nodes A, B and C are located at unit distance from node V1, and node V2 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
t1 t2
C
t5 t6
B
t3 t4
V1
t7 t8
V2
t9
vs
1
1
1
d
d′
d′
Figure 1: Task locations in Example 1
Tasks in set T0 = {t1, t2, t3, t4, t5, t6} are generic tasks. Tasks {t1, t2} are located at node A,
{t3, t4} are located at node B, and {t5, t6} are located at node C. Agent A1 has one type-specific
task t7, i.e. T1 = {t7}. Agent A2 has one type-specific task t8, i.e. T2 = {t8}. Tasks t7 and t8 are
located at node V1. Agent A3 has one type-specific task t9, i.e., T3 = {t9} and t9 is located at node
V2.
Both CycleSplit and HeteroMinMaxSplit algorithms first allocate the type-specific tasks
to the respective agents. Thus, agent A1 is allocated task t7, agent A2 is allocated task t8 and agent
A3 is allocated task t9.
CycleSplit algorithm splits the generic tasks at nodes A, B and C to the three agents. Thus,
agent A1 gets allocated tasks {t1, t2}, agent A2 gets allocated tasks {t3, t4}, and agent A3 gets
allocated tasks {t5, t6}. 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 A1 and A2 (which already travel to node V1 to do their type-specific tasks). Thus,
tasks {t1, t2} located at node A are allocated to agent A1, and tasks {t3, t4, t5, t6} located at nodes B
and C are allocated to agent A2. 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 HeteroMinMaxS-
plit algorithm in the following example.
Example 2. Consider a scenario with two type 1 agents A1 and A2 located at the start node vs.
Let type-specific tasks for type 1 agents T1 = {t1, t2} be located at node A, which is at a distance of
1 unit from vs as shown in Figure 2. Generic tasks T0 = {t3, t4} are located at node B which is at
a distance of 1 from vs as shown in Figure 2.
A
t1 t2
B
t3 t4
vs
1
1
Figure 2: Task locations in Example 2
In Phase 1, one type-specific task gets allocated to each of the agents, say t1 gets allocated to
agent A1 and t2 gets allocated to agent A2. In Phase 2, one generic task gets allocated to each of
the agents, say t3 gets allocated to agent A1 and t4 gets allocated to agent A2. 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 {t1, t2, t3, t4} are pooled and the TaskSplitter
algorithm SPLITOUR is run on this set of tasks. Thus, one agent, say A1, gets tasks at node A
and the other agents A2 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: A1 of type 1 and A2 of type 2. Task t1 is of type 1 and must be
performed by agent A1, and tasks t2, t3 are generic tasks that can be done by either of the agents,
i.e., T1 = {t1}, T2 = ∅, T0 = {t2, t3}. Task t1 is located at node A. Tasks t2 and t3 are located at
node B. Agents start from start node vs.
A
t1
B
t2 t3
vs
1
1
Figure 3: Task locations in Example 3
CycleSplit algorithm allocates type-specific task t1 to agent A1 and splits generic tasks {t2, t3}
among agents A1 and A2.
Hence, A1 is allocated tasks {t1, t2} and A2 is allocated {t3}.
The
tour costs for agents A1 and A2 are 4 and 2 respectively, and thus, the min-max tour cost is
max{4, 2} = 4.
HeteroMinMaxSplit algorithm allocates type-specific task t1 to agent A1 in Phase 1. In
Phase 2, generic tasks {t2, t3} are split among agents A1 and A2 based on remaining capacity. For
λ = 2, HeteroSplit allocates {t1} to agent A1 and {t2, t3} to agent A2. 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
{A1, A2, . . . , Ak} are located at start node vs. Tasks Ti = {ti} located at node Vi has to performed
by Ai for i = 1, 2, . . . , k−1, and tasks T0 = {tk, tk+1, . . . , t2k−1} located at node Vk are generic tasks
and can be completed by any agent. Let d(·, ·) denote the distance function. The distance between
the start node vs and any other node is 1 unit, i.e., d(vs, Vi) = 1, for 1 ≤i ≤k. The distance
between two nodes Vi and Vj is given by d(Vi, Vj) = d(Vi, vs)+d(vs, Vj) = 2 if i ̸= j and zero if i = j.
In this case, CycleSplit algorithm allocates tasks {ti, tk+i−1} for agents Ai, 1 ≤i ≤k −1 and
task {t2k−1} to agent Ak. This allocation has a min-max tour cost of 4. HeteroMinMaxSplit
allocates task {ti} to agent Ai for 1 ≤i ≤k −1 and tasks {tk, tk+1, . . . , t2k−1} to agent Ak. 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.