DAI-List Digest Thursday, 25 February 1993 Issue Number 108 Topics: Looking for ESPRIT-III Partners in DAI Report Available on Logical Theory of Intention Abstracts of CKBS Research Papers Query on Communication in Multiagent Systems Administrivia: Please send submissions to DAI-List@mcc.com. Send other requests, such as changes in your e-mail address, to DAI-List-Request@mcc.com. ---------------------------------------------------------------------- From: Christian Traue Subject: Looking for ESPRIT-III partners - DAI Date: 23 Feb 1993 15:25:24 GMT Expose of an ESPRIT-III project Tasks 5.7, 5.8, 6.2 - looking for partners - We -?the DAI-lab at Technical University of Berlin?- are currently looking for partners for an ESPRIT-III project. In the following you will find an expose of the project we would like to conduct. We would also be interested in joining an existing group possibly already having formulated a related proposal. If the proposed project sounds interesting to you or if you know of any other project that might be of interest to us please contact us, preferrably via e-mail or fax by March 15th. Regarding our own proposal we suggest a meeting of potential partners on March 22nd in Berlin to speed up the procedure. (Proposed) Title: The DAI-Toolkit: An Experimental Testbed For Development and Evaluation Of DAI Scenarios ESPRIT-Areas: Domain 5 (CIME), Task 5.7 (provision of tools ... industrial plant ... control systems), Task 5.8 (interactive ... production management systems ... multisite) Domain 6 (Basic Research), Task 6.2 (basic aspects of multiple computing agents) Keywords: Distributed Artificial Intelligence, Multiple and Cooperating Agents, CIM environments, experimental testbed Current state of DAI research Over the last several years considerable efforts were spent on exploring the behavior of 'cooperative' problem-solving. It could be shown that this extension of the traditional AI approach often leads to more sophisticated systems when compared to using monolothic approaches - even more so if the problem is inherently distributed and complex (as is the case with e.g., CIM-type problems). Up to now, most energy was put into realization of concrete systems rather than modeling distributed problem-solving applicable on a wider range of domains. This can be seen as a revelation of a similiar problem tackled by the AI communitiy in the early 80's - namely the lack of a methodological background for building 'intelligent' systems. Nevertheless, several researchers have come up with tentative concepts (e.g., Gasser, Lesser). Based upon those concepts, experimental testbeds have been developed, e.g., MACE (Gasser et al.), MICE (Durfee et al.), providing formal languages for modeling agents. It is quite difficult, though, to specify the behavior of agents (like solving problems in a domain, communicating, cooperating, etc.) in a manner more abstract than conventional programming languages. Objectives of the project The overall goal of the project proposed here is to develop a generic experimental testbed for modeling DAI scenarios. It will then be possible for developers of DAI systems to specify and define the behavior of agents, like solving problems in a domain, communicating, cooperating, etc. with greater ease. The approach taken here is highly influenced by the 'knowledge-level' debate initiated by Newell in his presidential address to the AAAI 1980. He claimed that a distinct level of analyses for problem solving systems above the symbol or program level does exist. Since then the 'knowledge level', as he coined it, has been identified as the adequate level of abstraction for knowledge acquisition and engineering by a variety of authors (e.g., Wielinga, et al., Chandrasekaran et al.). In the same spririt one of the aims of the project will be to allow specifying the behaviour of agents in DAI scenarios at the knowledge level. A generic testbed should also provide a library of predefined methods. In addition to methods specifying the behaviour of agents, like problem-solving, communicating, cooperating, etc., knowledge acquisition methods allowing for multiple expertise and diverging agents are needed. In order to 'test the testbed' some applications in the CIM area shall verify the usefulness of the approach. The CIM area was chosen because of the experiences the DAI lab has in this domain, the possibility of acquiring the expertise from our industrial partners, and last but not least the high economic potential lying here. Contributions of the DAI-Lab Emerging from several externally funded research projects in the area of Distributed Artificial Intelligence (DAI), the DAI-lab was founded in April 1992 by Prof. Dr. Hermann Krallmann, head of the department of systems analysis and EDP at Technical University of Berlin . It is one of four work groups the department currently consists of. Current projects In close cooperation with industrial partners several projects are currently in progress. The outcome of all is likely to influence the project proposed. Objective of the project CoKoM (Cooperated Knowledge-based System for Manufacturing Control) is enhancement of a software system developed in a foregoing project (Blackboard-DEC), the distributed knowledge-based shop-floor control center, VerFLEX-BB. One of the main goals of the project is the extension and completion of the problem solving methods. Furthermore, the system will be physically distributed using broadband communication technologies, specifically B-ISDN. In another project, TeleCAS, the goal is to enhance and embellish a software system for computer-aided selling, which was basically developed in the INTERBIT project. Methods and technologies of DAI will be put to use in order to physically distribute the system via B-ISDN and incorporate multimedial aspects. The reusability of the whole system is another major aspect of the project. Whereas the above described projects are funded by Deutsche Telepost BERKOM and are conducted with Bosch-Siemens-Hausger{te GMBH, Berlin (a manufacturer of household appliances) as the industrial partner, the third project is sponsored by Deutsche Forschungs-gemein-schaft (DFG). It deals with knowledge-based configuration and is another off-spring of INTERBIT. Areas of research General subject of all research and practical work at the DAI-lab are cooperating knowledge-based systems. In the long run all work at the lab aims at realizing the above mentioned experimental testbed for development of DAI systems. Relevant basic parts of this testbed were already designed and over the coming years more components will be identified and realized. The specific topics of current research include: * Modeling Agents - Tentative Agent Model A task group at DAI-lab is concerned with definition of a generic model of agents. Taken into account are findings of others in this area as well as practical experience gained in the development of the above mentioned prototypical shop-floor control center. As a first result a tentative agent model has emerged. It differs from other approaches as it separates the so-called object-knowledge, consisting of methods required for solving a problem, from meta-knowledge reasoning about those methods (e.g., knowledge for selecting and combining certain methods). This separation has lead to a lot of 'working packages' - like specification and operationalization of problem solving methods, cooperation methods, goal detection, selection mechanisms etc. which can be easily tackled by different working groups. * Knowledge Acquisition The goal of a second group at the lab is to develop knowledge- acquistion KA tools for DAI scenarios. At the moment a specific KA tool for the VerFLEX-BB system is under way. Enhancing the KADS methodology for acquring multiple expertise is another topic of that group. * Communications and Man-Machine-Interfaces It is intended to realize physical distribution of DAI systems to be developed using broadband communications services, specifically B-ISDN. As the intended systems will be quite powerful it is necessary to provide adequate means for `using' the system. The user-interfaces will therefore include concepts from multimedia technology. * Complementary Research - Technology Assessment To the staff at DAI-lab technology assessment (TA) regarding realization and implementation of their systems in real-life environments is a crucial aspect. Therefore, aspects of TA will be taken into consideration in all work conducted at the lab. Some of the problems to be tackled here include qualification of workers using DAI systems and loss of responsibility (or a feeling thereof) in workers supported by such systems. Contributions of Others We think that the development of a generic testbed for DAI applications is a project so ambitious that several independent tasks can be easily identified. We are looking for partner research institutions and application partners in industry that would like to contribute to the described goals. Also, we are interested in existing or planned projects covering this subject area. Please do not hesitate to contact us. Contact Dr. Ing. Sahin Albayrak Technical University of Berlin DAI-Lab Sekr. FR6-7 Franklinstr. 28/29 D-W1000 Berlin 10 Phone: +49 - 30 - 314 - 24943 Fax: +49 - 30 - 314 - 22357 e-mail: dai-lab@cs.tu-berlin.de ------------------------------ From: rpg@cs.tulane.edu (Robert Goldman) Subject: Technical Report - Logical theory of intention Date: Wed, 24 Feb 1993 22:49:44 GMT Intentions in Time Robert P. Goldman and R. Raymond Lang Technical Report TU 93-101 ABSTRACT: Representing and reasoning about goal-directed actions is necessary in order for autonomous agents to act in or understand the commonsense world. This paper provides a formal theory of intentional action based on Bratman's characterization of intention. Our formalization profits from the insights developed by Cohen and Levesque in their formalization of Bratman's theory. We review Cohen and Levesque's formalization and illustrate its weaknesses. Using Allen's temporal logic as a foundation, we construct a formalization that, like Cohen and Levesque's, satisfies Bratman's desiderata for an acceptable theory of intentional action. We introduce a characterization of success and failure of intentional action and show that our richer theory of time allows us to formalize more complex intentional actions, particularly those with deadlines. Finally, we argue that the use of a syntactic theory of belief allows us to accommodate a more descriptive theory of intentional action by fallible agents. Our work has relevance to applications like multiagent planning, speech-act processing and narrative understanding. We are pursuing applications of this theory to representing the content of narratives and to constructing and understanding description-based communication. Technical report available by anonymous ftp from rex.cs.tulane.edu [129.81.132.1] as file tutr-93-101.ps.Z in directory pub/tech File is a compressed postscript file. Because of compression, the file must be transferred in BINARY mode and, when expanded (using the UNIX uncompress utility) may be printed on a postscript printer. ------------------------------ From: "Baird Ndovie" Subject: Abstracts of Research papers Date: Mon, 15 Feb 93 12:17:15 GMT The CKBS research group of the DAKE Centre at Keele University presents below a list of abstracts of research papers written by its members during 1992. The list is in bibtex format. You can obtain full papers by contacting: Mr. Baird Ndovie Computer Science Dept Keele University Staffs., ST5 5BG England. Fax number: (0782) 713082 @TECHREPORT{Fletcher92a, author="Martyn Fletcher, S. Misbah Deen, Mark Walsh and Athula Herath", title="{\bf The Search for Optimised Routing in a MultiAgent Framework}", year=1992, institution="Data and Knowledge Engineering Centre", type="Technical report no. {DAKE/-/TR-92003.1}", month="August", address="University of Keele, Staffordshire, ST5 5BG, U.K.", note="{\it Released to the public domain in December, 1992, due to a confidentiality restriction of the EEC ESPRIT IMAGINE Project}", abstract=" In the the Intelligent Network Management (INM) application domain, a major activity is that of routing, i.e., deciding on the optimal path along which to send packets from their source to destination within a directed network. A multiagent system approach to this problem is to use agents located at the nodes to cooperate with each other in order to produce an optimal network performance. By optimisation, we mean applying a cost function to a number of different network configurations to decide on the optimal strategy. In this paper, we provide a model of the issues which can be optimised, together with a cost function to compare various strategies. A collection of multiagent techniques is also given so that this optimal network configuration can be instantiated." } @TECHREPORT{Fletcher92b, author="Martyn Fletcher and S. Misbah Deen", title="{\bf Some Design Considerations for Optimisation in Intelligent Network Routing}", year=1992, institution="Data and Knowledge Engineering Centre", type="Technical report no. {DAKE/-/92015.1}", month="November", address="University of Keele, Staffordshire, ST5 5BG, U.K.", note="({\it Presented at CKBS-SIG workshop, Keele University, Sept.1992})", abstract=" In the the Intelligent Network Management (INM) application domain, a major activity is that of routing, ie deciding on the best path along which to send packets from their source to destination within a directed network. A multiagent system approach to this problem is to use agents located at the nodes to cooperate with each other in order to produce an optimal network performance. In this paper, we present a model of a multiagent routing framework with particular attention being addressed to three parts of the model. Firstly, the routing table retained by the agents which details several paths to each destination. We present techniques to 1) enable the agents to choose between multiple paths for some destination, and 2) let the agents update their table by comparing the tuples with those held by other agents. Secondly, the hierarchical organisation in which the agents cooperate. We provide a structure whereby an agent can retain information not only concerning its simultaneous membership of two independent hierarchies, but also about frequently used routes. Thirdly, the information exchange strategy which governs what knowledge is sent to which agent and when. We provide an example of such a strategy which gives the agents timely and accurate information to base their decisions upon. We go on to provide an analysis of our routing model from a number of criteria. The manner in which the multiagent framework improves the coherence of the routing mechanism is investigated. The paper is terminated with an introduction to a multiagent resource cost model." } @TECHREPORT{Fletcher92c, author="Martyn Fletcher and S. Misbah Deen", title="{\bf Optimising the Hierarchical Organisation within a Multi-Agent Network Routing Framework}", year=1992, institution="Data and Knowledge Engineering Centre", type="Technical report no. {DAKE/-/TR-92016.1}", month="November", address="University of Keele, Staffordshire, ST5 5BG, U.K.", abstract=" Often when there are a large number of intelligent agents which need to cooperate with each other, via communication, an organisation emerges. One of the most versatile organisations is that of a hierarchy. In this paper we present a method for deciding upon the optimal hierarchy which the agents should collaborate within. This mathematical treatment is used for determining the best route between agents in an Intelligent Network Management (INM) framework. Once the parameters (ie the group size and the number of levels) for the best tree have been found, a two phase process of instantiating the physical hierachy with such parameters must be undertaken. The first phase is to construct a logical hierarchy of the available agents. This hierarchy will be the best possible within the constraints imposed by both the optimal parameters and any organisational requirements of the system. The second phase is to convert the logical hierarchy into a physical one shared by all the agents concerned. We propose techniques to achieve the two phases mentioned above. Namely a constrained minimal spanning tree algorithm for the logical tree creation. While a collection of inter agent negotiation protocols are used to enable the agents to decide on the physical tree instance." } @TECHREPORT{Ndovie91a, author="Baird Ndovie", title="{\bf A Survey of Forms of Communication in current ATC system}", year=1991, institution="Data and Knowledge Engineering Centre", type="Technical Report no. {DAKE/-/TR-91004.1}", month="May", address="University of Keele, Staffordshire, ST5 5BG, U.K.", note="({\it Released to the public domain in 1992, due to a confidentiality restriction of the EEC ESPRIT IMAGINE Project})", abstract="The objective of communication in air traffic control(ATC) is to provide a means of exchanging information between controller and aircraft, and among controllers in order to achieve a safe, orderly and expeditious movement of air traffic. This paper presents the types of communications used in current ATC system, and concludes with some of the future developments in aviation communications." } @TECHREPORT{Ndovie91b, author="Baird Ndovie", title="{\bf Cooperation in Air Traffic Control(ATC)}", year=1991, institution="Data and Knowledge Engineering Centre", type="Technical Report no. {DAKE/-/TR-91005.1}", month="June", address="University of Keele, Staffordshire, ST5 5BG, U.K.", note="({\it Released to the public domain in 1992, due to a confidentiality restriction of the EEC ESPRIT IMAGINE Project})", abstract="The air traffic control(ATC) requires controllers to cooperate in order to achieve a safe, orderly and expenditious movement of traffic in airspace. In this paper, we outline the situations involving cooperation in current ATC system and some of the cooperation strategies which may be used to find solutions to these situations." } @TECHREPORT{Ndovie92, author="Baird Ndovie", title="{\bf Analysis of Cooperation in Air Traffic Control(ATC)}", year=1992, institution="Data and Knowledge Engineering Centre", type="Technical Report no. {DAKE/-/TR-92019.1}", month="November", address="University of Keele, Staffordshire, ST5 5BG, U.K.", note="({\it Presented at CKBS-SIG workshop, Keele University, Sept.1992})", abstract=" Air Traffic Control(ATC) is a technologically rich environment which has, over the years, incorporated many innovations in computing. The objective of a computer system in an ATC environment is to direct and guide aircraft within its jurisdiction through phases of flight (i.e. take-off, ascent, descent, cruising and landing). In ATC environment the major activity is that of cooperation among controllers (agents) and between controllers and aircraft( agent). Cooperation is required in this environment in order to achieve a safe, orderly and expenditious movement of traffic in airspace. In this paper, we outline the ATC tasks which require interagent cooperation during flight control. We, then, present a framework for multiagent cooperation in ATC and a taxonomy of ATC agents participating in the interagent c cooperation." } @TECHREPORT{Walsh91, author="Mark Walsh", title="{\bf Agents in Telecommunications Network Management(TMN)}", year=1991, institution="Data and Knowledge Engineering Centre", type="Technical Report no. {DAKE/-/TR-91011.1}", month="May", address="University of Keele, Staffordshire, ST5 5BG, U.K.", note="({\it Released to the public domain in 1992, due to a confidentiality restriction of the EEC ESPRIT IMAGINE Project})", abstract=" This paper outlines the nature of Telecommunications Network Management. It also offers a brief introduction to the nature of TNM in the real world and the functions that are provided within these TNM systems. Current TNM practices are based very largely in the areas of electrical engineering and low level computer science. Only a small amount of work has been done in the area of distributed artificial intelligence and telecommunications and so the concept of an agent is still relatively novel in TNM. This paper concerns itself mainly with TNMs within data networks where there are a number of emerging standards on which to base a discussion of Agents in TNM. The concept of an Agent is addressed within the report and the functionality required of an Agent in order to support TNM requirements." } @TECHREPORT{Herath91, author="Athula Herath", title="{\bf Survey of the forms of cooperation in Network Management}", year=1991, institution="Data and Knowledge Engineering Centre", type="Technical Report no. {DAKE/-/TR-91012.1}", month="May", address="University of Keele, Stafforshire, ST5 5BG, U.K.", note="({\it Released to the public domain in 1992, due to a confidentiality restriction of the EEC ESPRIT IMAGINE Project})", abstract=" This paper is an attempt to identify the forms of cooperation in network management tasks. It provides a brief overview of network management and reviews the network management strategies of OSI and Internet Community. And it also provides and overview of intelligent network management schemes. It also provide a brief account of what {\it cooperation} meant to the author, (just enough) to identify forms of cooperation in network management tasks." } @TECHREPORT{Deen92a, author="S. Misbah {Deen}", title="{\bf A General Framework for Coherence in a CKBS}", year=1992, institution="Data and Knowledge Engineering Centre", type="Technical Report no. {DAKE/-/TR-92012.1}", address="University of Keele, Staffordshire, ST5 5BG, U.K.", note="({\it To be published in the Journal of Intelligent Information Systems, Kluwer Academic Publishers})", abstract=" Coherence in a distributed system is meant to offset the disadvantages of distribution. The paper explores four issues under coherence, namely preservation of knowledge consistency across the agents, reliability of the overall system, integration of local solutions and the global performance. It presents some general strategies that can be employed to improve coherence in a CKBS, which include a weak consistency with versions for knowledge revision, and a recovery mechanism based on a hierarchic three stage coordination, which ensures the correct isolation of potentially hierarchic multi-agent actions. The paper goes on to identify the sources and classes of conflicts in global integration, and it suggests remedies, which at worst case would involve negotiation. In global performance, it focusses on planning and result synthesis, as the two most important problem domains, and suggests strategies ameliorate performance." } @TECHREPORT{Heidari92, author="Farhad Heidari", title="{\bf Survey of Programming Environments: CASE Tools and Agent cooperation}", year=1992, institution="Data and Knowledge Engineering Centre", type="Technical Report no. {DAKE/-/TR-92020.0}", month="May", address="University of Keele, Staffordshire, ST5 5BG, U.K.", abstract=" Different software tools used in Distributed Artificial Intelligence have been analysed in this report. Expressing their design objectives, which are basically reflections of different DAI concepts, has been the prime purpose of this analysis. Integrative systems, experimental testbeds, distributed object- oriented languages and blackboard-based systems are explained through relatively detailed analysis of MACE, AGORA, ABCL/1, ACT3, AGE and MXA systems. Some of these tools are used for multiple purposes. MACE as an experimental testbed, allows the integration of heterogeneous and propably pre-existing systems. AGE, CAGE and MXA, as blackboard-based systems introduce general tools for the development of many DAI applications. ACT3 and also ABCL/1 represent useful ideas towards object-oriented methodolgy. These tools are finally compared with respect to their knowledge representation strategies, interagent communication, scheduling mechanism and their advantages and/or disadvantages are reported." } @TECHREPORT{Deen92b, author="S. Misbah {Deen}", title="{\bf Architectural Issues in A CKBS Environment}", year=1992, institution="Data and Knowledge Engineering Centre", type="Technical Report no. {DAKE/-/TR-92013.0}", month="September", address="University of Keele, Staffordshire, ST5 5BG, U.K.", note="({\it To be published})", abstract=" A Cooperating Knowledge Based System (CKBS) is an applied multiagent system, where the development of generic models for real-world application is a major objective. This paper focusses on the need for a pragmatic architecture for the social interactions of agents, based on a simple model providing abstractions, reusability and global coherence. Within the constraints of these requirements the paper explores some of the issues and solutions in decomposition and recomposition, allocation, execution and negotiation, with emphasis on a three-stage coordination protocols and a need for a high-level algebra. The paper uses examples from air-traffic control, distributed sensor networks and distributed fault diagnostics in telecommunication networks." } @TECHREPORT{Walsh92a, author="Mark Walsh and Baird Ndovie", title="{\bf Types of Agents: A General Taxonomy}", year=1992, institution="Data and Knowledge Engineering Centre", type="Technical Report no. {DAKE/-/TR-92021.0}", month="September", address="University of Keele, Staffordshire, ST5 5BG, U.K.", note="({\it Released to the public domain in December 1992, due to a confidentiality restriction of the EEC ESPRIT IMAGINE Project})", abstract=" The aim of this paper is to identify major classifications of agents. From this information common features are identified and correlated to allow a general taxonomy of agents to be produced. The taxonomy is derived using two specific application areas as a model, Air Traffic Control (ATC), and Telecommunications Network Management (TMN). The intention is that once classified, agents in a system can always be assigned a set of known features or attributes common to all agents in their class, and further generation of agents can be based on differences to the template of agents generic class." } @TECHREPORT{Walsh92b, author="Mark Walsh and S. Misbah {Deen}", title="{\bf A Study of Some Multi-Agent Application Design Strategies with a View to Enhancing Performance}", year=1992, institution="Data and Knowledge Engineering Centre", type="Technical Report no. {DAKE/-/TR-92014.2}", month="September", address="University of Keele, Staffordshire, ST5 5BG", note="({\it Presented at CKBS-SIG workshop, Keele University, Sept.1992})", abstract=" Multiagent system technology is still very much in its infancy, there are currently only a few complete systems in existence, and industrial scale systems are still the ideal to be aimed for. One domain where MAS are envisaged is that of Telecommunications Network Management TMN. The role of TMN is to provide a management function over a telecommunications network in order to facilitate the maintenance, expansion, modification and control of that network. The TMN functions are implemented as a community of agents in a MAS. In this paper we have examined issues in the TMN domain, in particular the role of an agent community in the diagnosis of faults in a telecommunications network, with a view to suggesting designs that provide better performance. In this fertile area for study there appears to be much scope for research, development and optimisation." } @TECHREPORT{Fletcher92d, author="Martyn Fletcher and Mark Walsh", title="{\bf Coherence in Multi Agent Systems}", year=1992, institution="Data and Knowledge Engineering Centre", type="Technical report no. {DAKE/-/TR-92008.1}", month="April", address="University of Keele, Staffordshire, ST5 5BG, U.K.", note="{\it Released to the public domain in December, 1992, due to a confidentiality restriction of the EEC ESPRIT IMAGINE Project}", abstract=" This is a review of the work done on coherence, presented in comparison with a coherence framework elaborated from the discussions we have had. This report is raw, but it will surely be cooked when scorching comments are made about it. Coherence is the study of how activities carried out by autonomous agents can be integrated to produce a required global outcome and how well the system performs as a whole. A framework for understanding coherence is described in terms of the symptoms, causes and cures of incoherent behaviour. From this framework, a checklist of coherence criteria is given which should be considered when building future multi agent systems. A review of work done by other researchers is given in comparison with our framework while the Air Traffic Control application domain is considered with regard to the framework." ------------------------------ Date: Thu, 25 Feb 93 08:58 N From: Subject: communication in multiagent systems Hi, my name is Michel Ludwig and I am working on a DAI project in Fribourg Switzerland. I am especially interested in the communication mechanisms in multiagent systems. I am looking for anything on point-to-point communication, broadcasting, or any other way to communicate. Thanks in advance milu ------------------------------ End of DAI-List Digest Issue #108 *********************************