Self-organisation and Emergence in Collective Robotics

TITLE: Self-organisation and Emergence in Collective Robotics

Living as cognitive beings in a world of stability and change we permanently face known and unknown situations, happenings and shifting perceptual patterns in the world, but rarely true chaos or strict regularity. If you claim to fully understand an event or system, you are thought to possess an explanation of it in terms of the mechanisms that produce the phenomenon in question however when an event occurs we may find ourselves unable to verbally recreate the moment. A system is more predictable, it can be thought of as a group of interacting parts, which can be fixed (an engine), unconstrained (a gas) or a mixture of both (a cell) functioning as a whole and distinguishable from its surroundings by recognisable boundaries. Such a system is not entirely predictable it may demonstrate a property or feature not previously observed as a functional characteristic; known as emergent properties. For example; an automobile is an emergent property of its interconnected parts. That property disappears if the parts are disassembled and placed in a heap. The essence is that system’s structure often appears without explicit pressure or involvement from outside the system. Emergent characteristics can also be applied to nature, such as the appearance of life on earth, which can be considered as an emergent structure. Another form of emergence is the interaction of behaviours within a system. Emergent behaviour is a characteristic of some agent systems, and is a consequence of the interaction of simple behaviours resulting in the system performing a task it was not explicitly programmed to perform. Each of these properties, structures and behaviours exceed the sum of its parts and the difficultly is to understand how blind interactions can create order.

This essay endeavours to make clear the overall principle of emergent behaviour through the concept of self-organisation and collective behaviour in both natural and synthetic systems – and explain the architecture required to generate the emergent characteristics. The paper will also introduce, through experimental articles, the notion of collective robotics, which attempts to explain the behaviour of groups of agents within the context of a computational organisation theory (the articulation of an organisation theory in the form of a computer program studied through the use of simulated autonomous intelligent agents). Finally the essay will discuss the problems encountered in the experimental articles and conjecture possible solutions.

Emergent behaviour is exhibited in the actions of many insect colonies. A beehive is built by thousands of bees each playing a small part without knowledge of the extent of the work done by co-workers or having an overall plan. Beehive building is an emergent behaviour through the self-organising actions of thousands of bees. This self-organisation of a system alters its structure as a function of its experience and environment (Farley & Clark 1954).

Another example of self-organising emergent behaviour can be seen in termites. When termites build their nests, no termite has any comprehension of form of the completed nest. The construction of the complex nest structure involves stimergy, which allows indirect communication between creatures through sensing and alteration of the restricted setting. This communication determines the creature’s behaviour. The colony starts to build the nest, by carrying amounts of mud with a small amount of a pheromone is placed inside each ball. To begin with the mud balls are placed at random, the placing of these balls determine the placement of other balls, because termites move toward the strongest pheromone and drop where the smell is strongest; so more balls at a certain location give off more pheromones, which attracts more termites to drop their mud ball. Through this positive feedback spiral the large nest is constructed.

Ant colonies engage in collective behaviours, which enable them to gather objects and place them in particular places. All ants in the colony have the tendency to store food in one place and carcasses of dead ants in another. In this way they are able to collect and store food, or carry dead ants to a “cemetery”. If a large number of ant corpses are scattered outside a nest they will pick them up, carry them for a while and drop them. Within a short it can be observed that the corpses are being arranged into small clusters and as time goes on the number of clusters some decrease and the size of others increases until eventually all the corpses will be in one or two large clusters.

In natural systems, self-organisation is an effect far from balanced. However through blind interactions of individual insects results a form of order:-

Non-equilibrium presses for compensation

(Each ant engages in behaviour)

This compensation changes the non-equilibrium

(Causes a change in the environment)

This mutual change of non-equilibrium and compensation leads to a steady state.

(Clusters are formed)

Forming a dynamic equilibrium in which non-equilibrium

And compensation condition each other and a state

Of dynamic order is achieved (Küppers 1997)

(A “cemetery” is built)

Figure 2. An interpretation of the balance of ...

This is a preview of the whole essay

In natural systems, self-organisation is an effect far from balanced. However through blind interactions of individual insects results a form of order:-

Non-equilibrium presses for compensation

(Each ant engages in behaviour)

This compensation changes the non-equilibrium

(Causes a change in the environment)

