See discussions, stats, and author profiles for this publication at: [Link]

net/publication/221344458

Auction-Based Multi-Robot Routing

Conference Paper · June 2005

DOI: 10.15607/RSS.2005.I.045 · Source: DBLP

CITATIONS READS
278 1,847

9 authors, including:

Michail G. Lagoudakis Pinar Keskinocak

Technical University of Crete Georgia Institute of Technology
102 PUBLICATIONS 3,863 CITATIONS 241 PUBLICATIONS 7,630 CITATIONS

SEE PROFILE SEE PROFILE

Craig A. Tovey Adam Meyerson

Georgia Institute of Technology Google Inc.
151 PUBLICATIONS 6,432 CITATIONS 32 PUBLICATIONS 2,988 CITATIONS

SEE PROFILE SEE PROFILE

Some of the authors of this publication are also working on these related projects:

Mental Health View project

Influenza and Pandemic View project

All content following this page was uploaded by Sonal Jain on 02 June 2014.

The user has requested enhancement of the downloaded file.

 Auction-Based Multi-Robot Routing
Michail G. Lagoudakis∗ , Evangelos Markakis† , David Kempe‡ Pinar Keskinocak∗ ,
Anton Kleywegt∗ , Sven Koenig‡ , Craig Tovey∗ , Adam Meyerson§ , and Sonal Jain‡
∗
School of Industrial and Systems Engineering †
College of Computing
Georgia Institute of Technology, Atlanta, GA 30332–0205 Georgia Institute of Technology, Atlanta, GA 30332–0280
Email: {mlagouda, pinar, anton, ctovey}@[Link] Email: vangelis@[Link]

‡Computer Science Department §

Computer Science Department
University of Southern California, Los Angeles, CA 90089-0781 University of California, Los Angeles, CA 90095-1596
Email: {dkempe, skoenig, sonaljai}@[Link] Email: awm@[Link]

Abstract— Recently, auction methods have been investigated The efficiency of auction-based methods has been demon-
as effective, decentralized methods for multi-robot coordination. strated experimentally [1]–[7], but there has been little the-
Experimental research has shown great potential, but has not oretical study [6]. In this paper, we make the following
been complemented yet by theoretical analysis. In this paper we
contribute a theoretical analysis of the performance of auction contributions: (1) we suggest a generic framework for auction-
methods for multi-robot routing. We suggest a generic framework based multi-robot routing, and (2) we derive and analyze
for auction-based multi-robot routing and analyze a variety of six bidding rules for three team objectives (minimizing total
bidding rules for different team objectives. This is the first time cost, maximum cost, or average service cost), specifically, we
that auction methods are shown to offer theoretical guarantees provide lower and upper bounds on their performance relative
for such a variety of bidding rules and team objectives.
to optimal performance. This is the first time that auction
I. I NTRODUCTION methods are shown to offer theoretical guarantees for such
a variety of bidding rules and team objectives.
Robot teams are increasingly becoming a popular alternative
to single robots for a variety of difficult robotic tasks, such as II. M ULTI -ROBOT ROUTING
planetary exploration or planetary base assembly. Robot teams A multi-robot routing problem is specified by a set of robots,
offer many advantages over single robots: robustness (due to R = {r1 , r2 , . . . , rn }, a set of targets, T = {t1 , t2 , . . . , tm },
redundancy), efficiency (due to parallelism), and flexibility their locations, and a non-negative cost function c(i, j), i, j ∈
(due to reconfigurability). However, an important factor for R ∪ T , which denotes the cost of moving between locations
the success of a robot team is the ability to coordinate the i and j. We assume that these costs are symmetric, c(i, j) =
team members in an effective way. Coordination involves c(j, i), are the same for all robots, and satisfy the triangle
the allocation and execution of individual tasks through an inequality. Travel distances and travel times between locations
efficient (preferably decentralized) mechanism. satisfy these assumptions in any typical environment. The
In this paper, we focus on multi-robot routing, a class of objective of multi-robot routing is to find an allocation of
problems where a team of mobile robots must visit a set targets to robots and a path for each robot that visits all targets
of locations for some purpose (e.g., delivery or acquisition) allocated to it so that a team objective is optimized. In this
with routes that optimize certain criteria (e.g., minimization paper, we study three intuitive team objectives:
of consumed energy, completion time, or average latency).
M INI S UM: Minimize the sum of the robot path costs over all robots.
Examples include search-and-rescue in areas hit by disasters,
M INI M AX: Minimize the maximum robot path cost over all robots.
surveillance of a facility, placement of sensors, delivery of
M INI AVE: Minimize the average target path cost over all targets.
parts, and localized measurements. Such routing problems, in-
cluding Vehicle Routing Problems (VRPs) and several variants The robot path cost of a robot r is the sum of the costs along
of the Traveling Salesman Problem (TSP), have been studied its entire path, from its initial location to the last target on its
from a centralized point of view in operations research, and path. The target path cost of a target t is the total cost of the
recently in robotics with a focus on decentralized approaches. path traversed by robot r from its initial location up to target
Even in decentralized multi-robot coordination, some infor- t, where r is the unique robot visiting t.
mation exchange is necessary; it is desirable to enable good
III. O PTIMAL S OLUTIONS
decision making while communicating as little information
as possible. One promising approach of this type is the Optimizing performance for any of the three team objectives
use of market-based mechanisms, in particular, auction-based is NP-hard, as shown by the following theorem.
methods, where the communicated information consists of bids Theorem 1: There is no polynomial time algorithm for
robots place on various tasks, and coordination is achieved by solving multi-robot routing optimally with the M INI S UM, the
a process similar to winner determination in auctions. M INI M AX, or the M INI AVE objective, unless P = NP.
 Proof: We show that a polynomial-time algorithm for bid. This procedure is repeated in every round of the auction.
