Applicability of Emergence Engineering to Distributed Systems Scenarios

Genetic Programming can be effectively used to create emergent behavior for a group of autonomous agents. In the process we call Offline Emergence Engineering, the behavior is at first bred in a Genetic Programming environment and then deployed to the agents in the real environment. In this article we shortly describe our approach, introduce an extended behavioral rule syntax, and discuss the impact of the expressiveness of the behavioral description to the generation success, using two scenarios in comparison: the election problem and the distributed critical section problem. We evaluate the results, formulating criteria for the applicability of our approach.

Evolving Classifiers - Evolutionary Algorithms in Data Mining

Data mining means to summarize information from large amounts of raw data. It is one of the key technologies in many areas of economy, science, administration and the internet. In this report we introduce an approach for utilizing evolutionary algorithms to breed fuzzy classifier systems. This approach was exercised as part of a structured procedure by the students Achler, Göb and Voigtmann as contribution to the 2006 Data-Mining-Cup contest, yielding encouragingly positive results.

Offline Emergence Engineering For Agent Societies

Many examples for emergent behaviors may be observed in self-organizing physical and biological systems which prove to be robust, stable, and adaptable. Such behaviors are often based on very simple mechanisms and rules, but artificially creating them is a challenging task which does not comply with traditional software engineering. In this article, we propose a hybrid approach by combining strategies from Genetic Programming and agent software engineering, and demonstrate that this approach effectively yields an emergent design for given problems.

A Language for Interactive Cooperative Agents

Cooperative behaviour of agents within highly dynamic and nondeterministic domains is an active field of research. In particular establishing highly responsive teamwork, where agents are able to react on dynamic changes in the environment while facing unreliable communication and sensory noise, is an open problem. Moreover, modelling such responsive, cooperative behaviour is difficult. In this work, we specify a novel model for cooperative behaviour geared towards highly dynamic domains. In our approach, agents estimate each other’s decision and correct these estimations once they receive contradictory information. We aim at a comprehensive approach for agent teamwork featuring intuitive modelling capabilities for multi-agent activities, abstractions over activities and agents, and a clear operational semantic for the new model. This work encompasses a complete specification of the new language, ALICA.

Evolving Distributed Algorithms with Genetic Programming

Distributed systems are one of the most vital components of the economy. The most prominent example is probably the internet, a constituent element of our knowledge society. During the recent years, the number of novel network types has steadily increased. Amongst others, sensor networks, distributed systems composed of tiny computational devices with scarce resources, have emerged. The further development and heterogeneous connection of such systems imposes new requirements on the software development process. Mobile and wireless networks, for instance, have to organize themselves autonomously and must be able to react to changes in the environment and to failing nodes alike. Researching new approaches for the design of distributed algorithms may lead to methods with which these requirements can be met efficiently. In this thesis, one such method is developed, tested, and discussed in respect of its practical utility. Our new design approach for distributed algorithms is based on Genetic Programming, a member of the family of evolutionary algorithms. Evolutionary algorithms are metaheuristic optimization methods which copy principles from natural evolution. They use a population of solution candidates which they try to refine step by step in order to attain optimal values for predefined objective functions. The synthesis of an algorithm with our approach starts with an analysis step in which the wanted global behavior of the distributed system is specified. From this specification, objective functions are derived which steer a Genetic Programming process where the solution candidates are distributed programs. The objective functions rate how close these programs approximate the goal behavior in multiple randomized network simulations. The evolutionary process step by step selects the most promising solution candidates and modifies and combines them with mutation and crossover operators. This way, a description of the global behavior of a distributed system is translated automatically to programs which, if executed locally on the nodes of the system, exhibit this behavior. In our work, we test six different ways for representing distributed programs, comprising adaptations and extensions of well-known Genetic Programming methods (SGP, eSGP, and LGP), one bio-inspired approach (Fraglets), and two new program representations called Rule-based Genetic Programming (RBGP, eRBGP) designed by us. We breed programs in these representations for three well-known example problems in distributed systems: election algorithms, the distributed mutual exclusion at a critical section, and the distributed computation of the greatest common divisor of a set of numbers. Synthesizing distributed programs the evolutionary way does not necessarily lead to the envisaged results. In a detailed analysis, we discuss the problematic features which make this form of Genetic Programming particularly hard. The two Rule-based Genetic Programming approaches have been developed especially in order to mitigate these difficulties. In our experiments, at least one of them (eRBGP) turned out to be a very efficient approach and in most cases, was superior to the other representations.

Ansätze einer akteursbasierten Innovationserklärung

