Robust Regulation Adaptation in Multi-Agent Systems

Abstract

Adaptive organisation-centred multi-agent systems can dynamically modify their organisational components to better accomplish their goals. Our research line proposes an abstract distributed architecture (2-LAMA) to endow an organisation with adaptation capabilities. This article focuses on regulation-adaptation based on a machine learning approach, in which adaptation is learned by applying a tailored case-based reasoning method. We evaluate the robustness of the system when it is populated by non compliant agents. The evaluation is performed in a peer-to-peer sharing network scenario. Results show that our proposal significantly improves system performance and can cope with regulation violators without incorporating any specific regulation-compliance enforcement mechanisms.

References

1. Aamodt, A. and Plaza, E. 1994. Case-based reasoning: Foundational issues, methodological variations, and system approaches. Artif. Intell. Commun. 7, 1, 39--59.
2. Alda, S. and Cremers, A. B. 2005. Towards composition management for component-based peer-to-peer architectures. Electron. Note Theoret. Comput. Sci. 114, 47--64.
3. Artikis, A., Kaponis, D., and Pitt, J. 2009. Multi-agent systems: Semantics and dynamics of organisational models. V. Dignum, IGI Global, 460--479.
4. Axelrod, R. 1986. An evolutionary approach to norms. Amer. Polit. Sci. Rev. 80, 4, 1095--1111.
5. Becker, G. S. 1968. Crime and punishment: An economic approach. J. Polit. Econ. 76, 2, 169--217.
6. Bittencourt, I. I., Costa, E., Silva, M., and Soares, E. 2009. A computational model for developing semantic Web-based educational systems. Knowl.-Based Syst. 22, 4, 302--315.
7. BitTorrentInc. 2001. BitTorrent protocol specification. http://www.bittorrent.org/beps/bep_0003.html.
8. Boissier, O. and Gâteau, B. 2007. Normative multi-agent organizations: Modeling, support and control. Norm. Multi-Agent Syst. 1--17.
9. Bou, E., López-Sánchez, M., and Rodríguez-Aguilar, J. A. 2009. Autonomic electronic institutions’ self-adaptation in heterogeneous agent societies. In Organized Adaption in Multi-Agent Systems, 18--35.
10. Brooks, L., Iba, W., and Sen, S. 2011. Modeling the emergence and convergence of norms. In Proceedings of IJCAI. 97--102.
11. Campos, J. 2011. Adaptive organisation centered multi-agent systems. PhD thesis, University of Barcelona.
12. Campos, J., Esteva, M., López-Sánchez, M., and Morales, J. 2009a. An organisational adaptation simulator for p2p networks. In Proceedings of Engineering Societies in the Agents World X (ESAW). 240--242.
13. Campos, J., López-Sánchez, M., Esteva, M., Novo, A., and Morales, J. 2009b. 2-LAMA Architecture vs. BitTorrent protocol in a peer-to-peer scenario. In Proceedings of Catalan Congres of Artificial Intelligence (CCIA).
14. Campos, J., López-Sánchez, M., Esteva, M., and Piqué, N. 2010. Comparison of topologies in peer-to-peer data sharing networks. In Artificial Intelligence Research and Development, Proceedings of the 13th International Conference of the Catalan Association for Artificial Intelligence. 49--58.
15. Campos, J., Esteva, M., Lopez-Sanchez, M., Morales, J., and Salamó, M. 2011. Organisational adaptation of multi-agent systems in a peer-to-peer scenario. Comput. 91, 169--215.
16. Carley, K. 1995. Computational and mathematical organization theory: Perspective and directions. Comput. Math. Org. Theory 1, 1, 39--56.
17. Carley, K., Lee, J.-S., and Krackhardt, D. 2002. Destabilizing networks. Connections 24, 3, 79--92.
18. Conte, R., Andrighetto, G., and Campenni, M. 2010. Internalizing norms: A cognitive model of (social) norms’ internalization. Int. J. Agent Technol. Syst. 2, 1, 63--73.
19. Corkill, D. D. and Lesser, V. R. 1983. The use of meta-level control for coordination in a distributed problem solving network. In Proceedings of the 8th International Joint Conference on Artificial Intelligence (IJCAI). Morgan Kaufmann Publishers Inc., San Francisco, CA, 748--756.
20. Costa, A. and Demazeau, Y. 1996. Toward a formal model of multi-agent systems with dynamic organizations. In Proceedings of the International Conference on Multi-Agent Systems. MIT Press, 431.
21. Cuevas, R., Laoutaris, N., Yang, X., Siganos, G., and Rodriguez, P. 2009. Deep diving into BitTorrent locality. In Proceedings of the 5th International Student Workshop on Emerging Networking Experiments and Technologies. 7--8.
22. Dastani, M., Meyer, J.-J., and Tinnemeier, N. 2012. Programming norm change. J. Appl. Non-Class. Logics 22, 1--2, 151--180.
23. Davies, J., Goel, A. K., and Yaner, P. W. 2008. Proteus: Visuospatial analogy in problem-solving. Knowl.-Based Syst. 21, 7, 636--654.
24. Demšar, J. 2006. Statistical comparisons of classifiers over multiple data sets. J. Mach. Learn. Res. 7, 1--30.
25. de Pinninck, A., Sierra, C., and Schorlemmer, M. 2008. Distributed Norm Enforcement via Ostracism. Lecture Notes in Computer Science, vol. 4870, 301.
26. Dignum, V. 2004. A model for organizational interaction: Based on agents, founded in logic. PhD Monography, Universiteit Utrecht.
27. Dignum, V., Dignum, F., Furtado, V., Melo, A., and Sonenberg, L. 2005. Towards a simulation tool for evaluating dynamic reorganization of agents societies. In Proceedings of Workshop on Socially Inspired Computing, AISB Convention. Vol. 230. 153--162.
28. Ferber, J., Gutknecht, O., and Michel, F. 2004. From agents to organizations: An organizational view of multi-agent systems. In Agent Oriented Software Engineering IV, 214--230.
29. Friedman, M. 1937. The use of ranks to avoid the assumption of normality implicit in the analysis of variance. J. Amer. Statist. Assoc. 32, 200, 675--701.
30. Garlan, D., Allen, R., and Ockerbloom, J. 1994. Exploiting style in architectural design environments. In Proceedings of the 2nd ACM SIGSOFT Symposium on Foundations of Software Engineering (SIGSOFT). ACM, New York, NY, 175--188.
31. Gasparetti, F., Micarelli, A., and Sciarrone, F. 2009. A Web-based training system for business letter writing. Knowl.-Based Syst. 22, 4, 287--291.
32. Glaser, N. and Morignot, P. 1997. The reorganization of societies of autonomous agents. In Multi-Agent Rationality, M. Boman and W. Van de Velde Eds., Lecture Notes in Computer Science Series, vol. 1237, Springer Berlin, 98--111.
33. Golobardes, E., Llorà, X., Salamó, M., and Martí, J. 2002. Computer aided diagnosis with case-based reasoning and genetic algorithms. Knowl.-Based Syst. 15, 1--2, 45--52.
34. Gomez-Sanz, J. J. and Pavon, J. 2005. Implementing multi-agent systems organizations with INGENIAS. In Proceedings of ProMAS. 236--251.
35. Grizard, A., Vercouter, L., Stratulat, T., and Muller, G. 2007. A peer-to-peer normative system to achieve social order. In Proceedings of the Workshop on Coordination, Organizations, Institutions, and Norms in Agent Systems (COIN).
36. Guessoum, Z., Ziane, M., and Faci, N. 2004. Monitoring and organizational-level adaptation of multi-agent systems. In Proceedings of the 3rd International Joint Conference on Autonomous Agents and Multiagent Systems. IEEE Computer Society, Los Alamitos, CA, 514--521.
37. Horling, B., Benyo, B., and Lesser, V. 2001. Using self-diagnosis to adapt organizational structures. In Proceedings of the 5th International Conference on Autonomous Agents. ACM, New York, NY, 529--536.
38. Hübner, J. F., Sichman, J. S., and Boissier, O. 2004. Using the MOISE+ for a cooperative framework of MAS reorganisation. In Proceedings of the 17th Brazilian Symposium on Artificial Intelligence (SBIA). 506--515.
39. Hübner, J. F., Sichman, J. S., and Boissier, O. 2005. S-MOISE+: A middleware for developing organised multi-agent systems. In Proceedings of the Workshop on Coordination, Organizations, Institutions, and Norms in Agent Systems (COIN). 64--78.
40. Jones, J. and Goel, A. K. 2004. Revisiting the credit assignment problem. In Proc. AAAI (Challenges of Game AI) 4, 4.
41. Kota, R., Gibbins, N., and Jennings, N. 2008. Decentralised structural adaptation in agent organisations. AAMAS Workshop Organised Adaptation in MAS, 54--71.
42. Martin, C. and Barber, K. S. 2006. Adaptive decision-making frameworks for dynamic multi-agent organizational change. Auton. Agents Multi-Agent Syst. 13, 3, 391--428.
43. Mukherjee, P., Sen, S., and Airiau, S. 2008. Norm emergence under constrained interactions in diverse societies. In Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS). International Foundation for Autonomous Agents, Richland, SC, 779--786.
44. Pasquier, P., Flores, R. A., and Chaib-Draa, B. 2005. Modelling flexible social commitments and their enforcement. In Proceedings of Engineering Societies in the Agents World V (ESAW). 153--165.
45. Patterson, D., Rooney, N., Galushka, M., Dobrynin, V., and Smirnova, E. 2008. Sophia-TCBR: A knowledge discovery framework for textual case-based reasoning. Knowl.-Based Syst. 21, 5, 404--414.
46. Piatek, M., Isdal, T., Anderson, T., Krishnamurthy, A., and Venkataramani, A. 2007. Do incentives build robustness in BitTorrent? In Proceedings of NSDI.
47. Powell, J. H., Hauff, B., and Hastings, J. D. 2005. Evaluating the effectiveness of exploration and accumulated experience in automatic case elicitation. In Proceedings of the International Conference on Case-Based Reasoning (ICCBR). 397--407.
48. Richter, M. M. 1995. The knowledge contained in similarity measures. In Proceedings of the International Conference on Case-Based Reasoning (ICCBR).
49. Riesbeck, C. K. and Schank, R. C. 1989. Inside Case-Based Reasoning. Lawrence Erlbaum Associates, Hillsdale, NJ.
50. Salamó, M. and López-Sánchez, M. 2011a. Adaptive case-based reasoning using retention and forgetting strategies. Knowl.-Based Syst. 24, 2, 230--247.
51. Salamó, M. and López-Sánchez, M. 2011b. Rough set-based approaches to feature selection for case-based reasoning classifiers. Pattern Recog. Lett. 32, 280--292.
52. Savarimuthu, B., Cranefield, S., Purvis, M., and Purvis, M. 2012. Identifying prohibition norms in agent societies. Artif. Intell. Law, 1--46.
53. Savarimuthu, B. T. R. and Cranefield, S. 2009. A categorization of simulation works on norms. Dagstuhl Seminar Proceedings 09121: Normative Multi-Agent Systems.
54. Sen, O. and Sen, S. 2010. Effects of social network topology and options on norm emergence. In Coordination, Organizations, Institutions and Norms in Agent Systems V, 211--222.
55. Sen, S. and Airiau, S. 2007. Emergence of norms through social learning. In Proceedings of IJCAL. 1507--1512.
56. Serugendo, G. D. M., Gleizes, M. P., and Karageorgos, A. 2006. Self-organisation and emergence in MAS: An overview. Informatica 30, 45--54.
57. Shoham, Y. and Tennenholtz, M. 1997. On the emergence of social conventions: Modeling, analysis, and simulations. Artif. Intell. 94, 1--2, 139--166.
58. Sims, M., Corkill, D., and Lesser, V. 2008. Automated organization design for multi-agent systems. Auton. Agents Multi-Agent Syst. 16, 2, 151--185.
59. Sutton, R. S. and Barto, A. G. 1998. Reinforcement Learning: An introduction. The MIT press.
60. Villatoro, D., Andrighetto, G., Conte, R., and Sabater-Mir, J. 2011a. Dynamic sanctioning for robust and cost-efficient norm compliance. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence. 414--419.
61. Villatoro, D., Sabater-Mir, J., and Sen, S. 2011b. Social instruments for robust convention emergence. In Proceedings of IJCAI. 420--425.
62. Watson, I. 1997. Applying Case-Based Reasoning: Techniques for Enterprise Systems. Morgan Kaufmann Publishers Inc.
63. Wooldridge, M. 2009. An Introduction to Multiagent Systems. Wiley.
64. Xie, H., Yang, Y. R., Krishnamurthy, A., Liu, Y., and Silberschatz, A. 2008. P4P: Provider portal for applications. ACM SIGCOMM Comput. Comm. Rev. 38, 4, 351--362.
65. Zhang, C., Abdallah, S., and Lesser, V. 2009. Integrating organizational control into multi-agent learning. In Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems. Vol. 2, International Foundation for Autonomous Agents and Multiagent Systems, 757--764.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Distributed artificial intelligence

      • Multi-agent systems