=Paper=
{{Paper
|id=None
|storemode=property
|title=A Context Aware Multi-robot Coordination System Based on Agent Technology
|pdfUrl=https://ceur-ws.org/Vol-621/paper24.pdf
|volume=Vol-621
|dblpUrl=https://dblp.org/rec/conf/woa/GrossoABC10
}}
==A Context Aware Multi-robot Coordination System Based on Agent Technology==
https://ceur-ws.org/Vol-621/paper24.pdf
A Context Aware Multi-robot Coordination System
based on Agent technology
Alberto Grosso, Davide Anghinolfi, Antonio Boccalatte, and Giorgio Cannata
DIST
University of Genova
Genova, Italy
alberto.grosso@unige.it
Abstract—This paper presents an approach for multi-robot • to drive the swarm through the environment: the tags
coordination based both on coordinated navigation and task make it a smart area;
allocation method. An ad hoc agent based architecture is defined
in order to implement the robot control system in both simulation • to allow local communication;
and real applications. The coordination of the multi-robot system
is based on agent interaction and negotiation, and a
• to provide the infrastructure for constituting context
communication infrastructure based on open web standards is aware knowledge.
provided. The system employs the RFID technology for building The proposed system is based on both a coordination
a context aware information system which is the base of the control algorithm and a distributed task allocation method: as
coordination strategies. mentioned above, both methods rely on RFID technology and
exploit context aware information for navigation and task
Multi-Robot Systems; Multi-Agent System; Distributed
execution aims. An ad hoc agent-based architecture is defined
Interactive Systems; Multi-Robot Task Allocation.
for implementing the robot control system. AgentService [14]
I. INTRODUCTION is adopted for abstracting hardware level and making the
developed software work both in simulation and in real
The general objective of this work is to develop an open application, a previous implementation of the architecture was
knowledge environment for self-configurable, low-cost and based on Player/Stage tool [19] and detailed in [20].
robust robot swarms usable in everyday applications. Advances
in the state-of-the art of networked robotics are proposed In next paragraphs, the state of the art in applying RFID
through introduction of a local and global knowledge base for technology and task allocation methods to multi-robot systems
ad hoc communication within a low-cost swarm of autonomous is briefly analyzed. Section 2 illustrates a novel approach for
robots operating in the surrounding smart IT infrastructure. robot team coordination that could be applied in different
application contexts; in addition we present the agent-based
The work will address the development of flexible, cost- architecture implemented for applying the coordination
effective, dependable, and user driven robot swarm, which methods in robot applications. Conclusions are given in
possesses a higher intelligence collectively than each member Section 3.
of the swarm independently. In particular, this paper involves
self-organizing task-sharing mechanisms between individual A. Exploiting RFID technology in the field of multi-robot
members of the swarm to capitalize on the availability of a system
large number of simple and cost-efficient robots. Reuse of the RFID tags have attracted great attention as a key device in
local and global level knowledge is pursued by creating on-site various domains, from object tracking to robotics. As a result,
(near to objects of interest) distributed data environment. the deployment of RFID technology on a larger scale is about
System is kept scalable and manageable by decentralization of to become both technically and economically feasible [6].
control and manipulation to local level.
Focusing on mobile robotics applications, attached to walls,
In this work RFID tags [4, 5] are used for deploying machines, or other specific places in the environment, RFID
information through the environment that is used for applying tags works as dedicated landmarks making the robot able to
distributed coordination strategies. It is assumed that RFIDs are detect items, obtain information about its position, and even get
distributed in the environment prior to robot operation, and instructions to reach a given goal [5]. Considering the analysis
used to build a sort of “navigation graph”: each RFIDs contains of the state-of-the-art, different aspects are investigated in
navigation directions to neighboring RFIDs, thus allowing literature obtaining different level of success. The main topics
robots to safely execute paths from and to different locations. considered by researchers in applying RFID technology to
We decide to exploit the localized information tagged on robotics are: localization, coordination, exploration, and object
RFIDs at different levels: recognition [1, 7, 18]. The basic idea of such approaches is to
employ the wireless sensor network, provided by RFID in [15]. Each robot of the swarm performs the coordinated
technology, as a way to coordinate teams of robotic agents and coverage algorithm as default task but, if required, different
human by employing its ad-hoc communication capability in application oriented tasks (e. g. find objects, collect items, etc.)
addition to its sensing. Moreover, novel approaches are based can be assigned to it through a distributed and robust allocation
on the concept of stigmergy: a swarm of agents can coordinate mechanism described below. We integrate these behaviors in a
its components' behavior by modifying the environment [8, 9]. high level robot control architecture implemented with agent
based technology and presented in section C.
B. Multi-robot Task Allocation Algorithms
Sharing the task related workload among robots through a B. Task Allocation System
task allocation mechanism is an effective way for making a In order to assign tasks to robots in an effective way, a
team of robots act in a coordinated way. A task can be distributed task allocation mechanism is defined. One of the
decomposed into sub-tasks and an assignment process can be goals of the defined methods is to be able to adapt both
adopted in order to allocate tasks among the team. Different environment changes (e. g. addition of new environment areas)
approaches are proposed in literature for solving the task and robots’ team changes (e. g. robot failures). Finally the
allocation problem starting from classical operational research allocation mechanism has to be robust enough for working in
algorithms to social behaviors inspired by human society or critical scenarios like rescuing where broadcast communication
swarm organization. may be not available. In the multi-robot system a central server
is considered in order to interoperate with external software
One of the most diffused and adopted mechanism for task applications and to provide services to robots. The main phases
allocation are auctioning systems [10]. They naturally form a of the auction algorithm can be summarized as follows:
distributed framework, and offer a good way of sharing
information between agents/robots. The basic idea behind a 1. The central server acquires tasks to be executed by the
market-based task-allocation mechanism is to assign tasks via robot team, new tasks can emerge as results of user requests or
an auction, where agents/robots bid a value in a shared automatically generated by a reasoning system.
currency based on their perceived fitness for a task [10]. Tasks
are awarded to the lowest bidder if the goal is minimizing cost, 2. The central server analyzes the task definitions and
or to the highest bidder if the goal is to maximize reward. One decides how many robots should be assigned to each specific
first work is M+ [11] but a lot of studies are presented, papers task but do not explicit identify them.
in [12, 13] illustrate some interesting results. 3. Then the robots should be informed about the new
tasks to be assigned and the number of robots required.
II. THE CONTEXT AWARE MULTI-ROBOT COORDINATION
SYSTEM 4. The assignment is the result of a negotiation that each
robot leads by itself.
A. The Context Aware Multi-robot Coordination System
These last two points have to be investigated in order to
Cooperative robotics is one of the hottest topics in current
make the proposed task allocation system adaptive and robust.
research, as shown by the growing number of articles published
every year. There are two main ways of achieving coordinated
multi-robot behaviors: making the single robot control Service Zone B
processes work coordinated; orchestrating single robot Room
behaviors by allocating properly the tasks to be accomplished. S
The former approach operates by defining robot control
architecture based on algorithms which take into account the
behaviors of other robots belonging to the team. In the latter,
robots compete or cooperate for acquiring tasks, or a central Zone A
system allocates the tasks optimizing some parameters; after Hot Spot Zone C
that, each robot performs the assigned tasks as a single system. Node
Zone Graph
We think that the two approaches are complementary and Topological Graph
can be applied together in order to obtain a whole coordinated
Figure 1. – The graph based model of the
behavior of the robot swarm. We selected for our multi-robot
application a classical problem that can be applied in different environment.
context. A traditional problem in multi-robot system is to As previously mentioned, the environment is modeled
repeatedly visiting a set of specific locations, a variant of the through a graph. For task allocation purpose, it is also divided
dynamic coverage problem (see [1] and the reference within) in zones and for each zone an hot spot is defined. The hot spot
which is particularly relevant for surveillance and patrolling, is a local memory (e. g. a cluster of RFID tags - in order to
and – to some extent – for repeatedly cleaning crowded areas. record a larger amount of data) containing information relevant
In addition to this general problem, we choose to add the for that zone: blackboard for robots indirect communication (e.
possibility to assign to the robots’ team context specific tasks g. task allocation messages), robots log (each robot logs in/out
such as guard a specific area, clean a zone, etc. entering/leaving the zone), additional relevant task oriented
information. At least a Service Room is foreseen within the
We propose a coordination system in which the coverage environment: this is a special zone in which robots can
problem is solved with a real time search algorithm presented
recharge their batteries and the communication with the server couriers and the zone hotspots as mailboxes. The couriers
system is ensured. collect auction data from the server, within the service room,
and deliver CFT to the hotspots. All the robots can play the role
Each application oriented task consists in performing some of message courier: they can get CFT information from the
specific actions in a defined area; it is modeled by the server when they go to the Service Room for recharging their
following properties: Priority, Deadline, Required capabilities, battery and then they became able to deliver the CFT to the
and Revenue credits. The priority is critical for scheduling the target hot spots while coming back to the working zones.
task while the deadline defines the time within the task has to Hence, in the messenger scenario the server communicates to
be completed. In order to effectively perform each task specific robots in the service room the new CFTs along with the
robot capabilities are required: this is a relevant point when hotspots where to deliver them and these robots deliver the
considering a team of heterogeneous robots. CFTs to hotspots playing the role of messengers. Once the
Once a task is concluded, it determinates an amount of CFTs are published into the hotspots, robots periodically visit
virtual credits that is assigned to the robot as revenue for the hotspot of the area in which they are working. Periodically
completing the task; this is a focal aspect of the bidding means that they visit the hotspot when they terminate the
mechanisms. The “Call For Task”, CFT, represents the “call” execution of a task or at fixed interval (polling strategy); the
promoted by the Server System, which play the role of interval may vary in function of the priority of task already
Auctioneer. It mainly contains the task and the auction assigned to that robot. If a robot is interested in a CFT, it starts
information, in particular the auction deadline: the time within the negotiation process by leaving its bid for task on the
robots can send a valid bid to acquire the task. hotspot blackboard. At the deadline indicated into the CFT,
each robot involved in the negotiation process checks the
The basic steps of the auctioning process are: auction result (best offer) in the hotspot, hence the winner auto-
• while performing assigned tasks, robots look for new allocates the task in its schedule. The Server System will be
CFT; informed on task allocation (auction results) when robots come
back to the service room collecting runtime information. If a
• when a robot gets informed about a new task, it CFT doesn’t receive offers, the Server System can decide to
evaluates the acquisition of the new task taking into reschedule the involved task in a new one.
account: task required capabilities, already assigned
tasks, task priority compared with the already C. Robot Control Architecture
scheduled task, and deadline; The robot control architecture is described in the following
schema. The proposal is based on the result achieved in the
• and then the robot decides to start a negotiation Roboswarm project [2], funded by European Community in the
process. Sixth Framework Programme.
The negotiation process is based on a first-price auction:
• each robot, able and interested in performing the task,
makes its offer specifying an amount of credits
according to its state (task already assigned/performed,
battery charge, ..);
• at the expiration of the auction time-out, indicated
within the CFT, the task is assigned to the robot that
made the highest offer;
• when a robot successfully terminates a task an amount
of credit is assigned to it; a Revenue function
determines the credit amount considering task revenue
credits, priority, task deadline, and completed time.
As mentioned above, in order to work in real scenarios the
auction mechanism could not rely completely on the robot
communication infrastructure. Two scenarios are considered:
with broadcast communication and with local/indirect
communication. In the first case the Server System manages
and drives the auction with direct server-robots communication
that is used for publishing the CFT and collecting the robot
offers, this scenario is the most effective considering
performance and scalability factors. In the latter scenario, we Figure 2. – Robot Control Architecture
assume that no Wi-Fi communication is possible and only
indirect communication through RFID is available, a
mechanism for delivering the CFT to the robots deployed We adopt the agent paradigm for modeling the single robot
within the environment is required. In order to solve this control architecture and the whole multi-robot systems. The
problem, the proposed idea is to exploit the robots as message architecture involves a dedicated multi-agent system; different
kinds of agents can be defined in order to solve/execute D. Multi-Robot System Architecture
specific problems/actions. A reactive agent, Main Control Considering inter-robots communication, in the scenario in
Agent works as the central control process and it can activate which the WiFi infrastructure is available, it is important to
reactive behaviors. It executes the real time coordination follow software standards in order to be able to interoperate
algorithm and schedule the application oriented task if with different system/technology and to improve system
requested. We introduce two other reactive agents: Sensor maintenance making the Multi Robot System open. The
Agent and Actuator Agent. The Sensor Agent is in charge of concepts introduced with the Service Oriented Architecture
reading input data from sensors and writes them in a shared [16] along with the standardization of XML Web Service
buffer. Actuator Agent reads robot commands and passes them (SOAP, WSDL, UDDI) lead to the adoption of these standards.
to robots’ hardware. Reactive agents have to be scheduled as
high priority tasks in order to guarantee predictable behavior For inter-robot communication, the proposal is that the
and safety in performing motion. software agents inside the robot can send data to other robots
(agent deployed on) or to the system through the ACC and the
The Broker Agent negotiates with other robots and, Service Access Layer.
according with the Supervisor (Planner) Agent, models robot
tasks that the Main Control Agent will perform. Its behaviors
implement the bidding mechanisms. The Rule Engine performs
elaboration on robot knowledge [17], dealing with learning
activities out of the scope of this paper.
All the agents, implemented as an AgentService solution,
could be deployed on board (a dedicated mobile device in our
tests), or some of them, the upper level agents (Broker and
Planner), can be distributed on server side. Following the
AgentService scheduling model, a correspondence agent-thread
is adopted within mobile device while a more solutions are
available on server side.
A dedicated agent communication channel (ACC) is
defined in order to make agents, and other on-board software
artifacts interact. Moreover, the ACC manages the inter-robot
communication using open standard technologies for sending
data to other robots. Hence an agent, deployed inside the robot,
is able to send asynchronous messages to other agents with no Figure 3. – Robot Layered Architecture
care about the place where receivers are deployed: the ACC
performs the right action for us. According to the operational
scenario, the communication service could be degraded in In addition, each robot may promote its activities through a
indirect robot communication through RFID tags when WiFi dedicated Web Service (Robot Web Service) placed on the
communication is absent. highest and external layer of the robot architecture (server-
side).The Multi-Robot Server System can provide services to
The agent-robot interaction is modeled through a robots and should be able to orchestrate external services too.
programming interface which invokes a specific low level In this way everything is a service or is wrapped by a service.
Application Programming Interface (API) modeled by the Communication between the Robot Web Service and the
Robot Interaction Layer. The Robot Interaction Layer abstracts onboard software layer is based on standard SOAP messages
the interaction with the software components which act on the ensuring easy integration with different software system and, if
hardware. By means of this level of abstraction, agent required, semantic expression of the communication acts.
behaviors are not strongly coupled with the hardware level
increasing their reuse and portability. Even this software level III. FINAL CONDIDERATIONS AND CONCLUSIONS
is implemented with AgentService [14]. The Robot Interaction This paper presents a coordination system for swarm of
Layer works in two ways: emulating the robots behaviors in a robots based on agent technology. As demonstrated in
virtual 2D environment, directly sending commands and literature, the exploitation of RFIDs for getting context aware
receiving sensors data from the robots. Considering the last information system is providing good results. Two approaches
mechanism, a couple of IRobot Roomba platforms equipped for making teams of robots work cooperative are considered.
with RFID readers and Bluetooth adapters are used for real The objective of task allocation is to find the best distribution
experiments while an instance of AgentService platform has of the tasks and sub-tasks among the robots belonging to a
been deployed on a mobile device based on Windows Mobile team. As previously discussed, this problem is widely applied
and .NET Compact Framework. Hence, the system can be in different application context and the researchers in the field
configured to work both in simulation and in real robot of multi-robot system coordination exploits the works
hardware context in a transparent way from the point of view previously done in the field of multi-agent systems, as we have
of client applications. seen for the market-based approaches. On the other hand
control coordination algorithms try to make robots behaviors
cooperative by directly controlling the actions of each robots;
this approach is closely related to specific tasks the team of [4] V.A. Ziparo, A. Kleiner, B. Nebel, and D. Nardi. RFID-Based
robots have to solve. We can state that task allocation operates Exploration for Large Robot Teams, Proc. of the IEEE Int. Conf. on
Robotics and Automation, 2007, pp. 4606-4613.
at an higher level than coordination control algorithms: the
[5] D. Hahnel, W. Burgard, D. Fox, K. Fishkin, and M. Philipose, Mapping
former improves the teams’ work by assigning, and in some and localization with RFID technology, Proc. IEEE Int. Conf on
cases dynamically re-allocating, tasks to robots and the latter Robotics and Automation, vol. 1, 2004.
coordinates robots’ actions while they are executing the [6] J. Bohn and F. Mattern, Super-distributed rfid tag infrastructures, Proc.
assigned task. Hence, it seems clear that the two coordination of the 2nd European Symposium on Ambient Intelligence, 2004.
techniques are complementary aspects of the same [7] A. Milella, P. Vanadia, G. Cicirelli, and A. Distante, RFID-Based
coordination process and can be applied together in order to Environment Mapping for Autonomous Mobile Robot Applications,
improve the effectiveness of the multi-robot systems behaviors. International conference on Advanced intelligent mechatronics, 2007.
[8] G. Roussos, D. Papadogkonas, J. Taylor, D. Airantzis, M. Levene, and
The proposed coordination strategy is based on context M. Zoumboulakis, Shared Memories: A Trail-based Coordination Server
aware information deployed within RFID tags distributed in the for Robot Teams, First International Conference on Robot
environment and does not rely on an internal robot Communication and Coordination, Athens, Greece, 2007.
representation of the system. This information infrastructure is [9] J. Werfel and R. Nagpal, Extended Stigmergy in Collective
used to drive the control behavior of each robot and to Construction, IEEE Intelligent Systems 21(2), 2006.
distribute tasks among the team. Furthermore, the proposed [10] M. B. Dias, R. Zlot, N. Kalra, and A. Stentz, Market-based multirobot
coordination: A survey and analysis. Proc. of the IEEE – Special Issue
system is robust against environment changes and do not on Multi-Robot Coordination, 2006.
require direct robot-robot communication: the model of the [11] S. C.Botelho, and R. Alami, M+: a scheme for multi-robot cooperation
environment is distributed with the tags and robots can through negotiated task allocation and achievement, Proc. of the IEEE
communicate using the tags as mailboxes. The system has been Intl. Conf. on Robotics and Automation, Michigan, 1999.
implemented through an ad hoc agent control architecture [12] M. B., Dias and A. Stentz, Opportunistic Optimization for Market-
which provides modularity and scalability. It has been Based Multirobot Control. Proceedings of the IEEE/RSJ International
extensively tested in the AgentService environment both in Conference on Intelligent Robots and Systems IROS 2002, 2002.
simulation and on real robots. The test case scenarios involve [13] R. Zlot and A. Stentz, Complex Task Allocation For Multiple Robots,
Proc. of IEEE Int. Conf. on Robotics and Automation, Barcellona,
two main phases: team navigation and coverage of the Spain, 2005.
environment with indirect coordination exploiting RFID
[14] C. Vecchiola, A. Grosso, A. Boccalatte; AgentService: a framework to
context information; task composition and allocation based on develop distributed multi-agent systems, Int. J. Agent-Oriented Software
the distributed auction mechanisms. The tests state the Engineering, Vol. 2, No.3 pp. 290 – 323, 2008.
feasibility of the agent architecture and the effectiveness of the [15] M. Baglietto, G. Cannata, F. Capezio, A. Grosso, A. Sgorbissa, R.
integrated coordination approach. The multi-robot architecture Zaccaria, PatrolGRAPH: a Distributed Algorithm for Multi-Robot
exploits the abstraction and the cooperative aspects of the agent Patrolling, The 10th International Conference on Intelligent
paradigm. It can be noticed the adoption of a communication Autonomous Systems, Germany, 2008.
channel transparent for agents which can exchange messages [16] T. Erl, SOA Principles of Service Design, The Prentice Hall Service-
Oriented Computing Series from Thomas Erl, 2007.
with peers with no care on where receivers are deployed. A
[17] Vain, J.; Tammet, T.; Kuusik, A.; Juurik, S. (2008). Towards scalable
service oriented approach is proposed for exposing and proofs of robot swarm dependability. In: BEC 2008 : 2008 International
promoting the robot team services and easily integrating the Biennial Baltic Electronics Conference : Proceedings: 11th Biennial
system with external software components. Baltic Electronics Conference, Tallinn University of Technology,
October 6-8, 2008, Tallinn, Estonia. IEEE copyright, 2008, pp. 199 -
REFERENCES 202.
[1] Myungsik Kim, Nak Young Chonga, RFID-based mobile robot guidance [18] M. Mamei, F.Zambonelli, Pervasive Pheromone-Based Interaction with
to a stationary target, Mechatronics, Volume 17, Issues 4-5, May-June RFID Tags, ACM Transactions on Autonomous and Adaptive Systems,
2007, Pages 217-229. 2(2):1-28, ACM Press, 2007.
[2] Knowledge Environment for Interacting ROBOt SWARMs project, a [19] B. Gerkey, R. T. Vaughan, and A. Howard, The Player/Stage Project:
European project supported within the IST priority of the Sixth Tools for Multi-Robot and Distributed Sensor Systems, Proceedings of
Framework Programme for Research and Technological Development. the 11th International Conference on Advanced Robotics (ICAR 2003),
Contract Number: 045255 (www.roboswarm.eu). June 2003, 317-323.
[3] M. A. Batalin and G. S. Sukhatme, The analysis of an efficient algorithm [20] M. Baglietto, G. Cannata, F. Capezio, A. Grosso, R. Zaccaria, A Multi-
for robot coverage and exploration based on sensor network deployment, Agent Control Architecture For Large Scale Multirobot System, 27th
Proc. IEEE Int. Conf. Robot. Autom., 2005. IASTED Modelling, Identification, and Control (MIC) 2008, Innsbruck,
Febbraio 2008.