Fabien Michel
email: fabien.michel@univ-reims.fr

The IRM4S Model: The Influence/Reaction Principle for Multi-Agent Based Simulation

Keywords: I.2.11 [Distributed Artificial Intelligence]: Multiagent systems-Multi-Agent Based Simulation Theory, Design, Experimentation Influence/Reaction, multi-agent based simulation

The IRM4S model (Influence Reaction Model for Simulation) is an adaptation of the formalism of [2] for multi-agent based simulations (MABS). The goal of IRM4S is to provide a framework that eases the use of the Influence/Reaction principle within MABS.

INTRODUCTION

Within MABS, the result of agents actions and interactions are usually modeled as a transformation of a global state. For instance, in [START_REF] Genesereth | Logical foundations of artificial intelligence[END_REF], wherein Σ is the world state, the behavior of an agent a is modeled using Behaviora : Σ → Σ which is decomposed in three functions : (1) P ercepta : Σ → Pa computes a percept, (2) Mema : Pa × Sa → Sa computes the new internal state sa, and (3) Decisiona : Pa × Sa → Σ modifies the world according to the action of an action that the expected result will happen (e.g. the action means of a robot may be out of order). More generally, an agent cannot compute the result of its actions: It does not know exhaustively the environmental settings, especially the other actions taking place at the same time. This can be summarized as the environmental integrity constraint: An agent should not be able to directly modify its environment.

Thirdly, there is an issue related to agents autonomy. Indeed, agents interactions, and especially joint actions which conceptually involve independent decisions, are usually implemented so that only one agent, the initiator, does decide for the others, modifying the targeted agents and the environment at once (e.g. in a reproduction process [START_REF] Michel | Weak interaction and strong interaction in agent based simulations[END_REF]). Thus, the targeted agents goals are not considered. Is it normal that a targeted agent find itself involved in an interaction process not explicitly chosen? Is this entity autonomous? To be correctly modeled, some interactions require to consider all the involved behaviors, not only one [START_REF] Michel | Weak interaction and strong interaction in agent based simulations[END_REF].

Finally, in a modeling and simulation context, it is crucial that the results obtained from the modeling specifications do not depend on the implementation [START_REF] Zeigler | Theory of Modeling and Simulation[END_REF]. However, MABS models that rely on a classical action representation are extremely sensitive to the way they are implemented [START_REF] Michel | Formalisme, outils et éléments méthodologiques pour la modélisation et la simulation multi-agents[END_REF].

Ferber and Müller have proposed an original action model (noted FM in this paper) which is a solution to the simultaneous actions modeling issue [START_REF] Ferber | Influences and reaction : a model of situated multi-agent systems[END_REF]. This paper shows that it also represents a solution to the other preceding issues and presents an adaption of FM for MABS, namely the IRM4S model. The next sections describe our proposition and give examples of IRM4S use cases.

THE IRM4S MODEL

Influence/Reaction: a MAS action theory

This theory relies on two notions: (1) influences and (2) reaction to influences [START_REF] Ferber | Influences and reaction : a model of situated multi-agent systems[END_REF]. In this theory, an agent does not perform actions, in the meaning seen previously, but produces influences (e.g. "try to open a door"). The difference is fundamental. Influences do not directly modify the environment and, from an agent's point of view, nothing can be guaranteed about their result. This perspective enables to distinguish the individual gestures (agent level) from what actually happens considering the other gestures: The environment reaction to all the influences (multiagent level). So, the reaction cannot be computed without knowing all the influences which are produced at the same time.

Applying this theory at the implementation level thus requires a two phases mechanism that (1) collects the influ-a.So,thedirect modification of the environment is the means by which is computed the deliberation result (e.g.

σ = {door(closed)} → σ = {door(open)}).
However, such an action modeling raises a number of problems at both the modeling and implementation levels.

Firstly, it does not allow to easily model simultaneous actions since the actions are validated one by one [START_REF] Ferber | Influences and reaction : a model of situated multi-agent systems[END_REF].

Secondly, by directly modifying the environment, it is not possible to model the uncertainty related to external dynamics. Indeed, it is not because an agent decides to do ences, Influence phase, and then (2) compute the result of their combination, Reaction phase. Based on an extension of [START_REF] Genesereth | Logical foundations of artificial intelligence[END_REF], the formalism of FM relies on such a mechanism.

However, FM is complex and parts of it remain fuzzy [START_REF] Weyns | Formal model for situated multi-agent systems[END_REF][START_REF] Michel | Formalisme, outils et éléments méthodologiques pour la modélisation et la simulation multi-agents[END_REF]. Moreover, since simulating a system relies on modeling its evolution from an instant t to the next t + dt [START_REF] Zeigler | Theory of Modeling and Simulation[END_REF], the lack of a temporal variable in FM does not ease its use in MABS and notably leads to ambiguities on how its specification should be implemented [START_REF] Dávila | Towards a logic-based, multi-agent simulation theory[END_REF][START_REF] Michel | Formalisme, outils et éléments méthodologiques pour la modélisation et la simulation multi-agents[END_REF]. So, despite the interests of its theory, FM has not been used as it is and the works that try to apply FM are always an adaptation of it [START_REF] Dávila | Towards a logic-based, multi-agent simulation theory[END_REF][START_REF] Weyns | Formal model for situated multi-agent systems[END_REF].

The IRM4S equations

A two phases mechanism

Contrary to the previous cited adaptations, IRM4S does not formalize all the mechanisms which could be derived from the Influence/Reaction principle. The IRM4S purpose is to clarify the two phases mechanism underlying the Influence/Reaction theory, especially from a temporal point of view.

As in FM, we use the notion of dynamical state δ ∈ Δ to represent the system state. δ is a 2-tuple < σ, γ > where σ ∈ Σ represents the environmental variables, and γ ∈ Γ the influences. The system evolution is defined using a function Evolution such that δ(t + dt) = Evolution(< σ(t), γ(t) >). Thus, to apply the Influence/Reaction principle, we decompose Evolution in two functions, Influence and Reaction, that define the required two phases mechanism:

Influence : Σ × Γ → Γ then Reaction : Σ × Γ → Σ × Γ.
Influence globally defines the influences γ (t) ∈ Γ produced at the micro level (agents and environment). We note this set γ (t) (not γ(t)) to express that it is a temporary set which will be used immediately in the Reaction. Reaction defines how the world changes, considering σ(t) and γ (t). So Evolution corresponds to a two phases mechanism:

γ (t) = Influence(σ(t), γ(t)) (1) < σ(t + dt), γ(t + dt) >= Reaction(σ(t), γ (t)) (2)

Influence phase: agents and environment

Contrary to [START_REF] Genesereth | Logical foundations of artificial intelligence[END_REF], the perception of an agent is now computed from a dynamical state Δ, and not only from Σ. This allows to model perceptions which express the dynamics of a situation (e.g. the fact that a ball is rolling). Such a perception is tricky to compute from Σ variables, while it is easy to model using influences. Moreover, the behavior of an agent now produces an influence γ ∈ Γ . Thus, we have now Behaviora : Σ × Γ → Γ , which can be decomposed in:

pa(t) = Perceptiona (σ(t), γ(t)) (3) sa(t + dt) = Memorizationa (pa(t), sa(t)) (4) γ a (t) = Decisiona (pa(t), sa(t + dt)) (5)
The environment has endogenous dynamics and thus also produces influences (moving objects, pheromone diffusion, etc.). Contrary to approaches that integrate these dynamics into the reaction computation, these influences belong to the Influence phase in IRM4S. Indeed, from a temporal point of view, all the influences are simultaneous: The environment and the agents are not temporarily independent (an agent and a rolling ball produce influences simultaneously). Besides, as for the behavior of an agent, the environment dynamics is also a consequence of the current system dynam- ical state. We thus represent the environmental dynamics with Naturalw : Σ × Γ → Γ, similarly to Behaviora . However, Naturalw does not represent any autonomous behavior at all. So, we have γ w (t) = Naturalw (σ(t), γ(t)).

Influence thus gives a set γ (t) that contains the influences which already are in the system and those which are produced by the environment and the agents:

