DAI-List Digest Friday, 15 March 1991 Issue Number 29 Topics: DAI Research at Florida International University 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. ------------------------------------------------------------------------ Date: Wed, 6 Mar 91 13:31:50 EST From: stary@scs.fiu.edu (Dr. Christian Stary) Subject: Contribution to the AISB Quarterly Issue on DAI. ON THE NEED OF COMPREHENSIVE MODELING FOR DISTRIBUTED PROBLEM SOLVING ENVIRONMENTS Christian Stary Florida International University School of Computer Science University Park Miami, FL 33199 stary@fiu.scs.edu or vexpert!stary@relay.EU.net DPS (Distributed Problem Solving) is a term used as a shorthand way of referring to a diverse set of concerns about supporting multiple individuals working together to solve one or more common problems. The more and longer investigations are performed on how cooperative problem solving is performed, the more it becomes evident that cooperative decision making is the crucial point in DPS (Lesser et al., 1987; Sycara, 1989). Productivity of groups can only be enhanced, if the work context, i.e., knowledge processing as well as interaction procedures using common knowledge in a decision-making process, can be modelled in a comprehensive way (Bullen et al., 1990). Thus, incorporating decision support into problem solving environments has at least to deal with: cooperation (concerning communication capabilities, roles and organization of work), concurrent events, and shared knowledge (concerning the common problem as well as decision procedures). To cope with the diversity of issues and their integration for the development of models, several disciplines have already contributed concepts and formalisms for cooperative decision making: Organizational Science (e.g., Huber, 1984), Artificial Intelligence (AI) (e.g., Huhns, 1987), Office Automation (e.g., Conklin et al., 1988), Operations Research (e.g., Jarke et al., 1987), and Computer Supported Cooperative Work (CSCW) (e.g., Malone, 1988). In the following we investigate in how far existing approaches model decision support in distributed cooperative environments comprehensively. INFORMATION SHARING ------------------- Information sharing support is a term which summarizes all approaches covering basic activities for argument exchange in decision making (i.e. messages, tasks, etc.): Object Typing ------------- Henderson et al., 1986 enabled users of Rooms to create local sets of objects to protect them from overload and to allow individual environments. Although the system has been used for desktop objects its concept for structuring shared workspaces shows a way to focus attention on persuasion, dialogue and negotiation. An concept of high originality for structuring information spaces was developed by Halasz et al., 1987. They encoded the foci of work by index cards, which can be easily linked and cross-referenced. Message Typing -------------- To prevent information overload and to support structured cooperation, Information Lens (Malone et al., 1987) uses (group-defined) message types. They are used to provide meta-information on messages. The system routes and selects messages according to the needs of group members. Thus, the emergence of conventions among agents is supported. Task Typing ----------- For Co-Authoring Muse (Hodges et al., 1989) supports cooperation by four different representation schemes, including directed graphs, declarative constraints, and procedural descriptions. For specialized groups problem-specific languages can be created. NEGOTIATION SUPPORT ------------------- Negotiation support tools have been designed to provide quantitative support of decision processes by validation of values indicating success resp. failure of exchanged arguments for persuasion: Application of Game Theory -------------------------- Whenever game theory has been incorporated into interaction models, the strategic behaviour of agents has been characterized, e.g., by introducing types of rational activities. Game theory applications assume concurrent common knowledge, i.e. interaction within continuous environments. For example, Rosenschein et al., 1985 assume a payoff matrix to be concurrent common knowledge. This assumption is based on the belief that agents are always willing to cooperate. Since this assumption is somewhat unrealistic, it can be overridden by approximating preferences of agents. - Debate modelling Debates are commonly understood as the exchange of arguments along of semantic links among agents. For instance, in gIBIS (Conklin et al., 1988), a hypertext tool for exploratory policy discussions, the underlying model of argument exchange is based on the representation of internal structures of design decisions as well as high level dependencies which grow up among agents: - Each problem has to be defined by one or more key issues. - Each issue can have many position statements. A position statement is a statement or an assertion resolving the issue. Positions may exclude each other. - Each position may have one or more arguments which support the position or object to it. For each issue there exists a tree whose root node is constituted by an issue. The root's children are position statements. The children of positions are arguments. A variety of links, e.g., 'responds-to' between position and issue, allows to trace and represent argument exchange. In summary, negotiation support can be achieved by quantification of arguments, by application of game-theoretical strategies, and by providing semantical links between predefined entities of argument exchange (i.e., position statement, issue, and argument). With the exception of game theory applications, there exists no stop condition resp. a way of recognizing that an issue has been resolved by agreement upon some position statement. INTERACTION AMONG RATIONAL AGENTS --------------------------------- Multiagent interaction research is traditionally focused on planning, because cooperation has been identified as aggregation of understanding, planning, and reasoning (Durfee, 1988). Debate modeling has been primarily modeled as goal-oriented: Goals and Protocols ------------------- The first approach to argumentation modeling can be considered to be the Contract Net model introduced by Smith, 1980. Its intended goal was the automation of agents' behavior with respect to negotiations. Agents should be able to communicate their specific desires (goals) and compromise to reach mutually beneficial agreements. The protocols used in Contract Nets ``generate considerable communication overhead'' (Huhns, 1987) because they are based on government contract awarding setup. Negotiation was understood as one agent announcing the availability of tasks and awarding them to other bidding agents. - Economic Extensions Further developments, e.g., Malone et al., 1988 refine the Contract Net approach by overlaying them with a more sophisticated economic model, where optimality unter certain conditions can be proven. In addition, agents are not assumed to act autonomously. In the authors' view, task sharing algorithms have to be specified by a proper language. - Cognitive Extensions Sycara, 1989 elaborated the motivational aspects from Malone et al., 1988. She modelled cognitive aspects of negotiations. Her work is based on the assumption that information resp. argument exchange within negotiations constitutes successful multiagent interaction, originally assumed by Durfee, 1988. Since cognitive events may change, interaction behaviour cannot be specified in advance by static models. In considering interaction as a game of strategies each agent within multiagent environments only has partial control over the consequences of his/her/its activities (Galliers, 1988}. To take into account partial autonomy of agents they are characterized by goals and beliefs. To represent relationships between goals and beliefs, 'preferences' have been defined. In addition, 'interests' denote goals which the agent not only believes to be achievable but which he/she/it believes will eventually be achievable. Interaction among agents is determined by exchanging statements which are based on goals, beliefs, interests and preferences. Conflicts in interaction concern either goals or beliefs. Negotiations are defined as situations where arguments have to be exchanged for conflict resolution. In case of no conflicts, situations are called cooperative. In any case, arguments are generated by an agent, which has a belief that the addressed agent(s) has (have) a certain goal. Plans ----- To increase cooperative behaviour, Sycara, 1989 introduced the term of persuasive argumentation which denotes a mechanism that achieves convergence towards a global solution by purposefully modifying plans, goals and the behaviour of other agents. Negotiation is considered to be a ``planning process for coordinating not fully cooperative agents'' (Sycara, 1989). Persuasive argumentation is based on the assumption that negotiation is that kind of interaction which ensures the willingness to cooperate with other agents. Thus, communicated information is used to convince agents to cooperate. To perform that task, an agent has to reason about another agent to modify its own intentions and plans. Agents are represented by belief structures containing goals and their attached importance. The belief structure is mapped to an acyclic graph, which is searched and updated during negotiations. Each argument is used within a negotiation strategy to achieve certain goals. Beyond that, the concept of preference structures represents an agent in terms of selections among future alternatives and past activities. Each alternative is evaluated in terms of a number of attributes that an agent considers to be important. The resulting set of attributes is called 'utility'. Apparently, neither pure goal-oriented approaches nor their extensions allow comprehensive representation of (concurrent) collaborations and decision making. EVALUATION ---------- The existing models are more or less comprehensive. Logic-based approaches, e.g., by modeling beliefs, as well as information processing models do not comprise common knowledge, collaborative activities, and decision processes in distributed problem solving. Conventional, i.e., non-AI approaches to model cooperation are focussed on structuring information based on clustering resp. message typing. They handle cooperation implicitly by providing problem-oriented contexts which has to be made explicit for specification of knowledge in distributed problem solving environments. To enhance transparency, dynamic entities like processes have to include the required information to identify shared knowledge, the status of the decision making process and the role(s) of agents. Such a comprehensive model allows us to overcome particular shortcomings which we have found in current approaches: 1. Histories concerning agents, messages, and roles cannot be accessed. Thus, tracing interactions is not possible. 2. Temporal constraints cannot be specified in terms of (in)consistencies of shared information in the strength of centralized control. Thus, the knowledge of a problem solver at a certain time cannot be specified explicitly. 3. Once a common context is achieved, it cannot be adapted to the status of the collaborative problem solving process. There are no mechanisms to adapt the representation of cooperative distributed problem solving processes according to organizational needs. 4. Intentions, beliefs and/or attitudes, like the unwillingness to collaborate, cannot be the basic assumptions for modeling cooperative decision making. Rather they are considered higher categories of social behaviour, which are not primarily problem-oriented and thus, have to be modeled after modeling basic communication acts like information exchange. Alternative approaches, such as process-oriented agent-to-agent communication seem to be promising, but have to be elaborated to determine their usability for comprehensive modeling of problem solving in distributed environments. REFERENCES ---------- Bullen, Ch.V.; Bennett, J.L.: Groupware in Practice: An Interpretation of Work Experience, CISR WP No. 205, MIT, March 1990. Conklin, J.; Begemann, M.L.: gIBIS: A Hypertext Tool for Exploratory Policy Discussion, in: ACM Transactions on Office Information, Vol. 6, No. 4, pp.~303-331, October 1988. Durfee, E.H.: Coordination of Distributed Problem Solvers, Kluwer, Boston, 1988. Galliers, J.G.: A Strategic Framework for Multi-Agent Cooperative Dialogue, in: Proceedings ECAI'88, ed: Kodratoff, Y., GI, pp.~415-420, Munich, 1988. Halasz, F.G.; Moran, T.P.; Trigg, R.H.: NoteCards in a Nutshell, in: Proceedings CHI'87, ACM, Toronto, pp. , April 1987. Henderson, D.; Austin, Jr.; Card, St.C.: Rooms: The Use of Multiple Virtual Workspaces to Reduce Space Contention in a Window-Based Graphical User Interface, in: ACM Transactions on Graphics, Vol. 5, No. 3, July 1986. Hodges, M.E.; Sasnett, R.M.; Ackermann, M.S.: A Construction Set for Multimedia Applications, in: IEEE Software, January 1989. Huber, G.P.: Issues in the Design of Group Decision Support Systems, in: MIS Quarterly, pp.~195-205, September 1984. Huhns, M.N. (ed.): Distributed Artificial Intelligence, Pitman, London, 1987. Jarke, M.; Jelassi, M.T.; Shakun, M.F.: MEDIATOR: Towards a Negotiation Support System, in: European Journal of Operational Research, Vol. 3, September 1987. Lesser, V.R.; Corkill, D.G.: Distributed Problem Solving, in: Encyclopedia of Artificial Intelligence, pp.~245-251, Wiley, New York, 1987. Malone, T.W.; Grant, K.R.; Turbak, F.A.; Brobst, St.A.; Cohen, M.D.: Intelligent Information-Sharing Systems, in: Communications of the ACM, Vol. 30, No. 5, pp.~390-402, May, 1987. Malone, T.W.; Fikes, R.E.; Howard, M.T.: Enterprise: A Market-Like Scheduler for Distributed Computing Environments, in: The Ecology of Computation, ed.: Huberman, B.A., North Holland, Amsterdam, 1988. Rosenschein, J.S.; Genesereth, M.R.: Deals among Rational Agents, in: Proceedings IJCAI'85, pp.~91-99, Los Angeles, August 1985. Smith, R.G.: The Contract Net Protocol: High Level Communication and Control in a Distributed Problem Solver, in: IEEE Transactions on Systems, Man and Cybernetics, Vol. C-29, No. 12, December 1980. Sycara, K.P.: Resolving Conflicts via Negotiation, in: Proceedings AAAI'88, pp.~245-249, St. Paul, Minnesota, August 1988. Sycara, K.P.: Argumentation: Planning Other Agents' Plans, in: Proceedings IJCAI'89, pp.~517-523, Detroit, August 1989.