multi-robot routing with any of the three objectives implies Broadcasting can be achieved by means of relaying messages
a polynomial time algorithm for Hamiltonian Path, a well from robot to robot. Clearly, there is no need for a central
known NP-complete problem. An instance of Hamiltonian auctioneer, and therefore, there is no single point of global
Path consists of a graph G = (V, E) and a vertex v, and failure in the system. Notice also the low communication
we are asked to decide if there exists a path starting from v complexity; each robot needs to receive n numbers (bids) in
that visits all the vertices exactly once. We reduce it to an each of the m rounds, therefore O(nm) numbers need to be
instance of multi-robot routing as follows. Let G0 = (V, c) be communicated over any single link.
the complete weighted graph on V with weights c(u, w) = 1,
if (u, w) ∈ E, and c(u, w) = 2, otherwise. One robot is V. PATHS VERSUS T REES
placed at vertex v and the remaining |V | − 1 vertices are We explore two ways of obtaining approximate solutions
designated as targets. The costs (weights) in G0 satisfy the to multi-robot routing within our auction framework: paths
triangle inequality. and trees. In particular, during the auction, one can consider
We claim that G has a Hamiltonian path if and only if an constructing paths that collectively span all targets (one path
optimal M INI S UM solution in G0 has a cost of |V | − 1. A for each robot), or constructing trees that span all targets
Hamiltonian path in G is also an optimal M INI S UM solution (a forest with one tree rooted at each robot). Considering
in G0 with cost |V | − 1 (this is the least possible cost for paths is a direct method, whereas considering trees is an
visiting |V | − 1 targets). Conversely, if G does not have a indirect method, since the trees must be converted to paths
Hamiltonian path, then any path in G0 that starts from v and to obtain a solution to the original problem. This extra step is
visits all the vertices exactly once has to use some edge of relatively easy and does not significantly affect the quality of
cost 2 in G0 . Hence, the cost of an optimal solution will be the solution.
at least |V |. Similarly, G has a Hamiltonian path if and only The choice of paths versus trees depends on how efficiency
if an optimal M INI M AX solution in G0 has a cost of |V | − 1. and performance are affected. The rationale behind the idea of
Finally, G has a Hamiltonian path if and ¡ only if an optimal constructing trees rather than paths is that trees with certain
0
M INI AVE solution
¢ ¡ in G has
¢ a cost of 1 + 2 + . . . + (|V | − properties might be readily computable compared to paths with
2) + (|V | − 1) / |V | − 1 = |V |/2. similar properties. For example, given any weighted graph, a
Given this hardness result, we focus on efficient approxima- minimum-cost spanning tree can be obtained in polynomial
tion algorithms for solving large-scale instances of multi-robot time, whereas a finding a minimum-cost path through all nodes
routing. However, optimal solutions for small instances can be is an NP-hard problem. Therefore, instead of directly seeking
obtained through a mixed integer programming formulation. paths that achieve a team objective, one may seek to find trees
that achieve an analogous objective, and then convert the trees
IV. AUCTION F RAMEWORK to paths that approximate the original team objective.
Our auction-based coordination system for multi-robot rout- For M INI S UM, the analogous objective is to find a minimum
ing considers the robots as bidders and the targets as goods, spanning forest (MSF), that is, a collection of trees rooted
and operates as follows. All targets are initially unallocated. at the robots that span all targets with minimum total cost.
During each round of bidding, all robots bid on all unallocated Such a forest is computable in polynomial time by a variant of
targets. The robot that places the overall lowest bid on any Prim’s algorithm [8]. For M INI M AX, the analogous objective
target wins and is allocated that particular target. A new round is to find a minimax spanning forest, which is a collection
of bidding begins, and all robots bid again on all unallocated of trees rooted at the robots that span all targets such that
targets, and so on, until all targets have been allocated. Note the cost of the most expensive tree is minimized. Computing
that each robot needs to bid only on a single target in each the minimax tree is an NP-hard problem [9]. Finally, for
round, namely on a target for which its bid is the lowest, since M INI AVE, the analogous objective is to find a minimum
all other bids from the same robot have no chance of winning. average-cost spanning forest which is a collection of trees
Upon allocation of all targets, each robot computes a path for rooted at the robots that span all targets such that the average
visiting the targets allocated to it and then moves along that root-target cost over all targets is minimized. Such a forest can
path. Bid selection and path computation are the key factors be trivially computed by connecting each target to the closest
that affect team performance. root, and consists of stars.
The main advantage of this multi-round auction mechanism A tree can be easily turned into a path using shortcut-
is its simplicity and the fact that it allows for a decentralized ting [10], as commonly used in TSP algorithms. Shortcutting
implementation on real robots. Initially, each robot needs to constructs a path from a tree by performing a depth-first search
know its own location, the location of all targets, and the on the tree to derive the ordering of nodes in the path while
number of robots (the number of bids in each round), but not skipping previously visited nodes. It is well-known that the
the locations of the other robots. In each round, each robot total cost of the resulting path is no more than twice the cost
computes its single bid locally and in parallel with the other of the tree [10]. Alternatively, one could use any sophisticated
robots, broadcasts the bid to the other robots, receives the bids TSP algorithm on the nodes of each tree to obtain a good
of the other robots, and then locally determines the winning path for each robot. The specific method used does not affect
the results in this paper as long as the total cost of each path For the M INI S UM team objective, robot ri bids on target t
is at most twice the cost of the corresponding tree, which X X
can be guaranteed through shortcutting. Thus, in our auction RP C(rj , Sj0 ) − RP C(rj , Sj )
j j
framework and analysis, we assume that the final step of
converting trees into paths incurs an approximation factor of = RP C(ri , Si ∪ {t}) − RP C(ri , Si ).
at most 2 (in M INI S UM cost). For the M INI M AX team objective, robot ri bids on target t
VI. B IDDING RULES max RP C(rj , Sj0 ) − max RP C(rj , Sj )
j j
In every round of the auction, the robots use a bidding rule = RP C(ri , Si ∪ {t}) − max RP C(rj , Sj ).
to determine the appropriate (according to the team objective) j