γ (t) = Influence(σ(t), γ(t)) = {γ(t) ∪ γ w (t) [ a γ a (t)} (6)

Reaction phase: macro level

In the previous section, we have decomposed the Influence phase to show how the micro level could be managed. Considering the Reaction phase, the same must not be done. Indeed, MABS models could be related to very different domains and the influences could be very heterogeneous: movements, speech acts, reproduction processes, etc. So, it would be not relevant to propose a unique solution to the reaction computation. It is up to the modeler to define the desired system dynamics.

We can however notice that this computation raises an issue: The complexity of combining all the influences. To reduce this complexity, two main solutions can be considered:

(1) distribute the reaction computation and (2) classify the influences. Firstly, it is indeed possible to take into account that, a priori, an agent only influences its surroundings (e.g. a movement does not need to be considered at a global level). Secondly, it is interesting to classify the influences according to their type. An agent that wants to move will not have, a priori, any impact on a neighbor that consumes a resource.

Schematic representation of IRM4S

IRM4S defines a two phases mechanism: Influence then Reaction. So, our temporal vision of the Influence/Reaction cycle makes a clear distinction between (1) the influences and (2) the reaction to these influences (figure 1).

MODELING EXAMPLES

Soccer robots

Let be the following scenario. (1) two robots (Bot1 and Bot2) are in position so they can shoot a ball. ( 2) Each robot decides to shoot the ball (Influence phase). ( 3) The shoots are combined and make the ball moves (Reaction phase). ( 4) The movement of the ball then produces an environmental influence that models the frictions to which the ball is subjected (Influence phase). [START_REF] Michel | Weak interaction and strong interaction in agent based simulations[END_REF] The location of the ball has been changed and its speed reduced (Reaction phase). This scenario could be implemented as follows:

1 < σ(0) = {Bot1, Bot2, Ball}, γ(0) = {} > 2 γ (0) = {shoot1(1, 1), shoot2(-1, 1)} : (force vectors) 3 < σ(1) = {Bot1, Bot2, Ball}, γ(1) = {moveball(0, 2)} > 4 γ (1) = {moveball(0, 2), slowball(0, -0.5)} 5 < σ(2) = {Bot1, Bot2, Ball}, γ(2) = {moveball(0, 1.5)} >
This simple example highlights several IRM4S aspects. First of all, the modeling of the simultaneity is eased thanks to the distinction between the agent and multiagent levels. Indeed, thanks to the recovery of the influences (2), we have all the information which enables the computation of the shoots combination (3). Secondly, this example also illustrates how the endogenous dynamics of the environment could be modeled [START_REF] Michel | Formalisme, outils et éléments méthodologiques pour la modélisation et la simulation multi-agents[END_REF]. Finally, it also shows the possibility for the agents to simply perceive the fact that the ball is rolling because it is modeled as an influence [START_REF] Genesereth | Logical foundations of artificial intelligence[END_REF]. As previously said, such a perception could be very tricky to model using classical approaches.

A prey/predator system

Let be a system, composed of preys and predators localized on a 2D grid: Σ = {Prey1 (x , y), ..., Predn (x , y)}. Every agent can perceive the entities which are at the same place: Pprey = Ppred = {Prey1 , ..., Predn }. The predators can move and eat preys. The preys can move and reproduce with each other. So, we have the following influences: Γpredator = {movei (direction), eati (Preyid )} and Γprey = {movei (direction), reproi (Preyid )}. Here are some examples of behaviors which could be obtained:

Behaviorprey 2 (Prey1 , Prey4 ) = repro2 (Prey1 ) Behaviorpred 2 (Prey2 , Prey3 ) = eat2 (Prey3 )
Here is an example of how the reaction could be done: reactionComputation(){

(1) For each influence eati(P reyid) eati(P reyid) is validated according to a coin flip probability. In case of competition (that is {eati(P reyk), eatj(P reyk)} ∈ γ ) the predator with the highest energy is selected (2) Suppression of the agents killed in (1) (3) Considering influences reproi(P reyj)

If {reproi(P reyj), reproj(P reyi)} ∈ γ Then a new prey is created (4) Validate the influences movei (direction) } Figure 2 is an example of the dynamic which could be thus obtained. This example illustrates all the interests of the notion of influence with respect to the modeling of the reproduction interaction. Indeed, contrary to the classical approaches, all the agents influences are taken into account and there is no violation of the autonomy property: We do not decide in place of the agents, but we do explicitly decide of the dynamics of the system. Besides, even if the computation of the reaction which has been proposed is only a solution among others (the scheduling of the reaction could be modified), it is however the expression of a dynamic which is entirely controlled and which cannot be different whatever the used implementation. This is a fundamental aspect of IRM4S: Whatever the order in which the agents produce their influences, the reaction completely specifies the dynamic of the system.

Moreover, the IRM4S model is not related to a particular simulation technique (event-based of discrete time simulation). Indeed, the produced influences may not be immediately consumed within the reaction and can persist during the time of the behavior. So, in an event-based simulation, two reproduction influences can overlap and thus succeed.

CONCLUSIONS

This paper has presented the IRM4S model which eases the use of the Influence/Reaction principle within MABS thanks to the use of an explicit temporal variable that clarifies the two phases mechanism embedded in this principle.

Moreover, IRM4S is also a solution to the other issues related to the classical action representation. Indeed, thanks to the notion of influence, IRM4S fully integrates the environmental integrity constraint: The agents do not directly modify the environment. Consequently, the agents cannot violate the autonomy property of the others as well. Besides, autonomous behaviors are always taken into account through their influences. Finally, IRM4S provides an efficient means to design modeling specifications which are fully independent from the way they are implemented.

Figure 1 :

 1 Figure 1: System evolution in the IRM4S model.

Figure 2 :

 2 Figure 2: Influence


Jérôme Los

Luisa Paoluzzi

António Salgueiro

Non-isometric hyperbolic 3-orbifolds with the same topological type and volume

Keywords: AMS classification: Primary 57M10, Secondary 57M50, 57M60, 37E30 Branched covers, mapping tori, (pseudo-)Anosov diffeomorphisms

We construct pairs of non-isometric hyperbolic 3-orbifolds with the same topological type and volume. Topologically these orbifolds are mapping tori of pseudo-Anosov maps of the surface of genus 2, with singular locus a fibred (hyperbolic) link with five components.

Introduction

In this brief note, building upon techniques and ideas already used in [LPS], we construct a hyperbolic 3-manifold that is a branched cover of a link in another hyperbolic manifold (the mapping torus of an pseudo-Anosov map of the surface of genus 2) in two different ways. More precisely we show Theorem 1. Given two integers n > m ≥ 2, there are infinitely many non isometric pairs (M, L) where M is a fibred hyperbolic 3-manifold and L a fivecomponent link contained in another fibred hyperbolic 3-manifold |O| such that M is a 2mn-sheeted branched cover of L in two non-equivalent ways.

Here L is transverse to the fibration of the manifold in which it is contained. As a straightforward consequence of the above result, we obtain Corollary 2. There are infinitely many pairs of non-isometric hyperbolic 3orbifolds that have the same topological type and volume.

Indeed, the two orbifolds of each pair mentioned in the corollary are obtained as quotients of M by the action of two groups of order 2mn: in both cases, the space of orbits is |O| and the points with non trivial stabilisers map onto L with orders of ramification (2, 2, 2m, 2m, n) in one case and (2, 2, 2n, 2n, m) in the other.

In order to build our examples, we start by describing certain (branched) covers of surfaces. As in [LPS], the 3-manifolds and orbifolds we are looking for will be then obtained as mapping tori of pseudo-Anosov maps defined on the surfaces considered. The maps will be chosen so that they "commute" with the covering projections, indeed all maps will be lifts of a single Anosov map defined on the common quotient of all surface covers, that is a torus in this construction.

Surface covers

Given two integers n > m ≥ 2 we wish to construct two non-equivalent 2mnsheeted covers from the (closed, connected, orientable) surface S g of genus g = 6nm -n -m + 1 onto the surface of genus 2, branched over five points, with orders of ramification (2, 2, 2m, 2m, n) for the first cover and (2, 2, 2n, 2n, m) for the second one. We shall see the bases of the two covers as two 2-orbifolds: Σ 2 (2, 2, 2m, 2m, n) and Σ 2 (2, 2, 2n, 2n, m). Both orbifolds are orbifold double covers of the torus T (2, 2, 2m, 2n) with four cone points of orders (2, 2, 2m, 2n).

In order to make the construction of the different coverings easier to understand we will separate it in two different steps. In step one we will construct an mn-sheeted branched cover from S g to the orbifold Σ 5 (m, m, n, n) of genus five with four cone points of orders (m, m, n, n). In step two we will show that the orbifold Σ 5 (m, m, n, n) double covers both Σ 2 (2, 2, 2m, 2m, n) and Σ 2 (2, 2, m, 2n, 2n). Using the fact that the deck transformations of the covering constructed commute, we will also see that Σ 2 (2, 2, 2m, 2m, n) and Σ 2 (2, 2, m, 2n, 2n) have a common quotient, which is the Z/2 × Z/2 quotient of Σ 5 (m, m, n, n). This quotient will be T (2, 2, 2m, 2n). The branched covers just discussed can be summarised in the following commuting diagram of covers:

S g Σ 5 (m, m, n, n) Σ 2 (2, 2, 2m, 2m, n) Σ 2 (2, 2, m, 2n, 2n) T (2, 2, 2m, 2n)
Note that all covers associated to arrows appearing in the diagram are regular. The group of deck transformations associated to S g -→ Σ 5 (m, m, n, n) is isomorphic to Z/m × Z/n, the other being double covers, as already observed.

Step one

In this part we start by constructing a cover of order mn from the surface of genus (m -1)(n -1) onto the 2-sphere with four branch points, two of order n and two of order m. Having fixed an integer h ≥ 0 we will then adapt the construction in order to have a cover from the surface of genus g = hmn + (m -1)(n -1) onto the surface of genus h again with four branch points, two of order n and two of order m. Observe that for the case we are interested in we have h = 5 and g = 6nm -n -m + 1 = 5mn + (m -1)(n -1).

To construct the covering we want, it is sufficient to find a surface of genus (m-1)(n-1) admitting a symmetry of type Z/m×Z/n where the generators of both cyclic subgroups have fixed points belonging to precisely two orbits of the Z/m×Z/n-action. A simple way to build a surface having prescribed symmetry is to use a symmetric graph and see the surface as the boundary of a regular neighbourhood of a standard embedding of the graph in 3-space (as was done in [LPS]).

We will build a graph embedded in the 3-sphere. To make things more explicit, it is convenient to see the 3-sphere

S 3 ⊂ C 2 as the set of points (z 1 , z 2 ) such that |z 1 | 2 + |z 2 | 2 = 1. Note that S 3 admits a Z/m × Z/n-action defined on the generators as (z 1 , z 2 ) → (e 2iπ/m z 1 , z 2 ) and (z 1 , z 2 ) → (z 1 , e 2iπ/n z 2 ).
Consider now the following sets of points in 3-sphere: A = {p k = (e 2ikπ/m , 0) | k = 0, . . . , m -1} and B = {q l = (0, e 2ilπ/n ) | l = 0, . . . , n -1}. Observe that both sets are invariant by the Z/m × Z/n-action by construction. The graph we are interested in is the complete bipartite graph with sets of vertices A and B and set of edges {e kl : k = 0, . . . , m -1; l = 0, . . . , n -1} where e kl = {(cos t p k + sin t q l ) : 0 < t < π/2}. It is clear that the graph is embedded in S 3 in a Z/m×Z/n-equivariant way. Figure 2 shows the case n = 3 and m = 4, where the solid tori

{(z 1 , z 2 ) ∈ S 3 : |z 2 | 2 ≤ 1 2 } and {(z 1 , z 2 ) ∈ S 3 : |z 2 | 2 ≥ 1
2 } have their boundaries identified, and their cores are the components of a Hopf link. Figure 3 shows the whole graph for n = 2 and m = 3.

We then obtain the desired surface by taking the boundary of a sufficiently small regular and equivariant neighbourhood of the graph. Note that the Euler characteristic of our graph is m + n -nm, so it follows immediately that the genus of the boundary surface is mn -m -n + 1. We wish to stress that the fixed-point set of the cyclic subgroup of order m acting on the 3-sphere is the circle of equation z 1 = 0 containing the set B and, similarly, the fixed-point set of the cyclic subgroup of order n acting is the circle of equation z 2 = 0 containing the set A. As a consequence, nearby each point of A (respectively B) the cyclic group of order n (respectively m) has two fixed points on the surface. Since the Z/m × Z/n-action is freely transitive on the edges of the graph, it is not hard to see that the quotient of this surface by the action is a sphere with two cone points of order m and two of order n.

To construct a covering with the same type of action from the surface of genus hmn + (m -1)(n -1) onto a surface of genus h, we start by observing that the surface we have just built can be decomposed into n m-holed spheres, m n-holed spheres and mn tubes each attached on one side to some hole of a sphere of the first type and on the other to some hole of a sphere of the second type. To generalise the construction it suffices to replace each tube with a surface of genus h with two holes (see Figure 4): the boundary components of the surface are attached as the boundary components of the original tubes were.

It is obvious that one can carry out this construction in a Z/m×Z/n-equivariant way.

Step two

For the remaining coverings we follow the same strategy: we start by considering a symmetric graph embedded in R 3 . Consider the unit circle C 0 in the plane of equation x 3 = 0. In the same plane, consider four circles C i , i = 1, 2, 3, 4, of centres (1, 1, 0), (-1, 1, 0), (-1, -1, 0), and (1, -1, 0) respectively, all of radius √ 2 -1. The set Γ = ∪ 4 i=0 C i is a graph in the plane of equation x 3 = 0. By construction, Γ is invariant by the action of the π-rotations about the x 1 and x 2 axes. Once more, consider a small and invariant regular neighbourhood of Figure 4: A tube and a surface of genus h = 5 that replaces it in the construction.

Γ: its boundary is clearly a surface of genus 5. We wish to identify this surface with the quotient Σ 5 (m, m, n, n) of the cover constructed in Step one. We do so by imposing that the outermost points of intersection of the surface with the x 1 axis are the two cone points of order m and the outermost points of intersection of the surface with the x 2 axis are two cone points of order n. It is now straightforward to realise that the quotient of Σ 5 (m, m, n, n) by the πrotation about the x 1 (respectively x 2 ) axis is the orbifold Σ 2 (2, 2, 2m, 2m, n) (respectively Σ 2 (2, 2, 2n, 2n, m)). The two π-rotations commute and generate a Klein group of order four. The quotient of Σ 5 (m, m, n, n) by its action is T (2, 2, 2m, 2n).

Remark that, although the two double branched covers from the surface of genus five to that of genus two are equivalent, the 2mn-sheeted branched coverings S g -→ Σ 2 (2, 2, 2m, 2m, n) and S g -→ Σ 2 (2, 2, 2n, 2n, m) are not, for the orders of ramification are different. Notice that the two double branched covers are equivalent since the surface of genus five admits a cyclic symmetry of order four (a π/2-rotation about the x 3 -axis) which conjugates the two covering involutions. This symmetry preserves the marked points, although not their orders and generates, together with the Klein group, a dihedral group of order eight.

Mapping tori

We wish now to construct 3-manifolds as mapping tori of homeomorphisms defined on the surfaces built in the previous section. We want, moreover, that the mapping tori fulfill some extra requirements.

Lemma 3. Consider the five surfaces S g , Σ 5 (m, m, n, n), Σ 2 (2, 2, 2m, 2m, n), Σ 2 (2, 2, 2n, 2n, m), and T (2, 2, 2m, 2n) constructed in the previous section. For each of the five surfaces it is possible to choose a homeomorphism of the surface in such a way that the five chosen homeomorphisms and the associated mapping tori satisfy the following conditions.

1. Each covering of surfaces induces a covering of the corresponding mapping tori. 2. The mapping tori associated to the homeomorphisms of Σ 2 (2, 2, 2m, 2m, n) and Σ 2 (2, 2, 2n, 2n, m) are homeomorphic.

3. The cone points of Σ 2 (2, 2, 2m, 2m, n) and Σ 2 (2, 2, 2n, 2n, m) are fixed by the chosen homeomorphisms and they close up to equivalent five-component links in the mapping tori.

Proof. The first condition is easy to fulfill. Indeed, it is sufficient to choose any homeomorphism ψ of the torus which fixes four points (corresponding to the four cone points of T (2, 2, 2m, 2m)). Since we are dealing with finite covers there is a non-trivial power of ψ that lifts to all covers and, up to choosing possibly a further power, we can even ensure that the fibres of the cone points are fixed pointwise by the lift.

To ensure that the remaining two conditions hold, we need that the lifts of ψ to Σ 2 (2, 2, 2m, 2m, n) and Σ 2 (2, 2, m, 2n, 2n) are conjugate, and the conjugation maps the cone points of the first orbifold to those of the second.

To achieve this we need to start with a further quotient of our surfaces. We point out that this quotient will not be the base space of an orbifold covering with total space S g . Consider T (2, 2, 2m, 2m). If we forget the orders of the cone points we see that the symmetry of order four of the surface of genus five induces an elliptic involution of T (2, 2, 2m, 2m) which exchanges the two cone points of order two and those of orders 2m and 2n. Observe that this elliptic involution is also induced by any of the two π-rotations about the diagonals x 1 = ±x 2 in the x 3 = 0 plane of the previous construction (see Figure 5).

We can thus start with a homeomorphism ϕ of the 2-sphere quotient of the torus by the action of the elliptic involution. We require that ϕ fixes six points: two points a and b corresponding to the orbits of the cone points of T (2, 2, 2m, 2m) and four others corresponding to the orbits of the fixed-points of the elliptic involution. Up to passing to a power, we can assume that ϕ lifts to a homeomorphism ψ of the covering torus which fixes each point a 1 , a 2 in the fibre of a and b 1 , b 2 in the fibre of b. We identify this torus with T (2, 2, 2m, 2n) in such a way that a 1 and a 2 are cone points of order 2, b 1 of order 2m and b 2 of order 2n. We also require that {a i , b i } are the images of the fixed points of the π-rotation about the axis x i , i = 1, 2.

With this choice of ψ, the mapping tori associated to the lifts of ψ discussed above satisfy all given requirements.

The diagram of surface orbifold covers give thus rise to a diagram of induced 3-dimensional orbifold covers between mapping tori:

M N (m, m, n, n) O(2, 2, n, 2m, 2m) O(2, 2, m, 2n, 2n) Q(2, 2, 2m, 2m)
We stress again that here the orbifolds O(2, 2, n, 2m, 2m) and O(2, 2, 2n, 2n, m) have the same topological type, that is are homeomorphic as manifolds and their singular sets are equivalent links.

Hyperbolic structures

To ensure that our mapping tori are hyperbolic manifolds (and orbifolds) it suffices to choose the homeomorphism ψ described in the previous section to be Anosov. This can be done without considering the quotient by the elliptic involution. Indeed, each linear Anosov map commutes with the standard elliptic involution corresponding to minus the identity; in particular, the elliptic involution preserves the fixed points of the Anosov map. Now, to our purposes it is sufficient that the linear Anosov we choose has at least four fixed points that are exchanged in pairs by the hyperelliptic involution. Indeed, we only need to identify these two orbits with the set of cone points of order two, and of order 2m and 2n respectively. Since Anosov maps have periodic orbits of arbitrarily large orders, up to perhaps taking a power, we can assume that our linear Anosov has at least eight fixed points. Now the standard elliptic involution has precisely four fixed points, all other points belonging to orbits with two elements. We can thus conclude that the Anosov map has at least four points that are exchanged in pairs by the standard elliptic involution.

Note that all finite group of deck transformations can be realised as isometry groups for the hyperbolic structure of the 3-manifolds or orbifolds on which they act. Here again, since the orders of the groups acting are arbitrarily large we see that we must have infinitely many non isometric manifolds M having two non equivalent branched covers on the same link.

Also, by taking powers of ψ we obtain infinitely many commensurable examples and infinitely many links. Indeed, for a fixed choice of n > m ≥ 2, and for a fixed link L, the set of possible volumes of orbifolds with singular set L and ramifications orders of the form (2, 2, 2n, 2n, m) or (2, 2, 2m, 2m, n) must be finite. However, by taking mapping tori associated to powers of ψ the volume must grow, because they cover each other.

Note that the five-component links in |O| are fibred and hyperbolic. Indeed, the pseudo-Anosov maps defined over the surface of genus 2 with five cone points restrict to pseudo-Anosov maps of the five-punctured genus-2 surface obtained by removing the cone points.

Figure 1 :

 1 Figure 1: The orbifold Σ 5 (m, m, n, n).

Figure 2 :Figure 3 :

 23 Figure 2: A local picture of the (n, m)-complete bipartite graph with vertices on the Hopf link for n = 3 and m = 4.

Figure 5 :

 5 Figure 5: The circle pattern in the x 3 = 0-plane and the position of the cone points of orders n and m on the genus-5 surface boundary of a regular neighbourhood (not shown in the picture).

* Partially supported by the Centre for Mathematics of the University of Coimbra -UID/MAT/00324/2013, funded by the Portuguese Government through FCT/MEC and cofunded by the European Regional Development Fund through the Partnership Agreement PT2020.


Angélique Gougelet
email: angelique.gougelet@inserm.fr

Christèle Desbois-Mouthon

Non-coding RNAs open a new chapter in liver cancer treatment

Keywords: Non-coding RNAs, Liver cancer, Exosome, Therapeutic opportunities

Despite the intensive efforts to identify the molecular events responsible for the emergence of liver cancer, hepatocellular carcinoma (HCC) remains a major health problem in the world. Thus, the identification of new therapeutic opportunities is a short-term necessity. These last few decades, non-coding RNAs appeared as interesting therapeutic strategies with their pleiotropic inhibitory action in the cell itself but also in recipient cells via their secretion into extracellular vesicles. This short review recapitulates recent advancements concerning non-coding RNAs and their deregulations in liver cancer.

Introduction

For decades, proteins were believed to carry hereditary information, in particular during bacterial transformation described by the microbiologist Frederick Griffith in 1928.

Abbreviations: circRNA, circular RNA; EMT, epithelial to mesenchymal transition; HCC, hepatocellular carcinoma; LINE, long interspersed nuclear elements; LNA, locked nucleic acid; lncRNA, long non-coding RNA; miRNA, microRNA; ncRNA, non-coding RNA; piRNA, piwiRNA; RISC, RNA-Induced silencing complex; RNP, ribonucleoprotein; P-bodies, processing bodies; pre-miRNA, precursor miRNA; pri-miRNA, primary miRNA; PDX, patient-derived xenograft; SINE, short interspersed nuclear elements; snRNA, small nuclear RNA; SNAP, Soluble N-ethylmaleimide-sensitive-factor attachment protein; SNARE, SNAP Receptor; snoRNA, small nucleolar RNA.

* Corresponding author at: 15, rue de l'école de médecine, 75006

Nevertheless, fifteen years later, this precept was questioned by the experiment of Oswald Avery, Colin MacLeod, and Maclyn McCarty in 1944, which demonstrated that DNA was the hereditary genetic material controlling the pathogenicity of the bacteria [START_REF] Lederberg | The transformation of genetics by DNA: an anniversary celebration of Avery, MacLeod and McCarty[END_REF]. After years of consolidating experiments, the scientific community assumed that DNA makes us who we are. Therefore, over several decades, proteins that result from DNA genetic information were credited to be the master regulators of cell behavior. It had to wait for the 2000s and the opportunity of whole exome sequencing to crush the concept of DNA world and open the new era of a RNA world. Indeed, the human genome only contains a tiny fraction of protein-coding genes, supporting that RNA play a more substantial role than originally believed [START_REF] Bertone | Global identification of human transcribed sequences with genome tiling arrays[END_REF]. The rest of the genome is nonetheless actively transcribed into RNAs without coding potential, and called non-coding RNAs (ncRNAs). NcRNAs are partitioned into repetitive DNA, which constitute the largest fraction (40-50%), including:

• telomeres;

• transposable elements (long (LINE) and short interspersed nuclear elements (SINE)); • introns (approximately 25%); • miscellaneous sequences [START_REF] Lander | Initial sequencing and analysis of the human genome[END_REF].

Non-protein-coding DNA sequences, once considered as junk DNAs, proportionally increase with evolution complexity from prokaryotes to mammals, reaching more than 98% of the human genome ( [START_REF] Palazzo | Non-coding RNA: what is functional and what is junk?[END_REF] for a review). This discovery has shaken the conscience and largely modified our understanding of complex diseases like cancer. Scientists now face major issues to unveil the precise biological functions of these non-coding RNAs and the impact of their deregulations in pathological processes. And, even if crucial roles in gene regulations have been assigned to a great majority of these sequences, non-coding RNAs globally remain a mysterious world to explore.

Non-coding RNA biogenesis

NcRNAs are arbitrarily divided into two categories, small (< 200 nucleotides (nt)) and long non-coding RNAs (lncRNAs) (>200 nucleotides) [START_REF] Kapranov | RNA maps reveal new RNA classes and a possible function for pervasive transcription[END_REF]. Small ncRNAs notably include:

• Piwi-interacting RNAs (piRNAs), mainly identified in germ cells to silence genetic elements such as transposons [START_REF] Ozata | PIWIinteracting RNAs: small RNAs with big functions[END_REF]; • small nucleolar RNAs (snoRNAs), that guide chemical modifications of other RNAs [START_REF] Dupuis-Sandoval | The emerging landscape of small nucleolar RNAs in cell biology[END_REF]; • small nuclear RNAs (snRNAs), found within the spliceosome [START_REF] Matera | A day in the life of the spliceosome[END_REF]; • the most widely characterized ncRNAs, the microRNAs (miRNAs), involved in post-transcriptional gene silencing [START_REF] He | MicroRNAs: small RNAs with a big role in gene regulation[END_REF].

Long non-coding RNAs are generally 1,000-10,000 residues in length and refer to natural antisense transcripts and other regulatory long non-coding RNAs [START_REF] Mercer | Long non-coding RNAs: insights into functions[END_REF]. Based on their proximity to protein-coding genes, miRNAs and lncR-NAs have been classified into exonic, intronic and intergenic ncRNAs and quite commonly produced in a polycistronic manner. Although biogenesis and biological functions differ for all ncRNAs, and more notably for lncRNAs, small ncRNA biogenesis shares several similarities with RNA interference pathway [START_REF] Tang | siRNA and miRNA: an insight into RISCs[END_REF] (Fig. 1). RNA-processing proteins usually cleave primary transcripts of small ncRNAs into small RNA fragments. Then, processed ncRNAs are loaded into the multi-protein machinery called RISC (RNA-induced silencing complex), which helps in Argonaute recruitment. Argonaute proteins are evolutionarily conserved and phylogenetically subdivided into the Ago subclass, for miRNA and siRNA processing, and the Piwi subfamily that binds to piRNAs [START_REF] Hock | The Argonaute protein family[END_REF]. Both Argonaute protein subfamilies have the common capacity to repress gene expression following binding of associated small guiding RNAs on complementary seed sequences in target genes.

In contrast, lncRNA biogenesis shares many features with protein-coding RNAs. LncRNAs are often 5 -capped, spliced and 3 polyadenylated, but they are shorter in length, do not possess open-reading frames and are expressed in lower abundance. After processing, lncRNA play scaffolding roles to form ribonucleoprotein complexes (RNP) without processing activity. Growing evidence points that lncRNA functions are associated with their subcellular localization [START_REF] Chen | Linking Long Noncoding RNA Localization Function[END_REF]. They function as signal, decoy, scaffold, guide or enhancer, to promote chromatin modification, transcription, translation, splicing, mRNA decay, protein transport and assembly [START_REF] Wang | Molecular mechanisms of long noncoding RNAs[END_REF].

Recently, the landscape of ncRNAs has been remarkably expanded with the emergence of next-generation sequencing and the development of robust bioinformatics tools [START_REF] Veneziano | Computational Approaches for the Analysis of ncRNA through Deep Sequencing Techniques[END_REF]. In particular, the pattern of human piRNAs switched from about 32,000 identified piRNA sequences in 2014 to reach 8 millions in the second piRBase release published in 2018 [START_REF] Wang | piRBase: a comprehensive database of piRNA sequences[END_REF]. Similarly, Lncipedia catalogs around 50,000 genes of LnRNAs in human [START_REF] Volders | LNCipedia: a database for annotated human lncRNA transcript sequences and structures[END_REF], while miRBase refers 1,917 human miRNAs, a number in continuous increase [START_REF] Alles | An estimate of the total number of true human miRNAs[END_REF]. Finally, another widespread and abundant class of non-coding RNAs has been identified in 2012 with the improvement of deep-sequencing, which is called circular RNAs (circRNAs). These RNAs transcriptionally produced from thousand of genes exhibit covalently linked 3 and 5 ends and frequently show a higher expression than their linear isoforms [START_REF] Salzman | Circular RNAs are the predominant transcript isoform from hundreds of human genes in diverse cell types[END_REF].

NcRNAs and liver cancer

These recent decades, researchers have paid growing interest for ncRNAs due to their pleiotropic regulating potentials and their ubiquitous distribution in mammalian cells. Now, ncRNAs are defined as versatile cellular switch for good or ill. Accordingly to several deregulations in ncRNA expression observed in various tumors, it is not surprising that the numbers of publications concerning ncRNAs and cancer are constantly increasing: slowly for snoRNAs and piRNAs, reported to be associated with cancer these last years (123 and 186 items in PUBMED respectively), but more intensively for LncRNA (5,182 items) and miRNAs (16,358 items). CircRNAs have already reached 84 items with cancer. Their potential as non-invasive prognostic and predictive biomarkers is substantial since ncRNAs have been detected in a great diversity of body fluids, such as blood, urine and saliva.

microRNAs

Since their discovery at the end of the 1990s, miRNAs are the best-characterized small ncRNAs. The transcription of primary transcripts of miRNAs (pri-miRNAs) is firstly driven by the RNA polymerase II. In about 15% of cases, pri-miRNAs derive from polycistronic miRNA transcripts. Pri-miRNAs are processed by specific complexes of proteins containing Drosha and Dicer, to become mature (pre-miRNAs). Then, they are integrated in RISC complexes to match with complementary sequences mainly located in the 3 UTR (untranslated transcribed region) of mRNAs, resulting in most cases in translation inhibition and accelerated mRNA degradation in subcellular compartments called processing bodies (P-bodies) [START_REF] Hutvagner | A microRNA in a multiple-turnover RNAi enzyme complex[END_REF][START_REF] Lee | MicroRNA maturation: stepwise processing and subcellular localization[END_REF]. MiRNAs are from [START_REF] Wang | piRBase: a comprehensive database of piRNA sequences[END_REF] miRNA expression is also largely described in a variety of tumors. MiRNA signature can be characteristic of each tumor type in line with its tissue origin and the driven molecular alterations [START_REF] Lu | MicroRNA expression profiles classify human cancers[END_REF]. By their multiplicity of action and their tissue-specific distribution, miRNAs have been pointed as robust therapeutic candidates, and potent biomarkers for cancer diagnosis. MiRNA expression has been largely found disturbed during hepatocarcinogenesis [START_REF] Ladeiro | MicroRNA profiling in hepatocellular tumors is associated with clinical features and oncogene/tumor suppressor gene mutations[END_REF], with specific miRNA deregulations at each step before HCC development, from liver disease to cirrhosis [START_REF] Gougelet | MicroRNAs linking cancer and inflammation: Focus on liver cancer[END_REF]. MiR-122 emerges as the most hopeful miRNA with diagnostic, prognostic and therapeutic potentials. It is the most abundant miRNA in the adult liver, whose expression is largely altered during non-alcoholic steatohepatitis [START_REF] Cheung | Nonalcoholic steatohepatitis is associated with altered hepatic MicroRNA expression[END_REF] and in HCC, in the liver/tumor but also in the serum [START_REF] Gougelet | Hepatocellular carcinoma diagnosis: Circulating microRNAs emerge as robust biomarkers[END_REF]. This year, Teufel and coworkers have identified a plasmatic signature of nine miRNAs including miR-122 (miR-122, miR-30a, miR-125b, miR-200a, miR-374b, miR-15b, miR-107, miR-320, and miR-645), which is significantly associated with patient overall survival during regorafenib treatment [START_REF] Teufel | Biomarkers Associated With Response to Regorafenib in Patients With Hepatocellular Carcinoma[END_REF]. In addition, miR-135a, a miRNA upregulated in HCC [START_REF] Van Renne | miR-135a-5p-mediated downregulation of protein tyrosine phosphatase receptor delta is a candidate driver of HCV-associated hepatocarcinogenesis[END_REF], has been also described as a promising prognostic factor [START_REF] Huang | Factor VII-Induced MicroRNA-135a Inhibits Autophagy and Is Associated with Poor Prognosis in Hepatocellular Carcinoma[END_REF], since its expression is associated with recurrence after tumor resection [START_REF] Von Felden | High expression of micro RNA-135A in hepatocellular carcinoma is associated with recurrence within 12 months after resection[END_REF].

In addition to their prognostic benefit, miRNAs could also be useful as therapeutic opportunities in HCC. Importantly, the first miRNA-based therapy to enter into clinical trials was an anti-miR-122 against hepatitis C virus based on the locked nucleic acid technology (LNA)-the virus perverting miR-122 in hepatocytes for its replication [START_REF] Janssen | Treatment of HCV Infection by Targeting MicroRNA[END_REF]. MiRNA-based therapies appear as promising therapeutic strategies as they simultaneously impact on proliferation, metabolic features and immune contexture of liver tumors. MiRNA-based therapies have been successfully tested in liver diseases and cancers (LNA against miR-34a, 2-O-metoxyethyl anti-miR-191) [START_REF] Gougelet | MicroRNAs linking cancer and inflammation: Focus on liver cancer[END_REF][START_REF] Gougelet | Antitumour activity of an inhibitor of miR-34a in liver cancer with beta-catenin-mutations[END_REF] -this type of molecules being preferentially delivered to the liver [START_REF] Roberts | Efficient and persistent splice switching by systemically delivered LNA oligonucleotides in mice[END_REF]. Mimic-based therapies have also been tested to increase the expression of tumor suppressive Please cite this article in press as: Gougelet miRNAs. Mimics of miR-34a and Let-7 encapsulated into liposomes have been developed by the miRNAtherapeutics company and tested in HCC. Despite interesting results, their use in patients has been limited because of offside effects of mimics and/or toxicity of liposomes leading to immune dysfunction [START_REF] Beg | Phase I. study of MRX34, a liposomal miR-34a mimic, administered twice weekly in patients with advanced solid tumors[END_REF]. A number of challenges are yet to be addressed to improve the efficiency of miRNA-based therapies and reduce the current limitations concerning their stability, administration, specificity, distribution and secondary effects. The recent use of endogenous vesicles called exosomes could be a promising alternative, as developed at the end of this review.

Small nucleolar RNAs

SnoRNAs are usually localized in the nucleolus, a dense zone in the nucleus. They are from 60 to 300nt in length and constitute a conserved class of small non-coding RNAs anciently spread by retrotransposition [START_REF] Terns | Small nucleolar RNAs: versatile transacting molecules of ancient evolutionary origin[END_REF]. SnoRNAs are expressed in all eukaryotes, incorporated into small nucleolar ribonucleoprotein complexes (snoRNPs) with specific conserved protein partners to usually serve as guides for the chemical modifications of other non-protein-coding RNAs: either 2 -O-methylation of target RNAs (box C/D snoRNAs), or pseudouridylation (box H/ACA snoRNAs). However, recent studies revealed that snoRNAs display common features with miR-NAs for their genomic location, processing pathways and integration in RISC complexes [START_REF] Scott | From snoRNA to miRNA: Dual function regulatory non-coding RNAs[END_REF]. Although most snoRNAs were originally thought able to modify ribosomal RNAs for translation, a subgroup of snoRNAs has been shown to target small nuclear RNAs, tRNAs and mRNAs or even to be involved in rRNA processing.

Until very recently, snoRNA dysfunction had not been studied in cancer. However, works performing genomic analysis of snoRNAs in tumors highlighted their aberrant expression levels in cancer, including HCC [START_REF] Yang | Genomic analysis of small nucleolar RNAs identifies distinct molecular and prognostic signature in hepatocellular carcinoma[END_REF]. Su and coworkers were the first to report in tumor tissues a frequent overexpression of fibrillarin, a protein component of C/D box snoRNP [START_REF] Su | Elevated snoRNA biogenesis is essential in breast cancer[END_REF], in correlation with elevated amount of snoRNA clusters. Last year, the snoRNA snoU2 19, which is upregulated in HCC, has been found to play an oncogenic role through Wnt/␤-catenin pathway activation [START_REF] Wang | Small nucleolar RNA U2 19 promotes hepatocellular carcinoma progression by regulating Wnt/beta-catenin signaling[END_REF]. Another snoRNA regulating the Wnt/␤-catenin pathway and promoting liver tumorigenesis is SNORD76, whose expression is increased in HCC tissues and associated with poorer patient survival [START_REF] Wu | Clinical significance of C/D box small nucleolar RNA U76 as an oncogene and a prognostic biomarker in hepatocellular carcinoma[END_REF]. Altogether, these observations support potent roles of snoRNA pathways in cancer. It remains to unravel how snoRNAs are deregulated and precise their roles during tumorigenesis to open new opportunities for therapeutic intervention.

PiwiRNAs

piRNAs are preferentially detected in germ line and are usually 25-31nt in length [START_REF] Brennecke | Discrete small RNA-generating loci as CLINRE-1303; No. of Pages 8 Non-coding RNAs open a new chapter in liver cancer treatment 7 master regulators of transposon activity in Drosophila[END_REF]. They are characterized by their outstanding diversity of millions of sequences, poorly conserved but with a genomic localization commonly shared among species. The best-characterized class of piRNAs is repeat-associated piRNAs, guardians of transposon invasion. Another class of piRNAs called pachytene piRNAs, originating from the 3 UTR regions of mRNAs or from intergenic lncRNAs, exhibits unknown targets and functions [START_REF] Robine | A broadly conserved pathway generates 3'UTR-directed primary piRNAs[END_REF]. The mechanisms underlying piRNA biogenesis and functions are still elusive, due to the lack of easy-to-use in vitro models, and because little is common with the miRNA system. In contrast with miRNAs, repeat-associated piRNAs are produced from long single-stranded piRNA clusters independently to RNAse processing [START_REF] Ishizu | Biology of PIWI-interacting RNAs: new insights into biogenesis and function inside and outside of germlines[END_REF]. One mechanism of biogenesis is named ping-pong cycle creating secondary piRNAs, which target the initial piRNA clusters, amplifying the pattern of piRNAs. They bear 2 -O-methyl-modified 3 termini recognized by the PIWI subfamily members of the Argonaute family, and prefer uracil in 5 -termini of their targets. By this repeated endonucleolytic cleavage, piRNAs guard the germline genome against detrimental DNA damage induced by multiplication and insertion of mobile transposons. Their major role aims at preserving spermatogenesis, a period of global epigenetic remodeling [START_REF] Carmell | MIWI2 is essential for spermatogenesis and repression of transposons in the mouse male germline[END_REF]. PiRNA-mediated transposon silencing could also be induced by epigenetic regulation during germline development by DNA and histone H 3 K 9 me 3 methylation [START_REF] Kuramochi-Miyagawa | DNA methylation of retrotransposon genes is regulated by Piwi family members MILI and MIWI2 in murine fetal testes[END_REF]. PiRNAs are also required to silence the paternally imprinted gene RASGFR1 during de novo methylation [START_REF] Watanabe | Role for piRNAs and noncoding RNA in de novo DNA methylation of the imprinted mouse Rasgrf1 locus[END_REF]. As a methylation inducer, the impact of piRNAs during cancer development could be a consistent question. These later years, some works have profiled piRNA expression and explored their biological functions in cancer, including liver cancer [START_REF] Law | Deep sequencing of small RNA transcriptome reveals novel non-coding RNAs in hepatocellular carcinoma[END_REF][START_REF] Rizzo | Specific patterns of PIWI-interacting small noncoding RNA expression in dysplastic liver nodules and hepatocellular carcinoma[END_REF]. In particular, piR-Hep1 was found to be upregulated in half of HCC tumors and piR-Hep1 silencing inhibited cell viability, motility, and invasiveness via a reduction of AKT phosphorylation. The PIWI pathway also seems to be involved in the maintenance of cancer stemness and particularly in the resistance to chemotherapies [START_REF] Weng | Piwi-interacting RNAs (piRNAs) and cancer: Emerging biological concepts and potential clinical implications[END_REF]. These data gave new insights into liver tumorigenesis and support that piRNAs might be new disease biomarkers and could result in innovative treatment strategies.

Lon non-coding RNAs

LncRNAs are the class of ncRNAs, which currently knows the biggest attention from the scientific community. LncRNAs are transcribed by the RNA polymerase II from intergenic regions (lincRNAs), introns or enhancers in sense, antisense or bidirectional manner [START_REF] Derrien | The GENCODE v7 catalog of human long noncoding RNAs: analysis of their gene structure, evolution, and expression[END_REF]. They are frequently polyadenylated. Their sequences are poorly conserved among species, challenging the comprehension of their underlying mechanisms. As for other ncRNAs, the number of lncRNAs is directly proportional to organism complexity. They exhibit a great diversity of sequences and structures and postulated to account for the majority of the non-coding transcriptome (50,000 lncRNAs are currently defined). LncR-NAs display a tissue-specific pattern of expression and are finely regulated in time and space across the stages of development. In contrast to other ncRNAs, lncRNAs are predominantly nuclear and interact with ribonucleoproteins to control:

• transcription, either positively (ribosome guide, scaffold for transcriptional activators, chromatin remodelers, signal for transcription) or negatively (decoy, recruitment of transcriptional repressors); • chromatin architecture (chromosome loops and interchromosomal interactions) [START_REF] Marchese | The multidimensional mechanisms of long noncoding RNA function[END_REF].

•
Panels of lncRNAs have been shown to play essential roles during embryogenesis [START_REF] Ulitsky | Conserved function of lincRNAs in vertebrate embryonic development despite rapid sequence evolution[END_REF] and tumorigenesis [START_REF] Huarte | The emerging role of lncRNAs in cancer[END_REF], due to their regulatory roles in proliferation, differentiation, stress response and survival. Numbers of LncRNAs have been recently associated with HCC, and particularly with epithelial-to-mesenchymal transition (EMT), stem cell features and tumor invasion: lncRNA DANCR [START_REF] Yuan | Long noncoding RNA DANCR increases stemness features of hepatocellular carcinoma by derepression of CTNNB1[END_REF], hPVT1 [START_REF] Wang | Oncofetal long noncoding RNA PVT1 promotes proliferation and stem cell-like property of hepatocellular carcinoma cells by stabilizing NOP2[END_REF], lncTCF7 [START_REF] Wang | The long noncoding RNA lncTCF7 promotes self-renewal of human liver cancer stem cells through activation of Wnt signaling[END_REF] or ATB [START_REF] Yuan | A long noncoding RNA activated by TGF-beta promotes the invasionmetastasis cascade in hepatocellular carcinoma[END_REF]. Others have been associated with HCC development and progression such as MEG3 [START_REF] Braconi | microRNA-29 can regulate expression of the long noncoding RNA gene MEG3 in hepatocellular cancer[END_REF], H19 [START_REF] Matouk | The H19 non-coding RNA is essential for human tumor growth[END_REF], MALAT-1 [START_REF] Lai | Long noncoding RNA MALAT-1 overexpression predicts tumor recurrence of hepatocellular carcinoma after liver transplantation[END_REF] or TUG1 [START_REF] Huang | Long non-coding RNA TUG1 is up-regulated in hepatocellular carcinoma and promotes cell growth and apoptosis by epigenetically silencing of KLF2[END_REF]. The first lncRNA identified as overexpressed in HCC is HULC (highly upregulated in liver cancer) [START_REF] Panzitt | Characterization of HULC, a novel gene with striking up-regulation in hepatocellular carcinoma, as noncoding RNA[END_REF], and thus the most studied. It regulates HCC proliferation, angiogenesis, lipid metabolism, autophagy and sensitivity to chemotherapies [START_REF] Xiong | LncRNA HULC triggers autophagy via stabilizing Sirt1 and attenuates the chemosensitivity of HCC cells[END_REF]. HULC expression predicts better outcomes [START_REF] Yang | HULC and H19 Played Different Roles in Overall and Disease-Free Survival from Hepatocellular Carcinoma after Curative Hepatectomy: A Preliminary Analysis from Gene Expression Omnibus[END_REF] and may functions as a non-invasive potent biomarker [START_REF] Li | HULC and Linc00152 Act as Novel Biomarkers in Predicting Diagnosis of Hepatocellular Carcinoma[END_REF]. Another interesting lncRNA is CASC9, upregulated in half of HCCs and associated with lower recurrence after surgery [START_REF] Gramantieri | LncRNAs as novel players in hepatocellular carcinoma recurrence[END_REF]. This study also highlights CASC9 as a putative non-invasive prognostic biomarker in HCC since higher level of circulating CASC9 is correlated with tumor size and HCC recurrence. Regarding to the large amount of lncRNAs implicated in HCC, these RNAs represent rational candidates for innovative therapy using RNAi approach, small inhibitory molecules or modulators of their secondary structures. The last three months, a study obtained encouraging results with nanoparticles delivering an inhibitor of the LncRNA TUG1, which exhibit antitumour activity on pancreatic and brain PDX (patient-derived xenograft) models [START_REF] Wu | Clinical significance of C/D box small nucleolar RNA U76 as an oncogene and a prognostic biomarker in hepatocellular carcinoma[END_REF]. In addition, MALAT-1 appears as a potent druggable lncRNA using LNA-Gapmer in multiple myeloma and probably other tumors [START_REF] Amodio | Drugging the lncRNA MALAT1 via LNA gapmeR ASO inhibits gene expression of proteasome subunits and triggers anti-multiple myeloma activity[END_REF], opening potential new avenues in molecular medicine based on lncRNAs.

Circular RNAs

As previously mentioned, the landscape of circRNAs has rapidly grown with improvement of next-generation sequencing, to reach more than 100,000 circRNAs identified in humans [START_REF] Ji | Expanded Expression Landscape and Prioritization of Circular RNAs in Mammals[END_REF]. In most cases, circRNAs are generated by alternative splicing of pre-mRNAs called backsplicing but expressed independently of their linear isoforms [START_REF] Memczak | Circular RNAs are a large class of animal RNAs with regulatory potency[END_REF]. Thus, circRNA biogenesis competes with linear splicing because of overlapping dependence on the spliceosome. Accordingly to their recent discovery, the understanding of how circRNAs participate in biological processes is still preliminary. However, circRNAs have been extensively described as microRNA sponges [START_REF] Hansen | Natural RNA. circles function as efficient microRNA sponges[END_REF] but also as transcriptional and translational modulators [START_REF] Huang | The emerging role of circular RNAs in transcriptome regulation[END_REF]. Hundreds of circRNAs have been described deregulated in human cancers, including in liver cancer [START_REF] Fu | Circular RNAs in hepatocellular carcinoma: Functions and implications[END_REF], and thus may serve as potential biomarkers [START_REF] Vo | The Landscape of Circular RNA in Cancer[END_REF]. They could act either as oncogenes or tumor suppressors through regulatory actions on cell proliferation, invasion or EMT [START_REF] Wang | Characteristics, Function and Clinical Significance in Hepatocellular Carcinoma[END_REF]. Circ 100338 [START_REF] Huang | CircRNA-100338 Is Associated With mTOR Signaling Pathway and Poor Prognosis in Hepatocellular Carcinoma[END_REF] and circ 0078602 [START_REF] Kou | hsa circ 0078602 may have potential as a prognostic biomarker for patients with hepatocellular carcinoma[END_REF] are associated with poor prognosis in HCC patients. CircRNA-based research is still in its infancy. The main challenge in future to make circRNAs as powerful candidates for cancer therapy will be circRNA targeting without detrimental interfering with linear RNA expression.

Exosomal ncRNAs as therapeutic and diagnostic candidates

Exosomes are double membrane cell-derived microvesicles from 30 to 100 nm in diameter, containing nucleic acids (> 3,400 mRNAs and 2,800 miRNAs according to Exocarta) and proteins (> 9700) [START_REF] Keerthikumar | ExoCarta: A Web-Based Compendium of Exosomal Cargo[END_REF]. Most cells, and particularly immune cells, are physiologically secreting exosomes originated from multivesicular bodies (MVB), whose fusion with the plasma membrane is orchestrated by Rab, SNAP (Soluble N-ethylmaleimide-sensitive-factor attachment protein) and SNARE (SNAP Receptor) proteins [START_REF] Thery | Exosomes:. composition, biogenesis and function[END_REF]. During tumorigenesis, tumor cells aberrantly secrete exosomes to communicate with stromal cells, such as the lncRNA TUC339 secreted from HCC cells towards the surrounding macrophages to promote tumor growth and spreading [START_REF] Li | Regulation of Macrophage Activation and Polarization by HCC-Derived Exosomal lncRNA TUC339[END_REF]. Interestingly, a very recent work reciprocally showed that adipose tissue secrete exosomal circRNA circ-DB (hsa circ 0025129) to favor HCC growth, providing new insights into the understanding of the association between adipose tissue and HCC [START_REF] Zhang | Exosome circRNA secreted from adipocytes promotes the growth of A. Gougelet, C. Desbois-Mouthon hepatocellular carcinoma by targeting deubiquitinationrelated USP7[END_REF]. Exosomes are also useful for tumor cells to modify secondary recipient sites and to subsequently favor metastasis [START_REF] Kalluri | The biology and function of exosomes in cancer[END_REF]. The detection of exosomal ncRNAs in body fluids is thus a valuable non-invasive diagnosis tool for cancer, including HCC. This has been extensively described in literature for miRNAs [START_REF] Gougelet | Hepatocellular carcinoma diagnosis: Circulating microRNAs emerge as robust biomarkers[END_REF], such as miR-221 [START_REF] Li | Expression of serum miR-221 in human hepatocellular carcinoma and its prognostic significance[END_REF] or miR-224 [START_REF] Lin | Serum miR-224 as a biomarker for detection of hepatocellular carcinoma at early stage[END_REF], but also miR-21 and other ncRNAs like LncRNA-ATB [START_REF] Lee | Circulating exosomal noncoding RNAs as prognostic biomarkers in human hepatocellular carcinoma[END_REF], and circSMARCA5 [START_REF] Li | Using circular RNA SMARCA5 as a potential novel biomarker for hepatocellular carcinoma[END_REF].

Additionally, exosomes offer an attractive modality for personalized cancer treatment [START_REF] Gougelet | Exosomal microRNAs as a potential therapeutic strategy in hepatocellular carcinoma[END_REF]. They have been used as a targeted delivery system for chemotherapeutic agents, leading to cancer cell killing and promoting a domino effect through the release of secondary cytotoxic vesicles [START_REF] Tang | Delivery of chemotherapeutic drugs in tumour cell-derived microparticles[END_REF]. Importantly, new encouraging works have been obtained by injection of stellate cell-derived exosomes in mice developing liver cancer. Exosomes incorporating mimics of miRNAs have successfully impaired tumor cell proliferation and favored apoptosis in vivo [START_REF] Li | Extracellular vesicles carry microRNA-195 to intrahepatic cholangiocarcinoma and improve survival in a rat model[END_REF][START_REF] Wang | Exosome miR-335 as a novel therapeutic strategy in hepatocellular carcinoma[END_REF]. To avoid limitations associated with patient-derived exosomes (expensive and complex production, time consuming, poorly reproducible), a promising alternative is the synthesis of bioengineered exosome mimetics, more suitable for clinical use [START_REF] Wu | Exosome-Mimetic Nanovesicles from Hepatocytes promote hepatocyte proliferation in vitro and liver regeneration in vivo[END_REF].

Conclusion

In conclusion, this review describes how ncRNA could represent in future promising tools for the treatment of liver cancer. The current advances in the field of nanotechnologies might facilitate delivery of ncRNA-based therapeutics in favor of clinical studies. Further studies are thus critically needed to precisely unravel the impact of ncRNA deregulations in cancer and how they could be counteracted to finalize clinical trials in the coming years.

3 Figure 1

 31 Figure 1The great diversity of biogenesis and action of non-coding RNA world. NcRNAs are divided into small ncRNAs (< 200 nt) including piRNAs, snoRNAs and miRNAs, and long non-coding RNAs (> 200 nt) consisting of lncRNAs and circRNAs. Pre-miRNAs processed from pri-miRNAs are integrated in RISC complexes to impair translation and accelerate mRNA degradation. SnoRNAs serve as guides for the 2 -O-methylation chemical and pseudouridylation of other RNAs. piRNAs are produced from long singlestranded piRNA clusters and engaged into a ping-pong cycle to protect the genome from transposon invasion. LncRNAs control transcription, either positively or negatively, mRNA stability and translation and chromatin architecture. circRNAs generated by alternative splicing of pre-mRNAs act as microRNA sponges and transcriptional and translational modulators. This landscape of ncRNAs finely regulate gene program and thus cell function and fate. Disequilibrium in their expression could favor liver disease and promote liver tumorigenesis. NcRNAs could also be secreted from tumor and immune cells into exosomes to modulate cell fate in their neighborhood or at a distance to favor metastasis. CircRNA: circular RNA, LncRNA: long non-coding RNA, miRNA: microRNA, MVB: multivesicular bodies, P-bodies: processing bodies, Pi-P-bodies: processing bodies for piRNAs, piRNA: PiwiRNA, snoRNA: small nucleolar RNA.

  A, Desbois-Mouthon C. Non-coding RNAs open a new chapter in liver cancer treatment. Clin Res Hepatol Gastroenterol (2019), https://doi.org/10.1016/j.clinre.2019.07.005 ARTICLE IN PRESS +Model CLINRE-1303; No. of Pages 8 A. Gougelet, C. Desbois-Mouthon

  mRNA stability and translation (miRNA sponge); Please cite this article in press as: Gougelet A, Desbois-Mouthon C. Non-coding RNAs open a new chapter in liver cancer treatment. Clin Res Hepatol Gastroenterol (2019), https://doi.org/10.1016/j.clinre.2019.07.005 ARTICLE IN PRESS +Model CLINRE-1303; No. of Pages 8 Non-coding RNAs open a new chapter in liver cancer treatment 5

Funding

AG was supported by the Ligue Nationale Contre le Cancer and the Agence Nationale de la Recherche (DLK1-EPILIV 2018-2020). CDM was supported by the Ligue Nationale

Contre le Cancer and the Association contre le Cancer (grant 20171206548).

Disclosure of interest

The authors declare that they have no competing interest.


Smaine Mazouzi
email: mazouzi@leri.univ-reims.fr

Zahia Guessoum
email: zahia.guessoum@lip6.fr

Fabien Michel
email: fmichel@leri.univ-reims.fr

Mohamed Batouche
email: batouche@wissal.dz

A Multi-agent Approach for Range Image Segmentation

Keywords: Image segmentation, Multi-agent systems, Range image, Agent coordination, Artificial potential field

This paper presents and evaluates a multi-agent approach for range image segmentation. A set of reactive and autonomous agents perform a collective segmentation by partitioning a range image in its different planar regions. The agents move over the image and perform cooperative and competitive actions on the pixels, allowing a robust region extraction, and an accurate edge detection. An artificial potential field, created around the pixels of interest, ensures the agent coordination. It allows the agents to concentrate their actions around the edges and the noise regions. The experimental results show the potential of the proposed approach for scene understanding in range images, regarding both segmentation efficiency, and detection accuracy.

Introduction

Image segmentation consists in assigning the pixels of an image to homogenous and disjoint subsets, providing a compact and convenient description of the image. In range imagery, segmentation algorithms can be divided into two dual categories: edge-based segmentation algorithms and region-based segmentation algorithms. In the first category, pixels that correspond to discontinuities in depth or in surface normals are selected, chained and then used to delimit the regions in the image [START_REF] Inokuchi | A three dimensional edge-region operator for range pictures[END_REF][START_REF] Jiang | Edge detection in range images based on Scan Line approximation[END_REF]. Region-based methods use geometrical surface descriptors to group pixels, with the same proprieties, in disjoint regions [START_REF] Kang | The complex EGI: A new representation for 3-D pose determination[END_REF][START_REF] Li | Gradient-based polyhedral segmentation for range images[END_REF][START_REF] Ding | Range image segmentation based on randomized hough transform[END_REF][START_REF] Hadiashar | Range image segmentation using surface selection criterion[END_REF]. In both categories, algorithms must deal with noisy and uncertain data.

To overcome this difficulty, some authors have proposed multi-agent systems for 2-D image segmentation. Solutions provided by such systems inherit the advantages of the agent-oriented approach for collective problem solving. In such systems a single agent has a limited perception and limited capabilities, and it is not designed to solve an entire problem. Agents cooperate thus in order to provide a collective solution. Contrary to conventional systems, solutions in multi-agent systems emerge from the collective action of interactive agents [START_REF] Krishnamurthy | Distributed agent paradigm for soft and hard computation[END_REF].

In this paper, a new multi-agent approach for range image segmentation is presented and discussed. It consists in the use of reactive agents, which move over the image, and act on the visited pixels. While moving over the image, an agent adapts to the planar region on which it moves, and memorizes its proprieties. At the boundaries between regions, the agents will be in competition to align the pixels of the boundaries to their respective regions. The resulting alternative alignment of the boundary pixels preserves the region boundaries against smoothing. Noise regions, which are characterized by small sizes or by aberrant depths (outliers), prevent agents from adapting. So, the pixels on their borders are continuously aligned to the true regions that surround them. After several iterations these regions will entirely disappear.

This work aims to overcome the difficulty related to the local perception around the processed pixel. A pixel is therefore processed according to both its neighborhood, and the agents that visit this pixel. An agent acts on the pixels with more certainty, acquired from its move on large areas on the image regions. The combination of the global information memorized within the agent, and the local information of the image, provides more reliable decisions. We show in this work that despite the simplicity of the model used to represent the image surface, the obtained results are better than those provided by conventional approaches. We believe that interactions between agents provide an alternative way for image segmentation to that of approaches based on complicated and costly models. Extensive experiments have been performed using real images from the ABW database [5]. The obtained results show the high potential of the proposed approach for an efficient and accurate segmentation of range images.

The remainder of the paper is organized as follows: In Section 2, we review some agent-based approaches for image segmentation. Section 3 is devoted to the proposed approach. It describes the behavior of the agents, and shows the underlying collective mechanism to deal with the edge detection and the noise removal. The experimental results are introduced in Section 4, in which we discuss the parameter selection, and we analyze and comment the obtained results. Finally, a conclusion summarizes our contribution.

Related Work

Several agent-based systems have been proposed to deal with various problems in image analysis and object recognition. In this review we consider only some works that have addressed a solution in image segmentation.

Liu et al. [START_REF] Liu | Adaptive image segmentation with distributed behavior-based agents[END_REF] introduce a reactive agent-based system for brain MRI segmentation. Four types of agents are used to label the pixels of the image according to their membership grade to the various regions. In this system, the agents neither interact directly between them nor act on the image. Their actions depend only on their local perception. Nevertheless, each agent is created so that it becomes more likely to meet more homogenous pixels. For the same type of images, Richard et al. [START_REF] Richard | Automated segmentation of human brain MR images using a multi-agent approach[END_REF] propose a hierarchical architecture of situated and cooperative agents. Several types of agents were used. Interaction between agents in the various hierarchic levels has allowed to deal with the control over the low-level segmentation tasks. However, the system was specially optimized to brain MRI segmentation. The two previous systems can provide correct results because region characteristics are regular in the various brain anatomic parts. In addition, most of the edges in such images are jump edges (at discontinuities of image data), which are easy to detect, compared to roof or smooth edges (edges respectively at normal or curvature discontinuities).

Based on a cognitive architecture, Bovenkamp et al. [START_REF] Bovenkamp | Multi-agent segmentation of IVUS images[END_REF] have developed a multi-agent system for Intra Vascular Ultra Sound (IVUS) image segmentation. They aim to elaborate a high knowledge-based control over the low-level image processing algorithms. In this system, an agent is assigned to every expected object in the image. In this work, the problem of the control over the segmentation algorithms seems to be well resolved. However, no agent or even behavior has been proposed to deal with uncertain and noisy data.

The proposed agent-based systems for image segmentation are specific to image contents. Following a supervised approach, these systems segment images in known and previously expected regions. The system proposed in this paper claims to be general and unsupervised. It aims to segment an image into its different regions by using some invariant surface proprieties. The adaptive and competitive behavior of the agents allows overcoming the constraint related to the restriction of the treatments to the local neighborhood of the pixels.

Multi-agent Range Image Segmentation

A range image is a discretized two-dimensional array where at each pixel (x, y) is recorded the distance Z(x, y) between the range finder and the corresponding point of the scene. A new image Z * , called plane image is derived from the range image. Each pixel (x, y) of the new image records the tangent plane to the surface at (x, y). The tasks performed by the agents on the plane image are based on the comparison of planes. So, we consider that two planes ax + by + cz = d and a x + b y + c z = d are equal if they have, according to given thresholds (T r θ , T r D ), the same orientation, and the same distance to the coordinate origin. T r θ and T r D are respectively the angle and the distance thresholds.

The plane image Z * is considered as the environment in which the agents are initialized at random positions. An agent checks if it is situated on a planar region, and adapts to this region if it is planar, by memorizing its plane equation. Next, the agent performs actions, which depend on both its state and the state of the pixel on which it is located. At each time t, an agent is characterized by its position (x t , y t ) over the image, and by its ability A t to act on the encountered pixels. At the beginning of the process, all the agents are unable to alter any pixel of the image. After having been adapted to a planar region, an agent becomes able to modify the first encountered pixel that not belongs to the current region (A t =true). When an agent alters a pixel, it loses its alteration ability (A t =false) and starts again searching for a new planar region. An agent having modified a pixel records in an appropriate two-dimensional array I, at (x t , y t ) the last state of the visited pixel: I(x t , y t ) ∈ {smoothed, aligned, unchanged}. We show next, that this simple behavior of the agents allows both the detection of the image edges, and the removal of the noise regions.

Agent Behavior

An agent adapts to the region of the image on which it is moving by computing and memorizing the proprieties of this region, and by adopting the suited behavior to the local image data. An agent can be in one of the following situations : searching for a planar region, moving on a planar region, aligning images pixels.

After its creation, an agent randomly moves within the image and searches for a planar region around its current position. The agent uses a region seed formed by the last L visited pixels. L is called the adaptation path-length. It represents the confidence degree that the agent is situated within a planar region. So, the agent considers that it is within a planar region if the pixels of the seed form a planar surface. The agent memorizes the new region and considers it as its current planar region. It becomes then able to alter the first encountered pixel that does not belong to its new region (A t =true).

While moving inside a planar region, an agent smoothes the pixel on which it is located, by updating the equations of both the memorized plane and the plane at the position of the pixel. This is done by replacing the two equations by their weighted average. Let (a, b, c, d) and (a , b , c , d ) be the parameters respectively of the plane at the current pixel, and the memorized plane. Resulting parameters of the weighted average plane are obtained as follows:

(a , b , c , d ) = 1 1 + l (a + la , b + lb , c + lc , d + ld ) ( 1
)
where l is the length of the path crossed by the agent on the planar region.

When an agent meets a pixel of interest (not belonging to its current planar region, i.e. noise pixels or edge pixels), the pixel is partially aligned to the planar region on which the agent moves. The parameters (a , b , c , d ) of the new plane equation at the pixel position are obtained by linear combination of the current parameters (a, b, c, d) and the parameters of the memorized plane equation (a ,b ,c ,d ): (a ,b ,c ,d

) = 1 1 + ξ (a + ξa , b + ξb , c + ξc , d + ξd ) ( 2
)
where ξ is the alteration strength. The agent loses then its alteration ability (A t =false) and starts again to search for a new planar region. The alteration strength ξ is a critical parameter, which affects the quality of the results and the time of computation. Indeed, high values of ξ lead to a fast region detection. However, the resulting region boundaries are distorted and badly localized (Fig. 1b). Low values of ξ result in a slow detection, but region boundaries in this case, are well detected and correctly localized (Fig. 1c). In order to speed up the segmentation process, without edge distortion, an agent chooses the alteration strength among ξ min and ξ max according to the information recorded by other agents in the array I. So, an agent assumes that the current planar region is adjacent to a noise region, and thus uses ξ max as alteration strength, if the number of "unchanged" pixels (situated within a noise region) around the agent is greater than a given threshold (fixed to 3 in our experimentations). Indeed, pixels labeled "unchanged" in the adjacent region mean that this latter is a noise region for which agents have not adapted and consequently have not smoothed its pixels. Otherwise, the agent assumes that the current planar region is adjacent to another planar one, where other agents have labeled the pixels as "smoothed" or "aligned". In this case, the agent uses the alteration strength ξ min .

Agent Coordination by Artificial Potential Field

To endow agents with a self-organization mechanism, an artificial electrostaticlike potential field is used. It is created and updated around the aligned pixels.

It allows agents to be gathered around pixels of region boundaries, and concentrate their actions at these pixels. Contrary to other works, where the potential field is created at known positions of objects (goals and obstacles) [START_REF] Ferber | Multi-Agent Systems: An Introduction to Distributed Artificial Intelligence[END_REF][START_REF] Tsuji | Bio-mimetic trajectory generation of robots via artificial potential field with time base generator[END_REF], the potential field in our case results from the interaction of agents with the objects in the environment (pixels). The intensity Ψ (x, y) of the potential field at position (x, y) created by a set of P pixels beforehand aligned {(x i , y i ),i = 1..P ∧ I(x i , y i )=aligned} is given by:

Ψ (x, y) = P i=1 k (x -x i ) 2 + (y -y i ) 2 , k ∈ R + ( 3
)
where k is the constant of the electrostatic force, set to 1. An agent which is able to alter pixels (A t =true) and situated at position (x t , y t ) undergoes an attractive force -→ F . This force is expressed by the gradient vector of the potential field:

-→ F = ⎧ ⎨ ⎩ - -→ ∇Ψ (x t , y t ) if A t =true -→ 0 o t h e r w i s e (4)
So, the agent movements, which are stochastic in nature, are weighted by the attractive force applied by the potential field. Agents are influenced to head for the pixels of interest, while keeping random moves. The random component of the agent moves allows the exploration of all regions of the image. A Relaxation mechanism of potential field is also introduced. It allows the agents gathered around pixels of interest to be released and thus to explore other regions of the image. Around a given pixel, the field intensity decreases after every alteration of this pixel. The equation of the relaxation dynamic is expressed as follows:

Ψ t+1 (x, y) = μ × Ψ t (x, y), μ < 1 ( 5 )
Ψ 0 (x, y) corresponds to the created field after the first alteration of the pixel. The constant μ set to 0.9, represents the decrease rate of the field intensity. After several alignments of a given pixel, the field intensity around this pixel decreases, and tends to zero. This situation represents the final state of the process, after which the system can be stopped.

Edge Detection and Noise Removal

While moving over the image, an agent smoothes the pixels that approximately belong to its planar region and considers all other pixels as noise pixels. Among these latter, the agent systematically aligns the first encountered one to its current region. However, pixels on the boundaries of regions are true-edge pixels, and thus should not be aligned. Nevertheless, the competition between agents preserves these pixels against an inappropriate smoothing. Indeed, around an edge between two adjacent planar regions, two groups of agents are formed on the two sides of the edge. Each group is formed of agents passing from one region to the other. Agents of each group align the pixels of the edge to their respective region. So, the pixels of the edge are continuously swapped between the two adjacent regions. The resulting alternative alignment of edge pixels allows these pixels to remain emergent in the image. This pattern of competitive actions between agents allows the emergence of the edges in the image, whose detection is not coded in any agent, but results from the collective action of all the agents. Unlike the true regions of the image, which remain preserved against erasing, the noise regions continuously narrow, and they finally disappear. The borders of these regions are continuously aligned to the true planar regions that surround them. An agent, having aligned a pixel that belongs to the border of a noise region, and having moved inside it, will not be able to adapt. Consequently, the agent cannot align any pixel when leaving the noise region. This occurs in two distinct situations: 1) when the region is planar but insufficiently large to allow agents to cross the minimal path-length L, necessary to be able to adapt; 2) when the region is sufficiently large but not planar, or made up of random depths (noise). In both situations, the agent leaves the noise region and will adapt inside the surrounding planar one. As a summary we can say that true regions have large sizes, sufficient to allow agents to adapt and then align the boundary pixels when leaving these regions. However, noise regions, which are non planar or having weak sizes, prevent agents from adapting. Consequently, agents will be unable to align pixels on the boundaries of these regions when leaving them. As a result, the borders of a noise region are continuously aligned from outside by including their pixels in the true surrounding regions. After several iterations, all the noise regions will be completely erased. At the end of the process, all the regions in the image are well delimited by the detected boundaries. A simple region growing, steered by the detected boundaries, allows extracting the regions of the image. Fig. 2 shows an instance of segmentation progression within time. The time t represents the number of steps performed by each agent since the beginning of the process. Displaying a range image by a simple rendering algorithm (Fig. 2a), allows to notice the high level of noise in the used images. Figures 2b, 2c, 2d and2e show the set of pixels of interest (edge or noise pixels) respectively at t=1000, 5000, 9000 and 13000. Regions are progressively smoothed by aligning the noise pixels to the surrounding planar regions. Edges between adjacent regions are also progressively thinned. At the end of the process, region borders consist of thin lines of one pixel wide (Fig. 2e). Fig. 2f shows the segmentation result obtained by displaying the borders of the extracted regions.

