Jérôme Durand-Lose
email: jerome.durand-lose@univ-orleans.fr

Abstract geometrical computation 5: embedding computable analysis

Keywords: Analog computation, Abstract geometrical computation, Computable analysis, Signal machine, Type-2 Turing machine

come

Dealing with real values is handled in various ways: fixed approximation (π is 3.14), formal manipulation (π is PI), unbounded approximation on demand (π is a program that provide extra digits on demand), interval arithmetics (π is [3.1, 3.2]). . . Following their definition as Cauchy sequences of rational numbers, real numbers can be encoded by infinite decreasing sequences of intervals with rational endpoints, such that the length of the intervals tends to zero. The whole infinite sequence represents exactly one real (at its intersection), but a finite prefix of the sequence is enough to get an approximation; the larger the prefix, the better the approximation. Rational endpoints allow exact coding and manipulation of each interval in classical computation, so that the infinite sequence of intervals can be written as an infinite sequence of symbols. Functions over these infinite sequences could represent functions on the reals. A Turing machine is used: the infinite entry is written on a read-once tape and the infinite output is expected on a write-once tape (extra working tapes are available). These tapes can be seen as input and output streams. To entirely process the input and generate the whole output, an infinite number of iterations is needed, but in finitely many steps an approximation of the result is generated.

This approach, now called Computable Analysis (CA) was initiated by [START_REF] Turing | On computable numbers, with an application to the entscheidungsproblem[END_REF], then [START_REF] Grzegorczyk | On the definitions of computable real continuous functions[END_REF] and is detailed in classical textbooks [START_REF] Ko | Computational Complexity of Real Functions[END_REF][START_REF] Weihrauch | Introduction to computable analysis[END_REF]. It has been proven equivalent to a variation of Shannon's General Purpose Analog Computer [START_REF] Bournez | Polynomial differential equations compute all real computable functions on computable compact intervals[END_REF].

In the present paper, Abstract Geometrical Computation (AGC) is proven capable to carry out any CA computation with a representation of real numbers with finitely many signals. This representation is compatible with the one used to implement the original Blum, Shub and Smale (BSS) model [START_REF] Durand-Lose | Abstract geometrical computation and the linear Blum[END_REF][START_REF] Durand-Lose | Abstract geometrical computation with accumulations: Beyond the Blum, Shub and Smale model[END_REF] (a different approach to analog computing: values and primitives are freely available [START_REF] Blum | On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines[END_REF]).

Abstract geometrical computation is defined by dimensionless signals moving uniformly in an Euclidean (continuous) space in continuous time. To each signal corresponds a meta-signal which defines its speed. The number of meta-signals is finite. Existing signals are only modified when they collide: they are replaced by new signals according to their meta-signals and collision rules. A signal machine collects the definition of available meta-signals and collision rules.

In [START_REF] Durand-Lose | Abstract geometrical computation and the linear Blum[END_REF][START_REF] Durand-Lose | Abstract geometrical computation with accumulations: Beyond the Blum, Shub and Smale model[END_REF], to implement the BSS-model, real numbers are encoded by the distance between two parallel signals (plus two more signals to encode the scale, i.e. distance 1). On one side, for CA, this is not so convenient since infinite sequences are expected. On the other side, in the AGC context, infinitely many signals would either occupy the whole infinite space or produce accumulation of signals (and maybe collisions), both are problematic.

Stoking infinitely many signals in a bounded space is a very complex yet powerful feature (fore example, with the use of folding structures, exact multiplication of real numbers was achieve [START_REF] Durand-Lose | Abstract geometrical computation with accumulations: Beyond the Blum, Shub and Smale model[END_REF]). Special care has to be taken in defining the space-time diagram near them. The only scheme used here is that any singularity reduced to a point in the spacetime diagram results in one signal (always the same). More complex rules can be devised to handle accumulations -unused here-so as to emulate the (nested) black hole model of computation [START_REF] Hogarth | Non-Turing computers and non-Turing computability[END_REF][START_REF] Etesi | Non-Turing computations via Malament-Hogarth spacetimes[END_REF][START_REF] Durand-Lose | Abstract geometrical computation 1: Embedding black hole computations with rational numbers[END_REF], 2009a].

To avoid handling infinitely many signals, a mixed representation is used. A real number x is encoded by n + ε where n is an integer and -1 < ε < 1; n is encoded in signed binary and ε as a distance between two signals (a pair of signals somewhere in the configuration amounts for distance 1). The encoding used for CA implementation is signed binary with symbols 1, 0, 1 plus a decimal point. To go back and forth between the encodings, n is encoded as a sequence of signed bits (and thus does not have to be taken care of) and the first approximation is (n-1, n+1). Then the approximation goes by steps: the interval (a, b) is replaced by (a, a+b 2 ), ( 3a+b 4 , a+3b 4 ) and ( a+b 2 , b) that corresponds to 1, 0 and 1 respectively. (Intervals overlap and the infinite sequence is not unique.) The geometric construction to generate from the decimal part an infinite sequence corresponding to the real number relies on five signals amounting for values -1 2 n , -1 2 n+1 , 0, 1 2 n+1 and 1 2 n . The position of ε gives the signed bit, ε is reduced while the five-signal structure is scaled down.

The presentation of the implementation of (classical) Turing machines (TM) is only illustrated; it is quite straightforward and already done in [Durand-Lose, 2009a[START_REF] Durand-Lose | Abstract geometrical computation 4: small Turing universal signal machines[END_REF]. A Type-2 TM needs infinitely many iterations to complete a computation. To get the results in finite duration, TM and input are embedded into a folding structure as in [START_REF] Durand-Lose | Abstract geometrical computation 1: Embedding black hole computations with rational numbers[END_REF], 2009a].