bid for each target. We suggest a generic methodology for This derivation uses the fact that maxj RP C(rj , Sj0 ) =
deriving such rules for any given team objective, and we derive RP C(ri , Si0 ); otherwise, target t would have already been
six bidding rules for the three team objectives we consider. We allocated in a previous round of bidding. The term
divide the bidding rules into two classes depending on whether maxj RP C(rj , Sj ) can be dropped since the outcome of the
they aim to build paths or trees. auction remains unchanged if all bids change by a constant.
Suppose that the team objective is expressed as Thus, robot ri can just bid RP C(ri , Si ∪{t}) on target t. Last,
¡ ¢ for the M INI AVE team objective, robot ri bids on target t
min f g(r1 , A1 ), . . . , g(rn , An )
A
1X 1X
where function g measures the performance of each robot, CT P C(rj , Sj0 ) − CT P C(rj , Sj )
m j m j
function f measures the performance of the team, and A =
{A1 , A2 , . . . , An } is a partition of the set of targets, where 1³ ´
= CT P C(ri , Si ∪ {t}) − CT P C(ri , Si ) .
targets in Ai are allocated to robot ri . The three team objec- m
tives we consider fit this structure. Let RP C(ri , Ai ) denote The factor 1/m can be dropped since the outcome of the
the minimum robot path cost for robot ri to visit all targets auction remains unchanged if all bids are multiplied by a
in Ai from its current location. Similarly, let CT P C(ri , Ai ) positive constant. Thus, robot ri can bid just CT P C(ri , Si ∪
denote the minimum cumulative target path cost of all targets {t}) − CT P C(ri , Si ) on target t.
in Ai , again, if robot ri visits all targets in Ai from its current Thus, the bidding rules for the three team objectives are
location. Then, the three team objectives can be expressed as • B ID S UM PATH : RP C(ri , Si ∪ {t}) − RP C(ri , Si ),
• B ID M AX PATH : RP C(ri , Si ∪ {t}), and
X
M INI S UM : min RP C(rj , Aj ),
A • B IDAVE PATH : CT P C(ri , Si ∪ {t}) − CT P C(ri , Si ).
j
M INI M AX : min max RP C(rj , Aj ), The robots need to be able to calculate their bids efficiently, but
A j computing RP C or CT P C is NP-hard. Therefore, we assume
1X that each robot ri uses a heuristic method to approximate these
M INI AVE : min CT P C(rj , Aj ).
A m functions. In particular, we make use of the insertion heuristic
j
for TSP: given a path that visits the targets in Si , evaluate all
Let (S1 , S2 , . . . , Sn ) be the current partial allocation of insertions of target t into all possible positions on the existing
targets to robots in some round of the auction, and let t be path, and choose the one that minimizes the cost of the new
an unallocated target. We propose the following bidding rule, path. Our results are not affected if other methods are used, as
which is directly derived from the team objective. long as the resulting bids are not worse than the bids computed
Bidding Rule Robot r bids on unallocated target using the insertion heuristic.
t the difference in performance for the given team A similar analysis can be used to derive bidding rules for
objective between the current allocation of targets to the case of constructing trees. For any robot ri and any set
robots and the allocation that results from the current of targets Si , let RT C(ri , Si ) denote the minimum robot
one if robot r is additionally allocated target t. tree cost, that is, the cost of a minimum spanning tree over
the nodes {ri } ∪ Si . Similarly, let CT T C(ri , Si ) denote the
Consequently, robot ri should bid on target t the difference minimum cumulative target tree cost which is the sum of root-
target costs for all targets in Si in a spanning tree over {ri }∪Si
³ ´ ³ ´
f g(r1 , S10 ), . . . , g(rn , Sn0 ) − f g(r1 , S1 ), . . . , g(rn , Sn ) ,
with root ri . Without going through details, the bidding rules
where Si0 = Si ∪ {t} and Sj0 = Sj for i 6= j. This for the three team objectives in this case are
generic bidding rule thus performs some sort of hill climbing, • B ID S UM T REE : RT C(ri , Si ∪ {t}) − RT C(ri , Si ),

aiming to find a good, but not necessarily optimal, allocation. • B ID M AX T REE : RT C(ri , Si ∪ {t}), and

Note that this generic bidding rule may require additional • B IDAVE T REE : CT T C(ri , Si ∪ {t}) − CT T C(ri , Si ).

communication for computing the bids. However, for the Given the sequential nature of allocation, the T REE bidding
objectives we consider, bid computation can be done locally. rules can be further simplified. In particular, a tree over Si
 TABLE I
