Software Engineering Approaches
to Adaptive Systems.

John Daigle

Abstract:

There is a great deal of interest in Adaptive Systems. This interest spans many fields of computer science, including software engineering, and extends back to the early days of modern computing, and even back to Leibniz's universal logic. However, a brief survey of the literature reveals no clear definition for what an adaptive system is, or what problems would be appropriate for an adaptive systems approach.

This paper briefly surveys some adaptive systems approaches, the problems they intend to solve, and the difficulties those problems present.

1  Introduction

For at least 50 years, computer scientists have been struggling both to define and implement systems that were capable of solving problems that they were not explicitly programmed to solve. Such a system would need to have some ability to recognize the shape of a problem and tailor its responses. In this most general case then, an adaptive system in one that changes its behavior based on its environment, that is, any system that adapts. In a software environment, typically, an adaptive system is also meant to handle complex problems. In addition, it is typical to include a desire for a system to be robust in the sense of minimizing errant responses.[4]

In this paper we will examine several papers concerned with the idea of adaptive systems from several perspectives. A 1962 paper on adaptive systems will be examined for historical context. Two modern, object oriented models of adaptive systems, Gaia and ROADMAP, will be compared. The next section will discuss Swarm based computing from an adaptive perspective.

An adaptive system, then, is defined in terms of problem complexity, adaptability, and robustness. In fact, all three of these criteria were outlined in a 1962 paper by John Holland entitled Outline for a Logical Theory of Adaptive Systems[3]. Since 1962, the field has diverged considerably, and now adaptive systems are more concerned with the capabilities of ``General Problem Solvers'' than with self-reproducing automata, both of which are concerns in Holland's paper. However, general problem solvers are particularly well suited to Holland's theory.

2  Examples of Adaptive Systems

2.1  The theory of adaptive systems

Holland chose to frame adaptive systems in terms of generative procedures, that is, a perfectly adaptable system would be one that would be capable of producing all programs of an idealized Turing Machine. Therefore, a restricted, or realistic adaptive system, would be one that was capable of producing some particular population of programs.

Of key importance to Holland's theory is that a computer should not produce single procedures. Rather, he supposed that a population of procedures should be generated, competing against one another in an attempt to solve the problem at hand. This takes the idea of a genetic algorithm one step further, that is, the generation of the algorithms themselves is a genetic process. The generation process itself is described as a random connection along a graph of generators to create programs.

Where Holland diverges from genetic algorithms and provides a foundation for future work in agent oriented adaptive systems is in the concept of templates and the description of the supervisory program. In the TAS, a set of simple procedures may or may not connect probabilistically to form a program, which then is set to solve a particular problem. The program may succeed or fail utterly, may be suited to the problem or not, depending on the probability of certain kinds of procedures connecting or not. A template is a probabilistic calculation that skews the chances of two procedures connecting to create a program. By altering the template, the class of problems that can be expected to be solved well by the adaptive system changes. The supervisory program monitors the progress of the system and chooses templates to impose on the system based on the performance of the system.

Because each set of generators can be of any complexity, the template may in fact be probabilistic operation on the behavior of very complex software systems, what we could consider today to be an object or model. Holland was mostly concerned with well formed and understood theoretical problems, but the basic ideas that he outlined are appropriate for the more complex environments that we expect adaptive systems to handle today.

Holland's main critique of his own work is that modification of the generation procedures can ``only be carried out in terms of available information about the environment''. This slows down the rate of adaptation. Implicit in this is the cost of self-reflection, which is treated rigorously in the paper.

2.2  The Model Based Approach

In a 1999 paper, Gabor Karsai and Jano Sztipanovits present ``A Model-Based Approach to Self-Adaptive Software''. Ideas that have survived from 1962 include the concept of run-time generation of procedures, and an overall atomic approach to computing. However, the system described is much more domain specific and the program generator works on much larger objects than the smaller procedures described by Holland. The key goal of Karsai and Sztipanovits is, to produce a system that is adaptive, high-performance, and robust, appropriate for implementation in embedded systems.[5]

One key difference between the modeling approach described in this paper and the previous work is that the models being discussed are abstract conceptual models, far removed from the actual code and possibly deeply disconnected from the actual operation of the system that supports them. Rather than a ground up approach, where simple procedures are connected together, Model--based computing suggests a heavily top down approach, where an abstract concept is imposed and the underlying tools convert this abstraction to a working system.

In order to make this work, Karsai and Sztipanovits use a runtime system called the Multigraph Kernel which provides a virtual machine above a number of computing environments. Combined with graphical modeling tools, and object database, and domain specific algorithms, this creates the Multigraph Architecture, in which program parts are connected along a graph according to control algorithms to form runtime programs. This is very similar to the template/generator pattern described by Holland.

Karsai and Sztipanovits report success in developing a model based architecture to work on some tasks. They were able to implement self--reflective control units to interpret models---based on the ODMG--93 standards---and generate functioning software systems. Outstanding issues that remained as of the time of publication were difficulties with creating compiled, rather than interpreted, models.

