Automated norm synthesis in an agent-based planning environment

ABSTRACT

Norms and social laws are one of the key mechanisms used to facilitate coordination in multiagent systems. In existing approaches the process of designing useful norms has to either be performed by a human expert, or requires a full enumeration of the state space which is bound to cause tractability problems in non-trivial domains. In this paper we propose a novel automated synthesis procedure for prohibitive norms in planning-based domains that disallow access to a set of predefined undesirable states. Our method performs local search around declarative specifications of states using AI planning methods. Using this approach, norms can be synthesised in a generalised way over incomplete state specifications to improve the efficiency of the process in many practical cases, while producing concise, generalised, social norms that are applicable to entire sets of system states. We present an algorithm that utilises traditional planning techniques to ensure continued accessibility under the prohibitions introduced by norms. An analysis of the computational properties of our algorithm is presented together with a discussion of possible heuristic improvements.

REFERENCES

• 1: G. Boella, L. van der Torre, and H. Verhagen. A normative framework for agent-based systems. Computational and Mathematical Organization Theory, 12(2--3):71--79, Oct. 2006.
• 2: W. Briggs and D. Cook. Flexible social laws. In In Proceedings 14th International Joint Conference on Artificial Intelligence, pages 688--693, 1995.
• 3: David Fitoussi , Moshe Tennenholtz, Choosing social laws for multi-agent systems: minimality and simplicity, Artificial Intelligence, v.119 n.1-2, p.61-101, May 2000 [doi>10.1016/S0004-3702(00)00006-0]
• 4: D. Lewis. Convention: A Philosophical Study. Harvard University Press, first edition, 1969.
• 5: B. Nebel. On the compilability and expressive power of propositional planning formalisms. Journal of Artificial Intelligence, 12:271--315, May 2000.
• 6: Shmuel Onn , Moshe Tennenholtz, Determination of social laws for multi-agent mobilization, Artificial Intelligence, v.95 n.1, p.155-167, Aug. 1997 [doi>10.1016/S0004-3702(97)00045-3]
• 7: Y. Shoham and M. Tennenholtz. On the synthesis of useful social laws for artificial agent societies. In Proceedings of the 10th National Conference on Artificial Intelligence, pages 276--281, 1992.
• 8: Yoav Shoham , Moshe Tennenholtz, On social laws for artificial agent societies: off-line design, Artificial Intelligence, v.73 n.1-2, p.231-252, Feb. 1995 [doi>10.1016/0004-3702(94)00007-N]
• 9: W. van der Hoek, M. Roberts, and M. Wooldridge. Social laws in alternating time: Effectiveness, feasibility, and synthesis. Synthese, 156(1), May 2007.
• 10: G. Weiß, editor. Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence. MIT Press, Cambridge, MA, USA, 1999.

INDEX TERMS

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

General Terms:
Algorithms, Design

Keywords:
automated planning, conflict resolution, coordination, norms, social laws