remains unchanged within a tree over Si ∪ {t} under any of
B OUNDS ON PERFORMANCE RATIO ( RULE PERFORMANCE OVER OPTIMAL
the three objectives. This is true because target t was not
PERFORMANCE ) WITH n ROBOTS AND m TARGETS .
allocated in earlier rounds (even though it was present and Bidding Team Objective
available), and hence it does not offer a better way to connect Rule M INI S UM M INI M AX M INI AVE
nodes in Si . For the B ID S UM T REE and B ID M AX T REE rules, Lower Upper Lower Upper Lower Upper
m+1
target t is connected to Si through the cheapest edge, whereas B ID S UM PATH 1.5 2 n 2n
2
2m
for the B IDAVE T REE rule, it is connected directly to the n+1
B ID M AX PATH n 2n 2n Ω(m1/3 ) 2m
root ri because of the triangle inequality assumption. In other 2
2 n+1 2 1/3
B IDAVE PATH m 2m 2m n Ω(m ) 2m2
words, RT C(ri , Si ∪ {t}) = RT C(ri , Si ) + c(Si ∪ {ri }, t), 2
m+1
where c(Si ∪ {ri }, t) is the cost of the cheapest edge between B ID S UM T REE 1.5 2 n 2n 2m
2
any node in Si ∪ {ri } and t, and CT T C(ri , Si ∪ {t}) = n+1 1/3
B ID M AX T REE n 2n 2n Ω(m ) 2m
CT T C(ri , Si ) + c(ri , t). Thus, the rules can be expressed as: 2
n+1
B IDAVE T REE m 2m 2mn Ω(m1/3 ) 2m2
• B ID S UM T REE : c(Si ∪ {ri }, t), 2
• B ID M AX T REE : RT C(ri , Si ) + c(Si ∪ {ri }, t), and
shortcutting (polynomial). Once again, we only assume that,
• B IDAVE T REE : c(ri , t).
whatever the choice, the cost of each path is at most twice the
Bids for the T REE rules are computable in polynomial time. cost of the corresponding tree as guaranteed by shortcutting.
VII. S UMMARY OF R ESULTS Our bounds apply to the entire family of rules. In deriving
the upper bounds, we do not assume any better heuristic
We assess the performance of each bidding rule theoretically than the insertion heuristic or shortcutting. In addition, the
in comparison to optimal performance and with respect to each lower bounds hold even if RP C and CT P C, as well as the
of the three team objectives. This is done in terms of upper conversion of trees to paths, are computed optimally.
and lower bounds on the performance ratio (maximum ratio Table I summarizes our results. The PATH and the T REE
of rule performance over optimal performance). rules offer almost identical guarantees, which implies that
If I(n, m) is the class of all instances of multi-robot they are not fundamentally different from a theoretical point
routing with n robots and m targets, an upper bound on the of view. In practice, the PATH rules yield somewhat better
performance ratio for a rule R and an objective X is a function solutions, as they build paths directly, whereas the T REE
UB(n, m, R, X) such that for any n and m: rules are computationally more efficient, since bid computation
R(I, X) for the T REE rules is much faster than for the PATH rules.
max ≤ UB(n, m, R, X) , Given that often n ¿ m, it is clear that the best guarantees
I∈I(n,m) O(I, X)
are offered for the M INI S UM and the M INI M AX objectives,
where R(I, X) is the cost of the solution under objective X whereas there are only loose guarantees for the M INI AVE
for instance I ∈ I(n, m) obtained using rule R and O(I, X) is objective. Independently of the objective, the B ID S UM PATH
the optimal cost under objective X for instance I. The perfor- and B ID S UM T REE rules provide uniformly the best guaran-
mance ratio is lower bounded by a function LB(n, m, R, X) tees. Overall, our results show that our auction-based methods
if there exists some infinite family of instances F such that constitute a principled, viable approach to multi-robot routing.
for each I ∈ F:
VIII. A NALYSIS
R(I, X)
LB(nI , mI , R, X) ≤ , In this section we prove the bounds in Table I. We make
O(I, X) the following notational conventions. The solution found by
where nI and mI are the number of robots and targets in using any of the bidding rules is marked with the name
instance I. Therefore, the performance ratio cannot be less of the rule, e.g. B ID S UM T REE. An optimal solution for
than LB(n, m, R, X). An upper bound provides a guarantee each team objective is denoted by O PT S UM, O PT M AX, and
on the performance of the corresponding rule for the corre- O PTAVE, respectively, and the cost of a solution S according
sponding objective, whereas a lower bound usually represents to each team objective by S UM(S), M AX(S), and AVE(S),
pathological cases that demonstrate worst-case behavior. respectively. With a slight abuse of notation, if F is a forest, we
It should be pointed out that each bidding rule essentially also use S UM(F ) for the total cost of the forest, M AX(F ) for
represents a family of rules. For the PATH rules, we do the cost of the most expensive tree in the forest, and AVE(F )
not specify a particular choice for the computation of the for the average of all root-target costs in the forest.
functions RP C and CT P C. This choice can be anything The following lemma on the relationship of the various
between computing them optimaly (NP-hard) and computing objective functions is used repeatedly.
them approximately through the insertion heuristic (polyno- Lemma 1: Let F be a spanning forest rooted at the robots,
mial). However, we assume that whatever the choice, the that spans all targets in an instance of multi-robot routing with
approximation will not be worse than the insertion heuristic n robots and m targets. Then, it holds that
approximation. Similarly, for the T REE rules we do not specify
AVE (F) ≤ M AX (F) ≤ S UM (F) ≤ n M AX (F),
a particular choice for the conversion of trees to paths, which
can range from computing optimal paths (NP-hard) to using S UM (F) ≤ m AVE (F).
 Proof: The maximum root-target cost of any target can which implies that