Mit der vorliegenden Arbeit soll ein Beitrag zu einer (empirisch) gehaltvollen Mikrofundierung des Innovationsgeschehens im Rahmen einer evolutorischen Perspektive geleistet werden. Der verhaltensbezogene Schwerpunkt ist dabei, in unterschiedlichem Ausmaß, auf das Akteurs- und Innovationsmodell von Herbert Simon bzw. der Carnegie-School ausgerichtet und ergänzt, spezifiziert und erweitert dieses unter anderem um vertiefende Befunde der Kreativitäts- und Kognitionsforschung bzw. der Psychologie und der Vertrauensforschung sowie auch der modernen Innovationsforschung. zudem Bezug auf einen gesellschaftlich und ökonomisch relevanten Gegenstandsbereich der Innovation, die Umweltinnovation. Die Arbeit ist sowohl konzeptionell als auch empirisch ausgerichtet, zudem findet die Methode der Computersimulation in Form zweier Multi-Agentensysteme Anwendung. Als zusammenfassendes Ergebnis lässt sich im Allgemeinen festhalten, dass Innovationen als hochprekäre Prozesse anzusehen sind, welche auf einer Verbindung von spezifischen Akteursmerkmalen, Akteurskonstellationen und Umfeldbedingungen beruhen, Iterationsschleifen unterliegen (u.a. durch Lernen, Rückkoppelungen und Aufbau von Vertrauen) und Teil eines umfassenderen Handlungs- sowie (im Falle von Unternehmen) Organisationskontextes sind. Das Akteurshandeln und die Interaktion von Akteuren sind dabei Ausgangspunkt für Emergenzen auf der Meso- und der Makroebene. Die Ergebnisse der Analysen der in dieser Arbeit enthaltenen fünf Fachbeiträge zeigen im Speziellen, dass der Ansatz von Herbert Simon bzw. der Carnegie-School eine geeignete theoretische Grundlage zur Erfassung einer prozessorientierten Mikrofundierung des Gegenstandsbereichs der Innovation darstellt und – bei geeigneter Ergänzung und Adaption an den jeweiligen Erkenntnisgegenstand – eine differenzierte Betrachtung unterschiedlicher Arten von Innovationsprozessen und deren akteursbasierten Grundlagen sowohl auf der individuellen Ebene als auch auf Ebene von Unternehmen ermöglicht. Zudem wird deutlich, dass der Ansatz von Herbert Simon bzw. der Carnegie-School mit dem Initiationsmodell einen zusätzlichen Aspekt in die Diskussion einbringt, welcher bislang wenig Aufmerksamkeit fand, jedoch konstitutiv für eine ökonomische Perspektive ist: die Analyse der Bestimmungsgrößen (und des Prozesses) der Entscheidung zur Innovation. Denn auch wenn das Verständnis der Prozesse bzw. der Determinanten der Erstellung, Umsetzung und Diffusion von Innovationen von grundlegender Bedeutung ist, ist letztendlich die Frage, warum und unter welchen Umständen Akteure sich für Innovationen entscheiden, ein zentraler Kernbereich einer ökonomischen Betrachtung. Die Ergebnisse der Arbeit sind auch für die praktische Wirtschaftspolitik von Bedeutung, insbesondere mit Blick auf Innovationsprozesse und Umweltwirkungen.

Decision Making for Teams of Mobile Robots

In the past years, we could observe a significant amount of new robotic systems in science, industry, and everyday life. To reduce the complexity of these systems, the industry constructs robots that are designated for the execution of a specific task such as vacuum cleaning, autonomous driving, observation, or transportation operations. As a result, such robotic systems need to combine their capabilities to accomplish complex tasks that exceed the abilities of individual robots. However, to achieve emergent cooperative behavior, multi-robot systems require a decision process that copes with the communication challenges of the application domain. This work investigates a distributed multi-robot decision process, which addresses unreliable and transient communication. This process composed by five steps, which we embedded into the ALICA multi-agent coordination language guided by the PROViDE negotiation middleware. The first step encompasses the specification of the decision problem, which is an integral part of the ALICA implementation. In our decision process, we describe multi-robot problems by continuous nonlinear constraint satisfaction problems. The second step addresses the calculation of solution proposals for this problem specification. Here, we propose an efficient solution algorithm that integrates incomplete local search and interval propagation techniques into a satisfiability solver, which forms a satisfiability modulo theories (SMT) solver. In the third decision step, the PROViDE middleware replicates the solution proposals among the robots. This replication process is parameterized with a distribution method, which determines the consistency properties of the proposals. In a fourth step, we investigate the conflict resolution. Therefore, an acceptance method ensures that each robot supports one of the replicated proposals. As we integrated the conflict resolution into the replication process, a sound selection of the distribution and acceptance methods leads to an eventual convergence of the robot proposals. In order to avoid the execution of conflicting proposals, the last step comprises a decision method, which selects a proposal for implementation in case the conflict resolution fails. The evaluation of our work shows that the usage of incomplete solution techniques of the constraint satisfaction solver outperforms the runtime of other state-of-the-art approaches for many typical robotic problems. We further show by experimental setups and practical application in the RoboCup environment that our decision process is suitable for making quick decisions in the presence of packet loss and delay. Moreover, PROViDE requires less memory and bandwidth compared to other state-of-the-art middleware approaches.

