IEEE Robotics & Automation Magazine - December 2010 - 65

solution is that, theoretically, the optimal solution can be
found. However, the centralized solution features a high computation and communication overhead, lack of scalability, and
slow responsiveness. Moreover, the actual cost for communicating is ignored, especially for large robot networks. It is
further not clear how robots communicate if the graph is not a
complete one. Centralized solutions also have low fault tolerance if the leader is malfunctioning in any way.
Localized and distributed solutions utilize spreading all
decision making and planning responsibility among robots.
Here, we consider the multihop UDG scenarios, where the
communication graph is not complete. Robots only use the
locally available information to make their decision. Good
scalability and fault tolerance are the main advantages. Proposed solutions are normally close to the optimal one. However, decisions made based on the local information can
sometimes be highly suboptimal. We only identified one distributed solution designed for the multihop scenario, SAP [4],
which considers the multihop UDG model of robot communication. It is flooding based; each robot retransmits the
received search request exactly once and responds to the
auctioneer by a separate routing task. For large robot networks, it incurs an unacceptable delay in selecting the best
robot, although the best responding robot is expected to be
near the event.
In this article, we first propose to limit the robot selection
to a certain local neighborhood, even for SAP. We then propose a localized solution, based on the market paradigm, called
AAP. The bidding process is spreading to neighboring robots
until no improvement can be envisioned within a k-hop
neighborhood of a robot that analyzes if any more remote
robots could provide better a service than the best service it is
already aware of. If not, it stops the search process and responds
back to its parent robot with the best possible recommendation it has. During the contraction process of bid gathering,
best bids are forwarded back to the auctioneer robot by intermediate robots. The main advantage is that the search is
limited to some neighborhood and flooding potentially huge
robot network is avoided. When the best robot is selected
based solely on its distance to the event, the search can be very
efficient by simply routing toward the event location, with the
traversal of the face of Gabriel graph containing the event discovering the nearest robot (RFT-routing with face traversal
algorithm). Simulation data confirm findings and show the
performance of our protocol in some scenarios.

Literature Review
Multirobot Task Assignment
Taxonomy of multirobot task allocation (MRTA) problems is
presented in [5]. In most of the papers, the task assignment
problem is formulated as a variant of the integer linear
programming problem (e.g., [4] and [6]). Mobility is usually not
considered (an exception is [6]). In those centralized formulations, the optimization objective is any of energy consumption
minimization, maximization of processing time, utility maximization, total travel distance minimization, or residual energy
DECEMBER 2010

Normally, messages originate
from and converge toward
the robot decision maker.
maximization. Although these centralized solutions can be
formulated to target our scenario (single event), they either
ignore communication cost or assume a complete graph.
The communication aspects of task assignment are rarely
taken into account. In centralized MRTA [7], communication
aspects are modeled by including one term in the optimization objective function, which represents the number of robot
pairs that can communicate (and that should be maximized).
The communication protocol is not specified and only singlehop (direct) communication is considered. In [8], robots are
likely to win tasks that have a low cost for themselves but a
high average cost for the rest of the team. When there is only
one task to assign, the closest robot is selected. This article
does not discuss any communication protocol among sensors
or robots. Thus, the complete graph is assumed in the coordination process.
A communication-efficient multirobot (CEMR) task
scheduling algorithm for heterogeneous MRS is given in [9].
CEMR assumes direct communication between each robot
and a central unit, and direct communication among some
robot pairs. Each robot reports its status and detected tasks to a
central unit, which allocates tasks using an auction-based
method with a fitness function (including capability, distance
from task, and availability). Robots receive the status, including the position, of all other robots from the central unit and
can also ask directly for help from other nearby robots. The
article does not discuss any multihop communication protocols. A simulation is made with six robots, and the alternative
approach is broadcasting, which is a direct request to all other
robots instead of to a few of them who might be available
based on a priori knowledge.
Three decentralized task allocation schemes among unmanned aerial vehicles (UAVs) in a destroy targets scenario
using negotiation concepts from team theory and game theory
are given in [10]. It is acknowledged that full communication
between all UAVs poses high communication costs, and the
idea of localized communication (communication among
neighbors only) is given as well as the necessity for multihop
communication if agents are out of the communication range.
However, only a complete graph is simulated. Multihop communication was stated in some scenarios, but there is no
discussion of any communication protocol actually applied.
In summary, finding solutions to concrete task assignment
scenarios in the presence of robot mobility (when communication cost is not negligible, and communication protocols
need to be specified) still remains a research challenge.
Market-Based Task Assignment and Auctions
For robot-robot coordination, a market-based approach [11]
is considered. It is based on auctions organized by a robot or
IEEE Robotics & Automation Magazine

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