José Barbosa
email: jbarbosa@ipb.pt

Paulo Leitão
email: pleitao@ipb.pt

Emmanuel Adam
email: emmanuel.adam@univ-valenciennes.fr

Damien Trentesaux
email: damien.trentesaux@univ-valenciennes.fr

Structural Self-organized Holonic Multi-Agent Manufacturing Systems

Keywords: self-organization, multi-agent systems, reconfigurable manufacturing control

Worldwide systems are increasingly growing into unprecedented complexity levels. This increase of system complexity has to be tackled with new control approaches, where decentralization is playing an important role and particularly the Multi-Agent Systems and Holonic Systems. Despite the benefits of this distribution, new problems arise such as the need for entities coordination. This paper proposes an innovative holonic multi-agent system architecture, named ADACOR 2 , which sets foundation on the already proved ADACOR architecture. This new control architecture is empowered by a two vector selforganization, called behavioural and structural self-organization. This paper describes the structural self-organization vector, particularizing the need for embedding in it learning techniques and nervousness stabilizer. A futuristic test bed, inspired in a real flexible-manufacturing system, is used to demonstrate the benefits of this vector in the architecture.

Introduction

Nowadays, problems' complexity has no parallel in past since the world complexity has grown into unprecedented levels. As examples, in avionics the system complexity has grown from the first airplanes to the nowadays state of the art airplanes, such as the Airbus A380, or in economics where an evolution from local economy to worldwide global markets has noticed. Complexity can also be found on diverse fields of modern society and range from telecommunications to economics or from health to ecosystems in nature. This amazing level of system complexity makes urgent the development of new solutions, methodologies and approaches to better tackle the current demands, such as controlling the chaotic behaviour that these systems may display. Also important to consider is to manage the butterfly effect present in such systems, where small changes in one part of the system can have a huge impact on the other side or at medium/long term. Manufacturing systems domain is also increasingly becoming more complex where a multitude of unexpected or unpredicted events are constantly appearing, such as rush orders, resources malfunctions, late changes requests, order cancelation/modification. The classical solution to solve these problems passes by the use of information and communication technologies and high processing power, usually using a centralized structure, where decision-making functions are centralized in one node that guarantees high levels of performance optimization. This is currently true for most of the control systems and in fact this approach still works pretty well if one assumes that the system is perfect in the sense that it doesn't have unexpected events. But, the truth is that nowadays industrial systems must deal daily with unexpected events and in that sense must promptly respond, effectively, to them. In this way, these traditional centralized approaches are unable to properly cope with these requirements due to its rigid structure.

One of the most consensual solutions to handle very dynamic and complex systems is the distribution of the processing capacity throughout the system by giving to individuals, more or less intelligent, the capacity to manage its local action space. In this approach, the global system's goals are achieved by cooperation, e.g. by means of information sharing or by the association of individual skills.

Several paradigms have risen to address these challenges, proposing distributed approaches, e.g. Multi-Agent Systems (MAS) and Holonic Systems (HS). MAS [START_REF] Wooldridge | An introduction to multiagent systems[END_REF] derive from the artificial intelligence field and is built upon autonomous and cooperative entities called agents, which are intelligent and autonomous entities capable to take decisions based on local knowledge. HS got inspiration by the work of A. Koestler [START_REF] Koestler | The Ghost in the Machine[END_REF] and has several differences from the MAS such as the creation of stable intermediary states as a mean to achieve optimization or the notion of holarchy which is a mixture of heterarchical autonomous entities (like in MAS) and hierarchical organizations, possibly considering the use of recursivity. The elementary concept in a HS is the term holon, proposed by Koestler, which derives from the Greek word holos which means whole and the suffix on that suggests a part like in proton. Another key difference between HS and MAS is that a holon can easily be designed as the integration of a physical with an informational part, facilitating the design of more real time and control-based approaches.

Detailing into manufacturing systems, these two paradigms, particularly MAS applications, have been used in the past in several different applications (see for example the surveys [START_REF] Leitão | Agent-based Distributed Manufacturing Control: A State-of-the-art Survey[END_REF][START_REF] Leitao | Past, Present, and Future of Industrial Agent Applications[END_REF]). One example, of a Holonic Manufacturing System, is the PROSA reference architecture, which defines the basic holons that a manufacturing system must have as also their basic interactions. Other example is the ADACOR (ADAptive holonic COntrol aRchitecture for distributed manufacturing systems) architecture [START_REF] Leitão | ADACOR: A Holonic Architecture for Agile and Adaptive Manufacturing Control[END_REF], that proposes an adaptive production control system that switches from a stable state, where the system is organized in a hierarchical approach to achieve optimization, to transient state, where the control is passed into the lower level entities for a prompt response to disturbances. This binary state has shown very good results facing very condition changing environments, but restrings the system to the two pre-defined states.

The current work sets foundation on this already proven holonic system and unleashes it from these two states by allowing the system to dynamically evolve without any pre-defined boundaries. This evolution, called ADACOR 2 , is supported by the self-organization concept, found in biology and other fields, decoupled in two different levels: behavioural and structural self-organization. The first one, appears at the micro-level, and is related to the increase of the performance of the individual holons by means of proper adaptation of their behaviour. The second one, described in this paper, appears at the macro-level, and is about the dynamic structural organization of the holons. Having this mechanism in mind, it can be stated that the ADACOR evolved into a more dynamic and open structure allowing the re-arrangement of the entities in the system, exploring the unpredictability of complex systems.

In such dynamic self-organized systems, the problem of nervousness [START_REF] Parunak | How to calm hyperactive agents[END_REF][START_REF] Hadeli | A Study of System Nervousness in Multi-agent Manufacturing Control System[END_REF][START_REF] Barbosa | Nervousness in Dynamic Selforganized Holonic Multi-agent Systems[END_REF], which is related to the will that entities have to change at the minimum stimuli from external or internal events, should be considered to guarantee the system stability. Additionally, the development of structural self-organized systems must consider important questions, like what is the best structural configuration, when the system should evolve/re-configure, and how to evolve, which answers may consider the implementation of learning mechanisms.

This paper depicts the architecture for the structural self-organization, as part of the self-organization principle used within the ADACOR 2 approach. To fully demonstrate the proposed approach, the architecture was implemented, tested and validated using a Flexible Manufacturing System (FMS) that is a re-design of the real AIP-PRIMECA, located at the of the Université de Valenciennes et du Hainaut-Cambrésis, in which the resources have moving capabilities.

The rest of the paper is organized as follows: Section 2 overviews the selforganization concept defined in the ADACOR 2 holonic multi-agent system architecture and Section 3 details one of its vectors, the structural self-organization. Section 4 describes the internal architecture of a holon belonging to ADACOR 2 focusing the model to support the self-organization capabilities. Section 5 presents the experimental validation of the proposed approach by using the AIP PRIMECA flexible manufacturing system. At last, Section 6 rounds up the paper with the conclusions.

ADACOR : enhanced by self-organization

The ADACOR control architecture defines four types of holons [START_REF] Leitão | ADACOR: A Holonic Architecture for Agile and Adaptive Manufacturing Control[END_REF]: Supervisor Holon (SH), Product Holon (PH), Task Holon (TH) and Operational Holon (OH). Besides defining the roles, behaviours and interactions among these holons, ADACOR also introduced an adaptive production control based on balancing the control structure between a stationary state (where the holons are organized according to a hierarchical structure) and a transient state (where the holons are organized in a complete heterarchical structure). The stationary state should be used as much as possible to achieve optimization, and the transient state should be adopted in presence of perturbations to provide adaptive response (returning to the stationary state after the resolution of the perturbation, which should be as fast as possible). This switching mechanism proved to be very efficient [START_REF] Leitão | ADACOR: A Holonic Architecture for Agile and Adaptive Manufacturing Control[END_REF] to manage the production control in very unpredictable scenarios, but is restrained to the two pre-defined states. ADACOR 2 unleashes the architecture from these chains by allowing the system to dynamically evolve throughout a set of configurations, dynamically discovered, using the concept of self-organization usually found in biology.

The self-organization mechanism considered in ADACOR 2 comprises two vectors, as illustrated in Fig. 1: the first vector, to cope with smaller impact perturbations, called behavioural self-organization, is achieved by providing holons a set of different behaviours that are dynamically selected accordingly to the current needs. The second vector, called structural self-organization, is more related to dynamic changing of the relations and interactions among holons. Additionally, since ADACOR 2 follows the holonics principles, the structural self-organization is also related to the establishment of intermediary states e.g., the group formation. This macro-level self-organization definition allows the system to dynamically adapt, in a more drastic manner, to larger perturbations by changing the holons relations. In this way, a configuration is defined as a snapshot of the system at a given point in time, having information of the holons state, behaviours and their relations (representing the organizational structure of the system). This context-aware knowledge is helpful in situations where the system must evolve, in the way that holons reason on this set of configurations to learn from past situations. To achieve this, ontologies plays an important role enabling the sharing of knowledge in this dynamic and distributed system. In this way, besides the ADACOR manufacturing ontology [START_REF] Borgo | Foundations for a Core Ontology of Manufacturing[END_REF] that has already been developed, a complementary ontology is developed to support the sharing of knowledge related to the configuration contextualization in this dynamic, distributed system. In case of conditions change, the holon(s) that have recognized the situation can find a starting point from similar conditions through the ontology rea-soning. This warm, i.e. not being executed from scratch, self-organization allows a faster and most optimized way to evolve into a stable configuration.

