Imagine it is the year 2061 and your shipboard nanobots attempt to repair some meteor damage. Do you trust them to do the job right?
It is increasingly apparent that collections of distributed adaptive agents (such as nanobots, robots, androids, etc.) will be increasingly important for the accomplishment for various real-world tasks. Distributed agents provide increased capacity for fault tolerance, self-repair, and self-assembly. Fault tolerance is the continued ability of distributed agents to perform a task after damage, albeit at a slightly lower efficiency level. Self-repair is the ability to restore optimal efficiency. Self-assembly is the ability of the initial system to construct itself, thus achieving great cost efficiency. These capacities would hold regardless of scale (i.e., ranging from nanobots and "smart matter" to space platforms).
However, the complexity of having collections of distributed adaptive agents raises important concerns as to the trustworthiness of the agents. Our goal, then, is to ensure that collections of agents are subject to rigorous constraints on their behavior.
We are pursuing two approaches. The first relies on the concept of "emergent phenomena." Emergent phenomena refers to the observation that complex global behavior can "emerge" naturally (and often surprisingly) from collections of agents subject only to simple local interactions. Thus, with this approach the goal is to define local interactions that result in the proper global behavior, without the need for a high-level global controller. In this approach constraints emerge from the local interactions. An example of this is provided in [1], which illustrates how global speciation can occur by the addition of simple local tags to individuals in an evolutionary algorithm. Another example is provided by our work in Artificial Physics / Physicomimetics.
The second approach lessens the engineering burden by relying instead on evolutionary techniques. Rather than engineer the local interactions, the system evolves the local interactions between agents, until the desired global behavior emerges.
In either approach, any resulting local interactions will require rigorous verification to ensure that global constraints are guaranteed satisfied (see efficient verification of adaptive systems).
[1] Spears, William M. (1994). Simple Subpopulation Schemes. In Proceedings of the Evolutionary Programming Conference, 296-307.
Most of our theory has focused on evolutionary algorithms, since they are complex adaptive systems that defy conventional analysis. We have taken a multi-faceted approach, in the belief that it is unlikely that one form of theoretical analysis will be sufficient for full understanding. For example, we have performed schema analyses of recombination and mutation in evolutionary algorithms, helping us characterize when recombination and mutation will help/hinder performance. We have examined the limiting distributions of populations undergoing recombination and/or mutation. Also, we have derived expected performance models of EAs with selection and mutation and have performed Markov chain analyses of full evolutionary algorithms with selection, recombination and mutation. Details about these analyses can be found in [2].
Other theory has focused on No-Free Lunch theorems for classification and search [3]. For a collection of papers on this topic click here.
[2] Spears, William M. (1998). The Role of Mutation and Recombination in Evolutionary Algorithms. Ph.D. Dissertation, George Mason University, Fairfax, Virginia.
[3] Rao, R. B., Diana F. Gordon, and William M. Spears (1995). For Every Generalization Action, is There Really an Equal and Opposite Reaction? Analysis of the Conservation Law for Generalization Performance. Proceedings of the Twelfth Int'l Conference on Machine Learning, 471-479.
Two sets of tools have been created for the analysis of complex adaptive systems. The first set deals with the automatic aggregation of models of complex systems -- the aggregation simplifies the model without introducing significant error. The most general tool is for general complex adaptive systems that can be described via Markov chains. Since the chains for most interesting complex systems have a huge number of states we have created an algorithm for compressing large Markov chains into Markov chains with far fewer states [5]. A more specific tool performs aggregation of simple evolutionary algorithms with selection and mutation, with fitness functions of a certain class [4].
[4] Spears, William M. (1999). Aggregating Models of Evolutionary Algorithms. Conference on Evolutionary Computation.
[5] Spears, William M. (1998). A Compression Algorithm for Probability Transition Matrices. In SIAM Matrix Analysis and Applications, Volume 20, #1, 60-77.
The second set of tools is called "test problem generators". Many complex adaptive systems run in an environment (for example, evolutionary algorithms run within the environment of a fitness function). In order to understand the behavior of these systems, various ad hoc environments are often created. We propose instead to use generators for those environments. The generators produce random environments within a certain class. Each generator is a black box with knobs that can be adjusted. Changing the knobs changes the characteristics of the environment. The goal is to match algorithm performance with environment characteristics. We have investigated test problem generators that produce fitness functions of varying epistasis and multimodality, yielding useful insights into the behaviour of evolutionary algorithms [6][7]. These particular test problem generators are based on classes of boolean satisfiability problems, that are mapped to real-valued fitness functions [8][9][10]. For more information on the generators click here.
[6] Kennedy, James, and William M. Spears (1998). Matching Algorithms to Problems: An Experimental Test of the Particle Swarm and Some Genetic Algorithms on the Multimodal Problem Generator. Proceedings of the IEEE Int'l Conference on Evolutionary Computation. Warning - the PostScript was generated by Microsoft Word. I'm unable to display the paper, but I can print it.
[7] De Jong, Kenneth A., Mitchell A. Potter, and William M. Spears (1997). Using Problem Generators to Explore the Effects of Epistasis. Proceedings of the Int'l Conference on Genetic Algorithms.
[8] Spears, William M. (1996). Simulated Annealing for Hard Satisfiability Problems. In Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, David S. Johnson and Michael A. Trick (eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 26, American Mathematical Society, 533-558.
[9] Spears, William M. (1996). A NN Algorithm for Boolean Satisfiability Problems. Proceedings of the 1996 Int'l Conference on Neural Networks, 1121-1126.
[10] De Jong, Kenneth A. and William M. Spears (1989). Using Genetic Algorithms to Solve NP-Complete Problems. In Proceedings of the Int'l Conference on Genetic Algorithms, 124-132.
Further information on complex adaptive systems
can be found at a nice web site maintained by
Mark Voss.