Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Commitment-modeled protocols enable flexible and robust interactions among agents. However, existing work has focused on features and capabilities of protocols without considering the active role of agents in them. Therefore, in this paper we propose to augment agents with the ability of reasoning about and manipulating their commitments to maximize the system utility. We adopt a bottom-up approach by first investigating the intra-dependency between each commitment's preconditions and result which leads to a novel classification of commitments as well as a formalism to express various types of complex commitment. Within this framework, we provide a set of inference rules to benefit an agent by means of commitment refactoring which enables composition and/or decomposition of its commitments to optimize runtime performance. We also discuss the pros and cons of an agent scheduling and executing its commitments in parallel. We propose a reasoning strategy and an algorithm to minimize possible loss when the commitment is broken and maximize the overall system robustness and performance. Experiments show that concurrent schedules based on the features of commitments can boost the system performance significantly.

REFERENCES

• 1: Bradley J. Clement , Edmund H. Durfee, Theory for coordinating concurrent hierarchical planning agents using summary information, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.495-502, July 18-22, 1999, Orlando, Florida, United States
• 2: Philip R. Cohen , Hector J. Levesque, Intention is choice with commitment, Artificial Intelligence, v.42 n.2-3, p.213-261, March 1990 [doi>10.1016/0004-3702(90)90055-5]
• 3: M. Dastani, M. B. van Riemsdijk, and J.-J. C. Meyer. Programming multi-agent systems in 3apl. In Multi-Agent Programming, pages 39--67. 2005.
• 4: Nirmit Desai , Ashok U. Mallya , Amit K. Chopra , Munindar P. Singh, Interaction Protocols as Design Abstractions for Business Processes, IEEE Transactions on Software Engineering, v.31 n.12, p.1015-1027, December 2005 [doi>10.1109/TSE.2005.140]
• 5: Mark D'Inverno , Michael Luck , Michael Georgeff , David Kinny , Michael Wooldridge, The dMARS Architecture: A Specification of the Distributed Multi-Agent Reasoning System, Autonomous Agents and Multi-Agent Systems, v.9 n.1-2, p.5-53, July-September 2004 [doi>10.1023/B:AGNT.0000019688.11109.19]
• 6: Leah Epstein , Rob Van Stee, Online scheduling of splittable tasks, ACM Transactions on Algorithms (TALG), v.2 n.1, p.79-94, January 2006 [doi>10.1145/1125994.1125999]
• 7: B. Gaudou, A. Herzig, and D. Longin. Grounding and the expression of belief. In KR, pages 221--229, 2006.
• 8: N. R. Jennings. Commitments and conventions: The foundation of coordination in multi-agent systems. The Knowledge Engineering Review, 8(3):223--250, 1993.
• 9: Audun Jøsang , Roslan Ismail , Colin Boyd, A survey of trust and reputation systems for online service provision, Decision Support Systems, v.43 n.2, p.618-644, March, 2007 [doi>10.1016/j.dss.2005.05.019]
• 10: J. J. E. Kelley. Critical-path planning and scheduling: Mathematical basis. Operations Research, 9(3):296--320, 1961.
• 11: Shakil M. Khan , Yves Lespérance, On the semantics of conditional commitment, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160883]
• 12: S. Kumaran , P. Bishop , T. Chao , P. Dhoolia , P. Jain , R. Jaluka , H. Ludwig , A. Moyer , A. Nigam, Using a model-driven transformational approach and service-oriented architecture for service delivery management, IBM Systems Journal, v.46 n.3, p.513-529, July 2007
• 13: João Alexandre Leite , José Júlio Alferes , Luís Moniz Pereira, Multi-dimensional Dynamic Knowledge Representation, Proceedings of the 6th International Conference on Logic Programming and Nonmonotonic Reasoning, p.365-378, September 17-19, 2001
• 14: Ashok U. Mallya , Munindar P. Singh, An algebra for commitment protocols, Autonomous Agents and Multi-Agent Systems, v.14 n.2, p.143-163, April 2007 [doi>10.1007/s10458-006-7232-1]
• 15: Zohar Manna , Amir Pnueli, The temporal logic of reactive and concurrent systems, Springer-Verlag New York, Inc., New York, NY, 1992
• 16: Project Scheduling Problem Library - PSPLIB. http://129.187.106.231/psplib/, last visited 28 September 2008.
• 17: Sarvapali D. Ramchurn , Dong Huynh , Nicholas R. Jennings, Trust in multi-agent systems, The Knowledge Engineering Review, v.19 n.1, p.1-25, March 2004 [doi>10.1017/S0269888904000116]
• 18: Tuomas Sandholm , Victor Lesser, Leveled-commitment contracting: a backtracking instrument for multiagent systems, AI Magazine, v.23 n.3, p.89-100, Fall 2002
• 19: Yoav Shoham, Agent-oriented programming, Artificial Intelligence, v.60 n.1, p.51-92, March 1993 [doi>10.1016/0004-3702(93)90034-9]
• 20: J. Thangarajah, L. Padgham, and M. Winikoff. Detecting&avoiding interference between goals in intelligent agents. In IJCAI, pages 721--726, 2003.
• 21: Mario Verdicchio , Marco Colombetti, A logical model of social commitment for agent communication, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860660]
• 22: D. N. Walton and E. C. Krabbe. Commitment in Dialogue: Basic Concepts of Interpersonal Reasoning. State University of New-York Press, NY, 1995.
• 23: Michael Winikoff, Implementing commitment-based interactions, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329283]
• 24: Pinar Yolum , Munindar P. Singh, Commitment Machines, Revised Papers from the 8th International Workshop on Intelligent Agents VIII, p.235-247, August 01-03, 2001

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Reliability

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Languages and structures; Multiagent systems

General Terms:
Design, Performance, Reliability

Keywords:
agent interaction, commitment machines, commitment refactoring, robustness, scheduling