Karsai and Sztipanovits also remark that their system can be used to construct reliable fly--by--wire systems by replacing control units to match changing situations. The main difficulty with this is that there is not a smooth transition between one state and another, which is an issue if the system is being used in real time in a mission critical capacity. For example, if the system is acting as the go between from a pilot to the control surfaces of a passenger jet encountering heavy weather, it would be undesirable for the system to be offline---however briefly---as a result of losing an engine, because that is in fact the situation that the system is in place to deal with.

2.3  Program, heal thyself

A short-coming of the MGA was that changing controllers entailed a great deal of overhead.[5] However, there are advantages to the idea of self-adaptation that mitigate such problems, specifically, a self-adapting system can generate novel solutions to unanticipated problems in its environment. The Carnegie Mellon Rainbow Project is an attempt to implement a model--based architecture with self--healing capability.[2]

Garlan and Schmerl's approach is to build models of a system external to the system. Rather than use run--time error checking within the application itself exclusively, the authors move the adaptation to the platform, separate from the running application. In a sense, the system runs the application several times concurrently, once as a functioning agent, and also as a model. The model can be used to determine optimal behavior, recognize sub-optimal behavior, and develop solutions.

A model--based self--healing system is domain specific and requires that there be adaptation mechanisms which are well understood by a control module. Central to the idea of a self--healing system is that the system is built to function optimally, and then adopts its behavior if something goes wrong. This is in keeping with the Multi-Graph architectures fly--by--wire application domain, but not with Holland's original concept of a system that builds optimal solutions. Further, while Karsai and Sztipanovits' system could be adopted to build optimal solutions, as it is meant to be adaptive and generate its own software, the self-healing system of Garlan and Schmerl is not capable of altering its essential software elements. Rather, the adaptive elements must be built in, for example, bringing a server on line or taking one off--line.

2.4  From models to agents

So far, all of the systems and theories we have examined have consisted of a population of processes being put together by a central control program to solve well understood problems. Wooldridge, Jennings, and Kinny present a different paradigm with the introduction of the Gaia Methodology for Agent-Oriented systems.[8] The year before coining the catchy name, the same authors put forward a much briefer case for their agent-oriented methodology.[7]

Essentially, an Agent is an autonomous construct which occupies a role in the system. Wooldrige, et. al's Role Schema contains the following elements: The liveness and safety responsibilities may require explaining, essentially, liveness refers to things that should be done, and safety refers to limitations on when to do things. The example used by the authors is of a coffee filling agent. The agent should fill the coffee pot if the pot is empty (the liveness responsibility) unless the stock of coffee is at 0 (the safety responsibility).

Agent-oriented methodologies represent a real change in the approach to adaptive systems. Rather than being tied to specific domains, the agent-oriented approach is general purpose. It is easy to conceptualize how the behavior of the system would easily adapt to new situations by the cumulative responses of multiple agents.

Agents represent an additional level of data abstraction. The design process in an agent oriented methodology is concerned with transforming the agent oriented system into a "sufficiently low level of abstraction that... object oriented techniques may be applied." The main weakness of the agent-based methodology is the difficulty of developing the lower level implementations of higher level abstractions.

The agent-oriented methodology solves the generator problem for adaptive systems by relying on interactions between fixed agents to provide adaptability. It assumes a social system of tasks and agents across a network (whether actual or virtual) and a hierarchy based on a directed graph of message passing privileges. whereas Holland's original theory proposed procedures creating programs under the guidance of a controller, the agent-oriented approach has programs creating procedures in response to their environment.

The agent-based methodology, unlike the two model based approaches, does not have a preferred operating state that it attempts to maintain or rebuild. The agent-based method does not have a controller.

2.5  Simplifying the agent-based model

Holland's paper allowed for some possibility of stochastic procedures developing forecasting of future states, e.g.. weather prediction. This kind of computing is difficult to do with agent-based systems. An alternative to traditional computing approaches is swarm intelligence based computing.

A swarm based system is highly adaptable, fault tolerant, and scalable. Like the agent based approach, the swarm approach is without a central controller. But unlike the agent based approach, each individual process is identical and can take one of a small number of very simple roles depending on input.[9]

The swarm based approach is based on observations of social insect populations. Social insects engage only in very simple behavior, but social insect colonies are quite complex, robust, and adaptable. The swarm based model emulates the method in hopes of achieving the result.

In real world analysis, one interesting note about the swarm computing approach to the multi-agent system is that swarm based systems perform better as the situation changes, compared to other algorithms. The more stable a system is, the less advantage (if any) that can be achieved by using a swarm based approach.[1] However, swarm based systems are highly fault tolerant and perform well in environments that require high degrees of adaptability.

2.6  Swarm-based agents

Rouff, Hinchey, Truszkowski and Rash propose a final model for adaptive systems, the intelligent swarm.[6] An intelligent swarm system is made up of a swarm, in the sense that many of the individual processes are clones, of agents, in the sense that some of them are more intelligent than others.

