DAI-List Digest Tuesday, 23 July 1991 Issue Number 41 Topics: DAI Employment DAI Research Activities in NTT Laboratories Conference Proceedings in CKBS Available MAAMAW 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: rw02@gte.com (Robert Weihmayer) Subject: Full-time position for DAI researcher Date: Wed, 10 Jul 91 12:13:00 EDT Dear Colleague, The DAI-LIST has recently helped us to fill a summer position in our Distributed AI project at GTE Laboratories. We were very happy about that. We now have an opening, described below, for a full-time DAI researcher. The requirements for that position are described below. I would appreciate it very much if you would bring this opportunity to the attention of those who might be interested and qualified. _____________________ Position Description: The Distributed AI project at GTE Laboratories is developing a multiagent architecture for customer network control. Our mission is to develop prototype cooperative systems for the next generation of telecommunication operations support systems. We are taking a pragmatic approach to agent-building and coordination of distributed problem solvers: our current testbed uses agents based on PRODIGY planners and we are also experimenting with various cooperative approaches to multiagent fault management. We are currently looking for a researcher with experience in Distributed AI, multiagent planning or in closely related fields. Telecommunication expertise is not a prerequisite. This person will be expected to support the current project framework but also to assume leadership, specifically in the area of interagent coordination. The project is multidisciplinary and, in addition to telecommunications aspects, it also involves many areas of AI with which the candidate should be familiar: planning, distributed agent architectures, computational models of discourse, etc. The position involves both systems level research and implementation activities. A solid computing background is required for this position. Specific experience on UNIX platforms with demonstrated proficiency in LISP is highly desirable. Excellent communication skills and ability to sustain good team interaction will be necessary. __________________ GTE Laboratories provides a well-supported research environment, a friendly atmosphere, proximity to an abundance of cultural centers in the Boston area, as well as vast opportunities for personal and professional growth. For more information about this position, contact me (info in banner below). Email is fine. If you decide to use the USPS: GTE Laboratories Incorporated, 40 Sylvan Road, Waltham, MA 02254. An equal opportunity employer, M/F/H/V. Robert Weihmayer weihmayer@gte.com GTE Laboratories Inc. 40 Sylvan Road Senior Member of Technical Staff Waltham, MA 02254, USA Phone: (617) 466-2811 ------------------------------------------------------------------------ Date: Tue, 16 Jul 91 14:17:58 JST From: Toru ISHIDA Subject: DAI Research Activities in NTT Laboratories Research Activities in Distributed Artificial Intelligence NTT Communication Science Laboratories Sanpeidani, Inuidani, Seika-cho Soraku-gun, Kyoto 619-02 Japan July 4, 1991 1 Introduction NTT Communication Science Laboratories were established as the 12th laboratory of Nippon Telegraph & Telephone Corporation on July 4,1991. This laboratory conducts basic research into computer science, with emphasis on artificial intelligence, cryptography, and parallel architecture. The main goal of NTT Communication Science Laboratories is to contribute to the advances of computer science and basic research is performed with a long range view. In particular, many distributed artificial intelligence (DAI) topics are being researched by the artificial intelligence research group. Our research effort on DAI ranges from multiagent problem solving algorithms, and models and programming languages for describing agent's behavior. Current research topics and publications of interest are given in the next three sections. For further information, please contact: Toru Ishida Internet: ishida@cslab.kecl.ntt.jp 2 Multiagent Programming Language 2.1 Agent Oriented Programming We are currently developing a programming language in which one can program agents so that they cooperate by communicating with one another. The language has the following features. 1) The language adopts a version of agent rationality: agents take actions according to situations to fulfill their commitments. In other words, a program for an agent specifies actions that the agent should take in a certain situation to fulfill its commitments. 2) Program is regarded as a mentalistic notion such as knowledge and commitment. Adopting modal and temporal logic to represent the mental states of the agents, we express programs as logic sentences. 3) Communication primitives based on the speech-act theory, such as informing and requesting are provided. With these primitives, one can write programs for agents so that they interact with one another. 1. Jun-ichi Akahani, "AOPL: An Agent-Oriented program- ming Language," Research Note, Information Processing Society of Japan, Vol. 90, No. 101, pp. 167-174, 1990 (in Japanese). 2.2 Multiagent Production System Parallel production systems have been studied in two categories: parallel rule matching, which aims to parallelize the matching process to compress each production cycle; and parallel rule firing, which aims to parallelize multiple rule firings to reduce the total number of sequential production cycles. We are currently extending our theory of parallel rule firing to create a basis for multiagent production systems, where multiple production system programs compete or cooperate to solve a single or multiple problems. An agent architecture based on metalevel control and a new transaction model for multiple production systems are being investigated. 1. Toru Ishida, "Parallel Firing of Production System Pro- grams," IEEE Transactions on Knowledge and Data En- gineering, Vol. 3, No. 1, pp. 11-17, 1991. 2. Toru Ishida, "CoCo: A Multi-Agent System for Concur- rent and Cooperative Operation Tasks," 9th Distributed Artificial Intelligence Workshop, pp. 197-213, 1989. 3. Toru Ishida, Yutaka Sasaki and Yoshimi Fukuhara, "Use of Procedural Programming Languages for Controlling Pro- duction Systems," IEEE Conference on Artificial Intelli- gence Application (CAIA), 1991. 3 Multiagent Problem Solving: Algorithm 3.1 Distributed Constraint Satisfaction Viewing cooperative problem solving as distributed constraint satisfaction provides a useful formalism for characterizing multiagent techniques. We have formalized distributed constraint satisfaction problems (DCSPs) and compared algorithms for solving them. In particular, we have developed the new techniques called Distributed ATMS (Assumption-based Truth Maintenance System) and Asynchronous Backtracking that allow agents to act asynchronously and concurrently, in contrast to the traditional sequential backtracking techniques employed in constraint satisfaction problems. Our experimental results show that solving DCSPs in a distributed fashion is worth while when the problems to be solved by individual agents are loosely-coupled. 1. Makoto Yokoo and Toru Ishida, "ATMS for Distributed Constraint Satisfaction Problems," Journal of Information Processing Society of Japan, Vol. 31, No. 1, pp. 106-114, 1990 (in Japanese). 2. Makoto Yokoo, Toru Ishida and Kazuhiro Kuwabara,"Dis- tributed Constraint Satisfaction for DAI Problems," 10th Distributed Artificial Intelligence Workshop, Chapter 18, 1990. 3.2 Cooperative Search The motivation of this research is to find an algorithmic basis for cooperative problem solving. A typical exampleis to solve a maze with two agents. One enters from the entrance and the other enters from the exit. In such a problem, we found that the goal of each problem solver changes dynamically in response to the decisions of the other problem solver. Thus, as the first step towards cooperative search, we in- vestigated the Moving Target Search (MTS) algorithm, where the location of the target may change during the course of the search. We have proved that if the average speed of the target is slower than that of the problem solver, then the problem solver is guaranteed to eventually reach the target. An implementation with randomly positioned obstacles confirms that the MTS algorithm is highly effective in various situations. (This work has been done with Richard E. Korf of UCLA.) 1. Toru Ishida and Richard E. Korf, "Moving Target Search," IJCAI-91, 1991 (to appear). 4 Multiagent Problem Solving: Model 4.1 Negotiation Negotiation is one of models for achieving coordination among agents. We have developed a negotiation paradigm called `multistage negotiation' in collaboration with V. R. Lesser (University of Massachusetts), S. E. Conry and R. A. Meyer (Clarkson University). This paradigm was originally developed for restoring disrupted circuits in a communications network and was extended for solving a distributed constraint satisfaction problem. In multistage negotiation, an agent can acquire sufficient information about the impact of its local decisions so that the agent can make its local decisions that are correct from a global perspective without providing complete internal information to all agents. 1. Kazuhiro Kuwabara, Victor R. Lesser, "Extended Pro- tocol for Multistage Negotiation," 9th Workshop on Dis- tributed Artificial Intelligence, pp. 129-161, 1989. 2. Susan E. Conry, Kazuhiro Kuwabara, Victor R. Lesser, and Robert A. Meyer, "Multistage Negotiation for Dis- tributed Constraint Satisfaction," IEEE Transactions on Systems, Man and Cybernetics, 1991 (to appear). 4.2 Organizational Adaptation Research on Organizational Problem Solving aims to create a new paradigm for adaptive multiagent problem solving in dynamically changing environments. Organization has emerged as a key concept for structuring the activities of collections of problem-solvers. Organization self-design has been studied as an adaptive approach to long term, strategic work-allocation and load-balancing. We introduce two new reorganization primitives, composition and decomposition. They change the population of agents and the distribution of knowledge in an organization. To create these primitives, we formalized organizational knowledge, which represents knowledge of potential and necessary interactions among agents in an organization. We developed computational organization self-design techniques for agents with architectures based on production systems to take advantage of the well-understood body of theory and practice. (This work has been done with Les Gasser of USC.) 1. Toru Ishida, Makoto Yokoo and Les Gasser, "An Organiza- tional Approach to Adaptive Production Systems," AAAI- 90, pp. 52-58, 1990. 2. Les Gasser and Toru Ishida, "A Dynamic Organizational Architecture for Adaptive Problem Solving," AAAI-91, 1991 (to appear). ------------------------------------------------------------------------ From: Mark Walsh Subject: Conference Proceedings in CKBS available Date: Tue, 16 Jul 91 12:14:54 MET We are pleased to be able to announce that : CKBS'90 Proceedings of the International Working Conference on Cooperating Knowledge Based Systems is now available. ISBN 3-540-19649-8 ISBN 0-387-19649-8 It is published by Springer-Verlag London Ltd and it contains sections on * Cooperation Framework: DB Perspective * Cooperation Framework: AI Perspective * Knowledge Revision * Conflict Resolution Strategies * Multi-agent Development Model * Interactions in Data/Knowledge Bases and is compiled from papers given at the CKBS conference held at Keele University (U.K.) in October 1990. Regards Mark Walsh -- | Mark Walsh | JANET : mark@uk.ac.keele.cs | | Dept. Computer Science, | UUCP : ...!ukc!kl-cs!mark | | Keele University, Keele, | BITNET: mark%cs.kl.ac.uk@ukacrl | | Staffs. ST5 5BG. U.K. | other : mark@cs.keele.ac.uk | ------------------------------------------------------------------------ Date: 16 Jul 91 14:10 +0100 From: Eric Werner Subject: MAAMAW *********************** * MAAMAW '91 * *********************** FINAL PROGRAM & REGISTRATION FORM Modeling Autonomous Agents in a Multi Agent World Third European Workshop 5-7 August 1991, Kaiserslautern, Germany Monday, 5 August 1991 - morning - ================================= INTRODUCTION: TRENDS IN DAI CC Eric Werner (Co-Chairman), University of Hamburg IP 1 THE ROLE OF REPRESENTATION IN INTERACTION: DISCOVERING FOCAL POINTS AMONG ALTERNATIVE SOLUTIONS Jeffrey Rosenschein (invited speaker) & Sarit Kraus Hebrew University, Jerusalem (IS) AP 1 SANP : A COMMUNICATION LEVEL PROTOCOL FOR NEGOTIATIONS Man Kit Chang & Carson C. Woo University of British Columbia, Vancouver (CDN) AP 2 SOCIAL PLANS : A PRELIMINARY REPORT Anand S. Rao, Michael P. Georgeff & Elizabeth A. Sonenberg Australian AI Institute (AUS) & University of Melbourne (AUS) AP 3 COLLABORATIVE PLAN CONSTRUCTION FOR MULTIAGENT MUTUAL PLANNING Ei-Ichi Osawa & Mario Tokoro Sony Computer Science Laboratory Inc., Tokyo (J) Monday, 5 August 1991 - afternoon - =================================== AP 4 COOPERATIVE PROBLEM-SOLVING GUIDED BY INTENTIONS AND PERCEPTION Birgit Burmeister & Kurt Sundermeyer Daimier-Benz AG Research Institute, Berlin (D) AP 5 INSIGHTS INTO COOPERATIVE GROUP DESIGN : EXPERIENCE WITH THE LAN DESIGNER SYSTEM Mark Klein & Stephen Lu Advanced Research Lab Hitachi Ltd (J) & University of Illinois (USA) AP 6 A MULTI-AGENT ANALOGICAL REPRESENTATION FOR PHYSICAL OBJECTS Lucia Maria Gambardella & Marc Haex IDSIA, Lugano (CH) Tuesday, 6 August 1991 - morning - ================================== IP 2 VARIABLE COUPLING OF AGENTS TO THEIR ENVIRONMENT: COMBINING SITUATED AND SYMBOLIC AUTOMATA George Kiss (invited speaker) The Open University, Milton Keynes (UK) AP 7 TOWARD AN ARCHITECTURE FOR ADAPTIVE, RATIONAL, MOBILE AGENTS Innes A. Ferguson University of Cambridge (UK) AP 8 ECO-PROBLEM-SOLVING MODEL : RESULTS OF THE N-PUZZLE Alexis Drogoul & Christophe Dubreuil LAFORIA - Universite Paris VI, Paris (F) & CERT-ONERA, Toulouse (F) AP 9 EXPLOITING EMERGENT BEHAVIOUR IN MULTI-AGENT SYSTEMS Peter Wavish Philips Research Laboratories, Redhill (UK) Tuesday, 6 August 1991 - afternoon - ==================================== IP 3 HOW TO MOVE (PHYSICALLY SPEAKING) IN A MULTI-AGENT WORLD Jean-Claude Latombe (invited speaker) Stanford University (USA) AP 10 A DISTRIBUTED ARTIFICIAL INTELLIGENCE VIEW ON GENERAL PURPOSE VISION SYSTEMS Olivier Boissier & Yves Demazeau LIFIA, Grenoble (F) AP 11 REAL-TIME PERFORMANCE OF INTELLIGENT AUTONOMOUS AGENTS Anne Collinot & Barbara Hayes-Roth LAFORIA/IBP Universite Paris VI (F) & Stanford University (USA) Wednesday, 7 August 1991 - morning - ==================================== PANEL THE DYNAMICS OF KNOWLEDGE AND ORGANIZATION IN MULTI-AGENT SYSTEMS IP 4 PLURALITY: EXPLAINING WHY DAI SYSTEMS WORK AND WHY THEY DON'T. Les Gasser (invited speaker) Universite de Paris VI and CSI/Ecole des Mines (F) AP 12 TOWARDS A SEMANTICS OF DESIRES Georges Kiss & Han Reichgelt The Open University, Milton Keynes (UK) & University of Nottingham (UK) Wednesday, 7 August 1991 - afternoon - ====================================== AP 13 DEPENDENCE RELATIONS AMONG AUTONOMOUS AGENTS Christiano Castelfranchi & Maria Miceli & Amedeo Cesta CNR Institute of Psychology, Rome (I) & University of Rome (I) AP 14 A GAME THEORETIC APPROACH TO DISTRIBUTED ARTIFICIAL INTELLIGENCE AND THE PURSUIT PROBLEM Ran Levy & J.S. Rosenschein Hebrew University, Jerusalem (IS) LOCAL ARRANGEMENTS, REGISTRATION and FEES ----------------------------------------- The workshop will take place at the Dorint Hotel in Kaiserslautern. Kaiserslautern is located in the southwest of Germany near the extensive Palatinate Forest, with good car and train connections to Frankfurt (150km), Stuttgart (150km), Saarbruecken (70km) and Paris (450km). The Workshop Fee (DM 770) covers single room accommodation at the workshop hotel from Sunday, August 4 to Wednesday, August 7, breakfast and lunch from Monday to Wednesday, the workshop costs, as well as the social events. The Accompanying Person Surcharge (DM 444) provides an upgrade to a double room, additional breakfast and lunch from Monday to Wednesday, and participation in the social events. For students, we have a Student Fee (DM 240) which does not include the hotel accommodation and the proceedings. Students are, however, welcome and even encouraged to participate in the social events. A contact will be provided to arrange for possible student housing at the university. Extra proceedings will be available at the workshop for a nominal charge. The following social events are included in all fees. Sunday, August 4: Opening Reception Buffet Monday, August 5: Wine Tasting and dinner at a Rhineland Palatinate winery Tuesday, August 6: Medieval Banquet in the Palatinate Forest To maintain the close nature of a workshop, we have restricted the number of full paying participants to 70. For this reason, we encourage participants to register early, and institutions are advised to send at most 3 people. To register, please fill in the accompanying registration form, and return it to the organisers. Full payment, or proof of the payment order, of the registration fee must reach the organisers by July 30, 1991, or else the hotel reservation will not be guaranteed. IMPORTANT DATES -- ------------ Registration and Payment of registration fees : July 30, 1991 Workshop : August 5-7, 1991 REGISTRATION FORM -- -------------- Modeling Autonomous Agents in a Multi Agent World Third European Workshop *********************** * MAAMAW '91 * *********************** 5-7 August 1991, Kaiserslautern, Germany REGISTRATION Name ________________________________ Affiliation ________________________________ Address ________________________________ ________________________________ ________________________________ Workshop Fee ___ at DM 770 each: DM _____ Accompanying Person Surcharge ___ at DM 444 each: DM _____ Student Fee ___ at DM 240 each: DM _____ (please send proof of student status) Total DM ______ Please send the completed form by June 28, 1991 to: MAAMAW '91 c/o Donald Steiner DFKI P.O. 2080 D W 6750 Kaiserslautern GERMANY or via e-mail to: maamaw@dfki.uni-kl.de Payment may be made by sending an International Bank Cheque (payable to MAAMAW '91 in German Marks) to the above address, or by bank-to-bank transfer to the MAAMAW '91 account: from Europe, USA, etc.: from Germany: MAAMAW '91 MAAMAW '91 Kto.000964569 Kto.000964569 Kreissparkasse Kaiserslautern Kreissparkasse Kaiserslautern BIC: KLTK DE 55 BIC Bankleitzahl 540 502 20 via Landesbank Rheinland-Pfalz SWIFT Adress: MALA DE 55 540 (all charges to be covered by sender) Full payment must be received by July 31, 1991, or your reservation in the hotel will be subject to cancellation.