nach oben

1999 | Buch

Kapitel lesen Erstes Kapitel lesen

Collaboration between Human and Artificial Societies

Coordination and Agent-Based Distributed Computing

herausgegeben von: Julian A. Padget

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

The full title of the HCM network project behind this volume is VIM: A virtual multicomputer for symbolic applications. The three strands which bound the network together were parallel systems, advanced compilation techniques andarti?cialintelligence witha commonsubstrate in the programminglanguage Lisp. The initial aim of the project was to demonstrate how the combination of these three technologies could be used to build a virtual multicomputer — an ephemeral, persistent machine of available heterogeneous computing resources — for large scale symbolic applications . The system would support a virtual processor abstraction to distribute data and tasks across the multicomputer, the actual physical composition of which may change dynamically. Our practical objective was to assist in the prototyping of dynamic distributed symbolic app- cations in arti?cial intelligence using whatever resources are available (probably networked workstations), so that the developed program could also be run on more exotic hardware without reprogramming. What we had not foreseen at the outset of the project was how agents would unify the strands at the application level, as distinct from the system level o- lined above. It was as a result of the agent in?uence that we held two workshops in May and December 1997 with the title “Collaboration between human and arti?cial societies”. The papers collected in this volume are a selection from presentations made at those two workshops. In each case the format consisted of a number of invited speakers plus presentations from the network partners.

Inhaltsverzeichnis

Frontmatter

Languages and Systems

Frontmatter

A Classification of Various Approaches for Object-Based Parallel and Distributed Programming

Abstract

This paper aims at classifying and discussing the various ways along which the object paradigm is used in concurrent and distributed contexts. We distinguish the applicative approach, the integrative approach, and the reflective approach. The applicative approach applies object-oriented concepts, as they are, to structure concurrent and distributed systems through libraries. The integrative approach consists in merging concepts such as: object and activity, message passing and transaction, etc. The reflective approach integrates protocol libraries intimately within an object-based programming language. We discuss and illustrate each of these approaches and we point out their complementary levels and goals.

Jean-Pierre Briot, Rachid Guerraoui

Towards Meta-Agent Protocols

Abstract

Software agents “live” in changing environments. Perception and actions of agents need to adapt dynamically to new situations. This paper is concerned with meta-agent protocols, an approach to support the modular and portable implementation of various kinds of agent systems. Meta-agent protocols are derived from object-based reflective systems that allow access to the state and structure of a program during its execution. A meta level interface to the internal representation of agents can provide support for introspection and adjustment of agents. Meta-agent protocols result in a clear separation between application level and meta level (e.g. dynamic communication protocols, dynamic modification of behaviour, fault tolerance, monitoring, dynamic performance optimization) in agent systems which leads to modular as well as portable application components.

Andreas Kind, Julian Padget

Examples of Fuzziness in Compilers and Runtime Systems

Abstract

In this paper, we review some techniques used in compilers and runtime systems for parallel and distributed computation, involving aspects of fuzziness. Fuzziness is in a general sense considered as being present if the techniques applied classify, rate or otherwise handle information with some range of tolerance, if they operate with similarities, uncertainties, or do not seek for perfect/optimal solutions (but apply heuristics or approximations). In many cases, fuzziness, in this sense, is already used but may need a better theoretical basis; and in others, its integration may improve approaches, opens up new perspectives or become relevant for future applications, as in distributed computing. In this paper, we focus on the potential application of fuzzy theory, providing a simplified – but in many cases sufficiently accurate – approach on sound theoretical principles. Other important theoretical approaches – as far as they are applied in compilers for dealing with approximateness – are the determination of bounds guaranteeing minimal quality or maximal runtime, or statistics providing means and variances. As a spin-off, so to speak, the paper investigates – from the point of the user – the various forms and benefits of fuzziness, concluding with a brief philosophical discussion of fuzziness.

Angela C. Sodan

Towards Rigorous Compiler Implementation Verification

Abstract

This paper sketches a rigorous correctness proof of a compiler executable. We will emphasize the central rôle of partial program correctness and its preservation, which captures the intuitive correctness requirements for transformational programs and in particular for compilers on real machines. Although often left out of sight, implementation verification is definitely necessary, not only but also for compilers. We will show that a rigorous compiler correctness proof also for the final binary compiler machine program is possible and feasible. Verified compiler implementations guarantee correctness properties for generated executable program implementations; we need them, not only in safety critical systems, but also for security in e.g. network computing.

Wolfgang Goerigk, Friedemann Simon

Shifting the Focus from Control to Communication: the STReams OBjects Environments Model of Communicating Agents

Abstract

The paper presents the computational model underlying new agent communication languages. The model, called STROBE, has been identified and two prototypical languages inspired by the model have been implemented. In order to describe unambiguously the STROBE model we have chosen to use a formal programming language, i.e. Scheme. STROBE shows how generic communication may be described and implemented by means of STReams of pragmatically marked messages to be exchanged by agents represented as OBjects interpreting messages in multiple Environments. The model, therefore, is at the same time a software architecture and a proposal for a lexicon potentially useful for exchanging efforts in emergent agent technologies. An outline of the expected functionality’s of the languages under development may allow to appreciate if and how they may fit the expected ones, i.e. cognitive simplicity for designing and controlling multi-agent generic dialogues, including human and artificial communication facilities.

