=Paper=
{{Paper
|id=Vol-1949/ICTCSpaper07
|storemode=property
|title= Multi-robot Task Allocation Problem: Current Trends and New Ideas
|pdfUrl=https://ceur-ws.org/Vol-1949/ICTCSpaper07.pdf
|volume=Vol-1949
|authors=Mattia D'emidio,Imran Khan
|dblpUrl=https://dblp.org/rec/conf/ictcs/DEmidioK17
}}
== Multi-robot Task Allocation Problem: Current Trends and New Ideas==
https://ceur-ws.org/Vol-1949/ICTCSpaper07.pdf
Multi-robot task allocation problem: current
trends and new ideas
Mattia D’Emidio1 , Imran Khan1
Gran Sasso Science Institute (GSSI)
Via F. Crispi, 7, I–67100, L’Aquila (Italy)
{mattia.demidio,imran.khan}@gssi.it
Abstract. The use of robotic fleets, a.k.a. multi-robot computing sys-
tems, is a de–facto standard in a variety of real-world applications. Effi-
ciently solving the multi-robot task allocation (mrta) problem is perhaps
one of the most fundamental feature of such systems. In this paper,
we attempt at overviewing recent research on the matter. In particu-
lar, we first briefly survey some of the most interesting results of the
last decade. Then, we focus on a prominent variant, namely the single-
task single-robot task allocation problem with hard temporal constraints
(st-sr-hc, in short), and on auction-based algorithms, which have been
shown to be rather effective solutions in the st-sr-hc setting. To this
regard, we discuss the state-of-the-art and highlight some ideas we are
currently exploring to improve the best algorithm of the category, i.e.
tessi. We provide preliminary experimental evidences of how such ideas
seem to lead to better balancing number of performed tasks, distance and
makespan optimization objectives.
1 Introduction
The use of robotic fleets is becoming increasingly compelling for many reasons.
Chiefly, there has been a significant decrease in the cost of robotic devices (e.g.
drones or ground robots), while at the same time hardware continues to improve.
This makes so–called multi-robot computing systems (mrs) a pertinent option
for many applications of critical practical importance as, e.g., exploration of
hazardous zones or rescue of people in emergency contexts. In this context,
many different problems/scenarios have been studied. Robots might be asked to
form desired geometric patterns [8], to explore unknown zones [2]. They can be
constrained to move on an Euclidean plane [1], or on a graph [4, 6], which can be
either known in advance or not [3]. They can be equipped with different kinds
of hardware [7], and be able to act synchronously or not [5].
One of the major thread of research in the mentioned area, due to its high in-
dustrial and academic relevance, is that regarding the multi-robot task allocation
(mrta) problem, i.e. the problem of partitioning tasks (to be performed) across
robots such that some objective of interest is optimized [11]. Unfortunately, even
the basic version of the problem, where, given a set R of robots, and a set T
of tasks, one wants to find an assignment of the tasks in T to the robots in R
such that the total time for completing all the tasks (i.e. the makespan) is mini-
mized, is NP–Hard [11] For this reason, a plethora of alternative approaches have
been proposed over the years, ranging from polynomial time approximation al-
gorithms to techniques that chase good solutions via heuristics with no provable
guarantees. The situation is even more complicated, algorithmically speaking,
when it comes to incorporate further practically relevant aspects (e.g. prece-
dence constraints). Nonetheless, a countless number of variants of the general
mrta problem have been defined and investigated in last decade.
In this paper, we attempt at overviewing the results of such investigation. In
particular, we first briefly survey some of the most interesting works on special-
izations of the mrta problem (Section 2). Then, we focus on a prominent variant,
namely the single-task single-robot task allocation problem with hard temporal
constraints (st-sr-hc, in short), and on auction-based algorithms, which have
been shown to be rather effective solutions w.r.t. the st-sr-hc setting [11] (Sec-
tion 3). To this regard, we discuss the state-of-the-art and highlight some ideas
we are currently exploring to improve the best algorithm of the category, i.e.
tessi. We provide preliminary experimental evidences of how such ideas seem
to lead to better balancing number of performed tasks, distance and makespan
optimization objectives (Section 4).
2 Variants of the mrta problem
In the robotic field, the mrta problem is always considered in the realistic setting
where both robots and tasks are spread within a physical environment [11]. In
this case, time for moving robots where the tasks have to be performed needs to
be considered and, possibly, optimized. Other main flavors of the problem are
mostly due to the variance in: i) abilities of robots; ii) nature of tasks; iii) system
goals; iv) computational paradigm. In what follows, we briefly summarize the
most commonly considered distinctions w.r.t. these four directions.
Regarding i), the broadest classification concerns the amount of tasks that
can be executed by a robot at a time. In particular, a robot can either perform
at most one task at a time (single-task robot setting, or st) or more than one
task at a time (multi-task robot setting, or mt) [11]. Moreover, sometimes robots
can have an upper bound on the maximum allowed operational time [9, 12].
Concerning ii), symmetrically w.r.t. i), the main distinction is usually due to
the number of robots that are required to execute a task, i.e. a task can either
be accomplished by a single robot (a.k.a. single-robot task setting, or sr) or
require more than one robot (multi-robot task setting, or mr) [11]. Secondary
classifications are induced by domain-related constraints on when or how tasks
must be completed, i.e. temporal and ordering constraints [11]. On the one hand,
temporal constraints require a task to be executed within a specific time window,
i.e. a time interval that implicitly imposes a latest starting time and a deadline
within which the task must be completed. In more details, deadlines can be hard
(hc setting) or soft (sc setting) where in the hc (sc, resp.) case the execution
of the task outside the corresponding time window is not allowed (allowed by
a predefined fixed amount, resp.) [11]. On the other hand, ordering constraints
restrict the execution of some tasks to be dependent on the completion of some
other tasks (a.k.a, precedence constraints) [11].
Regarding iii), the main difference is induced by the number of objective
functions to be optimized (single vs multi-objective) [11]. Commonly adopted
optimization goals in the area are temporal objectives (e.g., makespan or tar-
diness [9]), spatial objectives (e.g. distance traveled [10]), cardinality of the re-
quired robots (e.g. minimizing number of used robots [11]).
Finally, concerning iv), as in many other optimization problems, heavy differ-
ences in the problem are induced by the possibility of having a central coordinat-
ing entity (centralized setting) or not (decentralized setting). In the former case,
there is a robot or a ground station responsible for allocating tasks, while in the
latter the computation is distributed to the robotic fleet itself. Centralized com-
putation offers the typical benefits of better optimizing efforts, resources, cost
and time, since the central entity has complete environment awareness.However,
it suffers from both the well-known drawbacks, e.g. single point of failure. Dis-
tributed approaches are often preferred since, despite they require more complex
coordination strategies, they achieve higher reliability and scalability [9].
3 The st-sr-hc problem
In this section, we focus on the st-sr-hc problem, which can be defined as
follows. We are given a set of n st robots and a set of m sr tasks whose time
window is of type hc, with n < m. Each robot has an associated budget in terms
of operational time and both tasks and robots are embedded in a 2D plane, i.e.
they have an associated set of coordinates. The objective is to assign the largest
amount of tasks to robots such that: i) temporal constraints are satisfied; ii)
makespan and distance covered by the robots are minimized.
Of the wide variety of approaches addressing the different variants of mrta
problem, only a handful of them deal with the st-sr-hc setting. Among these,
auction-based algorithms enjoyed a wide range of popularity [11]. Auction-based
algorithms are market inspired and their behavior can be summarized as follows.
The computation takes place in rounds and each round consists of two phases:
an announcement phase and a selection phase. During the announcement, a set
of available tasks T is broadcasted to be ready for execution to all robots, by a
so–called auctioneer which is assumed to become aware of T by monitoring the
environment. Then, each robot computes a so–called bid for each available task
which is transmitted to the auctioneer. The bid is basically a number, computed
by a robot by considering both constraints and system goals, i.e. the impact that
allocating a task to the robot has on the considered objectives. Bids are then
collected by the auctioneer and processed to select the so-called winning bidder
(robots are often referred to as bidders here), according to some optimization
criteria, e.g. by choosing the one who has sent the bid of minimum value. Finally,
the auctioneer sends a message to the winning robot to confirm the allocation of
the corresponding task. The robot accordingly adds the task to its schedule, i.e.
a data structure storing assigned tasks along with their temporal information.
Some of the most relevant algorithms of the area are of single sequential
item auction (ssi) type (they allow bidding on a single task at the time [9]).
They are usually preferred over other approaches (e.g. combinatorial auction
solutions [12]) since they are more parsimonious w.r.t. communication and com-
putational resources, therefore suited to be used in mrs where robots are less
powerful in this sense. The state-of-the-art ssi algorithm is tessi, which has
been shown to outperform previous methods in producing quality solutions w.r.t.
number of allocated tasks, makespan and distance objectives [10].
4 Beyond tessi
tessi requires a robot to check the internal consistency of the current schedule
whenever a bid needs to be placed, where a schedule is said to be consistent if all
tasks can be performed without violating any temporal constraint [10]. To this
aim, each schedule is stored in a suited data structure, called stn, whose space
complexity is linear in the number k of tasks currently associated to the schedule,
and each of the above consistency checks take O(k 3 ) time, which is clearly not
practical whenever k is large [10]. To overcome this limit, we are investigating
the possibility of devising an enhanced version of the stn that, by storing some
additional data, can allow faster consistency tests. In particular, by exploiting
some properties of the st-sr settings (e.g. the stn, stored locally on each st
robot, cannot have two or more events, i.e. tasks, occurring in parallel to each
other), so far we are able to show that consistency checking can be done in O(k)
time at the price of an extra O(k) of space (which asymptotically does not affect
the space requirements of the original stn). Furthermore, we are also studying
how to better optimize the distance objective by modifying the criterion used
by tessi for placing bids. The intuition here is to weight “more” the distance
traveled by a robot in such criterion. More details on the above modifications
will be provided in an extended version of this paper.
To assess the effectiveness of this enhanced version (called etessi) against
tessi, we carried out a preliminary experimental evaluation. We considered both
real-world and synthetic inputs and various settings. Our results (Fig. 1) suggest
etessi to be computationally more parsimonious than conventional tessi (as
theoretically expected), while at the same time being slightly better w.r.t number
ETESSI TESSI ETESSI TESSI
TESSI 1.06 1.10
3.5 ETESSI
1.04
3.0 1.05
Ratio ETESSI / TESSI
Ratio ETESSI / TESSI
Time (Seconds)
2.5 1.02
1.00
2.0 1.00
0.95
1.5 0.98
0.90
1.0
0.96
0.85
0.5
0.94
1000-60
1200-60
1400-60
400-40
500-40
500-50
600-50
800-60
1000-60
1200-60
1400-60
400-40
500-40
500-50
600-50
800-60
0.0
20 40 60 80 100 120
Number of Tasks # of tasks - # of Robots # of tasks - # of Robots
Fig. 1: Results of the experimental evaluation of etessi against tessi: (left)
CPU Time, (middle) number of tasks scheduled by etessi over number of tasks
scheduled by tessi, (right) maximum distance travelled by robots using etessi
over maximum distance travelled by robots using tessi.
of scheduled tasks and distance objectives, with a similar makespan (results w.r.t.
latter omitted due to space limitations). To extend our work, we are planning
to: i) expand the theoretical foundations of etessi and improve its performance;
ii) consider other settings, e.g. sc or dynamic settings where rescheduling tasks
is allowed; iii) enlarge our experimental evaluation.
Bibliography
[1] S. Das, P. Flocchini, G. Prencipe, N. Santoro, and M. Yamashita. The
power of lights: Synchronizing asynchronous robots using visible bits. In
Proc. of 32nd IEEE International Conference on Distributed Computing
Systems (ICDCS), pages 506–515, 2012.
[2] M. D’Emidio, D. Frigioni, and A. Navarra. Exploring and making safe
dangerous networks using mobile entities. In Proc. of 12th International
Conference on Ad Hoc Networks and Wireless (ADHOC-NOW), volume
7960 of Lecture Notes in Computer Science, pages 136–147. Springer, 2013.
[3] M. D’Emidio, D. Frigioni, and A. Navarra. Explore and repair graphs with
black holes using mobile entities. Theor. Comput. Sci., 605:129–145, 2015.
[4] M. D’Emidio, D. Frigioni, and A. Navarra. Characterizing the computa-
tional power of anonymous mobile robots. In Proc. of 36th IEEE Interna-
tional Conference on Distributed Computing Systems (ICDCS), pages 293–
302, 2016.
[5] M. D’Emidio, D. Frigioni, and A. Navarra. Synchronous robots vs asyn-
chronous lights-enhanced robots on graphs. In Proc. of 17th Italian Confer-
ence on Theoretical Computer Science (ICTCS), volume 322 of Electronic
Notes in Theoretical Computer Science, pages 169–180. Elsevier, 2016.
[6] M. D’Emidio, G. D. Stefano, D. Frigioni, and A. Navarra. Improved proto-
cols for luminous asynchronous robots. In ICTCS, volume 1720 of CEUR
Workshop Proceedings, pages 136–148. CEUR-WS.org, 2016.
[7] P. Flocchini, D. Ilcinkas, A. Pelc, and N. Santoro. Computing without
communicating: Ring exploration by asynchronous oblivious robots. Algo-
rithmica, 65(3):562–583, 2013.
[8] N. Fujinaga, Y. Yamauchi, H. Ono, S. Kijima, and M. Yamashita. Pat-
tern formation by oblivious asynchronous mobile robots. SIAM Journal on
Computing, 44(3):740–785, 2015.
[9] L. Luo, N. Chakraborty, and K. Sycara. Distributed algorithms for multi-
robot task assignment with task deadline constraints. IEEE Transactions
on Automation Science and Engineering, 12(3):876–888, 2015.
[10] E. Nunes and M. L. Gini. Multi-robot auctions for allocation of tasks
with temporal constraints. In Proc. of 29th AAAI conference on aritifical
intelligence, pages 2110–2116, 2015.
[11] E. Nunes, M. Manner, H. Mitiche, and M. Gini. A taxonomy for task
allocation problems with temporal and ordering constraints. Robotics and
Autonomous Systems, 90:55–70, 2017.
[12] W. Zhao, Q. Meng, and P. W. Chung. A heuristic distributed task allocation
method for multivehicle multitask problems and its application to search
and rescue scenario. IEEE transactions on cybernetics, 46(4):902–915, 2016.