This mutual change of non-equilibrium and compensation leads to a steady state.

(Clusters are formed)

Forming a dynamic equilibrium in which non-equilibrium

And compensation condition each other and a state

Of dynamic order is achieved (Küppers 1997)

(A “cemetery” is built)

Figure 2. An interpretation of the balance of self-organisation

Common experiences, where biologically inspired control structures are implemented on real robots, allow biologists to understand how living organisms’ work and engineers to develop new technologies that can deal with unsolved problems. The study of robot models of animal’s behaviour can make an important contribution to understanding how the nervous system, body and environment interact to generate adaptive behaviour. The interaction of engineers and biologists brings new ideas to computational paradigms of robotics, which typically involve several sequential and precise functional processes. The hypothesis behind this approach is that such a synergistic robot system - one whose capabilities exceed the sum of its parts - can be created. Using a decentralized control method in which each agent is equipped with map building, planning and decision making capabilities behaviour based artificial intelligence is concerned with a system exhibiting life-like features using autonomous agents that behave within some environment (Deneubourg et al 1991;Martinoli & Mondada 1995; Beckers, et al 1994; Gaussier & Zrehen 1994).

Autonomous agents, the basic elements of multiple mobile robot populations (able to automatically and independently operate, sense and impact an environment) when situated within an environment can cluster objects based on stimergic coordination. Deneubourg, Goss, Franks, Sendova, Franks, Detrin and Chatier (1991), Beckers, Holland and Deneubourg (1994) Martinoli & Mondada (1995) analysed collective behaviour incorporating an artificial form of stimergy, demonstrating “ant-like” cluster generating collective behaviour using a simple mechanism relating puck dropping and puck density. Robots have a “pusher” in front so they can move the pucks. They also have infrared sensors to avoid obstacles. The stimergic behaviour is manifested in the agent via a micro-switch, which is able to determined two conditions;

A maximum of two pucks can be pushed at one time by the agent - creating a stimulus to work by the products of the work.
When greater than two pucks are detected - through the micro-switch - the agent stops pushing and changes direction.

The agents start to collect pucks in small piles, and eventually all of the pucks are pushed into a single large pile. The actions of the robots are a set of simple behaviours and the only possible interactions between the robots are the reciprocal avoidance of collisions and indirect forms of messages, which arise from the modifications of the environment. The robots do not communicate with each other. The exact behaviour of the agent in the world, using the simplest of algorithms, is impossible to predict precisely, as the actions of an agent depends on the states/actions of other agents. The experiments were performed with varying number of robots it was found that adding robots sped convergence, up to a maximum. An optimal number of robots in relation to the geometry of the environment was determined indicating, the task is achieved in a non-cooperative manner.

The intelligence emerges form an agent-environment interaction base on a large number of parallel loosely coupled processes that run asynchronously. An approach that can be used to structure and simplify the process of both designing and analysing whilst offering room for agent emergent behaviours, uses Brooks (1986) subsumption architecture, which decomposes one complex into many "simple" layers of increasingly more abstract behaviours, where each layer can overrule (subsume) the decision of the lower layer. E.g. the lowest obstacle-avoidance layer could choose to overrule the decision to move by the eat-food layer.

An abstract example of this concept can be demonstrated in constructing the architecture of a country.

Figure 3. How a country would be created by using subsumption architecture (Kevin Kelly, in his book Out of Control)

Subsumption architecture used in biologically analogous experiments is usually implemented to define individual behaviours, as the biological agent’s achievement is purely non-cooperative. The parallel principles can apply to systems with many agents, as the individuals can be seen as representing individual processes that run in parallel. Collective robotic behaviour has, in past experiments, reached a saturation point with relatively few robots, (Beckers et al 1994;Deneubourg et al 1991;Martinoli & Mondada 1995) - as every robot decides itself which action to take on the basis of its own perception, which is strictly local and private. No system/master is responsible for supervising the robots nor is there any type of cooperation protocol allowing the system to be flexible or fault tolerant. The computational paradigm is created through the performance of autonomous agents, which are considered to be embodied systems; designed to fulfil internal and external goals by their own actions in continuous long-term interaction with their environment. Simple behaviours (avoidance, aggregation, and dispersion) based on local sensing only, are combined so that global behaviours emerge through, sensing the environment, then detecting features and constructing a model for the task one step at a time while updating the world model. This leads to problems when cooperation between the individual agents is required to perform a task.