be at most equal to the cost of the most expensive tree in the ¡ ¢
S UM (B ID S UM PATH ) ≤ 2 S UM MSF(G) . (1)
forest. Therefore, the average of the root-target costs cannot
be more than the cost of the most expensive tree in the forest. An optimal solution O PT S UM for the M INI S UM team objec-
Furthermore, the cost of the most expensive tree in the forest tive is also a spanning forest in G, therefore it is true that
cannot exceed the total cost of the forest. The total cost of ¡ ¢
S UM MSF(G) ≤ S UM (O PT S UM ).
the forest cannot exceed an n-multiple of the cost of the most
expensive tree, since there are at most n trees in the forest. Thus, we conclude that
Finally, there are m targets in the forest and the contribution
S UM (B ID S UM PATH ) ≤ 2 S UM (O PT S UM ).
of each target to the total cost of the forest is no more than its
root-target cost. Therefore, the total cost of the forest cannot
exceed the sum of all root-target costs, which can be expressed Using Equation (1), Lemma 1, and the fact that both O PT-
as an m-multiple of the average root-target cost. M AX and O PTAVE are spanning forests, we also conclude:
Note that Lemma 1 holds even if F is a collection of disjoint Corollary 1: The performance ratio of the B ID S UM PATH
robot paths which span all targets. bidding rule for the M INI M AX team objective is at most 2n.
Corollary 2: The performance ratio of the B ID S UM PATH
A. Upper Bounds for B ID S UM PATH
bidding rule for the M INI AVE team objective is at most 2m.
Theorem 2: The performance ratio of the B ID S UM PATH
bidding rule for the M INI S UM team objective is at most 2. B. Upper Bounds for B ID M AX PATH
Proof: Let G = (R ∪ T, c) be the weighted graph over Theorem 3: The performance ratio of the B ID M AX PATH
all robot and target nodes. In each round k of the auction, bidding rule for the M INI S UM team objective is at most 2n.
k = 0, . . . , m − 1, let Vk be the set of robot nodes and Proof: As in Theorem 2, consider the cuts (Vk , V̄k ) in
allocated target nodes and V̄k the set of unallocated target each round k of the auction. Let c(Vk , V̄k ) be the cost of a
nodes. The sets Vk and V̄k define a cut over G, and, obviously, cheapest edge across the cut (Vk , V̄k ) and Pik , i = 1, . . . , n,
V0 = R, V̄0 = T , Vm = R ∪ T , and V̄m = ∅. In each round be the robot paths in Vk . We establish by induction that in any
k, B ID S UM PATH selects a target t ∈ V̄k that can be added round k, the S UM cost of each path Pik is bounded by:
to one of the paths in Vk with the least additional cost. Let k−1
this cost be b(Vk , V̄k ), which is exactly the bid placed by the
X
S UM(Pik ) ≤ 2 c(Vj , V̄j )
winning robot. Therefore, the S UM cost of the solution found j=0
by B ID S UM PATH at the end of the auction is:
The base case is certainly true as Pi0 = {ri } (a single node),
m−1
X S UM(Pi0 ) = 0. Assume that the assertion holds for k. In
S UM (B ID S UM PATH ) = b(Vk , V̄k )
the next round, B ID M AX PATH allocates a target t ∈ V̄k that
k=0
minimizes the cost of the most expensive path in Vk+1 . The
Let c(Vk , V̄k ) be the cost of a cheapest edge across the cut path Prk+1 where t was added must be the most expensive
(Vk , V̄k ). A target in V̄k corresponding to a cheapest edge path in Vk+1 , otherwise t would have been allocated in some
can be inserted into some path in Vk with a cost increase previous round. Therefore, for any path Pik+1 in Vk+1 it is
of at most 2c(Vk , V̄k ) in S UM cost (because of the triangle true that
inequality assumption). Since the B ID S UM PATH rule identifies S UM(Pik+1 ) ≤ S UM(Prk+1 ).
an insertion with minimum increase in S UM cost, it must be
the case that b(Vk , V̄k ) ≤ 2c(Vk , V̄k ). Hence, Let (t00 , t0 ) be the cheapest edge across the cut (Vk , V̄k ), with
m−1
t0 ∈ V̄k . Also, let Prk0 ⊆ Vk be the path containing t00 . Target
S UM (B ID S UM PATH ) ≤ 2
X
c(Vk , V̄k ) t0 can be inserted into path Prk0 with an increase of at most
k=0
2c(Vk , V̄k ) in the S UM cost of Prk0 (because of the triangle
inequality assumption). Since B ID M AX PATH chose to insert t
Consider another graph G0 which is identical to G except that
in Prk in round k, it must be the case that
exactly m edges have their costs lowered. In particular, for
every cut (Vk , V̄k ) the cost of a cheapest edge connecting t (the S UM(Prk+1 ) ≤ S UM(Prk0 ) + 2 c(Vk , V̄k )
target selected by B ID S UM PATH) to Vk is lowered to c(Vk , V̄k )
Finally, by the inductive hypothesis we have
(the cost of a cheapest edge across the cut) in G0 . Clearly, those
k−1 k
m edges in G0 form an MSF in G0 (it is equivalent to running X X
Prim’s algorithm starting with the robot nodes connected to S UM(Pik+1 ) ≤ 2 c(Vj , V̄j )+2 c(Vk , V̄k ) = 2 c(Vj , V̄j ).
j=0 j=0
each other with zero cost). An MSF in G cannot have less
S UM cost than any MSF in G0 , since we have only lowered Since the M AX cost of the B ID M AX PATH solution is the S UM
costs while constructing G0 from G. Therefore, we obtain: cost of the most expensive path, we conclude that
m−1 m−1
X
X
c(Vk , V̄k ) = S UM MSF(G0 ) ≤ S UM MSF(G) . M AX (B ID M AX PATH ) ≤ 2 c(Vj , V̄j ).
¡ ¢ ¡ ¢

k=0 j=0
Using the construction for graph G0 as in Theorem 2, we have Using Equation (3), Lemma 1, and the fact that both O PT-
M AX and O PTAVE are spanning forests, we also conclude:
M AX (B ID M AX PATH ) ≤ 2 S UM (MSF). (2)
Corollary 5: The performance ratio of the B IDAVE PATH
An optimal solution O PT S UM for the M INI S UM team objec- bidding rule for the M INI M AX team objective is at most
tive is also a spanning forest, so by Lemma 1 we have 2m2 n.
Corollary 6: The performance ratio of the B IDAVE PATH
S UM (B ID M AX PATH ) ≤ 2n S UM (O PT S UM ). bidding rule for the M INI AVE team objective is at most 2m2 .

D. Upper Bounds for B ID S UM T REE