Stefano A. Cerri

Direct Manipulation, Scalability and the Internet

Abstract

UNIX has provided us with a tried and tested set of shell utilities. The associated shells provide rich languages for generating scripts to automate common tasks using pipelines, sequences, conditionals and iterations. These facilities are also used to compose components in complex user-defined systems. Unfortunately, the shell-like facilities are inaccessable to the growing majority of users who have never experienced a command-line interface. These users are only familiar with directing computers in a visual manner. The Psh project is an attempt to provide similar functionality to the UNIX shell in a visual context. In this paper, we consider how the project relates to the existing desktop metaphor as found in the Macintosh Finder or a modern Microsoft Windows system. In a separate thread, we also integrate the desktop with the internet by using the URL as the general identifier instead of the traditional UNIX style identifier.

Don Cruickshank, Hugh Glaser

Agents and Capabilities

Frontmatter

Towards the Abstraction and Generalization of Actor-Based Architectures in Diagnostic Reasoning

Abstract

Research in multimodel based diagnosis stresses the role of a centralized diagnostic agent in a computational framework made of different models. Each of these models provides knowledge according to a given representation of the system to diagnose: structural, behavioral, functional and teleological aspects are each embodied into a different model. According to this approach, various proposals have been formulated in terms of cooperation among different views without comprehensively addressing the issues of concurrency and collaboration, in particular the effect of asynchronous message passing in software design. We present here the use of a distributed and concurrent architecture in which different models collaborate in order to achieve a global diagnosis through a set of independent actors. The paper reports about two experiences: a distributed architecture representing a user model in an intelligent tutoring system (ITS) and a diagnostic engine for troubleshooting a physical system. In spite of the difference of the two applications, we may abstract from the two architectures important common patterns that constitute the core of the distributed management of the multiple knowledge sources.

Stefano A. Cerri, Antonio Gisolfi, Vincenzo Loia

Converting Declarative into Procedural (and Vice Versa)

Abstract

Procedural and declarative are often seen as two irreconcilable extremes. In this paper, we show how a reflective rule system can move between declarative and procedural interpretations with relative ease. We outline a new way to interpret these shifts, one which is more principled than the usual dichotomy. We also show that some relatively small changes in rule structure allow different dynamics to be assigned to rule components and to entire rules. This serves not only to show that description plays a critical role in reflection, but also to show that different kinds of dynamics can be supplied when required. Alternative dynamics can be provided by rule sets encoded in the same representation. The new structure can be used in exactly the same way as the ELEKTRA interpreter that is the main focus of this paper’s attention.

Iain D. Craig

Reflective Reasoning in a Case-Based Reasoning Agent

Abstract

As a Case-Based Reasoning agent (CBR) evolves over time, and solves new problems based on previous experiences, there are some pitfalls that can appear in the problem-solving task. When those troubles arise, is the time to start some reflective reasoning tasks to overcome those problems and to improve the CBR performance. Our proposal is to extend the basic reasoning and learning cycle with some new added reflective tasks such as forgetting cases, learning new cases, updating the case library organisation or re-exploring the case library, and including other strategies such as building meta-cases.

Miquel Sànchez-Marrè, Ulises Cortés, Javier Béjar, Ignasi R. Roda, Manel Poch

Modelling Rational Inquiry in Non-ideal Agents

Abstract

The construction of rational agents is one of the goals that has been pursued in Artificial Intelligence (AI). In most of the architectures that have been proposed for this kind of agents, its behaviour is guided by its set of beliefs. In our work, rational agents are those systems that are permanently engaged in the process of rational inquiry; thus, their beliefs keep evolving in time, as a consequence of their internal inference procedures and their interaction with the environment. Both AI researchers and philosophers are interested in having a formal model of this process, and this is the main topic in our work.

Beliefs have been formally modelled in the last decades using doxastic logics. The possible worlds model and its associated Kripke semantics provide an intuitive semantics for these logics, but they seem to commit us to model agents that are logically omniscient and perfect reasoners. We avoid these problems by replacing possible worlds by conceivable situations, which are all the situations that the modelled agent is capable of considering.

In this paper we show how this notion of conceivable situations may be used to model the process of rational inquiry in which a non-ideal rational agent is engaged. We define a wide class of agents, called rational inquirers, which are a general abstraction of any kind of non-ideal agent. We show how the beliefs of this kind of agents evolve in time as a consequence of a multi-dimensional belief analysis, and we use the framework of conceivable situations in order to model this evolution.

Antonio Moreno, Ulises Cortés, Ton Sales

On the Process of Making Descriptive Rules

Abstract

