arXiv:1308.3956v3  [cs.RO]  31 Jul 2014
1
Target Assignment in Robotic Networks:
Distance Optimality Guarantees and
Hierarchical Strategies
Jingjin Yu, Soon-Jo Chung, Petros G. Voulgaris
Abstract
We study the problem of multi-robot target assignment to minimize the total distance traveled by
the robots until they all reach an equal number of static targets. In the first half of the paper, we
present a necessary and sufficient condition under which true distance optimality can be achieved for
robots with limited communication and target-sensing ranges. Moreover, we provide an explicit, non-
asymptotic formula for computing the number of robots needed to achieve distance optimality in terms
of the robots’ communication and target-sensing ranges with arbitrary guaranteed probabilities. The
same bounds are also shown to be asymptotically tight.
In the second half of the paper, we present suboptimal strategies for use when the number of
robots cannot be chosen freely. Assuming first that all targets are known to all robots, we employ a
hierarchical communication model in which robots communicate only with other robots in the same
partitioned region. This hierarchical communication model leads to constant approximations of true
distance-optimal solutions under mild assumptions. We then revisit the limited communication and
sensing models. By combining simple rendezvous-based strategies with a hierarchical communication
model, we obtain decentralized hierarchical strategies that achieve constant approximation ratios with
respect to true distance optimality. Results of simulation show that the approximation ratio is as low as
1.4.
Jingjin Yu is currently with the Computer Science and Artificial Intelligence Lab at the Massachusetts Institute of Technology.
E-mail: jingjin@csail.mit.edu. The work was completed when J. Yu was at the University of Illinois at Urbana-Champaign. Soon-
Jo Chung and Petros G. Voulgaris are with the Coordinated Science Lab and the Department of Aerospace Engineering at the
University of Illinois at Urbana-Champaign. E-mail: {sjchung, voulgari}@illinois.edu. This work was supported in part by
AFOSR grant FA95501210193, NSF grant IIS-1253758, and NSF grant ECCS 10-27437.
2
I. INTRODUCTION
In this paper, we study the permutation-invariant assignment of a set of networked robots
to a set of targets of equal cardinality. Focusing on minimizing the total distance traveled by
the robots in a planar setting, we seek optimality guarantees and near-optimal strategies. For
robot-to-robot communication, we investigate both a simple circular range-based model and a
region-based model in which all robots within the same region can communicate with each other.
When we consider the limited target-sensing capability of the robots, a circular range sensing
model is used.
The class of problems that we study is denoted as target assignment in robotic networks as
it shares many similarities with the problems studied in Smith and Bullo (2009). In Smith and
Bullo (2009), the authors characterized the performance of ETSP1 ASSGMT and GRID ASSGMT
algorithms (strategies) in achieving time optimality (i.e., minimizing the time until every target
is occupied). In contrast, we focus on minimizing the total distance traveled by all robots with
significantly different assumptions on the communication and sensing models of the robots. The
total distance serves as a proper proxy to quantities such as the total energy consumption of
all the robots. Note that a distance-optimal solution for the target assignment problem generally
does not imply time optimality and vice versa Yu and LaValle (2012).
As its name implies, the problem of target assignment in robotic networks requires solving an
assignment (or matching) problem. The assignment problem is extensively studied in the area of
combinatorial optimization, with polynomial time algorithms available for solving many of its
variations Bertsekas (1988); Bertsekas and CastaŻnon (1991); Burkard et al. (2012); Edmonds and
Karp (1972); Kuhn (1955); Zavlanos et al. (2008). If we instead put more emphasis on multi-robot
systems, the problems of robotic task allocation Ji et al. (2006); Tanner et al. (2007); Treleaven
et al. (2013); Zavlanos and Pappas (2008), swarm reconfiguration Chung et al. (2013), multi-
robot path planning Kloder and Hutchinson (2006); Sharma et al. (2007); Turpin et al. (2013),
and multi-agent consensus Cort´es et al. (2006); Jadbabaie et al. (2003); Lin et al. (2007a,b) are
relevant. For a more comprehensive review on these topics, see Bullo et al. (2009).
Our work is also closely related to the study of the connectivity of wireless networks. An in-
teresting result Xue and Kumar (2004) showed that, if n robots are uniformly randomly scattered
1ETSP stands for the Euclidean traveling salesman problem.
3
in a unit square, then each robot needs to communicate with k = Θ(logn) nearest neighbors for
the entire robotic network to be asymptotically connected as n approaches infinity. In particular,
the authors of Xue and Kumar (2004) showed that k < 0.074logn leads to an asymptotically
disconnected network whereas k > 5.1774logn guarantees asymptotic connectivity. This pair of
bounds was subsequently improved and extended in Balister et al. (2005). These nearest neighbor
based connectivity models were further studied in Freris et al. (2010); Ganesh and Xue (2007);
Mao and Anderson (2013), to list a few. In many of these settings, a geometric graph structure
is used Penrose (2003).
This research effort brings forth three contributions. First, for robots with limited range-
based target-sensing and communication capabilities (the ranges are captured by radii rsense and
rcomm, respectively), we derive necessary and sufficient conditions for ensuring a distance-optimal
solution. In particular, we provide a probabilistic estimate of the number of robots (denoted by
n) sufficient for all robots to form a connected network for a fixed communication radius rcomm.
In contrast to the asymptotic connectivity results from Xue and Kumar (2004); Penrose (1997),
we give n as an explicit function of rcomm that is also non-asymptotic. Therefore, our bounds
hold without requiring n →∞. We further show that the same bounds are asymptotically tight
when a high probability guarantee is required.
Second, allowing the robots to have global target-sensing capabilities coupled with a region-
based communication model, we show that an infinite family of hierarchical strategies can lead
to decentralized target assignments while ensuring that the total expected distance traveled by the
robots is asymptotically within a constant multiple of the optimal distance. Our simulation results
show that this bound can often be smaller than two. Moreover, because hierarchical strategies
avoid running a centralized assignment algorithm, significant savings on computation time (in
certain cases, a speedup of 1000 times or more) are achieved.
Third, for robots with global target-sensing capabilities and a range-based communication
model, hierarchical strategies (for assignment) and rendezvous-based strategies (for compen-
sating for the lack of global communication) are combined to obtain decentralized suboptimal
algorithms. These hybrid strategies, under mild assumptions, preserve the constant approximation
ratios on distance optimality achieved by the “pure” hierarchical strategies. We further show that
the global target-sensing assumption can be removed without affecting asymptotic optimality.
Portions of this work were presented in Yu et al. (2014a,b) for the early dissemination of
4
results. Compared with Yu et al. (2014a,b), this paper provides a more comprehensive view
of the results along with complete proofs for all theorems. Many of the proofs have been
significantly improved to illustrate more clearly proof techniques that may be of interest on their
own. In addition, the current paper discusses extensively generalizations of the stochastic target
assignment problem to mismatching number of robots and targets, and to higher dimensions.
The rest of the paper is organized as follows. In Section II, we present notations and well-
known results from other branches of research needed for the development of our results. After
stating the problem formally in Section III, we then elaborate on the three stated contributions in
Sections IV-VI. We present results of simulation studies in Section VII to validate our theoretical
results and conclude in Section VIII.
II. PRELIMINARIES
In this section, we review results on the balls and bins problem, linear assignment, and random
geometric graphs. The symbols R,R+,N denote the set of real numbers, the set of positive reals,
and the set of positive integers, respectively. For a positive real number x, logx denotes the natural
logarithm of x; the function ⌈x⌉(resp., ⌊x⌋) denotes the smallest (resp., largest) integer that is
larger (resp., smaller) than or equal to x. | · | denotes the cardinality for a set and the absolute
value for a real number. We use ∥v∥2 to denote the Euclidean 2-norm of a vector v. The unit
square [0,1]2 ⊂R2 is denoted as Q. The expectation of a random variable X is denoted as E[X].
We use E(·) to represent a probabilistic event and the probability with which an event e occurs
is denoted as P(e).
Given two functions f,g : R+ →R+, f(x) = O(g(x)) if and only if there exist MO,xO ∈R+
such that
∀x > xO,| f(x)| ≤MO|g(x)|.
Similarly, f(x) = Ω(g(x)) if and only if there exist MΩ,xΩ∈R+ such that
∀x > xΩ,| f(x)| ≥MΩ|g(x)|.
If f(x) = O(g(x)) and f(x) = Ω(g(x)), then we say f(x) = Θ(g(x)). Finally, f(x) = o(g(x))
(resp., f(x) = ω(g(x))) if and only if f(x) = O(g(x)) (resp., f(x) = Ω(g(x))) and f(x) = Θ(g(x))
does not hold.
5
A. Balls and Bins
The well-studied problem in probability theory known as the urns-problem, or the problem
of balls and bins, considers the distribution generated as a number of balls are randomly tossed
into a set of bins. The following classical result on the ball and bins problem is due to Erd˝os
and R´enyi.
Theorem 1 (Balls and Bins Erd˝os and R´enyi (1961)) Suppose that a number of balls are
tossed uniformly randomly into m bins, one ball per time step. Let Tk denote the first time
such that k balls are collected in every bin. Then for any real number c,
lim
m→∞P(Tk < mlogm+(k −1)m loglog m+cm) = e−e
−
c
(k−1)! .
(1)
It is worth noting that the proof of Theorem 1 is fairly short and elegant, employing only
basic tools from analysis and combinatorics. A useful corollary for k = 1 follows readily.
Corollary 2 For an arbitrary real number c, suppose that no fewer than (mlogm +cm) balls
are tossed uniformly randomly into m bins. As m →∞, every bin contains at least one ball with
probability e−e−c.
PROOF. In (1), letting k = 1 yields
lim
m→∞P(T1 < mlogm+cm) = e−e−c.
(2)
The corollary directly follows (2) (recall that T1 is the number of tosses needed so that every
bin has at least one ball).
□
Corollary 2 says that T1 = mlogm is a sharp threshold. Letting c = 5 in (2) yields that the
probability of every bin being occupied by at least one ball is greater than 0.99 when at least
mlogm + 5m balls are tossed. On the other hand, the same probability is no more than 0.001
when no more than mlogm−2m balls are tossed.
B. Linear Assignment Problem
The (linear) assignment problem, as a fundamental combinatorial optimization problem, can
be defined as follows.
6
Problem 1 (Linear Assignment) Given two finite sets X and Y with |X| = |Y|, together with a
weight function C : X ×Y →R, find a bijection f : X →Y that minimizes the cost
∑
x∈X
C(x, f(x)).
(3)
Problem 1 is also called the perfect weighted bipartite matching problem. Here, the mapping
C is essentially a square matrix that can be used to represent a variety of weights, such as the
Euclidean distance when X and Y represent physical locations. The Hungarian method for the
assignment problem, proposed by Kuhn Kuhn (1955), has an O(n4) running time, which was
subsequently improved to O(n3) by Edmonds and Karp Edmonds and Karp (1972). Many other
algorithms for the assignment problem exist, including other primal-dual (linear programming)
methods Burkard et al. (2012), auction based methods Bertsekas (1988), and parallel algorithms
Bertsekas and CastaŻnon (1991); Zavlanos et al. (2008). Nevertheless, the strongly polynomial2
O(n3) Hungarian method remains as the fastest exact (sequential) algorithm, which we use in
our simulations.
When X and Y are restricted to points on the plane with the weight function C being the
Euclidean distances between the points, the special linear assignment problem is known as the
Euclidean bipartite matching problem, which can be solved exactly using an O(n2.5logn) primal-
dual algorithm Vaidya (1989). Alternatively, near linear time approximation algorithms can yield
near optimal solutions with high probability Sharathkumar and Agarwal (2012).3
C. Random Geometric Graphs
Let X = {x1,...,xn} be a set of n points in the unit square Q. For a fixed communication radius
rcomm, the geometric graph G over this set of points is formed by taking each point as a vertex
and connecting any two vertices whose underlying points x1 and x2 satisfy ∥x1 −x2∥2 ≤rcomm.
When X is selected randomly following some distribution, the resulting graph is called a random
geometric graph.
2A polynomial time algorithm runs in strongly polynomial time only if its running time does not depend on the size of the
input parameters. Note that n is the number of input parameters in this case.
3Although algorithms from Sharathkumar and Agarwal (2012); Vaidya (1989) have theoretically faster running times than the
Hungarian method and apply to the problem that we study, they are more difficult to implement and slower in practice unless
|X| is very large because they are not strongly polynomial time algorithms like the Hungarian method.
7
Properties of random geometric graphs have been studied extensively; see Penrose (2003) for
a thorough coverage. One such property is the connectivity of these graphs, which is of particular
interest to wireless communication and robotic networks.
Theorem 3 (Random Geometric Graphs Penrose (1997)) Let G be a random geometric graph
obtained following the uniform distribution over the unit square for some n and rcomm. Then for
any real number c, as n →∞,
P(G is connected | πnr2
comm −logn ≤c) = e−e−c.
(4)
From (4), it is possible to estimate the number of robots required to guarantee a connected
geometric graph G.
III. TARGET ASSIGNMENT IN ROBOTIC NETWORKS
In this section, we formally define the problem of target assignment in robotic networks and
the optimality objective.
A. Problem Statement
Let X0 = {x0
1,...,x0
n} and Y 0 = {y0
1,...,y0
n} be two sets of points (the superscript emphasizes
that these points are obtained at the start time t = 0) in the unit square Q 4, selected uniformly
randomly. Place n = |X0| = |Y 0| point robots on the points in X0, with robot ai occupying x0
i . Each
robot has a unique integer label (e.g., i). In general, we denote robot ai’s location (coordinates)
at time t ≥0 as xi(t). The basic task (to be formally defined) is to move the robots so that at
some final time t f ≥0, every y ∈Y 0 is occupied by a robot. We may assume that there is a final
time t f
i for each robot ai, such that xi(t) ≡xi(t f
i ) for t ≥t f
i . For convenience, we also refer to
X0 and Y 0 as the set of initial locations and the set of target locations, respectively.
Motion model: The robots are single integrators, i.e., ˙xi(t) = ui(t) with ui(t) being piece-wise
smooth and ∥ui(t)∥2 ∈{0,1}. We assume the size of the robots is negligible with respect to the
distance they travel and ignore collisions between robots.
4Our results are scale-invariant because all the theorems hold for squares of any size with proper scaling. Hence, a unit square
environment is used throughout the paper.
8
Communication Model 1: We study two communication models in this paper. In the first
communication model, a robot ai may communicate with other robots within a disc of radius
rcomm centered at xi(t). At any given time t ≥0, we define the (undirected) communication graph
G(t), which is a geometric graph that changes over time, as follows. G(t) has n vertices v1,...,vn,
corresponding to robots a1,...,an, respectively. There is an edge between two vertices vi and vj
if the corresponding robot locations xi(t) and xj(t), respectively, satisfy ∥xi(t)−xj(t)∥2 ≤rcomm.
Figure 1(a) provides an example of a (disconnected) communication graph.
Given our focus on distance optimality, we make the simplifying assumption that all robots
corresponding to vertices in a connected component of the communication graph may exchange
information instantaneously. In other words, robots in a connected component of G(t) can be
treated as a single robot insofar as decision making is concerned.
rcomm
(a) Comm. model 1
(b) Comm. model 2
Fig. 1.
(a) The communication graph (solid blue nodes and edges) for a set of robots under Communication Model 1 with
a communication radius of rcomm. Robots (blue dots) in the same connected component of a communication graph can freely
communicate with each other. (b) The communication graph for a set of robots under Communication Model 2 with m = b2 = 9.
Communication Model 2: The unit square Q is divided into m = b2 equal-sized smaller
squares (regions).5 Robots within each region can communicate with one another but robots
from different regions cannot exchange information (see, e.g., Fig. 1(b)). This model mimics
the natural (geometrical) resource allocation process in which supplies and demands are first
matched locally; the surpluses and deficits within each region then get balanced out at larger
regions, giving rise to a hierarchical strategy.
5In this paper, m is frequently used to denote the number of small squares in a division of the unit square Q and b = √m is
the number of resulting partitions on an edge of the unit square. The value of m and b may vary.
9
Target-sensing model: We assume that a robot is aware of a point y ∈Y 0 if ∥y−xi(t)∥2 ≤rsense,
the target-sensing radius.
The problem we consider in this paper is defined as follows.
Problem 2 (Target Assignment in Robotic Networks) Given X0, Y 0, rsense, and Communica-
tion Model 1 with rcomm or Communication Model 2 , find a control strategy u(t) = [u1(t),...,un(t)],
such that for some 0 ≤t f
i < ∞and some permutation σ of the numbers 1,...,n, xi(t f
i ) = y0
σ(i)
for all 1 ≤i ≤n.
Over all feasible solutions to an instance of Problem 2, we are interested in minimizing the
total distance traveled by all robots, which can be expressed as
Dn :=
n
∑
i=1
Z t f
i
0 ∥˙xi(t)∥2dt.
(5)
As an accurate proxy to the energy consumption of the entire system, the cost defined in (5)
is an appropriate objective in practice. Unless otherwise specified, distance optimality refers to
minimizing Dn. Over all permutations σ of the numbers 1,...,n, and for fixed X0 and Y 0, the
minimum total distance for robots moving along continuous paths is
D∗
n := min
σ
n
∑
i=1
∥x0
i −y0
σ(i)∥2,
(6)
which may or may not be achievable depending on the capabilities of the robots (e.g, if the
robots cannot follow straight-line paths, then Dn > D∗
n). Let U denote the set of all possible
control strategies that solve Problem 2 given a fixed set of capabilities for the robots, we say that
distance optimality is achieved if minU Dn = D∗
n. Besides distance optimality, we also briefly
discuss the total task completion time (i.e., the sum of the individual task completion times as
targets are occupied), denoted by Tn. If all robots start moving toward targets and do not stop
in the middle, then Tn = Dn. In particular, we define T ∗
n := D∗
n.
IV. GUARANTEEING DISTANCE OPTIMALITY FOR ARBITRARY rcomm AND rsense
In this section, we use Communication Model 1. In general, when rsense <
√
2 or rcomm <
√
2,
it is impossible to guarantee distance optimality, since global assignment is no longer possible
in general. For example, as rsense →0, the robots must search for the targets before assignments
can be made; it is very unlikely that the paths taken by the robots toward the targets will be
10
straight lines, which is required to obtain D∗
n. This raises the following question: Given a pair of
rcomm and rsense, under what conditions can we ensure distance optimality? Theorem 4 answers
this question.
Theorem 4 In a unit square, under sensing and communication constraints (i.e., rcomm,rsense <
√
2), distance optimality can be achieved with probability one if and only if at t = 0:
i) the communication graph is connected, and
ii) every target is within a distance of rsense to some robot.
PROOF. We first prove that the conditions are necessary with two claims: 1) an optimal assign-
ment that minimizes Dn is possible in general only if G(0) is connected, and 2) an optimal
assignment that minimizes Dn is possible only if for all y ∈Y 0, y is within a distance of rsense
to some x ∈X0.
To see that the first claim is true, we note that distance-optimal assignments forbid robots
from moving unnecessarily, requiring at t = 0 a pairing between elements of X0 and Y 0 that
minimizes Dn. We now show that this is not possible in general when rcomm <
√
2. For n = 2,
assume that the two targets are located at y1 and y2 as given in Fig. 2 (solid red dots). Assume
the first robot a1 is located at x1 (the blue solid dot at the lower left of Fig. 2) and a1 is of equal
rcomm
rcomm
x1
x2
y1
y2
x¶
2
Fig. 2.
A general setup in which the two robots cannot communicate with each other at t = 0 and therefore cannot always
decide an optimal assignment at t = 0.
distance to y1 and y2. Let the second robot a2 take two possible locations x2 and x′
2 as shown,
which are symmetric along a diagonal of Q. If a2 is at x2 (resp. x′
2), then a2 should go to y2
(resp. y1), forcing a1 to go to y1 (resp. y2). Not knowing a2’s location because a1 is out of a2’s
11
communication radius, a1 has at most 50% chance of picking the distance minimizing choice
at t = 0. We can readily extend the locations of the robots and targets to include neighborhoods
around them (the dotted circles in Fig. 2) to show that there is a non-zero probability that an
optimal assignment cannot be made at t = 0. This proves that that G(0) cannot have more than
one connected component and must be connected. The example can be extended to work for
arbitrary n by adding additional robots and targets to close vicinities of x1 and y1, respectively.
For the second claim, suppose that at t = 0, some y ∈Y 0 is not within a distance of rsense to
any x ∈X0. A robot must move to search for that y. This will cause the robot to follow a path
that is not a straight line with probability one, implying that Dn = D∗
n with probability zero.
It is not hard to see that the necessary conditions from the two claims are also sufficient:
when G(0) is connected and each target is observable by some robot ai, the robots can decide
at t = 0 a global assignment that minimizes Dn.
□
Theorem 4 suggests a simple way for ensuring distance optimality by either increasing the
number of robots or increasing one or both of rcomm and rsense. This essentially leads to a
centralized communication and control strategy (Strategy 1). Note that given the assignment
permutation σ, each robot ai can easily compute its straight-line path between x0
i and y0
σ(i).
Since every robot can carry out the computation in Strategy 1, to resolve conflicting decisions
and avoid unnecessary computation, we may let the highest labeled robot (e.g., an) handle the
entire assignment process.
Strategy 1: CENTRALIZED ASSIGNMENT
Initial condition: X0,Y 0
Outcome: permutation σ that assigns a robot ai to y0
σ(i)
1 compute di, j = ∥xi −yj∥2 between each pair of (xi,yj) in which xi ∈X0 and yj ∈Y 0
2 compute over {di, j} an assignment that minimizes Dn
3 communicate the assignment to all the robots
The rest of this section establishes how the conditions from Theorem 4 can be met. We
point out that similar conclusions can also be reached by exploring Theorem 3, which yields
an asymptotic relationship between the required number of robots for G(0) to be connected and
12
rcomm. We take a different approach and produce the required number of robots as an explicit
function of rcomm without the asymptotic assumption.
A. Guaranteeing a Connected G(0)
Since the robots can be anywhere in the unit square Q, given a communication radius of
rcomm <
√
2, intuitively, at least Θ(1/r2
comm) robots are needed for a connected G(0), which
requires the robots to take a lattice-like formation such as a grid. It turns out that when the
robots are uniformly randomly distributed, only a logarithmic factor more robots are needed to
ensure a connected G(0).
Lemma 5 Suppose that n robots are uniformly randomly distributed in the unit square. For fixed
rcomm <
√
2 and 0 < ε < 1, at t = 0, the communication graph is connected with probability at
least 1−ε if
n ≥⌈
√
5
rcomm
⌉2 log(1
ε ⌈
√
5
rcomm
⌉2).
(7)
PROOF. We divide the unit square Q into m = b2 equal-sized small squares with b = ⌈
√
5/rcomm⌉.
Label these small squares {q1,...,qm}. Under this division scheme, a robot residing in a small
square qi can communicate with any other robot in the four squares sharing a side with qi (see
Fig. 3). Therefore, G(0) is connected if each qi contains a robot. Let ni denote the number of
robots in qi. Then
P(ni = 0) = (1−1
m)n < e−n
m.
1
2
b
.
.
.
rcomm
Fig. 3.
If the small squares have a side length of ⌈
√
5/rcomm⌉or smaller, then a robot in such a square (e.g., the gray square)
can communicate with any robot in the four neighboring small squares sharing a side with the gray square.
13
The inequality holds because (1−x)n < e−nx for 0 < x < 1. To see this, let f(x) = log(1−x)/x.
The Taylor expansion of f(x) at x = 0 is −1 −x/2 −x2/3 + o(x3) < −1 for 0 < x < 1. This
shows that log(1 −x) < −x for 0 < x < 1 ⇒nlog(1 −x) < −nx ⇒(1 −x)n < e−nx. By Boole’s
inequality (i.e., the union bound), the probability that at least one of q1,...,qm is empty can be
upper bounded as
P(
m
[
i=1
E(ni = 0)) ≤
m
∑
i=1
P(ni = 0) < me−n
m.
Setting me−n/m = ε and replacing m = ⌈
√
5/rcomm⌉2 yields
⌈
√
5
rcomm
⌉2exp(−n
1
⌈
√
5
rcomm⌉2) = ε
⇒n = (⌈
√
5
rcomm
⌉2)log(1
ε ⌈
√
5
rcomm
⌉2),
which guarantees that each small square contains at least one robot with probability 1−ε.
□
The bound in Lemma 5 can be further tightened; Corollary 6 (below) illustrates one way to
achieve this. It produces n smaller than that given by (7) when rcomm <
√
5/2.
Corollary 6 Suppose that n robots are uniformly randomly distributed in the unit square. For
fixed rcomm <
√
2 and 0 < ε < 1, at t = 0, the communication graph is connected with probability
at least 1−ε if
n ≥⌈
√
5
rcomm
⌉2 log
h1
ε (1
2⌈
√
5
rcomm
⌉2 +⌈
√
5
rcomm
⌉)
i
.
(8)
Fig. 4.
As long as each of the shaded small squares contains an robot, G(0) must be connected. Therefore, only b2/2 + b
small squares need to have robots in them.
PROOF. If each of the shaded small squares in Fig. 4 has at least one robot, then G(0) must
be connected: any robot falling in a small white square must be connected to some robot in a
14
shaded small square. This shows that (8) is sufficient.
□
Remark. In comparison to Theorem 3, Lemma 5 provides n as an explicit function of rcomm.
Moreover, our sufficient condition on n given in (7) (and (8)), unlike (4), is not an asymptotic
bound. Therefore, our bound applies to an arbitrary rcomm. On the other hand, if we let rcomm →0,
then an asymptotic statement can also be made.
Lemma 7 Suppose that n robots, each with a communication radius of rcomm, are uniformly
randomly distributed in the unit square. At t = 0, the communication graph is asymptotically
connected with arbitrarily high probability e−e−c (for some c > 0) if
n ≥(2log⌈
√
5
rcomm
⌉+c)⌈
√
5
rcomm
⌉2.
(9)
PROOF. Given the division scheme used in the proof of Lemma 5, distributing robots into the unit
square Q is equivalent to tossing the robots (balls) into the m small squares (bins) uniformly ran-
domly. By Corollary 2, as m →∞, having n ≥mlogm+cm = (2log⌈
√
5/rcomm⌉+c)⌈
√
5/rcomm⌉2
robots guarantees that all m small squares must have at least one robot each with probability
e−e−c.
□
Since f(x) = cx grows slower than g(x) = xlogx as x →∞, Lemma 7 says that n = Θ((1/rcomm)2
log(1/rcomm)) robots can ensure that G(0) is connected with probability arbitrarily close to one
asymptotically. Next, we show that these many robots are also necessary for the high probability
guarantee.
Let Pn,m(E) denote the probability of an event E happening after tossing n balls into m bins.
We work with two events: E0, the event that “at least one bin is empty”, and E1, the event that
“at least one bin contains exactly one ball”. We want to show that Pn,m(E1) is not too small for
n up to mlogm, which is proven in the next two lemmas.
Lemma 8 Suppose that 1 ≤n ≤m balls are tossed uniformly randomly into m bins. Then
Pn,m(E1) ≥(1−1
m)m−1 > e−1.
PROOF. First we prove a useful inequality: for m ∈N,
(1−1
m)m−1 > e−1.
(10)
15
To see this, note that the function log(1−x)
1
x−1 has a Taylor expansion of −1+x/2+o(x2) > −1
for small x > 0, yielding that (1−x)
1
x−1 > e−1 for small x > 0. Since the derivative of (1−x)
1
x−1
is positive for x ∈(0,1), (10) holds for all m > 0 (we use the definition 00 = 1 here).
To prove Lemma 8, because all bins are initially empty, after tossing the first ball, some bin
contains exactly one ball. That is, P1,m(E1) = 1. Let the bin occupied by the first ball be bin 1.
As k−1 additional balls are tossed into the m bins, the probability that none of these k−1 balls
occupy bin 1 is (1−1/m)k−1. Therefore, for 1 ≤k ≤m, we have
Pk,m(E1) ≥P1,m(E1)(1−1
m)k−1
≥P1,m(E1)(1−1
m)m−1
= (1−1
m)m−1 > e−1.
□
Lemma 9 Suppose that m < n < mlogm balls are tossed uniformly randomly into m bins. As
m →∞,
Pn,m(E1) ≥(1−e−e)(1−1
m)m−1 > (1−e−e)e−1.
PROOF. Suppose that after an experiment of n′ tosses into m bins, E0 holds; i.e., at least one bin
is empty. Without loss of generality, we assume the empty bin is bin 1. Now consider tossing
an additional k balls into the m bins. The probability of exactly one of these k balls falling in
bin 1 is
Pk,m(exactly one ball falls in bin 1)
=
k
1
 1
m(1−1
m)k−1 = k
m(1−1
m)k−1.
Therefore,
Pn′+k,m(E1)
≥Pn′,m(E0)Pk,m(exactly one ball falls in bin 1)
= k
m(1−1
m)k−1Pn′,m(E0).
(11)
Letting c = −1 in Corollary 2, we have
lim
m→∞P(T1 ≥mlogm−m) = 1−e−e.
(12)
16
That is, as m →∞, for 0 < n′ < mlogm−m, Pn′,m(E0) ≥1−e−e. Plugging this into (11) and
letting k = m, we have that for m < n < mlogm, as m →∞,
Pn,m(E1) ≥(1−e−e)m
m(1−1
m)m−1 > (1−e−e)e−1,
in which the last inequality is by (10).
□
Under the assumptions of Lemmas 8 and 9, we always have that as m →∞,Pn,m(E1) >
min{e−1,(1 −e−e)e−1} > 0.34. We now show that n = Θ((1/rcomm)2log(1/rcomm)) is a tight
bound on the number of robots for guaranteeing the connectivity of G(0) with high probability.
Theorem 10 For n uniformly randomly distributed robots in a unit square with a communication
radius rcomm,
n = Θ(
1
r2comm
log
1
rcomm
)
(13)
is necessary and sufficient to ensure that at t = 0, the communication graph is asymptotically
connected with arbitrarily high probability.
PROOF. Lemma 7 covers sufficiency; we are to show that there is some non-trivial probability
that G(0) is disconnected if the number of robots satisfies
n = o(
1
r2comm
log
1
rcomm
).
To prove the claim, we partition the unit square Q into m = b2 equal-sized small squares in
which b = ⌊1.1/rcomm⌋. The factor of 1.1 in the expression makes the side of the small square
larger than rcomm. Assuming that m is divisible by 3 (it is always possible to truncate some small
squares to satisfy this), we may group the small squares into m/9 groups of 3×3 blocks (see,
e.g., Fig. 5).
If there is a single robot in a 3×3 block, the robot cannot communicate with the rest of the
robots if it falls inside the small square in the center of the block (e.g., the solid gray square in Fig.
5). By Lemmas 8 and 9, for less than (m/9)log(m/9) = 2⌊1.1/rcomm⌋2 log(⌊1.1/rcomm⌋/3)/9
robots, the probability of having at least one of these 3 × 3 blocks containing exactly one
robot is at least 0.34 as m →∞(i.e., rcomm →0). If a 3 × 3 block has exactly one robot in
it, with probability of 1/9, the robot is in the middle square. Therefore, with probability at least
0.34/9 ≈0.04, G(0) is disconnected.
□
17
rcomm
Fig. 5.
A 3×3 block as defined in the proof Theorem 10.
B. Ensuring Target Observability
With a connected communication graph G(0) guaranteed by Lemma 5, we can solve a single
assignment problem if for each y ∈Y 0, ∥y −x∥2 ≤rsense for some x ∈X0. Similar techniques
used in the proof of Lemma 5 lead to a similar lower bound on n.
Lemma 11 Suppose that n robots and n targets are uniformly randomly distributed in the unit
square. For fixed rsense and 0 < ε < 1, every target is observable by some robot at t = 0 with
probability at least 1−ε if
n ≥⌈
√
2
rsense
⌉2 log(1
ε ⌈
√
2
rsense
⌉2).
(14)
PROOF. If we partition the unit square Q into ⌈
√
2/rsense⌉2 equal-sized small squares and there
is at least one robot in each small square, then any point of Q is within rsense distance to some
robot. Following the same argument used in the proof of Lemma 5, the inequality from (14)
ensures that this happens with probability at least 1−ε.
□
Putting together Lemmas 5 and 11, we obtain a lower bound on n that makes a distance-optimal
assignment possible.
Theorem 12 Suppose that n robots and n targets are uniformly randomly distributed in the unit
square. Fixing 0 < ε < 1, at t = 0, the communication graph is connected and every target is
observable by some robot with probability at least 1−ε if
n ≥⌈
√
10
θ
⌉2 log(1
ε ⌈
√
10
θ
⌉2),
(15)
in which θ := min{
√
5rsense,
√
2rcomm}.
18
PROOF. When θ =
√
5rsense, (15) becomes (14), which implies (9). Therefore, G(0) is connected
with probability 1−ε.
When θ =
√
2rcomm, i.e., rsense ≥
√
10rcomm/5, by Lemma 5, (9) implies that G(0) is connected
with probability 1−ε. Moreover, there is at least one robot in each of the small squares with a side
length of at most rcomm/
√
5 (as specified in the proof of Lemma 5). Having rsense ≥
√
10rcomm/5
guarantees that robots in a small square observes all targes within the same small square.
Therefore, every y ∈Y 0 is within a distance of rsense to some x ∈X0.
□
Remark. Theorem 12 is not an asymptotic result and applies to all rcomm and rsense. If a high
probability asymptotic result is desirable, Lemma 11 can be readily turned into a version similar
to Theorem 10, by following the same proof techniques. In view of this fact, the bounds from
Theorem 12 are asymptotically tight.
V. HIERARCHICAL STRATEGIES FOR rsense ≥
√
2: OPTIMAL DISTANCE AND PERFORMANCE
GUARANTEES
In this section, we work with the (region-based) Communication Model 2 and assume that
rsense ≥
√
2 (that is, every robot is aware of the entire Y 0). The study of Communication Model 2,
besides leading to interesting conclusions on hierarchical strategies, also facilitates the analysis
in Section VI as we revisit Communication Model 1.
A region-based communication model naturally leads to a hierarchical strategy for solving
Problem 2 under the optimality criterion of minimizing the cost defined by (5). Let h ≥1 be the
number of hierarchies and mi,1 ≤i ≤h, be the number of equal-sized regions at hierarchy i. We
make the following assumptions that are mainly used in Theorem 16: i) m1 ≡1, ii) mi+1 ≥mi,
and iii) a region at a higher numbered hierarchy is contained in a single region at a lower
numbered hierarchy. For example, dividing Q into 4i−1 squares at hierarchy i satisfies these
requirements. We call the associated strategy under these assumptions the hierarchical divide-
and-conquer strategy, the details of which are described in Strategy 2. Note that for each region
in Strategy 2, the robots can again let the highest labeled robot within the region carry out the
strategy locally.
It is clear that Strategy 2 is correct by construction because |X0| = |Y 0|. The rest of this section
is devoted to analyzing the strategy. We begin with a single hierarchy (h = 1). Since rsense ≥
√
2
19
Strategy 2: HIERARCHICAL-DIVIDE-AND-CONQUER
Initial condition: X0,Y 0,h,m1,...,mh
Outcome: permutation σ that assigns a robot ai to y0
σ(i)
1 for each hierarchy i ∈{1,...,h} in decreasing order do
2
for each region j ∈{1,...,mi} do
3
let na and ng be the number of unmatched robots and targets in region j,
respectively
4
if na ≥ng > 0 then
5
pick the first ng robots from the na unmatched robots and run an assignment
algorithm to match them with the ng unmatched targets in region j
6
else if ng ≥na > 0 then
7
pick the first na targets from the ng unmatched targets and run an assignment
algorithm to match the na unmatched robots with these na targets in region j
8
else
9
continue
implies that all robots are aware of the entire set Y 0, the robots may form a consensus of which
robot should go to which target at t = 0 by finding an optimal assignment σ that yields D∗
n
as defined by (6). This assignment problem can be solved using a bipartite matching algorithm
such as the Hungarian method. Ajtai, Koml´os, and Tusn´ady proved the following about D∗
n.
Theorem 13 (Optimal Matching Ajtai et al. (1984)) Assuming that n points are i.i.d. follow-
ing the uniform distribution over a unit square, then, with probability 1−o(1),
C1
p
nlogn ≤D∗
n ≤C2
p
nlogn,
(16)
in which C1 and C2 are positive constants.
Remark. The second inequality in (16) remains true in expectation and also for arbitrary
probability measures on [0,1]2, albeit with a different universal constant than C2, by a result of
Talagrand Talagrand (1992). Therefore, D∗
n = Θ(√nlogn) in expectation. Although no formulas
for C1 and C2 from (16) were given in Ajtai et al. (1984), a simulation study suggests that
20
 0.3
 0.4
 0.5
 0.6
 0.7
 0
 200
 400
 600
 800
 1000