The decision of how to better cope with the condition changes, considers learning mechanisms aggregated to a nervousness mechanism to select the best option to take from either behavioural or structural self-organization (pushing the system into the limits but remaining under control). This selection is accomplished by analysing the performance indicators output from the known self-organization mechanisms of the holon. Additionally, learning mechanisms are also responsible to detect new opportunities to evolve, making possible for the system to increase its performance even if on the absence of a disturbing event.

Resuming, the main difference between ADACOR 2 and its predecessor is the removal of the two pre-defined states by introducing the concept of self-organization spited at two levels: behavioural at micro level and structural at macro-level.

Next sections will detail the structural self-organization mechanisms.

Structural self-organization in ADACOR 2

In this work, the structural self-organization is classified in a three level division. This classification closes the gap with the behavioural self-organization by relating it with the structural self-organization.

 Level 0 (emergence): the relations between holons are changed as consequence of the behavioural self-organization. The holon by changing its internal behaviour could, indirectly, imply changing its external relations. This level of structural changing is classified as weak since the structural change is not driven directly by the need.  Level 1 (logical structural self-organization): each holon is always trying to optimize its place into the holarchy structure. This constant optimization may drive the holon to change from holarchy, to belong to several holarchies at the same time or as freelancer to work completely autonomously.  Level 2 (physical structural re-organization): similar to level 1 with the addition that holons, e.g. OHs, can physically change their place, changing not only their relations and positions in the holarchy but their physical places.

The stimulus that can trigger a structural self-organization can be any event that disrupts or deviates the predicted function of the system, such as a rush-order, order cancellation, production quality issue, supply shortage, or resource malfunction. To illustrate this, two examples can be provided. The first example of a stimulus that can start a structural self-organization is the introduction of a big batch order. Let's assume that the system is functioning in a stable state with a given configuration, and that at a given point in time, a very large order arrives into the system. The system, realizing these new constraints, will select the most adequate structure to better cope with this. In the simplest way, individual holons can adjust themselves by changing their behaviour or if the impact to the system is large, the holons may find the need to start a structure re-organization. In other words, the holons can change relations keeping the holarchies composition, holons can change holarchies or, if possible, the physical resources can move into another working position to improve the performance indicators.

A second example, at a longer time window, concerns the smoothed changing in a usual set of recurrent orders. Let consider two types of products, A and B. Let also consider that a customer asking for a specific kind of product type B takes more and more importance compared to historical customers asking for product type A. This evolution in the production demand can be detected and the re-arrangement of the structure occurs smoothly to evolve with the needs of customers from a production optimized to make product of type A to a production optimized to make products of type B.

A pertinent question is how does the ADACOR 2 holons self-reorganize structurally? Getting inspiration from the social behaviour of swarms of fishes and birds, it is concluded that they function very well as a group, maintaining system equilibrium and, as a group, avoid predators (in our case, these are the system external perturbations). What is more amazing is that this is achieved by following very simple rules and without any central authority in charge.

ADACOR 2 holons follow the same basic principles as swarms, trying to constantly make cohesive groups but maintaining distances and having crowd management. One observed principle that is not followed in ADCOR 2 is the lack of central authority. In fact, a central authority is used to create stable intermediary states into the holonic holarchy introducing high levels of optimization. These higher level holons, i.e. SHs, have under their supervision a set of OHs, which they try to optimize. Another atomic rule in structural self-organization, under the SH umbrella, is to endow each group with a set of services, as diverse as possible, opening the possibility to attend a wider set of requests. This rule is not restrictive, allowing making more dedicated groups, i.e. more skilled groups, and also makes the system less dependent of a limited group of holons. This characteristic can be seen in Fig. 2, where the services are distributed uniformly among groups.

Fig. 2. Equality services distribution in ADACOR 2 group formation

Another crucial rule is related to the possibility of an OH be shared between SHs. Let's suppose that a given service is missing under a stable state governed by a SH. At a given point in time, a SH may find the need to acquire one more service in order to respond accordingly to an external demand or even to the malfunction or decommissioning of the existing OH that offers that service. In this case, the SH will search within the system domain for OHs that offers the same service. Once found, the SH will start a negotiation process, with the other SH or directly with the OH in case of no hierarchical dependency, to find equilibrium between these two groups, i.e. not degrading heavily the service from the source group but allowing the second one to have the possibility to acquire that service. In the case of OH sharing among SHs, its utilization is achieved by the higher level negotiation of the SHs to whom he belongs. An example of this mechanism is depicted in Fig. 3 where the OH that offered the service #4 becomes unavailable, triggering the search to re-acquire the lost service. After a negotiation process (i.e., the first agreement from the SHs level), the SH#1 proposes the OH that has the desired service to belong also to its group. If agree, the holons start the structural re-arrangement and relationship redefinition ending on the holon sharing among groups. Naturally, ADACOR 2 being a holonic multi-agent system allows that this negotiation process may be started directly with the OH, bypassing the SH.

Architecture of individual holons to support structural selforganization

The structural self-organization of the system is driven by the behaviour of the distributed holons that constitutes the ADACOR 2 system. For this purpose, each one exhibits proper mechanisms in its internal structure architecture to support the structural self-organization mechanism. Fig. 4 illustrates the internal architecture of a holon belonging to ADACOR 2 , focusing mainly the model to support self-organization, which comprises primarily the monitoring, discovery, reasoning, nervousness stabilizer and dispatcher components. The structural self-organization process can be very time-consuming, especially in large-scale systems. In this way, ADACOR 2 has on the start of this process a contextaware feature. The system, at every disrupting event, takes a snapshot of the system state additionally with the actions taken and the achieved results (i.e., performance indicators). This context-aware mechanism, aided with data processing, e.g. data mining, will facilitate futures events by allowing the system to filter from the best measures taken to similar events and start a warm structural self-organization. The discovery and monitoring modules, supported by a knowledge base, will feed the reasoning and learning engines that are responsible to discover new opportunities to evolve and decide how to evolve. In this approach, the learning capabilities embed in holons assume crucial importance to support the generation of new knowledge, contributing to behave better in the future. The implementation of such learning capabilities can range from simple observation or repetition techniques to more complex ones, such as neural networks or support vector machines. The selection of the learning techniques to be deployed in ADACOR 2 must consider several features. Among them are the type of communication to be considered (direct or indirect) and scalability. Other issues are related to the fact that multi-agent systems are typically deployed into dynamic environments and with problem decomposition to reduce complexity [START_REF] Panait | Cooperative Multi-Agent Learning: The State of the Art[END_REF].

ADADCOR 2 uses different types of learning techniques in different parts of holons or different parts of the system. Social learning is used to support the propagation of new behaviours among the holons or by PHs when creating THs, passing accumulated knowledge from past THs. A reinforcement learning mechanism may be used as a behaviour mechanism for route selection. This reinforcement learning mechanism, inspired in the ant food foraging mechanism, separates the exploration and exploitation phases, and relies in the random decision of the holon as a way to discover new solutions. The feedback from past decisions is also used, where bad past decisions will have a negative impact in the future choice for the same decision as opposite to a good result that will have a positive impact.

In such dynamic environments, where holons are autonomous and self-organized, the system has the predisposition to become unstable and chaotic. Instability and chaos are addressed in ADACOR 2 by applying nervousness stabilizers to each of the two self-organization mechanisms. The purpose of the nervousness stabilizers is to bring stability into the behaviour of the holons and to the structural self-organization in ADACOR 2 . By introducing these stabilizers, the system operates in a such manner that is pushed to its limits by enhancing the self-organization and chaotic principles, but always under control. Note that any decision to evolve provided by the reasoning and learning engines is evaluated in the nervousness stabilizer which will validate the decision.

Typical approaches to calm the holons' will of change passes by restring the number of changes during a given time, by allowing the entities to change only at predefined intervals or by setting the exploration/exploitation threshold [START_REF] Barbosa | Nervousness in Dynamic Selforganized Holonic Multi-agent Systems[END_REF]. ADACOR 2 holons use an innovative technique [START_REF] Barbosa | Nervousness in Dynamic Selforganized Holonic Multi-agent Systems[END_REF] where the inspiration from the classical control theory, namely the Proportional, Integrative and Derivative (PID) controller, acts as a constrain to the response time and defines the accepted deviation from the known optimal plan or the speed of the deviation mitigation.

The AIP cell application example

The testing and validation of the proposed structural self-organization mechanism uses an adapted version of the AIP-PRIMECA manufacturing system, located at the Université de Valenciennes et du Hainaut-Cambrésis. In this scenario, resources can self-reorganize, responding in a more appropriate way to perturbations maintaining high levels of performance. This test scenario allows to verify all potentialities of the structural self-organization of ADACOR 2 .

