The adoption of Multi-Agent Systems (MAS) is permeating Internet of Things (IoT) and Cyber-Physical Systems (CPS). Timing reliability of MAS is a daring challenge. The study of local task execution and negotiation of workloads are catalyzing considerable interest. By adopting techniques typical of Real-Times Systems (RTS), MAS's ability to comply with strict timing constraints has been proven. However, a complete formalization is still missing, and some of the existing mathematical models introduce considerable pessimism in the performance analysis. Therefore, the need for tools supporting the study of the behavior of agent-based systems is rising. Particularly, the capability of systematic assessment and comparison of their performance. This paper presents a system to generate task-sets and operating scenarios, to support the study of timing reliability, behavior, and performance of MAS. The parameters required for such a generation are characterized by randomly extracted values (e.g., the number of agents, single agent utilization factors, and single task utilization factor). For each parameter, it is possible to select a given statistical distribution to be applied to user-defined ranges. In particular, logic, constraints, and dependencies characterizing the generation algorithm are detailed and framed in a functional work-flow. Moreover, such a system integrates a MAS simulator powered by both general-purpose and real-time algorithms, named MAXIMGPRT. Hence, the presented tool is also able to show the logs of the tested scenarios equipped with graphs to enable the performance analysis.
However, their employment in safety-critical scenarios has been recently questioned [
This class of systems is characterized by a multitude of elements with factors operating simultaneously. To study their primitive mechanisms, the compliance with strict timing constraints, the load balancing, and the overall performance, they have to be individually and collectively studied.
Investigating the timing-reliability, Calvaresi et al. studied the behavior and role of
the local-scheduler [
Currently, the most used agent-based framework and systems take the negotiation,
allocation, and execution of tasks/services for granted [
However, by investigating the state of the art, the need for a standardized and semiautomatic manner to generate task-sets and MAS scenarios is still clearly unmet. Therefore, in the context of MAS, our aim is to support studies of performances analysis, risk and failure detection 3, in both General-Purpose (GP) and Real-Time (RT) scenarios.
This paper presents a generator of task-sets and scenarios that we have recently developed. Although it has been conceived to cope with MAS, it can be employed to study any type of system requiring the generation of task-sets according to a given set of parameters and bounds. The task-sets are composed of tasks, which are randomly generated and subject to given statistical distributions applied to user-defined bounds. The scenarios are characterized by a set of parameters representing the operating conditions and the selected algorithms (see Table 2).
The paper is organized as follows: Section 2 presents and elaborates the state of the art, Section 3 describes the task-set and scenario generator, Section 4 details the steps and a case study used as an example. Section 5 discusses about the design approach and assesses the accuracy of the generator. Finally, Section 6 concludes the paper. 3 with particular emphasis for safety-critical systems
On one hand, by investigating the state of the art in the domain of multi-agent
systems, the notion of scheduling applies mainly to mechanisms of task/resources
allocation among the agents rather than concerning the arrangement and execution of the local
tasks/behaviors within a given agent [
Such a tool is composed of three main modules operating sequentially: (i) the generator produces a synthetic task-set composed of periodic tasks with implicit deadlines (i.e. Deadline (D) = Period (T )). Such tasks are generated according to the following parameters: range of task-set utilization; step value between two utilization; number of task-sets per utilization; number of tasks per task-set; lower and upper bound of the period; level of granularity of the period; seed value for pseudo-random generators.
Firstly, the generator assigns a utilization U i to each task according to the constraint that Pn
i=0 U i = Ut, where Ut is the total utilization of the task-set.
Then, the period of each task is generated within the given bounds, and the computation time is calculated according to Equation 2. (ii) Secondly, the Timing Analysis on Code-Level Benchmark suite (TACLeBench) evaluates the Worst Case Execution Time (WCET) for each generated task. (iii) Finally, the task-set is implemented as a collection of C++ functions and a makefile.
Compiling that source code produces a set of executables which can be run on a target hardware.
Emerson et al. [12] outlined the Randfixedsum algorithm to study the
underlying mathematical problem of the efficient generation of uniformly distributed random
points whose elements sum-up to a predefined value (i.e., 1, indicating a feasible task
set). In the uni-processor case, the UUniFast algorithm created by Bini and Buttazzo [
However, the requirements of agent-based systems, particularly the ones of the simulator MAXIM-GPRT, go beyond what is currently available. Therefore, the next section presents the tool that we have developed to cope with the still unmet requirements. 3
To support a comprehensive and meaningful analysis of the indicators provided by MAXIM-GPRT (see Table 1), there is the need for coordinating many parameters and inter-dependencies. This section presents elements, constraints, and logic standing behind the presented tool. 3.1
The parameters characterizing the generated task-sets and setups are listed in Table 2.
The features P4 and P5 are expressed in the form of a percentage. Such a value indicates the number of services and needs requiring generation with respect to the number of tasks composing the task-set. Moreover, it is possible to define a range indicating the time of release of the needs4. Similarly, the generation of the parameters P7, P8, and P9 4 It triggers the needs release during the simulation, abstracting the “will” of the agent . depends on the ranges chosen by the user and related statistical distributions (e.g., uniform and Gaussian). Figure 1 shows that P7 and P8 will be generated in the [0:2 0:8] range, and that P9 will be generated in the [2 4] range, according to the selected distributions. Hence, it is possible to select the statistical distribution singularly.
The number of agent composing the simulated community (P1) indicates the number of task-sets to be generated. The user can define it assigning an integer value (x 1) to such a variable;
A task is characterized by: id, executor, demander, computation time 5, residual computation time, arrival time5, relative deadline, period5, number of executions, first activation time, last activation time, public flag, and server id. The task-set is generated in CSV and XML (see listing 1) formats.
The set of tasks that an agent is capable of executing represents its knowledge (P2). Elements of such tasks can be labeled as public, which are services (P4) eligible to be demanded for by other agents6. The needs (P5) are tasks that an agent have to execute at a certain point in time. Such tasks might be part of its knowledge (P2) and/or marked public by other agents. For each agent, the running tasks (among those contained in their P1) compose the task-set (P3).
Figure 2 proposes a graphical representation of P2, P3, P4, and P5. In particular, such sets are generated as follows: (i) generation of P3, (ii) possibly marking a given percentage of the tasks in P3 public and generating new services, and (iii) When the 5 Values computed according to a uniform or Gaussian probability distribution. 6 The execution of such tasks is subject to negotiation mechanisms.
P4 of all the agents have been generated, a percentage of needs with the related release time 7 is associated to each agent.
The task (P6) models that can be generated are: periodic, periodic in an interval,
and aperiodic [
The user can define a lower bound (ula) and an upper bound (uah), such that P7 can assume a real value (0 < ula x uah 1). Thus, all the generated task-sets are schedulable under the Earliest Deadline First (EDF) conditions (Processor utilization Factor U 1)8.
Moreover, the user can define two ranges in which the following features of the generated tasks are extracted: – a lower bound (ul ) and an upper bound (uh), such that the single task-utilization
Ui is a real number x j (0 < ul x uh 1) (P8), – a lower bound (cl ) and an upper bound (ch), such that the computational time Ci is an integer number x j (0 < cl x ch) (P9).
Thus, according to the generated Ui and Ci, the period of the task Ti is computed as shown in Equation (2). Finally, the generation of the tasks composing a given task-set stops when the sum of their Ui matches (P7).
Concerning the negotiation protocols (P10), the demonstrated tool proposes the
selection of a generic implementation of the Contract Net Protocol and Reservation-Based
Negotiation Protocol (RBN) [
U = n X Ci i=1 Ti Ti =
Ci
Ui
(1)
(2)
First Served (FCFS), Round Robin (RR), EDF, and Constant Bandwidth Server (CBS)
selection is proposed [
Heuristics can be selected for key activities such as (i) selecting which agents require a given service, (ii) how to elaborate a proposal for a given request, and (iii) how to select the agent to award for the execution of the negotiated service. Those heuristics are: – (H1) select first agent in the list, – (H2) select a random agent, – (H3) select a random subset of agents, – (H4) select the best offer according to a cost function.
P1 and P10 are the only parameters valid for the entire community. The remaining parameters can be set differently for each agent. 1 <t a s k P a r a m e t e r s > 2 <i d >1</ i d > 3 <a g e n t E x e c u t e r >0</ a g e n t E x e c u t e r > 4 <a g e n t D e m a n d e r >0</ a g e n t D e m a n d e r > 5 <c o m p u t a t i o n T i m e u n i t =” s ”>3</ c o m p u t a t i o n T i m e > 6 <r e s i d u a l C o m p u t a t i o n T i m e u n i t =” s ”>3</ r e s i d u a l C o m p u t a t i o n T i m e > 7 <a r r i v a l T i m e u n i t =” s ”>0</ a r r i v a l T i m e > 8 < r e l a t i v e D e a d l i n e u n i t =” s ”>7</ r e l a t i v e D e a d l i n e > 9 <p e r i o d u n i t =” s ”>7</ p e r i o d > 10 <n e x e c > 1</n e x e c > 11 < f i r s t A c t i v a t i o n T i m e > 1</ f i r s t A c t i v a t i o n T i m e > 12 < l a s t A c t i v a t i o n T i m e u n i t =” s ”> 1</ l a s t A c t i v a t i o n T i m e > 13 <i s P u b l i c >t r u e </ i s P u b l i c > 14 <s e r v e r >0</ s e r v e r > 15 </ t a s k P a r a m e t e r s >
3.2
The operations and functionalities required to generate task-sets and scenarios according to the input set by the user are reported in the form of pseudocode by the Listing 2.
Once the initial ranges for all the parameters have been set, the generation can be triggered. The tool starts iterating on the agents number to generate the related task-sets. For each of them, it generates the agent utilization (P7), and it iterates generating tasks to reach it. By defining Utaemp equal to P7 minus the sum of the generated P8 for that task-set, the stop conditions are: (i) if (Ul Utaemp < Uh ), a task is generated with u equal to the remaining utilization to match P7;
P1 Agent
P3 P10
P4 P11
P6
P8
P9 P5 P12
P2
P7 (ii) if (Utaemp < Ul ), the task generation for that task-set is stopped (no task respecting the preset range and distribution can be generated).
According to Buttazzo [
Table 3 proposes the setup characterizing the case study used to show the main functionality of the presented tool. Concerning the generation of the parameters within the ranges (Ula Uha), (Ul Uh ), and (Cl Cl ), the current case study employs a uniform distribution. This case study focuses on the generation of task-sets. Therefore, the generation of needs and services has been neglected9. Table 4 presents the tasksets generated according to Table 3, detailing the values of the main variables at each step. The objective is to show the behavior of the algorithm shown in Listing 2, thus facilitating its understanding. 9 setting to 0 the related parameters neither needs or services have been generated.
To realize this generator tool, we followed a top-down approach. Hence, as shown in Listing 2, the sequence to break down the problem starts by (i) generating the parameters per agent, then (ii) generating the parameters per tasks-set (for every given agent), and finally (iii) generating parameters for any given task.
Concerning the accuracy of the generated task-sets, Figure 4 shows how close generated task-sets meet the requirements expressed in input. In particular, Figure 4 plots the agents utilization values obtained by generating a task-set with 1000 agents on three different ranges of U (0:01 0:05; 0:1 0:2; 0:2 0:3). The targeted U a is defined in the range Ula = 0:7 and Uha = 0:9. Both U a and U employ a Gaussian distribution.
Target Generated
Target
Generated 0:05 Target
Generated 0.4 0.5 0.6 0.7 0.8 0.9 1.0
Agent utilization 0.4 0.5 0.6 0.7 0.8 0.9 1.0
Agent utilization 0.4 0.5 0.6 0.7 0.8 0.9 1.0
Agent utilization
Thus, it is possible to notice that the accuracy is given by Ul . Its impact, in the form of a shift between the centers of the two bells (targeted and generated), becomes more relevant when Ul rises.
The principal cause generating this behavior is that the last task is generated only if the remaining U a is greater than Ul (see line 16 in Listing 2). This results in an inevitable shift downwards of the distribution.
To reduce this phenomena, we allowed the task utilization range to expand. Mean and distribution are initially kept centered and then shifted. This is possible by overriding the final criteria to generate the last task employed in the algorithm presented above. The precision (pr) is now defined as pr = Ul =2. Consecutively, the new U a target becomes U a + pr. Such a tweak, helps to recenter the distribution, setting pr as the new precision. Nevertheless, borderline cases (e.g., Uh = 1) still need attention. A possible solution would be to recompute those task-sets that exceeded such a bound.
Figure 5 is obtained by repeating the tests performed to generate Figure 4 and applying the updated stop condition. 0.4 0.5 0.6 0.7 0.8 0.9 1.0
Agent utilization 0.4 0.5 0.6 0.7 0.8 0.9 1.0
Agent utilization 0:05 Target
Generated 0.4 0.5 0.6 0.7 0.8 0.9 1.0
Agent utilization
Although minimally observable, the utilization of the generated task-sets for 0:1 Ul < 0:2 (Figure 5b) starts to shift towards a bi-modal distribution. In the case of 0:2 Ul < 0:3 (Figure 5c), such a utilization assumes a pronounced bi-modal Gaussian distribution.
Such behavior is due to the employement of a Gaussian distribution which, with the above mentioned bound, generates in average U 0:25. By summing up three tasks we get U a 0:75. Therefore, recalling that the stop condition is U a P U < Ul , if U a > 0:8 for Ul = 0:2, the task generation stops. Thus, explaining the distributiongap.
Observing the inputs listed in Table 2 and related constraints highlights how the presented tool copes with an over-determined system. Let us consider, for example, the constraints (statistical distributions) applied to U a and U . Being related to each other as shown in Equation 1, results in the behavior shown in Figure 5c as a direct consequence.
Over-determined systems have been studied for decades. A possible solution simplifying the approach can be used for constrained optimization techniques (e.g., by employing linear programming solvers). Adopting a bottom-up approach results in the sequence (i) generating the parameters following their distributions, (ii) aggregating such parameters to compose tasks, and (iii) distributing tasks among the agents. Such a new approach might optimize the overall system while respecting all the preset constraints. This new approach is under evaluation to be included in the future version of the presented tool.
With respect to the traditional command-line interface, the presented tool also provides
a web interface. Such a version is still an ongoing work. However, at the current status,
it provides a few additional features such as the enabling of the visualization of graphs
supporting the analysis of the results obtained by the generated task-sets and scenarios
simulated in MAXIM-GPRT [
Concerning the indicators provided by MAXIM-GPRT (see Table 1), it is possible to visualize: (i) which tasks missed their deadlines within an agent in a given time window (see
Figure 6a) (i) the trend of the deadline-missed of all the tested agents in a given time window (see Figure 6b). 200 400 tim60e0(s) 800 1000
1200 (b) Deadline misses for 10 agents time window (a) Deadline misses for 10 agents, time window [0-1200s]. [0-200s]. Fostering the study of timing-reliability and load balancing in MAS, this work presented a tool to generate task-sets and scenarios for testing purposes. The current implementation provides the output in the format supported by the MAXIM-GPRT, but can be easily extended to handle different output formats.
Considering that the performances of general-purpose scheduling algorithms are strongly dependent from the features of the scheduled task-set, it is impossible to provide any off/on-line timing guarantee. Such a study faces more challenges if it refers to communities of agents scheduling and negotiating tasks executions in a broad range of scenarios. Therefore, the employment of a task-set and scenario generator is strategical to many unpredictable scenarios with the support of a simulator.
In light of the data produced by the presented generator, it has proven to be a strategical tool fulfilling the need for a generator of task-sets and scenarios of Multi-Agent Systems.
As future work, we aim at: (i) improving the functionalities related to the performance analysis, (ii) enabling possible benchmarks by indexing and saving the generated scenarios, and (iii) providing customizable scenarios directly from the industrial domain. 11. De Bock, Y., Altmeyer, S., Huybrechts, T., Broeckhove, J., Hellinckx, P.: Task-set generator for schedulability analysis using the taclebench benchmark suite. SIGBED Rev. 15(1), 22–28 (Mar 2018), http://doi.acm.org/10.1145/3199610.3199613 12. Emberson, P., Stafford, R., Davis, R.I.: Techniques for the synthesis of multiprocessor tasksets. In: proceedings 1st International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS 2010). pp. 6–11 (2010) 13. Horn, W.: Some simple scheduling algorithms. Naval Research Logistics (NRL) 21(1), 177– 185 (1974) 14. Hsieh, F.: Modeling and control of holonic manufacturing systems based on extended contract net protocol. In: American Control Conference, 2002. Proceedings of the 2002. vol. 6, pp. 5037–5042. IEEE (2002) 15. McArthur, S.D.J., Davidson, E.M., Catterson, V.M., Dimeas, A.L., Hatziargyriou, N.D., Ponci, F., Funabashi, T.: Multi-agent systems for power engineering applications 2014;part i: Concepts, approaches, and technical challenges. IEEE Transactions on Power Systems 22(4), 1743–1752 (Nov 2007) 16. Stafford, R.: Random vectors with fixed sum. See http://www. mathworks. com/matlabcentral/fileexchange/9700 (2006) 17. Wu, J., Huang, Y.C.: Mcrtsim: A simulation tool for multi-core real-time systems. In: 2017 International Conference on Applied System Innovation (ICASI). pp. 461–464 (May 2017)