10-06-2013, 03:44 PM
Distributed Bees Algorithm for Task Allocation in Swarm of Robots
Distributed Bees Algorithm.pdf (Size: 2.82 MB / Downloads: 22)
Abstract
In this paper, we propose the distributed bees
algorithm (DBA) for task allocation in a swarm of robots.
In the proposed scenario, task allocation consists in assigning
the robots to the found targets in a 2-D arena. The expected
distribution is obtained from the targets’ qualities that are
represented as scalar values. Decision-making mechanism is
distributed and robots autonomously choose their assignments
taking into account targets’ qualities and distances. We tested the
scalability of the proposed DBA algorithm in terms of number
of robots and number of targets. For that, the experiments
were performed in the simulator for various sets of parameters,
including number of robots, number of targets, and targets’
utilities. Control parameters inherent to DBA were tuned to test
how they affect the final robot distribution. The simulation results
show that by increasing the robot swarm size, the distribution
error decreased.
Introduction
IN applications that are too risky or too demanding for
humans, or where a fast response is crucial, multirobot
systems can play an important role thanks to their capability to
cover the area. Possible applications are planetary exploration,
urban search and rescue, monitoring, surveillance, cleaning,
maintenance, among others. In order to successfully perform
the tasks, robots require a high degree of autonomy and a good
level of cooperation. The set of robots should behave like a
team and not merely as a set of entities.
In scenarios that require area coverage, dozens, hundreds,
or even thousands of robots can be used. Such a large group of
robots, if organized in a centralized manner, could experience
information overflow that can lead to the overall system
failure. For this reason, the communication between the robots
can be realized through local interactions.
Related Work
Multirobot systems offer the possibility of enhanced task
performance, increased task reliability and decreased cost over
more traditional single-robot systems. However, multirobot
systems must be designed having these issues in mind. Research
field of multirobot systems is not new and various
architectures that differ in size and complexity have been proposed.
Dudek et al. [7] provided a taxonomy that categorizes
the existing multirobot systems along various axes, including
size (number of robots), team organization (e.g., centralized
versus distributed), communication topology (e.g., broadcast
versus unicast), and team composition (e.g., homogeneous
versus heterogeneous).
Rather than characterize architectures, Gerkey and Matari´c
[8] categorized instead the underlying coordination problems
with a focus on MRTA. They distinguish: single-task (ST)
and multitask (MT) robots, single-robot (SR) and multirobot
(MR) tasks, and instantaneous (IA) and time-extended (TA)
assignment. The authors showed that many MRTA problems
can be viewed as instances of well-studied optimization problems
in order to analyze the existing approaches, but also to
use the same theory in the synthesis of new approaches. In
order to estimate a robot’s performance, they defined utility
that depends on two factors, namely expected quality of task
execution and expected resource cost.
Distributed Task Allocation
Problem Definition
Based on the described taxonomy, our multirobot system
can be categorized as homogeneous and distributed, using
broadcast communication. We address a problem of singletask
robots, multirobot tasks and instantaneous assignment
(ST-MR-IA). The task allocation scenario we study considers
the environment that contains a number of tasks that could be
of same or different importance and robots that are equally
capable of performing each task but can only be assigned to
one at any given time. More specifically, the tasks are targets
with their associated qualities. The quality of a target is an
application-specific scalar value that may represent target’s
priority or complexity, where a higher value requires more
robots to be allocated. For example, it could represent the
richness of the mineral or water source on a planet that we
want to harness, the amount of garbage to be collected in a
public space, or the number of injured people in a need for
assistance in urban search and rescue scenario. In this paper,
we do not consider how these values are obtained.
Simulation Results and Discussion
In order to test the scalability of the proposed DBA with respect
to the size of the swarm, the experiments were performed
with 10, 20, 40, 60, and 100 robots for the experimental setup
1, and 20, 40, 60, and 100 robots for the experimental setup
2 and the experimental setup 3. The number of targets was
also changed, from two in the experimental setup 1 to four
in the experimental setup 2, in order to test the performance
of the algorithm with respect to the number of targets. In
the experimental setup 3, we used four targets with different
quality values to show the adaptability of the swarm to a
nonuniform distribution of the “food” in the environment. This
is also the most realistic scenario. Finally, the experimental
setup 4 was created to test how by changing the ratio of the
control parameters α and β we can affect the resulting robots’
distribution.
Conclusion
Various applications for large multirobot systems require
efficient task allocation in terms of individual and combined
robots’ utilities. The quality of the solution is analyzed using
a defined performance metrics, which in our case was a
mean absolute error of the resulting robots’ distribution with
respect to the qualities of the available targets in the robot
arena. In case of large, autonomous, multirobot systems, the
scalability and the ability to adapt to different environments are
the features of utmost importance. Our experiments through
simulation showed that the proposed DBA provides the robot
swarm with scalability in terms of the number of robots and
number of targets, but also with adaptability to a nonuniform
distribution of the targets’ qualities.