Jérémie Chalopin
email: chalopin@labri.fr

Election and Rendezvous with Incomparable Labels ⋆

In "Can we elect if we cannot compare" (SPAA'03), Barrière, Flocchini, Fraigniaud and Santoro consider a qualitative model of distributed computing, where the labels of the entities are distinct but mutually incomparable. They study the leader election problem in a distributed mobile environment and they wonder whether there exists an algorithm such that for each distributed mobile environment, it either states that the problem cannot be solved in this environment, or it successfully elects a leader. In this paper, we give a positive answer to this question. We also give a characterization of the distributed mobile environments where election and rendezvous can be solved.

Introduction

Consider an intercontinental highway network linking different cities in different countries. In each city, the directions to the other cities are written in the language that is locally spoken. Consider now a set of different drivers coming from different countries. Initially, each driver starts in his town and all the drivers want to meet at a single place. The only mean they have to communicate is to leave messages in each city they reach, but each driver can only speak his mother tongue: he can see that another driver left some message, but he cannot understand it. Moreover, each driver can consistently distinguish the different directions in each city, but the drivers cannot agree on an alphabetical order on these directions: a French driver would not be able to figure out how to order Chinese words in the Chinese way, for example. We wonder whether there exists a procedure that enables them to meet at a single point in a finite time.

In distributed computing, the links incident to each process are usually labelled by distinct numbers in order to allow each process (or each mobile agent) to consistently distinguish its neighbours; this labelling is usually called a port-numbering. In fact, these numbers enable not only to distinguish the links, but also to order them. Many distributed algorithms assume also that all the processes can be unambiguously identified, and therefore the processes are given numbers. Again, one can see that this enables to order the different processes according to their labels. This usual setting is a quantitative model, since each label can be seen as a number.

Nevertheless, as in the example presented above, one may be able to distinguish labels without being able to order them. In this paper, we consider distributed mobile environments where mobile agents are scattered all over a network. All the agents have distinct colors (their labels), which are mutually incomparable: each agent can just check whether two colors are equal or not. The links incident to each vertex are also given distinct incomparable colors. This model is close to the one introduced by Barrière et al. in [START_REF] Barrière | Can we elect if we cannot compare?[END_REF]; it is qualitative, in the sense that there is no a priori order between the labels. As in [START_REF] Barrière | Can we elect if we cannot compare?[END_REF], we study the impact of the lack of a total order on the set of labels in a distributed mobile environment. In this way, we investigate the leader election problem, that is a classical problem to highlight the differences between various models of distributed computing.

In usual models, there is always an implicit order over the set of labels, since for each agent, each information is just a sequence of bits. Nevertheless, consider an algorithm designed to be executed by mobile agents over a network. If the agents have been implemented by different companies, and if the specifications of the algorithm do not specify how the integers must be represented, some agents can for instance store numbers with most significant bit first whereas other agents store numbers with least significant bit first; in this case, the agents would not agree on the meaning of the sequence 01101. Moreover, it is always interesting to deal with algorithms that need less specifications, since they are generally more robust, and easier to implement in different models of distributed computing.

The Model

In this paper, an agent is an entity which executes an algorithm: it can move from place to place (with some data and its algorithm) through communication links, it can make local computations on a place (a place provides tools for local computations: data, memories and process) and leave messages on a place.

In our model, the environment is represented by a simple undirected connected graph G = (V (G), E(G)) and a set E of mobile agents is scattered over G. We suppose that the graph G is anonymous, i.e., vertices of G do not have identities. Communications between agents is achieved through writing messages on whiteboards, where agents can read, write, and erase messages. There is one whiteboard on each vertex of G, and access to a whiteboard is in fair mutual exclusion.

Each agent r ∈ E is initially placed on a vertex of the graph and we denote by p the injection describing the initial placement of the agents in G. The vertex p(r) is called the homebase of the agent r ∈ E and we suppose that initially, the homebases are marked: they contain a marker that enables each agent to know that a place is a homebase. We will denote such a distributed mobile environment by (G, E, p).

We consider an injective function color that associates to each agent r ∈ E a unique color from a set C a . There is no a priori order on the set of colors: each agent can give its own order on the set of colors, but the agents do not necessarily agree on a particular order. If there is a message on some whiteboard, an agent can always know the color of the message (i.e., the color of its author), but it cannot understand it if the color of the message is different from its own color (i.e., it can only understand the messages it has written). We also suppose that each time an agent r is on the homebase p(r ′ ) of an agent r ′ , it can detect the color of this homebase (i.e., the color of r ′ ).

In each place, the incident links are labelled by different colors that enable each agent to consistently distinguish the neighbours of the place: for each vertex u, there exists an injective function δ u that associates a color from a set C δ (disjoint from C a ) to each edge incident to u. The set δ = {δ u : u ∈ V (G)} constitutes the port-labelling of G. Thanks to this labelling δ, each agent can make a distinction between the incident edges of each vertex. As for C a , the agents do not agree on an a priori order on the set of colors C δ . Such a distributed colored mobile environment will be denoted by (G, δ, E, p, color).

The agents are asynchronous, in the sense that every action they perform (computing, moving, etc.) takes a finite but otherwise unpredictable amount of time. The actions an agent a located at a node v can perform depends on the current state of a, the current state of the whiteboard at v, and the color of the port through which a entered v. According to these information, a can decide to write a message on the whiteboard of v, to leave v (through a port whose color may result from some computation), or to stay at v (for example, to wait that another agent leaves a message on the whiteboard).

As in [START_REF] Barrière | Can we elect if we cannot compare?[END_REF], we suppose that an agent has not an initial knowledge of the network topology, neither of its size nor of the number of agents in the system. Nevertheless, the model considered in this paper is more restrictive than the one presented in [START_REF] Barrière | Can we elect if we cannot compare?[END_REF], since in the model of Barrière et al. the agents cannot agree on an order on the set of colors, but they fully understand the symbols written by the other agents. However, the necessary condition presented in our model is the same as the one presented in [START_REF] Barrière | Can we elect if we cannot compare?[END_REF]: the results presented in this paper remain true in the model of [START_REF] Barrière | Can we elect if we cannot compare?[END_REF].

Election and Rendezvous

The election problem is one of the paradigms of the theory of distributed computing, that was first posed by LeLann [START_REF] Lelann | Distributed systems, towards a formal approach[END_REF]. In the distributed mobile setting, the aim of a leader election algorithm is to distinguish one agent among the others. All the agents execute the same protocol, i.e., the only initial difference between two agents is their colors. At the end of the execution of the algorithm, there is exactly one agent in the state elected, whereas all the other agents enter the state non-elected. Moreover, it is supposed that once an agent enters the state elected or non-elected, it remains in such a state until the end of the computation.

Another important problem in this setting is the rendezvous problem. The aim of a rendezvous algorithm is to reach a configuration where all the mobile agents gather in the same place. These two problems are equivalent, since once an agent has been elected, if all the agents agree on the label elected, all the agents can gather in the homebase of the elected agent. Reversely, once all the agents have gathered in some place, the first agent that writes on the whiteboard of this place is elected, whereas all the others become non-elected. There exists a large variety of results for these problems in the mobile agent setting assuming different properties of the environment [BFFS06,DFNS05,DFP03,KKR06]. The election problem has also been extensively studied in the distributed setting, and particularly in anonymous networks, where the processes do not have distinct labels [Ang80,BCG + 96,CM05,YK96,YK99].

In the model we consider, an election (or rendezvous) algorithm for a distributed mobile environment must not use some particularity of the colors used to label the ports or the agents or make any assumption on the set of colors (for example, one cannot design an algorithm that elects a red agent when there is such an agent). Consider a graph G and a set of agents E scattered over the network according to a function p. We say that we can solve the election (resp. rendezvous) problem on (G, E, p) if the problem can be solved on (G, δ, E, p, color) for all port-labellings δ and all agent-coloring functions color. Note that, as for anonymous networks in the distributed setting [START_REF] Chalopin | A bridge between the asynchronous message passing model and local computations in graphs[END_REF][START_REF] Yamashita | Computing on anonymous networks: Part i -characterizing the solvable cases[END_REF], the protocols must not depend on the port-labelling. Indeed, the role of the port-labelling is just to enable an agent to make a distinction between the different neighbours of a vertex.

As in [START_REF] Barrière | Can we elect if we cannot compare?[END_REF], we say that an algorithm A is an effective election (resp. rendezvous) algorithm if for each distributed mobile environment (G, E, p), each port-labelling δ and each coloring function color, for all the executions of A on (G, δ, E, p, color), either all the agents detect that the election (resp. rendezvous) problem cannot be solved in (G, E, p) (i.e., there does not exist any algorithm that can solve the problem in this environment), or the agents successfully elect one of them (resp. gather in some vertex). In particular, note that such an algorithm does not need any initial knowledge about the topology, the size, the diameter of the network or about the number of agents.

In the following, we will mainly focus on the election problem, but we have to keep in mind the results obtained remain true for the rendezvous problem.

Main Results

In this work, we give a characterization (Theorem 1) of distributed mobile environments, where the election problem can be solved.

In [START_REF] Barrière | Can we elect if we cannot compare?[END_REF], Barrière et al. wonder whether there exists an effective election algorithm for the qualitative world. The algorithm we describe gives a positive answer to this question (Theorem 2).

To obtain a necessary condition (Proposition 3), we use well-balanced automorphisms that have been introduced by Bougé in [START_REF] Bougé | On the existence of symmetric algorithms to find leaders in networks of communicating sequential processes[END_REF].

Then, we show that this necessary condition is also sufficient: we use some links between fibrations and automorphisms presented in [START_REF] Boldi | Fibrations of graphs[END_REF] to describe an effective algorithm in Section 4.2 that solves the election problem when the necessary condition is satisfied.

Preliminaries

Labelled Digraphs

In the following, we will consider directed graphs (digraphs) with multiple arcs and self-loops. A digraph D = (V (D), A(D), s D , t D ) is defined by a set V (D) of vertices, a set A(D) of arcs and by two maps s D and t D that assign to each arc two elements of V (D): a source and a target (in general, the subscripts will be omitted); if a is an arc, the arc a is said to be going out of s(a) and coming into t(a). We say that s(a) is a predecessor of t(a) and that t(a) is a successor of s(a).

A digraph D is strongly connected if for all vertices u, v ∈ V (D), there exists a sequence of arcs a 1 , a 2 , . . . a p such that s(a 1 ) = u, ∀i ∈ [1, p -1], t(a i ) = s(a i+1 ) and t(a p ) = v. In the following, we will only consider strongly connected digraphs.

A symmetric digraph D is a digraph endowed with a symmetry, that is, an involution Sym : A(D) → A(D) such that for every a ∈ A(D), s(a) = t(Sym(a)). Definition 1. A homomorphism γ between the digraph D and the digraph D ′ is a mapping γ :

V (D) ∪ A(D) → V (D ′ ) ∪ A(D ′ ) such that for each arc a ∈ A(D), γ(s(a)) = s(γ(a)) et γ(t(a)) = t(γ(a)).
An homomorphism γ is an isomorphism if γ is bijective.

Throughout the paper we will consider digraphs where the vertices and the arcs are labelled with labels from a recursive label set L. A digraph G labelled over L will be denoted by (D, λ), where λ : V (D) ∪ A(D) → L is the labelling function. The digraph D is called the underlying digraph and the mapping λ is a labelling of D. A mapping γ :

V (D) ∪ A(D) → V (D ′ ) ∪ A(D ′ ) is a homomorphism from (D, λ) to (D ′ , λ ′ ) if γ is a digraph homomorphism from D to D ′
which preserves the labelling, i.e., such that λ ′ (γ(x)) = λ(x) for every x ∈ V (D) ∪ A(D). Labelled digraphs will be designated by bold letters like D, G, . . . If D is a labelled digraph, then D denotes the underlying digraph.

Given a connected simple graph G = (V (G), E(G)), one associate a symmetric strongly connected digraph denoted by Dir(G) and defined as follows: V (Dir(G)) = V (G) and for each edge {u, v} ∈ E(G), there exist two arcs

a (u,v) , a (v,u) ∈ A(Dir(G)) such that s(a (u,v) ) = t(a (v,u) ) = u, t(a (u,v) ) = s(a (v,u) ) = v and Sym(a (u,v) ) = a (v,u)
. Note that this digraph does not contain multiple arcs or self-loop.

Given a mobile environment (G, E, p), we define the labelling function χ p of the vertices by χ p (v) = 1 if there exists an agent a such that p(a) = v, and χ p (v) = 0 otherwise. A distributed mobile environment (G, E, p) can therefore be represented by the labelled digraph (Dir(G), χ p ).

Fibrations and Coverings

The notions of fibrations and coverings are fundamental in this work; definitions and main properties are presented in [START_REF] Boldi | Fibrations of graphs[END_REF].

A fibration is a homomorphism that induces a isomorphism between the incoming arcs of each vertex and the incoming arcs of its image. Definition 2. A digraph D is fibred over a digraph D ′ via a homomorphism ϕ if ϕ is a homomorphism from D to D ′ such that each arc a ′ ∈ A(D ′ ) and for each vertex v ∈ ϕ -1 (t(a)), there exists a unique arc a ∈ A(D) such that t(a) = v and ϕ(a) = a ′ .

The homomorphism ϕ is then called a fibration from D to D ′ and the digraph D ′ is the base of ϕ.

The fibre over a vertex v ′ (resp. an arc a ′ ) of D ′ is the set ϕ -1 (v ′ ) of vertices of D (resp. the set ϕ -1 (a ′ ) of arcs of D).

A covering projection is a fibration that also induces a isomorphism between the outgoing arcs of each vertex and the outgoing arcs of its image.

Definition 3. A digraph D is a covering of a digraph D ′ via a homomorphism ϕ if ϕ is a homomorphism from D to D ′ such that each arc a ′ ∈ A(D ′ ) and for each vertex v ∈ ϕ -1 (t(a)) (resp. v ∈ ϕ -1 (s(a)), there exists a unique arc a ∈ A(D) such that t(a) = v (resp. s(a) = v) and ϕ(a) = a ′ .
The homomorphism ϕ is then called a covering projection from D to D ′ .

A symmetric covering projection is a covering projection between symmetric digraphs that preserves the function Sym.

Definition 4. A symmetric digraph D is a symmetric covering of a symmetric digraph D ′ via a homomor- phism ϕ if D is a covering of D ′ via ϕ and if for each arc a ∈ A(D), ϕ(Sym(a)) = Sym(ϕ(a)). The homomorphism ϕ is a symmetric covering projection from D to D ′ . A digraph D is symmetric-covering-minimal if there does not exist any digraph D ′ not isomorphic to D such that D is a symmetric covering of D ′ .
An interesting property satisfied by any covering projection is that the preimage of all the vertices of the base have the same size.

Proposition 1 ([BV02]

). Given two strongly connected digraphs D and D ′ and a covering projection ϕ from D to D ′ , there exists q ∈ N such that for each

x ′ ∈ V (D ′ ) ∪ A(D ′ ), |ϕ -1 (x ′ )| = q.
The notions of fibrations and coverings extend to labelled digraphs in a natural way: the homomorphisms must preserve the labelling. Examples of fibrations and coverings are given in Figures 1, 2 and4.

G/Γ (G) 1 2 B Γ (G) (G) 1 2 G 1 2 1 H/Γ (H) 1 2 B Γ (H) (H) 1 2 H 1 2 2 1 Fig. 1. The digraph G is fibred over B Γ (G) (G) via the homomorphism ϕG that maps each vertex of G labelled i to the unique vertex labelled i of B Γ (G) (G). The digraph H is a covering of B Γ (H) (H)

Fibrations, Coverings and Automorphisms

We now describe some properties of the relations that exist between fibrations and the automorphisms of a digraph. These results are described and proved in [START_REF] Boldi | Fibrations of graphs[END_REF].

An automorphism σ of a digraph G is an isomorphism from the digraph G onto itself. Consider a subgroup Γ of the group Γ (G) = Aut(G) of the automorphisms of a digraph G = (G, λ); we will denote by Id the identity automorphism of G. The action of this group on G induces an equivalence relation over the vertices and the arcs of G:

for each x, x ′ ∈ V (G) ∪ A(G), x ∼ Γ x ′ if there exists σ ∈ Γ such that σ(x) = x ′ .
The equivalence class of x is called the orbit of x and is denoted by [x] Γ . Recall that an automorphism of (G, λ) must preserve the labelling, and therefore for all elements

x 1 , x 2 ∈ [x] Γ , λ(x 1 ) = λ(x 2 ). If Γ = Γ (G), we will note x ∼ x ′ (resp. [x]) for x ∼ Γ x ′ (resp. [x] Γ ). Remark 1. For all vertices v, v ′ ∈ V (G), if v ∼ Γ v ′ ,
then there is a label-preserving bijection between the incoming arcs of v and the incoming arcs of v ′ .

We will now describe two kinds of constructions. The first one allows us to build a digraph B Γ (G) from a digraph G such that G is fibred over B Γ (G). The second one allows us to build the quotient-graph G/Γ . Examples are presented in Figures 1 and2 where Γ = Γ (G).

From the relation ∼ Γ , we construct the directed graph B Γ (G) defined as follows: V (B Γ (G)) is the set of the equivalence classes of V (G) under the action of Γ and there are as many arcs from

[v] Γ to [w] Γ as each vertex in [w] Γ has predecessors in [v] Γ . Due to Remark 1, this does not depend on the choice of the element of [w] Γ . We define the labelling ν of B Γ (G) by ν([v] Γ ) = λ(v) for each v ∈ V (G).
We label the arcs from [v] to [w] with the labels of the arcs from the elements of [v] to w in G. By Remark 1, there exists a fibration ϕ from G to (B Γ (G), ν).

We consider also the quotient-graph G/Γ whose vertices and arcs are the equivalence classes of the vertices and the arcs of G under the action of Γ and whose labelling µ is defined by µ

([x] Γ ) = λ(x) for each x ∈ V (G) ∪ A(G).
There exists a natural surjective homomorphism from (B Γ (G), ν) to G/Γ which is the identity on the vertices and which maps an arc a to [a] Γ (a can be seen as an arc of G).

We say that a subgroup Γ of Γ (G) acts freely on G if for each x, y ∈ V (G) ∪ A(G), there is at most one σ ∈ Γ such that σ(x) = y. Equivalently, Γ acts freely on G if and only if for each σ ∈ Γ \ {Id}, σ has no fixpoint.

1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 P 2 1 3 B Γ (P) (P) 2 1 3 P/Γ (P)
Fig. 2. The labelled digraph P is a covering of P/Γ (P): the automorphism group of P contains only well-balanced automorphisms.

In the following, we will use a particular class of automorphisms: the class of well-balanced automorphisms. These automorphisms have been introduced by Bougé in [START_REF] Bougé | On the existence of symmetric algorithms to find leaders in networks of communicating sequential processes[END_REF] to study the importance of the guards in CSP through the symmetric election problem. In [START_REF] Palamidessi | Comparing the expressive power of the synchronous and the asynchronous π-calculus[END_REF], Palamidessi uses also well-balanced automorphisms to study the same problem in order to give a hierarchy between different subsets of the π-calculus. Definition 5. An automorphism σ of a digraph G is well-balanced if there exists an integer q such that for each vertex or arc

x of G, |{σ k (x) | k ∈ N}| = q.
Equivalently, σ is well-balanced if and only if the subgroup Γ σ generated by σ acts freely on G.

The group Γ contains only well-balanced automorphisms if and only if Γ acts freely on G. Thanks to this equivalence and the results of Boldi and Vigna [START_REF] Boldi | Fibrations of graphs[END_REF], we have the following property.

Proposition 2. Given any strongly connected digraph G, the quotient projection Γ : G → G/Γ is a covering projection if and only if for each σ ∈ Γ , σ is well-balanced.

Impossibility Result

The following proposition gives a necessary condition that the distributed mobile environment (G, E, p) must satisfy if there exists an election algorithm for (G, E, p) that successfully elects an agent. This necessary condition is equivalent to the one presented in [START_REF] Barrière | Can we elect if we cannot compare?[END_REF].

Proposition 3. Consider a graph G and an initial placement of the agents p. If there exists a non-trivial well-balanced automorphism σ of the digraph G ′ = (Dir(G), χ p ), then it is impossible to elect an agent over the graph G with the initial placement of the agents p.

Proof. Consider a distributed mobile environment (G, E, p) such that there exists a well-balanced automorphism σ of G ′ = (Dir(G), χ p ) different from Id. There exists an integer q ≥ 2 such that ∀v ∈

V (G), |{σ k (v) | k ∈ N}| = q.
Suppose that there exists an election algorithm A for (G, E, p). Consider a port-labelling such that each port has a unique color. The automorphism σ induces a permutation of the agents and a permutation of the colors of the agents and of the ports, that will also be denoted by σ. These permutations induce equivalence relations on the agents and on the colors.

Initially, an agent r is on v if and only if σ(r) is on σ(v), and two equivalent agents are not in the same place. Moreover, the information available to σ(r) is the same as the one available to the agent r, up to the permutation σ of the colors. We can exhibit an execution of A such that these properties remain true all along the execution and such that if a message is written with a color c on a vertex v, then the same message is written on σ(v) with the color σ(c). Note that two equivalent agents should behave in the same way in this execution and consequently, they should not gather in the same place during the execution. Indeed, if this happens, then the symmetry between the two agents can be broken since one of them can access the whiteboard before the other one.

If an agent r writes a message with its color c on the whiteboard of a vertex v, then for each k ∈ [1, q -1], the agent σ k (r) writes the same message with its color σ k (c) on σ k (v). Suppose now that an agent r leaves a vertex v through a port colored c 1 to arrive in a vertex w through a port colored c 2 . Then for each k ∈ [1, q-1], the information available to σ k (r) is the same as the one available to r (up to the permutation σ k of the colors), it leaves the vertex σ k (v) through the port colored σ k (c 1 ) to arrive at the vertex σ k (w) through the port colored σ k (c 2 ) and obtains the same information from the whiteboard of σ k (w) as r. Moreover, since σ is well-balanced, we can ensure that two equivalent agents do not gather in a same vertex.

Consequently, if during the execution of A, an agent r takes the label elected, then the agent σ(r) takes also this label, and therefore A is not an election algorithm.

⊓ ⊔

Using known results in the message-passing model [BCG + 96,CM05,YK96] and the results of [START_REF] Chalopin | Mobile agent algorithms versus message passing algorithms[END_REF], we can show that in the anonymous setting, i.e., when the agents can understand each other but do not have distinct labels, there exists an election algorithm for an environment (G, E, p) if and only if the labelled digraph G ′ = (Dir(G), χ p ) is symmetric-covering-minimal. Moreover, from Proposition 2, we know that if the symmetric digraph G ′ = (Dir(G), χ p ) admits a non-trivial well-balanced automorphism σ, then G ′ is a symmetric covering of G ′ /Γ σ that is not isomorphic to G ′ .

Consequently, an interesting corollary of Proposition 3 is that if the election problem cannot be solved on (G, E, p) in the qualitative setting, then it cannot be solved on (G, E, p) in the anonymous setting. On the other hand, we will show in the following that this necessary condition is also sufficient.

Since there exist symmetric digraphs that are not symmetric-covering-minimal and that does not admit any non-trivial well-balanced automorphism, such as the graph G of Figure 3, it means that one can solve the election problem in strictly more environments in the qualitative setting than in the anonymous one.

Example 1. On the Figure 3, we present a digraph G that is not covering minimal, whereas the underlying digraph G does not admit any automorphism.

Consequently, if we consider the distributed mobile environment corresponding to the digraph (G, χ p ) where χ p (v) = 1 for each v ∈ V (G), we know from [BCG + 96,CM05,YK96,CGMO06] that there does not exist any election algorithm for this environment in the anonymous setting.

Nevertheless, from the results of the following sections, we can show that one can solve election and rendezvous in this particular distributed mobile environment in the model we consider in this paper.

An Effective Election Algorithm

In this section, we show that the necessary condition described in Proposition 3 is also sufficient. We first show that even if the agents do not understand each other, they can agree on an order on some equivalence classes of vertices and arcs. We then present an algorithm that solves the election problem on any distributed mobile environment (G, E, p) whenever (Dir(G), χ p ) does not admit any non-trivial well-balanced automorphism.

How to order the equivalence classes?

We use the same ideas as Barrière et al. [START_REF] Barrière | Can we elect if we cannot compare?[END_REF] to define a total order between the different equivalent classes. The fact that graphs o size n can be canonically ordered is well-known [START_REF] Mckay | Practical graph isomorphism[END_REF]. We construct here a total ordering on digraphs of size n labelled by elements of a totally ordered set.

Consider a labelled digraph G = (G, λ) without multiple arcs where λ is a labelling function from V (G)∪A(G) to a totally ordered set L with a minimal element ⊥. We suppose that ∀x ∈ V (G)∪A(G), λ(x) ∈ L \ {⊥}.

Let n = |V (G)| and consider an enumeration function num of the vertices (i.e., num is a one-to-one mapping from V (G) onto [1, n]). We say that num is an increasing enumeration of the vertices if for all vertices

v, v ′ ∈ V (G), if num(v) ≤ num(v ′ ), then λ(v) ≤ L λ(v ′ ).
Given an increasing enumeration num, we define the adjacency matrix M num as follows: for all vertices v, v ′ , M num [num(v), num(v ′ )] = ℓ, if there is an arc from v to v ′ labelled by ℓ, and M num [num(v), num(v ′ )] = ⊥ otherwise. To this matrix, we associate the word w(M num ) obtained by the concatenation of the n rows of M num .

To each vertex v ∈ V (G) (resp. arc a ∈ A(G)), we choose num such that (num(v), w(M num )) (resp. (num(s(a)), num(t(a)), w(M num ))) is minimum for the lexicographic order and associate this value, denoted by π(v) (resp. π(a)), to v (resp. a). Note that there exists an automorphism σ of G such that σ(x) = x ′ if and only if π(x) = π(x ′ ). Consequently, this induces a total ordering of the equivalence classes of vertices and arcs: we will write [x ′ ] ≺ [x] if π(x) is greater than π(x ′ ) in the lexicographic order.

Remark 2. In the following, we will show that all the agents agree on a total order of the classes and all the agents use the same order. Actually, as it was already explained in [START_REF] Barrière | Can we elect if we cannot compare?[END_REF], even if the agents cannot agree on an a priori order over the set of colors, they can agree on an order on the different classes, provided that all the agents have the same representation of the graph (up to isomorphism).

In fact, we suppose that each agent has its own totally ordered set isomorphic to (N, ≤) and each agent can use its own way to compute its order: the algorithm does not make any assumption on the way the order is implemented by each agent.

An Election Algorithm

In this section, we describe our effective election algorithm. In a first phase all the agents reconstruct the digraph (Dir(G), χ p ) and check that the election problem can be solved on (G, E, p). Then, using its knowledge of the graph, each agent constructs the equivalence classes induced by Γ ((Dir(G), χ p )). During successive rounds, using the order between the different classes defined above, some agents become passive and get the label non-elected, whereas the active agents mark some vertices and some arcs of the digraph to obtain a new labelling µ of the digraph on which all the active agents agree. At the end of the computation, the automorphism group of (Dir(G), µ) consists only of the identity and each vertex has a unique label. At this point, there is exactly one active agent that is elected. A high level description of the algorithm is presented in Algorithm 1.

Algorithm 1: The Election Algorithm

Every agent builds a map of the graph; Synchronization; if there exists a non-trivial well-balanced automorphism of G ′ = (Dir(G), χp) then

Every agent knows that it is impossible to solve the election problem; else Every agent marks as many vertices as possible to construct its initial territory; Synchronization; /* Initially, all the agents are active and µ = χp */ repeat repeat The active agents compute the equivalence classes of all the vertices and arcs of G ′ = (Dir(G), µ); if two vertices v, v ′ (resp. arcs a, a ′ ) have the same label µ(v) = µ(v ′ ) (resp. µ(a) = µ(a ′ )) and are not in the same equivalence class then Refine the labelling µ of G ′ ; else if two equivalent active agents do not own the same number of vertices in a given class then Refine the labelling µ of G ′ ; else if there exists two equivalent arcs a, a ′ such that an agent r owns s(a) and t(a) whereas two distinct agents r, r ′ own respectively s(a ′ ) and t(a ′ ) then

Refine the labelling µ of G ′ ;

until the labelling µ of G ′ = (Dir(G), µ) cannot be refined ; if all the active agents are not in the same class then Select active agents;

The passive agents take the label non-elected ;

The active agents mark the homebases of the passive agents; Synchronization;

else if G ′ is not a covering of B Γ (G ′ ) (G ′ ) then
The active agents mark a class of vertices; Synchronization;

else if G ′ is not a covering of G ′ /Γ (G ′ ) then
The active agents mark a class of arcs; Synchronization; else /* In this case, there is exactly one active agent */ The active agent takes the label elected ;

until An agent is elected ;

A Synchronization Procedure. In the algorithm we describe below, we distinguish different rounds. An important point is that an active agent does not enter in a new round if another active agent has not finished the previous one. To be able to avoid this kind of situation, we synchronize the active agents. Each agent can consistently distinguish its homebase; therefore, we can construct an algorithm such that no agent needs to write anything on its homebase. Moreover, we suppose that each agent has already built its own map of the graph and does not need to write anything on any whiteboard in order to perform a traversal of the graph.

In the following, the active agents will do some traversals of the network and they will store the colors of the marks that appear on each vertex to construct what we will call a colored map of the network. The marks that appear in a colored map of an active agent will correspond to marks that have been put by other active agents during the round (but it will not necessary contain all the marks the active agents should put during this round).

In any round of the algorithm described below, the following properties will always be satisfied.

(P1) Each active agent can know from a colored map if any other active agent has marked all the vertices it should have marked during the round. (P2) In each round of the algorithm, each agent will mark at least one vertex (which is not its homebase).

In the synchronization procedure described below, some active agents will have to wait on some particular vertices for other agents to put (resp. remove) some marks. Each time an agent arrives on a place where it has to wait for a mark to be put (resp. removed), it can immediately continue to execute the procedure if this mark is present (resp. not present).

To synchronize the agents, we proceed as follows. Each round is divided in nine steps and during each round, each active agent r executes the following steps. During the first step, the active agents mark some vertices in order to communicate according to the rules of the algorithm we described below; the eight remaining steps are used to synchronize the active agents.

(Step 1) The agent r marks some vertices (but not its homebase) according to the computation rules of the round. In this step, the property (P2) is always satisfied. (Step 2) The agent r does a traversal of the network and stores all the colors of the marks that appear on each vertex to construct a colored map of the network. (Step 3) If there exists another active agent r ′ that has not finished (Step 1) (the agent r can detect it from the colored map it has of the network, since properties (P1) and (P2) are always satisfied), then the agent r goes to the homebase of r ′ and waits until the agent r ′ puts a mark on its homebase. Then the agent r does a traversal of the network and stores all the colors of the marks that appear on each vertex in order to update its colored map of the network. (Step 4) The agent r puts a mark on its homebase. (Step 5) The agent r does a traversal of the network and each time it arrives on the homebase of another active agent r ′ , it waits until the agent r ′ marks its homebase. (Step 6) The agent r does a traversal of the network and it removes the marks it puts during (Step 1), but not the mark on its homebase. (Step 7) The agent r does a traversal of the network. Each time it arrives on a vertex that has been marked by another active agent r ′ during this round (but that is not the homebase of r ′ ), it waits until the agent r ′ removes its mark. (Step 8) The agent r removes the mark it puts on its homebase. (Step 9) The agent r does a traversal of the network. Each time it arrives on the homebase of an active agent r ′ , it waits until the agent r ′ removes its mark on its homebase.

We can note that the synchronization procedure enables also to erase all the marks that have been put on the vertices during the round, i.e., when one agent has finished Step (9) of a round, then all the marks that have been left by the active agents during this round have been erased. The following proposition ensures that the procedure is indeed a synchronization procedure.

Proposition 4. Each time an agent starts executing

Step (1) of the i + 1th round, then each active agent knows what vertices have been marked by the other active agents during Step (1) of the ith round and all the marks that have been put during the ith round have been removed. Moreover, the synchronization procedure avoids any deadlock.

Proof. First, we show that if an agent is executing some particular step of a round, then one can know what are the possible steps the other agents can perform at this moment.

If an agent is currently performing Steps (1), (2) or (3) (resp. Steps (4) or ( 5), Steps (6) or (7), Steps (8) or (9)) of a round i, then it means that it has finished Step (9) of the i -1th round (resp. Step (3) of the ith round, Step (5) of the ith round, Step (7) of the ith round). Consequently, all the other agents have finished

Step (8) of the i -1th round (resp.

Step (1) of the ith round, Step (4) of the ith round, Step (6) of the ith round).

If an agent has neither finished Step (9) of the i -1th round nor Step (1) of the ith round (resp. Steps (2), (3) nor (4) of the ith round, Steps (5) nor (6) of the ith round, Steps (7) nor (8) of the ith round), then it means that no agent can have finished Step (3) of the ith round (resp. Step (5) of the ith round, Step (7) of the ith round, Step (9) of the ith round).

All these properties are summarized in the following table.

If an agent r is performing then any active agent r ′ and no active agent r ′

Step has finished

Step Suppose now that an active agent r is blocked at Step (7) (resp.

Step (9)) of a round i. Then all the active agents have finished Step (4) (resp. Step (6)) of the ith round and consequently, no active agent can be blocked at step (5) (resp. ( 7)) of the ith round. Consequently, each active agent has finished Step (6) (resp. Step (8)) of the ith round and then no agent can be waiting for another agent while it is performing Step (7) (resp. Step (9)) of the ith round.

Consequently, there is no deadlock in the application of the synchronization procedure. Moreover, each time an agent starts the computation of a round i + 1, i.e., each time it performs Step (1) of a round i + 1, all the active agents have finished Step (8) of the ith round and consequently all the marks that have been put during the ith round have been removed. Furthermore, since all the active agents have have finished Step (3) of the ith round, they get all the information they should gather during the execution of the ith round. ⊓ ⊔ Initialization. During the first phase of the algorithm, each agent reconstructs the graph with the position and the colors of the different homebases. Using the whiteboards, each agent performs a depth first traversal of the graph.

Since each agent can distinguish all the homebases, we suppose that during this traversal, the agents do not write anything on the whiteboard of any of the homebases. Once an agent has reconstructed the whole graph, it performs a traversal of the network using the information it has stored to erase what it has written on the whiteboards. At this point, each agent puts a mark on the homebase of another agent (note that a homebase may be marked by two or more agents).

During this first phase, no agent has written anything on its homebase. Furthermore, an agent has finished performing this phase if and only if it has marked the homebase of another agent and this can be checked from a colored map of the network. Moreover, at the end of this phase, each agent has reconstructed a map of the network and it knows the position of all the homebases. We can therefore use the synchronization procedure defined above at this point.

If the digraph (Dir(G), χ p ) admits a well-balanced automorphism σ different from Id, then each agent detects it and declares that the election problem is unsolvable in this environment. We will now suppose that (Dir(G), χ p ) does not admit such an automorphism.

Once the graph is known by all the agents, each agent tries to mark as many vertices of the networks as possible. It does a traversal of the network and each time it arrives on a vertex that is not a homebase, it performs one of the two following actions. Either the whiteboard is blank and it puts a mark with its color on the whiteboard, or there is already a mark on the whiteboard and it stores the color of the mark. Once an agent has finished this traversal, it puts a mark on the homebase of another agent. Again we use the synchronization procedure at this point. Then each agent is aware of the different vertices marked by the other agents during this round.

At the end of this phase, each agent reconstructs a graph where all the vertices are colored (they belong to the agent that has this color) and it knows the position and the color of the homebases of all the other agents. The territory of an agent is the set of all places this agent owns.

How can the agents increase their territory? During the different phases of the algorithm, some agents become passive whereas the others continue to execute the protocol in order to elect one of them. In our algorithm, in order to break the symmetry between the agents, all the vertices must belong to one active agent, and all the active agents must agree on which agent a vertex belongs to. During the initialization, each vertex is marked by one agent and we say that it belongs to this agent. Once an agent becomes passive, the vertices that belonged to this agent must be given to another agent.

Once a selection between agents is done, the agents that become passive take the label non-elected and remain passive until the end of the algorithm, whereas the others try to mark the homebases of these agents that have just become passive. Each active agent knows what are the colors of the other active agents. From its representation of the graph, each active agent can reach the homebases of the passive agents.

The first agent that reaches such a homebase during this round puts a mark with its color on the vertex. The other agents (there is already a mark on the homebase when they reach it) store the color of the agent that owns this vertex (i.e., the color of the mark). Again, at the end of its traversal of the graph, each Remark 3. Note that to refine the labelling µ of the graph (Dir(G), µ), the agents do not have to move in the network. All these computations can be performed only with the information available to each agent. Since all the agents have the same colored map of the network (up to isomorphism) and execute the same algorithm, we know that all the agents will compute exactly the same refined labelling.

If some active agents are in different classes. We suppose now that the labelling µ of (Dir(G), µ) cannot be refined any more, i.e., two vertices (or arcs) have the same number if and only if they are in the same equivalence class, all the active agents own the same number of vertices in each class and two arcs in a same class are either both owned by some agents, or both shared by distinct agents.

At this point, if the active agents are not in the same equivalence class, we are able to select some agents. Consider all the equivalence classes of active agents that contain a minimal number of agents. Among these classes, we select the class [r] such that π(v) is minimal, where v is the homebase of r. The agents that do not belong to this class take the label non-elected and become passive. The agents of the class [r] remain active and try to increase their territory as explained above. Then they try to refine again the labelling µ.

(G, E , p)

1 2 0 0 2 1 2 0 0 2 (G, µ) 1 2 0 B Γ (G ′ ) (G ′ )
Fig. 4. A colored map of a distributed mobile environment (G, E , p) with two agents, the corresponding graph (G, µ) and the digraph B Γ (G ′ ) (G ′ ) where G ′ = (Dir(G), µ). In the representation of (G, E , p) the homebases are represented by double-circled vertices and each vertex belongs to the agent whose homebase has the same color. For sake of clarity, the labels of the arcs in (G, µ) and B Γ (G ′ ) (G ′ ) do not appear.

If G ′ = (Dir(G), µ) is not a covering of B Γ (G ′ ) (G ′ ).
There exist some configurations where it is impossible to select some agents just by using the representation the agents have of the graph, because there is too much symmetry in the graph.

Example 2. Consider the distributed mobile environment corresponding to the graph represented on Figure 4. We suppose that the agents agree on the colored map of the network and on the graph (Dir(G), µ). We can observe that the labelling µ cannot be refined and that (Dir(G), µ) does not admit any well-balanced automorphism.

We now explain how active agents can break these symmetries by marking some vertices or arcs. We suppose that the labelling µ cannot be refined any more and that all the active agents belong to the same equivalence class.

All the active agents agree on the graph G ′ = (Dir(G), µ). All these agents consider the automorphism group Γ (G ′ ) and construct the graphs B Γ (G ′ ) (G ′ ) and G ′ /Γ (G ′ ). We already know that G ′ is fibred over At the end of this round, all the agents give the number q + 1 to the vertices that have just been marked, where q is the greatest label that appears on a vertex in (Dir(G), µ).

B Γ (G ′ ) (G ′ ). If G ′ is not a covering of B Γ (G ′ ) (G ′ ), it
Using this new labelling µ ′ , the active agents try to refine the labelling µ ′ , as explained above.

If G ′ = (Dir(G), µ) is not a covering of G ′ /Γ (G ′ ). We suppose now that the labelling µ cannot be refined any more and that all the active agents belong to the same equivalence class. We suppose also that To select arcs from [a], each agent r just chooses one arc a r in [a] such that s(a r ) belongs to r and then puts a mark with its color on t(a r ). An agent has finished this round if and only if it has marked exactly one vertex: it can be detected from a colored map of the graph. Then, the agents synchronize. Once an agent knows what vertices have been marked by the other agents, it knows what are the arcs that have been marked.

G ′ is a covering of B Γ (G ′ ) (G ′ ) but not of G ′ /Γ (G ′ ). It
At the end of this round, all the agents give the number q + 1 to the arcs that have just been marked, where q is the greatest label that appears on an arc in (Dir(G), µ).

Using this new labelling µ ′ , the active agents try to refine again the labelling µ ′ , as explained above.

If G ′ is a covering of G ′ /Γ (G ′ ). At this point, G ′ = (Dir(G), µ) is a covering of G ′ /Γ (G ′ ).
From Proposition 2, it implies that Γ (G ′ ) contains only well-balanced automorphisms, and since we already know that there is no well-balanced isomorphism of (Dir(G), χ p ) different from Id, we have Γ (G ′ ) = {Id}. Consequently, there is exactly one active agent, since the set of active agents is an equivalence class of the relation induced by Γ (G ′ ) and this agent takes the label elected.

The Characterization

In Section 3, we have shown that if the graph (Dir(G), χ p ) admits a well-balanced automorphism, then it is impossible to solve the election problem on (G, E, p). The algorithm described in Section 4.2 is an algorithm that answers that it is impossible to solve the problem if the graph (Dir(G), χ p ) admits a well-balanced automorphism, and otherwise it successfully elects an agent: it is an effective algorithm. We have therefore proved the following theorems.

Theorem 1. There exists an election algorithm for a distributed mobile environment (G, E, p) if and only if (Dir(G), χ p ) does not admit a non-trivial well-balanced automorphism.

Proof. The necessary condition comes from Proposition 3. For the sufficient condition, we just have to prove that Algorithm 1 elects a leader whenever the necessary condition is satisfied. Consider a distributed colored mobile environment (G, δ, E, p, color) such that (Dir(G), χ p ) does not admit a non-trivial well-balanced automorphism. Consider an execution of Algorithm 1 on (G, δ, E, p, color). From Proposition 4, we know that no deadlock can occur within a round.

Initially, all the agents agree on the labelling µ = χ p of G ′ . After the initialization, each vertex belongs to exactly one agent and each agent knows the owner of each vertex of the graph.

From Remark 3, we know that each time the active agents refine the labelling µ of G ′ , they agree on the new labelling µ ′ of G ′ provided that they agreed on the labelling µ. Since the territory of any agent has not changed, the active agents also know the territory of any other active agent and each vertex still belongs to exactly one active agent.

Furthermore, each time the active agents mark some vertices and arcs, they also agree on the new labelling µ ′ of G ′ whenever they agreed on the labelling µ of G ′ . Since the territory of any agent has not changed, the active agents also know the territory of any other active agent and each vertex still belongs to exactly one active agent.

Finally, when a selection is made between active agents, the labelling µ is not modified and consequently, we know that the active agents always agree on the labelling µ of G ′ . It is easy to see that after such a phase, once the active agents have marked the homebases of agents that have just been defeated, then each vertex belongs to exactly one active agent and each active agent knows the territory of any other active agent.

Consequently, by induction, we know that after each round, all the active agents agree on the labelling µ of G ′ , each vertex belongs to exactly one active agent and each active agent knows the territory of any other active agent.

Note that each time the labelling µ of G ′ is refined, then the number of labels given to vertices and arcs by active agents increases. Since the graph G is finite, we know that the labelling refinment procedure will always terminate. Moreover, each time a selection is made between active agents, the number of active agents decrease. Furthermore, each time active agents mark vertices or arcs, the number of labels given to vertices and arcs by active agents increases. Consequently, there won't be any infinite execution of the algorithm.

Consider now the final configuration of the environment reached after the execution. Suppose that some agent is in the state elected. It means that G ′ is a covering of G ′ /Γ (G ′ ) and since (Dir(G), χ p ) does not admit any non-trivial well balanced automorphism, then from Proposition 2, Γ (G ′ ) = {Id}. Consequently, there is exactly one active agent that took the label elected, i.e., the execution has successfully elected an agent.

Suppose now that in the final configuration, no agent has took the label elected. Since (Dir(G), χ p ) does not admit any non-trivial well balanced automorphism, we know that all the active agents are executing the loop repeat . . . until An agent is elected. Since the execution has terminated, then the labelling µ of G cannot be refined any more and we know that all the agents are in the same equivalence class. In this case, we know that G ′ is a covering of B Γ (G ′ ) (G ′ ), since otherwise the active agents can select vertices. We also know that G ′ is a covering of G ′ /Γ (G ′ ), since otherwise the active agents can select arcs. Consequently, there is exactly one active agent and this active agent took the label elected, which leads to a contradiction.

Consequently, any execution of Algorithm 1 on (G, δ, E, p, color) succesfully elects an agent. Then Algorithm 1 is an election algorithm for (G, δ, E, p, color).

The proof of the following theorem follows from Theorem 1 and the fact that the agents can easily reconstruct a map of the graph, as explained in the description of the algorithm.

Theorem 2. Algorithm 1 is an effective election algorithm.

Complexity of the algorithm

The main goal of this work was to design an effective election algorithm in our model, but it can also be interesting to have a look on the complexity of the algorithm. The traditional coast measures for mobile agents are the number of agents moves (edge traversals) and the amount of time.

To determine the amount of time, we make the following assumptions : the time needed by an agent to perform computations is equal to zero time unit, whereas the time needed by an agent to traverse an edge is equal to one time unit. The time complexity of the algorithm is the time consumed by an execution of the algorithm under these assumptions. In other words, we do not take into account the computation time of each agent, and we suppose that all the agents traverse all the edges at the same speed. Note that the correctness of our algorithm does not rely on these assumptions.

The following proposition gives a bound on the worst case complexity of our algorithm. Proof. To perform the first traversal of the graph, each agent will traverse each edge exactly twice: it can do it in O(m). After this traversal, each agent has a map of the graph, and it can check if the problem can be solved. If it is not possible to solve the problem, the agents just need to do this traversal of the graph to give a correct output: it can be done in O(mk) moves in time O(m). In the following, each time an agent has to check the state of the different vertices, it can use the map of the graph it has reconstructed: it can do it in O(n) moves. The initialization phase of the algorithm can be performed in O(mk) moves in time O(m).

We will consider different phases in the execution of the algorithm. Each time we select a class of agents, we go from phase i to phase i + 1. Let k i denotes the number of active agents at phase i: we know that k i+1 ≤ k i /2, and therefore, there is at most log k phases during each execution of the algorithm.

To perform the synchronization between agents, each active agent has to do a few traversals of the graphs that can be performed in O(n), and therefore, each time the synchronization procedure is applied during the phase i, it can be done in O(nk i ) moves with time O(n). The time needed by the agents to mark the homebases of the agents that become passive at the end of the phase i -1 and to synchronize can be done in O(nk i ) moves with time O(n) . The total time complexity for the territory acquisition is O(n log k).

During the whole execution, the agents will perform at most n times the procedure to mark vertices and m times the procedure to mark arcs. Each time the active agents mark some vertices or some arcs, each agent do its traversal and apply the synchronization procedure in O(n) time (note that even when the agents mark arcs, they do a traversal to visit all the vertices and not all the arcs). The time complexity is therefore O(nn) + O(mn) + O(n log k) = O(mn).

During each phase, some vertices and arcs can be marked. Consider a class [x] of vertices or arcs of size s at the beginning of the phase i. If during the round, there exists a class of vertices or arcs of size lower than k i , some agents will be selected and therefore we go to phase i + 1. Consequently, during the phase i, each active agent mark at most s/k i vertices or arcs in [x], They can do it in O(s/k i * n * k i ) = O(sn) moves. Since the sum of the sizes of all classes of vertices and edges is O(m), the agents need O(mn) moves in each phase to mark vertices and arcs and to synchronize.

Consequently, the total number of moves in one phase is O(nk i ) + O(nn) + O(mn) = O(mn). Therefore, the total number of moves to execute the algorithm is O(mn log k).

⊓ ⊔

Final Remarks

In this paper, we have characterized the distributed mobile environments where the election problem can be solved. The algorithm we present to solve the problem is an effective algorithm: we give a positive answer to the question stated in [START_REF] Barrière | Can we elect if we cannot compare?[END_REF]. Since election and rendezvous are two equivalent problems, we also have characterized the mobile distributed environments where the rendezvous problem can be solved in our model. One can observe that the algorithm and the results presented in this paper can be adapted to other kinds of distributed mobile agent systems. Indeed, the algorithm rely on the two following assumptions :

-each agent can reconstruct a map of the graph with the position of the homebases and can know the exact position of its homebase, -it is possible to identify the author of a message written on the whiteboard of some vertex.

Consequently, if we consider an anonymous mobile agent system where each agent knows initially the network (a map of the graph with the port-numbering function) and its position in the network, then we can solve election and rendezvous if and only if the digraph (Dir(G), χ p ) does not admit any non-trivial well-balanced automorphism. In order to identify the author r of a message written at a vertex v, it is sufficient that the message contains the port-numbers that appear on a path between the vertex v and the homebase p(r) of r. Therefore, if we consider anonymous systems with sense of direction, as considered by Barrière et al. in [START_REF] Barrière | Rendezvous and election of mobile agents: impact of sense of direction[END_REF], we have the same results as in our model, since sense of direction enables each agent to build a map of the network.

In our model, the labels are mutually incomparable. In the quantitative world, we usually suppose that there is always an order between two elements. Between these two extremal cases (a total order or no order at all), one can wonder whether the existence of a partial order between labels really modifies the conditions presented here.

We can also consider a network where the labels cannot be compared, but where we do not assume that each label is unique: is there a characterization of the graphs where the election problem can be solved if there are different agents with the same label? Note that if all the agents have the same label, we are in the anonymous setting, and in this case, we already know that there is no effective algorithm for the class of all graphs. We can still wonder whether there is a characterization of classes of graphs that admit an universal election algorithm or an effective election algorithm.

  Fig. 1. The digraph G is fibred over B Γ (G) (G) via the homomorphism ϕG that maps each vertex of G labelled i to the unique vertex labelled i of B Γ (G) (G). The digraph H is a covering of B Γ (H) (H) via the homomorphism ϕH defined in the same way. The digraph G/Γ (G) (resp. H/Γ (H)) is the digraph whose vertices and arcs correspond to equivalence classes of vertices and arcs of G (resp. H) under the action of Γ (G) (resp. Γ (H)).

Fig. 3 .

 3 Fig.3. The digraph G is a symmetric covering of H via the homomorphism that maps each vertex of G labelled i to the unique vertex labelled i of H.

  implies that there exist two classes of vertices[v] and[v ′ ] such that |[v]| = |[v ′ ]|.Let [r] be the class of the homebases of the active agents.Consider a class [v] such that for each class [v′ ] ≺ [v], |[v ′ ]| = |[r]| and |[v]| = |[r]|.We already know that each active agent owns the same number of vertices in [v] and therefore |[r]| divides |[v]|. Each active agent then marks a vertex it owns that is in[v]. An agent has finished this round if and only if it has marked exactly one vertex in [v]: it can be detected from a colored map of the graph. Then, the agents synchronize.

  means that all the equivalence classes of vertices have the same size s, but there exists an equivalence class of arcs [a] such that |[a]| > s. Instead of marking vertices, we mark arcs in this round. Each class [a] of arcs of G ′ corresponds to exactly one arc in G ′ /Γ (G ′ ). Consider the class of arcs [a] such that for each class [a ′ ] ≺ [a], |[a ′ ]| = s but |[a]| > s. We already know that each active agent owns exactly one vertex in [s(a)] and one vertex in [t(a)]. Since |[a]| > s and since two arcs in the same class are either both owned by an agent or both shared by distinct agents, we know that each arc in [a] is shared.

Proposition 5 .

 5 Consider a distributed mobile environment (G, E, p) where |V (G)| = n, |E(G)| = m and |E| = k. If the election problem cannot be solved in this environment, the agents detect it in O(mk) moves in time O(m). Otherwise, the protocol successfully elects a leader with O(mn log k) moves in time O(mn).

has finished Step (1) in the ith round, (8) of the i -1th round, (3) of the ith round. (2) in the ith round, (8) of the i -1th round, (5) of the ith round. (3) in the ith round, (8) of the i -1th round, (5) of the ith round. (4) in the ith round, (1) of the ith round, (5) of the ith round. (5) in the ith round, (1) of the ith round, (7) of the ith round. (6) in the ith round, (4) of the ith round, (7) of the ith round. (7) in the ith round, (4) of the ith round, (9) of the ith round. (8) in the ith round, (6) of the ith round, (9) of the ith round. (9) in the ith round, (6) of the ith round, (3) of the i + 1th round.

Suppose that there exists a deadlock in the application of the synchronization procedure, i.e., there exists a moment in the execution where all the agents are blocked at some step of the procedure. In each round, the only steps where an agent can be blocked are Steps (3), (5), (7) and (9).

Suppose that an active agent r is blocked at Step (3) of a round i. Then, we know that all the other active agents have finished Step (8) of the i -1th round and consequently, none of them can be blocked at Step (9) of the i -1th round and all of them have finished Step (1) of the ith round. Suppose that during the ith round, there exists k i distinct active agents and let call r 1 the first agent that have finished Step (1) of the ith round, r 2 the second one, r 3 the third one, etc... We consider the agent r j and we suppose that for any j < l ≤ k i , the agent r l has performed Step (4) of the ith round (this hypothesis is trivially true for the agent r ki ). Suppose that the agent r j is waiting at the homebase of another agent r l during Step (3) of the ith round. If l < j, then the agent r l has finished Step 1 of the ith round before r j . Consequently, from the colored map r j constructs during Step (2) of the ith round, r j knows that r l has finished Step (1) of the ith round and then r j cannot wait at the homebase of the agent r l . Suppose now that l > j. We already know that the agent r l has performed Step (4) of the ith round and then r l has marked its homebase. Consequently, the mark r j was waiting for has been put and then r j cannot be waiting on the homebase of r l . Then r j cannot be blocked at Step (3) of the ith round and it has also finished Step (4) of the ith round, since it cannot be blocked at this step.

By induction, it is then easy to prove that no active agent can be waiting for another agent while it is performing Step 3 of a round i.

Suppose now that an active agent r is blocked at Step (5) of a round i. Then all the active agents have finished Step (1) of the ith round and we already know that none of them can be blocked at Step (3) of the ith round. Consequently, each active agent has performed Step (4) of the ith round and then no agent can be waiting for another agent while it is performing Step (5) of the ith round. agent puts a mark on the homebase of another active agent. Therefore, each active agent can detect from a colored map if another active agent has finished this phase. Then the active agents apply the synchronization procedure.

If an agent has marked the homebase of a passive agent, then all the vertices that were belonging to this passive agent belong now to this active agent. In this way, all the active agents agree on the color of the agent that owns any vertex of the graph.

How to refine the labelling µ? During the execution of the algorithm, the agents mark vertices and arcs to break the symmetry that may exist in the network. In this way, at each round, numbers will be associated to some vertices and arcs and we will obtain a labelling of the graph µ. Initially, all the homebases have the label 1 whereas all the other vertices have the label 0 and all the arcs are labelled 0.

At the beginning of each round, from its representation (Dir(G), µ) of the graph, each agent computes the value π(v) (resp. π(a)) for each vertex v ∈ V (Dir(G)) (resp. for each arc a ∈ A(Dir(G))). We say that two agents are equivalent if their homebases are in the same equivalence class, and we use the order ≺ on the homebases of the agents to order the classes of agents.

Since all the agents agree on the order to compare the equivalence classes, we can use the following procedure. If there exist two vertices v, v ′ such that µ(v) = µ(v ′ ) and π(v) = π(v ′ ), then let m be the lowest number such that there exist v, v ′ with µ

, where q is the greatest label that appears on a vertex in (G, µ). The labels of the other vertices are not changed.

We apply the same method to arcs using the order we have on the classes of arcs, i.e., the lexicographic order over the π(a). Thanks to this procedure, two arcs that are not in the same class are given distinct labels.

We repeat this procedure, until all the vertices (resp. all the arcs) that have the same label are in the same equivalence class.

If some active agents do not own the same number of vertices in a given class. We consider now a configuration such that two vertices (resp. ) is true. In this case, we give different numbers to the homebases of the agents that do not own the same number of vertices in [v]. We subdivide the class [r] into a partition R 1 , . . . , R j such that the agents in R i own strictly more vertices in [v] than the agents in R i ′ when i < i ′ . Using the same technique as before, we give different numbers to the homebases of the agents that are not in the same R i and then obtain a new representation of the digraph (Dir(G), µ ′ ).

Then, the agents try to refine again this new labelling.

How to split the arc classes thanks to the colors of their ends? We will say that an arc a belongs to an agent r, if r owns s(a) and t(a). Otherwise, the arc is such that s(a) belongs to an agent r 1 and t(a) to a distinct agent r 2 . We will say that this arc is shared by r 1 and r 2 . If there exists a class of arcs [a] such that some arcs of [a] belong to some agents, whereas the other arcs are shared by distinct agents, then we apply the following technique. Consider a class of arcs a such that for each class [a ′ ] ≺ [a], either [a ′ ] contains only arcs that belong to some agents or [a ′ ] contains only arcs shared by different agents. We suppose also that [a] contains arcs that belong to some agents and arcs that are shared. All the arcs in [a] that are shared by distinct agents are relabelled q + 1, where q is the greatest label that appears on an arc in (Dir(G), µ).

Then, the agents try to refine again this new labelling.


F Lamarche

S Donikian
email: donikian]@irisa.fr

The Orchestration of Behaviours using Resources and Priority Levels

Reproducing daily behaviours requires the ability to schedule behaviours depending on resources (body parts for example) and priority (intentions or physiological parameters) constraints. A simple way is to say that behaviours which are using the same resources are mutually exclusive. This approach is not sufficient to achieve realism purpose, as in real life, we are able to combine them in a much microscopic way. All day long, we mix different behaviours, as for example reading a newspaper while drinking a coffee and smoking a cigarette. If all behaviours using common resources were mutually exclusive, an agent could not reproduce this example, except if a specific behaviour is created. This solution becomes rapidly too complex and has motivated the work presented in this paper. It consists in an extension of HPTS, our behavioural model, by the introduction of resources and priority levels. In the contrary of some previous approaches, it is not necessary to specify exhaustively all behaviours that are mutually exclusive; this is done implicitely by attaching resources to nodes and a priority function to each state machine, and by using a scheduler.

Introduction

The goal of behavioural models is to simulate autonomous entities like organisms and living beings. The issue addressed in our work concerns the specification of a general formalism for behaviour modeling based on psychological studies and compatible with real-time constraints. Information needed to describe the behaviour of an entity depends on the nature of this entity. No theory exists for determining either necessary or sufficient structures needed to support particular capabilities and certainly not to support general intelligence. As direction and inspiration towards the development of such a theory, Newell [START_REF] Newell | Unified Theories of Cognition[END_REF] posits that one way to approach sufficiency is by modeling human cognition in computational layers or bands. Reproducing daily behaviours requires to schedule behaviours depending on resources (body parts for example) and priority (intentions or physiological parameters) constraints. A simple way is to say that behaviours which are using the same resources are mutually exclusive. This approach is not sufficient to achieve realism purpose, as in real life, we are able to combine them in a much microscopic way. All day long, we mix different behaviours, as for example reading a newspaper while drinking a coffee and smoking a cigarette. If all behaviours using common resources were mutually exclusive, an agent could not reproduce this example, except if a specific behaviour is created. This solution becomes rapidly too complex. We have proposed in the past the HPTS model which integrates several psychological requirements. In this paper, we propose to extend this model to be able to manage, in a generic way, resources, adaptation and priority levels. It becomes possible to describe behaviours independently and to adapt automatically their execution when they are running in parallel, with respect to their priorities.

In the next section, related works are presented, while section three focuses on the HPTS model. The integration of resources and priority levels and the overview of the scheduler are presented in section four. Finally section five focuses on an example to illustrate advantages of this new approach.

Related Works

Behavioural models have been developed to describe the human behaviour in specific tasks. The common characteristics of these models are: reactivity, parallelism and different abstract levels of behaviours. As humans are deliberative agents, purely reactive systems are not sufficient to describe their behaviour. It is necessary to integrate both cognitive and reactive aspects of behaviour. Cognitive models are rather motivated by the representation of the agent's knowledge (beliefs and intentions). Intentions enable an agent to reason about its internal state and that of others. The center of such a deliberative agent is its own representation of the world which includes a representation of his mental state and the one of other agents which he is currently interacting with [START_REF] Funge | Cognitive modeling: Knowledge, reasoning and planning for intelligent characters[END_REF]. To achieve such a purpose, Badler et al. [START_REF] Badler | Towards personalities for animated agents with reactive and planning behaviors[END_REF] propose to combine Sense-Control-Action (SCA) loops with planners and PaT-Nets. SCA loops define the reflexive behaviour and are continuous systems which interconnect sensors and effectors through a network of nodes, exactly like in the sensor effector approach described above. PaT-Nets are essentially finite state automata that can be executed in parallel (for example the control of the four fingers and of the thumb for a grasping task). The planner queries the state of the database through a filtered perception to decide how to elaborate the plan and to select an action. More recently they have introduced Parameterized Action Representation (PAR) to give a description of an action, and these PARs are directly linked to PaT-Nets. It allows a user to control Autonomous Characters actions with instructions given in natural language [START_REF] Bindiganavale | Dynamically altering agent behaviors using natural language instructions[END_REF]. In this system, like in others [START_REF] Noser | Sensor based synthetic actors in a tennis game simulation[END_REF], the action is directly associated with each node, which does not allow an explicit management of concurrency.

A lot of models have also been proposed for human like minds in the agent community [START_REF]Formal Models of Agents[END_REF]. They are all based on the perception/treatment/action loop, but they mainly differ in the way the treatment unit is built. As in the Newell theory, A. Sloman [START_REF] Sloman | What sort of control system is able to have a personality[END_REF] proposed an architecture of an intelligent agent in different layers (reflexes, automatic processes, resource-limited reflective management processes, metamanagement processes), involving different routes through the system form perception to action. In his theory, automatic processes have dedicated portions of the brain and can operate in parallel whenever they need, while different management processes have to share a common working memory, and their parallelism is then restricted. F. Brazier et al. [START_REF] Brazier | Formal Models of Agents[END_REF] proposed a model of a rational agent using notions such as beliefs, desires and intentions. In their task hierarchy, beliefs and desires influence each other reciprocally, and they both influence intentions and commitments. S. Ambroszkiewicz and J. Komar [START_REF] Ambroszkiewicz | Formal Models of Agents[END_REF] distinguish six parts in an agent model: perception, desire, knowledge and belief, rational behaviour, reasoning process and intention, and they propose a formal model based on this decomposition.

V. Decugis and J. Ferber [START_REF] Decugis | Action selection in an autonomous agent with a hierarchical distributed reactive planning architecture[END_REF] address an interesting problem: how to combine reactivity and planning capabilities in a real-time application. They propose to extend the ASM (Action Selection Mechanism) proposed by Maes [START_REF] Maes | Situated agents can have goals[END_REF] into hierarchical ASMs. At the bottom of the hierarchy, basic reflexes are found, such as reflex movements orientation and basic perceptive mechanisms, while higher levels integrate more complex behaviours. B. Rhodes [START_REF] Rhodes | PHISH-Nets : Planning Heuristically In Situated Hybrid Networks[END_REF] has proposed another extension of ASM, called Phish-Nets. This model permits to use parameterized actions and to specify relations between them (inhibiting and preceding). In such models, reactive planning is possible, but the main drawback is the need of an exhaustive specification of all possible interactions between actions.

According to Newell, our goal is to build a model which will allow some adaptative and flexible behaviour to any entity evolving in a complex environment and interacting with other entities. Interactive execution is also fundamental. This has lead us to state that paradigms required for programming a realistic behavioural model are: reactivity (which encompasses sporadic or asynchronous events and exceptions), modularity in the behaviour description (which allows parallelism and concurrency of subbehaviours), data-flow (for the specification of the communication between different modules), hierarchical structuring of the behaviour (which means the possibility of preempting sub-behaviours). HPTS [START_REF] Donikian | Reactivity, concurrency, data-flow and hierarchical preemption for behavioural animation[END_REF], as HCSM [START_REF] Ahmad | Hierarchical, concurrent state machines for behavior modeling and scenario control[END_REF], is a model based on hierarchical concurrent state machines, and it offers a set of programming paradigms which permit to address hierarchical concurrent behaviours. HPTS offers also the ability to manage time informations (such as reaction time, state frequency, delay, minimal and maximal durations), undeterministic choices [START_REF] Donikian | HPTS: a behaviour modelling language for autonomous agents[END_REF].

HPTS

HPTS [START_REF] Donikian | Reactivity, concurrency, data-flow and hierarchical preemption for behavioural animation[END_REF] which stands for Hierarchical Parallel Transition Systems, consists of a reactive system, which can be viewed as a multi-agent system in which agents are organized as a hierarchy of state machines. Each agent of the system can be viewed as a blackbox with an In/Out data-flow and a set of control parameters. The synchronization of the agent execution is operated by using state machines. To allow an agent to manage concurrent behaviours, sub-agents are organized inside sub-state machines. In the following, agents will be assimilated to state machines. Each state machine of the system is either an atomic state machine, or a composite state machine. Though the model may be coded directly with an imperative programming language like C++, we decided to build a language for the behaviour description. Figure 1 presents the syntax of the behavioural programming language which fully implements the HPTS formalism. As this paper focuses on the integration and management of resources and priority levels, the behavioural description language is not described in details. For a complete description of the model (except for resources and priorities) refers to [START_REF] Donikian | HPTS: a behaviour modelling language for autonomous agents[END_REF]. Keywords are written in bold, whereas italic typeface represents a non-terminal rule. A * stands for a 0..n repetition while a + stands for a 1..n repetition and a statement enclosed in { } is optional. The description of a state machine is done in the following way: the body of the declaration contains a list of states and a list of transitions between these states. A state is defined by its name and its activity with regard to data-flows. A state accepts an optional duration parameter which stands for the minimum and maximum amount of time spent in the state. A state machine can be parameterized; the set of parameters will be used to characterize a state machine at its creation. Variables are local to a state machine. Only variables that has been declared as outputs can be viewed by the meta state machine. A transition is defined by an origin, an extremity, a transition expression, two optional parameters and a transition body. The transition expression consists of two parts: a read-expr which includes the conditions to be fulfilled in order to fire the transition, and a write-expr which is a list of the generated events and basic activity primitives on the state machine. The body of a transition (C++ code) is executed after the action part. As for the body part of a state, it is possible to call extern functions or methods and to access to the value of outputs of sub-state machines. Afterwards, C++ code for our simulation platform is generated. It is totally encapsulated: all transitions systems are included in their own class directly inheriting from an abstract state machine class which provides pure virtual methods for running the state machines and debugging methods. An interpreter has also been implemented, which is very useful for the behaviour specification phase as it allows to modify state-machines during the execution phase.

SMACHINE Id ; { //

Behaviour synchronization

In order to synchronize behaviours and to allow efficient mixing of behaviours in accordance with their relative importance, notions of resources, degrees of preference and priorities have been introduced. Resources allow to describe exclusions between behaviours while degrees of preference are used to describe different possible realizations or possibilities of adaptation of a behaviour. Using this information, a scheduler automatically synchronize the different behaviours according to their respective priorities.

Resources

For all state machines running in HPTS hierarchy, a set of resources is defined. Those resources are considered as semaphores, thus they are used for mutual exclusion. A set of resources is associated to each node of a state machine; it contains all resources used by a node. Hence, resource allocations are adapted to the state machine granularity. This type of description allows to handle resource allocations automatically:

• Entering a node implies that its associated resources are taken.

• Exiting a node implies that its resources are released.

• A resource will be kept if two nodes connected by a transition use it.

As resources are semaphores, one constraint has to be respected while running parallel state machines: all nodes executed in parallel have to use different resources. Using this constraint it becomes possible to synchronize the execution of parallel state machines according to the resources they use, by only authorizing transitions in nodes which do not use allocated resources.

Given that several parallel state machines are using the same set of resources, the problem of dead lock has to be studied. A dead lock occurs when the dependency graph of resources is cyclic. Therefore, in order to ensure maximum security and to make synchronization easier to handle, it is necessary to provide a mechanism ensuring that no dead lock can arise. While compiling the different state machines, information about resources allocation dependencies are pre-compiled. Thus, at runtime, the scheduler is able to use this information in order to check upon the fact that executing two nodes in parallel can not lead to a deadlock. This mechanism is very useful because it allows describing behaviours without precise knowledge on other behaviours.

As HPTS is a hierarchical model, each state machine can create sons and wait for their ending; this type of synchronization creates dependencies between state machines. Consequently, it exists risks of dead lock if a state machine using common resources with its son waits until its ending. Thus, another constraint has been added: resources used by a state machine must be different than resources used by its descendants. Respecting this constraint ensures that all descendants can be executed and terminated before the ending of their ascendants. As structure of state machines is known before runtime, this constraint can be checked while compiling state machines. By now those resources are used to describe internal resources of the agent like its hands, eyes or legs. They allow synchronizing behaviour in accordance to body parts they use.

Degrees of preferences

The notion of degree of preference has been introduced in order to provide the ability to describe different possibilities of adaptation of a behaviour, depending on resources availability.

A degree of preference (p) is associated to each transition of a state machine. It is a real coefficient with value in interval [-1; 1]. This coefficient corresponds to the state machine proclivity to use this transition when the associated condition is true. Depending on its value, it has different meanings:

• p > 0: This transition favors the realization of the behaviour. By default, the transition having the greatest degree of preference should be chosen. • p < 0: This transition does not favor the realization of the behaviour. Those transitions are used to describe a coherent way of stopping behaviour or adapting its execution while releasing some resources. • p = 0: the behaviour is quite indifferent to this transition. This coefficient allows to concentrate all information about a specific behaviour into one state machine. Due to state machine structure, the concentration ensures consistency during the realization of the behaviour.

Let consider the state machine of figure 2; transitions are labeled with their associated conditions and degrees of preference. It describes a behaviour consisting in moving an object. While moving an object, eyes are necessary when taking the object and putting it somewhere; but while moving it, it is possible to focus on the object or to look at something else. Transition starting from state MoveAndWatch and ending by MoveObject has a degree of preference of -0.4 which specifies that, by default, this transition should not be used, except if another behaviour needs to take eyes resource.

The reciprocal transition has a degree of preference of 0.4 according the same positive preference to return into state MoveAndWatch. Using degrees of preference, this behaviour is totally described. Then the scheduler will choose to force behaviour to transit in the state which does not use eyes or to stay in the state which uses the eyes if no other behaviour needs the eyes.

Priority

The notion of priority has been introduced to provide the ability to specify the importance of a behaviour relatively to others. A priority function is associated to each state machine running in HPTS hierarchy. This function returns a real value representing the importance of a behaviour in a given context. Depending on its sign, this function has different meanings:

• priority > 0: the behaviour must be achieved, and is adapted to the current context. This value can be interpreted as a coefficient of adequacy between context and behaviour. • priority < 0: the behaviour is inhibited, the value can be interpreted as a coefficient of inadequacy between context and behaviour.

This function is user defined. Thus, it can be correlated to different parameters, such as for example:

• physiological parameters;

• a value related to a plan generated by a rational model, in that case, it is correlated to the importance of the goal this action contributes to satisfy: • a stimuli related to the environment to handle reflex behaviours.

This priority function provides an easy way to control the behaviour realization.

Scheduling

Notions explained below are used to create a scheduler. It allows to schedule different parallel behaviours in such a way that behaviours having the greatest priority will be favored in their execution and will automatically adapt their execution, if it is possible, to the other ones which are running. State machines are executed at a fixed frequency. Thus, a scheduling is computed at each time step. At the beginning of the time step, scheduler collects information from each state machine. This information is compounded of the current state of a state machine plus all accessible nodes (i.e. nodes ending a transition with a true condition and starting from current node) ; this results in the creation of a set of possible transitions.

Then the scheduler computes a weight for each transition of this set. Let note prio the current priority of the considered state machine, p the degree of preference associated to the transition ending with the state e. The weight (W ) associated to this transition is computed as follow:

W = prio * p (1)
Let consider a weight W associated to a proposition, this weight has different meanings:

• W > 0: state machine is proned to transit in the state associated to the proposition. Two cases can arise:

-(prio > 0) ∧ (p > 0): transiting to this node favors the accomplishment of the behaviour. -(prio < 0) ∧ (p < 0): the behaviour is inhibited; transitions that conduct to a coherent stop of the behaviour have to be favored. • W < 0: state machine is not proned to transit in this node. Two cases can arise:

-(prio > 0) ∧ (p < 0): transiting in this state does not favor the realization of the behaviour. This case can be used for proposing a possibility of adaptation of the behaviour releasing some resources that are not necessary. It can also be used to stop behaviour execution because a behaviour having a greater priority needs resources used by the considered behaviour. -(prio < 0) ∧ (p > 0): the behaviour is inhibited, this case can be used to propose an other possibility of stopping behaviour using less resources. • W = 0: state machine is indifferent to transit in this node.

Once weights associated to each proposition of transition of the state machines are computed, the scheduler is searching for a combination of propositions between all state machines respecting resource constraints (no resource conflict and no possible deadlock) and maximizing the sum of associated weights. Therefore, behaviours having the greatest priorities will be favored in their execution while those having lowest priorities will release their resources, if possible and in a consistent way. Adaptation between concurrent behaviours becomes automatic when the concurrency concerns the sharing of common internal resources.

Example

Let us consider a complex behaviour consisting in drinking a coffee and smoking a cigarette while reading a newspaper. This kind of combination of multiple behaviours can not be directly handled by systems using mutual exclusion on behaviours which use themselves common resources. Moreover, a specific behaviour has to be created for systems using only semaphores synchronization without notions of priority and adaptation. In this section, we will study this example and show how the scheduler, helped with notions of resources, degrees of preference and priorities, is able to reproduce this behaviour just by describing independently the three sub-behaviours and their associated priority functions.

Behaviour description

All state machines use the following set of resources: Hl (left hand), Hr (right hand), rHl (reserve left hand), rHr (reserve right hand), M (mouth) and E (eyes). Resources rHl/rHr are used to handle releasing of resources Hl/Hr. The scheduler can only act on the next transition of a state machine. Hands are resources that often need more than one transition to be freed, for instance, putting down an object to free the hand resource. Thus, in order to free the hand resource Hr/Hl, resource rHr/rHl have to be taken. Then propositions of transitions in states only using resource Hr/Hl propose a sequence of actions freeing hand resources.

The behaviour is compounded of three sub behaviours: read a newspaper, drink a coffee and smoke a cigarette. All state machines used to solve this problem are presented in figures 3, 4 and 5. In these state machines, resource H stands for Hr or Hl as it exists the same behaviour for each hand. Note that descriptions of state machines are totally independent one from each other. Drinking and smoking: Those two behaviours are described through the same state machine consisting in grasping the object of interest, moving it to the mouth and keeping the object into the hand. The object is put on the table if another behaviour needs hand resource or if the current behaviour becomes inhibited.

Reading the newspaper: This behaviour consists in two parallel sub-behaviours. One consists in reading the newspaper with different possibilities of pause depending on the text structure. Those different levels of interruption are described through degrees of preference. The second consists in manipulating the newspaper taking it into the hand and moving it near the eyes.

Note that thanks to resources, each behaviour is described independently from the others but propose different possibilities of adaptation. Each possibility of adaptation is described through degrees of preference allowing specifying the cost of such adaptation. Moreover, as a mechanism ensures that no deadlock can arise, conceiving a behaviour does not need to know other described behaviours.

Defining priorities: the importance of behaviours described below depends on different parameters. The difficulty arises with the fact of unifying priority functions that depend on different parameters.

Drinking and smoking: those two behaviours have variable priorities evolving with the time. Those priorities are directly correlated to the thirst/need of nicotine. Let note p(t) the priority function where t represents the time. It has the following definition:

p(t) = p(t -dt) + dp 1 × dt if not(consuming) p(t) = p(t -dt) -dp 2 × dt if consuming (2)
where dp 1 (respectively dp 2 ) is the increase rate (respectively the decrease rate) of the thirst or the need of nicotine. Consuming stands for drinking or smoking depending on the behaviour. Then, when instantiating state machines corresponding to those behaviours, dp 2 becomes a parameter as well as the priority function which is linked to the thirst or the need of nicotine.

Reading: priority of reading behaviour is correlated to the interest of the reader for the text. In this example the function is defined as a constant. The behaviour having the greatest priority is the reading one while behaviour allowing to manipulate the sheet has a lower priority.

Note that once behaviours are described through state machines, they are controlled through their priority. This property allow to handle every type of executive behaviour without need of information about their internal structure in term of resources or possible adaptations.

Scheduling the example

In order to handle the reading behaviour, another behaviour has been added which consists in moving a sheet of paper with the right hand in front of the agent in order to read, and when the sheet is read, it is moved and the next sheet is taken. Moving the sheet of paper is handled by the behaviour described in figure 2. The priorities have been defined as follow:

• Moving sheet, followed by reading the sheet have a constant priority of 2.0.

• Manipulating the sheet while reading have a constant priority of 1.5 and can be realized with right or left hand. • Drinking and smoking behaviours have a variable priority function. It is the function given in equation 2. Their increase rates are respectively set to 0.02/0.05 per second whereas their decrease rates are respectively set to 0.08/0.07 per second. Moreover, corresponding state machine stay in state Consume for a maximum time of one second, and stay in state Pause for a minimum of 10 seconds.

During execution phase, moving sheet behaviour is followed by manipulating and reading sheet behaviours, while drinking and smoking behaviours are continually running. Figure 6 describes evolution of drinking and smoking priorities during the simulation. By default thirst and need of nicotine levels are increasing. Decrease is due to consumption linked to drinking and smoking behaviours. Note that thirst and need of nicotine never decrease at the same time, due to mutual exclusion on mouth noticed in node Consume of the corresponding state machine.

Figure 7 shows activity of each running behaviour. Activity is defined by states using resources Hr/Hl/E/M, which can be assimilated to active resources (i.e. resources enabling manipulation of body parts). In this figure, 1 stands for the activity of reading the sheet of paper, 2 the activity of moving the sheet of paper, 3 the activity of smoking with the left hand, 4 the activity of drinking with the right hand, 5 the activity of manipulating the sheet of paper with the left hand and 6 the activity of manipulating the sheet of paper with the right hand. Parallelization of actions shown in this figure and mutual exclusion of behaviours are automatically handled by the scheduler. It exploits all propositions of transitions of state machines describing behaviours. For example, at time 30 -40, interruption of smoking behaviour, whereas its priority is active, is due to request of left hand resource by behaviour consisting in manipulating the sheet, which has a greater priority. This organization of behaviours has been automatically generated by the scheduler such as the overall realization of the example (Cf. figure 8).

The overall example has been designed in one day, helped by a high level pilot allowing to control character animation through simple primitives. It shows the advances of the scheduling system which allows to describe independently all behaviours with their different possibilities of adaptation. During running phase, their adaptation to all other running behaviours is automatic. Moreover, consistency is ensured because the scheduler can only exploit propositions of transition of each state machine which are supposed to be consistent.

Conclusion

We have presented in this paper a generic approach to integrate the management of resources and priority levels into HPTS, our formal model. This formal model has been implemented in a description language which is able to generate efficient C++ code for GASP, our Simulation Platform. The behavioral model allows us to describe, in a same way, different kinds of living beings, and to simulate them in the same virtual environment, while most of behavioral models are presently restricted to the animation of one model in a specific environment.

Another important point is that our behavioral model has been built to generate dynamic entities which are both autonomous and controllable, allowing us to use the same model in different contexts and moreover with different levels of control. Resources and priorities are described in an easy way, and behaviour incompatibilities are automatically detected. The scheduling algorithm enables us to combine together and to orchestrate several behaviours, depending on the human character intentions and desires.

In the contrary of some previous approach, it is not necessary to specify exhaustively all behaviours that are mutually exclusive; this is done implicitly just by attaching resources to nodes and a priority function to each state machine, and by using a scheduler. Actually, our scheduler is able to handle a fixed number of resources declared at compilation time. An extension would be to allow resource declaration at runtime in order to handle external resources. Another extension will be to connect this work to a higher level of reasoning.

Video sequences related to the example can be found at http://www.irisa.fr/prive/donikian/resources/.

Figure 2 .

 2 Figure 2. Moving object behaviour.

Figure 3 .Figure 4 .Figure 5 .

 345 Figure 3. Common behaviour for drinking and smoking.

Figure 6 .

 6 Figure 6. Evolution of drinking and smoking priorities during simulation. x axis corresponds to elapsed time in seconds, y axis corresponds to the priority value.

Figure 7 .

 7 Figure 7. Activity of behaviours during simulation.

Figure 8 .

 8 Figure 8. Behavioural Coordination Example.

University of Rennes I

CNRS