Web Service Composition Systems for the Web Service Challenge - A Detailed Review

This report gives a detailed discussion on the system, algorithms, and techniques that we have applied in order to solve the Web Service Challenges (WSC) of the years 2006 and 2007. These international contests are focused on semantic web service composition. In each challenge of the contests, a repository of web services is given. The input and output parameters of the services in the repository are annotated with semantic concepts. A query to a semantic composition engine contains a set of available input concepts and a set of wanted output concepts. In order to employ an offered service for a requested role, the concepts of the input parameters of the offered operations must be more general than requested (contravariance). In contrast, the concepts of the output parameters of the offered service must be more specific than requested (covariance). The engine should respond to a query by providing a valid composition as fast as possible. We discuss three different methods for web service composition: an uninformed search in form of an IDDFS algorithm, a greedy informed search based on heuristic functions, and a multi-objective genetic algorithm.

Dual retrieval in conceptual information systems

Conceptual Information Systems provide a multi-dimensional conceptually structured view on data stored in relational databases. On restricting the expressiveness of the retrieval language, they allow the visualization of sets of realted queries in conceptual hierarchies, hence supporting the search of something one does not have a precise description, but only a vague idea of. Information Retrieval is considered as the process of finding specific objects (documents etc.) out of a large set of objects which fit to some description. In some data analysis and knowledge discovery applications, the dual task is of interest: The analyst needs to determine, for a subset of objects, a description for this subset. In this paper we discuss how Conceptual Information Systems can be extended to support also the second task.

Systems of Parallel Communicating Restarting Automata

