Intelligent Systems 

Discussion group on Entropy and Self-organisation in Multi-Agent Systems

Entropy,  Extropy,  Cellular Automata,  Chaos

Chris Lucas essay on Self-Organization & Entropy - The Terrible Twins.

      Introduction. Many people will have heard of the Second Law of Thermodynamics. That's the one that states that the Universe is forever running down towards a "Heat Death". It is based on the concept of Entropy. This has several definitions - the inability of a system to do work; a measure of the disorder in a system and the one most often used nowadays - the tendency of a system to enter a more probable state, usually described as being to create chaos from order. Here we will look at the opposite idea, that order and not chaos is the most probable state.

Rajesh R. Parwani introduction to Complex Systems. Also a course on Complexity.

      Complexity refers to the study of complex systems, of which there is no uniformly accepted definition because, well, they are complex. Roughly speaking, one says that a system is complex if it consists of many interacting components (sub-units) and if it exhibits behaviour that is interesting but at the same time not an obvious consequence of the known interaction among the sub-units.

H. Van Dyke Parunak,  Sven Brueckner. Entropy and self-organization in multi-agent systems. Proceedings of the fifth international conference on Autonomous agents. 2001.

      Abstract. Emergent self-organization in multi-agent systems appears to contradict the second law of thermodynamics. This paradox has been explained in terms of a coupling between the macro level that hosts self-organization (and an apparent reduction in entropy), and the micro level (where random processes greatly increase entropy). Metaphorically, the micro level serves as an entropy “sink”, permitting overall system entropy to increase while sequestering this increase from the interactions where selforganization is desired. We make this metaphor precise by constructing a simple example of pheromone-based coordination, defining a way to measure the Shannon entropy at the macro (agent) and micro (pheromone) levels, and exhibiting an entropybased view of the coordination.

Christopher Langton. "Computation at the Edge of Chaos: Phase Transitions and Emergent Computation." In Emergent Computation, edited by Stephanie Forest. The MIT Press, 1991. Pages 12-37. 

      Abstract. A technical paper in which Langton explains his investigation of one-dimensional cellular automata and discusses the "lambda" parameter.

Andrew Wuensche. Classifying Cellular Automata Automatically; Finding gliders, filtering, and relating space-time patterns, attractor basins, and the Z parameter.

       Abstract. CA rules can be classified automatically for a spectrum of ordered, complex and chaotic dynamics, by a measure of the variance of input-entropy over time. Rules that support interacting gliders and related complex dynamics can be identified, giving an unlimited source for further study. The distribution of rule classes in rule-space can be shown. A byproduct of the method allows the automatic filtering" of CA space-time patterns to show up gliders and related emergent configurations more clearly. The classification seems to correspond to our subjective judgment of space-time dynamics. There are also approximate correlations with global measures on convergence in attractor basins, characterized by the distribution of in-degree sizes in their branching structure, and to the rule parameter, Z. Based on computer experiments using the software Discrete Dynamics Lab (DDLab), this paper explains the methods and presents results for 1d CA.

Stephen Wolfram. Cellular Automata as Models of Complexity. Nature, 311, (October 1984)

      Abstract. Natural systems from snowflakes to mollusc shells show a great diversity of complex patterns. The origins of such complexity can be investigated through mathematical models termed `cellular automata'. Cellular automata consist of many identical components, each simple, but together capable of complex behaviour. They are analysed both as discrete dynamical systems, and as information-processing systems. Here some of their universal features are discussed, and some general principles are suggested.

W.A. Wright, R. E. Smith, M. Danek, P. Greenway. A Measure of Emergence in an Adapting, Multi-Agent Context. 

      Abstract. In adaptive systems that involve large numbers of agents, emergent, global behaviours that arise from local agent interactions are a critical concept. In nature, such behaviours are central complex group behaviours that must arise from individuals that evolve selfishly. In artificial systems that mimic these adaptive, multi-agent models, understanding and shaping emergence may be essential to such systems' success. To aid in this understanding, this paper introduces a measure gleaned from statistical physics and non-linear systems theory. Unlike other measures of this sort, the one presented here is easy to calculate and can be used for any system that can be described by a set of local state variables centred on each of its constituent agents. It is shown that the measure can be successfully employed as feedback to an optimising genetic algorithm (GA), and to a GA that has similarities to a learning classifier system. The paper concludes that this measure (and others like it) may be a useful tool for understanding and shaping emergent behaviours, and discusses future directions for its use.

Contact:

Dr Mikhail Prokopenko
Tel : 61 (02) 9325 3264
Fax: 61 (02) 9325 3200
mikhail.prokopenko@csiro.au