skip to main content
10.5555/1558013.1558035guideproceedingsArticle/Chapter ViewAbstractPublication PagesaamasConference Proceedingsconference-collections
research-article
Free access

Automated norm synthesis in an agent-based planning environment

Published: 10 May 2009 Publication History

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]
D. Fitoussi and M. Tennenholtz. Choosing social laws for multi-agent systems: Minimality and simplicity. Artificial Intelligence, 119:61--101, 2000.
[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]
S. Onn and M. Tennenholtz. Determination of social laws for multi-agent mobilization. Artificial Intelligence, 95:155--167, Jun 1997.
[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]
Y. Shoham and M. Tennenholtz. On social laws for artificial agent societies: Off-line design. Journal of Artificial Intelligence, 73(1--2):231--252, Feb. 1995.
[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.

Cited By

View all
  • (2016)Normative multiagent systemsProceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence10.5555/3060621.3060777(1123-1129)Online publication date: 9-Jul-2016
  • (2016)Designing minimal effective normative systems with the help of lightweight formal methodsProceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering10.1145/2950290.2950307(50-60)Online publication date: 1-Nov-2016
  • (2015)Online Automated Synthesis of Compact Normative SystemsACM Transactions on Autonomous and Adaptive Systems10.1145/272002410:1(1-33)Online publication date: 9-Mar-2015
  • Show More Cited By

Index Terms

  1. Automated norm synthesis in an agent-based planning environment

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image Guide Proceedings
    AAMAS '09: Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems - Volume 1
    May 2009
    701 pages
    ISBN:9780981738161

    Sponsors

    • Drexel University
    • Wiley-Blackwell
    • Microsoft Research: Microsoft Research
    • Whitestein Technologies
    • European Office of Aerospace Research and Development, Air Force Office of Scientific Research, United States Air Force Research Laboratory
    • The Foundation for Intelligent Physical Agents

    Publisher

    International Foundation for Autonomous Agents and Multiagent Systems

    Richland, SC

    Publication History

    Published: 10 May 2009

    Author Tags

    1. automated planning
    2. conflict resolution
    3. coordination
    4. norms
    5. social laws

    Qualifiers

    • Research-article

    Acceptance Rates

    AAMAS '09 Paper Acceptance Rate 132 of 651 submissions, 20%;
    Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)40
    • Downloads (Last 6 weeks)2
    Reflects downloads up to 19 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2016)Normative multiagent systemsProceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence10.5555/3060621.3060777(1123-1129)Online publication date: 9-Jul-2016
    • (2016)Designing minimal effective normative systems with the help of lightweight formal methodsProceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering10.1145/2950290.2950307(50-60)Online publication date: 1-Nov-2016
    • (2015)Online Automated Synthesis of Compact Normative SystemsACM Transactions on Autonomous and Adaptive Systems10.1145/272002410:1(1-33)Online publication date: 9-Mar-2015
    • (2013)Automated synthesis of normative systemsProceedings of the 2013 international conference on Autonomous agents and multi-agent systems10.5555/2484920.2484998(483-490)Online publication date: 6-May-2013
    • (2011)Open issues for normative multi-agent systemsAI Communications10.5555/2350116.235012224:3(233-264)Online publication date: 1-Aug-2011
    • (2010)Learning from experience to generate new regulationsProceedings of the 6th international conference on Coordination, organizations, institutions, and norms in agent systems10.5555/2018118.2018140(337-356)Online publication date: 1-May-2010
    • (2010)Norm refinement and design through inductive learningProceedings of the 6th international conference on Coordination, organizations, institutions, and norms in agent systems10.5555/2018118.2018124(77-94)Online publication date: 1-May-2010
    • (2010)Exploiting domain knowledge to improve norm synthesisProceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1 - Volume 110.5555/1838206.1838317(831-838)Online publication date: 10-May-2010

    View Options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Login options

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media