Home

Background

Low level design

High level work

Build your own robot

Rendezvous

Collaborative Robotics - Related Work

Mobile robots have been around since the 1970s in one form or another [1] [2], initially only able to perform the simplest tasks under close supervision. However, as the technology improved so did their capabilities, until just a few weeks ago, Beagle 2, a modern mobile robot was blasted into space on a one way unsupervised trip to Mars [3].

Nonetheless, the fundamental requirements of the mobile robot remain the same [P10]. A robot must be able to sense details of its surrounding environment, use that information in both navigation and any other task it may be obliged to perform, and move under its own power. All this must also be done whilst the robot continues to perform whatever task has been assigned to it, whether that is taking samples of Mars rock [3], picking oranges [Cavalieri 97] or detecting mines [4].

Even beyond the basic necessities a robot must feature, there are still further additional requirements demanded of any mobile robot, these are safety and reliability [T2]. Naturally, the same is true of any automated system which must work alongside humans, but in the case of mobile robots, where their location itself is unpredictable, the task of ensuring that the robot is safe to humans becomes a significant undertaking. Although separately considered, reliability must be a feature of any safety critical system; it must also be considered even when safety is not at issue - such as in inhospitable environments. Once a robot has been deployed into an inhospitable environment, a common application target of many mobile robots, it would by definition be difficult or impossible for any malfunction to be corrected. Thus, the robot's behaviour must be entirely predictable and reliable.

More recent work in the field of robotics has taken a significantly altered approach to the issues of safety and reliability. Although the necessity for the robot to be able to navigate autonomously remains (this is the definition of an autonomous robot as we consider it to be true), the safety and reliability aspects of the mobile robot problem have been transformed by making everything much smaller. Technology has, of course, played a large part in the timing of this evolution, but there has also been a change of focus amongst the research community, bringing about collaborative robotics.

Many of the autonomous mobile robots under development today no longer work alone, they work collaboratively. Collaborative robotics can be taken to mean robots collaborating with other robots or with a human; in this context we have taken it to mean collaboration with other robots working towards the same goal [P1]. There are both advantages and disadvantages to this new approach. Taken from any perspective, the reduction in size of any individual robot is going to come at a price even with advances in technology. Smaller robots aren't able to carry as many sensors or shoulder the weigh of such a bulky processor as their solitary predecessors. However, this can be compensated for by the full utilisation of their team based format. With this methodology there is no longer a single point of failure, making reliability necessary but no longer absolutely critical to quite the same degree, in addition collaborating robots will be able to cover far greater area in less time [P4].

There are already established approaches to the programming of collaborating mobile robots, dealing both with the traditional localisation problems faced by standard mobile robots, and with the range of new difficulties brought about by the necessity to interact with entities as blind and stupid as they are themselves. This interaction must not only be at the level of communicating simple information to one another, collaborating robots must successfully share in the task they are assigned without either treading on one another's toes or removing the advantage they do have of combining their work from a wider area to give a more complete view. The key to this is the introduction of roles [P1][P3][P5], a type of behaviour that the robot must exhibit. Behaviour based control of a robot is nothing new [T3], but in the framework of a team of collaborating robots, this must be applied as a series of different roles which the robots can use as a means to function more effectively than if they each performed the exact same task. [P6][P4][P3][P10]

Roles can be defined statically in advance [P4], and there are generally modelling methods such as finite state machines or state transition diagrams [P1][P6] applied to this process, but they may not necessarily be given to a robot and maintained statically. Instead, robots will often switch roles dynamically [P3], for example in [P1] when a robot soccer player finds itself in a role which is not suited to its current position as well as another role might be (i.e. the robot is defending the goal but it thinks that it is a forward) these robots will be able to negotiate to switch roles, thus improving the team's overall performance. Dynamic assigning and exchanging of roles can still be a complex process, even in the context of robot soccer the robots must ensure that the team retains an appropriate balance of different players, which is most often carried out through the use of a task broker [P3][P4][P24]. Task brokers work on a market type strategy, allowing robots to bid on roles most suited to them and assigning the role to the highest bidder, thus ensuring that roles are not repeated unexpectedly.