The automatic inductive learning of production rules in a classification environment is a difficult process which requires several considerations and techniques to be studied. This is more noticeable when the learning process is applied to real world domains. Our goal is to focus and study some of the most important problems related to the automatic learning of production rules as well as to provide some tools for dealing with these problems. We first consider the data representation problem. Four different types of data are proposed. We then deal with the unsupervised case in which the data are observations of objects in the world and we pose three alternative mechanisms for clustering. If the data set contains examples and counter examples of some world concepts, the learning is called supervised. Within supervised learning we find the data redundancy problem. Two sorts of redundancy are studied: the one which is concerned with the set of examples, and the one which is concerned with the set of example descriptors.

Before we generate rules that describe the domain which is represented by the input data, we analyze the set of conditions which will be the basis of our rules. These conditions are called selectors and they enable us to control more directly the semantics of the induced rules. We have implemented several algorithms that generate selectors automatically and we have tested them together with four new rule generation algorithms. The results obtained are compared with those other results produced by other classical rule learning methods such as cn2 and c4.5rules.

D. Riaño

Coordination and Collaboration

Frontmatter

A Service-Oriented Negotiation Model between Autonomous Agents

Abstract

We present a formal model of negotiation between autonomous agents. The purpose of the negotiation is to reach an agreement about the provision of a service by one agent for another. The model defines a range of strategies and tactics that agents can employ to generate initial offers, evaluate proposals and offer counter proposals. The model is based on computationally tractable assumptions and is demonstrated in the domain of business process management. Initial proofs about the convergence of negotiation are also presented.

Carles Sierra, Peyman Faratin, Nick R. Jennings

Competing Software Agents Support Human Agents

Abstract

A community of interacting software agents can support an activity of human agents. We describe an experiment based on an existing information server showing how software agents compete for the attention of the user with the intention to support her in an information-rich task through providing her some useful comment. To be successful in the competition, agents have to capture contextual parameters about the current activity of the user and render them in a context-sensitive annotation to information. The outcome of the competition for attention consists of a weighted topic structure, annotated with text templates. The annotated topic structure is the basis for generating a context-sensitive navigation node by a process of template expansion and aggregation.

Sabine Geldof, Walter Van de Velde

Coordination Developed by Learning from Evaluations

Abstract

This paper reports on research into the origins of communication and coordination. Several problems with defining communication and coordination are noted. A research methodology is described that circumvents these problems. The methodology is used in an experiment concerning the development of coordination. The aim of the experiment is to see whether a learning agent can use coordination signals, which represent evaluations of its behavior, to learn to coordinate its actions in an unknown environment. The task is a pursuit problem where four agents are needed to capture a randomly moving prey. One of these agents adapts its behavior based on the coordination signals it receives from the three other agents. The development of coordination increased the capture rate in this pursuit problem from an initial 5% to 93%. Thus, in combination with a general learning mechanism, coordination signals may be sufficient for the development of coordination.

Edwin D. de Jong

Rules of Order for Electronic Group Decision Making – A Formalization Methodology

Abstract

This paper reports on an ongoing research project, consisting of formalizing rules of order for group decision making, and implementing them as a procedural component of automated mediation systems for group decision making. The component should ultimately assist a human mediator in maintaining order at electronic meetings, and in giving advice to the participants on their options, rights and obligations in the decision making process. A main requirement for the system is that order can be maintained in a flexible way, allowing to set the rules aside when needed. This paper presents the first research result of the project: a way of formalizing rules of order that makes it possible to maintain order in such a flexible way.

Henry Prakken, Thomas F. Gordon

Broadway: A Case-Based System for Cooperative Information Browsing on the World-Wide-Web

Abstract

The World Wide Web is a huge hypermedia where finding relevant documents is not an easy task. In this paper, we present our case-based system for cooperative information browsing, called Broadway. Broadway follows a group of users during their navigations on the WWW (proxy-based architecture) and advises them by displaying a list of potentially relevant documents to visit next. Broadway uses case-based reasoning to reuse precise experiences derived from past navigations with a time-extended situation assessment: the advice are based mainly on similarity of ordered sequence of past accessed documents. In addition, the dynamic nature of the WWW is addressed in the reuse step and with a specific method for case forgetting.

Michel Jaczynski, Brigitte Trousse

Towards a Formal Specification of Complex Social Structures in Multi-agent Systems

Abstract

In this paper we summarize the results obtained so far in the course of the Fishmarket project concerning the study of the formalization, design and construction of agent-mediated electronic institutions (AMIs). We argue that AMIs are the most appropriate social structure for a large variety of multi-agent systems. Here we present the realization of an actual AMI, FM, inspired on the traditional fish market that we employ as a case study in our proposal for the formalization of electronic institutions.

Juan A. Rodríguez-Aguilar, Francisco J. Martín, Pere Garcia, Pablo Noriega, Carles Sierra

Backmatter

Titel: Collaboration between Human and Artificial Societies
herausgegeben von: Julian A. Padget
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-540-46624-6
Print ISBN: 978-3-540-66930-2
DOI: https://doi.org/10.1007/10703260