In Durand-Lose [2009b], a convoy is defined and used to bring the infinite output to a structure that bring forth better and better approximations and at the limit the exact number. This is not needed here anymore: the shrinking structure is itself embedded into another shrinking structure that accumulates at the exact location of the output. Theses shrinking structures are called, respectively, inner and outer. The inner one stops each time a signed bit is output. On receiving this bit, the outer structure makes one shrinking operation on the left, central or right half depending on the value of the bit. Then some acknowledgement signal is sent to resume the inner structure shrinking and the T2-TM computation.

Another way to express this it to say that the TM is accelerated until a signed bit is output then it is stopped until the bit is proceeded, then the process starts again. The computation providing the bits is embedded inside the structure that accumulates on the exact output. (The inner structure been stopped and translated, it accumulates at the same location).

Definitions of AGC and CA are gathered in Section 2. Section 3 concentrates on approximation, i.e. the mixed representation as well as how to get bits, and the simulation of type-2 Turing machines. Section 4 deals with exact computation in finite duration. Section 5 concludes this paper.

Definitions

Abstract geometrical computation

A signal machine (SM) is defined by (M, S, R) where M (meta-signals) is a finite set, S (speeds) a mapping from M to R, and R (collision rules) a function from the subsets of M of cardinality at least two into subsets of M (all these sets are composed of meta-signals of distinct speeds). A signal machine is extended if some meta-signal µ ✺ is distinguished to be used as the result of an isolated accumulation.

Each instance of a meta-signal is a signal located on the real axis. The mapping S assigns speeds to signals. A collision rule, ρ -→ρ + , defines what emerges (ρ + ⊆ M ) from the collision of two or more signals (ρ -⊆ M ). Since R is a function, SM are deterministic. The extended value set, V , is the union of M and R plus two special values: ⊘ for void, ✺ for isolated accumulation.

A (finite) configuration, c, is a mapping from R to M ∪ R ∪ {⊘} such that the set { x ∈ R | c(x) = ⊘ } is finite. An extended (finite) configuration, is a mapping from R to V such that the set { x ∈ R | c(x) = ⊘, ✺ } is finite.
A (resp. extended) space-time diagram is a mapping from an interval of R (representing the time) into (resp. extended) configurations. A signal corresponding to a meta-signal µ at a position x, i.e. c(x) = µ, is moving uniformly with constant speed S(µ). A signal must start (resp. end) in the initial (resp. final) configuration or in a collision. At a ρ -→ρ + collision, signals corresponding to the meta-signals in ρ -(resp. ρ + ) must end (resp. start) and no other signal should be present. There is a ✺ if and only if collisions are accumulating and it is isolated in the configuration (i.e. at the time it exists). A ✺ immediately turns into a (regular) µ ✺ signal, so that a µ ✺ signal can also result from an accumulation.

Space-time diagrams are represented with time increasing upward. The traces of signals are line segments whose directions are defined by (S(.), 1) (1 is the temporal coordinate) so that the speed is the inverse of the slope. Collisions correspond to the common extremities of these segments.

Computable Analysis

A type-2 Turing machine (T2-TM) is a regular Turing machine (TM) such that the entry is an infinite sequence of symbols written on a read-only tape. The output is also expected to be an infinite sequence of symbols written on a write once tape. The TM has an extra work tape on which it can freely read and write. It needs infinitely many iterations to read a whole entry and write the whole result. These read-once and write-once tapes are treated as input and output streams. After finitely many iterations, a finite part of the entry is read and a finite part of the result is generated; they represent approximation of the entry and the result. Since the output is write-once, anything written never changes and it converges to the infinite output according to the prefix topology.

To link this machinery to analysis, a representation of real numbers by infinite sequences should be provided. The larger the prefix of the representation is read, the more should be known on the encoded real number x, ultimately x should be perfectly known and distinguished from any other real number. The standard representation of a real number x is by any decreasing sequence of intervals with rational ends such that their intersection reduces to {x}. The infinite sequence is then just the self-delimiting concatenation of the naming of the intervals. In the present paper, an equivalent representation is used.

Let Σ = {•, 1, 0, 1}, the signed binary representation, ρ sb :⊆ Σ ω -→ R, (from [Weihrauch, 2000, Def. 7.2.4 p. 206]) is defined only for infinite sequences with exactly one dot (•) by:

w 0 •d 1 d 2 d 3 . . . d n . . . -→ ν sb (w 0 ) + 1≤i d i 2 i
where w 0 ∈ {1, 0, 1} * , d i ∈ {1, 0, 1} and ν sb is a naming of natural integers signed in base 2 (1 stands for -1).

Each real number is represented by infinitely many sequences. Computing from different representations of x might produce different sequences, but since CA defines functions over R, these should represent the same real number y.

Approximation

This section deals with finite run of type-2 Turing machines. After defining the mixed representation of real numbers and the extraction of signed bits, T2-TM implementation is presented.

Mixed representation and decoding

Each real number can be decomposed as n + ε where n is an integer and ε belongs to (-1, 1). The representation used in AGC is in two parts. The integer n is encoded as a sequence of signals in {1, 0, 1} followed by a • signal. This is a direct signed binary representation. The real number ε is represented in AGC, by the distance between two signals (there exist two signals somewhere representing the scale, i.e. their distance is 1).

The aim is now to extract an infinite sequence of signed bits (plus a •) encoding the real. Each query for a signed bit is started by receiving a get signal. The integral part is treated very simply: the first signal encountered get transformed into 1 R , 0 R or 1 R . The dot is treated similarly. The integral part is not addressed anymore in this paper.

The two signals to represent ε are zero and e. More signals are present: one, half, half and one at position respectively -1, -1 2 , 1 2 and 1 (position 0 is the one of zero). Signal e is between the two one signals, it might be superposed with half or zero, in such a case a different meta-signal is used (these special cases are omitted).

