Run-time Norms Synthesis in Multi-Objective Multi-Agent Systems

IRON machine is composed of a central unit that is responsible for detection of conflicts, synthesises of new norms to avoid conflicts, evaluation of the synthesised norms, refinement of norms, and announcement of the norm set to the agents. To simplify the illustration of the responsibilities of IRON, we will use a traffic junction example with two orthogonal roads scenario. The vehicles represent the agents, each occupying a single cell and moving in a specific direction per time-step.

• •

  In conflicts detection, conflicts are detected when a collision occurs between two or more vehicles. The occurrence of a collision will trigger IRON to synthesise new norm to avoid future collisions of similar cases. As for norms synthesising, norms are created based on a case-based reasoning algorithm. In the algorithm, the conflicting situation at time $t$ is compared to the conflicting vehicles’ context at time $t-1$. Then a norm is created using the conflicting views as a precondition for applying the norm and prohibiting the ‘Go’ action in this context. The synthesised norm is then added to a norm set and communicated to the agents(vehicles) of the system. For example, in Fig. 2, if vehicle $A$ and $B$ collided at the intersection (grey cell) then the context and action of $A$ or $B$ is chosen randomly by the system to create a new norm. If $A$ is chosen the new norm will be $n=if(left(<),front(-),right(<))->proh(^{\prime}Go^{\prime})$. The left() attribute in the precondition of the norm stores the direction of the left neighbour vehicle of vehicle $A$. While the right() attribute stores the direction of the right vehicle to vehicle $A$, which is in this case vehicle $B$.

• •

  Norms Evaluation is carried out by measuring necessity and effectiveness of a norm and comparing it to a threshold. Necessity is measured according to the ratio of harmful violated norms, which are norms that resulted in conflicts when violated, compared to the total number of violated norms. The norm’s necessity reward $NNR$ is calculated by:

  $$NNR=\frac{m_{V_{C}}(n)\times w_{V_{C}}}{m_{V_{C}}(n)\times w_{V_{C}}+m_{V_{\bar{C}}}(n)\times w_{V_{\bar{C}}}}$$

  (1)

  
  

  $m_{V_{C}}(n)$: Number of violations which led to conflicts

  $w_{V_{C}}$: Weight that measure the importance of harmful applications

  $m_{V_{\bar{C}}}(n)$: Number of violations which did not led to conflicts

  $w_{V_{\bar{C}}}$: Weight that measure the importance of harmless applications
  

  The effectiveness of norms is measured based on the extent to which the norm is successful (i.e. which resulted in the minimum number of conflicts). The norm’s effectiveness reward $NER$ is calculated by:

  $$NER=\frac{m_{A_{C}}(n)\times w_{A_{C}}}{m_{A_{C}}(n)\times w_{A_{C}}+m_{A_{\bar{C}}}(n)\times w_{A_{\bar{C}}}}$$

  (2)

  
  

  $m_{A_{C}}(n)$: Number of applied norms which led to conflicts

  $w_{A_{C}}$: Weight that measure the importance of unsuccessful applications

  $m_{A_{\bar{C}}}(n)$: Number of applied norms which did not led to conflicts

  $w_{A_{\bar{C}}}$: Weight that measure the importance of successful applications
  

• •

  Norms refinement is carried out by generalisation or specialisation of norms. Norms are mapped in a connected graph that expresses the relationship between the norms. The graph shows the child and parent norms that are linked. Norms generalisation is applied when two or more norms have acceptable necessity and effectiveness results compared to the threshold for time-interval $T$. Specialisation or deactivation of norms is conducted when the effectiveness and necessity of the norm or its children have been below threshold for time-interval $T$.

• •

  Norms communication is the final step, where the norms are communicated to the agents.