In der vorliegenden Dissertation werden Systeme von parallel arbeitenden und miteinander kommunizierenden Restart-Automaten (engl.: systems of parallel communicating restarting automata; abgekürzt PCRA-Systeme) vorgestellt und untersucht. Dabei werden zwei bekannte Konzepte aus den Bereichen Formale Sprachen und Automatentheorie miteinander vescrknüpft: das Modell der Restart-Automaten und die sogenannten PC-Systeme (systems of parallel communicating components). Ein PCRA-System besteht aus endlich vielen Restart-Automaten, welche einerseits parallel und unabhängig voneinander lokale Berechnungen durchführen und andererseits miteinander kommunizieren dürfen. Die Kommunikation erfolgt dabei durch ein festgelegtes Kommunikationsprotokoll, das mithilfe von speziellen Kommunikationszuständen realisiert wird. Ein wesentliches Merkmal hinsichtlich der Kommunikationsstruktur in Systemen von miteinander kooperierenden Komponenten ist, ob die Kommunikation zentralisiert oder nichtzentralisiert erfolgt. Während in einer nichtzentralisierten Kommunikationsstruktur jede Komponente mit jeder anderen Komponente kommunizieren darf, findet jegliche Kommunikation innerhalb einer zentralisierten Kommunikationsstruktur ausschließlich mit einer ausgewählten Master-Komponente statt. Eines der wichtigsten Resultate dieser Arbeit zeigt, dass zentralisierte Systeme und nichtzentralisierte Systeme die gleiche Berechnungsstärke besitzen (das ist im Allgemeinen bei PC-Systemen nicht so). Darüber hinaus bewirkt auch die Verwendung von Multicast- oder Broadcast-Kommunikationsansätzen neben Punkt-zu-Punkt-Kommunikationen keine Erhöhung der Berechnungsstärke. Desweiteren wird die Ausdrucksstärke von PCRA-Systemen untersucht und mit der von PC-Systemen von endlichen Automaten und mit der von Mehrkopfautomaten verglichen. PC-Systeme von endlichen Automaten besitzen bekanntermaßen die gleiche Ausdrucksstärke wie Einwegmehrkopfautomaten und bilden eine untere Schranke für die Ausdrucksstärke von PCRA-Systemen mit Einwegkomponenten. Tatsächlich sind PCRA-Systeme auch dann stärker als PC-Systeme von endlichen Automaten, wenn die Komponenten für sich genommen die gleiche Ausdrucksstärke besitzen, also die regulären Sprachen charakterisieren. Für PCRA-Systeme mit Zweiwegekomponenten werden als untere Schranke die Sprachklassen der Zweiwegemehrkopfautomaten im deterministischen und im nichtdeterministischen Fall gezeigt, welche wiederum den bekannten Komplexitätsklassen L (deterministisch logarithmischer Platz) und NL (nichtdeterministisch logarithmischer Platz) entsprechen. Als obere Schranke wird die Klasse der kontextsensitiven Sprachen gezeigt. Außerdem werden Erweiterungen von Restart-Automaten betrachtet (nonforgetting-Eigenschaft, shrinking-Eigenschaft), welche bei einzelnen Komponenten eine Erhöhung der Berechnungsstärke bewirken, in Systemen jedoch deren Stärke nicht erhöhen. Die von PCRA-Systemen charakterisierten Sprachklassen sind unter diversen Sprachoperationen abgeschlossen und einige Sprachklassen sind sogar abstrakte Sprachfamilien (sogenannte AFL's). Abschließend werden für PCRA-Systeme spezifische Probleme auf ihre Entscheidbarkeit hin untersucht. Es wird gezeigt, dass Leerheit, Universalität, Inklusion, Gleichheit und Endlichkeit bereits für Systeme mit zwei Restart-Automaten des schwächsten Typs nicht semientscheidbar sind. Für das Wortproblem wird gezeigt, dass es im deterministischen Fall in quadratischer Zeit und im nichtdeterministischen Fall in exponentieller Zeit entscheidbar ist.

Growing through Connections – A Multi-Case Study of Two Alternative Food Networks in Cluj-Napoca, Romania

In a context of urgent global socio-ecological challenges, the aim of this paper has been to explore the potential of localised and socially connected food systems. More specifically, through a multi-case study of two alternative food networks in the city of Cluj-Napoca, Romania, their contribution to a sustainable food paradigm has been explored. An important synergy within the networks is how good food is equated with peasant produce, but issues regarding quantity, delivery arrangement, power relations and inclusiveness constitute potential conflicts. Although challenged by unfavourable trends on national and EU levels, the networks are becoming more embedded horizontally, through an intrinsic focus on community in one case and through quality food stimulating good relations in the other case. The networks contribute to a sustainable food paradigm by promoting agroecology, by reclaiming socio-cultural factors of food provisioning and by being part of a (re)-peasantisation process. Exploring how these kinds of initiatives can emerge, be sustained and be developed is of relevance, especially considering their potential for improving the prospects of environmentally sustainable and socially just futures in Romania and beyond.

Evaluation of major feed resources in crop-livestock mixed farming systems, southern Ethiopia: Indigenous knowledge versus laboratory analysis results

Evaluation of major feed resources was conducted in four crop-livestock mixed farming systems of central southern Ethiopia, with 90 farmers, selected using multi-stage purposive and random sampling methods. Discussions were held with focused groups and key informants for vernacular name identification of feed, followed by feed sampling to analyse chemical composition (CP, ADF and NDF), in-vitro dry matter digestibility (IVDMD), and correlate with indigenous technical knowledge (ITK). Native pastures, crop residues (CR) and multi-purpose trees (MPT) are the major feed resources, demonstrated great variations in seasonality, chemical composition and IVDMD. The average CP, NDF and IVDMD values for grasses were 83.8 (ranged: 62.9–190), 619 (ranged: 357–877) and 572 (ranged: 317–743) g kg^(−1) DM, respectively. Likewise, the average CP, NDF and IVDMD for CR were 58 (ranged: 20–90), 760 (ranged: 340–931) and 461 (ranged: 285–637)g kg^(−1) DM, respectively. Generally, the MPT and non-conventional feeds (NCF, Ensete ventricosum and Ipomoea batatas) possessed higher CP (ranged: 155–164 g kg^(−1) DM) and IVDMD values (611–657 g kg^(−1) DM) while lower NDF (331–387 g kg^(−1) DM) and ADF (321–344 g kg^(−1) DM) values. The MPT and NCF were ranked as the best nutritious feeds by ITK while crop residues were the least. This study indicates that there are remarkable variations within and among forage resources in terms of chemical composition. There were also complementarities between ITK and feed laboratory results, and thus the ITK need to be taken into consideration in evaluation of local feed resources.