Preference-based decision making for cooperative knowledge-based systems

ABSTRACT

Recent advances in cooperative knowledge-based systems (CKBS) offer significant promise for intelligent interaction between multiple AI systems for solving larger, more complex problems. In this paper, we propose a logical, qualitative problem-solving scheme for CKBS that uses social choice theory as a formal basis for making joint decisions and promoting conflict resolution. This scheme consists of three steps: (1) the selection of decision criteria and competing alternatives, (2) the formation of preference profiles and collective choices, and (3) the negotiation among agents as conflicts arise in group decision making. In this paper, we focus on the computational mechanisms developed to support steps (2) and (3) of the scheme. In addition, the practicality of the scheme is illustrated with examples taken from a working prototype dealing with collaborative structural design of buildings.

REFERENCES

• 1: ARROW, K. J. 1951 Social Choice and Indtwdual Values. Wiley, New York.
• 2: ATLSS CENTER. 1992. Sixth-year renewal proposal to the NSF, Vol. 2: Projects, Publications, and Biosketches. ATLSS Drive, Imbt Lab., Lehigh Umversity, Bethlehem, Pa., Section 7.
• 3: BORDA, J. C. 1953. Memoire sur les Electzons au Scrutin, 1781. Ists, 44. English translation by A. De Grazla.
• 4: Ivan Bratko, Prolog programming for artificial intelligence, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 5: CARNAP, R. 1962. Logical Foundations of Probability. University of Chicago Press, Chicago, I1.
• 6: CONDORCET, M. 1785. Essaz sur l;4pplzcat~on de I54nalyse a la Probabilitie des Dects~ons rendues ~ la pluralitd des vo~x. Paris, L'Imprimerie Royale.
• 7: John R. Corbin, The art of distributed applications: programming techniques for remote procedure calls, Springer-Verlag New York, Inc., New York, NY, 1991
• 8: DAVIS, M. 1973. Game Theory. Basic Books, New York.
• 9: DAVIS, R., BUCHANAN, G., AND SHORTLIFEE, E. 1-I 1977. Production rules as a representation of a knowledge base consultation system. Arttf. Intell. 8, 15-45.
• 10: Johan de Kleer, An assumption-based TMS, Artificial Intelligence, v.28 n.2, p.127-162, March 1986 [doi>10.1016/0004-3702(86)90080-9]
• 11: DOYLE, J. 1979. A truth maintenance system Artif. InteIl. 12, 2, 231 272.
• 12: DURFEE, E. H., LESSER, V. R., AND CORKILL, D. D. 1989. Cooperative distributed problem solving. In The Handbook of Artzficial Intelhgence, vol. iv, A. Barr P. R. Cohen, E. A. Feigenbaum, Eds., 83-148.
• 13: EBBINGHAUS, H. 1885. Memory. Wiley, New York. Translated in 1964.
• 14: EPHRATI, E., AND ROSENSCHEIN, J. S. 1991. The Clarke tax as a consensus mechanism among automated agents. In Proceedzngs 9th AAAI Conference (July). AAAI/MIT Press, Cambridge, Mass., pp. 173 178.
• 15: GA~DENFORS, P. 1988. Knowledge in Flux--Modeling the Dynamics of Epistemlc States. MIT Press, Cambridge, Mass.
• 16: GASSER, L., AND HILL, R. W. 1989-90. Coordinated problem solvers. Ann. Rev. Comput. Sci. 4, 203-254.
• 17: Jay R. Galbraith, Designing Complex Organizations, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1973
• 18: GALBRAITH, J 1977. OrgamzationalDesign. Addison-Wesley, Reading, Mass.
• 19: KRAUS, S., AND WILKENFELD, J. 1991. Negotmtions over time in a multi-agent environment: prehminary report. In Proceedings 12th IJCAI Con{erence (Sydney, Australia, Aug.), 56 61.
• 20: Thomas W. Malone, Organizing information processing systems: parallels between human organizations and computer systems, Cognition, computing, and cooperation, Ablex Publishing Corp., Norwood, NJ, 1990
• 21: MORIZET-MAHOUOF, AX, P. 1991. Maintaining consistency of a database during monitoring of an evolving process by a knowledge-based systems. IEEE Trans. Syst. Man Cybern. 21, 1, 47 60.
• 22: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 23: SEARLE, J. R., AND VANDERVEKEN, D. 1985. Foundation of Illocutionary Logtc. Cambridge Umverslty Press, Cambridge, Mass.
• 24: SEN, A. 1970. Collective Choice and Social Welfare. Holden-Day, San Francisco.
• 25: SEN, A. 1982. Choice, Welfare, and Measurement. MIT Press, Cambridge, Mass.
• 26: SHAFER, G. 1976. A Mathematical Theory of Evidence. Princeton University Press, Princeton, N.J.
• 27: STERLING, L., AND YALCINALP, L. U. 1989. Explaining Prolog based expert systems using a layered metainterpreter. In Proceedings of the 11th IJCAI, 66-71.
• 28: SYKES, E. A., AND WroTE, C. C. 1991. Multiobjective intelligent computer-aided design. IEEE Truns. Syst. Man. Cybern. 21, 6 (Nov./Dec.), 1498-1511.
• 29: Stephen Tin Chi Wong, Framework for the description and design of cooperative knowledge-based systems, Lehigh University, Bethlehem, PA, 1991
• 30: S. T. C. Wong , J. L. Wilson, A Set of Design Guidelines for Object-Oriented Deductive Systems, IEEE Transactions on Knowledge and Data Engineering, v.5 n.5, p.895-900, October 1993 [doi>10.1109/69.243518]
• 31: WONG, S. T. C. 1992. A communication scheme for cooperative systems communication. In Proceedings of Multi-ugents Cooperatwe Computing Workshop (Kobe, Japan, Dec.).
• 32: S. T. Wong , J. L. Wilson, Extending knowledge-based systems through closely-coupled graphics and windows, Proceedings of the 2nd international conference on Industrial and engineering applications of artificial intelligence and expert systems, p.770-774, June 1989, Tullahoma, Tennessee, United States [doi>10.1145/67312.67346]
• 33: YON NEUMANN, J., AND MORGENSTERN, O. 1944. Theory of Games and Economic Behavior, Princeton University Press, Princeton, N.J.
• 34: ZADEH, L. A. 1975. Fuzzy logic and approximate reasoning. Synthese. 30.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

Additional Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.2 Types of Systems
          Subjects: Decision support (e.g., MIS)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Coherence and coordination

General Terms:
Design, Human Factors, Theory

Keywords:
cooperative knowledge-based systems, cooperative problem solving, decision making, social choice theory