n  (number of agents)
Dn
*/(n log n)
1/2
Fig. 6.
The ratio of D∗n/√nlogn. Each data point is an average of 25 runs.
C1 <C2 < 1 and C2/C1 →1 as n →∞. As an example, for 200 ≤n ≤10000, 0.4√nlogn ≤D∗
n ≤
0.5√nlogn on average (see Fig. 6).
Next, we look at the general case with h > 1 hierarchies. To bound Dn, at each hierarchy i,
we need to know the number of robots that cannot be matched locally. We derive this number
in Lemma 14. Note that Lemma 14 does not depend on m and n being large.
Lemma 14 Suppose that n robots and n targets are uniformly randomly distributed in the unit
square Q, and Q is divided into m equal-sized regions. Within each of these m regions, the robots
are matched one-to-one with the targets until no more matchings can be made. The total number
of robots that are left unmatched is no more than
p
n(m−1)/2 in expectation.
PROOF. Restricting to one of the m equal-sized regions, say qi, we know for x0
j ∈X0 and y0
j ∈Y 0,
P(x0
j ∈qi) = P(y0
j ∈qi) = 1
m,
and
P(x0
j ∈qi,y0
j /∈qi) = P(x0
j /∈qi,y0
j ∈qi) = m−1
m2 ,
in which the event (x0
j ∈qi,y0
j /∈qi) represents a surplus of one robot in qi and the event (x0
j /∈
qi,y0
j ∈qi) a deficit in qi. Thus, we may view the experiment of picking x0
j and y0
j as a one
step walk on the real line starting at the origin, with (m−1)/m2 probability of moving ±1. The
entire process of picking X0 and Y 0 can then be treated as a random walk of n such steps.
Under this random walk analogy, we may use a random variable Zj ∈{0,±1} to represent
the outcome of picking (x0
j,y0
j). We immediately have that E[Z2
j ] = 2(m −1)/m2. Letting Sn =
21
Z1 +...+Zn, we can compute the variance of Sn as
E[S2
n] = E[(Z1 +...+Zn)2] = E[Z2
1 +...+Z2
n]
= nE[Z2
j] = 2n(m−1)
m2
.
Applying Jensen’s inequality to the concave function √x with x = |Sn|2 = S2
n, we have
E[|Sn|] = E[
q
S2n] ≤
q
E[S2n]
⇒E[|Sn|] ≤
r
2n(m−1)
m2
.
Because, in expectation, an equal number of the m regions have surpluses (more robots than
targets) and deficits (fewer robots than targets), and some of the m regions may have neither, no
more than half of the m regions should have a surplus of robots on average. The total number
of unmatched robots in expectation is then no more than (m/2)∗E[|Sn|] ≤
p
n(m−1)/2.
□
The distance traveled by the matched robots at the bottom hierarchy with m regions can be
bounded easily. For simplicity, we now assume that these regions are equal-sized squares.
Lemma 15 Suppose that n robots and n targets are uniformly randomly distributed in the unit
square Q, and Q is divided into m equal-sized small squares. Within each of these m small
squares, the robots are matched one-to-one with the targets until no more matchings can be
made. The minimum total distance of matchings made between the robots and the targets within
the small squares is no more than C√nlogn in expectation, for some positive constant C.
PROOF. Since Q is divided into m squares, these squares all have a side length of 1/√m. Let one
such square be qi with ni robots (note that ∑m
i=1ni = n). Since a uniform distribution restricted
to qi is again uniform, we can apply Theorem 13 to qi. If we let these ni robots match only
with targets inside qi, then the total distance incurred locally will not exceed C
p
ni logni/m in
expectation. Here C is some positive constant.
Note that it is not necessarily the case that all ni robots will be matched locally in qi. This does
not affect the current proof. For some 1 ≤i ≤m, it may be the case that no local matchings can
be made because either ni = 0 or there is no target in qi. Let m′ ≤m denote the number of these
m squares in which local matchings can be made. The total distance incurred by local matchings
22
is then upper bounded by (note that ni is now indexed with respect to these m′ squares)
m′
∑
i=1
C
r
ni logni
m
= C m′
√m
m′
∑
i=1
1
m′
p
ni logni.
Here we assume that m′ > 0, otherwise the local matchings would have a distance cost
of zero. Since the function ϕ(x) = √xlogx is concave, by Jensen’s inequality, E[√xlogx]
≤
p
E[x]log(E[x]). Letting x = ni and the expectation be carried out over the discrete uniform
distribution with 1/m′ probability each, we have
C m′
√m
m′
∑
i=1
1
m′
p
ni logni ≤C m′
√m
v
u
u
t(
m′
∑
i=1
ni
m′)log(
m′
∑
i=1
ni
m′)
= C
r
m′
m
v
u
u
t(
m′
∑
i=1
ni)(log(
m′
∑
i=1
ni)−log(m′))
≤C
p
nlogn.
□
Remark. With minor modifications, Lemma 15 can be applied to regions with shapes other
than squares. Defining the diameter of a two-dimensional region as the diameter of the region’s
smallest enclosing circle, the main requirement for the modification to work is that the maximum
diameter of these regions is O(1/√m).
We now give an upper bound on Dn, in expectation, for general hierarchical strategies.
Theorem 16 Suppose that n robots and n targets are uniformly randomly distributed in the unit
square Q, and Q is divided into mi equal-sized small squares at hierarchy i with a total of h ≥2
hierarchies. For all applicable i ≥1, assume that mi+1 ≥mi and any small square at hierarchy
i+1 falls within a single square at hierarchy i. Then Strategy 2 yields
E[Dn] ≤C
p
nlogn+
h−1
∑
i=1
rnmi+1
mi
.
(17)
PROOF. The C√nlogn term on the RHS of (17) is due to Lemma 15. Then at each hierarchy i
with 1 ≤i < h, each of the mi squares contains mi+1/mi smaller squares from hierarchy i +1.
Here we use the assumption that a region at a higher numbered hierarchy falls completely
within a single region at a lower numbered hierarchy. This means that a robot that gets matched
at hierarchy i needs to travel at most a distance of
p
2/mi. Since there are no more than
23
p
n(mi+1 −1)/2 <
p
mi+1n/2 unmatched robots at hierarchy i in expectation by Lemma 14, the
distance incurred at hierarchy i is no more than
p
nmi+1/mi for 1 ≤i < h. Summing up all the
distances then gives us the inequality (17).
□
Theorem 16 allows us to upper bound the performances of different hierarchical strategies
depending on the choices of h and {mi}. We observe that for fixed h and {mi} independent of n,
the first term C√nlogn dominates the other terms in (17) as n →∞. This implies that Strategy
2 yields assignments whose total distance is at most a constant multiple of the optimal distance.
This observation is summarized in Corollary 17. Recall that D∗
n is the minimum possible distance
defined by (6).
Corollary 17 For fixed h and m1,...,mh that do not depend on n, as n →∞, Strategy 2 yields
target assignments with Dn/D∗
n = O(1) in expectation.
For example, with h ≥2 and mi = 4i−1 at hierarchy i, we have
E[Dn] ≤C
p
nlogn+
h−1
∑
i=1
√
4n
= C
p
nlogn+2(h−1)√n.
(18)
For any fixed h, as n →∞, Dn/D∗
n ≤C/C1 +o(1) = O(1). A constant approximation ratio can
also be achieved when h and {mi} depend on n. For example, letting h = 3, m2 = logn, and
m3 = log2 n, we have
E[Dn] ≤C
p
nlogn+
2
∑
i=1
p
nlogn = (C +2)
p
nlogn.
(19)
Since hierarchical strategies need not run centralized assignment algorithms for all robots, the
computational part of these strategies can be significantly faster. We will come back to this point
in the next section.
Remark. Before concluding this section, it is worth mentioning that the results of this section
continue to hold in only slightly weaker forms when the point sets X0,Y 0 are drawn i.i.d. from
the same arbitrary distribution over [0,1]2 (based on Talagrand Talagrand (1992)). Since the
topic of arbitrary probability measures diverges from the main focus of this paper, we only
briefly discuss extending the results of this section to deal with arbitrary probability measures
on [0,1]2.
24
To adapt Lemma 14 for arbitrary probability measures, assume that each region qi (see the
proof of Lemma 14) has an overall probability of pi of receiving a robot or target. Note that
∑m
i=1 pi = 1. This changes the upper bound of E[|Sn|] for the region qi to
p
2npi(1−pi). Then,
over all m regions, the total number of unmatched robots is bounded by
m
∑
i=1
p
2npi(1−pi) = m
√
2n
m
∑
i=1
1
m
p
pi(1−pi)
≤m
√
2n
s
m
∑
i=1
pi
m (1−
m
∑
i=1
pi
m )
= m
√
2n
r
1
m(1−1
m)
=
p
2n(m−1),
in which the inequality is obtained by applying Jensen’s inequality to the concave function
p
x(1−x).
Besides updating the uniform distribution of X0 and Y 0 to an arbitrary probability measure,
the statement and proof of Lemma 15 remain largely unchanged. This is because the second
inequality in (16) does not change asymptotically as the underlying robot and target distribution
changes. Then, the inequality (17) from Theorem 16 merely adds a multiplicative constant of 2 to
its second term on the RHS. Because the first inequality in (16) is not known to hold for arbitrary
probability measures, we do not have a parallel of Corollary 17 for arbitrary probability measures.
Nevertheless, these bounds for arbitrary probability measures suggest that the uniform distribution
is among the worst distributions for Problem 2 under the optimality constraint of minimizing (5).
This is because the uniform distribution leads to an optimal assignment distance of Ω(√nlogn),
and an arbitrary distribution leads to an optimal assignment distance of O(√nlogn). Note that
these updates also apply to the results in the next section with appropriate modifications.
VI. NEAR OPTIMAL STRATEGIES
After exploring hierarchical strategies for the region-based Communication Model 2, we now
return to the range-based Communication Model 1. If rcomm is arbitrary and the conditions
specified in Theorem 4 are not known to hold, the best we can do is obtain near distance-
optimal strategies. In this section, we show that constant ratio approximation of distant optimality
is possible for arbitrary rsense and rcomm. The basic idea behind our strategies is to move the
robots to pass around information about the locations of other robots. The assumption rsense ≥
√
2
25
is made temporarily. At the end of this section, we show how to remove this assumption without
affecting asymptotic optimality.
A. Near Distance-Optimal Rendezvous Strategy
Our first suboptimal strategy uses moving robots for information aggregation until some robot
is aware of the locations of all robots (i.e., the set X0), at which point a centralized optimal
assignment can be made. Although some robots will move and change their locations during
this process, the moved robots nevertheless are aware of their initial locations in X0. To carry
out the strategy, the unit square Q is divided into m = b2 disjoint, equal-sized small squares,
with b = ⌈
√
2/rcomm⌉. These small squares are labeled as qi, j’s, in which i and j are the row
number and column number of the square, respectively (see Fig. 7).
q2,5
Fig. 7.
Directions for robots to move in the rendezvous strategy.
Based on its initial location, each robot can identify the small square qi, j it lies in. At t = 0,
the robots in the squares on row 1 and row b start moving in the direction as indicated in Fig. 7.
We want to use these robot to pass the information of where all robots are. At most one robot
per square is required to move since all robots in a small square can communicate with each
other by the assumption b = ⌈
√
2/rcomm⌉.
Assuming that a robot in a square qi, j is moving downwards, it keeps moving until it is within
the communication radius of a robot in a square with label qi+k, j,k ≥1, at which point it passes
over the information it has and stops. The robot in qi+k, j then does the same. The procedure
continues until a robot reaches the middle of Q (row ⌈b/2⌉). Then, the robots in the squares
on row ⌈b/2⌉repeat the same process horizontally until a robot in the center of Q knows the
locations of all other robots. At this point, the robot in the center of Q that knows the location
26
of all other robots makes a global assignment so that each robot is matched with a target. The
moved robots then reverse their travel directions to deliver the assignment information to all
robots. The outline of the strategy is given in Strategy 3.
Strategy 3: RENDEZVOUS
Initial condition: X0,Y 0,rcomm
Outcome: produces a permutation σ that assigns robots to targets and communicates σ to
all the robots
1 each robot computes its square qi, j based on rcomm. Let the highest labeled robot within
each qi, j be ai, j, which represents qi, j
2 for each qi, j, 1 ≤i, j ≤b = ⌈
√
2/rcomm⌉do
3
if i ̸= ⌈b/2⌉then
4
waitTime ←|⌈b/2⌉−i|/b
5
else
6
waitTime ←1/2+|⌈b/2⌉−j|/b
7
ai, j waits for up to waitTime units of time for information from a robot coming from
the previous square. After the information is received or after waitTime passes, ai, j
starts moving to the next squares and delivers its information once it can communicate
with another robot in these squares. It then stops
8 robot a⌈b/2⌉,⌈b/2⌉computes σ; the earlier communication process is then reversed to
deliver σ to all the robots.
The correctness of Strategy 3 as an algorithm is proven by construction. Besides the distance
cost from the assignment, the robots in each column travel at most a total distance of two. The
middle row incurs an extra distance of at most two. Thus, in expectation, Dn < D∗
n+2b+2. Since
D∗
n = Θ(√nlogn), D∗
n dominates 2b + 2 when b = o(√nlogn). In particular, n = Θ(1/r2
comm)
satisfies this requirement. Therefore, Strategy 3 can yield near distance-optimal solution without
requiring an n as large as (13) with respect to 1/rcomm.
A drawback of Strategy 3 is that no robot can move to the targets until the assignment phase
is complete. This yields a total task completion time of Tn ≈2n +T ∗
n in expectation, which is
undesirable since T ∗
n = O(√nlogn) asymptotically. Furthermore, Strategy 3 requires running a
27
centralized assignment algorithm for all robots. This might be impractical for large n. We address
these issues with decentralized hierarchical strategies.
B. Decentralized Hierarchical Strategies
We first look at a decentralized hierarchical strategy that combines Strategies 2 and 3. Instead
of waiting for a centralized assignment to be made, in each of the small square qi, j as specified
in Strategy 3, we let the robots in qi, j be assigned to targets that belong to the same square (we
refer to these as local assignments). The robots that are not matched to targets then carry out
Strategy 3. We denote this hierarchical rendezvous strategy as Strategy 4 and omit the pseudo
code.
Corollary 18 For Strategy 4 (2-level Hierarchical Rendezvous), as n →∞,
E[Dn] ≤C
p
nlogn+√mn+2√m+2,
(20)
and
E[Tn] = Θ(
p
nlogn+√mn).
(21)
PROOF. The bound on E[Dn], given by (20), is straightforward to compute using Theorem 16,
in which the first two terms on the right side of (20) correspond to the first and second terms of
the right side of (17), respectively, and the last two terms are due to communication overhead.
For total completion time, all but Θ(√mn) robots can start moving to their targets at t = 0. For
the Θ(√mn) robots, they need to wait no more than two units of time each before moving to
their targets. This gives us (21).
□
Remark. Similar to Strategy 3, for any fixed m, in expectation, Dn/D∗
n = O(1) as n →∞.
Moreover, in contrast to Strategy 3, for any fixed m, Tn/T ∗
n = O(1) in expectation. Suppose that a
centralized algorithm requires t(n) running time. Using the same centralized algorithm, Strategy
4 has a running time of O(mt(n/m) + t(√mn)). If t(n) = O(n3) as given by the Hungarian
method, then Strategy 4 has a running time of O(n3/m2 +(mn)3/2). Taking n = 10000,m = 10,
for example, we get a 1000-time speedup.
By introducing additional hierarchies, Strategy 4 can be easily extended to a multi-hierarchy
decentralized strategy. Depending on how the subdivisions are made, many such strategies are
28
possible. For example, using h ≥2 hierarchies with each hierarchy i having 4i−1 small squares,
we get a “quad-merging” strategy as illustrated in Fig. 8, in which up to four representatives in
four adjacent squares meet to decide a local assignment of the robots in these squares at a given
hierarchy level.
Fig. 8.
Illustration of robot movements in a potential hierarchical strategy.
Although these suboptimal strategies vary in detail, they can be easily analyzed with Theorem
16. For example, we look at an extension to Strategy 4 with three hierarchies; let us call this
strategy Strategy 5. After partitioning the bottom (or third) hierarchy to m squares, the middle
(or second) hierarchy is partitioned into k = √m small squares. At either the third or the second
hierarchy, local assignments are made, followed by applying the rendezvous strategy as given
in Strategy 3. It is again straightforward to derive the following.
Corollary 19 For Strategy 5 (3-level Hierarchical Rendezvous), as n →∞,
E[Dn] ≤C
p
nlogn+2
q
n√m+4√m+2.
(22)
Remark. Again, Dn/D∗
n = O(1) as n →∞for a fixed m. Introducing more hierarchy levels
extends the total completion time Tn, which is increased by approximately 2√m. Thus, the total
completion time of Strategy 5 is also given by (21). Following similar analysis, the overall
running time required by Strategy 5 is O(mt(n/m)+√mt(√n)+t(
p
n√m)) given a centralized
assignment algorithm that runs in t(n) time.
C. Handling Arbitrary rsense
Because there can be targets anywhere in Q, to carry out the algorithms stated in this section,
each robot must be aware of all target locations. For this to happen for arbitrary rsense, Q must be
29
swept through in a worst scenario. To do this, we partition Q into ⌈1/(2rsense)⌉2 small squares
and let a robot in the top-left small square “zig-zag” through Q (i.e., following a Boustrophedon
path Choset (2000)) until it covers the bottom side of Q. If there is no robot in the top-left small
square, then a robot in a square along the Boustrophedon path is used; implicit timing can be
used to determine this. Once the end of the path is reached, the robot then reverses its course
until it gets back to the top-left small square. At this point, this robot is aware of all target
locations. It can then repeat a similar path to communicate that information to all other robots.
This procedure ensures that all robots are aware of all target locations. The total distance cost
of the procedure is about 2⌈1/(2rsense)⌉+ ⌈1/(2rcomm)⌉. Taking this penalty, which does not
depend on n and therefore has no impact on the asymptotic optimality, we can then effectively
assume rsense ≥
√
2.
VII. SIMULATION STUDIES
A. Number of Required Robots for a Connected G(0)
 0
 20
 40
 60
 80
 
