-This paper presents an approach for multi-robot coordination based both on coordinated navigation and task allocation method. An ad hoc agent based architecture is defined in order to implement the robot control system in both simulation and real applications. The coordination of the multi-robot system is based on agent interaction and negotiation, and a communication infrastructure based on open web standards is provided. The system employs the RFID technology for building a context aware information system which is the base of the coordination strategies.
Multi-Robot Systems; Multi-Agent System; Interactive Systems; Multi-Robot Task Allocation.
Distributed I.
INTRODUCTION
The general objective of this work is to develop an open knowledge environment for self-configurable, low-cost and robust robot swarms usable in everyday applications. Advances in the state-of-the art of networked robotics are proposed through introduction of a local and global knowledge base for ad hoc communication within a low-cost swarm of autonomous robots operating in the surrounding smart IT infrastructure.
The work will address the development of flexible, costeffective, dependable, and user driven robot swarm, which possesses a higher intelligence collectively than each member of the swarm independently. In particular, this paper involves self-organizing task-sharing mechanisms between individual members of the swarm to capitalize on the availability of a large number of simple and cost-efficient robots. Reuse of the local and global level knowledge is pursued by creating on-site (near to objects of interest) distributed data environment. System is kept scalable and manageable by decentralization of control and manipulation to local level.
In this work RFID tags [
The proposed system is based on both a coordination
control algorithm and a distributed task allocation method: as
mentioned above, both methods rely on RFID technology and
exploit context aware information for navigation and task
execution aims. An ad hoc agent-based architecture is defined
for implementing the robot control system. AgentService [
In next paragraphs, the state of the art in applying RFID technology and task allocation methods to multi-robot systems is briefly analyzed. Section 2 illustrates a novel approach for robot team coordination that could be applied in different application contexts; in addition we present the agent-based architecture implemented for applying the coordination methods in robot applications. Conclusions are given in Section 3.
RFID tags have attracted great attention as a key device in
various domains, from object tracking to robotics. As a result,
the deployment of RFID technology on a larger scale is about
to become both technically and economically feasible [
Focusing on mobile robotics applications, attached to walls,
machines, or other specific places in the environment, RFID
tags works as dedicated landmarks making the robot able to
detect items, obtain information about its position, and even get
instructions to reach a given goal [
Sharing the task related workload among robots through a task allocation mechanism is an effective way for making a team of robots act in a coordinated way. A task can be decomposed into sub-tasks and an assignment process can be adopted in order to allocate tasks among the team. Different approaches are proposed in literature for solving the task allocation problem starting from classical operational research algorithms to social behaviors inspired by human society or swarm organization.
One of the most diffused and adopted mechanism for task
allocation are auctioning systems [
II.
Cooperative robotics is one of the hottest topics in current 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 processes work coordinated; orchestrating single robot behaviors by allocating properly the tasks to be accomplished. 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 system allocates the tasks optimizing some parameters; after that, each robot performs the assigned tasks as a single system.
We think that the two approaches are complementary and
can be applied together in order to obtain a whole coordinated
behavior of the robot swarm. We selected for our multi-robot
application a classical problem that can be applied in different
context. A traditional problem in multi-robot system is to
repeatedly visiting a set of specific locations, a variant of the
dynamic coverage problem (see [
We propose a coordination system in which the coverage
problem is solved with a real time search algorithm presented
in [
In order to assign tasks to robots in an effective way, a distributed task allocation mechanism is defined. One of the goals of the defined methods is to be able to adapt both environment changes (e. g. addition of new environment areas) and robots’ team changes (e. g. robot failures). Finally the allocation mechanism has to be robust enough for working in critical scenarios like rescuing where broadcast communication may be not available. In the multi-robot system a central server is considered in order to interoperate with external software applications and to provide services to robots. The main phases of the auction algorithm can be summarized as follows: 1. The central server acquires tasks to be executed by the robot team, new tasks can emerge as results of user requests or automatically generated by a reasoning system.
2. The central server analyzes the task definitions and decides how many robots should be assigned to each specific task but do not explicit identify them.
3. Then the robots should be informed about the new tasks to be assigned and the number of robots required.
4. The assignment is the result of a negotiation that each robot leads by itself.
These last two points have to be investigated in order to make the proposed task allocation system adaptive and robust.
Service Room
S Hot Spot Node Zone Graph Topological Graph
Zone A
Zone B
Zone C recharge their batteries and the communication with the server system is ensured.
Each application oriented task consists in performing some specific actions in a defined area; it is modeled by the following properties: Priority, Deadline, Required capabilities, and Revenue credits. The priority is critical for scheduling the task while the deadline defines the time within the task has to be completed. In order to effectively perform each task specific robot capabilities are required: this is a relevant point when considering a team of heterogeneous robots.
Once a task is concluded, it determinates an amount of virtual credits that is assigned to the robot as revenue for completing the task; this is a focal aspect of the bidding mechanisms. The “Call For Task”, CFT, represents the “call” promoted by the Server System, which play the role of Auctioneer. It mainly contains the task and the auction information, in particular the auction deadline: the time within robots can send a valid bid to acquire the task.
The basic steps of the auctioning process are: • • • • • • The negotiation process is based on a first-price auction: while performing assigned tasks, robots look for new CFT; when a robot gets informed about a new task, it evaluates the acquisition of the new task taking into account: task required capabilities, already assigned tasks, task priority compared with the already scheduled task, and deadline; and then the robot decides to start a negotiation process. 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 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 within the environment is required. In order to solve this problem, the proposed idea is to exploit the robots as message couriers and the zone hotspots as mailboxes. The couriers collect auction data from the server, within the service room, and deliver CFT to the hotspots. All the robots can play the role of message courier: they can get CFT information from the server when they go to the Service Room for recharging their battery and then they became able to deliver the CFT to the target hot spots while coming back to the working zones. Hence, in the messenger scenario the server communicates to robots in the service room the new CFTs along with the hotspots where to deliver them and these robots deliver the CFTs to hotspots playing the role of messengers. Once the CFTs are published into the hotspots, robots periodically visit the hotspot of the area in which they are working. Periodically means that they visit the hotspot when they terminate the execution of a task or at fixed interval (polling strategy); the interval may vary in function of the priority of task already assigned to that robot. If a robot is interested in a CFT, it starts the negotiation process by leaving its bid for task on the hotspot blackboard. At the deadline indicated into the CFT, each robot involved in the negotiation process checks the auction result (best offer) in the hotspot, hence the winner autoallocates the task in its schedule. The Server System will be informed on task allocation (auction results) when robots come back to the service room collecting runtime information. If a CFT doesn’t receive offers, the Server System can decide to reschedule the involved task in a new one.
The robot control architecture is described in the following
schema. The proposal is based on the result achieved in the
Roboswarm project [
We adopt the agent paradigm for modeling the single robot control architecture and the whole multi-robot systems. The architecture involves a dedicated multi-agent system; different kinds of agents can be defined in order to solve/execute specific problems/actions. A reactive agent, Main Control Agent works as the central control process and it can activate reactive behaviors. It executes the real time coordination algorithm and schedule the application oriented task if requested. We introduce two other reactive agents: Sensor Agent and Actuator Agent. The Sensor Agent is in charge of reading input data from sensors and writes them in a shared buffer. Actuator Agent reads robot commands and passes them to robots’ hardware. Reactive agents have to be scheduled as high priority tasks in order to guarantee predictable behavior and safety in performing motion.
The Broker Agent negotiates with other robots and,
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 [
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 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 indirect robot communication through RFID tags when WiFi communication is absent.
The agent-robot interaction is modeled through a
programming interface which invokes a specific low level
Application Programming Interface (API) modeled by the
Robot Interaction Layer. The Robot Interaction Layer abstracts
the interaction with the software components which act on the
hardware. By means of this level of abstraction, agent
behaviors are not strongly coupled with the hardware level
increasing their reuse and portability. Even this software level
is implemented with AgentService [
Considering inter-robots communication, in the scenario in
which the WiFi infrastructure is available, it is important to
follow software standards in order to be able to interoperate
with different system/technology and to improve system
maintenance making the Multi Robot System open. The
concepts introduced with the Service Oriented Architecture
[
For inter-robot communication, the proposal is that the software agents inside the robot can send data to other robots (agent deployed on) or to the system through the ACC and the Service Access Layer.
In addition, each robot may promote its activities through a dedicated Web Service (Robot Web Service) placed on the highest and external layer of the robot architecture (serverside).The Multi-Robot Server System can provide services to robots and should be able to orchestrate external services too. In this way everything is a service or is wrapped by a service. Communication between the Robot Web Service and the onboard software layer is based on standard SOAP messages ensuring easy integration with different software system and, if required, semantic expression of the communication acts.
This paper presents a coordination system for swarm of robots based on agent technology. As demonstrated in literature, the exploitation of RFIDs for getting context aware information system is providing good results. Two approaches for making teams of robots work cooperative are considered. The objective of task allocation is to find the best distribution of the tasks and sub-tasks among the robots belonging to a team. As previously discussed, this problem is widely applied in different application context and the researchers in the field of multi-robot system coordination exploits the works previously done in the field of multi-agent systems, as we have 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 robots have to solve. We can state that task allocation operates at an higher level than coordination control algorithms: the former improves the teams’ work by assigning, and in some cases dynamically re-allocating, tasks to robots and the latter coordinates robots’ actions while they are executing the assigned task. Hence, it seems clear that the two coordination techniques are complementary aspects of the same coordination process and can be applied together in order to improve the effectiveness of the multi-robot systems behaviors.
The proposed coordination strategy is based on context aware information deployed within RFID tags distributed in the environment and does not rely on an internal robot representation of the system. This information infrastructure is used to drive the control behavior of each robot and to distribute tasks among the team. Furthermore, the proposed system is robust against environment changes and do not require direct robot-robot communication: the model of the environment is distributed with the tags and robots can communicate using the tags as mailboxes. The system has been implemented through an ad hoc agent control architecture which provides modularity and scalability. It has been extensively tested in the AgentService environment both in simulation and on real robots. The test case scenarios involve two main phases: team navigation and coverage of the environment with indirect coordination exploiting RFID context information; task composition and allocation based on the distributed auction mechanisms. The tests state the feasibility of the agent architecture and the effectiveness of the integrated coordination approach. The multi-robot architecture exploits the abstraction and the cooperative aspects of the agent paradigm. It can be noticed the adoption of a communication channel transparent for agents which can exchange messages with peers with no care on where receivers are deployed. A service oriented approach is proposed for exposing and promoting the robot team services and easily integrating the system with external software components.