DAI-List Digest Wednesday, 21 August 1991 Issue Number 50 Topics: More on DPS vs. MA Call for Papers - AIPS-92 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: Jeff Rosenschein Date: Wed, 21 Aug 91 11:48:08 +0300 Subject: More on DPS vs. MA I'm also enjoying using DAI-List for a focused discussion on DPS vs. MA systems. Ed Durfee points out that it's a good thing we're doing this before the summer ends and "term-time commitments" make it harder to participate...but the Fall term starts later over here, so I suppose I'll get to have the last word. :) I apologize in advance for the length of this message. I like reading and writing short notes, but I want to make sure that my point here is understood. I wholeheartedly agree with Ed's penultimate paragraph: > Thus, I once again argue that many DAI systems, whether DPS or MA, > blend cooperation and competition, and that neither DPS nor MA can > exclusively claim either of these forms of interaction. The placement of that paragraph after a comment about my previous message led me to believe that I may have been misunderstood. It's clear that DPS systems can use competitive behavior (Ed's citing of Corkill's work on "skepticism" hits the nail on the head), and that MA systems can exploit cooperative behavior (e.g., the AAAI-86 paper, "Cooperation without Communication," looked at cooperation in a clear Multiagent environment). The point that I was making in my last message was that a "pure" MA system is one where the agents have been designed separately, by different designers. That's why the designers' options at the design stage are limited, and the designers can't depend on how the other agents will act. Scenario: Boeing enters home-robot market, selling mass-produced mobile agents that are able to wash dishes, clean windows, and run simple neighborhood errands. IBM, seeing a lucrative market developing, rushes to design its own mobile agent. IBM's engineers need to build their own machine to deal flexibly with other agents, including Boeing's, and possibly other machines not yet on the market. Actually, Boeing had to do something similar, since their mobile robot had to deal with human agents. *That's* a pure Multiagent scenario. The designers can't depend on arbitrary cooperative behavior from other agents. I don't mean they choose not to, or it's more convenient not to---I mean they really *can't*. Research on multiagent systems ought to make a contribution to the questions that must be confronted by those Boeing and IBM design teams. The IBM team might, for example, be able to assume that the Boeing machine will be cooperative if there are rational reasons for the Boeing machine to act that way. This begins to touch on the work I've been doing with Gilad Zlotkin and Eithan Ephrati on methods for reaching consensus, which analyzes the kinds of environments we might set up that encourage certain kinds of behavior from autonomous agents. In that work, we might say "Negotiation protocol A has certain good features, for example, it allows agents to reach pareto optimal rational deals, and it discourages deception." We are arguing that Boeing and IBM designers would both agree to use this protocol (it's in their best interests), and that their agents then will be truthful (that's the only rational path for the self-interested agent). The careful reader will note the introduction of the word "pure" above. The Boeing/IBM scenario is "pure" MA, but there are precious few actual pure MA systems (one notable exception is the Prisoners' Dilemma experiment that Axelrod ran years ago; the agents in that series of games were really designed by different people who couldn't make any assumptions about the behavior of the other automated agents). It is becoming clear to me, though, that people are using the MA designation to refer to centrally designed systems whose agents adopt certain kinds of behavior. Examples of this are Keith Werkman's question about his system, Mike Huhns' reply to that question, and a whole slew of papers from the Modeling Autonomous Agents in a Multi-Agent World (MAAMAW) workshop at the beginning of August (including the paper coauthored with Ran Levy that I mentioned in a previous message). All these people are building centrally designed systems with competitive, autonomous behavior among the agents, and calling them multiagent systems. So my "pure" characterization of MA systems above is obviously missing something, at least as the term is coming to be used. Let me amend my MA characterization. I still think that MA research ought to make a contribution to those Boeing and IBM designers in the scenario above. DPS research is not as closely related to their problem, since DPS researchers are free to make interagent assumptions that might not be available in MA problems. The MA researcher, however, might make the following three-part statement: 1. "I study interaction from the point of view of 'pure' MA systems; I'm interested in analyzing how agents that have been designed by different designers might coordinate, compete effectively, etc." 2. "While I wait for Boeing and IBM to get their acts together and build real autonomous agents, I will build artificial-MA systems. These are systems where I have designed all the agents, but I have built them to be autonomous, and have not built them to depend on unmotivated cooperative behavior in other agents. I will study these artificial-MA systems, for the insights they give me into true MA interactions." 3. "My theoretical work on MA theory and my practical experience building artificial-MA systems will also be of use to the DPS community, since they are willing to build autonomous behavior into their agents if they find it useful. In fact, my artificial-MA systems don't look very different from their DPS systems. They are both centrally designed, and might have lots of agents communicating, competing, cooperating, and getting jobs done. At heart, though, I have built my system to analyze a different problem. Nevertheless, we have much to share with each other." My view of MA is that it's trying to model a different kind of phenomenon than DPS. If you do research on questions that arise only with purely self-motivated agents, that surely falls into the MA area. If you build systems where agents are designed to be a priori cooperative, that surely falls into the DPS area. If, however, you've built a centrally-designed system where the agents are really autonomous, then maybe you're an MA researcher building an artificial-MA system, and maybe you're a DPS researcher who has chosen autonomy as a very useful behavior to build into your system. Just from looking at the system, I wouldn't be able to tell. The papers from MAAMAW are from people who are building artificial-MA systems, but who are (I believe) for the most part motivated by versions of the three statements above. Hybrid DPS/MA research is certainly a possibility, depending on the kinds of questions that you're trying to answer. --Jeff ------------------------------------------------------------------------ Date: Wed, 21 Aug 91 10:58:29 +1000 From: Jim Hendler Subject: Call for Papers - AIPS-92 The First International Conference on AI Planning Systems College Park, Maryland June 15-19, 1992 CALL FOR PAPERS Much attention in AI has been given to the ``planning problem''---that is, designing computational systems that can automatically generate, debug, or optimize plans of action for one or more agents. Planning as a subdiscipline of AI has been around for almost thirty years, but has recently experienced rapid growth. The primary forums for discussion of issues in the field have been the National Conference on Artificial Intelligence, and a series of DARPA Workshops on Planning, Scheduling, and Control. This series has been increasingly successful in stimulating high-quality work. There are now interesting practical algorithms for achieving efficiency in planning (some domain-dependent, some heuristic and general). There are formal results on the completeness of planning algorithms in simple domains. We are seeing the beginning of the integration of planning theory with robot programming. The time is clearly ripe for the evolution of a full-fledged conference devoted to planning. The conference will be aimed at bringing together researchers attacking different aspects of the planning problem and related issues. In addition to AI researchers, others working on planning-related issues are also encouraged to attend. Of special interest are papers discussing the integration of differing approaches to planning or the integration of planning and other AI technologies. TOPICS OF INTEREST INCLUDE APPLICATIONS Empirical studies of existing planning systems Domain-specific techniques Heuristic techniques Scheduling Systems ARCHITECTURES Real-time support for planning and control Mixed-initiative planning and user interfaces FORMAL MODELS Reasoning about knowledge, action, and time Search methods and analysis of algorithms Formal characterization of existing planning systems INTELLIGENT AGENCY Resource-bounded reasoning Distributed problem solving Integrating reaction and deliberation MEMORY-BASED APPROACHES Case-based planning Plan and operator learning and reuse Incremental Planning PSYCHOLOGICAL AND BIOLOGICAL ISSUES Analyses of Complex goal-directed behavior Neurophysiological studies concerning planning Connectionist planning systems ROBOTICS Motion and path planning Active perception and sensor-based planning TIMETABLE: The conference will take place at the University of Maryland in College Park, Maryland, from June 15-19, 1992. Papers due: Dec. 13, 1991. Notification of acceptance/rejection: Feb. 18, 1992. Camera Ready Copy: March 7, 1992. REQUIREMENTS FOR SUBMISSION: Appearance: Papers should be submitted on 8.5"x11" (or, if necessary, A4) paper, with 12 pt. type. Letter quality print is required. (Normally, dot-matrix printout will be unacceptable unless truly letter quality. Exceptions will be made for countries where high quality printers are not widely available.) LaTeX 12pt article style will be acceptable. Title Page: Each copy of the paper must include a title page, separate from the body of the paper. This should contain (i) Title, (ii) Names, addresses and phone numbers and email addresses of all authors, and (iii) an abstract of 100-200 words. Length: Papers should be in 12pt text filling roughly 5.5"x7.5" per page. Papers should be no more than 12 pages including figures, tables, and diagrams (but not references). Short papers (5 pages or less) may be submitted for review as posters. Submission: Send 5 copies of papers to: AIPS-92 University of Maryland Institute for Advanced Computer Studies University of Maryland College Park, MD 20742 USA For more information contact: CONFERENCE CHAIR: Drew McDermott, Yale University (mcdermott@cs.yale.edu) PROGRAM CHAIR: James Hendler, University of Maryland (hendler@cs.umd.edu) INTERNATIONAL CHAIR: W. Hillier, IEE, UK PROGRAM COMMITTEE: P. Agre, UC San Diego; J. Allen, Rochester University; P. Bonasso, MITRE Corp.; T. Dean, Brown University; M. Drummond, Nasa Ames Research Center; M. Georgeff, Australian AI Institute; M. Ginsberg, Stanford University; J. Hertzberg, GMD, Germany; K. Hammond, University of Chicago; S. Kambhampati, Arizona State Univ.; A. Lansky, Nasa Ames Research Center; D. Nau, University of Maryland; M. Pollack, University of Pittsburgh; R. Simmons, Carnegie-Mellon University; S. Steel, University of Essex, UK; K. Sycara, Carnegie-Mellon University; A. Tate, AIAI, Edinburgh University, UK; M. Zweben, Nasa Ames Research Center Note: The "Second International Conference on Expert Planning Systems" has been merged with this one.