Using Equation (2), Lemma 1, and the fact that both O PT-
M AX and O PTAVE are spanning forests, we also conclude: Theorem 5: The performance ratio of the B ID S UM T REE
Corollary 3: The performance ratio of the B ID M AX PATH bidding rule for the M INI S UM team objective is at most 2 [6].
bidding rule for the M INI M AX team objective is at most 2n. Proof: The bid placed by each robot in each round is
Corollary 4: The performance ratio of the B ID M AX PATH equal to the cost of adding the closest unallocated target to its
bidding rule for the M INI AVE team objective is at most 2m. own subtree. Considering all robot nodes as connected with
each other with zero cost, the auction with the B ID S UM T REE
C. Upper Bounds for B IDAVE PATH rule is identical to Prim’s algorithm for MST [8]. Therefore,
Theorem 4: The performance ratio of the B IDAVE PATH the tree found by this rule is indeed an MSF. Converting the
bidding rule for the M INI S UM team objective is at most 2m2 . trees of an MSF to paths incurs a factor of 2, therefore:
Proof: As in Theorem 2, consider the cuts (Vk , V̄k ) in S UM (B ID S UM T REE ) ≤ 2 S UM (MSF). (4)
each round k of the auction. In each round k, B IDAVE PATH
selects a target t ∈ V̄k that is added to one of the paths in An optimal solution O PT S UM for the M INI S UM team objec-
Vk with the least increase in the AVE team objective. Let this tive is also a spanning forest, therefore we conclude that
increase be b(Vk , V̄k ) which corresponds to the bid placed by
S UM (B ID S UM T REE ) ≤ 2 S UM (O PT S UM ).
the winning robot. Therefore, the AVE cost of the solution
found by B IDAVE PATH at the end of the auction is:
m−1
X Using Equation (4), Lemma 1, and the fact that both O PT-
AVE (B IDAVE PATH ) = b(Vk , V̄k ) M AX and O PTAVE are spanning forests, we also conclude:
k=0 Corollary 7: The performance ratio of the B ID S UM T REE
bidding rule for the M INI M AX team objective is at most 2n.
Let c(R, V̄k ) be the cost of a cheapest edge across the sets
Corollary 8: The performance ratio of the B ID S UM T REE
R and V̄k , that is, the cost of a cheapest edge between some
bidding rule for the M INI AVE team objective is at most 2m.
unallocated target t0 and some robot r0 . Target t0 can always
be inserted as the first target in the path of r0 in Vk . Such E. Upper Bounds for B ID M AX T REE
an insertion causes an increase of at most 2c(R, V̄k ) in the
Theorem 6: The performance ratio of the B ID M AX T REE
robot-target cost of each target in the path because of the
bidding rule for the M INI S UM team objective is at most 2n.
triangle inequality assumption, while the robot-target cost of
Proof: As in Theorem 2, consider the cuts (Vk , V̄k ) in
t0 is c(R, V̄k ). In the worst case, this insertion occurs at a path
each round k of the auction. Let c(Vk , V̄k ) be the cost of
that contains all other targets. Since the increase of the robot-
the cheapest edge across the cut (Vk , V̄k ). We establish by
target cost for each of the m targets is at most 2c(R, V̄k ),
induction that in any round of the auction, the S UM cost of
so is the increase in AVE cost. Since the B IDAVE PATH rule
any tree Tik , i = 1, . . . , n, in Vk is bounded as follows:
identifies the insertion with the least increase in each round,
it must be the case that b(Vk , V̄k ) ≤ 2c(R, V̄k ), and therefore k−1
X
m−1
S UM(Tik ) ≤ c(Vj , V̄j )
j=0
X
AVE (B IDAVE PATH ) ≤ 2 c(R, V̄k ).
k=0 The base case is certainly true as Ti0 = {ri } (a single node),
It holds that c(R, V̄k ) ≤ S UM (MSF), since in an MSF, no S UM(Ti0 ) = 0. Assume that the assertion holds for k. In
robot can reach a target with cost less than the cheapest direct the next round, B ID M AX T REE allocates a target t ∈ V̄k that
edge from any robot to that target. Therefore, minimizes the cost of the most expensive tree in Vk+1 . The
tree Trk+1 where t was added must be the most expensive
AVE (B IDAVE PATH ) ≤ 2m S UM (MSF). (3) tree in Vk+1 ; otherwise, t would have been allocated in some
previous round. Therefore, for any tree Tik+1 in Vk+1 it is true
An optimal solution O PT S UM for the M INI S UM team objec-
that
tive is also a spanning forest, so by Lemma 1 we have that
S UM(Tik+1 ) ≤ S UM(Trk ) + c(Trk , t)
S UM (B IDAVE PATH ) ≤ 2m2 S UM (O PT S UM ).
Let (t00 , t0 ) be the cheapest edge across the cut (Vk , V̄k ), with
t0 ∈ V̄k . Also, let Trk0 ⊆ Vk be the tree containing t00 . Since
 1+² 1 1+² 1 m
