Multi Robot Communication
Amit Keswani
Chemakura Baba Kumar Reddy
Girish Dhameja
Moqtar Ahmed Syed
Vinod Devarajan
Navroop Singh
Department of Computer Science
LamarUniversity
P.O. Box 10056
Beaumont, TX77710
E-mail:
Abstract
Co-ordination, coupled with communication, is very important for any multi-robot system to successfully accomplish the task. Co-ordination and communication can multiply the capabilities and effectiveness of a group of robots. Communication between co-operating robots can be facilitated by using suitable protocols. Over the past decade, there have been a number of experimentally demonstrated multi-robot co-ordination and communication mechanisms. This paper discusses many of the considerations that impact the form of such protocols. A layered protocol is presented, consisting of data and transport layers borrowed from the Open System Interconnection (OSI) model and task-independent and task-dependent content layers. Finally, a description of a centralized communication architecture is presented followed by an efficient implementation of an ad-hoc multi robot system.
1. Introduction
Growing interests in the study of multi-robot systems adds increasing importance to the area of robot communications and encourages the development of communication protocols. For the purpose of this paper, a robot is any device which possesses sensors and effectors and uses these resources to act purposefully, autonomously and continuously.
Continually improving technology has made it realistic to consider the deployment of multi-robot systems consisting of increasingly large number of robots. Potential advantages of multi-robot systems over a single robot include, but are not limited to, reduced total system cost, increased robustness and increased parallelism. Furthermore, the inherent complexity of some task environments may require the use of a heterogeneous group of robots as the necessary capabilities are too substantial to be met by a single robot. Modular system design complements the concept of co-operating robots by facilitating a clear division of labor among the robots each of which is an expert in one type of task.
From a few robots performing a manipulation task to thousands of robots exploring the universe, as the number of robots increases, so does the necessity and importance of co-ordination. Co-ordination is defined as the act of regulating and combining so as to produce harmonious results. In the context of multi-robot systems, co-ordination is the process of appropriately regulating the robot’s actions such that a given task or goal is successfully achieved. The co-ordination of a team of robots would be impossible without communication and any but simplest communication scheme will introduce significant complications into the robotic system. However, these complications can be significantly ameliorated by structuring the interaction with suitable communication protocols. This paper introduces several aspects of robot communication and presents a layered protocol.
2. Communication
2.1 Need for communication
There are many scenarios where we desire communication in the context of multi robot systems. First there is need to co-ordinate actions between different robots so that the task can be accomplished without any conflicts. Second the robots could exchange knowledge about situations they are in, for example a map of a room one robot has explored but others haven’t. Third robots can share sensory evidence to enhance, de-noisify or reveal things about the world. A very basic example would be when robots are heterogeneous and have different kinds of sensors. Communication is desirable in the building of group goals. In case of a robocup team, there is a global, constant goal of winning the match. However, sub-goals that influence the current movements and near future tactics of the team members can and should change rapidly to be able to cope with the opponent. Such goals need to be communicated. Communication increases the group cohesion
2.2 Communication, a broad definition
In the context of multi robot systems, the definition of communication is very broad due to the fact that a lot of robots are simple agents. We define Communication as the transfer of information between one robot and another. The problem with this broad definition is that it includes all kinds of unintentional forms of communication. For a more precise definition, it is required that the conveying of information have some form of intentionality on both the sides.
2.3 Types of Communications:
A simple classification of communication used in the field of multi robot systems is as follows:
- Implicit Communication:
Implicit communication is communicating through change in the environment, also known as stigmery. Robots can leave marks and trails that can convey information to other robots that will recognize these changes in the environment. Such actions can be compared to human actions like children chalking arrows on the sidewalk or ants leaving scent trails.
- Explicit Communication:
This type of communication is purposely transmitting and receiving communication via some sort of protocol or language as a medium. Explicit communication is always intentional and the robots are completely aware of it. Examples of such communication are nothing but alarm calls or humans speaking language to one another. A communication device is required for such communication to serve as a medium, for instance radio or wireless Ethernet. In comparison, explicit communication is less robust than implicit communication as communication needs to be transmitted and received in a separate process.
- State Communication:
In state communication, the robots should be able to observe the behavior of other robots. An example would be body language. It can be applied to robotics for instance in a light following task, where robots follow each other towards a light source. Note that for such communication a robot must be able to recognize other robots and know what their actions mean.
- Goal Communication:
This type of communication involves the transmission and reception of specific goal-oriented information. Implementation of it on mobile robots requires data to be encoded, transmitted, received and decoded. Goal communication differs from state communication in that the sender deliberately sends or broadcasts the information. A natural example of this type of communication is found in the behavior of honeybees.
Thus communication has a huge impact on the performance of multi robot systems. But there are factors that directly influence multi robot communication thereby indirectly influencing the performance:
2.4 Factors which directly influence robot communications
While designing a protocol for robot communication, few factors need to be considered which can directly influence robot communications. This paper discusses about the primary factors which influence the communications. In practice, there could be many more factors that can influence the semantics of communications.
- Information Density:
Bandwidth is always limited in a network. The information exchanged between two robots has to be reduced to a bandwidth which is supported by the network channel. To reduce the exchanged information, preprocessing of the information is required. This term is used to designate a measure of the preprocessing required in the transmitting to reduce the exchanged information to the required bandwidth and to reconstruct the exchanged information at the receiving robot.
- Channel Bandwidth:
The bandwidth of a communication channel determines the total communication throughput which can be achieved.
- Channel Security and Detection:
Security means to avoid unintended interception of the information exchange. Although security has not yet been considered a prime issue in robot communication but it can be added in to the system by using encryption algorithms.
- Channel Reliability:
Channel Reliability is a function of channel noise. It dramatically affects the protocols chosen for communication. It is expressed as the ratio of the bits which are received error free to the total number of transmitted bits.
- Channel Efficiency:
The efficiency of communication channel is determined by the ratio of the total number of bits exchanged in a communication to the total power required to insure successful receipt of the message.
- Channel Traffic:
The number of robots competing for a channel to transmit information affects the available bandwidth. This results in flow control mechanism being introduced in the transport layer.
3. Result
3.1 Protocol
The communication protocol presented here consists of two sets of layers, the transport layers and the message content layers. The transport layers provide a channel between sender and receiver over which symbols are exchanged. The content layers format the information that is to be communicated.
Task Dependent Layer
Task Independent layer
Transport Layer
Net Layer
Link layer
Physical Layer
3.1.1 Transport Layers
The transport layers are completely independent of the information represented by the content layers. Thus, the information transmission aspect of robot communication can be treated as an instance of the more general situation of inter-computer communication. The transport layers consist of three layers, Link layer, Net layer and Transport layer which are borrowed from the OSI model. These layers provide more or less the same functionality as in computer networks.
Link layer:
The service this layer provides to the net layer is a transmission channel between neighboring robots. Its functions include sending and receiving data to and from neighboring robots. Since this layer deals with the physical communication channel, it directly depends on the type of the robot.
Net layer:
The service this layer provides to the transport layer is the routing of packets between any pair of robots. To enable routing of packets, one very fundamental issue is of addressing; each and every robot in the system should be uniquely identified. IP addresses are used in Internet. Each IP address is of 32 bits. In robots, the packet length is very small, generally 5 to 8 bytes, which makes long addresses obsolete. The implication of this is that we can have comparatively fewer robots in a system. Generally, 8 bits are used for addressing.
Transport layer:
Transport layer provides application to application communication. In a robot, there might be multiple applications running simultaneously, like the robot might be scanning at the same time it’s moving. To establish a communication flow between two applications, transport layer offers the abstraction of ports.
3.1.2 Content Layers
The content layers of robot communication protocol consist of a layer which is independent of the specific robot task domain and other layers which are strongly task dependent. The task independent layer is strictly structured and conveys parameters representing certain aspects of communicated information which are independent of the specific task environment. This paper discusses the task independent layer and on the elementary tools required to support the development of the task dependent layers.
Task Independent layer:
The task independent layer is made up of three different components, Address, Context and MessageState. The Address descriptor identifies the communicating robots. The Context descriptor identifies the message within the complete information exchange between cooperating robots as well as linking that message to other messages which relate to the same context. The MessageState descriptor describes properties of the task dependent component of the message.
Task Dependent layer:
The task dependent layers provide information coupled to the task description. There could be many layers depending upon the complexity of the task and the environment in which the robots are to execute the task.
Design of the task dependent layers involves two classes of decisions. One class determines those factors of the protocol layers which are required for successful performance in the task environment. This class of decisions includes choices of the types of information which are represented at the various levels, the definition of the minimum representations required by the task environment and the interactions which exist between the higher layers. The other class of design decisions consists of those factors which can be determined irrespective of the fundamental considerations. This class of decisions includes choices of representing symbology, particular format of representation and the identification of such convenient constructions as pronouns, quantifiers and expletives. This class of decisions requires consideration of those factors which are not directly related to the communication process. Most decisions of this class impact such minor issues as overall flexibility, reliability and utilization.
4. A Centralized Communication Architecture
Broker is an example of a centralized inter-agent communication system. Broker was created with a focus on developer convenience. With Broker, we can have the wide variety of OS/language choices. We have a very stable packet format
The design of an ideal IPC system must consider the following aspects:
- Language API
- Network connectivity graph
- Message based vs. Stream based
- Data serialization format
- Service location protocol
- Anonymous publish-subscribe vs. P2P remote procedure call
An ideal IPC system would be a flexible toolkit allowing the developer to choose and combine functionality at any desired point along each axis. No, existing IPC allows that, but allow a few choices. Broker is not an ideal too. It embodies a principled design approach with the convenience of developers as a primary goal.
A Broker network is centralized around a single process called the Broker. All the communication is done via UDP packets which flow between the clients and the broker
The greatest advantage of Broker is, it does not impose a strict API. Creating packets can be analogous to that of using printf in C. These packets can be instantly accessible to all languages. Parsing can be thought of similar to that of scanf in C or a regular expression. The Broker code base allows for convenient packet parsing functions in Java and C.
Centralized Broker system architecture
There are few disadvantages to the publish-subscribe model we chose for the Broker. The need for the RPC appears not to be well served. It is easy to build a RPC framework on top of the publish-subscribe. Broker, depends on fast and local connectivity between all components of the system. The server process sends copies of messages published on a channel to each client subscribed. If all the clients resided on the opposite end of a bandwidth-limited connection, this behavior might overwhelm the capacity of the link. One solution is to allow a system to contain multiple server processes, one for each high-speed domain.
There are various disadvantages of using centralized architecture. Few of them include:
- Load on the server will be increased when the number of client robots.
- If the server crashes, there is no way that the client can communicate with each other.
- If the load on server increases, it might lead to performance degradation.
- Low area coverage
5. An Ad-hoc Communication Architecture
5.1 Ad-Hoc Routing protocol
Wireless networks can be classified into two types Infrastructure networks and Ad-Hoc networks. PERA is a Ad-Hoc type wireless protocol for use in mobile robotics
Many Researchers have created routing protocols for Ad-Hoc networks. They use routing tables to correctly adapt to the frequent mobility of the nodes, to do so a node has to frequently send messages to the nodes in its vicinity. In this paper we describe about PERA which is based on AODV (Ad Hoc On Demand Vector) routing protocol. The implementation of PERA has been programmed so that robots can communicate independent of radio scope. The Paper also discusses about the implementation of PERA on a multi robot system called Eyebot.
Eyebot robots have three infrared sensors two encoders and a camera, in addition to this it has a communication module that uses PERA to communicate wither robots. All these devices are run on a RoBIOS operating system.
There are two types of routing Ad-Hoc routing protocols, One that is based on routing tables and other based on demand routing. Protocols based on routing tables use a lot of messages to keep the information in their tables reflect the current status of the network. WRP (Wireless routing Protocol ) comes under this category. Protocols based on demand routing only store in their tables that are really needed, if the node receives a packet to a destination unknown to the node a route discovery process is initiated. Route maintenance is also needed in order to keep fresh the routes learned and remove the unused routes. Some examples of this category are AODV, DSR (Dynamic Source Routing)
5.2PERA2 Ad-Hoc Routing protocol
PERA tries to fulfill the following requirements
- Each Robot can send data to other robot
- Each robot can receive data from other robot
- Movement of robots is allowed with out disturbing the communications
- Multiple applications concurrently running on PERA can send/ receive
- Each robot can send to a particular application running on a particular robot
- The library that implements PERA allows choosing between Unicast or Multicast transmission.
These requirements are not always possible to fulfill, if there is no existing path between the source and destination robot.
The limitations on PERA are placed by the RoBIOS operating system is that the data packet cannot be more than 35 bytes. Most ad-hoc protocol include complete path in each data packet, this is included to help the intermediate nodes to route the packet based on the route in the data packet.. Due to the small size of the data packet in PERA this option was discarded.
Protocols based on tables were considered for PERA but soon they were discarded because they would overwhelm the network withy the control messages just to maintain the real time vision of the network. Instead PERA uses demand based Routing that is table driven. Each robot maintains tables with routes. The data packet only contains the destination address each intermediate robot consults its tables to route the data packet. PERA only updates tables on demand. There are two main duties of the routing function Route discovery and route maintenance. Each entry in the route table can be erased or updated. There is a field called lifetime, when the route maintenance detects that the route is too old the lifetime field is not refreshed.