System description

The real AIP-PRIMECA manufacturing system comprises a set of 6 resources, each one able to perform a set of services that are linked by a fixed conveying system [START_REF] Pach | An effective potential field approach to FMS holonic heterarchical control[END_REF].

The proposed system assumes that resources have moving capabilities in the sense that they can unplug from one working position and be moved into another working position. A working position is a place in the environment that is equipped with supporting systems for resource normal functioning, such as power and communications. The rail type conveyor system present in the real AIP cell is removed and the transportation between resources is accomplished by using Automatic Guided Vehicles (AGVs). Fig. 5 depicts the conceptual view of the futuristic cell, where the purple places represent working positions and the green ones can only be used for routing paths. For transportation calculation times it is assumed that moving from one point to another takes 3 seconds to the AGV in a clear path. The shifting of resources depends from resource to resource since the complexity of cables, size and weight can vary. Having this in mind, the ADACOR 2 holons are deployed into the production control system, with resources being mapped as OHs and each AGV as a specialized transporter instantiation of the OH (see Fig. 5). This test bed is composed by 6 resources, each one having a number of offered services, as illustrated in Table 1. A level 3 structural self-organization was used for the tests, since resources will have the possibility to shift place in the shop-floor. The structural self-organization mechanism is triggered when a batch of orders is allocated to an OH. After receiving a batch of orders, the OH will start an information gathering from other OHs, where resource queue, allocated work-orders, processing times and actual location, is exchanged. The procedure used follows the principle that the most overloaded OH are the most critical ones and in that way tries to allocate them first by minimizing the transportation times between them. After finishing the allocation of all OHs, each OH sends the information of either better or worst solution achieved, from actual resources disposition. In the case of a better solution, the OH sends the KPI and the new allocation places to all the OH. The overall best solution, found in each OH, is automatically assumed and used.

Analysis of the results

The described system, developed using the JADE framework [START_REF] Bellifemine | Developing multi-agent systems with JADE[END_REF] and the Java Expert System Shell [START_REF] Friedman-Hall | Jess in action[END_REF], initializes with a manufacturing order to produce 2xBELT. After 120 seconds a new manufacturing order to produce 5xAIP appears in the system, which triggers a structural self-organization, see Fig. 6. Two scenarios are simulated and compared to evaluate the structural selforganization. On the first scenario the structural self-organization is disabled while it's enabled on the second one. For each scenario, several simulations were done and average values are presented in Table 2. As can be observed by the analysis of the previous table, enabling the structural self-organization reduces the overall Cmax, allowing a performance improvement. This is mainly accomplished by the reduction of transportation times when the structural self-organization is enabled (reduction from 19,4% to 14,9%). Also a reduction of the time to process each individual order was noticed.

The achieved preliminary experimental results show the merits of the structural self-organization approach to face severe changing conditions. However, the experiments also showed new possibilities to improve the proposed algorithm, e.g. by considering optimization in the re-configuration of the resources during the structural self-organization process.

Conclusions

System complexity has grown into unprecedented levels, turning on the need of new control architectures. In this subject, MAS and HS play an important role by proposing a distribution of the processing capacity by several autonomous entities. This paper introduced an innovative control architecture called ADACOR 2 , which considers a two vector self-organization mechanism, named behavioural and structural self-organization. The structural self-organization, detailed in this paper, operates in a macro-level and is related to the relations between holons and holarchies formation.

ADACOR 2 by being proposed to work in highly dynamic systems is supported with learning mechanisms allowing the dynamic discover of new ways to evolve. Additionally, by giving autonomy to these entities, they can display some nervous-ness, making the system to become more unstable. The idea is to push the system to its limits, by enhancing the self-organization and chaotic principles, but maintaining the system under control, by actuating in the nervousness control.

The structural self-organization mechanism was tested in a production cell, inspired in the real AIP cell, where resources have the possibility to shift their position in the shop-floor. The achieved preliminary results show that enabling the structural self-organization mechanisms a performance increase is achieved.

Future work will be devoted to improve the algorithms considered in the structural self-organization mechanism and to merge the two self-organization principals in ADACOR 2 .

Fig. 1 .

 1 Fig. 1. Self-organization in ADACOR 2 holonic architecture

Fig. 3 .

 3 Fig. 3. Structural self-organization initiation: service disruption

Fig. 4 .

 4 Fig. 4. Model to support the self-organization mechanisms

Fig. 5 .

 5 Fig. 5. Cell configuration test scenario (on the rigth side the real AIP cell).

Fig. 6 .

 6 Fig. 6. Structural self-organization in practice

Table 1 .

 1 Resource service list and processing times

	service	M 1 M 2 M 3 M 4 M 5 M 6
	Loading	10
	Unloading	10
	Axis	20	20
	R_comp	20	20	20
	I_comp			20
	L_comp	20	20	20
	Screw_com p
	Inspection			5
	Recovery			60

Table 2 .

 2 Experimental results

		Without structural self-organization	With structural self-organization
	Cmax	1147,5 s	1112 s
	%transpTime	19,4 %	14,9 %
	avg(order)	725,2 s	646,2 s


Benjamin Senechal
email: benjamin.senechal@lis.inpg.fr

Denis Pellerin
email: denis.pellerin@lis.inpg.fr

Laurent Besacier
email: laurent.besacier@imag.fr

Isabelle Simand

Stéphane Brès

Audio, Video and Audio-Visual Signatures for Short Video Clip Detection: Experiments on Trecvid2003

In this paper, we present the association of audio and video signatures for short video clip detection. First, we present an audio signature based on the spectral flatness measure. Then we describe a spatio-temporal video signature, based on the evolution of gray level centroids over time. The major contribution of this work is the association of these two signatures in a so-called audiovisual signature by late integration of similarity measures obtained on both modalities. Our experiments conducted on a large video database (28Gb / 34h extracted from TRECVID2003) show that our audio-visual signature is more robust than the audio-only or video-only signatures, and also permits better detection of video clips of shorter duration (about 2 seconds).

INTRODUCTION

The main goal of the TREC Video Retrieval Evaluation (TRECVID) is to promote progress in content-based retrieval from digital videos via open metrics-based evaluation [START_REF] Smeaton | TRECVID 2003 -An introduction[END_REF]. For this, many features, extracted from audio, video or text obtained with automatic speech recognition (ASR), can be used. While automatic speech recognition can be very useful to extract keywords and perform topic detection on a video stream, this technology has the drawback of not being easily transposable from one language to another. As an alternative, simpler technologies, consisting in detecting pertinent key sounds, so-called jingles, can reveal very interesting semantic information. For example, detecting automatically a particular jingle on a TV broadcast program can announce a particular sequence like the weather forecast.

Jingle detection can be related to a recent domain also named 'audio monitoring' or audio fingerprinting [START_REF] Cano | A review of algorithms for audio fingerprinting[END_REF]. It is generally based on the creation of a compact representation (signature) of each multimedia document in a database. The particularity of audio fingerprinting is that the search is generally based on a strong matching criteria instead of a similarity one. A similar process can also be applied to the video channel of a multimedia document [START_REF] Cheung | Efficient video similarity measurement with video signature[END_REF]. In this case, we call it 'video fingerprinting'.

In this paper, we discuss the interest of the association of audio and video signatures for short video clip detection. We first propose an audio signature which has the advantage of being relatively compact, since it uses only 8 acoustic parameters per frame, corresponding to the spectral flatness feature which is part of the MPEG-7 low level description [START_REF] Allamanche | Content-based identification of Audio Material Using MPEG-7 Low Level Description[END_REF]. We also describe a spatio-temporal video signature, based on the evolution of gray level centroids over time. This signature is compact (8 coefficients per frame). The major contribution of this paper is the proposal of an audio-visual signature which combines both audio and video signatures. To our knowledge, no real audio-visual signature has been proposed in the literature, except in [START_REF] Li | Multimedia content processing through cross-modal association[END_REF] where a crossmodal association was proposed for multimedia content processing. All three audio, video and audio-visual signatures are systematically evaluated on a same 34-hour database which is part of the TREC2003 video database.

In section 2, we describe the audio signature, as well as the general video clip detection system. Section 3 is dedicated to the description of the video signature proposed while section 4 presents the audio-visual signature. Section 5 describes the experiments and results and section 6 concludes this work.

AUDIO SIGNATURE

Each reference video clip was described by low level descriptors based on a spectral analysis while dissimilarity was measured between the target video clips and the whole video test set with a Euclidian distance. In the next subsections, we describe the audio signature more precisely.

Feature Extraction