¾- e¾- ¾- e e e e ... e e e e
1 61 n
Fig. 1. A simple instance with 2 robots (squares) and two targets (circles). β ?
¾- ...
B ID M AX T REE chose to attach t to Trk in round k, it must be
the case that Fig. 2. Parallel lines construction: n robots and m = n targets spaced
evenly (distance of β) on two parallel lines (one for robots, one for targets).
S UM(Trk ) + c(Trk , t) ≤ S UM(Trk0 ) + c(Trk0 , t0 ) , The distance between the two lines is 1, except for the left-most robot which
is a little closer to its corresponding target.
or, using the fact that c(Trk0 , t0 ) = c(Vk , V̄k ):
where the factor of 2 comes from the conversion of stars to
S UM(Tik+1 ) ≤ S UM(Trk0 ) + c(Vk , V̄k ). paths. Thus, given that any optimal solution O PT S UM is also
a spanning forest, we conclude that
Finally, by the inductive hypothesis
S UM (B IDAVE T REE ) ≤ 2m S UM (O PT S UM ).
k−1
X k
X
S UM(Tik+1 ) ≤ c(Vj , V̄j ) + c(Vk , V̄k ) = c(Vj , V̄j ). Using Equation (6), Lemma 1, and the fact that both O PT-
j=0 j=0 M AX and O PTAVE are spanning forests, we also conclude:
Corollary 11: The performance ratio of the B IDAVE T REE
Since the M AX cost of the B ID M AX T REE solution is at most
bidding rule for the M INI M AX team objective is at most 2mn.
twice the S UM cost of the most expensive tree (taking into
Corollary 12: The performance ratio of the B IDAVE T REE
account the conversion of trees to paths), we conclude that
bidding rule for the M INI AVE team objective is at most 2m2 .
m−1
X
M AX (B ID M AX T REE ) ≤ 2 c(Vj , V̄j ). G. Lower bounds
j=0 In all example instances, robots are shown as squares, single
Using the construction for graph G0 as in Theorem 2, we have targets as open circles, clusters of targets as solid circles, and ²
represents an arbitrarily small positive number. The examples
M AX (B ID M AX T REE ) ≤ 2 S UM (MSF), (5) that yield lower bounds for the T REE rules are identical to
those for the PATH rules, and therefore, they are omitted.
An optimal solution O PT S UM for the M INI S UM team objec- B ID S UM PATH applied to the instance in Figure 1 allocates
tive is also a spanning forest, so by Lemma 1 we have both targets to the robot on the right with a S UM cost of
S UM (B ID M AX T REE ) ≤ 2n S UM (O PT S UM ). 3 + ² ≈ 3, as opposed to the O PT S UM cost of 2 + 2² ≈ 2 (one
target to each robot). By replicating the construction, we obtain
an infinite family of such instances, thus a lower bound for
Using Equation (5), Lemma 1, and the fact that both O PT- the performance ratio of B ID S UM PATH for M INI S UM is 1.5.
M AX and O PTAVE are spanning forests, we also conclude: Applying the B ID S UM PATH rule to the example in Figure 2
Corollary 9: The performance ratio of the B ID M AX T REE with β = 1 − ² yields a solution that allocates all targets to
bidding rule for the M INI M AX team objective is at most 2n. the left-most robot, and a path that runs through all targets
Corollary 10: The performance ratio of the B ID M AX T REE left to right. Obviously, M AX (B ID S UM PATH ) ≈ n, whereas
bidding rule for the M INI AVE team objective is at most 2m. M AX (O PT M AX ) = 1 (each robot visits its corresponding
target). Therefore, a lower bound for the performance ra-
F. Upper Bounds for B IDAVE T REE tio of B ID S UM PATH for M INI M AX is n = m. Similarly,
Theorem 7: The performance ratio of the B IDAVE T REE AVE (B ID S UM PATH ) ≈ (1 + 2 + . . . + n)/n = (n + 1)/2,
bidding rule for the M INI S UM team objective is at most 2m. whereas AVE (O PTAVE ) = 1 (each robot visits its correspond-
Proof: Under the B IDAVE T REE rule, the intermediate ing target). Therefore, a lower bound for the performance ratio
spanning forest at the end of the auction will consist of stars, of B ID S UM PATH for M INI AVE is (n + 1)/2 = (m + 1)/2.
one for each robot, where each target is connected directly to Applying B ID M AX PATH to the instance in Figure 2 with
the closest (in terms of cost) robot. Because of the triangle β = ² yields a solution that allocates one target to each robot.
inequality assumption, direct connections minimize the robot- Thus, S UM (B ID M AX PATH ) = n, whereas S UM (O PT S UM ) =
target costs, and therefore the average. 1 + n² ≈ 1 (the left most robot takes all targets) for
Let c∗ be the cost of the most expensive robot-target edge ² = o(1/n). Thus, a lower bound for the performance
in the forest. It holds that c∗ ≤ S UM (MSF), since in an MSF, ratio of B ID M AX PATH for M INI S UM is n = m. Similarly,
no robot can reach a target with cost less than the cheapest S UM (B IDAVE PATH ) = n, whereas S UM (O PT S UM ) ≈ 1 (the
direct edge from any robot to that target. Since there are m left-most robot takes all targets). Thus, a lower bound for the
targets in total, the S UM cost of the forest is at most mc∗ , and performance ratio of B IDAVE PATH for M INI S UM is n = m.
thus, the S UM cost of B IDAVE T REE can be at most 2mc∗ , Applying B ID M AX PATH (or B IDAVE PATH) to the instance
in Figure 3 yields a solution that allocates one target per
S UM (B IDAVE T REE ) ≤ 2mc∗ ≤ 2m S UM (MSF), (6) cluster to each robot. The path of each robot traverses the grid
 e ...
