|
A self-organizing system is a system that changes its basic structure as a function of its experience and environment. |
This definition clearly relates to today's "hot" topics of adaptive control, neural networks and genetic algorithms. We will also dwell upon neural networks and unsupervised learning briefly at the end of this chapter.
A self-organizing system has three main characteristics (or functions): affect, telos and effect [33]. To explain these three functions, we will use our Army-ant scenario as an example: A robotic agent in a multirobot network observes its environment (affect), using these observations decides what to do next (telos) and executes according to its decision (effect). In a population of Army-Ant robots dispersed in an area where several loads are located, agents recognize the situation by observing the signals coming from other agents and "goals" (affect), compute the direction of movement at each step (telos) and move (effect). On a large scale, the whole population receives signals (affect) and, guided by decision algorithms (telos), acts (effect).
One encounters self-organization in many fields. Biology (insect societies, ecosystems), chemistry ( thermodynamics), computer science (decision algorithms, neural networks and fuzzy logic), geology (tectonic movements), sociology (communication and migration) and economy (socio-spatial systems) are some areas where self-organizing systems are encountered often.
Nicolis and Prigogine [25], defining self-organization in nonequilibrium systems, stated that self-organization emphasizes the large scale coordination processes at many levels. Nonlinear processes and nonequilibrium conditions play a significant role in these processes. Kauffman [19] believes that self-organization, an "inherent property of some complex systems," may be responsible for biological evolution along with selection. His computer models suggest that certain complex biological systems tend toward self-organization.
In a self-organizing system, individual behavior need not be changed in order to have different collective behavior. This characteristic of self-organization is highly advantageous for a swarm of robots since simple individual behavior can be achieved with relatively cheap and simple designs.
Some animal societies and particularly social insects can achieve complex tasks that are impossible to complete individually. We will state some examples in the next section. On the other hand, simplicity (and homogeneity) of individual agents on a robotic swarm decreases the cost of production and the likelihood of the breakdown.
Furthermore, breakdown of one agent will not effect the activity of the whole robotic team, which may not be the case in a deterministic system such as a production chain. The simplicity would also be in software as well as in hardware. In a deterministic system, programs are highly complex, in order to operate in every possible situation harmful to the system, and it is still impossible to foresee them all. However in a self-organizing system, simpler programs can operate in unforeseen situations and adapt to changing conditions. For these reasons, self-organizing algorithms which have only partial (local) knowledge of the network are used to manage data networks of large numbers of users.
Advantages of self-organization and the efficiency in self-organizing behavior of
some animal societies, as they became known, caused interest in the use of
self-organization in robotics. To quote Deneubourg and Goss [11]:
|
Engineers are often, consciously or not, prisoners of the Cartesian and scientific positivist philosophy that dominates their education, and it is therefore not surprising that robot designers have chosen to develop expensive, complicated, deterministic robots, tailored to specific problems. We can now propose the completely different approach of using teams of simple, interacting robots to perform a wide range of tasks. |
It has been shown in [37] that elementary rules of individual behavior makes it possible for a society of Polistes wasps to make efficient decisions when certain types of external constraints are encountered, as well as to create complicated patterns. This, as we defined in the previous section, is an important characteristic of self-organizing systems. The model discussed in [37] is based on two different characteristics of individual interactions: (i) hierarchical and (ii) thropic.
Hierarchical interactions guarantee that, when two bees interact, one assumes a dominant role while the other is submissive. Some form of hierarchical interaction is also used in this research, as we attempt to define a coupled system of nonlinear oscillators in order to create a simple decision system in Chapter 4.
The thropic type of interaction controls the relationships between individuals and the environment, especially with the brood. For example, when food supply is insufficient, the intensity of the larval stimulation increases and consequently, the number of foragers also increases. This type of process has also been observed in ants [10, 38].
Although most work done on schools of fish studied species of fish that are consumed, some predators also form schools. If a member of the school finds food, the other members can take advantage of the find. If the members of the school remain barely in the sight of one another, the search area is at a maximum. Application of this idea to populations of multiple mobile robots for searching pollutants, for planetary missions or for detecting missile launches, is obvious.
Partridge [27] determined an interesting coordination in tuna schools. Tuna schools of 50 or more members sometimes divide into smaller groups which consist of between 10 and 20 fish. These fishes spread out along a curve very similar to a parabola with concave side forward. Although achieving a regular distance between individuals along a parabola is difficult , that form provides a considerable advantage in hunting. If the parabolic school swims parallel to its axis, any prey reacting to the curved school, will be driven to the focus of the parabola, which is the most convenient place for surrounding the prey.
Fish schools do not have a regular geometric form; the structure is loose or probabilistic and it results from each fish's applying a few simple behavior rules. First rule is that each individual maintains an empty space around itself. In general, only one neighbor at a time is at the preferred distance from a particular fish. (In a regular geometric shape, neighboring fishes would be at the same distance.) Fishes also tend to keep their neighborhood at a particular preferred angle with respect to their body angle. Most schools of fish are organized on the same lines: preferred distance and angle.
Experiments on pollock [27] showed that vision and lateral lines are two important senses fishes employ to match the speed and direction of other fishes. Blinded fishes and fishes whose lateral lines are removed were able to school. But blinded fishes swam farther from their nearest neighborhoods than pollock's ordinarily do, while fishes with lateral lines removed swam closer to the nearest schoolmate. Only when a fish was both blinded and had had its lateral lines removed it did fail to maintain its position in the school. Vision seemed to provide the "attractive force" between members while lateral lines provided the "repulsive force." Other research suggested that vision take precedence in case of contradictory information.
The formation of this complex structure involves pheromones . The insects follow two simple rules:
When a pillar develops on a site of an original deposit, its uppermost region, being the deposition point, acts as a point attractor for insects. When two pillars are sufficiently close to each other, a virtual saddle point midway between the pillars results. Therefore, insects first approach the saddle point and then converge to one of the pillars from the direction of the other. This behavior leads to the formation of an arch. And the formation of arches, creating new attraction points, can result new saddle points that guarantee the formation of a dome. The cycle can repeat when new deposit sites emerge on top of the dome.
Army ants, like other self-organizing insect societies, exist in large colonies. "If 100 ants are placed in a flat surface, they will walk around and around in never decreasing circles until they die of exhaustion. In high number however it is a different story." [15] The collective intelligence of the Army ants is an emergent behavior of the collective communication.
Computer simulation based on nonlinear equations [12] showed that ant colonies are able achieve a collective spatial and temporal structure in raids without global coordination, but instead through the communication between foragers by laying down of trail pheromones, which they also react to. On the other hand, Deneubourg, et al, demonstrated that, although their mathematical model was very crude, certain amount of "noise" during foraging can be advantageous. Their model shows that a given amount of noise in the food recruitment process is needed to optimize food gathering when a multiple and aggregated source situation is present [9]. They also stated that the emergence of error could be regulated by the nature of the system of communication itself.
In a similar work [28], it is demonstrated that trail recruitment to newly discovered food sources in ants can be simulated using unspecialized identical units with a very simple program, no memory and a large stochastic behavior as a model. Even when the characteristics of behavior and communication in ants are oversimplified, the mathematical model was able to generate the integrated behavior observed in experiments with ants.
Each level generates a behavior and the competence of the robot is improved by addition of new layers. The subsumption architecture is based on decomposition of a mobile robot in terms of behavior rather than in terms of functional modules. Since the overall control system can be viewed as a system of agents acting separately, there is no need for a central control module.
An example of subsumption architecture is Squirt, a very small intelligent mobile robot. Squirt acts as a bug, hiding in dark corners and venturing out in the direction of noises, only after noises are gone, looking for a new place to hide near where the previous set of noises came from. The most interesting fact about Squirt is the way in which its high-level behavior, mentioned above, emerges from a set of simple interactions with the environment. Squirt's lowest level of behavior causes the robot to search for darkness. The second level of behavior is triggered once a dark spot has been found. Monitoring two microphones, the direction from which the noises come is detected, and when a few minutes of silence follows a sharp pattern of noise, Squirt moves in the direction of the last heard noise, suppressing the desire to stay in the dark. After a time-period, the first level is no longer suppressed and becomes active. This "bug behavior" fits in 1300 bytes of code on an 8-bit microprocessor [8].
The subsumption architecture has also demonstrated robust navigation for mobile robots in dynamically changing environments. Its layered structure is well-adaptable for hardware implementation.
The identifier constructs a local representation of the surroundings based on information obtained from sensors, and determines the speed of obstacles. Goal selector uses the map and speed of the obstacles and finds a locally optimal collision-free path satisfying other possible conditions. The adapter consists of two subsystems: one for path smoothing to avoid sharp turns and the other for determination of steering command (based on potential field path planning).
Problems often encountered in autonomous navigation models are (i) delay in feedback information, (ii) sensor and servo errors, and (iii) limited sensor range [14]. Due to the large amount of computation required to process the sensor data, a delay is expected in obtaining the local map. For Army-ant robots, this would not be a problem since Army-ant scenario does not include any map and/or path finding algorithms. Again sensor and servo errors create a problem for map building robots. Limited sensor range may cause a problem in obstacle avoidance. However, it is possible to overcome this by adjusting the speed of rovers according to the visibility range of the sensors.
On the other hand, Arkin, describing path planning and navigation as a collection of behaviors, use motor schemas to obtain a reactive navigation method for autonomous robots. Motor schemas serve as the basic unit of behavior specification for the navigation; they are concurrent processes that operate in conjunction with associated perceptual schemas and contribute independently to the overall action of the robot [3]. A variant of the potential field method is used to produce the appropriate velocity and steering commands. Motor schemas, such as move-ahead, move-to-goal, avoid-obstacle, which can be visualized as vector fields, are represented as asynchronous computing agents in terms of addition and multiplication.
The output of a schema is a single velocity vector derived from a potential field formulation of the forces exerted upon the robot at any particular point in space. The entire potential field is never computed; thus, the computational demand for a single schema is small. The output of each motor schema is combined using vector summation, and then normalized. Arkin's model includes a low-magnitude random vector that changes at random time intervals in order to remove the robot from undesirable equilibrium points that arise when active motor schemas balance each other. Also, gains of schema outputs can be changed (depending on established real-time deadlines for goal attainment) in order to allow a blocked robot to bypass obstacles. Arkin states that what might appear to be a naive approach, the summing of individual vector outputs of the "schemas," works quite well, both in simulations and real world experiments.
Although most reactive systems are not concerned with the use of world knowledge (map), Arkin's autonomous robot architecture [4] includes a priori information about the environment. The Army-ant scenario is closer to Brooks' works, which avoid "world modeling" for individual insect-like robots (such as Squirt and Genghis, a six-legged robot).
Systems of multiple mobile robots have gained interest in recent years when projects such as planetary surface mission and hazardous waste management, emerged. Large populations of mobile robots, as decentralized robotic systems (DRS), have many advantages over centralized systems, especially when high reliability is required, such as maintenance tasks in nuclear power plants.
The application of multiple mobile robots to planetary missions is outlined by Miller in [24]. This work states the fact that teams of small autonomous robots have advantages, such as lower cost, lower launch/landing mass and mission reliability, over larger robots. Behavior driven control methods described in the previous section are likely to be used in designing such small robots. The use of fixed radio beacons is also anticipated along with the necessity of leader selection for formation of a coordinated team. Leader selection can be achieved by assigning serial number to robots. Robots are assumed to be able to transmit/detect these numbers, and the one with higher serial number will be collectively elected as leader.
Miller also emphasize the fact that coded beacons and beacon readers on each robot , with other simple broadcast signals, could be sufficient to achieve a complex task with individual behavior, since navigation and homing techniques are well developed for autonomous mobile robots.
The term "distributed robotic system" (DRS) is sometimes used to describe a multirobot system based on instinctive responses and cooperation. Simulations of DRS designed for searching for pollutants are created by Genovese, et al. [16], based on biological systems and subsumption-like architectures. This design suggests a supervising user who can localize agents whenever necessary. In this context, the system is not a "swarm." Communication between agents is more complex than the one described by Miller and includes coded radio transmission on a single channel. Although this model includes "acknowledge" messages, this type of communication proves to be advantageous, as we investigate in Chapter 4.
In [6], Beni and Wang claim that all agents involved in an operation must communicate to each other the intention to execute their part of operation. Stating that the "commitment protocols" are basic building blocks of distributed computing algorithms, such communication is defined as a required characteristic. On the contrary, biological systems described in Section 2.2 are able to operate as a self-organizing system without direct communication (of intentions). The key factor here is the large number of agents. But again, in our Army-ant scenario, there may be a situation where number of agents at each "goal" is not sufficient to start the next phase. A temporary "do-not-consider-this-goal" signal can be introduced by the leader to overcome this problem.
Previous experimental works on multiple mobile robots include ACTRESS (ACTor Based Robots and Equivalent Synthetic Systems) developed by Habib et al. [17], and Yamabica robots realized by Yuta and Premvuti [40]. ACTRESS, as an autonomous and decentralized robotic system, does not only have mobile robots, but also any kind of robotic system and/or computers. Mobile robots developed for ACTRESS have a portable computer instead of an onboard microprocessor and weigh 51 kg. They demonstrated intelligent navigation behavior.
Yamabica robots, more compact than above-mentioned robots, are used to determine a solution for a deadlock situation caused by multiple mobile robots with overlapping running courses in aisles. The method described in [40] provides a shunting process to solve the deadlock. However it requires constant broadcast of information (e.g., current position), a world knowledge, and is based on complex decision modules "managing" the information obtained from sensors. Both ACTRESS and Yamabico models differ from our approach to self-organization in many contexts.
Part of the work on spatial self-organization in this thesis (Chapter 3) is inspired by an interesting work by Sugihara and Suzuki [35]. They give a method for motion coordination of a group of mobile robots. Each robot plans its motion individually based upon a defined goal and detected position of other robots. This method is fully distributed in that sense and shows that intelligent behavior can emerge from simple individual behavior.
Sugihara and Suzuki were able to create different geometric shapes by defining simple algorithms to be executed by a large number of agents. Their simulation shows that robots can form lines, circles, polygons and distributes themselves within a circle or convex polygon in the plane. Although the algorithms defined in [35] are shown to work quite well, most of these algorithms are based on the assumption that each robot can detect the distance from the farthest teammate (as well as the distance from the nearest teammate). In this research, we use the advantage of a goal beacon and eliminate the need for the distance from the farthest agent in computations.
Neural networks are characterized by having (i) a large number of neuronlike processing elements, (ii) a large number of weighted connection between these elements, (iii) highly parallel, distributed control and (iv) an emphasis on learning internal representations automatically [31]. Knowledge of the network is "encoded" in the weights between neurons.
Artificial neural networks are currently used in the fields of signal processing, speech recognition, visual perception, control and robotics. Neural networks help solve problems encountered in these fields with natural mechanism of generalization, and have the most promise in real-world problems.
Based on a "prototype" model, NNs naturally develop a category structure, "classification by similarity", which enables the use of NNs in speech recognition, visual perception, etc. However, the same characteristic is a serious potential weakness. For example, it is highly difficult for a simple NN to detect the parity of bit vectors.
NNs deal with uncertainty, not by calculated design, but as a result of the parallel-distributed structure. It is equally possible to directly build insights about categorization into an artificial system. Fuzzy systems are the result of this approach. When such insights are properly quantified, fuzzy systems can be just as well defined and useful as the traditional formulations of probability and statistics. In 1965, Lotfi Zadeh formally developed multivalued set theory and introduced the term "fuzzy" into technical literature. Neural networks and fuzzy systems estimate input-output functions, and both are trainable dynamical systems. Sample data affects their time evolution. Unlike statistical estimators based on mathematical models, they are model-free estimators. They "learn from experience" [21].
Artificial neural networks can be programmed and trained to estimate sampled functions whose form is unknown. Many feedback neural networks can learn new patterns and recall old patterns simultaneously. Supervised neural networks can learn far more input-output pairs than the number of neurons and synapses in the network. Since there is no input-output model of the system, the same neural-network architecture and dynamics can be applied to different problems.
Fuzzy systems are based on storage of "common-sense" rules [21]. For example, a fuzzy Army-ant robot controller might have the fuzzy association "if load is heavy, then signal for help longer." Fuzzy phenomena admit degrees: some loads are heavier than others; some signal durations are longer then others. A single association (heavy,longer) encodes all combinations. Fuzzy systems are newer than neural systems. Yet there are successful applications of fuzzy systems in many areas, such as automation of subways, camera focusing, automobile cruise control, etc. Fuzzy systems "reason" with parallel associative inference. A fuzzy system reasons with multivalued sets, instead of true or false propositions, and it may adaptively modify its fuzzy associations from representative numerical samples.
Kohonen introduced a self-organizing algorithm that produces a global ordering over the network. To every cell in the network, a reference vector is assigned and the same input vector is fed to all cells. The unit whose reference vector matches the input best, is chosen as "winner." To implement a process in which reference vectors are ordered spatially, it is necessary to update reference vectors in blocks, concentrated around the winners. Due to frequent overlap of such blocks in learning and similar correction imposed in each block, the values of reference vectors tend to be smoothed and to become ordered. Updating is always restricted to a topological neighborhood of cells. Size of the neighborhood decreases monotonically. At the end of the process the neighborhood for each cell contains the closest cells, not only the unit itself. If the neighborhood consists of only the unit itself, the map will degenerate into the zero-order topology model.
The number of training steps in the map method is approximately the same as in traditional neural networks. In [18], it is stated that statistical accuracy for phonemic recognition achieved with the map method and learning vector quantization algorithms exceeded the results provided by more conventional Neural Networks.
To Chapter 1
To Chapter 3