In this paper, Christelis and Rovatsos focus on the problem of norm synthesis, a problem known to be nondeterministic polynomial-time hard (NP-hard). The goal of the paper is to provide an automated design of social norms in planning-based domains.
Social norms represent one form of pre-planning coordination, based on constraining agent behavior. Therefore, social norms allow us to define what behavior is socially acceptable in the system. Norm synthesis deals with avoiding all the states modeled by a specification of undesirable conflict state, while ensuring accessibility to all conflict-free states.
The authors introduce conflict-rooted synthesis, a new three-part approach to solving this problem that guarantees accessibility to all conflict states without entering the specified conflict states. They present two important concepts of the proposed algorithm: state inference and state refinement. These two states are defined using appropriate key functions. State refinement occurs when some additional literals are introduced into some state specifications.
Overall, the paper is of high quality, the proposed method is novel, and the topic is fairly interesting. The paper is aimed at researchers and practitioners in the area of artificial intelligence.