(n, 1) (n, n) 6²
e
u u u ... u u u u e
T2
6 ? e
β+1 e e ...
?
u¾- u
e
u ... u u u u e 6
β T1 ²
.. .. .. .. .. .. ..
e ?
e ...
. . . . . . .
Fig. 4. Cluster arrangement in grid construction: example with 2 clusters
u u u ... u u u u of 5 targets each and 5 robots clustered on the left. Targets in cluster T1 are
arranged evenly on a line of slope -45◦ within a small cost from each other.
Each of the 5 robots visits one target in T1 , since the straight line is the
(1, 1) (1, n)
u u u ... u u u u shortest path. Targets in T2 have the same arrangement, but are shifted up by
² to ensure that the cost between corresponding targets in T1 and T2 is less
than any other inter-cluster cost. The robot that visits the first target in T1
Fig. 3. Grid construction: n robots at (1, 1) and m = n3 targets on a will also visit the first target in T2 , and so on. This pattern repeats along the
(n × n) rectangular grid; each of the n2 gridpoints is a cluster of n targets. horizontal axis, but it can also be used for clusters arranged vertically.
The intra-row distance is β, whereas the intra-column distance is β + 1.
alternating left-to-right and right-to-left, and also from bottom performance guarantees. We are currently conducting exten-
to top. Figure 4 shows the necessary adjustments to make this sive experimentation to assess the actual performance of our
possible. Thus, M AX (B ID M AX PATH ) = n(n − 1)β + (β + bidding rules and their effectiveness in solving large problems.
1)(n − 1) = (nβ + β + 1)(n − 1), whereas M AX (O PT M AX ) ≤
ACKNOWLEDGMENT
(n − 1)β + (β + 1)(n − 1) = (2β + 1)(n − 1) (each robot takes
one row of the grid). Thus, a lower bound for the performance This research was partially supported by NSF awards under
ratio of B ID M AX PATH for M INI M AX is (n+1)/2 = (m1/3 + contracts DMI-0113881, IIS-0413196, and IIS-0412912.
1)/2 for large β. In addition, without going into a detailed R EFERENCES
analysis, it is obvious that AVE (B ID M AX PATH ) = Ω(n2 ), [1] G. Rabideau, T. Estlin, S. Chien, and A. Barrett, “A comparison of
whereas AVE (O PTAVE ) = O(n) (each robot takes one row coordinated planning methods for cooperating rovers,” in Proceedings
of the Intl Conference on Autonomous Agents, 2000, pp. 100–101.
of the grid). Thus, a lower bound for the performance ratio [2] M. Dias and A. Stentz, “A free market architecture for distributed control
of B ID M AX PATH for M INI AVE is Ω(n) or Ω(m1/3 ) since of a multirobot system,” in Proceedings of the International Conference
m = n3 . The same bounds hold for B IDAVE PATH. on Intelligent Autonomous Systems, 2000, pp. 115–122.
[3] B. Gerkey and M. Matarić, “Sold!: Auction methods for multi-robot
IX. R ELATED W ORK coordination,” IEEE Transactions on Robotics and Automation, vol. 18,
no. 5, pp. 758–768, 2002.
Multi-robot routing falls into the class of Location Routing [4] R. Zlot, A. Stentz, M. Dias, and S. Thayer, “Multi-robot exploration
problems [11]. There has been a tremendous amount of work controlled by a market economy,” in Proceedings of the International
on centralized algorithms for solving such problems optimally Conference on Robotics and Automation, 2002, pp. 3016–3023.
[5] M. Berhault, H. Huang, P. Keskinocak, S. Koenig, W. Elmaghraby,
or approximately. The M INI S UM objective has been studied P. Griffin, and A. Kleywegt, “Robot exploration with combinatorial
in the context of k-TSP problems and can be approximated by auctions,” in Proceedings of the International Conference on Intelligent
a constant factor [12], [13]. The M INI M AX objective appears Robots and Systems, October 2003, pp. 1957–1962.
[6] M. Lagoudakis, M. Berhault, P. Keskinocak, S. Koenig, and A. Kley-
also in the Nurse Location Problem for which there exists an wegt, “Simple auctions with performance guarantees for multi-robot task
8-approximation [9]. This objective has also been studied in allocation,” in Proceedings of the International Conference on Intelligent
the context of job scheduling on unrelated parallel machines Robots and Systems, September 2004.
[7] C. Tovey, M. Lagoudakis, S. Jain, and S. Koenig, “The generation of
(makespan) [14]. Finally, the M INI AVE objective (also known bidding rules for auction-based robot coordination,” in Proceedings of
as the Traveling Repairman Problem) is approximable to a the 3rd International Multi-Robot Systems Workshop, March 2005.
constant factor [15]. Robotics researchers have studied the [8] R. C. Prim, “Shortest connection networks and some generalizations.”
Bell Systems Technical Journal, pp. 1389–1401, 1957.
M INI S UM [2], [5]–[7] objective extensively, but only occa- [9] G. Even, N. Garg, J. Könemann, R. Ravi, and A. Sinha, “Min-Max tree
sionally the M INI M AX [1], [7] and M INI AVE [7] objectives. covers of graphs,” Operations Research Letters, vol. 32, pp. 309–315,
A variety of auction methods have been used for multi- 2004.
[10] E. Lawler, J. Lenstra, A. Rinnooy Kan, and D. Shmoys, Eds., The Trav-
robot routing. Berhault et. al. [5] have used combinatorial eling Salesman Problem: A Guided Tour of Combinatorial Optimization.
auctions; however, the complexity of these auctions makes Wiley, 1985.
them impractical for large problems. Dias and Stentz [2] have [11] P. Toth and D. Vigo, Eds., The Vehicle Routing Problem, ser. Mono-
graphs on Discrete Mathematics and Applications. SIAM, 2002.
proposed a single-item auction similar to B ID S UM PATH which [12] G. N. Frederickson, M. S. Hecht, and C. E. Kim, “Approximation
has been implemented on real robots for exploration tasks. Our algorithms for some routing problems,” SIAM Journal of Computing,
PATH rules have been tested experimentally [7], and have been vol. 7, no. 2, pp. 178–193, 1978.
[13] J. O. Cerdeira, “The multi-depot traveling salesman problem,” Revista
shown to perform best for their corresponding team objective. Investigao Operacional, vol. 12, 1992.
Also, their actual performance is well below the theoretical [14] J. K. Lenstra, D. B. Shmoys, and E. Tardos, “Approximation algorithms
upper bounds. for scheduling unrelated parallel machines,” Math. Program., vol. 46,
no. 3, pp. 259–271, 1990.
X. C ONCLUSION [15] J. Fakcharoenphol, C. Harrelson, and S. Rao, “The k-traveling repairman
problem,” in SODA ’03: Proceedings of the fourteenth annual ACM-
We presented a theoretical analysis of auction-based meth- SIAM symposium on Discrete algorithms. Society for Industrial and
ods for multi-robot routing and established for the first time Applied Mathematics, 2003, pp. 655–664.

View publication stats