Data-Driven Revision of Conditional Norms in Multi-Agent Systems (Extended Abstract)

1 Introduction

Multi-agent systems (MASs) comprise autonomous agents that interact in a shared environment [Wooldridge, 2009]. For example, a smart traffic system is a MAS that includes autonomous agents like cars, pedestrians, smart traffic lights, etc. To achieve the system-level objectives of a MAS, the behavior of the autonomous agents should be controlled and coordinated [Bulling and Dastani, 2016]. Norms and their enforcement are one way to do this without limiting the autonomy of the agents in a MAS [Chopra et al., 2018; Tinnemeier et al., 2009; Testerink et al., 2016]. Similar to our society, norms can be viewed as standards of behavior specifying that certain states or sequences of actions in a MAS should occur (obligations) or should not occur (prohibitions)

∗ Full paper in Journal of Artificial Intelligence Research, Volume 75, 2022 [Dell'Anna et al., 2022a]

in order for the objectives of the MAS to be achieved [Boella and van der Torre, 2004].

For many applications, it is assumed that the behavior of the agents and the norms enforced in the MAS will guarantee the achievement of the system's objectives [Dastani et al., 2009]. This is possible, for example, when the MAS designer and agent designers are the same people, or when the agent's behavior is enforced via the regimentation of norms, so that the agents cannot deviate from the intended behavior.

Regimentation, however, is particularly difficult in open MASs [Dastani et al., 2004; Artikis and Pitt, 2001], where agents can freely enter or leave the system, and their internal architecture is not known to the MAS designer. Furthermore, without awareness of how the agents internally behave, the MAS designer cannot fully predict how the agents will react to the norms, making it impossible, or computationally infeasible, to design norms that guarantee the satisfaction of the system's objectives in every possible combination of the agents' behaviors. Also, the MAS objectives may change over time, and the designed norms may become outdated and ineffective for the new objectives [Bicchieri, 2005].

To cope with these issues, norms need to be continuously evaluated, and possibly revised when they become inadequate for achieving the MAS objectives [Knobbout et al., 2014; Knobbout et al., 2016; Dell'Anna et al., 2020].

In this paper, we make the following contributions. We introduce DDNR, a novel Data-Driven Norm Revision approach. DDNR revises norms from data describing the behavior of the agents in a MAS at run-time, and does not assume control over agents' design nor requires regimentation. We evaluate the complexity of DDNR (see full paper [Dell'Anna et al., 2022a]). We apply and experimentally evaluate a Java implementation of DDNR, available online [Dell'Anna et al., 2022b], on an agent-based traffic simulation where norms regulate the behavior (maximum speed and minimum safety distance) of vehicles on a highway.

2 NormRevision in Normative MASs

As an illustrative example, we use the highway section shown in Figure 1.

We focus on conditional prohibitions with deadlines, which express behavioral properties [Tinnemeier et al., 2009]. A conditional prohibition (over a finite propositional language L) is a tuple (ϕC, ϕP , ϕD), where ϕC, ϕP and ϕD are propositional formulas, expressed in Disjunctive Normal Form (DNF), over L. In this expression, ϕC is the (detachment) condition of the norm, ϕD is the deadline, and ϕP is a target state that is prohibited to occur after a state where the condition of the norm ϕC holds, and before a state where the deadline ϕD holds (the norm "expires").

Example. The norm "if a car enters the 2nd km of the highway, it is prohibited from driving faster than 70 km/h until it reaches the 7th km of the highway" can be represented as a conditional prohibition (km2 ∧ car, sp70, km7).

In our framework, a Monitoring and Norm Enforcement component monitors (e.g., via runtime monitoring [Alechina et al., 2014]) agent behavior, and stores the collected data in a database in the form of a data set of finite traces. A trace in the running example represents the car journey through the highway, and it is generated by the actions of a vehicle. An example of a trace γ composed of 10 states is the following, where kmi indicates that the vehicle reached the ith km of the highway, spx indicates that the vehicle's speed is higher than a certain speed x in km/h, and car indicates the vehicle's type.

The collected traces are then evaluated by the MAS objectives evaluator component, which labels each trace as either positive or negative with respect to the MAS objectives. The MAS objectives evaluator is assumed to be an external component, either human or automated, beyond the scope of this paper.

This paper focuses on the Data-Driven Norm Revision module (the green box in Figure 1), which revises the cur-

Algorithm 1 DDNR

• 1: Input: data set Γ; set of norms N; list T of |N| types of revisions, one for each norm in N; list V of |N| triples ⟨V C n , V P n , V D n ⟩ of propositional variables, one for each norm n in N; number of samples k
• 2: Output: ordered list of revised norms selected
• 3: ▷ Synthesis step 4: R(N) ← [ ] ▷ empty list
• 5: for all norm n ∈ N do 6: R(N).APPEND(SYNTHESIS(Γ, n, Tn, V C n , V P n , V D n )) ▷ Selection step 7: candidates ← RANDOMSAMPLE(R(N), k) 8: return argmax cand ∈ candidates ∪ {N} ML-ACC(cand, Γ)

rently enforced norms so to ensure that (i) traces (behaviors) that are labeled as negative by the MAS objectives evaluator are prohibited by the revised norms, and (ii) traces that are labeled as positive by the MAS objectives evaluator are not prohibited by the revised norms. The Data-Driven Norm Revision module is agnostic to the MAS objectives, for it only relies on labeled traces provided by the MAS objectives evaluator, which are considered as ground truth. This guarantees that the proposed Data-Driven Norm Revision module is data driven and supports those cases where the MAS objectives do not correspond directly to properties expressible in the language of the norms (e.g., we can express norms concerning the speed of the vehicles, while the objectives may concern CO2 emissions) or where the causal relationship between norms and objective is not known or unavailable.

3 DDNR: Data-Driven NormRevision

Given a set of norms N and a data set Γ of traces labeled w.r.t. the MAS objectives, DDNR (summarized in Algorithm 1) synthesises revised norms that are better aligned with the MAS objectives with respect to Γ.

DDNR consists of two steps: the synthesis step and the selection step. These are briefly described below for the case of revision of one norm. An in-depth technical description of DDNR, also for multiple norms, can be found in the full version of the paper [Dell'Anna et al., 2022a].

3.1 Revising the Norm: the Synthesis Step

Consider a norm n = (ϕC, ϕP , ϕD) to be revised. We distinguish three types of revisions of a norm: alteration, weakening, and strengthening.

Alteration - Prohibiting Different Behaviors

An alteration of a norm n is a new norm n′ that prohibits a different set of behaviors than n. An alteration of n can be realized by making at least one of the components of n, that is the condition, the target state or the deadline, either more or less specific. For example, an alteration of n is a new norm n′ = (ϕ′C , ϕ′P , ϕ′D ) such that ϕ′C is less specific than ϕC, while ϕ′P and ϕ′D are more specific than ϕP and ϕD, respectively.

Weakening - Prohibiting Fewer Behaviors

A weakening of a norm n is a special case of alteration of n: the new norm n′ prohibits a subset of the behaviors prohibited by n. To weaken a norm, it is necessary to do at least one of the following operations, each causing n′ to prohibit fewer behaviors: (i) making the condition more specific, so that the norm is detached in fewer states; (ii) making the target state more specific, so that fewer target states are prohibited; or (iii) making the deadline less specific, so that the norm "expires" in more states.

Strengthening - Prohibiting More Behaviors

A strengthening of a norm n is another special case of alteration of n, leading to a n′ that prohibits a superset of the behaviors prohibited by n. To strengthen a norm, it is necessary to do at least one of the following operations, each causing n′ to prohibit more behaviors: (i) making the condition less specific, so that the norm is detached in more states; (ii) making the target state less specific, so that more target states are prohibited; or (iii) making the deadline more specific, so that the norm "expires" in fewer states.

Technical details and algorithms for the synthesis of these three types of revisions can be found in the full version of the paper [Dell'Anna et al., 2022a]. Figure 2 provides examples of the types of norms that DDNR allows to synthesise from a data set of traces Γ.

3.2 Choosing the NewNorm: the Selection Step

The selection step chooses a new norm from the set R(n) of candidate revisions of n synthesised during the synthesis step.

The relationship between the classification of traces according to a norm (i.e., whether the trace is classified as normcompliant or norm-violating) and the correct classification of the traces according to the MAS objectives labeling can be described via a confusion matrix. Each cell (i, j) in the matrix contains the number of traces in the data set Γ that are classified as i by the MAS objectives evaluator and as j by the norm.

By analysing a confusion matrix that characterizes the traces in a data set w.r.t. the classification provided by a norm, we can determine the number of classification errors of a norm, the type of errors (i.e., whether negative traces are considered compliant more often than positive traces are considered violating), and we can determine whether a norm is better (aligned with the MAS objectives) than another.

We characterize the concept of alignment of a norm with the MAS objectives using the accuracy metric, defined as acc(n, Γ) = TP+TN |Γ| , with TP and TN being the number of true positives and true negatives obtained with a norm n on the data set of traces Γ.

Therefore, the selection step aims at choosing the revision of n with highest accuracy, i.e., given R(n), we choose, as a revision of n, the norm n∗ = argmaxn′∈R(n) acc(n′ , Γ).

4 Empirical Evaluation

We make use of a traffic simulation of the highway scenario described in Section 2 to generate a data set of traces describing the behavior of agents in a MAS. We implement the scenario with the SUMO traffic simulator [Krajzewicz et al., 2012], considering two types of vehicles (cars and trucks, each with their own properties such as maximum speed, acceleration, etc.). We use a population of agents randomly and uniformly distributed among cars and trucks. 75% of the agents are always compliant with the enforced norms, while the remaining 25% will ignore them (can afford the sanction resulting from violation) and focus on maximizing speed.

We execute 100 independent traffic simulations. In each simulation i, we enforce a norm ni randomly generated. We run every simulation i until 1,500 vehicles drive through the highway section under the enforcement of ni. Since the behavior of each vehicle corresponds to an execution trace (e.g., trace in Eq. 1), each simulation generates 1,500 traces.

(b)

Each trace is labeled by the MAS objectives evaluator as positive if the maximum emission of the vehicle from the beginning to the end of the highway section is below a threshold tco2 = 100 g/s and the travel time is below a threshold ttt = 450s (the time it takes to drive for 10 km at 80 km/h), and negative otherwise. Given the resulting labeled data set Γi, we execute DDNR for the three types of revisions. For each of the 100 norms initially enforced, we obtain 100 weakened norms, 100 strengthened norms and 100 altered norms. We analyze the accuracy of these revised norms in comparison with the 100 original norms.

Figure 3 compares the accuracy of the original norms with that of the revised norms, and shows the accuracy change when performing weakening, strengthening or alteration. All operations led to norms with significantly higher accuracy than the original norms. The improvement with weakening has a smaller magnitude, with a negligible effect size dCohen = 0.087, because in the data set obtained from simulation the number of negative traces was low (i.e., the original norms were already too weak and did not need further weakening). In the case of strengthening, instead, the average improvement of accuracy is around 20%, with a large effect size dCohen = 1.115. Finally, with alteration, the average accuracy improves even more, with a large improvement of around 24% (dCohen = 1.275). Note that half of the new norms have an accuracy higher than 76%, and 25% of the norms have an accuracy higher than 89%.

In the full version of this paper [Dell'Anna et al., 2022a], we report on an in-depth analysis of these and additional experimental results. Experiments reported in the full paper also include results for the revision of multiple norms and a study on how well the revised norms generalize to previously unseen traces. Overall, results show that the revised norms are significantly more accurate (aligned with the MAS objectives) than the original norms, exhibiting an average improvement of accuracy on the given data set of traces of about 30% and an average improvement of accuracy of about 13% on unseen traces.

5 Conclusions and FutureWork

We investigated the problem of norm revision in contexts where the internals of the agents in a MAS are unknown and where norms are expressed in a different language from that of the MAS objectives that they intend to bring about. We presented results regarding the automated synthesis and revision of conditional norms (prohibitions) with deadlines w.r.t. a set of observed traces representing the behavior of the agents in the MAS. The traces are partitioned into positive and negative ones, depending on whether each helps or hurts MAS objectives. Besides a boolean evaluation, the revision mechanism possesses no information about the relationship between a trace and the objectives. We proposed DDNR (Data-Driven Norm Revision): a practical heuristic approach to obtain approximate revisions of the conditional norms. We applied DDNR to a traffic simulation. Results show that the revised norms are significantly more accurate (aligned with the MAS objectives) than the original norms. In future work, we intend to embed DDNR in a runtime supervision framework presented in earlier work [Dell'Anna et al., 2019; Dell'Anna et al., 2020] that continuously monitors the system's execution and, based on probabilistic strategies, suggests how to revise the norms (i.e., whether to alter, weaken or strengthen them) to continuously guarantee the achievement of the MAS objectives. Considering the relative importance of different states and propositions in revising norms is another future direction of our work. Similarly, we also intend to extend the proposal to support multiple system objectives, and to more fine-grained evaluations (as opposed to the considered boolean evaluation) of the traces with respect to the objectives.