Our low level descriptors were 8 coefficients corresponding to the spectral flatness feature computed on 8 frequency bands. This spectral flatness feature is part of the MPEG-7 low level description and has shown to give interesting results for audio fingerprinting [START_REF] Allamanche | Content-based identification of Audio Material Using MPEG-7 Low Level Description[END_REF]. We have observed that the spectral flatness measure (SFM) is more efficient that the simple spectral coefficients by channel. Indeed, the right minima are easier to detect on the distance curve (Fig. 2.a) because the noise is reduced. Moreover, the number of coefficients necessary is much lower. As a comparison, 29 spectral parameters are used in [START_REF] Pinquier | Jingle detection and identification in audio documents[END_REF] for jingle detection. The formula of the SFM for the frequency band k is given by equation 1, where c(i) are filter bank coefficients corresponding to the spectral energy computed on n different frequency subbands inside frequency band k.

∏ = = = = = n i i n n i i k i c n i c SFM 1 1 ) ( 1 ) ( (1)
The so-called SFM is a function which is related to the tonality aspect of the audio signal and can therefore be used as a discriminating criterion between different audio signals.

It is also important to note that our frequency scale is not linear but logarithmic (we actually use the MEL scale, widely used in speech processing). The parameters are extracted on 64ms windows with a window shift of 33.375ms, corresponding approximately to the video frame rate. This window shift analysis will allow both audio and video signatures to be aligned which is particularly important to design the audio-visual signature.

Short video clip detection

The video clip detection principle is the same for the audio, video or audio-visual signature. It is described more precisely in the following subsections.

Distance computation

A reference video clip (the request) is characterized by a sequence of M 8-dimensional vectors which is called the signature of the clip. The size M is the number of analysis frames and corresponds here to the number of images on the video clip, because of the window shift value chosen. The detection consists in finding this sequence in the data flow (the database), which is also transformed in a large sequence of N 8-dimensional vectors (N>>M). The signature and the data flow are compared using an Euclidean distance, we then obtain N-M+1 distance values given by:

d h = = = = = M i i j j 1 8 1 | a (i-1+h) j -b i j | , 1 ≤ h ≤ N-M+1 (2)
where a kj , is the j-th SFM coefficient of vector k in the data flow signature (k=1..N, j=1..8), and b ij, is the j-th SFM coefficient of vector i in the video clip request signature (i=1..M, j=1..8).

Minima detection on the distance curve

The goal of this step is to find minima (valleys) on the distance curve computed in the previous step. An adaptative threshold is first applied. It is function of the mean and standard deviation of the distance curve. Then, the final video clip detection decision is made according to the width of the valleys detected, since it was shown in [START_REF] Pinquier | Jingle detection and identification in audio documents[END_REF] that the wider valleys may correspond to false alarms.

VIDEO SIGNATURE

We have chosen to characterize each video by calculating the gray level centroid of each frame of the video. The coordinates (c x ,c y ) of the centroid are calculated as the weighted sum of the pixel positions, the weights being the gray values of the pixels:

_1 0 _1 0 ( . ) size i i i x size i i L x c L = = = _1 0 _1 0 ( . ) size i i i y size i i L y c L = = = ( 3
)
where size is the number of pixels considered in the image, and L i the gray level or the luminance of the pixel.

Then, these coordinates are standardized to a single frame size. The resulting point is obviously not significant for one frame, but becomes characteristic for several successive frames, due to its movement during a few seconds. As a consequence, it leads to a spatio-temporal signature (Fig. 1).

As a video can be related to a complex scene, a single centroid is not sufficient to characterize it. We thus propose to divide the frames into several sub-images. Based on our experiments, dividing a frame into four quarters is the best compromise between the complexity of the signature and its discriminative power. For each quarter, a centroid is calculated. This allows us to keep minimal spatial information on the gray level repartition.

The computation of the centroids' location is biased toward brighter areas in order to amplify the centroids' movements. This is done by a look-up table, without any additional cost (Eq. 4). Then, the motion is less uniform and easier to be discriminated.

L f L = + ( 4
)
where L is the original gray level between 0 and 255. The signature of an image is composed of the eight values of the four centroids' coordinates. The signature of a video consists of the signatures of its images.

We have sub-sampled the image horizontally and vertically to 1 pixel out of 8 to speed up the computation. This selection is founded on the redundancy due to the gray level correlation of neighboring pixels.

The unicity of the signature cannot of course be proved but we shall assume this unicity as a consequence of the complexity of the signature: 8.N pixel locations, where N is the number of frames. For short video clips, the (video and audio) signatures are compact (for example, N=150 for a 5s video clip duration). For long video clips, the signature could be calculated after a temporal subsampling to reduce the frame number and then the size of the signature.

AUDIO-VISUAL DETECTION

The audio-visual method for video clip detection consists in using the signatures above. As the time step is synchronized between the video and the audio signatures, we propose to simply normalize both audio and video distance curves, and to add them together. Thus, our A/V fusion is not performed at the feature level, but at the level of the distance curves (late integration). After that, the minima detection process can be applied as it is done for audio or video signatures. Figure 2 presents an example of distances between a video clip and the data flow for audio, video and audio-visual signatures. The appearance of the three curves is similar. In this example, we observe three clear minima (valleys) which correspond to the same video clip repeated three times. For the audio-visual signature (Fig. 2c), the sum of the audio and video distance curves reduces the variance of the distance curve and facilitates the detection of the minima (illustrated by dotted lines on Fig. 2).

EXPERIMENTS AND RESULTS

Database and performance metrics

In our experiments we have used the TRECVID2003 database. This database is made up of TV broadcast news coming from ABC and CNN channels. We have selected 7 video clips which appear frequently in the database: six of them announce a particular news sequence, and the last one is an advertisement. The video clip detection performance measure metrics are recall R and precision P and are defined as follows.

-Recall: the percentage of the total relevant documents in a database retrieved by the search.

-Precision: the percentage of relevant documents in relation to the number of documents retrieved.

Results for audio, video and audio-visual signatures with a real ground truth

We have selected 69 videos (43 from CNN and 26 from ABC, in the MPEG format at 256kbps layer 2) from TRECVID2003 which represents a total duration of about 34 hours and 28 Gb of data. We have also selected video clips which are present a great number of times in our video base. A real ground truth, corresponding to the time location of all the video clip occurences in the 69 videos was obtained by manual annotation.

Case of video clips longer than 5s

Table 1 presents the detection performances for audio, video and audio-visual signatures in the case of video clips between 5 and 10s duration. For all the occurences of video clips 1 to 3, the audio stream is unchanged, whereas the video stream presents some variations (for instance, some images with journalists change for each opening) . In these cases, recall and precision ratios are high with audio signatures and lower for video ones. For all the occurences of video clip 4, it is the contrary: the video stream is unchanged, whereas the audio stream presents some variations (some words change according to the day). In these cases, recall and precision ratios are high with video signatures and lower for audio ones. We can note that, except for video clip 1 (which presents important variability on the video channel and a variable duration), audio-visual signatures give results close to the best ones obtained with audio or video signature. For video clips 5 and 6, the audio and the video streams are unchanged. Thus, recall and precision ratios are high with audio, video and obviously audio-visual signatures. Table 2 presents the detection performances for audio, video and audio-visual signatures in the case of shorter video clips. Clips 7, 8 and 9 have been made by shortening respectively clips 3, 4 and 5. In this case, the audio and video signatures are more sensitive to variations on respectively audio or video streams. Consequently, the quality of results for audio and video signatures generally decreases compared to table 1. Nevertheless, we can note an improvement of audio results for video clip 8 (versus video clip 4) because during the short duration clip the audio stream remains unchanged. On the contrary, very good results are obtained with audio-visual signatures. In particular, we observe that the association of audio and video signatures strongly increases precision (clips 7).

Finally, the few wrong clips retrieved look like the initial request. Video clip 10 does not exist in a longer version. In that case, audio and video signatures alone give poor results for detection, while the audio-visual signature is efficient.

Change of compression format

Table 3 presents the detection performances for audio, video and audio-visual signatures in the case of compression of the audio or video requests. It shows that the results remain good in spite of compression.

CONCLUSION AND FUTURE WORK

In this paper, we have presented the association of audio and video signatures for short video clip detection. Our experiments conducted on a large video database (28Gb / 34h extracted from TRECVID2003) have shown that our audio-visual signature is more robust than the audio-only or video-only signatures. We have also shown that the audio, video and audio-visual signatures are robust against some change of compression format (MP3 and DivX).

Figure 1 :

 1 Figure 1: Example of motion for a barycenter on a few frames.

Figure 2 :

 2 Figure 2: Example of Euclidean distances between a video clip and the data flow for a) audio and b) video signatures. c) Euclidean distance for audio-visual signature obtained by addition of curves a) and b) after normalization.

Table 1 .

 1 Case of video clips > 5s: recall R and precision P ratios with audio, video and audio-visual signatures.

		Dura-	Occu-	Audio	Video	Audio-
		tion (s)	rences			visual
				R(%)	R(%)	R(%)
				P(%)	P(%)	P(%)
	1: ABC-	10.2	26	80.7	57.6	65.3
	start			100	100	100
	2: CNN-	7.2	38	100	65.7	100
	dollar			100	100	100
	3: CNN-	5.2	40	100	90	100
	topstories			100	100	100
	4: CNN-	8.5	40	10	97.5	87.5
	sport			100	90.6	100
	5: CNN-	5.2	120	100	100	100
	headline			99.1	100	100
	6: advert-	8	3	100	100	100
	merri			100	100	100
	Total		267	84.6	88.7	94.7
				99.5	98.3	100
	5.2.2. Case of shorter video clips (<5s)

