Multi-experts scheduling system for real-time applications

This thesis focuses on the decisional process of autonomous systems, and more particularly, on the way to take a decision when the time at disposal in order to assess the whole situation is shorter than necessary. Indeed, numerous systems propose solutions to the user that are more and more "intelligent", or at least more personalized and adapted to the present context. As the process of taking a decision is complex, it exists different methods of resolution based on hypothesis and/or methods being complementary and/or concurrent. The three following examples exhibit different domains where the use of several methods of resolution would be of prime interest : Financial market investments : numerous studies on the volatility of the financial markets have been performed in order to build an automatic system being able to select the content of the optimal portfolio. Its diversity should promote the financial gain while minimizing the risks of the investments. However, it is difficult to guarantee that a single method is sufficiently robust against the chaotic variations of the financial markets. Video compression became more democratic since the large usage of the World Wide Web, handheld game player and mobile phones. The compression methods mainly cut the image in different regions, named macroblocks. Various methods of compression are applied onto these regions depending on some of their characteristics : static macroblock (i.e. steady background), or macroblock containing a moving object or moving scene. The goal is to guarantee the highest compression ratio for all the macroblocks, while maintaining the visual quality without any artifacts onto the architecture used to play the video. Speech recognition is used in an increasing number of services, for example mobile phones can compose automatically the phone number of a person present in the contact names, only by pronouncing his name. It exists also different softwares which allow to transcribe under typed shapes, the stream of word dictated in a microphone. The variability of the human voices, the local accents, the regional pronunciations, and the presence of background noise into the various speech samples can affect more or less significantly one or another of the recognition methods. An "agent" is an instance which uses a methodology leading to a particular solution of a given problem. Thus, if the same problem can be solved with 5 different methods, then it exists at least 5 different agents. The use of a multi-agent system handling various resolution methods (agents), increases the knowledge of a given problem, and thus increases also the robustness of the proposed solution with regards to a single agent solution. Comparing the results of the different agents allows using the competition between them, but also their ability to cooperate in order to build a robust solution. However, the time at disposal limits the number of used agents. In the previous example, it would be possible to use only 3 methods (agents) among the 5 agents at disposal. The goal is thus to determine how to chose optimally the n = 3 used agents in order to guarantee that they contain the best solution among the 5 methods at disposal. The solution taken up in this thesis uses a "Blackboard" systems. This multi-agent system contains the list of all the agents which may be used to solve a particular problem. The main module, which is named the supervisor, is in charge to schedule the activation of the agents which should provide the optimal solution in a reduced amount of time. We have described the behavior of 4 different supervisors1 in order to highlight the advantages and drawbacks of each of them (see Fig. II.1). The supervisors use the reliability of the agents (credibility function) having proposed a solution at time t < t0, and proposes a scheduling policy for the agents at cycle time t = t0 in order to increase the robustness and reliability of the next computed solution. A scheduling is said optimal if the series of n agents having time to be executed contains the agent with the most important credibility over the m agents at disposal (2 ≤ n ≤ 6 m). We have highlighted the advantages and drawbacks of the different supervisors and described the aspects and the major constraints to take into consideration with regards to the application requirements to satisfy. Figure II.1: These plots compare the robustness of the four tested supervisors when the credibility of each agent follows a Gaussian distribution. In this example, 100 agents are used and each decisional process has been repeated 2'000 times in order to reduce the random behavior and highlights the main trend of the supervisors. The goal is to measure the robustness with which the performed scheduling can recover the optimal agent among a reduced population of agents being executed. The plot (a) highlights the number of times where the optimal solution has been found with regards to the number of active agents. Similarly, (b) shows the standard deviation with which the supervisors can find the optimal solution through the 2'000 repetitions. In order to characterize the robustness of the multi-agent system, we have modelized the credibility function of the different agents with several statistical distributions (Gaussian, Uniform, Rayleigh, bi-Gaussian). This credibility function reflects the confidence of the agents to find the most appropriate solution. The simulation results have proved that the performance of the supervisors is consistent over the different distributions used. Thus, when 50% of the agents have time to be executed, then we have shown that simpler supervisors can find the optimal solution in only 50% of the cases. In the contrary, the supervisors called "random change of less efficient", and "evolutionary evaluation" find the optimal solution in more than 85% of the cases. Consequently, using an appropriate scheduling of the agents by respects to the application requirements, allows to increase the efficiency of the proposed solution, even though the computation time is limited and does not allow to use more than n agents among the m at disposal. Moreover, depending on the application to satisfy, we have shown that the selection of the supervisor will be lead by two main constraints. On one hand, it will be necessary to satisfy the trade-off between the computation time needed to set up the scheduling and the robustness of the solution proposed by the multi-agent system after the remaining time at disposal. On the other hand, specific requirements of the application can restrict the use of one or another of the solution. For example, applications related to the spatial area, or with the avionics industry, would require that the use of a supervisor should produce a behavior perfectly reproducible when the input conditions are identical. Finally, we have illustrated the methodology described in this thesis by applying it to a practical example in the automotive field, the "Advanced Driver Assistant Systems" (ADAS). These modules are integrated into vehicles to ease the driving behavior and increase the safety of the users. The practical application performed is the detection of the lane where the vehicle is allowed to evolve, by using an embedded camera ("Lane Detection"). The goal is to maintain the optimal trajectory of the vehicle and thus, to reduce the accidents happening when performing a dangerous maneuver. Several methods to perform the lane detection exist and several have been integrated into different agents. Each one tries to bypass the detection limitations of other technics in order to solve optimally all the situations that could arise in uncontrolled environment. Thus, the aging or the lack of white lines are only few of these possible difficulties. Indeed, driving under bridges, entering into tunnels, or objects situated near the road can produce intensity change in the image that could lead to reduce the detection performance of some agents. The use of our multi-agent system increases significantly the detection robustness with regards to use a single method of detection. Moreover, it allows to guarantee the efficiency of the found solution in a wide range of situations. Thus, when using only 50% of the agents, we have shown that it is possible to select the optimal agent with a probability of about 85%, while maintaining a computation time of 50% of the agents. This performance can overcome 98% if 75% of the agents can be used. ______________________________ 1 The 4 supervisors having been tested are : a fixed scheduling of the agents ("Fixed set of agents"); a random selection of the agents ("Random selection of agents"); a random permutation of the less efficient agents ("Randomly change the less-efficient agents"); a scheduling based on the probability evolution of the agents performances ("Evolutionary evaluation of agents' pool").