Скачать 91.42 Kb.
|Swarm Intelligence: Representations and Algorithms|
Andrew Adamatzky and Owen Holland
Intelligent Autonomous Systems Laboratory, University of the West of England, Frenchay Campus, Coldharbour Lane, Bristol BS16 1QY, United Kingdom
Physical swarm systems are found in biology and robotics; this paper examines the representation of swarm systems in the abstract domain of cellular automata. Certain types of swarm phenomena appear to be quite natural to this domain; techniques for the automatic identification of such phenomena are developed, and the complexity and efficiency of the underlying computations are evaluated. The approach is extended to the consideration of swarm models of reaction-diffusion systems; by direct analogy with a biological swarm system of ants, a swarm-based method is developed for the approximation of the minimum spanning tree (MST) and relative neighbourhood graph (RNG) of an arbitrary graph.
There are two main sources for the emerging theory of physical swarm systems: social insects in mathematical biology, and groups of interacting autonomous robots in engineering. Within mathematical biology, notions of swarm systems were developed in (Deneubourg, 1987; Deneubourg, 1990); however, some of the earliest ideas can be found in the area of biological cybernetics (Tsetlin, 1969). Within robotics, key early papers are (Beni and Wang, 1989; Dudek et al., 1993). Provisionally, a swarm system can be defined as a collection of autonomous mobile agents interacting with one another directly and locally, or indirectly (via changes in the environment), and which collectively solve some distributed problem. In recent years, the theory and application of swarm systems has developed in such as the characterisation of the features of ant societies (Zakharov, 1991, Holldobler and Wilson, 1995), self-organization (Willson and Holldobler, 1987, Rauch et al., 1995, Theraulaz and Bonabeau, 1995), the design of emergent robotics systems (Deneubourg et al., 1990, Beckers et al., 1994), and algorithms for stochastic optimization (Schonderwoed at al., 1996, Dorigo et al., 1996).
In the paper we will suggest a set of definitions of swarm systems, and show how such systems are related to discrete dynamical systems with static agents (cellular automata). The suitability of swarm algorithms for solving graph problems will be demonstrated in a new method for the approximation of the planar minimum spanning tree.
The following definition is adapted from the papers of theoretical biologists studying social insects (Deneubourg et al., 1995, Theraultz et al., 1990).
Definition 1. A swarm is a set of mobile agents able to communicate each with another directly or indirectly, to form and reconfigure functional patterns, and to collectively solve various problems by acting in parallel.
An abstraction from robotics is very similar:
Definition 2 (from Dudek et al., 1993). A swarm is a reconfigurable network of communicating agents capable of coordinated sensing and interaction with the environment.
In the archaeological context, an agent is a generator of behaviour, and interactions among agents are the source of structure (i.e. agents change the environment) (Haas, 1996). Agent-based concepts are also used in the analysis of economic systems. In most cases, the term 'agent' refers to a cell of a cellular automaton, which of course is static (Drazin and Rao, 1996, Ionnanides, 1996).
Definition 3. A swarm is a set of pre-rational entities acting and communicating locally.
Physically based swarm entities interact with each other locally in space and time. Typical biological agents have bounded memory (or have none at all), and sensors with limited capabilities. Swarm entities are agents because they are responsible for some acts or actions, and produce certain effects. Agents in a swarm are not able to reason, and so cannot explain or manipulate their belief or knowledge; they may therefore be though of as pre-rational (Holland, 1994).
In other words, swarms are social insects for biologists, agents for psychologists, economists and specialists in intelligent systems, and robots for the engineers.
Since agent motion is fundamental to ideas of physical swarms, methods of describing motion are of importance. The axiomatic approach to discrete image geometry, including the notions of translation and parallelity and the betweenness relation for point triples is discussed in (Hubler, 1989) as well as discrete motion; some basic facts on neighbourhoods in discrete planes can be found in (Yaroslavskij et al., 1987). Note that there is an opportunity for eliminating coordinate system in the definition of swarm systems which move autonomously: we may use axioms for directed fields, or analytically ordered Euclidean planes without coordinates (Prazmovski, 1987). Some basic mechanisms of motion in agents with simple sensors have been investigated (Holland and Melhusih, 1996). Another characteristics is communication between agents via the environment, or stigmergy, which is an important feature of terrestrial swarms (Beckers et al., 1994).
Definition 4. A swarm system is a tuple where is a set of agents, is a set of agent states, is a set of velocity vectors, , is an agent’s state transition function, , is a velocity vectors function, , is a translation function, and is a neighbourhood function, , , , , .
For any agent , the neighbourhood is , where for and , , . In this definition we have assumed that agents and elements of the environment can both be represented by finite automata.
Definition 5. A cellular automaton is a tuple of a -dimensional array of uniform cells, , ; is a finite set of cell states, , and the two mappings and , , are called the neigbourhood and cell state transition functions respectively. Every cell changes its state in discrete time by the rule .
Definition 6. The minimum spanning tree (MST) of the set , , is the connection of elements of by straight lines such that there is a path of lines between every pair in the set, the line segments connecting points do not intersect anywhere in the plane except at the points of , there are no cycles, and the sum of the lengths (weights) of all edges is minimal.
The edges of the MST of will be denoted as .
In the computation of MST using a swarm, we will use the so-called relative neighbourhood graph (RNG) which is defined in the following way (Jaromczyk and Toussaint, 1992):
Definition 7. Let be an open sphere with centre at and radius ; then for a given finite planar set , the relative neighbourhood graph is a graph such that for any : iff ; in other words, the intersection of spheres centred at points and with radius equal to the distance between and does not contain points of .
A detailed description of the algorithm for computing RNG can be found in (Jaromczyk and Kowaluk, 1980). About twenty years ago Toussaint (1980) proved that , where is a Delanue triangulation. The computation of MST based on RNG was demonstrated by Supowit (1988).
Swarms in Cellular Automata
A natural agent (N-agent) operates as follows: (1) it moves in the initially chosen direction until it undergoes interaction or collision with another N-agent or obstacle, (2) it changes its state (and velocity vector) as a result of at least one instance of interaction or collision with other N-agents.
Definition 8. A natural agent (N-agent) is a minimal movable compact indivisible cluster of a finite number of non-rest states that, in the absence of obstacles, moves on lattice without stopping during the evolution of cellular automaton .
Definition 9. The cellular automaton represents an N-swarm system if N-agents occur in the evolution of .
Three species of two-dimensional CA which exhibit particle-like behaviour are known in reasonable detail. They are the Life game developed by Conway (see e.g. Berlekamp et al., 1982), Flexica (Symmetr4 rule) (Gordon-Smith, 1997) and the 2+-medium (Adamatzky, 1995, 1996).
In the cellular automaton representing the Life game, cells take states from the set , and update their states by the rule
Every cell in the 1-state at time will be in the same state at time if it has exactly or neighbours in the 1-state. A cell changes the 0-state into the 1-state if there are exactly neighbours in the 1-state in its neighborhood.
A cell of Gordon-Smith’s cellular automaton Flexica behaves as follows: it takes the 0 state if all its neighbourhood is in the rest state; it keeps its current state if only one neighbour is in the 1 state; it changes its state to the opposite if its neighbourhood is unchanged by at least one of the reflections in a horizontal, vertical, or diagonal line through the centre of the neighbourhood, or by 180Error! Bookmark not defined. degree rotation around the centre; it takes the 1 state if it has exactly 5 neighbours in the 1 state and its neighbourhood has three 1 states on one side and two 1 states on the opposite side; and takes the 0 state in all other situations. The cell state transition rule is as follows:
where predicates and are defined as follows:
Cells of the 2+-medium take their states from the ternary set , denoting the rest state, , excited state, , and refractory state, . Every cell at rest becomes excited if exactly two neighbours are excited, and passes from the excited state into the refractory state, and from the refractory state to the rest state unconditionally in successive time steps:
, where .
There are only a small number of N-agents in these types of cellular automata: spaceships and gliders in Life, gliders in Flexica, and 2+ and 3+ particles in the 2+ medium.
Proposition 1. The 2+ particle is a minimal N-swarm.
The density of the minimal mobile patterns in these cellular automata types are (Life), (Flexica) and (the 2+ medium). The 2+ medium thus supports the N-agents which are minimal in size and density. (It can also be shown that it has the most compact, dense and smallest generators of N-agents, as well as the minimal period of 'reproduction' for N-agents; calculations of the total update times of the cells involved show the minimality of 2+ medium in time.)
Interactions between N-agents in the models discussed above have been investigated in (Berlekamp et al., 1982, Adamatzky, 1995, 1996).
To complete this section, we will examine the problem of finding N-swarms in cellular-automata models in the situation where we do not know the exact form of the N-agents. The set of methods can be divided into two classes: (i) evaluation of global dynamics, and (ii) investigation of local characteristics.
First ideas on the search for N-agents concern the rate of configuration growth. In spite of the fact that glider guns were used to prove that Life exhibits spatially unlimited growth (Berlekamp et al., 1982), the empirical condition for candidates for N-swarms in cellular automata is that
(i) all initially random configurations must exhibit bounded growth and
(ii) N-agents can exist and will naturally occur,
when we repeatedly apply the cell state transitions rule to the configurations of the cellular automaton (see e.g. Bays, 1991). A more simple and explicit criterion emerged during our investigation of the families of excitable media with different intervals of excitation (Adamatzky and Holland, 1996).
Claim 1. A cellular-automata model of an excitable medium will consitute an N-swarm if the number of rest states becomes constant under periodic boundary conditions after a long enough induction period.
This criterion rejects the kinds of medium exhibiting oscillating patterns and wave generators, but it allows the efficient discovery of quasi-stationary configurations with N-agents. The idea is that after a period of unstructured excitation dynamics, all nonminimal movable patterns will have disappeared, all N-agents moving along intersecting trajectories will have collided with one another, and we will therefore be left with a system where N-agents run on non-intersecting trajectories. This procedure will probably also work for reaction-diffusion media, and their relatives such as systems of interacting populations.
Two parameters computed on cell state transition rules have been proposed which claim to capture the relationship between the static properties of cellular automata and their dynamical behaviour. The first is the parameter (Langton, 1990): is the fraction of non-rest states in the rule table of the cellular automaton. The transition of from 0 to (), where is the number of cell states, is held to correspond to a 'phase transition' from ordered behaviour, i.e. fixed points and limit cycles with short transient periods, to chaotic behaviour, also with short transient periods. Automata with near-critical values of are characterized by complex behaviour, and exhibit particle-like patterns of non-rest states, i.e. they support N-swarms. We believe that the domain of this procedure using the parameter is probably limited to cellular automata with binary cell states, because it does not appear to work when searching for N-agents in excitable media (Adamatzky and Holland, 1996).
The parameter, introduced by Wuensche (1992, 1994), uses the notion of partial pre-images of some specified state, i.e. the state of the neighbourhood when the cell takes this state, and reflects the probability that the next cell to the right (left) in the partial pre-image has a unique value. It predicts the global dynamics of cellular automata very well (at least in the one-dimensional automata investigated by Wuensche), also accounting for the density of nonconstructible configurations. The parameter can be used to detect N-swarms in cellular automata belonging to the class with complex behaviour () that is characterized by balanced convergence, the density of nonconstructible configurations, and moderately long transient cycles. A wide spectrum of N-agents detected in one-dimensional cellular automata with complex rules is shown in (Wuensche, 1994).
Claim 2. Let be the one-dimensional cellular automaton of cells, each of which takes states and has neighbours: then N-swarm agents which have a size of cells can be identified in in a time proportional to .
The procedure for searching for N-agents is based on the exploration of local characteristics of space-time patterns of a one-dimensional cellular automaton using the algorithm introduced in (Crutchfield and Hanson, 1993). It uses a mask which interacts with binary strings and configurations, and detects what are essentially phase defects. The so-called domain filter (a finite state transducer) scans cells of the automaton in the specified direction, reads it state by state, and maps the states corresponding to an N-agent (a defect or defect wall) to another configuration that represents movable patterns (Hanson and Crutchfield, 1996). From this, we obtain for the computation of , and for the scanning of the CA configuration and the detection of N-agents.
«инструменты для анализа данных, построения отчетов и запросов могут помочь бизнес-пользователям преодолеть море данных для того,...