The main flow of activities that are carried out in the traffic scenario with the traffic junctions of two orthogonal roads (similar to Fig. 2), is as follows. Agent movements take place per time-step, however, prior to this movement, the norms set is checked for norms with matching precondition. If a norm was found, it will be applied directly, assuming there are no bad-behaving agents who violate the norms. If no norm was found the movement is undertaken. When a new collision is detected, a random agent/vehicle is chosen and its context (local view) is added as a precondition of a new norm that prohibits the ‘GO’ action. Then this norm will be added to the norms set (initially empty). In addition, norms evaluation and refinement are carried out per time-step, in which all the views at time-step $t$ are revised to determine the set of applicable norms for each of the views. Afterwards, the applicable norms are divided into four subsequent sets: (i) applied norms that led to conflicts (ii) applied norms that did not lead to conflicts (iii) violated norms that led to conflicts (iv) violated norms that did not lead to conflicts. Then set (i) and (ii) are used to calculate the effectiveness of each of the norms, while set (iii) and set (iv) represent the main inputs for the necessity calculation. Finally, norms refinement is conducted.

At each time-step $t$ as agents take actions, a set of monitors (e.g. traffic cameras) $M=\{m_{1},m_{2},...,m_{n}\}$ monitor these actions to detect any conflicts. A conflict $c$ is detected when more than one agent actions contradict at the same view $v_{i}$, where $v_{i}\in V$ . For example, in a traffic system, if vehicles standing before a junction in opposite directions decided to move (do a ’Go action’) towards the same position, a collision will occur and so a conflict will arise. To detect conflicts, views $V$ are sent as a parameter to the $ConflictDection$ function (see Algorithm 1, line 6). A conflict object definition is composed of responsible agents $Ag^{r}\subseteq Ag$ , context of these agents $ag^{r}(ac)$ (which is the local views of each of these agents), and the views transition of a state $s$ between time-step $t$ and $t-1$, $(v^{i}_{s_{t-1}},v^{i}_{s_{t}})$.

Case-based reasoning technique is used for norm synthesising. When a new conflict arises, a new case is created and then compared to similar cases and the best solution is chosen accordingly. In case that no similar solution is found a new random solution is created for this case and added to the set of cases. In this manner, after conflicts are detected, UNS carries out the norms synthesising steps for each of these conflicts (see Algorithm 1, line 7 to line 16). All the agents responsible for the conflict are retrieved in $Ag^{r}$ (e.g. all the vehicles that collided in the same intersection are considered as responsible agents). For each of these agents’ context at $t-1$ if an applicable norm was not found (applicable norms are norms that have the same context as a pre-condition of the norm and the same agent action prohibited in the norm), a new norm creation process takes place (line 12). A new norm is composed of agents’ context $ag_{i}(c)$ and prohibited action $\theta ag_{i}(ac)$. Getting the context of the agent at the previous time-step as a precondition of a norm and prohibiting the action that resulted in a conflict avoids future conflicts that might rise in similar situations. After the norm is created it is added to the system’s norms set $\Omega$ (line 13).

UNS Supporting Fairness: In IRON norms synthesising was carried out by creating norms as a solution for only one randomly chosen agent from the agents involved in a conflict. However, in UNS we have proposed a norm synthesising process, which considers all the contexts of the agents involved in a conflict. For example, in IRON if two vehicles had a conflict in an intersection, the norm will be created based on prohibiting a Go action of only one of the two vehicles. Although this will decrease the probability of creating unmatchable norms, it will not ensure fairness as one side will always have priority over the other side.

The norm reasoning process must meet systems’ objectives and handle unmatchable norms simultaneously. This is reached through defining a utility function $U$ that is constructed based on the system’s objectives $O_{s}$ and is used during the norm selection.

Utility Function Construction: In this paper, the utility function is constructed by adding the objectives with a maximisation function and subtracting the objectives with a minimisation function. For example, if $S_{o}$ include two objectives $S_{o}=\{so_{1},so_{2}\}$ and $so_{1}$ is to minimise all vehicles’ average waiting time and $so_{2}$ is to minimise the average waiting time of emergency vehicles specifically, then the system utility function $U$ will be defined as:

Accumulated Utility Calculation: At each time-step before the agents start moving (taking actions) UNS determines the set of applicable norms $N_{a}$ in each view $V_{t}$ ( see Algorithm 1, line 19). If more than one norm is applicable for the same view $V_{t}$, then UNS carries out the steps in Algorithm 1 (from line 21 to line 26) to choose the norm with the highest utility and dismisses the rest of the norms. For example, if we have a traffic scenario as seen in Fig. 2, where vehicle $A$, $ag_{1}$, and vehicle $B$, $ag_{2}$, are willing to move to the same junction (coloured in grey) at time $t$, the stored view at time $t$ will be represent by ($V_{t}$). UNS will retrieve the set of applicable norms $A_{n}=\{n1,\acute{n}1\}$, where $n1$: is to stop if there is a vehicle on the right and $\acute{n}1$ is to stop if there is a vehicle on the left. $n1$ is suggested for vehicle $A$ and $\acute{n}1$ is suggested for vehicle $B$. If both vehicles apply the norms then none of them will move, which result in a deadlock state. So, a decision must be made to choose only one of the two unmatchable norms. Accordingly, an empty array of struct is initialised (in line 21). The struct is composed of $ag_{i}$ (which is the responsible agent), $n$ (which is the applicable norm for this agent $ag_{i}$ situation), and $U_{i}$ (which is the calculated utility gained by the system if this norm $n$ is applied). For each of the applicable norms in $N_{a}$, the utility function is calculated (line 23). However, in our utility calculation strategy, we calculate an accumulated utility function, which does not only consider the utility gained by the agent applying the norm, but also considers all the agents that are indirectly affected by the norm adoption decision. For example, in Fig. 2, if vehicle $A$ will be the agent that will apply the norm and will stop if there is a vehicle on the right, it will force vehicles $C,D,E$ and $F$ to stop as well. While if vehicle $B$ decides to apply the norm $\acute{n}1$ and to stop, vehicle $G$ will be forced to stop as well. Based on this justification, to ensure gaining the actual maximum utility, UNS aggregates the utility of all the agents that are affected directly and indirectly with the norms adoption or dismissal. Then, the norm that gives the maximum utility is applied (lines 25 and 26), and the rest of the norms are dismissed.

The norm evaluation and refinement processes are inherited from IRON (illustrated in section 2.1). These processes are used to evaluate norms at run-time using efficiency and necessity equations (equation 1 and 2). If a norm’s efficiency and necessity does not reach a certain threshold its refinement takes place and it is specialised or deactivated. Also, if a norm’s efficiency and necessity exceeds a specified threshold it can be generalised.

We simulate a traffic-based scenario, with a 19 x 19 grid as a road network with a junction of two orthogonal roads (see Fig. 2). Each road has two lanes; one for each direction. In Fig. 2, the cells coloured in grey show the four cells that represent the intersections. Vehicles are the agents and they have two main types: ordinary vehicles and high priority vehicles to represent heterogeneity. The ratio of generating priority vehicles to ordinary vehicles is 12:100 respectively. Also, as it is an open MAS, vehicles can enter and leave the road network freely. Vehicles move per time-step aiming to reach their final destination which was randomly generated by the simulator at the beginning of the trip of the vehicle. In each time-step, the system randomly chooses the number of new vehicles (between 2 to 8 vehicles) to be emitted to start their trip. The system aims at avoiding conflicts (i.e., the collisions between vehicles) through the synthesised norms. Norms are defined as a pair that includes the agent context and the prohibited action. The agent context is the local view of the vehicle describing the direction of vehicles on its left, front, and right, which we call neighbouring vehicles. For example, in Fig. 2 the vehicles in the local context of vehicle $F$ are vehicles $A$,$C$ and $D$. The action prohibited is a ‘Go action’ to avoid vehicle movement in future similar contexts. UNS synthesises norms and adds them to a norm set that is initially empty at the beginning of the simulation. When a stable normative system is reached the system converges. The system has two main objectives, minimising the average waiting time for all vehicles and minimising the total waiting time of priority vehicles. The utility function used in the norm reasoning is constructed based on the previous two objectives as follows:

$X_{wt}$:Total waiting time of ordinary vehicles

$Y_{wt}$:Total waiting time of priority vehicles

$X$:Number of ordinary vehicles

$Y$:Number of priority vehicles