Signed bits are extracted one after the other and companion signals are prepared for next extraction: one, half, half and one are scaled by one half and e is translated in order to correspond to the remainder. The structure on Fig. 1 The Figure 1 presents all the basic ingredients in AGC. A lot of insights on this first construction is provided in order to illustrate how AGC works. In the following, meta-signals are not listed and collisions rules are not listed, all has been implanted and the reader should be able to name signals, deduce rules and prove the correction of the constructions.

On this figure, it can first be proved that starting with one, half, zero, half and one at position -4x, 2x, 0, 2x and 4x (x is any positive real number) and get coming from the right. At the end there should only be present one, half, zero, half and one at position -2x, x, 0, x and 2x. Looking at the speeds and collision rules, everything happens according to the picture. Since the new one signals replace the old half, they are directly correctly positioned. Let's take time 0 at the collision half with get + . The collision of zero and get 0 happens at (0, 2x) since get 0 has speed -1. Computing the intersection of two lines, the (right) collision of half R and half L happens at (x, 3x).

The three cases of bit extraction are represented on Fig. 2 where the signals handling ε, e is drawn with dashed lines. If -1 < ε < -1 2 n then the extracted bit is 1 (signal 1 L exits on the left) and ε is replaced by ε + 1 2 n (e is shifted by the distance from one to half). If -1 2 n < ε < 1 2 n then the extracted bit is 0 (signal 0 L ) and ε is kept (e is not shifted). Except for the geometric construction, the last case is symmetric to the first one. Arbitrarily, if -1 2 < x < 0, then the extracted bit is 0 although it could have been 1 (similarly for 0 < x < 1 2 ).

e e 1 R (a) -1 < ε < -1 2 e e 0 R (b) -1 2 < ε < 1 2 e e 1 R (c) 1 2 < ε < 1
Fig. 2 Extracting a single signed bit.

For bit extraction, get comes from the right and is subsequently transformed into get + (on meeting the first one) then get 0 (on the first half) then get -(on the second half). According to what signal meets e, 1, 0 or 1 is send back. If e is between the two half (Fig. 2(b)), it remains is position which is correct. If e is on the left between one and half (Fig. 2(a)), then it is set parallel to half R (they have the same speed). It get set into position by set, since set and get -are parallel, the displacement of e is exactly the same as the one of half R from the initial half to the zero where set is generated. If e is on the right between half and one (Fig. 2(c)), the construction is basically the same.

All the meta-signals and rules are not detailed in the paper. The corrections of the various constructions rely on simple geometry. All have been checked (and implemented in Java to generate the pictures).

Computable Analysis

A type-2 Turing machine is nothing but a regular TM that never halts together with two special purpose tapes: one initially totally filled -entryand one for writing once -result. On the entry tape, the head cannot change the read symbol nor move left (i.e. back to the start). On the result tape, the head either rewrites the blank symbol or moves right. In the transition table, transitions that read on the entry can be clearly identified. Reading is replaced by sending a get signal to the mixed structure and waiting for the signed bit. The same is done with writing, in this case, signals encoding signed bits are sent on the side but no acknowledge/returned value is expected (in this subsection).

Implementing a TM in AGC has already been done in Durand-Lose [2009a]. Read and write operations are carried out by signals sent on the side. Reading sent a get to the left and wait for an answer. Since the T2-TM is running for infinitely many iterations, the tape might be extended infinitely, car is taken that the space used for the tape remains bounded. Since space is continuous, it is pretty easy to put less and less space between signals amounting for the cells of the tape. Indeed, a geometric decrease is used so that each signal is two third of the distance from the last than the distance from the last to the previous one. This is illustrated on Fig. 3 with the first iterations of a TM and its implementation.

Figure 1 provides the definition of a type-2 Turing machine that is used to exemplify the construction. The regular transitions are as usual. The other two (reading a bit of the entry or writing a bit of the result) are done without moving the head nor changing the value under the head. The table reads as follows: q 2 !0 means that the next state is q 2 and 0 is written on the result tape and ?1 : q i . . . ?1 : q 2 means that a symbol should be queried if it is 1 then the next state is q i . . . if 1 is read then the next state is q 2 .

\ symbol 1 0 1 # qi qi,0,→ qi,1,→ qi,1,→ ?1 : q1 ?0 : q2 ?1 : q3 q1 - - - qi!1 q2 - - - qi!0 q3 - - - qi!1
This T2-TM goes right, inverting 1 and 0 and then queries the entry and output the same bit on and on. The simulation of the TM on Fig. 3(b) has three regular transitions then it enters a cycle of read in and write out. On Fig. 3(c), on the left is the structure holding the entry and on the right the simulation of the machine.

While the entry is queried, the state is encoded together with the letter on the tape as indicated on the upper part of Fig. 3(b). This way the position of the head is also indicated by the only such meta-signal. The write out signals are the ones leaving on the right. Each time a symbol is queries or send to the result, the signal encoding the state bounced on the signal directly on the right; this separated transitions which is necessary when symbols are outputted directly one after the other. The first transitions are displayed on Fig. 3(b).

These signals might go accumulating if the head is moving right forever. But in a proper CA-computation, it is not the case: there must be infinitely many readings and each one needs signals to go forth and back from the tape to the mixed structure. Since this distance is bounded away from zero, each reading requires a minimal time. There is no accumulation whatsoever in a proper CA-computation. A bounded space is used by the T2-TM simulation and the encoded real number. There is always finitely many signals in any configuration.

1 0 1 # q i 0 0 1 # q i 0 1 1 # q i 0 1 1 # q i 1 → 0 1 1 # q 3 →1 0 1 1 # q i 0 → 0 1 1 # q 2 →0 0 1 1 # q i 0 → (a) TM computation 1 ← - q i -→ q i 0 -→ q i 1 -→ q i # 1 g e t
In case of multiple entries (for example for an addition), it is easy to set one after the other on the right and to have a distinct get for each entry.

Exact computation

Folding and extended signal machines