Table 1 contains the average results obtained with all the test images, and for all the performance metrics. The compare tool tolerance was set to the typical value 80%. By considering both the correct detection and the incorrect detection metrics, obtained results show the good efficiency of our method. For all the incorrect detection metrics (instances of Over-segmentation, Under-segmentation, Missed Region, Noise Region), our method has equivalent scores to those of UE and USF. The two latter scored higher than UB and WSU. Fig. 3 shows the average numbers of correctly detected regions for all the test images according to the compare tool tolerance T . Results show that the number of the correctly detected regions by our method is in average better than those of USF, UB and WSU. For instance, our method scored higher than WSU for all the values of the compare tool tolerance T . It scored higher than USF for T ∈ {80%, 90%, 95%}, and better than UB for T ∈ {50%, 60%,70%, 80%}.

Conclusion

In this paper, we have introduced a multi-agent approach for range image segmentation. Competitive actions between agents have allowed the emergence of the edges in the image. Image edges, for which no explicit detection was coded in any agent, result from the collective action of all the agents. Obtained results are better than those provided by the traditional algorithms. Moreover, used agents are weakly coupled and indirectly communicate via the environment (image). This allows parallel or distributed implementations, suited for a high computational efficiency. The experimental results obtained with real images from the ABW database show the potential of the proposed method for an efficient and accurate segmentation of range images. The average run time is 8 sec., on a Compaq PC n×8220. The recorded run times were better that those provided by region based methods, and equivalent to edge-based ones. The proposed method should record interesting run times, when implemented on massively parallel architectures, such as Transputer-based architectures. The proposed approach can be extended to deal with more complex surfaces by defining their specific proprieties, and endowing the agents with the appropriate behavior.

Fig. 1 .

 1 Fig. 1. The impact of the alteration strength on the segmentation results: (a) Range image (abw.test.8); (b) Segmentation results with ξmin = ξmax = 4 at t=2500; (c) Segmentation results with ξmin = 0.3 and ξmax = 5 at t=13000

Fig. 2 .

 2 Fig. 2. Segmentation progression. (a) Rendered range image (abw.test.6); (b) at t=1000, (c) at t=5000; (d) at t=9000; (e) at t=13000; (f) Extracted regions.

Fig. 3 .

 3 Fig. 3. Average results of correctly detected regions of all methods

Table 1 .

 1 Average results of the different involved methods with T =80%

	Method GT Correct Over-seg Under-seg Missed Noise
	USF 15.2	12.7	0.2	0.1	2.1	1.2
	WSU 15.2	9.7	0.5	0.2	4.5	2.2
	UB 15.2	12.8	0.5	0.1	1.7	2.1
	UE 15.2	13.4	0.4	0.2	1.1	0.8
	2ARIS 15.2	13.0	0.5	0.1	1.4	0.9