Robots need not, however, be limited to a single role at any one time [P3]. It is entirely possible that a robot will be capable of carrying out two roles simultaneously, dependent only on the capabilities of the robot itself, particularly from a hardware perspective. As this capacity is reliant on the hardware of the robot, and not all robots are necessarily identical - for instance in [P1] all robots are identical except for the robot goalkeeper, but in [P4] the robots form a hierarchy where some robots are capable of carrying others - it must be up to the robot to decide whether it is able to fulfil all of its assigned roles. Again, this enables the methodology of the task broker which will rely on the ability of the individual robots to determine whether they should bid for a given role, and merely assign the role to the highest bidder.

"An agent is an encapsulated computer system that is situated in some environment, and that is capable of flexible, autonomous action in that environment in order to meet its design objectives." [P2]

Intuitively, the very concept of having roles which are executed on board separate, autonomous vehicles implies that the system is designed to be agent oriented, indeed, the approach taken in the state-of-the-art Gaia methodology for agent specification explicitly makes use of roles [P2 ref 15]. The theory behind agent oriented software, as opposed to object oriented, is to separate the complex communication problems faced by the autonomous agents from the everyday concerns common to any program. Agents need not be restricted to robotics; they are well suited to any application where division of the main task into smaller tasks is beneficial, whether that is a logical separation within a single computer or on board physically distinct autonomous robots [P24][P8].

The single biggest difficulty with agent-based programming is dealing with the communications between separate agents. This remains an active field of research, with protocols for coordination [P9], task distribution and control [P8], and can require the system to cope with incompatible agents and agents with conflicting goals [P10]. However, the advantages of the use of agents, such as parallelism, robustness and scalability continue to outweigh the difficulties faced in communications.

As is discussed in [P24], multiple intelligent agents can be effectively used for exploring and mapping an environment, a common goal among both collaborative and non-collaborative robots. The fundamental advantages of the multi agent system are based in more traditional, complementary areas such as data fusion, cooperative perception and sensor networks (where the picture of the environment is improved by an increasing the number of sensors applied to the problem) but there remain additional advantages in the intelligent collaboration of the agents, where it is necessary for them to interpret data selectively and intelligently.

Returning to the difficulties faced by every autonomous robot, this discussion of environmental perception becomes particularly relevant. Despite the move from solitary robots to collaborating ones, the difficulties with localisation of the robot remain for every application but the few in a position to make use of GPS. As implied in [P24] this problem is strongly connected to the use of sensor networks, collections of small low powered sensors which are often deployed randomly then abandoned to perform the sensing task assigned to them for as long as possible [P28] [P36] [P31] [P33].

Applying the theories of sensor networks to the use of collaborative robots, particularly in this initial localisation problem is entirely logical. With their collections of sensors on board, each one of the robots can easily be regarded as a sensor node and theories related to sensor networks may then be utilised. The major challenges faced by sensor networks are largely related to their initial deployment [P28][P18], communications and energy costs [P13][P21], all of which tend to be interrelated to some extent [P22]. They also have difficulties related to monitoring their survival [P35].

As with individual robots, there are only a few common methods of localisation put into use. For robots which will always work outdoors the obvious choice is GPS positioning, which can be accurate to approximately 2cms and gives the position of the robot anywhere in the world. However, this technology is not always appropriate, whether because the robots must work indoors, because the equipment is too large for the robots in question or even because of fears of GPS jamming [P26], and there are also a number of alternative indoor methods which are often put into practice.

Received signal strength indicator (RSSI) [P12] [R9] estimates the distance between two nodes by comparing the transmitted power at the sender with the received power at the receiver. In the case of individual robots, this type of positioning would rely on beacons being set up for the robot to communicate with, but with the introduction of a collaborating team of robots, this is no longer an issue and the robots can localise themselves relative to one another easily. This would, however, still rely on one of the robots knowing its initial position (unless there were beacons in place) in order to calculate a location relative to the outside world. There are a number of errors associated with this method, the most serious of which are the effects of reflection, scattering and diffraction, which will change the distance the signal has travelled and inevitably give the robots an inaccurate picture of their environment. This is at its worst when two robots no longer have line of sight due to an obstacle, or when errors in the orientation of the two robots which means that the transmitter and receiver are not directly facing one another. When acoustic ranging is used, errors can also be affected by changes in atmospheric conditions which will affect the speed of sound.