Intelligent swarms have been proposed as good candidates for environments requiring high degrees of flexibility as well as a certain degree of abstraction in environments with little or no oversight, such as a interplanetary robotic exploration.

Among the difficulties of using swarm based systems is designing them in such a way that their behavior falls within predictable boundaries. The more sophisticated the system, the worse this problem becomes. Rouff, et. al propose a formal method of capturing the adaptive power of swarms of intelligent agents while ensuring a certain predictability of outcome.

3  Analysis

Holland's paper proposes that adaptive systems can best be modeled as probabilistic relationships between sub-programs under the supervision of a control program. This basic approach is maintained by Karsai and Sztipanovits, who propose an approach that incorporates an additional level of abstraction but maintains the key concepts of templates and a control program from Holland's original proposal.

Agent-oriented architectures represent the first real departure from this model for adaptive systems, keeping the higher level abstractions but losing the control system. Wooldridge, Jennings, and Kinny describe such a system and propose a case study where the system is used for managing business processes. However, the agent based approach is considered to restrictive by some researchers, who attempt to simplify the system, essentially returning to the original Holland concept of very simple probabilistically connecting procedures, but without any control programs. These swarm based systems represent the current state of the art in adaptive systems.

All of the approaches to the problem of adaptive systems reviewed in this paper have two things in common: all strive to be robust by distributing the decision making load of the system, and all strive to be adaptive by distributing the decision making load of the system. In this sense, model-based systems and genetic algorithms will not be as adaptable as agent-oriented or swarm-based systems.

Any system that relies on a central control unit or processor is only as adaptable, ultimately, as that process. A multi-state system can only be as flexible as its designers anticipate it needing to be.

However, the agent based and swarm based models, ultimately, harness the power of emergent complexity to create systems that can be almost infinitely adaptable, depending on the communication protocol engaged by the system and the number of other systems using the same protocol. While no system will ever be able to solve problems that they are not designed to solve, the concept of a problem space is radically different for agent based systems and model-based systems.

In a model based system, the problem space is defined as a list of behaviors of the system and ways to alter that behavior. In an intelligent swarm, the problem space is the variety of input that the system can receive and the variety of behaviors it can engage in. This problem space is obviously a great deal larger than the former.

In short, the removal of the control system seems to represent a large leap forward in the theory of adaptive systems. By drawing on our understanding of the natural world, software engineering advances such as swarm based systems promise to improve the power, reliability and flexibility of current computing systems.

References

[1]
D. de Oliveira, P. R. F. Jr., and A. L. C. Bazzan, ``A swarm based approach for task allocation in dynamic agents organizations,'' in AAMAS '04: Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems.1em plus 0.5em minus 0.4emWashington, DC, USA: IEEE Computer Society, 2004, pp. 1252--1253.

[2]
D. Garlan and B. Schmerl, ``Model-based adaptation for self-healing systems,'' in WOSS '02: Proceedings of the first workshop on Self-healing systems.1em plus 0.5em minus 0.4emNew York, NY, USA: ACM Press, 2002, pp. 27--32.

[3]
J. H. Holland, ``Outline for a logical theory of adaptive systems,'' J. ACM, vol. 9, no. 3, pp. 297--314, 1962.

[4]
T. Juan, A. Pearce, and L. Sterling, ``Roadmap: extending the gaia methodology for complex open systems,'' in AAMAS '02: Proceedings of the first international joint conference on Autonomous agents and multiagent systems.1em plus 0.5em minus 0.4emNew York, NY, USA: ACM Press, 2002, pp. 3--10.

[5]
G. Karsai and J. Sztipanovits, ``A model-based approach to self-adaptive software,'' IEEE Intelligent Systems, vol. 14, no. 3, pp. 46--53, 1999.

[6]
C. Rouff, A. Vanderbilt, M. Hinchey, and W. Truszkowski, ``Verification of emergent behaviors in swarm-based systems,'' in Proceedings. 11th IEEE International Conference and Workshop on the Engineering of Computer-Based Systems, 2004, 2004, pp. 443--448.

[7]
M. Wooldridge, N. R. Jennings, and D. Kinny, ``A methodology for agent-oriented analysis and design,'' in AGENTS '99: Proceedings of the third annual conference on Autonomous Agents.1em plus 0.5em minus 0.4emNew York, NY, USA: ACM Press, 1999, pp. 69--76.

[8]
------, ``The Gaia methodology for agent-oriented analysis and design,'' Autonomous Agents and Multi-Agent Systems, vol. 3, no. 3, pp. 285--312, 2000.

[9]
S. Ziane and A. Melouk, ``A swarm intelligent multi-path routing for multimedia traffic over mobile ad hoc networks,'' in Q2SWinet '05: Proceedings of the 1st ACM international workshop on Quality of service & security in wireless and mobile networks.1em plus 0.5em minus 0.4emNew York, NY, USA: ACM Press, 2005, pp. 55--62.
This document was translated from LATEX by HEVEA.
Created 1 May 2006
by John P. Daigle

Valid HTML 4.0 Transitional Creative Commons License