Except for the output signals, the T2-TM simulation and the entry use a bounded portion of space during the whole computation. There exist constructions to fold into bounded space and time a spatially bounded infinite time computation. These can be used to fold the computation without interfering with the output signals (by running through the collision rules and cancelling any action that the folding structure would have on them, they become insensible to the folding). Inside the structure, the computation is scaled down, generating an infinite acceleration (used to emulate the black hole in Durand-Lose [2006, 2009a]). In finite time, the whole infinite output is generated and exits the structure as displayed on Fig. 9.

Inside the folding structure, the Turing machine has an infinite time ahead of it. The structure preserves ratios in the understanding that there are infinitely many pieces at different scales that reform the original spacetime diagram after rescaling, unbending and translating. Even though the mixed representation undergoes multiple rescaling, it still generates the same infinite sequence, and the T2-TM the same result.

The problem is then to deal with the output: infinitely many signals are generated in a bounded space, so that accumulation of signals have to be considered. In Durand-Lose [2009b], this was considered and convoy were introduced. We provide a construction avoiding that. The shrinking structure is embedded inside another one that will accumulate. (From now these structures are respectively designed as outer and inner.) The signals outputted from the inner are used to drive the outer structures so that it accumulates at the right place.

Inner structure

This first structure accelerates (shrinking) until a signal is eventually outputted. The is then frozen and only remains null speed signals (until they are unfrozen).

First the T2-TM is modified in order that writing is freezing the computation. Instead of the bouncing signal, the state and the read symbol are encoded together, waiting for some writing acknowledgement. This functions exactly as in the read case above, except that it is not restarted by a read bit signal but by a o write-done signal. So that when a bit is outputted, the signals encoding the T2-TM are all parallel. This is described in Fig. 4(a).

The real-number representation and T2-TM simulation are embedded in the inner shrinking structure as displayed on Fig. 4(b). As presented alone on Fig. 4(c), this structure is defined by 5 meta-signals: i border le , i scale hi , i scale lo , i back and i border ri and three collision rules. (The prefix i denotes meta-signals from the inner structure). An extra meta-signal, i start, is used to start shrinking from just i border le and i border ri . In the inner shrinking, the computation is displayed bent in triangles delimited i scale lo , i scale hi and i back and unbent (but scaled!) everywhere else. Please note that the computation is going on from one piece to the next and remains between i border le on the left and a succession of i border ri and i back on the right. The bending is done by replacing signals by bent signals.

Crossing i scale lo , each signal is replaced by a signal such that the directions (i.e. speeds) undergo a linear transformation corresponding to factor 1 on i scale lo (ensuring correct transition) and factor 1 2 on i scale hi . Crossing i scale hi , a (bent) signal is replaced by its unbent version. This result in applying the linear transformation corresponding to the same directions but exchanged factors. After being unbend, the combined linear transformation is factor 1 2 on both directions. The scaling is thus achieved. To stop the inner structure and be able to restart it, it suffices to remove all but i border le and i border ri . This is done by changing the collision rules so that the signal corresponding to a symbol output is not only unaffected by the structure but also affects it. If it is generated in the unbent zone, it crosses unaffected by the bending, turn i back to i back F and/or i border ri to i border F ri . As can be seen on Fig. 5, each case results in only two motionless signals: i border le on the left and i border ri or i border F ri on the right. Rules are changes so that the output signal is always generated unbent (this explains why it is not the bent version on the right diagram of Fig. 5). In any case, the simulation of the T2-TM is scaled and represented with unbent signals only. The order in which the inner structure and the T2-TM computation stop does not matter. They are both stopped before the output signal reaches the outer structure.

It is crucial that the computation as well as the inner folding could be resumed: the T2-TM computation is infinite and the shrinking ensure that the next output symbol comes in bounded time.

The awaking is done in two times. One symbol, o write-done-generated by the outer structure-crosses the configuration from right to left to restart the T2-TM computation. This signal reaches the left end of the outer struc-ture generating i start that resumes the shrinking. ( i border F ri behaves like i border ri .)

Outer structure

Each time a symbol is output, T2-TM and inner structure are frozen, apart from the symbol signal, only remains motionless signals. The outer structure reacts to the output signals: it shrinks everything by one half and does a translation so as to occupy the first half (for 1), the middle half (for 0) or the right half (for 1).

The inner structure and the computation within are frozen each time a symbol is outputted. This has two purpose: to treat each output independently and to prevent the inner structure from producing another accumulation: it will accumulated exactly at the same position.

In the following space-time diagram, the head of the T2-TM and i start are removed for clarity. (The meta-signals involved in the outer structure are denoted with an initial o .)

If 1 is received, all is described on Fig. 6. The triangle o minus lo , o minus hi and o write-done is used both to scale and to relocate. Since handled signals are parallel and hence there is no activity whatsoever, scaling is easier than previously (it is a special case). All bent signals are parallels to o write-done ensuring an exact preservation of ratios from one side to the other of the triangle. Finally, Fig. 9 depicts a whole run. It becomes rapidly hard to distinguished the inner part due to the cumulative shrinking effects. Nevertheless, the output signals can be distinguished, the sequence starts with 1, 0, 0, and 1.

The result might be an infinite constant sequences of 1. This would provide an ε equals to 1. This is very easy to test and to deal with.

Conclusion

The time for the accumulation is not only finite but bounded: the duration can be decomposed in accumulation time for inner structure, outer structure and interactions between the two structures. Each one is bounded by a geometrical series.

Theorem 1 With a proper handling of accumulations, it is possible to compute any function of computable analysis in bounded time. There are always finitely many signals in each configuration.

There is no hidden oracle. Although speeds may be any real and thus encode information, only a few rational values are used. And apart from mixed representation of ε, the distance between signals are also proportional with rational ratio.

Not only does the mixed representation use finitely many signals, but is also almost directly reusable to do analog computation in the Blum-Shub-Smale understanding (as presented in [START_REF] Durand-Lose | Abstract geometrical computation and the linear Blum[END_REF][START_REF] Durand-Lose | Abstract geometrical computation with accumulations: Beyond the Blum, Shub and Smale model[END_REF]). This leads to consider even more powerful analog computational system since CA and BSS are not comparable, e.g. analytic machines [START_REF] Chadzelek | Analytic machines[END_REF].

