An improvement to matchmaking algorithms for middle agents

ABSTRACT

A question frequently asked in multi-agent systems (MASs) concerns the efficient search for suitable agents to solve a specific problem. To answer this question, different types of middle agents are usually employed. The performance of middle agents relies heavily on the matchmaking algorithms used. Matchmaking is the process of finding an appropriate provider for a requester through a middle agent. There has been substantial work on matchmaking in different kinds of middle agents. To our knowledge, almost all currently used matchmaking algorithms missed one point when doing matchmaking -- the matchmaking is only based on the advertised capabilities of provider agents. The actual performance of provider agents in accomplishing delegated tasks is not considered at all. This results in the inaccuracy of the matchmaking outcomes as well as the random selection of provider agents with the same advertised capabilities. The quality of service of different service provider agents varies from one agent to another even though they claimed they have the same capabilities. To this end, it is argued that the practical performance of service provider agents has a significant impact on the matchmaking outcomes of middle agents. An improvement to matchmaking algorithms is proposed, which makes the algorithms have the ability to consider the track records of agents in accomplishing delegated tasks. How to represent, accumulate, and use track records as well as how to give initial values for track records in the algorithm are discussed. A prototype is also built to verify the algorithm. Based on the improved algorithm, the matchmaking outcomes are more accurate and reasonable.

REFERENCES

• 1: Katia Sycara , Anandee Pannu , Mike Williamson , Dajun Zeng , Keith Decker, Distributed Intelligent Agents, IEEE Expert: Intelligent Systems and Their Applications, v.11 n.6, p.36-46, December 1996 [doi>10.1109/64.546581]
• 2: D. Martin, A. Cheyer, and D. Moran, The Open Agent Architecture: A Framework for Building Distributed Software Systems, Applied Artificial Intelligence, 13(1--2), 1999, 92--128.
• 3: Adam Cheyer , David Martin, The Open Agent Architecture, Autonomous Agents and Multi-Agent Systems, v.4 n.1-2, p.143-148, March-June 2001 [doi>10.1023/A:1010091302035]
• 4: V. S. Subrahmanian , Jurgen Dix , Fatma Ozcan, Heterogeneous Agent Systems, MIT Press, Cambridge, MA, 2000
• 5: R. J. Bayardo, Jr. , W. Bohrer , R. Brice , A. Cichocki , J. Fowler , A. Helal , V. Kashyap , T. Ksiezyk , G. Martin , M. Nodine , M. Rashid , M. Rusinkiewicz , R. Shea , C. Unnikrishnan , A. Unruh , D. Woelk, InfoSleuth: agent-base semantic integration of information in open and dynamic environments, Readings in agents, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 6: K. Decker, K. Sycara, and M. Williamson, Middle Agents for the Internet, Proceedings of 15th IJCAI, Nogoya, Japan, 1997, 578--583.
• 7: Michael R. Genesereth , Steven P. Ketchpel, Software agents, Communications of the ACM, v.37 n.7, p.48-ff., July 1994 [doi>10.1145/176789.176794]
• 8: Stephen T. Welstead, Neural network and fuzzy logic applications in C/C++, John Wiley & Sons, Inc., New York, NY, 1994
• 9: Khaled A. Arisha , Fatma Ozcan , Robert Ross , V. s. Subrahmanian , Thomas Eiter , Sarit Kraus, Impact: A Platform for Collaborating Agents, IEEE Intelligent Systems, v.14 n.2, p.64-72, March 1999 [doi>10.1109/5254.757633]
• 10: Walter Brenner , H. Wittig , Rudiger Zarnekow, Intelligent Software Agents: Foundations and Applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1998
• 11: R. G. Smith, The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver, IEEE Transactions on Computers, 29(12), 1980, 1104--1113.
• 12: A Taxonomy of Middle-Agents for the Internet, Proceedings of the Fourth International Conference on MultiAgent Systems (ICMAS-2000), p.465, July 10-12, 2000
• 13: Katia Sycara , Matthias Klusch , Seth Widoff , Jianguo Lu, Dynamic service matchmaking among agents in open information environments, ACM SIGMOD Record, v.28 n.1, p.47-53, March 1999 [doi>10.1145/309844.309895]
• 14: D. Kuokka and L. Harada, Matchmaking for Information Agents, Proceedings of 14th IJCAI, 1995, 672--678.
• 15: N. Singh, A Common Lisp API and Facilitator for ABSI: Version 2.0.3, Technical Report Logic-93-4, Logic Group, Computer Science Department, Stanford University, 1993.
• 16: Massimo Paolucci , Zhendong Niu , Katia P. Sycara , Constantine Domashnev , Sean Owens , Martin Van Velsen, Matchmaking to Support Intelligent Agents for Portfolio Management, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.1125-1126, July 30-August 03, 2000
• 17: K. Sycara, J. Lu, M. Klusch, and S. Widoff, Matchmaking Among Heterogeneous Agents on the Internet, Proceedings of AAAI Spring Symposium on Intelligent Agents in Cyberspace, Stanford, USA, 1999, http://www.cs.cmu.edu/ ˜softagents/publications.html.
• 18: G. J. Wickler, Using Expressive and Flexible Action Representations to Reason about Capabilities for Intelligent Agent Cooperation, PhD thesis, University of Edinburgh, 1999.
• 19: Matthias Klusch , Katia Sycara, Brokering and matchmaking for coordination of agent societies: a survey, Coordination of Internet agents: models, technologies, and applications, Springer-Verlag, London, 2001
• 20: E. Peter, Chaos and Order in the Capital Markets, John Wiley & Sons, Inc., 1991.
• 21: F. Hoppner, F. Klawonn, R. Kruse, and T. Runkler, Fuzzy Cluster Analysis, John Wiley & Sons, 1999.
• 22: Chengqi Zhang , Zili Zhang , Ong Swee San, An Agent-Based Soft Computing Society, Revised Papers from the Second International Conference on Rough Sets and Current Trends in Computing, p.661-668, October 16-19, 2000

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Intelligent agents

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

General Terms:
Algorithms, Experimentation

Keywords:
intelligent agents, matchmaking, middle agents, multiagent systems