100
 1
 2
 3
 4
 5
 6
= 0.2
rcomm    0.1
   0.05
   0.02
   0.01
% of connected G(0)
  n/({ log       /       )
2
rcomm rcomm
Fig. 9.
Effects of n on the connectivity of G(0) for different values of rcomm.
In this subsection, we show a result of simulation to verify our theoretical findings in Section
IV. Since the bounds over rcomm and rsense are similar, we focus on rcomm and verify the
requirement for the connectivity of G(0) for several rcomm’s ranging from 0.01 to 0.2. For
each fixed rcomm, various numbers of robots are used starting from n = −logrcomm/r2
comm (the
number of robots goes as high as 3 × 105 for the case of rcomm = 0.01). 1000 trials were run
for each fixed combination of rcomm and n. The percentage of the runs with a connected G(0)
is reported in Fig. 9. The simulation suggests that the bounds on n from Theorem 10 are fairly
tight.
30
TABLE I
COMPARISON BETWEEN (4) AND (7)
prob.
rcomm
0.2
0.1
0.05
0.02
0.01
0.1
0.001, 0.82
0.001, 0.96
0.001, 0.99
0.001, 1
0.003, 1
0.5
0.007, 0.92
0.006, 0.98
0.027, 0.99
0.064, 1
0.081, 1
0.9
0.2, 0.99
0.31, 1
0.381, 1
0.477, 1
0.502, 1
0.99
0.702, 1
0.742, 1
0.794, 1
0.834, 1
0.855, 1
To compare to (4), which also allows for estimation of n in terms of rcomm with a specified
probability for obtaining a connected G(0), we computed n based on (4) and (7) for a range
of rcomm-probability pairs. We then use these n’s to estimate the actual probability of having a
connected G(0). We list the result in Table I. Each main entry of the table has two probability
numbers separated by a comma, obtained using (4) and (7), respectively. As we can see, (4)
gives underestimates (due to its asymptotic nature) and cannot be used to provide probabilistic
guarantees. On the other hand, (7) provides overestimates that guarantee the desired probability.
B. Performance of Near Optimal Strategies
Next, we simulate Strategies 2-5 and evaluate Dn, Tn, and running time for these strategies
over various values of n and rcomm, assuming rsense ≥
√
2. Due to our choice of k = √m in
Strategy 5, we pick specific rcomm’s so that m = ⌈
√
2/rcomm⌉is always a perfect square. These
values are rcomm = 0.16,0.09,0.057, and 0.04, which correspond to m = 81,256,625, and 1296,
respectively. The number of robots used in each simulation ranges from 100 to 10000. For each
n, 10 assignment problem instances are randomly generated. These problem instances are then
used to test all strategies. We test Strategy 2 using the same (two-hierarchy and three-hierarchy)
partitions that are used with Strategies 4 and 5.
Distance optimality: The ratios Dn/D∗
n for Strategy 3 over different n and rcomm are plotted in
Fig. 10. We observe that the overhead for establishing global communication among the robots
becomes insignificant as n increases, driving Dn/D∗
n to close to one.
For Strategy 4, the ratios were plotted similarly in Fig. 11 but with (small) error bars. The error
bars display the standard deviation over the 10 runs (we omitted these from a figure, such as Fig.
31
 2
 4
 6
 8
 10
 12
 100
 1000
 10000
/
Dn
*
Dn
n - number of agents 
= 0.16
= 0.09
= 0.057
= 0.04
rcomm
Fig. 10.
Distance optimality of Strategy 3 over varying n and rcomm.
 2
 4
 6
 8
 10
 12
 100
 1000
 10000
/
Dn
*
Dn
n - number of agents 
= 0.16
= 0.09
= 0.057
= 0.04
rcomm
Fig. 11.
Distance optimality of Strategy 4 over varying n and rcomm.
 1
 1.5
 2
 2.5
 3
 100
 1000
 10000
/
Dn
*
Dn
n - number of agents 
Fig. 12.
The effect of varying n on the distance optimality of Strategy 4 with rcomm = 0.16 (m = 81).
32
10, when they are too small to see). They can be better seen in Fig. 12, which is a zoomed-in
version of the rcomm = 0.16 line from Fig. 11. The similarities between Fig. 10 and Fig. 11 for
small n are not surprising since both strategies spend most of their effort (distance traveled) in
establishing communication. As this extra communication cost diminishes as n grows, the actual
assignment cost dominates. Strategy 3, with assignment being done in a centralized manner,
becomes better than the decentralized Strategy 4.
 5
 10
 15
 20
 25
 100
 1000
 10000
/
Dn
*
Dn
n - number of agents 
= 0.16
= 0.09
= 0.057
= 0.04
rcomm
Fig. 13.
Distance optimality of Strategy 5 over varying n and rcomm.
As expected, for a fixed rcomm, Dn/D∗
n decreases as n increases. For n = 10000, the ap-
proximation ratios for our choices of rcomm are around 1.4 (due to the slow growing nature of
D∗
n ∼√nlogn; fixing any rcomm, this ratio should be close to one for large n). On the other hand,
for a fixed n, as the partition of the unit square Q gets finer, Dn/D∗
n increases, implying that
decreasing the communication radius has a negative effect on distance optimality. We observe
similar results on the distance optimality of Strategy 5 (see Fig. 13).
If we remove the rendezvous part from Strategies 4 and 5, they become similar to Strategy 2.
The distance optimality performance of these two particular versions of Strategy 2 is shown in
Fig. 14 and Fig. 15, respectively. For all partitions made (m = 81,256,625,1296), Dn/D∗
n ratios
of less than two are achieved and can go as low as 1.06, showing that hierarchical strategies can
provide very good optimality guarantees.
Computational performance: We list the running time, in seconds, for Strategies 3-5 in Table
II. The standard O(n3) Hungarian method is used as the baseline assignment algorithm. Each
main entry of the table lists three numbers corresponding to the running time of Strategies 3, 4,
and 5, respectively, for the given combination of rcomm and n. Note that any version of Strategy 2
33
 1
 1.2
 1.4
 1.6
 1.8
 2
 100
 1000
 10000
 /
Dn
*
 Dn
n - number of agents 
= 81
= 256
= 625
= 1296
m
Fig. 14.
The assignment cost of a two-level “pure” hierarchical strategy.
 1
 1.2
 1.4
 1.6
 1.8
 2
 100
 1000
 10000
 /
Dn
*
 Dn
n - number of agents 
= 81
= 256
= 625
= 1296
m
Fig. 15.
The assignment cost of a three-level “pure” hierarchical strategy.
has the same amount of computation as a corresponding rendezvous-based strategy. As expected,
a hierarchical assignment greatly reduces the computation time, often by a factor over 103. The
computation was performed on a Intel Core-i7 3970K PC under a 8GB Java virtual machine.
Time optimality: Since Strategies 3-5 sacrifice distance (and therefore, time) to compensate
for limited communication, we do not expect the total completion time Tn of these strategies to
match T ∗
n closely. For example, in (21), although Tn →T ∗
n as n →∞for fixed m = ⌈
√
2/rcomm⌉2, it
requires a very large n for √logn to dominate √m. Thus, we only compare Tn among Strategies
3-5. Using Tn(i) to denote the Tn for Strategy i, Tn(4)/Tn(3) and Tn(5)/Tn(3) are plotted in
Figures 16-17. As n increases, Strategies 4 and 5 both take much less total completion time on
average.
34
TABLE II
RUNNING TIME FOR STRATEGIES 3-5
# of robots, n
rcomm(m)
0.16 (81)
0.09 (256)
0.057 (625)
0.04 (1296)
100
0.007
0.001
0.001
0.007
0.002
0.0001
0.007
0.002
0.0004
0.007
0.003
0.0004
200
0.02
0.001
0.0001
0.02
0.005
0.0003
0.02
0.01
0.0004
0.02
0.02
0.0006
500
0.34
0.005
0.0006
0.34
0.02
0.001
0.34
0.07
0.002
0.34
0.14
0.003
1000
2.76
0.015
0.002
2.76
0.07
0.003
2.76
0.22
0.003
2.76
0.54
0.006
2000
22.3
0.05
0.009
22.3
0.20
0.006
22.3
0.70
0.011
22.3
1.90
0.015
5000
345
0.02
0.069
345
0.78
0.032
345
2.84
0.043
345
8.28
0.058
10000
2756
0.83
0.43
2756
2.32
0.11
2756
8.35
0.11
2756
24.4
0.14
 0
 0.2
 0.4
 0.6
 0.8
 1
 1.2
 100
 1000
 10000
n - number of agents 
(4)/
Tn
(3)
Tn
= 0.16
= 0.09
= 0.057
= 0.04
rcomm
Fig. 16.
Ratio of total completion time between Strategies 3 and 4.
35
 0
 0.5
 1
 1.5
 2
 100
 1000
 10000
n - number of agents 
(5)/
Tn
(3)
Tn
= 0.16
= 0.09
= 0.057
= 0.04
rcomm
Fig. 17.
Ratio of total completion time between Strategies 3 and 5.
VIII. CONCLUSION AND DISCUSSIONS
Focusing on the distance optimality for the target assignment problem in a robotic network
setting, we have characterized a necessary and sufficient condition under which optimality can
be achieved. We also provided a direct formula for computing the number of robots sufficient
for probabilistically guaranteeing such an optimal solution. Then, we took a different angle;
we looked at suboptimal strategies and their asymptotic performance as the number of robots
goes to infinity. We showed that these strategies yield a constant approximation ratio when
compared with the true distance optimal solution. Many of these decentralized strategies also
provide computational advantages over a centralized one.
We conclude the paper by discussing our choice on certain elements that can be generalized
in a future work.
Equal number of initial and target locations: In the problem statement we assume that |X0| =
|Y 0|. If |X0| > |Y 0|, some robots do not need to move and if |X0| < |Y 0|, some robots may need
to reach multiple targets, assuming that the main goal is to serve the targets. Our result readily
generalizes to the case in which |X0|/|Y 0| is close to 1. When |X0| ≫|Y 0|, it is likely that for a
yi ∈Y 0, there is a unique xi ∈X0 that is closest to yi Smith and Bullo (2009). Moreover, for two
different yi,yj, xi ̸= xj. The spatial assignment problem then degenerates to finding the nearest
robot for each y ∈Y 0. When |X0| ≪|Y 0|, the problem becomes a multiple salesmen version of
the traveling salesman problem (we have a standard traveling salesman problem when |X0| = 1),
which is an NP-hard problem. It remains an interesting open question to investigate the middle
36
ground, i.e., |X0| = C|Y 0| for some constant C (for example C ∈[0.1,10]).
Distribution of initial and target locations: Although it is beyond the scope of this paper, it
would be interesting to establish a lower bound on the optimal assignment distance for arbitrary
probability measures. Also, it would be interesting to investigate the case in which the robots
and the targets assume different distributions. Another important aspect not covered in this paper
is the issue of targets distributed somewhat randomly over time.
Minimizing over other powers of the 2-norm: On the side of optimality measures, we note
that Theorem 13 generalizes to arbitrary powers of the Euclidean 2-norm Ajtai et al. (1984).
That is, for
D∗
n,p := min
σ
n
∑
i=1
∥x0
i −y0
σ(i)∥p
2,
(23)
it holds true that
D∗
n,p ∼n(logn/n)p/2.
(24)
Theorem 13 corresponds to the special case of p = 1. As p →∞, (23) minimizes the longest
distance traveled by any robot. This is true because for fixed X0, Y 0, and a sufficiently large p,
the largest ∥x0
i −y0
σ(i)∥p
2 becomes the dominating term in the sum ∑n
i=1∥x0
i −y0
σ(i)∥p
2. Although
we restrict our attention to p = 1 in this paper, our results readily extend to other values of p
(i.e., other optimality criteria) with (24). Note that this means the Dn definition given by (5)
needs to be updated accordingly to an appropriately defined Dn,p.
ACKNOWLEDGEMENTS
We thank anonymous reviewers, S. Har-Peled, and A. Nayyeri for their constructive comments.
REFERENCES
S. L. Smith and F. Bullo, “Monotonic target assignment for robotic networks,” IEEE Transactions on Automatic Control, vol. 54,
no. 9, pp. 2042–2057, Sep. 2009.
J. Yu and S. M. LaValle, “Distance optimal formation control on graphs with a tight convergence time guarantee,” in Proceedings
IEEE Conference on Decision & Control, 2012, pp. 4023–4028.
D. P. Bertsekas, “The auction algorithm: A distributed relaxation method for the assignment problem,” Annals of Operations
Research, vol. 14, pp. 105–123, 1988.
D. P. Bertsekas and D. A. CastaŻnon, “Parallel synchronous and asynchronous implementations of the auction algorithm,” Parallel
Computing, vol. 17, pp. 707–732, 1991.
R. Burkard, M. Dell’Amico, and S. Martello, Assignment Problems.
Philadelphia: Siam Society for Industrial and Applied
Mathematics, 2012.
37
J. Edmonds and R. M. Karp, “Theoretical improvements in algorithmic efficiency for network flow problems,” Journal of the
ACM, vol. 19, no. 2, pp. 248–264, 1972.
H. W. Kuhn, “The Hungarian method for the assignment problem,” Naval Research Logistics Quarterly, vol. 2, pp. 83–97, 1955.
M. M. Zavlanos, L. Spesivtsev, and G. J. Pappas, “A distributed auction algorithm for the assignment problem,” in Proceedings
IEEE Conference on Decision & Control, 2008, pp. 1212–1217.
M. Ji, S. Azuma, and M. Egerstedt, “Role-assignment in multi-agent coordination,” International Journal of Assitive Robotics
and Mechatronics, vol. 7, no. 1, pp. 32–40, Aug. 2006.
H. G. Tanner, A. Jadbabaie, and G. J. Pappas, “Flocking in fixed and switching networks,” IEEE Transactions on Automatic
Control, vol. 52, no. 5, pp. 863–868, 2007.
K. Treleaven, M. Pavone, and E. Frazzoli, “Asymptotically optimal algorithms for one-to-one pickup and delivery problems with
applications to transportation systems,” IEEE Transactions on Automatic Control, vol. 59, no. 9, pp. 2261–2276, 2013.
M. M. Zavlanos and G. J. Pappas, “Dynamic assignment in distributed motion planning with local coordination,” IEEE
Transactions on Robotics, vol. 24, no. 1, pp. 232–242, 2008.
S.-J. Chung, S. Bandyopadhyay, I. Chang, and F. Y. Hadaegh, “Phase synchronization control of complex networks of Lagrangian
systems on adaptive digraphs,” Automatica, vol. 49, no. 5, pp. 1148–1161, 2013.
S. Kloder and S. Hutchinson, “Path planning for permutation-invariant multirobot formations,” IEEE Transactions on Robotics,
vol. 22, no. 4, pp. 650–665, 2006.
V. Sharma, M. A. Savchenko, E. Frazzoli, and P. G. Voulgaris, “Transfer time complexity of conflict-free vehicle routing with
no communications,” International Journal of Robotics Research, vol. 26, no. 3, pp. 255–271, 2007.
M. Turpin, K. Mohta, N. Michael, and V. Kumar, “Goal assignment and trajectory planning for large teams of aerial robots,” in
Proc. Robotics: Science and Systems, 2013.
J. Cort´es, S. Mart´ınez, and F. Bullo, “Robust rendezvous for mobile autonomous agents via proximity graphs in arbitrary
dimensions,” IEEE Transactions on Automatic Control, vol. 51, no. 8, pp. 1289–1298, Aug. 2006.
A. Jadbabaie, J. Lin, and A. S. Morse, “Coordination of groups of mobile autonomous agents using nearest neighbor rules,”
IEEE Transactions on Automatic Control, vol. 48, no. 6, pp. 988–1001, 2003.
J. Lin, A. S. Morse, and B. D. O. Anderson, “The multi-agent rendezvous problem. part 1: The synchronous case,” SIAM Journal
on Control and Optimization, vol. 46, no. 6, pp. 2096–2119, Nov. 2007.
——, “The multi-agent rendezvous problem. part 2: The asynchronous case,” SIAM Journal on Control and Optimization, vol. 46,
no. 6, pp. 2120–2147, Nov. 2007.
F. Bullo, J. Cort´es, and S. Mart´ınez, Distributed Control of Robotic Networks, ser. Applied Mathematics Series.
Princeton
University Press, 2009, electronically available at http://coordinationbook.info.
F. Xue and P. R. Kumar, “The number of neighbors needed for connectivity of wireless networks,” Wireless Networks, vol. 10,
no. 2, pp. 169–181, Mar. 2004.
P. Balister, B. Bollob´as, A. Sarkar, and M. Walters, “Connectivity of random k-nearest-neighbour graphs,” Advances in Applied
Probability, vol. 37, pp. 1–24, 2005.
N. M. Freris, H. Kowshik, and P. R. Kumar, “Fundamentals of large sensor networks: Connectivity, capacity, clocks and
computation,” Proceedings of the IEEE, vol. 98, no. 11, pp. 1828–1846, Nov. 2010.
A. Ganesh and F. Xue, “On the connectivity and diameter of small-world networks,” Advances in Applied Probability, vol. 39,
pp. 853–863, 2007.
G. Mao and B. D. O. Anderson, “Connectivity of large wireless networks under a general connection model,” IEEE Transactions
38
on Information Theory, vol. 59, no. 3, pp. 1761–1772, 2013.
M. Penrose, Random Geometric Graphs, ser. Oxford Studies in Probability.
London: Oxford University Press, 2003.
——, “The longest edge of the random minimal spanning tree,” Annals of Applied Probability, vol. 7, pp. 340–361, 1997.
J. Yu, S.-J. Chung, and P. G. Voulgaris, “Distance optimal target assignment in robotic networks under communication and
sensing constraints,” in Proceedings IEEE International Conference on Robotics & Automation, 2014.
——, “Traveled distance minimization and hierarchical strategies for robotic networks,” in 2014 International Symposium on
Communications, Control, and Signal Processing, Special Session on Modeling and Control of Complex Networks, 2014,
invited.
P. Erd˝os and A. R´enyi, “On a classical problem of probability theory,” Publ. Math. Inst. Hung. Acad. Sci., vol. Ser. A 6, pp.
215–220, 1961.
P. M. Vaidya, “Geometry helps in matchings,” SIAM Journal on Computing, vol. 18, no. 6, pp. 1201–1225, 1989.
R. Sharathkumar and P. K. Agarwal, “A near-linear time ε-approximation algorithm for geometric bipartite matching,” in
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012, pp. 385–394.
M. Ajtai, J. Koml´os, and G. Tusn´ady, “On optimal matchings,” Combinatorica, vol. 4, no. 4, pp. 259–264, 1984.
M. Talagrand, “The Ajtai-Koml´os-Tusn´ady matching theorem for general measures,” In Probability in Banach spaces, vol. 30,
1992.
H. Choset, “Coverage of known spaces: The boustrophedon cellular decomposition,” Autonomous Robots, vol. 9, pp. 247–253,
2000.