It should also be possible to use higher order accumulation to hypercompute as is done for the BSS model in Durand-Lose [2009a] and to do some real hyper-computing [START_REF] Ziegler | Short) Survey of real hypercomputation[END_REF].

Fig. 1

 1 Fig. 1 Empty structure for extracting bits

Fig. 3

 3 Fig. 3 Simulation of a type-2 Turing machine.

Fig. 4

 4 Fig. 4 Inner structure.

Fig. 5

 5 Fig. 5 Stopping the inner structure.

Fig. 6 Fig. 7

 67 Fig.6Outer structure shrinking step for 1.

Fig. 8

 8 Fig. 8 Outer structure shrinking step for 1.

Fig. 9

 9 Fig.9The whole picture.

  is used for this. On this space-time diagram, the signal amounting for ε, e, is missing. Its presence only superposes signals and collisions. Rules {one, get}→{get + } {half, get + }→{get 0 , halfL, one} {zero, get 0 }→{get 0 , halfL, zero, halfR} {half, get 0 }→{get -, one, halfR} {one, get -}→{} {halfR, halfL}→{half, halfR} {halfR, one}→{set, one} {halfR, zero, set}→{set, zero} {one, set}→{one}

	g e t -	one one	g e t 0 h a l f R h a lf L half s e t s e t half h a l f R zero s e t zero	half half	h a l f R s e t one	time	Meta-Signal halfL get, get -, get 0 , get + set one, half, zero halfR	Speed -3 -1 0 1
			h a l f R h	one
	one		g e t 0 a lf L
		half
			zero			g e t +
						half
							one	g e t

Table 1

 1 Transition table of the type-2 Turing machine.

	state


Jihene Tounsi
email: jihene.tounsi@univ-savoie.fr

Georges Habchi
email: georges.habchi@univ-savoie.fr

Julien Boissière
email: julien.boissiere@univ-savoie.fr

A MULTIAGENT SYSTEM FOR PRODUCTION SYNCHRONIZATION IN SME MECHATRONICS SUPPLY CHAIN

Keywords: Small and Medium Enterprises (SME), Supply Chain (SC), Multiagent, Modelling, Integration, Synchronization Protocol

We present in this paper the application of multiagent system (MAS) for modelling and simulation of the dynamic structure and behaviour of the supply chain in SMEs mechatronic context in Savoie. First, a short literature overview describes the context and the contribution of multiagent modelling for SMEs integration. In the rest of the paper, the supply chain concepts and their agentification are presented. On the basis of this correspondence, we propose a synchronization protocol for the operational system (production flow and resources).

INTRODUCTION

The growing need for supply chain integration between the various actors is a major strategic challenge and a strong competitive advantage. Indeed, the supply chain is a complex macro-system, first due to the variety of implicated organizational structures and the relationships between them, and secondly due to the strategic decisions it involves. A company's success lies in its ability to integrate managerial processes of the supply chain but also to coordinate with other actors [START_REF] Drucker | Management's new paradigms[END_REF][START_REF] Lambert | Issues in supply chain management[END_REF].

As such, Small and Medium Enterprises (SMEs) evolve in an unstable and complex economic environment. In order to survive and to be able to support supply chain's requirements and market requests, SMEs have to collaborate together to achieve their goals without losing their autonomy and identity [START_REF] Julien | Les PME bilan et perspectives. 2 e edition[END_REF][START_REF] Villarreal Lizarraga | Contributing to management of shared projects in SMEs manufacturing clusters[END_REF]. According to Julien [START_REF] Julien | Les PME bilan et perspectives. 2 e edition[END_REF], to find equilibrium between big companies and SMEs, SMEs must maintain and even improve their competitiveness in an increasingly competitive market. This competitiveness can be achieved by the control of information and processes but also thanks to a network structure. The theory of SMEs network, which is based on collaboration, cooperation and coordination, is a crucial crossroad for its management strategy. The alliances will reduce their vulnerability and this stresses SCM integration in a global supply chain context. This philosophy is explained by Assens [START_REF] Assens | Du modèle bureaucratique au modèle organique[END_REF]: "the enterprises network is based on an autonomous and independent SMEs network which interacts in the context of mutual trust relationships to reduce the uncertainty of their environment.

During these local interactions, a global organization form emerges in the absence of a central regulatory entity".

In the French region of Savoie, the industrial environment consists of numerous productive SMEs of the mechatronic industry working together in a cluster to achieve a common goal in a complex global supply chain. Some economic researches defined the Savoie industrial context as a region based on sector and geographical concentration of independent SMEs which have complementary activities. This cluster's success is due to interlinking the different production units and developing relationships characterized by flow regulation, learning and coordination. According to this context description and some investigations, we have drawn three main features of the supply chain which integrates SMEs groups and especially mechatronic: (i) complexity due to the number of autonomous actors in SMEs network and the heterogeneity of their relationships (ii) decentralization due to the dispersion of the geographical production sites in the global supply chain (iii) only a local site visibility for SMEs group in the global supply chain. To fill the gap caused by these characteristics, SMEs coordinate their activities with other sites through physical and data flow [START_REF] Tounsi | A conceptual model for SME Mechatronics supply chain[END_REF]. The lack of work in this area and the growing need expressed by professionals lead us to study the structure of the supply chain essentially composed of SMEs mechatronic, and the different mechanisms of integration defining the dynamics behaviour. To fill this gap, we have studied the research advances in industrial and software engineering to find an adequate solution to the studied context. This solution is based on the multiagent approach to model and simulate the static and dynamic aspects. Indeed, the benefits of multiagent systems (MAS) are widely recognized in literature. Agent technology allows new approaches for modelling and simulation of complex distributed systems. Hence, on one hand, autonomous agents can communicate their preferences, deal objectives with other agents or coordinate together to reach their own objectives or some more global objectives (Bussman et al., 2004). On the other hand, the supply chain is composed of actors or entities which evolve in an organization and interact to achieve a collective purpose. This analogy leads to multiagent approach being a framework naturally oriented to model the supply chain.

