Automated Norm Synthesis in an Agent-based Planning Environment

George Christelis, Michael Rovatsos

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.
Original languageEnglish
Title of host publicationAAMAS '09 Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems - Volume 1
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems
Number of pages8
ISBN (Print)978-0-9817381-6-1
Publication statusPublished - 2009


  • automated planning, conflict resolution, coordination, norms, social laws


Dive into the research topics of 'Automated Norm Synthesis in an Agent-based Planning Environment'. Together they form a unique fingerprint.

Cite this