IEEE Robotics & Automation Magazine - December 2010 - 66

Centralized solutions usually define
the coordination problem as an
integer linear programming problem,
ignoring communication costs.
sink (central unit) collecting the task, the cost of performing
tasks by each robot, and potential benefit to the team. Robots
positioned in local neighborhoods participate, but the locality
is not predetermined; it is rather task-dependent. Robots participating in the auction decide on whether or not to invite
more robots to the auction, as the invitations themselves cause
communication overhead. One of the well-known auction
protocols is MURDOCH [12]. It uses anonymous broadcasting as a means to communicate and has the following five distinct
steps: task announcement, metric evaluation, bid submission,
auction closing, and progress monitoring/contract renewal.
However, MURDOCH assumes a complete graph among
robots, while we use UDG. Similarly, in [13] and [14], local
auctions are used as a distributed solution to dynamic MRTA.
However, all robots participating in an auction can communicate directly to the auctioneer.
Article [15] considers the problem of selecting one mobile
sensor for each of the positions to be covered so that the total distance traveled by the selected sensors to their allocated positions is
minimized. The market-based algorithm described gives the
same results as the matrix scan algorithm (where each element in
the matrix is the cost associated with the respective worker and
job), which selects the smallest element in the whole matrix as
part of the solution, deletes the selected row and column, and
continues the scan in the same way for the smaller matrix. When
only one task exists, the closest robot is assigned to it, and the
communication aspects of finding it are not discussed.
Survey article [16] summarizes research work done in the
field of robot coordination using the market-based approach.
Auction can be either centralized (for all robots) or localized,
where only nearby robots will respond. Market-based approaches have yet to be implemented on teams of more than a
few robots [16]. There is no discussion of communication cost
for large robot teams, except a simple statement [16, Table 3]
that communication cost is proportional to the number of
robots.

To the best of our knowledge, bid aggregation in the task
assignment problem in robot-robot coordination was not
considered in literature. We refer here to the aggregation of
responses of several robots by an intermediate robot, which
then selects the best of them and forwards only that bid to
the auctioneer.
Simple Auction Protocol
We identified only one protocol [4] for a single-task, singlerobot (called actor in [4]) assignment, which explicitly considers multihop scenarios (UDG). It is a localized solution
for actor-actor coordination based on auction protocol [4]
and is called here a SAP. The request for service is flooded
from the actor node that collected the report, and each actor
responds back (with the offer to provide service and the cost
of doing it) to it by a separate routing task. If blind flooding
is used for actor search, each robot retransmits the request
upon receiving it for the first time and ignores it afterward.
This protocol can always find the closest robot to the event,
since all robots are consulted. However, the response time
can be large even in the cases where the best robot is near the
event, since the response from all robots is gathered before a
decision is made.
Face Traversal
Stateless position-based routing with guaranteed delivery
was first described in [17]. It was applied in [18] for the data
storage problem as follows. A geographic hash table is used to
find the location for storing data based on its hashed table.
Data is then routed toward home, as decided by the hash
table, and stored there; in Figure 3, Point E is the home.
However, E is not an existing node in the network. Routing
proceeds with the greedy-face-greedy (GFG) algorithm [17]
from the source S toward destination E. It will create a loop
in the face containing E. In Figure 3, the whole path is
SABCDFC, and loop CDFC is detected. The closest node in
the network to node E is the one from the loop. In Figure 3,
it is node D, and node F can decide it since the closest node
to E travels together with the message. Face traversal is done
using Gabriel graph of UDG. An edge uv belongs to Gabriel
graph if and only if no other edges are located inside the
circle with diameter uv. Thus, its construction is easy. Figure
3 shows only the Gabriel graph of UDG for clarity. A readable and correct explanation of the GFG algorithm can be
found in [19].

Improved Simple Auction and
Auction Aggregation Protocols
A
S

C
B
E
F

Figure 3. The face traversal algorithm over the Gabriel graph
of UDG.
66

IEEE Robotics & Automation Magazine

For simplicity, in the following sections, we assume that the
robot network is connected, and the event location is known
to the bidding robot (robot collector). Note that in WSRN,
sensor nodes may be used to connect some robots; however,
this scenario is not considered here.
In this section, we describe five new protocols: k-SAP,
SAAP, k-SAAP, k-AAP, and RFT. The first one is an
improvement of the SAP. Instead of flooding the whole network, one can search for bids only among robots located up
DECEMBER 2010

Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - December 2010