In this paper, we focus on the description of the dynamic behaviour adopting the multiagent approach. This work is divided into three main parts. The first part discusses on one hand the different mechanisms of management integration in the supply chain domain and especially in the SMEs mechatronic field; and on another hand, the contribution of multiagent system to implement this dynamic behaviour. In the second part, we present the agentified domain metamodel which describes the static modelling of the context. The third part introduces the behaviour of the identified concepts in the physical system synchronization, before a conclusion is drawn.

LITERATURE OVERVIEW

In this section, we define the different communication mechanisms to integrate the potential actors in the supply chain. We also present the common communication mechanisms in the SMEs cluster and in the global supply chain. Moreover, in the last part we introduce the contribution of the multiagent paradigm to structure the decision-making and the dynamic behaviour of the supply chain actors.

Communication mechanisms in the supply chain

The primary factor of management practices integration in a supply chain is the use of a communication mechanism to synchronize the flows (physical, informational, decisional and financial). In this work, we define a communication mechanism as a "framework formalizing interaction between different actors in the network according to their managerial relationship characteristics". In a supply chain, we can find several types of actor's relationships depending on the nature of their goals and their degree of involvement. Indeed, Wong et al. [START_REF] Wong | Supply chain coordination Problems: Litterature Review from organization, economic and operations perspectives[END_REF] highlight that in a supply chain, integration is based on different types of relationships that are: coordination, cooperation and collaboration. In many cases, these mechanisms are used with confusion and as being similar. However, according to the literature, each mechanism has its own characteristics. Before describing a relationship between two actors in a supply chain, one must consider the criteria relating to: objectives, decision-making, risks, profits, formal exchanges and sharing product transformation.

According to [START_REF] Mattessich | Collaboration: what makes it works[END_REF], cooperation infers a less formal relationship and involves a lower degree of commitment to join goals. A cooperative relationship entails information sharing as needed, and authority is retained by each organization so that there is virtually no risk. In this kind of communication mechanism, resources and rewarded are separately treated. The product transformation is supported individually by each organization. The second communication mechanism to consider is the coordination which is defined in literature as a process to bring into a common action, movement or condition, or to act together in a smooth concerted way. Compared to cooperation, coordination leads to more formal relationships and an understanding of compatible missions. Planning, division of roles and communication channels are well-defined.

Resource allocations are mutually acknowledged, and risks and benefits may be shared or compensated. However, authority may still rest with the individual organization and the product transformation is handled individually. Finally, the third communication mechanism is the collaboration. It is defined as a mutually beneficial and well-defined relationship entered into by two or more organizations to achieve common goals. Collaboration is distinguished from coordination by its collaborative structure which determines a joined authority structure. Resources are pooled or jointly secured, and the product transformation is shared.

Integration of SMEs mechatronic network in the supply chain

Previously, we have identified different communication mechanisms that define the management framework of process and information. On the basis of this literature analysis, we studied the different integration mechanisms in the supply chain composed essentially of SMEs mechatronic in Savoie. So, briefly, the global supply chain is divided into many sites geographically dispersed. A cluster of some SMEs mechatronic in Savoie is integrated in this global network but only with a local visibility of the production sites. However, the SMEs cluster is not isolated and it communicates with the other nodes through the different types of flows. The study of the global supply chain and the SMEs cluster identifies two kinds of communication mechanisms according to the criteria defined before. Hence, in the mechatronic cluster, SMEs work together to achieve a common goal. Resources, benefits and products transformation are shared. So, the SMEs collaborate in cluster to reach the local objective. The collaborative process takes place according to the following scenarios:  Physical flow synchronization: in the cluster, the actors will synchronize their information and their actions for production needs. This collaboration is frequent in commonly encountered situations.



Local Monitoring: the monitoring and control of SMEs group will be based on the performance evaluation and the resolution of new perturbations on the physical environment which do not disturb the objectives of other parts of the SC.

Nevertheless, the SMEs cluster will coordinate its activities in order to achieve the global supply chain objectives. At the global level, each node has a limited perimeter of influence. For this reason, a cluster needs to communicate with the other actors to face the environment disturbance by coordinating their activities and local objectives in order to achieve the global objective. This coordination takes place according to the following scenarios:  Initial configuration of the system: the actors of the network interact in order to set and coordinate their goals in the global supply chain.



Environment perturbation affecting all goals: if a perturbation occurred in a cluster's environment which requires a modification of its local objective and which affects other nodes objectives, the coordination between supply chain sites is necessary in order to find an appropriate solution to the problem.  Reconfiguration of the system: if the actors recognize that the current system configuration cannot achieve the global objective, the interaction between the sites is required to set new objectives according to their experience.

In this paper, we implement the second scenario of the coordination mechanism and the two identified collaboration scenarios.

Multiagent approach for supply chain dynamic modelling

In supply chain modelling and simulation there are two main types of approaches: the equation-based modelling approach and the agent-based modelling one. Parunak et al. [START_REF] Parunak | Agent-based modelling VS equation-based modelling: a case study and user's guide[END_REF] have proven that multiagent systems and agents are more suitable to model the dynamics behaviour of the complex network manufacturing system and to study the impact of flow management between different entities than the equation-based modelling. In fact, agents are more suitable for applications that are decentralized, changeable, ill-structured (dynamic structure) and complex [START_REF] Parunak | Wat can agents do in industry, and why? An overview of industrially-oriented R&D at CEC[END_REF]. The multiagent approach provides a framework naturally oriented to model the supply chain. By comparing the supply chain and the multiagent system characteristics, similar concepts and the same organizational practices arise.

