To evaluate the proposed approach, we have developed the multi-agent dynamic with Actalk, an object oriented concurrent programming language using the Smalltalk-80 en-vironment. In our experiment, we generated random meeting scheduling problems. The parameters used for a meeting problem are: n agents in the system, m meetings per agent, p participants in a meeting, D global calendar, cH number of initial hard constraints per agent, cS number of initial soft constraints per agent, d maximal possible time slots per event, wAki weights for the soft constraints, and WAXi
k weights of the meetings (the weight of each hard constraint is equal to 1).
In order to compare our approach with that reported by Tsuruta and Shintani in [101], we used the same parameters to run both algorithms on randomly generated samples. Note that the approach in [101] presents some restrictions towards; first the handle of the hard constraints (i.e., all the constraints could be relaxed by this approach) and second, the dis-crimination between meetings. This approach processes all the proposed meetings with the same importance independently of neither the proposer nor the attendants. However in the real world, all meetings are not equivalent. For this reason we have brought to our consid-eration the notion of meeting priority in our formalization by associating a weightWXAki to reflect its greatness. Our approach tries then, in its solving process, to first schedule the most important meeting maintained by each agent, unlike the approach in [101].
In this manner, we attempt to describe ideally the real world meeting scheduling problems.
Therefore two kinds of experimentation are given in this section. For the first kind, we assume that for each generated problem, we have only soft constraints. We carried out the two approaches on the same meeting instances with: n=15, m∈ {3, 5}, p = 10, cS ∈ {20, 40, 60, 80, 100}, and WAXik ∈[0..1], wAki ∈[0..1] were randomly chosen. (35 instances are generated for eachhm; cSi). The initial calendar D in each problem is equal to 100.
Table 7.1 shows the obtained mean results for the ratio of CPU time of the approach in [101] divided by the CPU time of MSS approach. In order to analyze these results, let us consider the case h3; 20i. Both approaches require almost the same CPU time. For this case, the number of possible time slots is not large leading to a few number of constraints, so the approach in [101] can rapidly find a solution for each meeting without relaxing many constraints, causing few iterations on the same meeting. However, when the amount of soft constraints increases, the needed time for the approach in [101] almost double. With regard to MSS, the increment in the CPU time is largely lower than Tsuruta et al. approach.
Obviously, the main explanation of this result is that For Tsuruta et al. approach (see chapter
4), the agents of the system (the group agent and the participant agents) should exchange the possible constraints according to the time slots of the current meeting to schedule. As the number of meeting constraints grows, and so does the probability of getting the same dates for the meetings. Therefore, the number of relaxed constraints by the approach in [101]
increases leading to additional iterations for the same meeting and hence an increase in the CPU time.
Table 7.1. Mean results of MSS approach and Tsuruta et al. approach in term of the CPU time for meeting problems without hard constraints. Ratio CPU= CPU time Tsuruta et al. approach / CPU time MSS.
h3; 20i h3; 40i h3; 60i h3; 80i h3; 100i CPU time Tsuruta et al. App. 604.57 1894.74 4479.89 8378.06 13781.29
CPU time MSS 452.49 520.43 617.63 724.40 863.09
Ratio CPU 1.34 3.64 7.25 11.57 15.97
h5; 20i h5; 40i h5; 60i h5; 80i h5; 100i CPU time Tsuruta et al. App. 2116.14 6471.34 14849.86 23997.46 38355.91
CPU time MSS 776.14 871.71 1020.00 1204.80 1466.51
Ratio CPU 2.73 7.42 14.56 19.92 26.15
In addition, The protocol proposed by Tsuruta et al. proceeds by setting up a threshold equal to zero for the constraints to relax and then through negotiations with personnel agents, the group agent tries to relax the constraints, i.e., by incrementing the threshold, until attain-ing a compromise among participants. while our approach relies on a selfish protocol. We try to find the solution that maximizes the Proposer’s preferences. Although in our approach;
we try to process the most important meetings at first.
The approach in [101] takes more time than our approach in most cases because both the number of constraints and the number of meetings grow. Furthermore, in MSS approach each agent tries to perform all its meetings asynchronously and in parallel while for the approach in [101], it is done in a synchronous sequential manner for the same group agent4. As for the second kind of experimentation, i.e., to appraise the greatness of the enforce-ment of local consistency in the solving meeting problems, we have chosen to measure the percentage of reduction made by the first step of our approach. For this purpose, examples including hard constraints were randomly generated with n=10, m=3, p∈ {3, 5, 7},cH ∈ {0, 10, 20, 30, 40, 50}and d∈ {100%, 83%, 66%, 50%, 33%, 16%}corresponding respectively to each cH. For each pair hp, cHi, we first generated 35 instances, then we measured the average of the achieved results.
4Meetings are proceeded in parallel within group agents.
0 500 1000 1500 2000 2500 3000
0 10 20 30 40 50
Hard Constraints Ch
CPU Time (in milliseconds)
Mss App. for p=3 Tsuruta et al. App. for p=3
Mss App. for p=5 Tsuruta et al. App. for p=5
Mss App. for p=7 Tsuruta et al. App. for p=7
Figure 7.2. MSS approach vs. Tsuruta et al. approach in term of mean of the required CPU time in milliseconds. (35 random samples generated for each pairhCh,pi).
0%
20%
40%
60%
80%
100%
120%
0 10 20 30 40 50
Hard Constraints Ch
Percentage of Scheduled Meetings
Mss App. for p=3 Tsuruta et al. App. for p=3 Mss App. for p=5 Tsuruta et al. App. for p=5 Mss App. for p=7 Tsuruta et al. App. for p=7
p=7 p=5
p=3
Figure 7.3. MSS approach vs. Tsuruta et al. approach mean results in terms of the percentage of scheduled meetings.(35 random samples generated for each pairhCh,pi).
These results are expressed in term of five criteria: (i) the CPU time spent by each of the two approaches, (ii) the percentage of scheduled meetings, (iii) the percentage of reduced soft constraints performed by the first step of the proposed approach, (iv) the required num-ber of messages passed and (v) the amount of exchanged information. We have introduced some modifications to the approach in [101] to make it worthwhile for both hard and soft constraints. These two approaches were carried out on the same meeting examples. Figures 7.2 and 7.3 show the achieved mean results of both approaches in term of CPU time and the percentage of scheduled meetings. These results show that our approach requires less CPU time than approach [101]. For example in the case of 7 participants and 50 hard constraints, the problem is over-constrained and thus no meetings can be planned, i.e., no agreement can be reached between all the attendants. Therefore, our approach can discover merely the absence of solution from the first step, and before starting the solving process.
In the case of 7 participants and 20 hard constraints, only a few meetings can be planned.
Table 7.2 shows that the percentage of pruned dates from possible ones is high (=96,66%).
Therefore, our approach is able to schedule the possible meetings in considerably less CPU time than approach [101], i.e., the approach in [101] requires more than five times the time needed by our approach. This result can be elucidated by the fact that the first step is useful in order to discard the dates that cannot be in any solution and consequently avoid exploiting them in the solving process, leading to decreased CPU time consumption.
Table 7.2. MSS approach mean results in term of the percentage of reduced time slots for each pairhp,cH i.
h3; 0i h3; 10i h3; 20i h3; 30i h3; 40i h3; 50i
%Reduction 0.00% 51.44% 80.17% 94.04% 99.13% 99.98%
h5; 0i h5; 10i h5; 20i h5; 30i h5; 40i h5; 50i
%Reduction 0.00% 67.25% 91.49% 98.82% 99.95% 100.00%
h7; 0i h7; 10i h7; 20i h7; 30i h7; 40i h7; 50i
%Reduction 0.00% 77.14% 96.66% 99.72% 100.00% 100.00%
Nevertheless, for the percentage of the meetings scheduled, the approach in [101] planned, for some cases, more meetings than our approach. This is defended by the fact that for our approach we tried to plan the most important meeting at first. For example, in the caseh7;
20ithe 40%of the meetings scheduled by the approach in [101] may or may not contain the most important meetings in the problem. Meanwhile, with our approach we are sure that the 14%of the meetings scheduled are the most important because they were first chosen to be processed using their weights.
As for the number of exchanged messages needed to reach an agreement among all the
0 500 1000 1500 2000 2500 3000 3500 4000 4500
0 10 20 30 40 50
Hard Constraints Ch
Number of Exchanged Messages
Mss App. for p=3 Tsuruta et al. App. for p=3
Mss App. for p=5 Tsuruta et al. App. for p=5
Mss App. for p=7 Tsuruta et al. App. for p=7
Figure 7.4. Mean results in term of the number of exchanged messages.
users, Figure7.4 shows that the proposed approach requires many fewer exchanged messages than the Tsuruta approach [101]. This number increases with the number of participants in the meeting, even if the problem has no solution, i.e., there is no possible time at which all the participants can be gathered. However, with the proposed approach, the percentage of reduced values increases with both the number of participants and the number of hard constraints, consequently the number of exchanged messages decreases.
Finally, concerning the size of exchanged messages, we measured the required amount of information to reach a consensus among participants for both approaches. Figure 7.5 shows that in all cases MSS transfer less information than Tsuruta et al. approach. Let’s recall that for Tsuruta et al. approach, the negotiation process is based essentially on sending constraints related the user. The amount of the transferred information decreases at each step of the iteration process. Nevertheless, this amount largely increases with the number of participants in the meeting. Regarding MSS approach, only during first step agents need to exchange all the possible time slots for the concerned meeting. This step is necessary in order to reduce the set of meeting’s dates and consequently to avoid as much as possible the checking of initially non-valid dates.
We performed statistical hypothesis testing to evaluate the fairness of the obtained random experimental results. In order to compare the means of the samples’ results obtained for both approaches in terms of CPU time and percentage of scheduled meetings, we measured them using Matlab6.1 the dependent two samples t-test with significant levelα= 0.05.
For the mean in CPU time, we formalized the null hypothesis H0 and the alternative
hypoth-0 10000 20000 30000 40000 50000 60000 70000
0 10 20 30 40 50
Hard Constraints Ch
Quantity of Exchanged Information
Mss App. for p=3 Tsuruta et al. App. for p=3 Mss App. for p=5 Tsuruta et al. App. for p=5 Mss App. for p=7 Tsuruta et al. App. for p=7
Figure 7.5. Mean results in term of the necessary amount of exchanged information, i.e., necessary number of slot times exchanged to reach an agreement.
esis H1as follows:
H0:µM SS App.=µT suruta et al. App.
H1:µM SS App.< µT suruta et al. App.
In all cases, i.e., for each pair hcH, pi, with 34 degree of freedom, the null hypothesis (H0)) is rejected with significance equal to zero, which means that it never happens even by chance that the observed value of T-statistic could be as larger or larger with confidence interval 95%.
As for the means in term of the percentage of scheduled meetings, we carried on the fol-lowing hypothesis testing:
H0:µM SS App.=µT suruta et al. App.
H1:µM SS App.6=µT suruta et al. App.
For the casesh0, 3i,h0, 10i,h0, 5i,h50, 0i,h0, 7iandh50, 7ithe percentages of scheduled meetings are exactly the same for both approaches. However for the remaining cases and according to the obtained two samples t-test result, the null hypothesis is rejected for all pair hcH, pi with maximum significance=0.0399 for h40, 7i which means that for this case by chance we would have observed values of T more extreme that the one in this example in
only 399 of 10000 similar experiments. A 95%confidence interval on the mean is [-0.2232 -0.0054], which includes the theoretical (and hypothesized) difference of both means. Also, same for the caseh10, 5i, the significance is higher than other cases equal to 0.0037. Where as all the other cases, the significance is very low or equal to 0.
We can conclude that our approach is a scalable approach that outperforms the approach described in [101] and this is especially true when the number of meetings and the number of participants increase. One must note also that our approach seems to be more appropriate to real-world applications by dealing especially with strong constraints (i.e., inequality) and by bringing forward consideration of discrimination among the proposed meetings. In addition, in our approach, agents do not reveal directly any of the information related to the human user even to a trust person. While the approach in [101] relies especially on exchanging users’ private information with the group agent, no level of privacy is preserved.
The first step of the MSS approach can fulfill a premature detection of the impossibility of reaching any agreement between all the participants and this by maintaining arc-consistency.