Table 2 .

 2 Case of shorter video clips: recall R and precision P ratios with audio, video and audio-visual signatures.

		Dura-	Occu-	Audio	Video	Audio-
		tion (s)	rences			visual
				R(%)	R(%)	R(%)
				P(%)	P(%)	P(%)
	7: sCNN-	3	40	97.5	57.5	85
	topstories			65	85.7	97.1
	8: sCNN-	3	40	100	92.5	92.5
	sport			100	71.1	86
	9: sCNN-	2	120	100	97.5	98.3
	headline			47.7	100	98.3
	10: ABC-	2	16	100	6.25	100
	closerlook			32	100	69
	Total		216	99.5	81.9	94.9
				53.5	88	92.7

Table 3 .

 3 Case of compressed video clips: recall R and precision P ratios with audio (MP3 96kbps), video (DivX 500kbps) and audio-visual (MP3 96kbps and DivX 500kbps) signatures.

		Dura-	Occu-	Audio	Video	Audio-
		tion (s)	rences			visual
				R(%)	R(%)	R(%)
				P(%)	P(%)	P(%)
	1: ABC-	10.2	26	84.6	57.6	65.3
	start			100	100	100
	5: CNN-	5.2	120	100	100	100
	headline			98.3	100	100
	10: ABC-	2	16	100	6.25	100
	closerlook			41	100	84.2
	Total		162	97.5	84	94.4
				86.3	100	98.1


José Barbosa
email: jbarbosa@ipb.pt

Paulo Leitão
email: pleitao@ipb.pt

Emmanuel Adam
email: emmanuel.adam@univ-valenciennes.fr

Damien Trentesaux
email: damien.trentesaux@univ-valenciennes.fr

Behavioural validation of the ADACOR 2 Self-organized Holonic Multi-Agent Manufacturing System

Keywords: behavioural self-organization, multi-agent systems, reconfigurable manufacturing control

Global economy is driving manufacturing companies into a paradigm revolution. Highly customizable products at lower prices and with higher quality are among the most imposed influence factors. To respond properly to these external and internal constraints, such as work absence and machine failures, companies must be in a constant adaptation phase. Several manufacturing control architectures have been proposed throughout the years displaying more or less success to adapt into different manufacturing situations. These architectures follow different design paradigms but recently the decentralization and distribution of the processing power into a set of cooperating and collaborative entities is becoming the trend. Despite of the effort spent, there is still the need to empower those architectures with evolutionary capabilities and self-organization mechanisms to enable the constant adaption to disturbances. This paper presents a behavioural mechanism embed in the ADACOR 2 holons. A validation procedure for this mechanism is also presented and results extracted. This validation is achieved through the use of a benchmark and results are compared with classical hierarchical and heterarchical architectures as also with the ADACOR.

Introduction

The current panorama of the world economy is pushing the manufacturing companies to adopt more adaptive and responsive control architectures. Product customization, higher quality and shorter life-cycles are on the epicentre of the requirements imposed to manufacturing companies [START_REF] Elmaraghy | Change in Manufacturing -Research and Industrial Challenges[END_REF]. Situations of worker absence, resource breakdown and product demand fluctuation are also, at an internal level, a daily concern that require an increase of responsiveness and adaptation from the manufacturing control point of view. A proper manufacturing control architecture is mandatory, required to present responsiveness to the imposed disturbances, either at an internal or external level, guaranteeing the highest possible performance level of operation.

Traditionally, manufacturing control architectures relied on hierarchical organization as the mean to design those control systems. This type of organization has the advantage of collecting the information and place the processing and decisional capacity at central nodes that have a wider view of the system state and that are able to achieve high levels of performance optimization. At the other side, a considerable drawback can also be pointed out, related with the fact that the information processing time is high, decreasing dramatically the system responsiveness.

More recently, there's the growing trend of promoting the decentralization of the decision entities, bringing them closer to where they are really needed. This paradigm is also aligned with new research trends, such as the Cyber Physical System [START_REF] Lee | Introduction to embedded systems: a cyber physical systems approach[END_REF] and the Industrial Internet [START_REF] Evans | Industrial Internet: Pushing the Boundaries of Minds and Machines[END_REF] paradigms.

Manufacturing control architectures have been proposed throughout the years that already use the decentralization concepts. Notably in the holonic paradigm, two reference architectures can be pointed out, namely the PROSA [START_REF] Brussel | Reference Architecture for Holonic Manufacturing Systems: PROSA[END_REF] reference architecture and the ADACOR (ADAptive holonic COntrol aRchitecture for distributed manufacturing systems) [START_REF] Leitão | ADACOR: A Holonic Architecture for Agile and Adaptive Manufacturing Control[END_REF].

Despite the aforementioned, this new generation of manufacturing control architectures still need to further explore evolutionary theories and bio-inspired mechanisms, such as self-organization. To this part, there are already some propositions, namely the PROSA+ANTS [START_REF] Hadeli | Multi-agent Coordination and Control using Stimergy[END_REF] and the P2000+ [START_REF] Bussmann | Self-Organizing Manufacturing Control: An Industrial Application of Agent Technology[END_REF]. The first, extends the PROSA reference architecture with inspiration from the ants food foraging that is used as forecast technique, while on the second one, a buffer type self-organization mechanism is used as the system regulation mechanism.

This paper briefly presents the ADACOR 2 manufacturing control architecture that proposes to enhance its predecessor by acting at two levels: micro level, named behavioural self-organization, and at a macro level, named structural self-organization. The assessment and evaluation of the behavioural component is drawn, starting by depicting a mechanism used during this process and analysing important Key Performance Indicators (KPI).

The rest of the paper is organized as follows: Section 2 makes a brief description of the ADACOR 2 self-organized holonic multi-agent system architecture while Section 3 describes a magnetic based self-organization mechanism used during the validation process. Section 4 describes the validation procedure and results of the behavioural selforganization vector. At last, Section 5 rounds up the paper with the conclusions.

2

A self-organized manufacturing control architecture ADACOR 2 sets foundation of the well-known holonic manufacturing control architecture, named ADACOR. Therefore, ADACOR 2 makes use of the same set of holons as it have been defined in ADACOR, namely on the Supervisor Holon (SH), Product Holon (PH), Task Holon (TH) and Operational Holon (OH).

Briefly, the SH is responsible to introduce optimized schedules into its holarchy, the PH possesses the knowledge to produce the product that it's responsible for, whereas the TH has the responsibility to manage a product instance that is being produced, taking manufacturing decisions concerning that product. Finally, the OH maps the resources available at the shop-floor, managing its internal agenda, either negating directly with the TH or accepting the schedules from the SH.

Precisely at this last point, ADACOR proposed a binary configuration, where when the system is operation under a well-defined situation, the SH introduces optimization issuing an optimized schedule into lower level holons balancing into a more heterarchical organization where THs negotiate directly with the OHs, increasing the responsiveness of the system. This binary state is ADACOR's most strong point, allowing the combination of optimization with responsiveness, but it's also a weak point since it limits the system into two predefined configurations.

ADACOR 2 makes use of evolutionary theories and self-organization principles to enable the ADACOR architecture to evolve smoothly as possible and as drastic as necessary, unbounding the system from the two predefined configurations [START_REF] Barbosa | Dynamic self-organization in holonic multi-agent manufacturing systems: The ADACOR evolution[END_REF].

In ADACOR 2 , the evolution towards the system re-configuration is supported in two distinct manners:

 A micro-level self-organization, which is related to the self-organization of the behaviour of individual holons, provoking the emergence of a new global behaviour, and in this way a system adaptation. To achieve this, holons have built-in a set of different behaviours and use embedded learning and discover mechanisms to detect new opportunities to evolve and the proper way to reconfigure their behaviours [START_REF] Barbosa | Self-Organized Holonic Multi-agent Manufacturing System: The Behavioural Perspective[END_REF].  A macro-level self-organization, which is related to the re-organization of the interactions among the holons, provoking a new global behaviour based on a new society of holons [START_REF] Barbosa | Structural Self-organized Holonic Multi-Agent Manufacturing Systems[END_REF]. To achieve this, holons also possess a set of mechanisms that can be used to detect better structural organization and mechanisms to proceed to its implementation. The need to act at these two different levels is justified by having different disturbance groups, which impact the system in different levels. Having this in mind, ADACOR 2 is enriched with different mechanisms as ways to overcome these constraints levels. The low impact perturbations, being more limited in time and space, can be addressed locally using low impact measures as opposite to high impact perturbation where a deep and long term change in the system can be necessary. Behavioural selforganization is then applied into the micro-level of the system while the structural selforganization is acting on the macro-level allowing the system to evolve into a new configuration (see Figure 1).