In fact, both are composed by actors or entities which evolve in an organization and interact to achieve a collective purpose. This analogy leads to multiagent approach being a privileged way to model supply chain systems.

In literature, several research works propose different protocols based on multiagent system for modelling the dynamic behaviour of the supply chain. Most often, these protocols extend the Cooperative Problem Solving model (CPS) proposed by Wooldridge and Jennings [START_REF] Wooldridge | The cooperative Problem-Solving Process[END_REF]. The CPS defines an abstract way to structure a collective decision-making process in which a group of autonomous agents choose to work together to achieve a common goal. In more details, this model is deployed in four stages:

 Recognition: in which an agent identifies the potential for interaction.  Team formation: in which an agent solicits assistance.  Plan formation: in which the newly formed collective attempts to construct an agreed joint plan.  Execution: in which members of the collective play out the roles they have negotiated.

In the following, we describe the implementation of the different collaboration and coordination processes defined previously. These protocols apply the CPS abstract model and structure the interaction between the domain concepts in order to simulate the physical system synchronization.

AGENTIFIED DOMAIN METAMODEL

First, it is necessary to describe the architectural and functional properties of the domain concepts. In this section, we present the agentified domain metamodel which merges the domain concepts with multiagent concepts. The domain metamodel generation and its agentification are based on ArchMDE (Architecture Model Driven Engineering) development process which draws its metamodelling steps in MDE (Model Driven Engineering) approach. MDE [START_REF] Kent | Model-driven Engineering[END_REF] promotes the separation and combination of models in order to control the software development in its different phases (from the analysis to the implementation). In fact, in our research context, we identify two metamodels related to ArchMDE approach. The first one describes the functional concepts and properties of SMEs Mechatronic supply chain.

The second one defines a multiagent metamodel. A combination of the two metamodels will generate an agentified domain metamodel (see figure 1). Only the main results of this approach are outlined in this section. More details can be found in (Tounsi et al. 2009a).

Constraint

Figure 1 Domain metamodel (top-down)

The domain metamodel is an UML class diagram which represents the concepts defining the architecture and the properties of the global supply chain and the SMEs group (Tounsi et al., 2009b).  Supply chain (SC): this concept defines the root of the domain modelling. All the other concepts will detail this one.

 Environment: this concept models the space allocated to the product flow and management through the internal resources as well as the external elements able to influence the activities of the supply chain.  Sub Supply Chain (SSC): the SSC represents a group of SMEs which collaborate to achieve an internal aim and/or the overall objective of the supply chain. The SSC is responsible for the management of the product flow in a certain stage of its life cycle. The SSC is composed of 3 layers involving some particular concepts and playing a specific role. Finally, the following concepts considered as data support, allow some other concepts to play their roles in the metamodel:  The Physical Process (PhP) describes the sequences of processing stages of the product. The PhP is a concept to be integrated within a domain metamodel in order to define the tasks that can be handled by the Execution System.  The Indicator Base represents a database recording the indicator measures. The EA detects a Physical System deviation according to the gathered information within this database.

 The Action Base represents a database that stores the actions to apply when facing an indicator deviation.  The Objective models the global goals of the supply chain or of the SSC ones.  The Knowledge Base represents a database including all knowledge needed by the actors to make the right decision.

A n element of the Knowledge Base can be an organizational knowledge or a constraint.

At this step, the domain metamodel describes the supply chain in SMEs mechatronic context. This metamodel is merged with a multiagent metamodel in order to obtain a correspondence between each domain concept and multiagent one. The agentified domain concept implements the structural properties and dynamic behaviour of the multiagent one. Figure 2 draws the multiagent metamodel according to the "vowel approach" introduced by Demazeau [START_REF] Demazeau | Vowels[END_REF]. (Tounsi et al., 2009a) So, according to these two metamodels, the following table highlights the correspondence between the domain concepts and the multiagent ones.

Group

Domain concepts

Multiagent concepts

Description

Supply Chain (SC)

MAS

By analogy, the root of the domain metamodel corresponds to the root of the multiagent system. Environment Environment In the two metamodels, environment is the space defining all things external to agents and necessary to manage the SC. Sub Supply Chain (SSC)

PHYSICAL SYSTEM SYNCHRONIZATION

The SSC is responsible for the synchronization of the involved Physical System to achieve its task. This activity consists in applying a communication protocol according to the nature of the interaction framework. In this section, we describe the collaboration and coordination processes to implement in the Execution System and Monitoring System in order to synchronize the Physical System. These protocols are built according to the CPS abstract model.

In accordance with the agentified domain metamodel, the Execution system is responsible for the synchronization of the physical process (PhP) in common situations. Indeed, Executive Actors (EAs) which are reactive agents, synchronize PhP by taking into account the availability of resources. Then, on the basis of the agentified domain concepts, the synchronization protocol in the Executive System is shown in Figure 5: (Tounsi et al., 2009b)  An Executive Agent (EA) receives a request and reacts according to its type. Three kinds of request can be distinguished: a ME request, a collaborative request from another EA or a negative response to a collaborative action initiated by the agent itself.  If the request is a negative response to a collaborative demand that the EA initiated: the EA sends a request to the coordinator agent of the monitoring system.

 If the request is a synchronization need coming from the Moving Entity (ME) or a collaborative request from another initiator agent, EA checks the availability of the concerned resources.  If the resource is available, the EA carries out its task, updates the state of ME and informs the other agents from the executive system and the coordinator agent of the end of action.  If the resource is unavailable and the EA has been solicited by another executive agent to achieve the task, it sends a failure request to the initiator.  If the resource is unavailable and the EA is in charge of the task then it seeks in its organizational knowledge an agent from the Execution System of the SSC that might have the needed resource.  If the agent finds into its organizational knowledge an agent that can handle the task, it delegates the responsibility of the task. In this case, the collaboration process of the concerned agent will be activated and follows the same sequence.  If the agent does not find another agent having the needed resource to handle the task, it sends a request to the coordinator agent. This agent is a monitoring agent (MA) that receives requests from the Execution System. MA sends the information to other monitoring agents of the SSC in order to find a solution.