Work by Chantemargue and Hirsbrunner (1999) showed that in order to increase the probability of agent’s working in a parallel fashion, the use of richer perceptive capabilities rather than exclusively random moves need to be implemented, thus endowing the agent with the ability seek out an area of interest. Results indicate the global clustering is achieved and a positive correlation between the number of robots and the performance of the system.

Suggesting that behavioural autonomy at the level of the system, though operational at the level of each robot is able to exhibit the emergence of cooperation, since robots can be added or removed without destructive interferences among the agents. By organizing these simple robots into cooperating teams useful tasks may be accomplished tasks impossible using a single robot. In these systems there is an expectation, via the examination of the agent’s control algorithm that the global task can be achieved but the manner in which the task is achieved is driven at robot level. The required algorithm is necessarily more complex than that of the simple biological agent who does not share a common coordinate system. The algorithm needs to address how to appropriately divide the functionality of the decentralized system into multiple robots, and realise the dynamic configuration and cooperative behaviour through the development of an inter-robot communication mechanism.

Mataric and Fredslund (1999) used an algorithm where perceptive capabilities were incorporated, in that each robot referenced itself locally to on neighboring robot (friend) and keeps a certain bearing and distance. Through a sensor a unique ID is broadcast and detected so agents are aware of each other, formations are created via a calculation known as less than me, which determines the rank in the chain. Formations of columns, diamonds and wedges were successfully produced on most occasions (lines were unsuccessful). The success or failure of the formation was dependant on the angle required to maintain the relation with the agents “friend” (the greater the sum of the angles the more difficult the formation). The non-global heart-beat (unique ID) and minimal radio messages provided agents with the ability to “inform” each other and thus negotiate upcoming obstacles, originally through the adjustment in path by the conductor, who leads to all other agents who respond with the same degree of adjustment. The algorithm still incorporated simple behaviors, seen in biological agents, but added minimal communication behaviour and it this communication behaviour that makes cooperation of multiple robots feasible. The cooperative behaviours enable a team of mobile robots to accomplish tasks that cannot be easily achieved with an individual robot, and communication is the most common means of interaction among intelligent agents. Results indicate that the combination of simple local control and minimal communication was effective and robust. The emergence of the global formation behaviour results from the non-centralised coordinator agent “leading”, with other agents falling into position even though there is no agreed global heading. The behaviour is a positive feedback spiral.

Figure 5. Positive Feedback spiral of formation behaviour

The algorithm of multiple robot systems depends on the global task required. In biological systems all agents are able to operate as a self-organising system without direct communication on intention. Extending the planning paradigm from single to multi-robot domains requires algorithm expansion to include the state of each of the agents in which individual agent control strategies can be classified into;

Reactive, behaviour based (Deneubourg 1991)
Hybrid approaches (Fredslund and Mataric 1999)
Global communication (Qin Chen and Luh 1994).

The benefits of varying degrees of global knowledge could be evaluated in terms of position error and time to completed he task, allowing an algorithm to determine the minimal amount of communication required to perform the task within the specific environment.

In multi-robot systems all agents must communicate to varying degrees the intention to execute their part of the operation. However all the algorithms discussed use and depend on a relatively simple noise free environment, which is disparate to the environment the paradigm is attempting to replicate. The communication required by biological systems to perform tasks may be fundamentally made up of simple behaviours but they are living beings that are perhaps more than non-cooperative automaton-like robots carrying out mindless tasks. They have the capability to detect each other and their environment through their antenna and other senses, the amount of detection may not be fully understood but I believe they are more than “blind” agents performing tasks in a mechanized manner. They may not be socially aware in perhaps the sense that we understand, but they are aware of their colleagues to some degree. This would explain the need for a minimal communication algorithm in artificial agents created to perform biologically analogous tasks, which conversely implies that insects do communicate with each other.

A possible solution to the problem of inter-agent non-cooperation could be to return tot eh biological model and calculate a size ratio between the natural agent and the area of its environment E.g. Termite size in ration to the working arena of the individual termite. The outcome of a lack of cooperation Deneubourg, Martinoli & Mondada referred to in relation to the geometry of the environment may be solved by groups of agents using single agent subsumption architecture if an accurate and appropriate ratio is formed. By introducing mathematically “similar” sized environment more cooperative behaviour may result decreasing the need for more perceptive algorithms.