Considering that the system is working with a given configuration, C i , it can either evolve by applying one and/or two of the considered self-organization mechanisms. When a self-organization procedure is applied to either overcome a disturbance or to improve the current holon/system performance, it is said that the system evolves into a new configuration, C i+1 , since the current system state has changed.

behavioural self-organization C i C i+1 #3,4 #1,5 #3,4 #1,5 #3,4 #1,5 #3,4 #1,5 #1,5 #1,5

Figure 1 -Evolutionary components in ADACOR 2

The behavioural self-organization is observed at micro level, where each individual holon may change its internal behaviour according to the external conditions, resulting in a smooth evolution. The second component, named structural self-organization, is observed at the macro level and drives system to a drastic evolution by changing the relations between the holons. In this way, the system can either evolve using behavioural self-organization and/or structural self-organization, to face the external or internal disturbances.

The holons internal organization must also be re-designed to accommodate these self-organization components and to include a nervousness controller. This controller becomes necessary in this self-organized architectures since entities (and the system) might display instability features due to the entities constant will of adaptation [START_REF] Barbosa | Nervousness in Dynamic Selforganized Holonic Multi-agent Systems[END_REF].

A behavioural self-organized mechanism

Having in mind the two self-organization components, there is still the need to develop and embed into the holons such mechanisms. This section presents, in a simplified manner, one of the used mechanisms that enable the holons, namely the THs, to adapt dynamically their behaviour. The concept of a Potential Field (PF) is a technique that gets inspiration from the magnetism phenomenon, particularly from the inherent attraction and repulsion forces. This phenomenon can be the inspiration to design dynamic and reactive techniques. These concepts have already been used in several application areas such as in game development [START_REF] Hagelbäck | A Multiagent Potential Field-Based Bot for Real-Time Strategy Games[END_REF] robots motion planning [START_REF] Dolgov | Path Planning for Autonomous Vehicles in Unknown Semi-structured Environments[END_REF] and even in manufacturing control [START_REF] Zbib | Heterarchical production control in manufacturing systems using the potential fields concept[END_REF].

Since this approach is reactive, where the emitted force (or field) is changed as soon a given condition changes, it is a good candidate to be used as a behaviour technique for very reactive environments. In such way, an algorithm based on this concept was developed and deployed in ADACOR 2 holons.

Each OH emits a set of PFs based on the offered services, as shown in Figure 2. Briefly, Figure 2 is built by 3 OHs, mapping resources, namely OH 1 and OH 2 offer the service yellow (non-negative values) while OH 3 offers red and purple. The PF must be propagated accordingly with the transportation routes that are mapped in the figure by the thick straight arrow, e.g., it is possible to route from OH 1 to OH 2 . In such way, OH 2 back-propagates the yellow PF value to OH 1 , which then calculates its value reflected on it. The value on the final OH is calculated considering the distance to the emitting source OH, i.e. has farther the OH, the lower the PF is. Notice also that in this case, a propagation of the OH 2 PF value is also relayed back since it is possible to convey from OH 3 to OH 1 . The PF values are stored in the OHs using a blackboard system [START_REF] Engelmore | Blackboard systems[END_REF], represented as the black rectangles in Figure 2, being accessible to the holons that need to use them, e.g., THs searching for a processing resource. Additionally, the back-propagation of the PF value ends when the calculated value on the OH is lower than a pre-defined threshold. On the other side, the holons that require the execution of a given service, e.g., a TH that needs a processing task, will check in the current OH for the attractive fields of the next desired service. The selection of the OH that will perform the necessary service is selected by simply, chose the highest emitting field for the service.

Several resource parameters can be used to calculate the strength of each PF, namely the resource workload, the service processing times, the service quality and a scheduled maintenance.

where,  is the weight given to parameter P.  is the value of the parameter P.

In this way, every time a given considered parameter changes, the correspondent OH is responsible to re-calculate the strength of the PF, and to propagate it to its adjacent nodes (i.e. to its adjacent OHs).

Having this information spread over a set of OHs, the THs must then select the most appropriate OH. In this decisional phase, the TH will follow the maximum emitting PF value.

Although being a very simple, reliable and fast mechanism, the PF approach has a major drawback to be considered and that is related to its myopia. Note that from the point of view of the TH, it is only worthy to select the next processing task since if more tasks are allocated, the allocation assumptions for the subsequent tasks will dynamically change and are not therefore guaranteed in the processing execution moment.

As seen previously, two holons from the architecture are considered in the development of this mechanism, namely the OH and TH. These holons have well defined and independent roles in the process, where the OH is responsible for the generation and spread of the system conditions, whereas the TH is only concerned on monitoring and taking decisional actions, abstracting itself from the underlying process.

Validation of the behavioural self-organization

This section describes the use case used to validate the behavioural self-organization vector, particularly the system organization, the resources skills and the products catalogue. Additionally, the tests assumptions and results are also described.

The AIP-PRIMECA cell description

The FMS, depicted in Figure 3, is composed by 7 machines connected using a conveyor system. The rack conveyor system allows the parts needing processing operations to reach the desired machine using a transport shuttle. Each machine (from M 1 to M 7 ) offers a set of skills, needing a defined amount of time to complete the processing task, and the shuttles need to convey for different transportation times depending on the start and destination nodes [START_REF] Trentesaux | Benchmarking flexible job-shop scheduling and control systems[END_REF].

The system offers a catalogue of products, namely the BELT, AIP and LATE, that are composed by the appropriated set of sub-products, particularly the letters b, e, l, t, a, i and p. A visual perspective of the sub-products is given in Figure 4. To realize each sub-product, an assembly process must be followed, see Table 1. As an example, to produce the sub-product i, the assembly base plate must be loaded into the shuttle, followed by two axis components, one I and one Screw, followed by an inspection and ending with an unloading procedure. The decisional choices are then concerned with the appropriate machine selection, routing selection and product release order.

Validation scenarios

Several scenarios from the Bench4Star benchmark are used, namely those ranging from A0 to E0 [START_REF] Trentesaux | Benchmarking flexible job-shop scheduling and control systems[END_REF], allowing the test of different batch combinations, varying the batch products and number. In this work, all the scenarios have real transportations times and non-infinite transportation shuttles (note that these are neglected for some scenarios). Scenarios without and with disturbances are also considered, namely the #PS12 [START_REF] Trentesaux | Benchmarking flexible job-shop scheduling and control systems[END_REF] that introduces a 60s breakdown in M 2 at the end of processing of every 4 jobs.

10 Real #1 1 - - #2 - 1 - B0 10 Real #1 - 2 - C0 4 Real #1 1 - - #2 - 1 - D0 10 Real #1 1 - - #2 2 1 - E0 10 Real #1 2 1 - #2 - 2 1 #3 - - 2
Four manufacturing control architectures are compared in both situations, namely a fully hierarchical architecture, where a high level entity is always providing optimized schedule, a heterarchical architecture where entities are completely autonomous, and finally the ADACOR and ADACOR 2 approaches. Particularly, in the ADACOR 2 tests, the entities are allowed to switch between two different behaviours, namely between a market-based, following a Contract Net Protocol approach, and the Potential Field [START_REF] Barbosa | Self-Organized Holonic Multi-agent Manufacturing System: The Behavioural Perspective[END_REF].

Behavioural self-organization assessment

In order to provide a proper validation, each of the aforementioned architectures were simulated, considering each production scenarios, 30 times. Several KPIs, e.g., the C max , throughput and predictability, were extracted, providing a number of results that, after analysed, allow the assessment and validation of the control architectures. With the simulation results, statistical analysis was performed, namely average values and standard deviation were made. One of the most used KPI in manufacturing control is the C max that is a direct measure of the total time needed for the manufacturing control to produce a given amount of products. In such, and for simplicity reasons, this KPI will be used for the assessment of the behavioural part.

The first batch of simulations were conducted for scenarios where all parameters are well known and controlled, i.e. a system without disturbances. Experimental results for all the non-disturbance situations are shown in Figure 5.

As it can be seen, the hierarchical approach alongside with ADACOR and ADACOR 2 present the most optimized solution. This is explained by the fact that in these approaches, the SH is constantly introducing optimization schedules to the OHs, since everything is predictable and under control. The heterarchical approach presents the worst results since the THs are directly interacting with the OHs and in this way, myopic phenomena may appear. A system without disturbances is not realistic and not expected nowadays and so any manufacturing control architecture must be tested within these disturbance working conditions in order to assess its viability. In this way, the #PS12 scenario, as defined in [START_REF] Trentesaux | Benchmarking flexible job-shop scheduling and control systems[END_REF], is used. This disturbance scenario introduces a 60s malfunction in M 2 at every 4 th processing operation. The experimental results for the C max KPI are shown in Figure 6.