However, in unusual situations, the Executive System refers to the Monitoring System. In this case, MAs group evaluates the situation according to the defined objective and establishes an actions plan. If the objective is not reached, the MA needs to consult other SSCs to find a suitable solution. So, the synchronization protocol in the Monitoring System can be described according to the follow steps:  In the Monitoring System, a Monitoring Actor (MA) has the responsibility to check all the received requests and diffuses them to other MAs in the layer. Three kinds of requests can be distinguished: EA request, answer to a help request or a help request from another SSC in the global supply chain.  If a MA coordinator receives an EA request then it diffuses the information to other MAs. In this case, according to the objective, the group evaluates the situation. Two cases may arise: the problem has no impact on satisfying the SSC objective or the objective is deviated.  If there is no impact on the objective, the MA tries to find an internal solution according to its desire, belief and constraints. If a solution can be found, the MA coordinator spreads the actions plan to the Executive System.  If the objective is deviated or an internal solution can not be reached. The MA group sends a Help Request to other SSCs through the MA coordinator and waits responses.  If all responses are received, the MA coordinator classifies them by a reception date of help. The selection will be diffused in the Monitoring System. According to their beliefs, desires and constraints, MAs group chooses the suitable answer and diffuses the action plan to the Execution System. In this case, the EA updates the ME state.

 If the request is a Help Request from another SSC, the MA coordinator spreads the request to the Monitoring System. In this case, the Monitoring System evaluates the demands according to internal criteria (Objective, Constraint, Belief, and Desire). If the SSC can provide assistance, it makes an offer to the SSC initiator or it sends a negative response.  SSC initiator chooses the suitable offer and sends a confirmation to the selected SSC and a cancellation response to other bids.

The following figure shows the sequence of messages between the SSCs. This diagram represents the coordination process in the global supply chain in order to synchronize the physical flow in the case of a perturbation case (SSC cannot reach the internal aim).

CONCLUSION AND PERSPECTIVES

The present research work focuses on the integration of mechatronic SMEs into the global supply chain. These SMEs clustered in group are localised in Savoie, a French region. Communication protocols for physical environment synchronization are proposed. These protocols describe the dynamic behaviour of agentified domain concepts, since the modelling solution is based on multiagent paradigm. The multiagent system defines the behaviour characteristics of the domain concepts and consequently the establishment of communication protocols. Thereby, this article introduces a stage from a global solution. Now, our research work focuses on the implementation of the performance evaluation processes in the SMEs group and in the global supply chain. All the concepts and processes will be encoded within a simulation platform.

Figure 2

 2 Figure2Multiagent metamodel(Tounsi et al., 2009a)

Figure 3 .

 3 Figure 3. EA Synchronization Behaviour(Tounsi et al., 2009b)

  Figure 4. SSC coordination process

Table 1

 1 Table 1 summarizes the different criteria for each communication mechanism.

		Collaboration	Cooperation	Coordination
	Objective	Common	not grouped	Common
				Common + actor
	Decision-making	Common	Individually	decision maker
				(in some cases)
	Benefits	Shared	Individually	Shared
	Resources	Shared	Individually	Individually (but known by others)
	Formalism	Formal	Few formal	Formal
	Risks	Shared	Not shared	Shared
	Temporal aspect
	on product	Shared	Individually	Individually
	transformation

. Communication mechanisms

[START_REF] Tounsi | A conceptual model for SME Mechatronics supply chain[END_REF]

  The Monitoring System models the intelligent layer of the SSC. It controls and monitors the two other layers through the information provided by the Execution System. The Monitoring Actors (MA) are the main elements of this layer. They model the intelligent actors of SSC and establish metrics to evaluate the performance of the group and consequently act on the two other layers. Therefore, the MAs are the components responsible for the control and decision-making in SSC but also for the coordination activity in the global supply chain.

	These 3 first concepts define the abstract framework of the
	context. Thus, according to the domain metamodel a supply
	chain (SC) is composed of one or more organizations (SSC)
	and a physical environment. SSC at this level represents a
	SMEs group. A Detailed presentation of the internal
	architecture of the SSC and its perimeter of influence
	(visible part of the environment to the SSC) follows. These
	concepts represent the second level of the domain
	metamodel.
	

 The Execution System is the reactive layer of the SSC. It deals with two main roles: (i) it ensures the synchronization of the physical flow according to the information gathered from the Physical System, (ii) it observes and corrects the Physical System if a perturbation occurs. In abnormal situations, the Execution System refers to the Monitoring System for coordination and decision-making. The Executive Actors (EA) are the principal entities of this layer. The EAs mainly model the reactive actors and occasionally MAs having reactive behaviour in this layer.  The Physical System is the visible part of the environment from the SSC. It corresponds to the influence perimeter of the SSC. This layer is composed of passive elements controlled by the two other of the SSC. Two main concepts are identified: the Moving Entity (ME) modelling the product in circulation and the Resource modelling the production means.

Table 1 .

 1 Correspondence domain concepts and multiagent ones

		Organization It is an organization
			composed of two groups of
			agents.
	Physical	Resource	It is all needed resources
	System		for one agent or a group of
			agents to manage the group
			(perimeter of influence).
	Resource	Passive	It is an allocated resource
		Resource	to the agent to perform its
			task.
	Moving	Active	It is the product in
	Entity (ME)	Resource	circulation. ME activates
			the behaviour of the
			reactive agents.
	Physical	Task	It is a task or a physical
	Process (PhP)		activity to be handled by

THANKS

We thank the APS (Assemblée des Pays de Savoie) and the Laboratory SYMME (Systèmes et Matériaux pour la Mécatronique) who funded this work through a research grant.