The scientific study of self-organizing systems is relatively new and the use of autonomous robots, will one day affect society in a fundamental way. Their uses could be diverse; from applications in hazardous environments perhaps in an automated environmental monitoring and cleanup to their ability to perform monotonous wall-following tasks such as street cleaning, robotics will prove to be the enabling technology of the next century.

, Looking instead for system properties applicable to all such collections of parts, regardless of size or nature. It is here that modern computers prove essential, allowing us to investigate the dynamic changes that occur over vast numbers of time steps and with a large numbers of initial options.

REFERENCES

R Beckers, R., Holland, O.E., and Deneubourg, J.L. From local actions to global tasks: Stimergy and collective robotics. In R.Brooks and P.Maeas, editors, Proceedings of the Fourth Workshop on Artificial Life, Boston MA, 1994 MIT Press.

Brooks, R.A., (1996) A Robust layered control System for a mobile Robot. IEEE Robotics and Automation RA (2): pp14-23.

Chantemargue, F & Hirsbrunner, B. A Collective Robotics Application Based on Emergence and Self-organisation. In

Cite Seer (1999). A Collective Robotics Application Based On Emergence And Self-Organization [online]

http://citeseer.nj.nec.com/chantemargue99collective.html [Accesses, April 7th 2003]

Chen, Q., & Luh., J.Y.S., (1994) Coordination and Control of a group of small mobile robots. In IEEE international conference on robotics and automation (ICRA-1994) pp 2315-2320, San Diego, 1994 In

Deneubourg, J.C. Goss, S. Franks, N. Sendova, A. Franks, Adetrin, . C. and Chatier, L.. The dynamics of collective sorting: Robot-like ant and ant-like robot. In J.A.Mayer and S.W.Wilson, (1991) editors Simulation of Adaptive Behaviour: From Animals to Animals, pages 356-365. MIT Press,

Farley, B. G., & Clark, W. A. (1954) Simulation of self-organizing systems by digital computer. I.R.E. Transactions on Inf. Theory 4, 76--84. In

Cite Seer (1999). A Collective Robotics Application Based On Emergence And Self-Organization [online]

Gaussier. P., & Zrehen, S., (1994) A Constructivist approach for autonomous agents. In D. Thalmann editor, Artificial Life in Virtual Reality, pages 97-113, London. John Wiley and Sons.

Kelly, K., Out of Control In

Küppers, G. (ed) (1996). Coping with uncertainty: New forms of knowledge production, in: AI & Soc 13, S. 52-62. In http://www.uni-bielefeld.de/iwt/sein/paperno2.pdf

Fredslund, J. & Mataric,M.J. A General Algorithm for Robot Formations Using Local Sensing and Minimal Communication

Martinoli, A & Mondada, F (1995). Collective and Cooperative Group Behaviours: Biologically Inspired Experiments in Robotics. In Proceedings of the Third International Conference on Robotics And Automation, Los Alemitos, 1992, IEEE. Computer Society Press. In Cite Seer (1999). Collective and Cooperative Group Behaviours: Biologically Inspired Experiments in Robotics [online]

[Accesses, April 7th 2003]

DIRECTLY CONSULTED MATERIAL

Arkin, R.C., (1998) Behaviour Based intelligence. MIT Press USA

Belch, T., & Arkin, R.C., (1998) Behaviour-based Formation Control of Mult-Robot Teams. IEEE Transactions on Robots and Automation, 14.6.

Mataric,M.J. From Local interactions to Collective Intelligence. In Cite Seer (1999). F. Chantemargue and B. Hirsbrunner. A collective robotics application based on emergence and self organization. In Proceedings of ICYCS, 1999

Mataric, M.J., (1995) Issues and Approaches in the design of Collective Autonomous agents. Robots and Autonomous Systems. 16 (2-4) Dec. 321-331.

Pfierfer R.M & Scheier, C., (1999). Understanding Intelligence. MIT Press: Massachusetts USA.

Resnick. M., (2001) Termites, Turtles and Traffic Jams; Explorations in massively parallel Miniworlds. MIT Press USA.

The scientific study of self-organizing systems is relatively new, although