Time of arrival and time difference of arrival (TOA/TDOA) are widely considered to be improved methods of localisation in comparison to RSSI, but somewhat more complex. Here, any message is time stamped, and the time taken to receive it (or the difference in time taken for two different types of signal usually radio and ultrasonic) is used to calculate the distance between objects. Again, the biggest single problem is in reflections of signals, causing the signals to travel further than they should have, making the longer reflected path bias the calculations of distance over any line of sight path when averaged [P12] [R8][R7].

These reflective errors, are unavoidable, although improved by line of sight, and in the case of [P23] are enough to leave the authors preferring to use wheel odometers and magnetic compass only as their method of positioning, however, this is in part because of the tiny size of the robots in question, and the authors concede that due to the cumulative effects of the wheel encoders' error, it would be preferable to make use of ultrasonic or radio ranging at some point. Others have also opted to make use of alternative means of localisation. In [P36] a method is used where the robots truly collaborate even in their localisation as stationary robots track other robots carefully as they move. This method will allow the robots to maintain a view on the world relative to their initial position, but like odometry will ultimately become prone to errors without an external reference.

In [P16] an alternative approach to TOA is taken, known as angle of arrival (AOA) where the robots must measure the angle at which a message arrived rather than its time of arrival. This system can then, in conjunction with a compass, make use of triangulation in order to calculate the location of each robot. As with GPS, where trilateration is used, the greater the number of nodes used in the calculations, the greater the chance of the location calculated being accurate.

The method discussed in [P16], as with any other sensor network based localisation system is used on a collection of nodes which rely on ad-hoc networking [P27][R6]. Prior to embarking on any further discussion of the details of sensor networks, it should be noted that ad-hoc networking is one of the primary features that collaborative robots and sensor networks have in common. If collaborative robots are to remain at all dynamic, they must feature a dynamically reconfigurable network, namely an ad-hoc network where nodes can be added and removed without any re-initialisation. All of the examples discussed thus far make use of ad-hoc networking.

Beyond the type of network used on sensor networks, it is also highly relevant to note that sensor networks take a specifically designed approach to their network routing and protocols. Sensor networks, which are low powered and must pass useful information around as economically as possible, generally take a data-centric approach to their networking protocols. That is, rather than giving every node an address and using that address in order to send information (as on the Internet) the nodes refer to the data which they carry, in particular spatial information which will tell other nodes of the relevance of the data a node carries to them [P33][P36]. Taken in the context of collaborative robots these energy concerns seem less significant when compared to the operation of a motor. However, collaborative robots are smaller and lower powered than their solitary predecessors and may spend a good deal of their time stationary - depending on their configuration - so this discussion remains worthy of note.

Information gathering whilst conserving energy [P21] is commonly approached by allowing the sensor nodes to form clusters. These clusters, which are hierarchical, then use data fusion or data aggregation before sending the information to the base station [R5]. This shifts the finding of routes from address-centric to data-centric [P13] as discussed in the previous section. Five basic data aggregates which have been shown to result in significant power savings are suggested in [R4] namely: count, min, max, sum and average.

However, simply sending the information to the base station in larger sections than might have been done doesn't complete the needs of the sensor network, and certainly may cause problems when applied to collaborative robots or other sensor networks which may not feature a base station. In [P22] a trade off between memory storage on board nodes and the need to transmit is discussed leaving the nodes to store random messages within clusters to limit the necessity for communication to a minimum. Certainly, from a routing perspective, every node in such a parallel system being forced to only request information via the base station would be inefficient, so it has been necessary for sensor networks researchers to also create a more general means for approaching the dissemination of information. One such method is directed diffusion [R3], where intermediate nodes aggregate responses to queries for information.

As a means of limiting the need to flood the network with either queries for information (as in directed diffusion), or notification of events, whilst still providing the ability to match the two, [P30] suggests a method called "rumour routing". In rumour routing, a query is sent on a random walk through the network until it reaches the "event path" (from the source of the event to the base station in this case) and follows that directly. The query will find the event path the vast majority of the time in a well populated sensor network (in a sparse network directed diffusion would probably be better anyway) and if it fails the network can be flooded or query resubmitted easily.

