Скачать 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 reactiondiffusion systems; by direct analogy with a biological swarm system of ants, a swarmbased method is developed for the approximation of the minimum spanning tree (MST) and relative neighbourhood graph (RNG) of an arbitrary graph. Introduction 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), selforganization (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. Background 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). Agentbased 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 prerational 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 prerational (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 socalled 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 (Nagent) operates as follows: (1) it moves in the initially chosen direction until it undergoes interaction or collision with another Nagent or obstacle, (2) it changes its state (and velocity vector) as a result of at least one instance of interaction or collision with other Nagents. Definition 8. A natural agent (Nagent) is a minimal movable compact indivisible cluster of a finite number of nonrest 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 Nswarm system if Nagents occur in the evolution of . Three species of twodimensional CA which exhibit particlelike behaviour are known in reasonable detail. They are the Life game developed by Conway (see e.g. Berlekamp et al., 1982), Flexica (Symmetr4 rule) (GordonSmith, 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 1state at time will be in the same state at time if it has exactly or neighbours in the 1state. A cell changes the 0state into the 1state if there are exactly neighbours in the 1state in its neighborhood. A cell of GordonSmith’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 Nagents 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 Nswarm. 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 Nagents which are minimal in size and density. (It can also be shown that it has the most compact, dense and smallest generators of Nagents, as well as the minimal period of 'reproduction' for Nagents; calculations of the total update times of the cells involved show the minimality of 2^{+ }medium in time.) Interactions between Nagents 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 Nswarms in cellularautomata models in the situation where we do not know the exact form of the Nagents. 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 Nagents 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 Nswarms in cellular automata is that (i) all initially random configurations must exhibit bounded growth and (ii) Nagents 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 cellularautomata model of an excitable medium will consitute an Nswarm 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 quasistationary configurations with Nagents. The idea is that after a period of unstructured excitation dynamics, all nonminimal movable patterns will have disappeared, all Nagents moving along intersecting trajectories will have collided with one another, and we will therefore be left with a system where Nagents run on nonintersecting trajectories. This procedure will probably also work for reactiondiffusion 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 nonrest 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 nearcritical values of are characterized by complex behaviour, and exhibit particlelike patterns of nonrest states, i.e. they support Nswarms. 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 Nagents in excitable media (Adamatzky and Holland, 1996). The parameter, introduced by Wuensche (1992, 1994), uses the notion of partial preimages 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 preimage has a unique value. It predicts the global dynamics of cellular automata very well (at least in the onedimensional automata investigated by Wuensche), also accounting for the density of nonconstructible configurations. The parameter can be used to detect Nswarms 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 Nagents detected in onedimensional cellular automata with complex rules is shown in (Wuensche, 1994). Claim 2. Let be the onedimensional cellular automaton of cells, each of which takes states and has neighbours: then Nswarm agents which have a size of cells can be identified in in a time proportional to . The procedure for searching for Nagents is based on the exploration of local characteristics of spacetime patterns of a onedimensional 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 socalled 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 Nagent (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 Nagents. 
«инструменты для анализа данных, построения отчетов и запросов могут помочь бизнеспользователям преодолеть море данных для того,...  