To evaluate UNS’s performance, three main scenarios are tested with the settings illustrated in the previous sub-section with varying violation rate of norms, which represents the ratio of agents obeying the adoption of the norms. UNS will be compared to IRON machine (explained in section 2.1). The average waiting time for all vehicles and the total waiting time of priority vehicles are reported to show the performance of UNS and IRON. Moreover, the number of collisions is used to reflect the efficiency of the synthesised norms in avoiding conflicts. We present the moving average of the results at every 50 time-steps obtained from 10 runs of simulation as plotted in Fig. 3, 4, and 5.

Fig. 3(a) shows the average waiting time of all vehicles in UNS compared to the average waiting time of all vehicles in IRON. The average waiting time is decreased in UNS, particularly from time-step 322. Moreover, it can be noted that from time-step 322 almost the average waiting time in UNS is constant with an average value of 1.5 time-steps. As results show, UNS has minimised the average waiting time of the vehicles and so fulfilling the first objective of the system.

Fig. 3(b) shows the total time taken by priority vehicles per time-step in UNS compared to IRON. The average total waiting time of priority vehicles using UNS is 8.09 time-steps, while the average total waiting time of priority vehicles reached in IRON is 12 time-steps. Moreover, Fig. 3(a) and (b) do not only emphasise how UNS can coordinate objectives and norms, but the noticed stability and uniformity of the results show the reliability of UNS which is necessary in real-applications.

Fig. 5(a) presents the total number of collisions per time-step, which shows UNS is able to successfully synthesise norms at run-time to handle collisions. The results show UNS outperforms the synthesised norms set in IRON. Furthermore, observations showed that in a lot of time-steps UNS reached zero collisions, unlike IRON. The average number of collisions in UNS is 0.08 while the average number of collisions in IRON is 0.17. Also, comparing the total number of collisions, the total number of collisions in UNS is 51% lower than IRON, which shows the efficacy of the norm synthesis process.

Fig. 4(a) shows the average waiting time of all vehicles in UNS compared to IRON. The average waiting time in this scenario is increased to 2.45 time-steps compared to scenario A. However, UNS still outperforms IRON, in which its average waiting time per time-step decreased from 2.75 to 2.53 time-steps. This unexplained decrease in IRON shows the essence of the primary definition of the system objectives and its incorporation in the model. Moreover, the results show that even with a high violation rate the system objectives can be achieved using UNS.

Fig. 4(b) shows that UNS and IRON have quite similar range of total waiting time for priority vehicles. However, UNS outperforms IRON as the average of the total waiting time of priority vehicles is 8.92 time-steps using UNS and 9.24 time-step using IRON.

The results also show that although the violation rate has increased by 60% compared to scenario A, the average total waiting time of priority vehicles in UNS has only increased by 9.30%. Furthermore, the number of collisions occurred in this scenario using UNS is 4.66% fewer compared to IRON as seen in Fig. 5(b).

When using 0% violation rate with IRON simulation, IRON is not able to converge and continue the simulation. The reason behind this is that the system reaches a deadlock when all vehicles obey to the norms. Although, IRON strategy in synthesising norms relies on creating only one norm at a time, it might synthesises two unmatchable norms at different instances that when applied in the same conflict causes a deadlock. For example, if one norm is to stop if there is a vehicle on the right hand side and the second norm is to stop when there is a vehicle on the left, two lanes of the vehicles standing at the beginning of a junction will stop endlessly, when there is no violation. However, this situation does not arise in UNS because it handles unmatchable norms and if more than one norm is applicable, the utility for both norms is calculated and only one norm is applied (i.e. in the previous example, one vehicle will ’Stop’ and the other will ’Go’).

In all scenarios, UNS synthesises more norms than IRON. This is due to synthesising all the norms that would contribute in avoiding collision in a specific situation, supporting the idea of fairness. For example, in one of the runs IRON synthesised 15 norms, while UNS synthesised 17 norms. For example, UNS synthesises norm $n_{a}$, $n_{a}=(left(-),front(-),right(<),Proh(Go))$ and norm $n_{b}$, $n_{b}=(left(>),front(-),right(-),Proh(Go))$, both contributing in avoiding a collision. However, IRON only synthesises $n_{b}$ which will always give priority to vehicles on the right side of the intersection, and consequently cannot support fairness.