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.