As is partially suggested in these approaches, following on from the need to form clusters, it seems logical to have two different types of node [P21][P38], one which can perform data discovery using sensors, and the other which can spread this information throughout the network. This will assist in the spread of information without interfering with the sensing work carried out by the data discovery nodes as it otherwise might. However, it will also make the layout of the network more difficult to achieve and concepts such as rotation of cluster heads to avoid energy loss nearly impossible to achieve without a great deal of redundancy.

Taking data dissemination to another level, [P29] suggests a complete operating system which is essentially a tiny virtual machine such as the one used for Java programming. This approach allows not only for tweaking of message content, which would save energy in transmission time, but also enabling the complete download of a new sensor network program without significant impact on the overall energy available to the system as only a relatively small proportion of the program would be overwritten. Their approach is based on extensions to TinyOS [R2] a system already developed specifically for use on board sensor networks with inbuilt ad-hoc networking protocols and power saving features.

The difficulties arising with energy consumption versus the need to share information have led to investigations of passive networking [R1] where the sensor network is taken to its extreme case in the form of Smart Dust. Here, a method using the reflection of light waves when the motes (nodes) are within line of sight which requires no energy to be used at all has been devised for the Smart Dust motes to communicate.

However, whilst energy free transmission is not yet available or appropriate to the majority of sensor networks, sensor networks must struggle on with their low energy minimal transmission policy. For instance, the issue of monitoring the health of the system must also be considered [P35]. Taking the completely passive approach, it would be impossible to tell if a sensor had died as it would appear to be continuing its silence as it had done previously, whilst requiring the nodes to actively demonstrate their health uses valuable resources. Even making use of a hierarchy, transmitting a "keep alive" message would be wasting transmission seconds which could be used to transmit useful data later.

Further, the energy used by a transmission of any kind can be further affected by message collisions [P14], a factor which the majority of algorithms appear to ignore even though as the number of nodes in the network increases the cost of such collisions can be prohibitively high. This is also discussed with respect to sensor deployment, where a high denseness of sensors is shown to have a catastrophic effect on the number of collisions in the network [P28].

As the network protocols and applications of sensor networks and other multi-nodal systems are important, so is the infrastructure of the sensor network [P28]. Although one-time deployment is not strictly of interest to collaborative robotics, where the robots must continually redeploy, any considered approach to their ideal positioning must be taken into account. Deployment of sensors can be carried out randomly, in a geometrically regular formation, or in another planned formation [P28], although it should be taken into account that any non-random deployment will require additional effort in non-mobile sensor nodes. The type of deployment used must naturally be relevant to the task to be carried out by the sensors, whether it is a continuous phenomenon such as temperature sensing in a given environment or a discrete phenomenon which might require the sensors to track an object. For a discrete phenomenon with an expected movement pattern, it may for instance be possible to bias the sensors towards the object's movement [P28].

Deployment becomes more interesting when the sensors become capable of some small movement themselves, as the vast majority of sensor networks would be too complex to distribute any way other than randomly. In [P20] consideration is given to the once only redeployment of a randomly distributed set of nodes based on virtual force calculations of each node's potentially improved position. This will allow the overall capabilities of the sensor network to improve without consuming too significant a quantity of its initial energy. Taking redeployment further, in [P18] a mobile sensor network which may be continually redeployed is discussed. In this case the nodes are initially randomly distributed but then one at a time calculate the maximum coverage achievable by their movement and proceed to that position - exchanging places with another node if that node should pose an obstruction. Maintaining a line of sight with other nodes, the sensor network gradually oozes into the optimum position for its task.

Taking this oozing sensor network to its next level, the sensor network which is formed by a group of collaborative robots would be expected to achieve a similar result if chasing a particular sensory task. A collaborative robot team could easily deploy itself to the optimum configuration, given the lessons of the sensor networks research. The team may also take into consideration a great deal of information on the localisation of its distributed components, which once accomplished would make the localisation of the robotic team as a whole significantly easier even when compared to a single robot.

After 30 years or more of development, the mobile robot has changed beyond all recognition and developed more difficult research dilemmas without ever completely solving the original ones. However, though complex, this document has considered a number of the key elements required in construction of a collaborative robotics team, including roles, agents, communications and positioning, and given the capacity for performing interesting and useful applications we would consider the advantages of collaborative robots to outweigh the disadvantages when compared to a lone robot. It is these advantages, including the flexibility and redundancy provided by the collaborative robotic teams which we are interested in exploiting in the future.

References