After analysing the graph, it is possible to observe that under these conditions, ADACOR 2 is the one that achieves a better performance, allowing to produce the same amount of work in less time, i.e. providing a lower C max . Additionally, and as already shown in [START_REF] Leitão | ADACOR: A Holonic Architecture for Agile and Adaptive Manufacturing Control[END_REF] the ADACOR control architecture surpasses the hierarchical and heterarchical control solutions. Quantitatively, the ADACOR 2 control architecture is able to reduce, on average, the C max by 91s for the production scenario A0, 23s for C0 and 15s for E0. The apparent margin improvement decrease, as the batch size increases, seems counterproductive and is explained by the behavioural parameter adjustment. It is expected that with a proper selection and fine-tune of the selected behaviour parameters will improve these KPIs. It is worthy to note that a parameter adjustment was not performed during the simulation tests, despite the change of the working conditions for the different scenarios, e.g., the number of shuttles being able to transport the. Additionally, the AIP-PRIMECA FMS cell configuration may have harder freedom limits when a high congestion production appears, decreasing the improvement rate.

An impact assessment can be conducted, see Figure 7, foreseeing the performance degradation of the manufacturing control strategies when disturbances are introduced. Expectably, the heterarchical approach is the one that suffers less impact due to the disturbance introduction. As commonly known, in completely heterarchical structures, the entities react locally to the disturbances, making them more responsiveness. On the opposite side, the hierarchical approach, due to the higher amount of time that the superior entity needs to re-compute an optimal plan, has the worst performance impact. ADACOR and ADACOR 2 suffer impact levels between those bounds and have good impact performance indexes. ADACOR 2 has a gain over ADACOR, meaning that the dynamic selection of behaviour, in reaction to disturbances, helped to a decrease of the overall system impact.

Globally, and as it is possible to conclude, the ADACOR 2 manufacturing control architecture is the one that best perform under the full range of production scenarios.

Conclusions

The current manufacturing world is demanding for innovative control architectures that are able to constantly adapt to the daily constraints. To achieve this, holonic prin-ciples implemented using agent technology is a good candidate to address those constraints. Despite of the good results, there is still the need to further enhance those architectures, particularly allowing them to evolve alongside with the disturbances.

The ADACOR 2 manufacturing architecture combines the holonic design principles, it uses the agent based technology and empowers this combination with bio-inspired mechanism, namely self-organization principles. In fact, ADACOR 2 proposes to act at two distinct levels as the way to address different disturbances that may appear.

This paper addresses the behavioural vector, acting at the holons internal level, and assess and validates this approach by means of use of a benchmark. Results have shown that using these principles, ADACOR 2 is able to achieve better results than a hierarchical, heterarchical and the ADACOR control architecture.

Future work, related to this, will be devoted to the development of different behavioural mechanisms and the test in different production system configurations.

Figure 2 -

 2 Figure 2 -Potential Field concept

Figure 3 -

 3 Figure 3 -The AIP-PRIMECA cell layout

Figure 4 -

 4 Figure 4 -Sub-products representation

Figure 5 -

 5 Figure 5 -Cmax for non-disturbance scenarios

Figure 6 -

 6 Figure 6 -Cmax for disturbance scenarios

Figure 7 -

 7 Figure 7 -Impact of the disturbance occurrence

Table 1 -Products processing sequence

 1

	Oper	B	E	L	T	A	I	P
	#1	Loading	Loading	Loading	Loading	Loading	Loading	Loading
	#2	Axis	Axis	Axis	Axis	Axis	Axis	Axis
	#3	Axis	Axis	Axis	Axis	Axis	Axis	Axis
	#4	Axis	Axis	Axis	Rcomp	Axis	Icomp	Rcomp
	#5	Rcomp	Rcomp	Icomp	Lcomp	Rcomp	Screw	Lcomp
	#6	Rcomp	Rcomp	Icomp	Inspection	Lcomp	Inspection	Inspection
	#7	Icomp	Lcomp	Screw	Unloading	Icomp	Unloading	Unloading
	#8	Screw	Inspection	Screw		Screw
	#9	Inspection	Unloading	Inspection		Inspection
	#10	Unloading		Unloading		Unloading

Table 2 -Production scenarios (adapted from [16])

 2

	Number of shuttles	Transportation times	Order #	BELT	Products AIP	LATE
	A0


Mickael Guironnet
email: guironnet@lis.inpg.fr

Nathalie Guyader
email: nguyader@yahoo.fr

Denis Pellerin
email: pellerin@lis.inpg.fr

Patricia Ladret
email: ladret@lis.inpg.fr

Spatio-temporal Attention Model for Video Content Analysis

This paper presents a new model of human attention that allows salient areas to be extracted from video frames. As automatic understanding of video semantic content is still far from being achieved, attention model tends to mimic the focus of the human visual system. Most existing approaches extract the saliency of images in order to be used in multiple applications but they are not compared to human perception.

The model described here is achieved by the fusion of a static model inspired by the human system and a model of moving object detection. The static model is divided into two steps: a "retinal" filtering followed by a "cortical" decomposition. The moving object detection is carried out by a compensation of camera motion. Then we compare the attention model output for different videos with human judgment. A psychophysical experiment is proposed to compare the model with visual human perception and to validate it. The experimental results indicate that the model achieves about 88% of precision. This shows the usefulness of the scheme and its potential in future applications.

I. INTRODUCTION

The quantity of audiovisual information has increased with the arrival of Internet and digital television. The need to analyze video semantic content has appeared to serve in many applications: video summary, video browsing, and video retrieval... Automatic understanding of semantic content is still far from being achieved in spite of the significant advances of computer vision and image processing.

Attention models have been introduced to solve the limits of current algorithms. Without understanding the full video content, attention models tend to capture the focus of the visual human system. Attention is a neurobiological concept that represents the capacity of humans to concentrate and focus on things such as a single object, a landscape. . . Thus, the understanding of attention processes should facilitate scene analysis and help video content analysis by reducing the number of objects or area to be analysed.

The first attention model was proposed by Koch and Ullman [START_REF] Koch | Shifts in selective visual attention: Towards the underlying neural circuitry[END_REF] in 1985. Then, Itti et al. [START_REF] Itti | Target detection using saliency-based attention[END_REF] defined a visual attention map, which is the combination of different maps dedicated to different low level features (orientation, intensity and colour). Other authors, inspired by the human visual system, created more elaborated models. Chauvin et al. [START_REF] Chauvin | Natural scene perception: visual attractors and image processing[END_REF] proposed a model inspired by the retina and the primary visual cortex cell functionalities. Then, attention was introduced into videos to try to fill the semantic gap. The methods also tried to exploit the temporal component. Ma et al. [START_REF] Ma | A user attention model for video summarization[END_REF] defined a user attention model based on a motion vector field extracted from MPEG stream. This approach was used for video skimming. New systems appeared by combining maps of static and dynamic visual attention. Bollmann et al. [START_REF] Bollmann | Integration of static and dynamic scene features guiding visual attention[END_REF] introduced the detection of moving objects to the static features (symmetry, orientation and color analysis). Ho et al [START_REF] Ho | A user-attention based focus detection framework and its application[END_REF] presented an attention model based on three levels of features: low level (intensity and color), medium level (motion) and high level (face detection). The attention model defined in [START_REF] Courty | A new application for saliency maps: Synthetic vision of autonomous actors[END_REF] aimed at simulating eye saccades. Two applications were considered: virtual humanoid perception and automatic video surveillance. In [START_REF] Chen | Image adaptation based on attention model for small form factor devices[END_REF], the authors proposed an attention model based on many visual features (color, orientation and intensity) but also on face and text detection for adapting image size. In general, these models are not compared to human perception. They are directly used through various applications like video summarization, encoding, watermarking or surveillance.

This article presents a new visual attention model. It relies on the fusion of a static model inspired by the human system and a model of moving object detection in a scene. The static model is based on retinal filtering followed by a bank of Gabor filters. The moving object detection is carried out by compensation for camera motion. Once the visual spatiotemporal attention model was built, a psychophysical experiment allowed us to validate the proposed model. The main contributions of our work are a new user attention model and the building of an experiment to judge the effectiveness of the method.

II. ATTENTION MODEL

In this section, we describe our attention model. This model extracts the salient areas from videos. It is divided into two parts: a static and a dynamic one.

A. Static part of the model

This part is inspired by biology and functionalities of human visual system cells (from the retina to the primary visual cortex). This part of the model concerns each frame of the videos.

Retinal filtering

At the first level of information processing, the retinal photoreceptors carry out an adaptive compression process followed by high-pass filtering [START_REF] Beaudot | Sensory coding in the vertebrate retina: towards an adaptive control of visual sensitivity[END_REF]. This results in contrast equalization of the image, providing a relative insensitivity to local illumination variations. This pre-processing is interesting for extracting saliency because it is invariable to some modifications, such as luminance variations between images. Then, the parvocellular pathway provides a spatial high-pass filter (known to whiten an image's frequency spectrum) that compensates for the 1/f image amplitude spectrum.

Primary visual cortex

Primary visual cortex cells are sensitive to visual signal orientations and spatial frequencies. Here, we chose to model simple cell receptive fields. These cells are sensitive to stimuli having a certain orientation and a certain frequency with a specific position in the visual field, which is modelled by a two-dimensional Gabor filter. A Gabor function is defined by a gaussian with spatial extents σ x and σ y modulated by a complex exponential with frequency f in a direction θ. We carried out this filtering by directly multiplying the retina output image with the Gabor filter in the Fourier domain. Before achieving the Fourier transform, we multiplied the image by a Hanning window to remove edge effects. We chose here to decompose each image of the video using thirty-two Gabor filters (four different spatial frequencies and eight different orientations). So, we obtained thirty-two maps (thirty-two images), depending on the frequency and the orientation of the original image, for each frame of the video.

Interactions

A neuron is, by definition, a contact cell. Thus, the response of a cell is always dependant on a neuronal environment. Then, the neuron's activity is modeled by the visual field neighborhood and so is dependent on lateral connections. With regard to the orientations, the computed interactions preferentially connect neurons devoted to the same orientation. These interactions, which symbolize both excitatory and inhibitory connections, are modeled by a linear combination of the simple cells (fig 1):

E int (f i , θ j ) = k,l w k,l • E(f i+k , θ j+l ), w =   0 -0.5 0 0.5 1 0.5 0 -0.5 0   (1)
Figure 1 illustrates the interactions. In this example, the Gabor filter with weight 1 in direction π/4 interacts with its neighbours. The Gabor filters with the same direction symbolize excitatory and those with different directions represent inhibitory.

The output of this stage is composed of 32 maps for each image of a video. These maps put into relief the image energy in function of the spatial frequency and the orientation of the signal in the original image and take into account the interaction between the orientation maps.

Static saliency map

We extract a static saliency map for each image as the sum of the 32 energy maps described above:

E f = i,j E int (f i , θ j ) (2)
The regions having the highest energy are considered to be salient. Figure 2 shows examples of static saliency maps. The content of the images is rather varied: a rugby match, a car chase and a bicycle race. We can observe on the bottom row that the energy is located on objects which seem to be salient.

B. Dynamic part of the model

The dynamic part of the model detects the moving objects in a scene. In fact, we assume that the location where something moves is salient. Next, it is necessary to estimate camera motion. We use the 2D motion estimation algorithm developed in [START_REF] Odobez | Robust multiresolution estimation of parametric motion models in complex image sequences[END_REF]. This algorithm provides the dominant motion between two successive frames. A 2D parametric motion model between two successive frames is then defined and a robust multiresolution estimation of parametric motion models is carried out. We chose affine motion model to represent the camera motion.

v x = a 1 + a 2 • x + a 3 • y v y = a 4 + a 5 • x + a 6 • y (3)
Once we had the coefficients [a 1 , ..., a 6 ], we computed the motion compensated frame. Compensation of camera motion was formed by bilinear interpolation I c (x, y, t + 1) = I(x + v x , y +v y , t+1). The previous frame was then subtracted from the motion compensated frame to generate Displaced Frame Difference (DFD):

DF D(x, y, t) = I c (x, y, t + 1) -I(x, y, t)

Finally, the absolute value of DFD informs about regions that do not follow camera model and corresponds to displacement of objects. Figure 3 shows examples of object detection. We can see that the rugby players are correctly detected as well as the cars and the cyclists.

C. Spatio-temporal attention model

Before dealing with map fusion, it is necessary to carry out a temporal filtering of each map. Indeed, the maps are computed locally, either on one frame (for the static model) or on two successive frames (for dynamic model), and the salient regions must be temporally coherent inside a window of duration L. The temporal continuity of the video prevents the appearance of salient areas on one or two images only (two frames correspond to 2/25 = 0.08s). This is why a median filtering of width L is carried out. In our experiment, the size of window L equals five frames. Since the maps do not have the same magnitude, a standardization stage is necessary before carrying out the map fusion. This stage is carried out by the following:

S n = S/T h if S < T h 1 if S ≥ T h ( 5
)
where S is a static or dynamic saliency map and T h is a predefined threshold (25 in the two cases).

Once the maps have been normalized, a fusion stage is achieved to combine all maps into a final saliency map. The fusion is performed using the max operator which can be interpreted as an "or" logical operator. Thus, the final map contains static and dynamic information. Finally, the map obtained is a gray image with a higher value for salient zones.

Thanks to image processing techniques, we detect the regions of attention. The following steps are achieved: thresholding, morphological operation (close and open), region selection. In the last step, we determine the regions according to 4-connected neighbourhood. The regions with area lower than a threshold are removed. Finally, the remaining regions are selected and defined as masks. If the number of masks is greater than five, we keep only the five biggest masks. Figure 4 illustrates the fusion of maps and the selection of attention masks: the cars, crowd and players, and the cyclists.

III. EXPERIMENTAL RESULTS

In order to test and to validate our model, we carried out a psychophysical experiment. The goal of the experiment was to know if the areas defined as salient by the model are indeed salient. We tried to compare the model with human perception.

A. Method Subjects

Sixteen naive subjects underwent the experiment. All subjects had normal or corrected to normal vision.

Stimuli

The subjects saw nine different videos displayed in the middle of the screen with a frequency of 25 images per second. Videos were composed of 288x352 pixel-images in 256 gray-levels. For one randomly selected image of one video, we associate to it the spatio-temporal attention map using the presented model. In order to test if the salient areas provided by the model are in agreement with the human visual perception we take exactly the same image and the same masks but we apply the masks to random positions as shown in figure 5. The principle is as follows: the mask of model having highest area is first randomly moved in the image; the second mask having highest area is then moved but without possible overlapping with the other mask and so on... Finally the two images (fig 5) have the same masks but at different places in the image.

Procedure

The experiment was processed with a computer with a Pentium III processor. The stimuli were presented on a 21" screen (Mitsubishi Diamond Pro2020u) with a resolution of 1024 by 768 pixels and a frame rate of 100 Hz. Subjects were placed at a distance of approximately 50 cm from the screen. Figure 6 describes the events for one trial: a fixation point appeared (here a small black cross) in the middle of the screen for two seconds, followed by a 1.2s video still in the middle of the screen. Then, two images were presented symmetrically in the middle of the screen. These images belonged to the previous video and were masked in different ways: one following the model and the other with random position masks. The subject had to choose which one seemed to him to be the closest to the video. The selected image should have represented the best video content. His response and the reaction time were measured with a response box and E-Prime software. His answer had to be given as quickly as possible.

Each video appeared four times, with two different target images in the two possible positions on the screen. So in two cases the same images are used and in one case the image provided by the model is on the right side of the screen and in the other case is on the left. This allows us to have more answers for one condition and to see if a subject gave his answer randomly. The experiment is divided into three phases. Each phase contains three videos and so twelve random trials. During one experiment, each subject answered 36 trials.

B. Results

For the analysis we only kept fourteen subjects (two subjects had random responses). We measured the percentage of correct responses per subject (the correct response is in the case where the subject chose the model mask). Over all subjects the mean correct response percentage is 88% with a mean standard deviation of 5%. As we expected, for all subjects the model masks correspond more to the video than the random masks.

We can refine these results. For some masks there is an overlapping between the model masks and the random ones. So we should find fewer correct answers when the model masks are overlapped with random masks rather than when the masks are separated. So we added a condition: when masks had more than 50% of overlapping and when masks had less than 50% of overlapping. We made an analysis of variance (ANOVA) for the percentage of correct response as a function of these two conditions. The overlapping influences the correct response (F (1, 13) < 0.001). So the percentage of correct responses is lower when the model masks and the random masks are overlapped, which consolidates the model.

IV. CONCLUSION

We have presented a spatio-temporal attention model. It relies on the fusion of a static model inspired by the human system with a model of moving object detection. A psychophysical experiment was proposed to judge the effectiveness of the model. The proposed model provides good results with a precision of 88%. These results are promising.

In addition, the model can be used in many applications such as video indexing, summarization, watermarking and surveillance. One of the future works would be to use this model to provide a video summary and to use an experimental paradigm to test the efficiency of the method.

Fig. 1 .

 1 Fig. 1. Example of interactions. The Gabor filter with weight 1 in direction π/4 interacts with its neighbours.

Fig. 2 .

 2 Fig. 2. Examples of static attention maps. Top row: video frame. Bottom row: the associated static attention map.

Fig. 3 .

 3 Fig. 3. Examples of moving object detection. Images represent the absolute value of Displaced Frame Difference.

Fig. 4 .

 4 Fig. 4. Examples of spatio-temporal attention masks.

Fig. 5 .

 5 Fig. 5. Example of the target images. The left image is the output of the presented model. The right one is the same image with the same masks but placed in random positions.

Fig. 6 .

 6 Fig.6. Experimental design: one trial sequence is illustrated. First, a video appeared for 1.2s, and then two images appeared in the middle of the screen. The task was to choose the image that is closest to the video.

ACKNOWLEDGMENT The authors would like to thank Christian Marendaz (Laboratoire de Psychologie et NeuroCognition, Grenoble, France) for having received us and let us use the material for the experiments. The authors also thank the Vista Research team at Irisa/Inria Rennes for the use of the Motion2D software.