František Kardoš
email: frantisek.kardos@upjs.sk

Matjaž Krnc
email: matjaz.krnc@gmail.com

Borut Lužar
email: borut.luzar@gmail.com

Riste Škrekovski

Cyclic 7-edge-cuts in fullerene graphs

Keywords: fullerene, fullerene graph, cyclic edge-connectivity, cyclic edge-cut

published or not. The documents may come

Introduction

Mathematicians adopted the notion of fullerenes and defined the fullerene graphs as the plane cubic 3-connected graphs with only pentagonal and hexagonal faces. Nanotubes are members of the fullerene structural family. They are cylindrical in shape with the ends typically capped with a hemisphere of the fullerene structure. Nanotubes with the ends left open (open-ended nanotubes) are also interesting objects, see e.g. [START_REF] Zhang | k-resonance of open-ended carbon nanotubes[END_REF].

Došlić proved that fullerene graphs are cyclically 4-edge connected [START_REF] Došlić | On some structural properties of fullerene graphs[END_REF] and cyclically 5-edge connected [START_REF] Došlić | Cyclical edge-connectivity of fullerene graphs and (k, 6)-cages[END_REF]. The cyclic edge-connectivity of a fullerene graph cannot exceed 5, since it contains twelve pentagons, thus, there are at least twelve cyclic 5-edge-cuts -formed by the edges pointing outwards of each pentagonal face. There are also cyclic 6-edge-cuts formed by the edges pointing outwards of each hexagonal face. These cyclic 5-and 6-edge-cuts will be called trivial. Kardoš and Škrekovski [START_REF] Kardoš | Cyclic edge-cuts in fullerene graphs[END_REF] characterized 5and 6-edge-cuts, and independently the 5-edge-cuts were characterized by Kutnar and Marušič [START_REF] Kutnar | On cyclic edge-connectivity of fullerenes[END_REF].

An edge-cut of a graph G is a set of edges C ⊂ E(G) such that G -C is disconnected. A graph G is k-edge-connected if G cannot be separated into two components by removing less than k edges. An edge-cut C of a graph G is cyclic if each component of G -C contains a cycle. A graph G is cyclically k-edge-connected if G cannot be separated into two components, each containing a cycle, by removing less than k edges.

A cyclic edge-cut C of a fullerene graph G is non-degenerated, if both components of G -C contain precisely six pentagons. Otherwise, C is degenerated. Obviously, the trivial cyclic edge-cuts are degenerated.

There is a family of fullerene graphs, which have many non-degenerated cyclic edgecuts -the nanotubes. A fullerene graph is a nanotube, if it can be divided into a cylindrical part containing only hexagons, and two caps, each containing six pentagons and some hexagons. The cylindrical part should have the following structure: It contains a ring of hexagons h 1 , h 2 , . . . , h p such that after unfolding it back into the hexagonal grid, there are two unit vectors a 1 and a 2 forming a 60 • angle such that each h i -h i-1 is either a 1 or a 2 for i = 1, . . . p, h 0 = h p . (Here the hexagons are identified with their centers.) In this case, the cylindrical part is an open-ended nanotube of type (p 1 , p 2 ), where p j denotes the number of occurences of a j , j = 1, 2. The pair (p 1 , p 2 ) of coefficients in the equation r = p 1 a 1 + p 2 a 2 fully determines the type of the nanotube. It is easy to see that the vectors a 1 and a 2 can always be chosen in such a way that p 1 ≥ p 2 . The nanotubes of types (n, 0) are called zigzag, those of types (n, n) are called armchair (both types have mirror symmetry), the others are chiral (without mirror symmetry). In the light of this definition, also the buckyball C 60 can be viewed as the first in the series of nanotubes of type [START_REF] Klein | Theorems for carbon cages[END_REF][START_REF] Klein | Theorems for carbon cages[END_REF] with a single layer of hexagons in the cylindrical part.

a 1 a 2 p 1 a 1 + p 2 a 2 h 1 h 2 h 3 h 4 C e 1 e 2 e 3
The nanotubes that are interesting in material science usually have the length-todiameter ratio very large. But in many other fullerenes the nanotube-like structure can be found. We say that two non-degenerated cyclic edge-cuts are parallel if both of them induce the two partitions containing the same six pentagons in each, and the corresponding rings of hexagons do not share a face. Such a ring of hexagons is denoted a layer, and the maximal number of parallel layers is the lenght of a nanotube.

It is easy to see that the ring of hexagons induces a non-degenerated cyclic edge-cut in a nanotube. In [START_REF] Kardoš | Cyclic edge-cuts in fullerene graphs[END_REF] it was proven that nanotubes are the only graphs having nondegenerated cyclic 5 and 6-edge-cuts, however, there exist graphs that are not nanotubes and have non-degenerated cyclic k-edge-cut, for some k ≥ 7. In the paper we consider non-degenerated cyclic 7-edge-cuts and prove that there exist precisely two fullerenes with non-degenerated cyclic 7-edge-cut, which are not nanotubes.

2 = + + Figure 2:
The buckyball is the first nanotube of type [START_REF] Klein | Theorems for carbon cages[END_REF][START_REF] Klein | Theorems for carbon cages[END_REF].

Below we pose some known results regarding the non-trivial cyclic 5-and 6-edge-cuts. Let G k denote a fullerene graph comprised of two caps formed by six pentagons, and k layers of hexagons, see Fig. 3.

Theorem 1 A fullerene graph has non-trivial cyclic 5-edge-cut if and only if it is isomorphic to the graph G k for some integer k ≥ 1.

Figure 3: The graphs G k are the only fullerene graphs with non-trivial cyclic 5-edge-cuts.

As an immediate corollary we obtain that all non-trivial cyclic 5-edge-cuts in fullerene graphs are non-degenerated.

An important notion in this paper is a cut-vector. Let G be a fullerene graph and C a k-edge cut in G, and let H be one of the components of graph G -C. We label the vertices of degree one or two in H by v 1 , v 2 , . . . , v k . Let α i be the number of 3-vertices between v i and v i+1 (notice that v k+1 = v 1 ) on the segment on the outer face. Note that each vertex x of degree one in H is treated as two 2-vertices y and w. We define that between y and w there is -1 vertex of degree three.

We name the sequence [α 1 , α 2 , . . . , α k ] a cut-vector v(C) regarding H. It is easy to see that the components α i in fullerenes could only have values -1, 0, 1, 2 or 3, since each face of G is of size 5 or 6, see Fig. 4 for examples. Observe, that each nondegenerated cyclic edge-cut has two complementary cut-vectors associated with each of the components of G -C. Here complementary means that knowing one of them is enough, since the sum of components of the same index is in fullerenes always equal to two (only edges of hexagons are elements of non-degenerated cyclic edge-cut). The sum of cut-vector's components has a nice property, which is given in the following lemma: Lemma 1 Let C be a non-degenerated k-cut in a fullerene graph G, and let α = [α 1 , α 2 , . . . , α k ] be one of its two cut-vectors. Then,

α 1 + α 2 + • • • + α k = k.
To prove the lemma above, we use an extension of a result from [4, Lemma 1]: Lemma 2 Let C be an edge-cut in a fullerene graph G and H a component of G-C. Let n 1 and n 2 be the number of vertices of degree one and two, f 5 the number of pentagons, and l the size of the outer face of H. Then, 6 -

f 5 = 4n 1 + 2n 2 -l.
Proof. Let m be the number of edges, n 3 the number of 3-vertices, and f 6 the number of hexagons. Then

n 1 + 2n 2 + 3n 3 = 2m = 5f 5 + 6f 6 + l.
Using Euler's formula, we also have that

n 1 + n 2 + n 3 + f 5 + f 6 + 1 -m -2 = 0.
Putting it all together we get

(2n 1 + 4n 2 + 6n 3 -4m) + (5f 5 + 6f 6 + l -2m) + 4n 1 + 2n 2 + f 5 -l -6 = 0,
and hence 4n 1 + 2n 2l = 6f 5 .

Proof of Lemma 1. Let H be the component of G -C that corresponds to α. By the choice of C, H has n 1 1-vertices, n 2 2-vertices, where 2n 1 + n 2 = k, and six 5-faces. The length of its outer face is

l = k + k i=1 α i = 2n 1 + n 2 + k i=1 α i .
On the other hand, by Lemma 2 we have

l = 4n 1 + 2n 2 .
Hence

k i=1 α i = 2n 1 + n 2 = k,
which proves the lemma.

The type of a cut-vector α is the vector obtained from α after omitting the components with value 1. For example, the type of the cut-vector [2, 1, 1, 0, 1, 2, 0] is [2, 0, 2, 0]. If no two consecutive components of the cut-vector's type have the same value, we say that the cut is nanotubical. The notion nanotubical derives from the fact, that the two same consecutive components imply that there are all three direction vectors contained in the cut, and we know that the fullerene is a nanotube if and only if there exists a cut containing only two direction vectors.

The notion of cut-vector defined, we can now proceed with cyclic 6-edge-cuts. Unlike cyclic 5-edge-cuts, there exist degenerated cyclic 6-edge-cuts, which are not trivial.

Theorem 2 There are precisely seven non-isomorphic graphs that can be obtained as components of degenerated cyclic 6-edge-cuts with less than six pentagons. Moreover, the graphs with i pentagons are unique for i = 0, 1, 2, 3, 4. Non-degenerated cyclic 6-edge-cuts are, similarly as cyclic 5-edge-cuts, nanotubical. In [START_REF] Kardoš | Cyclic edge-cuts in fullerene graphs[END_REF] the following characterization is given: Theorem 3 A fullerene graph has non-degenerated cyclic 6-edge-cut if and only if it is a nanotube of type (p 1 , p 2 ), where (a) p 1 + p 2 = 6; or (b) p 1 = 5, p 2 = 0, with at least 2 layers of hexagons.

6D01 6D02 6D03 6D04 6D05 6D06 6D07

Degenerated cyclic 7-edge-cuts

In this section we list the degenerated cyclic 7-edge-cuts. There are 57 non-isomorphic graphs that can be obtained as components of degenerate cyclic 7-edge-cuts with less then 6 pentagons. To obtain the configurations we used the reverses of operations O 1 , O 2 and O 3 presented in [START_REF] Kardoš | Cyclic edge-cuts in fullerene graphs[END_REF]. Each of the three operations modifies the cyclic k-edge-cut C into another cyclic edge-cut C i . Below a brief description of the operations is given (see also Fig. 5).

(O 1 ) If a component H contains a vertex of degree one, then using (O 1 ) one can modify the k-edge-cut C into a (k -1)-edge-cut C 1 .

(O 2 ) If a component H contains two adjacent vertices of degree two, then using (O 2 ) one can modify the k-edge-cut C into a k-edge-cut C 2 .

(O 3 ) If the vertices of the outer faces of H are consecutively of degree 2 and 3, then using Using the three operations, all cyclic edge-cuts in a fullerene could be constructed, see [START_REF] Kardoš | Cyclic edge-cuts in fullerene graphs[END_REF]Theorem 1]. Note that the operation O 3 can be applied only if there are six pentagons in the configuration H, therefore when reconstructing degenerated cyclic edge-cuts from the trivial ones, it is never used. On Fig. 6 an example of constructing a degenerate cyclic 7-edge-cut is presented, and on Fig. 7 we listed the degenerated cyclic 7-edge-cuts.

(O 3 ) one can modify the k-edge-cut C into a k-edge-cut C 3 . H C H C H C ↓ (O 1 ) ↓ (O 2 ) ↓ (O 3 ) H 1 C 1 H 2 C 2 H 3 C 3
(O 1 ) ←- (O 2 ) ←- (O 2 ) ←- ↑ (O 2 ) (O 2 ) -→ (O 2 ) -→ (O 2 ) -→ Figure 6: An example of construction.
On Table 1 for each configuration depicted on Fig. 7 we list the number of pentagonal and hexagonal faces (denoted by f 5 and f 6 ), the number of vertices (denoted by v), the cut-vector, and the configurations that arise when applying operations O 1 , O 2 and an inverse O - cut Regarding nanotube types, where the sum p 1 + p 2 < 7, it was already proven in [START_REF] Kardoš | Cyclic edge-cuts in fullerene graphs[END_REF] that only graphs G k contain non-trivial cyclic 5-edge-cuts, in other words, for p 1 +p 2 = 5, only nanotubes of type (5, 0) exist. On the other hand, there are more possible types for p 1 + p 2 = 6. For type (6, 0) there exist five different caps, while for types (5, 1), (4, 2), and (3, 3) caps are unique. On Fig. 8 the caps retrieved from nanotubes of specified types are presented. Note that nanotubes with p 1 + p 2 < 5 do not exist, due to cyclic 5-edge-connectivity of fullerenes.

f 5 f 6 v cut-vector O 1 O 2 O -1 2 D01 0 1 7 [-1, 1, 0, 0, 0, 0, 1] 6D01 - D05 D02 1 0 7 [-1, 0, 1, 0, 0, 0, 2] 6D02 - D05, D06 D03 1 0 7 [-1, 1, 0, 0, 1, -1, 2] 6D02 - D05, D06 D04 1 0 7 [-1, 1, 0, 1, -1, 1, 1] 6D02 - D06, D07 D05 1 1 9 [0, 0, 0, 1, 0, 0, 1] - D02, D03 D08 D06 2 0 9 [-1, 1, 0, 1, 0, 0, 2] 6D03 D02, D03, D04 D08, D09, D10 D07 2 0 9 [-1, 1, 1, 0, 0, 1, 1] 6D03 D03 D09, D10 D08 2 1 11 [0, 0, 1, 0, 1, 0, 1] - D05, D06 D11, D12 D09 3 0 11 [0, 0, 1, 1, 0, 0, 2] - D06, D07 D11, D13 D10 3 0 11 [-1, 1, 1, 0, 1, 0, 2] 6D04 D06, D07 D12, D13, D14, D15 D11 3 1 13 [0, 1, 0, 1, 0, 1, 1] - D08, D09 D16, D17 D12 3 1 13 [0, 0, 1, 1, 0, 1, 1] - D08, D10 D17, D18 D13 4 0 13 [0, 0, 2, 0, 1, 0, 2] - D09, D10 D17, D19 D14 4 0 13 [-1, 2, 0, 1, 1, 0, 2] 6D05 D09 D18, D20 D15 4 0 13 [-1, 1, 1, 1, 0, 1, 2] 6D05 D09 D18, D19, D20, D21, D22 D16 4 1 15 [0, 1, 1, 0, 1, 1, 1] - D11 D23, D24, D25 D17 4 1 15 [0, 1, 0, 1, 1, 0, 2] - D11, D12, D13 D24, D25, D26, D27 D18 4 1 15 [0, 0, 1, 1, 1, 0, 2] - D12, D14, D15 D27, D28, D29, D30 D19 5 0 15 [0, 0, 2, 1, 0, 1, 2] - D13, D15 D27 D20 5 0 15 [-1, 2, 0, 2, 0, 1, 2] 6D06 D14, D15 D29, D30, D31 D21 5 0 15 [-1, 1, 2, 0, 1, 1, 2] 6D06 D15 D30, D32 D22 5 0 15 [-1, 1, 1, 1, 1, 0, 3] 6D06 D15 - D23 5 1 17 [0, 1, 1, 1, 1, 0, 2] - D16 D34 D24 5 1 17 [0, 1, 1, 1, 0, 1, 2] - D16, D17 D35
-1, 2, 1, 0, 1, 1, 2] 6D07 D20 D41, D42 D32 5 1 17 [-1, 2, 0, 1, 1, 1, 2] 6D07 D21 D42, D43 D33 5 1 17 [-1, 1, 1, 1, 1, 1, 2] 6D07 - D43 D34 5 2 19 [0, 1, 1, 1, 1, 1, 1] - D23 - D35 5 2 19 [0, 1, 1, 1, 1, 0, 2] - D24, D26 D44 D36 5 2 19 [0, 1, 1, 1, 0, 1, 2] - D26, D25 D45 D37 5 2 19 [0, 1, 1, 0, 2, 0, 2] - D26, D27 D46 D38 5 2 19 [0, 1, 1, 0, 1, 1, 2] - D27, D28 D46 D39 5 2 19 [0, 1, 1, 1, 1, 1, 1] - D28 - D40 5 2 19 [0, 1, 0, 1, 2, 0, 2] - D28, D29, D30 D47, D48 D41 5 2 19 [0, 0, 2, 1, 0, 1, 2] - D29, D31 D48 D42 5 2 19 [0, 0, 2, 0, 1, 1, 2] - D30, D31, D32 D48, D49 D43 5 2 19 [0, 0, 1, 1, 1, 1, 2] - D32, D33 D49 cut f 5 f 6 v vector O 1 O 2 O -1 2 D44 5 3 21 [0, 1, 1, 1, 1, 1, 1] - D35 - D45 5 3 21 [0, 1, 1, 1, 1, 0, 2] - D36 D50 D46 5 3 21 [0, 1, 1, 1, 0, 1, 2] - D37, D38 D51 D47 5 3 21 [0, 1, 1, 0, 1, 2, 1] - D40 D52 D48 5 3 21 [0, 1, 0, 2, 0, 1, 2] - D40, D41, D42 D52, D53 D49 5 3 21 [0, 1, 0, 1, 1, 1, 2] - D42, D43 D53 D50 5 4 23 [0, 1, 1, 1, 1, 1, 1] - D45 - D51 5 4 23 [0, 1, 1, 1, 1, 0, 2] - D46 D54 D52 5 4 23 [0, 1, 1, 0, 2, 0, 2] - D47, D48 D55 D53 5 4 23 [0, 1, 1, 0, 1, 1, 2] - D48, D49 D55 D54 5 5 25 [0, 1, 1, 1, 1, 1, 1] - D51 - D55 5 5 25 [0, 1, 1, 1, 0, 1, 2] - D52, D53 D56 D56 5 6 27 [0, 1, 1, 1, 1, 0, 2] - D55 D57 D57 5 7 29 [0, 1, 1, 1, 1, 1, 1] - D56 -
(6, 0) (6, 0) (6, 0) (6, 0) (6, 0) ( unless it is isomorphic to one of the two graphs depicted in Fig. 9. Proof. Let G be a fullerene graph and C a non-degenerated cyclic 7-edge-cut in G. Let H be one of the components of graph G -C. If C is nanotubical, it is obvious that G is a nanotube. Let us firstly consider such cuts.

We prove that all nanotubes, which contain cyclic 7-edge-cuts, are of type (p 1 , p 2 ), where p 1 + p 2 = k, k ∈ {5, 6, 7}. Consider cases regarding k. Let k = 5 and let the cylindrical part of the nanotube have only one layer of hexagons. Then, the only edges not adjacent to pentagons are the edges between hexagonal faces. There are only five such edges, thus a cyclic 7-edge-cut could not be obtained. On the other hand, having two or more layers, the edges between layers could be used to obtain the cut of greater length. Now, let k = 6 and consider nanotubes of types (5, 1), (4, 2), (3, 3), and (6, 0) separately. The nanotubes of type (5, 1) have uniquely defined caps, which contain a hexagon, so all such nanotubes have a configuration on Fig. 10, where exists a nondegenerated cyclic 7-edge-cut.

Figure 10: The cap of a nanotube of type (5, 1) with a non-degenerate cyclic 7-edge-cut.

On the other hand, the unique caps of nanotubes of types (4, 2) and [START_REF] Došlić | Cyclical edge-connectivity of fullerene graphs and (k, 6)-cages[END_REF][START_REF] Došlić | Cyclical edge-connectivity of fullerene graphs and (k, 6)-cages[END_REF] do not contain any hexagonal faces. So there exist nanotubes of such types that do not have non-degenerate cyclic 7-edge-cut. In fact for each type only the smallest nanotube is such, while all others have it. On Fig. 11 the smallest two nanotubes of each type are presented.

Figure 11: The two smallest nanotubes of types (4, 2) (on the top), and (3, 3) (at the bottom).

It remains to consider the nanotubes of type (6, 0). There are five possible caps for this type, see Fig. 8. Only the first cap does not contain a hexagonal face, so the nanotubes with both such caps need at least two layers of hexagons to obtain a nondegenerate cyclic 7-edge-cut. In all other configurations there are at least two edges in the cap that are not adjacent to a pentagonal face (the edges of cap's hexagon), and can be elements of the cut. In case, when k = 7, simply the edges in cyclindrical part are used to obtain a cyclic 7-edge-cut. Now, let C be non-nanotubical non-degenerated 7-edge cut. Consider the cut-vector of C. If it contains any 3, the complement must contain -1, since the cut is nondegenerated. If there is a -1, it corresponds to a vertex of degree 1 in one of the components; anytime the cut vector looks like [. . . , a, -1, b, . . . ], if we remove the vertex from the component, we get a non-degenerate cyclic 6-edge cut, with the cut vector [. . . , (a -1), (b -1), . . . ], see Fig. 12 for illustration. By Theorem 3, it is contained in a nanotube, moreover, if we insert the removed vertex back, we get a non-degenerated 7-edge-cut in the nanotube. Therefore, we deal only with 0s, 1s and 2s. Then, due to the definition, we have at least two consecutive 0's or 2's. So, the type of the cut-vector is one of the following three: [2, 2, 2, 0, 0, 0], [2, 2, 0, 2, 0, 0] or [2, 2, 0, 0]. Table 2 lists all possible cut-vectors (up to symmetry) which could arise from these types. Now, we will consider each of the cut-vectors separetly and prove that any cut with such a cut-vector is either a part of a nanotube, part of the graphs depicted in Fig. 9,

→

[2, 2, 2, 0, 0, 0] [2, 2, 0, 2, 0, 0] [2, 2, 0, 0] [2, 2, 2, 1, 0, 0, 0] [2, 1, 2, 0, 2, 0, 0] [2, 2, 1, 1, 1, 0, 0], [2, 2, 1, 1, 0, 0, 1] [2, 1, 2, 2, 0, 0, 0] [2, 2, 1, 0, 2, 0, 0] [2, 1, 2, 1, 1, 0, 0], [2, 1, 2, 1, 0, 0, 1] [2, 2, 0, 1, 2, 0, 0] [2, 1, 1, 2, 1, 0, 0], [2, 1, 2, 1, 0, 1, 0] [2, 2, 0, 2, 0, 0, 1] [2, 1, 1, 1, 2, 0, 0], [2, 1, 1, 2, 0, 1, 0]
Table 2: All possible cut-vectors that arise from non-nanotubical cut types.

or a part of a configuration, which is non-realizable. Notice that the cuts are depicted with the dotted lines on figures.

[2,2,2,1,0,0,0]: Consider the configuration of Fig. 13, left. Notice that the face A cannot be pentagonal, otherwise there would be a cyclic 3-edge-cut, which is impossible [START_REF] Došlić | Cyclical edge-connectivity of fullerene graphs and (k, 6)-cages[END_REF]. Thus, it is of length 6, and we obtain a non-degenerated 5-edge-cut with a cut-vector [2, 2, 0, 0, 1]. But by Theorem 1 it follows that such a configuration is non-realizable, since the only cut-vector of non-degenerated 5-edge-cut is [

[2,1,2,2,0,0,0]: Consider the configuration of Fig. 14, left. Similarly as in the case above, we may see that face A is of length 6. We obtain a non-degenerated 5-edgecut with a cut-vector [2, 1, 0, 1, 1]. Theorem 1 implies that such a configuration is non-realizable. [2,2,1,0,2,0,0]: In this case the size of the face A from Fig. 16, left, is considered again.

A [2, 1, 2, 2, 0, 0, 0]-cut =⇒ [2, 1, 0, 1, 1]-cut
If it is of size five, the configuration is non-realizable, since a degenerated 6-edgecut with the cut-vector [2, 1, 0, 1, 0, 1] is obtained. There is no such a degenerated cut according to Theorem 2. If A is hexagonal, we obtain a cut with the cut-vector [2, 1, 0, 1, 1, 1], which is nanotubical.

A [2, 2, 1, 0, 2, 0, 0]-cut =⇒ [2, 1, 0, 1, 0, 1]-cut or (4, 2)-nanotube
: Similarly as in the two cases above the size of the face A from Fig. 17, left, is taken in consideration. For A pentagonal we once again obtain a nonrealizable configuration, due to a cut with the cut-vector [2, 0,

. For A hexagonal the nanotubical cut with the cut-vector [2, 0, [2,2,0,2,0,0,1]: Analogously, if the face A from Fig. 18, left, is pentagonal, we once again obtain a non-realizable cut-vector [2, 2, 0, 1, 0, 0]. If A is hexagonal, a nondegenerate cyclic 6-edge-cut with the cut-vector [2, 2, 0, 1, 1, 0] is obtained. By Theorem 3 it must be nanotubical. [2,2,1,1,1,0,0]: If the face A from Fig. 19, left, is pentagonal, we obtain a degenerated cyclic 6-edge-cut with a cut-vector [2, 1, 1, 0, 0, 1] which is non-realizable. If A is hexagonal, we obtain a nanotubical cut-vector [1, 2, 1, 1, 0, 1]. [2,2,1,1,0,0,1]: Consider the face A from Fig. 20, left. If A is pentagonal, we obtain a degenerated 6-edge-cut with the cut-vector [2, 2, 1, 0, 0, 0], which is non-realizable.

If A is hexagonal, we obtain a non-degenerated 6-edge-cut, which is by Theorem 3 nanotubic. (However, it can be easily checked that it is non-realizable, too, since it leads to a nanotube of type (4, 1), which does not exist [START_REF] Kardoš | Cyclic edge-cuts in fullerene graphs[END_REF].) [2,1,2,1,0,0,1]: Consider the face A from Fig. 22, left. If A is pentagonal, we obtain a degenerated 6-edge-cut with the cut-vector [2, 1, 2, 0, 0, 0], which is non-realizable.

A [2, 2, 1, 1, 0, 0, 1]-cut =⇒ [2, 2, 1, 0, 0, 0]-cut or [2, 2, 1, 0, 1, 0]-cut
If A is hexagonal, we obtain a non-degenerated 6-edge-cut with the cut vector [2, 1, 2, 0, 1, 0], which can only appear in a nanotube. [2,1,2,1,0,1,0]: Consider the face A from Fig. 24, left. If A is pentagonal, we obtain a degenerated 7-edge-cut with a component of five pentagons and some hexagons, with the cut-vector [2, 1, 2, 0, 1, 0, 0], which is non-realizable, since no degenerated 7-edge-cut in Table 1 has such cut-vector. If A is hexagonal, we obtain a nondegenerated 7-edge-cut with the cut vector [2, 1, 2, 0, 2, 0, 0], which has already been considered and leads to nanotubic cuts only. [2,1,1,1,2,0,0]: In this case we consider two sub cases again, starting with the case with A being hexagonal. In that case we obtain a 6-edge-cut with the cut-vector [1, 1, 1, 1, 1, 1] (see Fig. 25), which is nanotubical. In the latter case A is pentagonal. We obtain a degenerated 6-edge-cut with the cut-vector [0, 1, 1, 1, 1, 1]. By Theorem 2, we know that there exists precisely one configuration with such a cut. It is composed by five pentagons and one hexagon, which is by the component with 0 value in the cut. We obtain the left configuration on Fig. 26. Obviously, it is realizable and does not have to be nanotubical, so we have to consider the other part of the graph, the complement of the original cutvector -[0, If the face A is pentagonal, we obtain a 6-cut with cut-vector [0, 1, 1, 1, 1, 1], which is realizable uniquely. We get the middle graph drawn in Fig 26, which is isomorphic to the left graph of Fig. 9. There is no nanotubical cut in it, so this fullerene is not a nanotube.

A [2, 1, 1, 1, 2, 0, 0]-cut =⇒ (6, 0)-nanotube or [0, 1, 1, 1, 1, 1]-cut
If the face B is pentagonal, we again obtain a 6-cut with cut-vector [0, 1, In the latter case precisely two of the faces A, B, C and D are pentagonal. We obtain a degenerated cut with four 5-faces in the interior. The only such configuration has the cut-vector [1, 1, 0, 1, 1, 0]. Notice that between the 0 components are two 1's. That infers the pentagonal faces are A and D, since there must be exactly two hexagons between the pentagons. The configuration is again realizable. We obtain the graph depicted in Fig. 27, which is isomorphic to the right graph of Fig. 9. It is not a nanotube, since there is no nanotubical cut in it.

[2,1,1,2,0,1,0]: Consider the faces A and B on Fig. 28, left. If both of them are hexagonal, we obtain a cut with the cut-vector [1, 1, 1, 1, 1, 1], therefore it is nanotubical. If at least one of them is pentagonal, we obtain a degenerated cut with the cut-vector having three consecutive 1's. The only degenerated cut with the cut-vector having three consecutive 1's has five pentagons in the interior, so exactly one of the faces A and B is pentagonal. In that case, we can always find a cut with the cut-vector [2, 1, 1, 1, 2, 0, 0], see Fig. 28. Therefore, we deal only with configurations already mentioned above. This proves the theorem.

Figure 1 :

 1 Figure 1: An example of a nanotube of type (6, 2).

Figure 4 :

 4 Figure 4: Degenerated cyclic 6-edge-cuts.

Figure 5 :

 5 Figure 5: The operations O 1 , O 2 and O 3 .

Figure 7 :

 7 Figure 7: Degenerated cyclic 7-edge-cuts.

Figure 9 :

 9 Figure 9: The only two non-nanotubical fullerenes with a 7-edge-cut.

Figure 12 :

 12 Figure 12: If the cut-vector of a k-cut contains -1, we can change it into a (k -1)-cut.

Figure 13 :

 13 Figure 13: The component associated with the cut-vector [2, 2, 2, 1, 0, 0, 0].

Figure 14 :Figure 15 :

 1415 Figure 14: The component associated with the cut-vector [2, 1, 2, 2, 0, 0, 0].

Figure 16 :

 16 Figure 16: The component associated with the cut-vector [2, 2, 1, 0, 2, 0, 0].

Figure 17 :

 17 Figure 17: The component associated with the cut-vector [2, 2, 0, 1, 2, 0, 0].

Figure 18 :

 18 Figure 18: The component associated with the cut-vector [2, 2, 0, 2, 0, 0, 1].

Figure 19 :

 19 Figure 19: The component associated with the cut-vector [2, 2, 1, 1, 1, 0, 0].

Figure 20 :Figure 21 :

 2021 Figure 20: The component associated with the cut-vector [2, 2, 1, 1, 0, 0, 1].

[ 2 ,Figure 22 :Figure 23 :

 22223 Figure 22: The component associated with the cut-vector [2, 1, 2, 1, 0, 0, 1].

Figure 24 :

 24 Figure 24: The component associated with the cut-vector [2, 1, 2, 1, 0, 1, 0].

Figure 25 :

 25 Figure 25: The component associated with the cut-vector [2, 1, 1, 1, 2, 0, 0].

Figure 26 :

 26 Figure26: The components associated with the cut-vector [0, 1, 1, 1, 0, 2, 2]: the general situation and the cases when only A or B is pentagonal.

Figure 27 :

 27 Figure 27: The graph obtained from the cut-vector [0, 1, 1, 1, 0, 2, 2] in the case two of the faces A, B, C, D are pentagonal.

Figure 28 :

 28 Figure 28: The components associated with the cut-vector [2, 1, 1, 2, 0, 1, 0].

Table 1 :

 1 Degenerated cyclic 7-edge cuts. the types of nanotubes in which non-degenerate cyclic 7-edge-cuts exist. It is obvious that nanotubes of type (p 1 , p 2 ), where p 1 + p 2 ≥ 8, cannot contain such a cut, due to the width of the cylindrical part (of course, degenerate cyclic edge-cuts are not limited by the type).

  Theorem 4 A fullerene graph has a non-degenerated cyclic 7-edge-cut if and only if it is a nanotube of type (p 1 , p 2 ), where (a) p 1 + p 2 = 7; or (b) p 1 + p 2 = 6, and the nanotube is not the smallest nanotube of types[START_REF] Došlić | Cyclical edge-connectivity of fullerene graphs and (k, 6)-cages[END_REF][START_REF] Došlić | Cyclical edge-connectivity of fullerene graphs and (k, 6)-cages[END_REF], and (4, 2), or it is not of type (6, 0) with one layer of hexagons and with both caps isomorphic to the first configuration on Fig.8; or (c) p 1 + p 2 = 5, with at least 2 layers of hexagons;

	, 1)	(4, 2)	(3, 3)

Figure 8: The caps of (p 1 , p 2 )-nanotubes, where p 1 + p 2 = 6. Now, let us state the main theorem of this article.

  Consider the faces A, B, C and D on Fig 26, left. We distinguish cases regarding their sizes. Notice that in all cases we obtain a cut with the cut-vector, which has two consecutive components with value 1. When all four faces are hexagonal, we obtain a nanotubical 6-edge-cut with the cut-vector [1, 1, 1, 1, 1, 1]. When at least one of them is pentagonal, a degenerated cut is obtained. By the Theorem 2 and the fact that there are two consecutive 1's in the cut-vector of the cut passing the faces A, B, C, D, and the two topmost hexagons drawn in Fig 26,it follows that either one or two faces are pentagonal. When only one of the faces is pentagonal, we consider two subcases, due to the symmetry, either A is pentagonal or B is pentagonal.

	C D	A B
	[0, 1, 1, 1, 0, 2, 2]-cut	the first exception	(4, 3)-nanotube

1, 1, 1, 0, 2, 2].

Non-degenerated cyclic 7-edge-cutsIn this section, we consider the non-degenerated cyclic 7-edge-cuts. We prove that all non-degenerated cyclic 7-edge-cuts are contained in fullerene graphs which are nanotubes, with two exceptions. There exist precisely two fullerene graphs, which have non-degenerated cyclic 7-edge-cuts and that are not nanotubical. We also characterize

Acknowledgement. Supported in part by bilateral projects BI-SK/05-07-001 and SK-SI-0007-08 between Slovenia and Slovakia, by Slovak Research and Development Agency under the contract No. APVV-0007-07, by the Slovak VEGA Grant 1/3004/06, and by the Slovenian ARRS Research Grant P1-0297.


Abdel-Illah Mouaddib

Laurent Jeanpierre

Decentralized decision

  L'archive ouverte pluridisciplinaire


Distributed Value Functions for Multi-Robot Exploration

Laëtitia Matignon and Laurent Jeanpierre and Abdel-Illah Mouaddib

Abstract-This paper addresses the problem of exploring an unknown area with a team of autonomous robots using decentralized decision making techniques. The localization aspect is not considered and it is assumed the robots share their positions and have access to a map updated with all explored areas. A key problem is then the coordination of decentralized decision processes: each individual robot must choose appropriate exploration goals so that the team simultaneously explores different locations of the environment. We formalize this problem as a Decentralized Markov Decision Process (Dec-MDP) solved as a set of individual MDPs, where interactions between MDPs are considered in a distributed value function. Thus each robot computes locally a strategy that minimizes the interactions between the robots and maximises the space coverage of the team. Our technique has been implemented and evaluated in real-world and simulated experiments.

I. INTRODUCTION

The exploration consists of making decisions about where to go to gather knowledge about the environment. Exploration of unknown environments has been attracting considerable attention in autonomous mobile robotics given its wide range of applications including surveillance, searchand-rescue and planetary missions. In this context, multirobot systems are often suggested to have obvious advantages over single-robot systems : faster, robust, fault-tolerant, compensation of sensors uncertainty, ... To minimize the overall time to complete the exploration task in the context of multi-robot exploration, efficient exploration techniques should consider strategies to distribute the robots over the environment to reduce the overlap between explored areas of each robot. This is the global coordination issue defined as allocating appropriately exploration goals for the individual robots so that they simultaneously explore different zones of the area. Favouring a well balanced spatial distribution of the robots in the environment has also the advantage to minimize the other main issue in multi-robot exploration, that is the interference between the members of the team. When robots are close to each other, local coordination such as collision avoidance is necessary. This can slow down the exploration because robots may spend time in these manoeuvres.

In this paper, we are interested in multi-robot exploration strategies that maximise the coverage and reduce the overlap between explored areas of each robot to efficiently explore by minimising local interactions. The context of this work is the CAROTTE challenge 1 , where one or more robots have to map some unknown indoor area, to return within 30 minutes, to recognize and localize objects from a list of items that may

The authors are with GREYC CNRS (UMR6072) -Université de Caen Basse-Normandie, France firstname.lastname@unicaen.fr 1 http://www.defi-carotte.fr be in the exploration area, and to do some opportunistic tasks like pushing a ball which position is unknown. We have at our disposal mobile robots able to communicate each others with their positions (when possible) and to construct local maps updated with the areas explored by the others. Throughout this paper, the localization aspect is not considered and we consider that robots are homogeneous, can share their positions and have access to such local maps. Under these assumptions, our objective is a distributed multirobot exploration algorithm so that each robot constructs its exploration strategy locally by taking into account the others, their possible intended exploration target and other tasks that may be opportunistic at the same time. Additionally, strategies must be computed locally on-board by each robot with limited resources. Our approach must also be robust to temporary network errors as communication may not be permanently available during the challenge.

Decentralized Markov Decision Process (Dec-MDP) provides an expressive means of modelling decentralized decision making problems but it is very hard to solve. Our approach is based on distributed value function (DVF) techniques. It decouples the multi-agent problem into a set of individual agent problems and considers possible interactions among team as a separate layer, which currently seems one of the main tracks to tackle scalability in Dec-(PO)MDPs [START_REF] Mouaddib | Towards a formal framework for multi-objective multiagent planning[END_REF], [START_REF] Canu | Collective decision-theoretic planning for planet exploration[END_REF]. This could be seen as representing a Dec-MDP as a set of MDPs, one per robot, where interactions between MDPs are considered in the DVF. Our technique has been applied successfully in real-world scenarios during the CAROTTE challenge where our consortium was vice-champion.

This paper is organized as follows. Section II reviews the existing literature on the multi-robot exploration problem. Section III presents motivations and our approach based on DVF techniques. In section IV, the decision model of our framework is detailed. Finally, we show experiments in simulation and with real robots before concluding.

II. RELATED WORK

Several robot's exploration strategies have been proposed in the literature. If a priori information about the area to explore is available as a first coarse map, exploration goals can be a set of points of interest which must be visited to increase the map definition [START_REF] Lozenguez | Map partitioning to approximate an exploration strategy in mobile robotics[END_REF]. Otherwise, exploration goals must be found during the exploration at each time step. This technique is classically named next best view. It consists in selecting the next best exploration goal from the current set of candidates by choosing the one with the highest expected utility value; then computing and executing the policy to reach this goal; lastly acquiring new data from the environment to update its map. To define appropriate exploration goals, a widely used approach is to extract exploration frontiers from the map. Exploration frontiers are defined as regions on the boundary between open space and unexplored space [START_REF] Yamauchi | A frontier-based approach for autonomous exploration[END_REF]. Then, a utility function captures in a value the interest of an exploration goal. In [START_REF] Yamauchi | A frontier-based approach for autonomous exploration[END_REF], [START_REF] Koenig | Greedy mapping of terrain[END_REF], the utility function is the inverse of the cost of reaching an exploration frontier so the exploration strategy guides the robot to the closest unexplored area.

In the context of multiple robots exploration, each robot must be associated to its next best exploration goal. Most approaches assume that robots share the information they gathered so as to build a shared map and know their location and the relative ones of the others in this map. So as to allocate exploration frontiers to the individual robots, several exploration strategies have been proposed that mainly differ by the way global coordination is realised.

In [START_REF] Yamauchi | Frontier-based exploration using multiple robots[END_REF], all the robots have the same exploration frontiers from the shared map and each robot is assigned to its closest frontier. This method does not require any central control but there is no global coordination as multiple robots can be assigned to the same frontier. In [START_REF] Simmons | Coordination for multi-robot exploration and mapping[END_REF], [START_REF] Burgard | Coordinated multi-robot exploration[END_REF], the utility of each target is computed as a compromise between the gain expected at this target (expected area discovered when the target will be reached taking into account the possible overlap in between robot sensors) and the cost for reaching this target. Global coordination is accomplished by assigning different targets to the robots, thus maximising the coverage and reducing the overlap between explored areas of each robot. In [START_REF] Wurm | Coordinated multi-robot exploration using a segmentation of the environment[END_REF], the multi-robot exploration strategy uses a segmentation of the environment instead of a frontier-based approach to improve the space sweeping. In [START_REF] Simmons | Coordination for multi-robot exploration and mapping[END_REF], [START_REF] Burgard | Coordinated multi-robot exploration[END_REF], global coordination is centralized by a central agent that collects utilities from all the robots and assigns frontier-robot pairs, or that executes a target point selection algorithm assigning the robot-frontier pair with the best utility and recomputing the utilities given the new and all previous assignments. This process is repeated until all robots are assigned. Global coordination can also be decentralized, as in [START_REF] Zlot | Multi-robot exploration controlled by a market economy[END_REF] where robots bid on targets thus negotiating their assignments. In [START_REF] Bautin | Towards a communication free coordination for multi-robot exploration[END_REF], the utility function is for each robot-frontier pair the number of robots closer than it towards the considered frontier (in path distance). Thus, each robot is allocated to the frontier for which there is the less robots between the frontier and the robot to be assigned.

To summarize, most of previous work adopts either central agents or negotiation protocols with complicated process. Besides existing work in multi-robot applications does not address the local coordination issue as if a strategy that distributes well the robots over the environment would avoid all local interactions. In our CAROTTE challenge context, all the robots must start and return in a specified zone where close interactions will take place and then local coordination is necessary. Another limitation of these works, except for [START_REF] Burgard | Coordinated multi-robot exploration[END_REF], is they do not address limited communication issues.

III. DISTRIBUTED VALUE FUNCTIONS

Multi-robot coordination can be formalized decentralized decision making, i.e. each individual robot must find its policy so that all robots simultaneously explore different areas of the environment. In this section, we first motivate the choice of the Dec-MDP framework. Then background is summed up and our distributed value function method is presented.

A. Motivations

In single robot exploration, the exploration model is fully subsumed by the Partially Observable MDP (POMDP) framework. However, exploring using POMDPs meets the curse of dimensionality and limits its application to exploration domains because it considers uncertainty on observations, on outcomes of actions and on its own state. In our work, the localization aspect is not treated. We assume that the location of the robot is known at decision time. Therefore, we can simplify the POMDP model to an MDP as the explored environment is perfectly known and the robot has a known position, like we did in previous work on singlerobot exploration [START_REF] Gloannec | Unknown area exploration with an autonomous robot using markov decision processes[END_REF]. Besides, MDP framework has many advantages: it allows for several goals at the same time and it accounts for uncertainty in the result of actions. MDPs can also be solved very efficiently through dynamic programming [START_REF] Bellman | Dynamic programming: Markov decision process[END_REF]. Finally, compared with most of published exploration algorithms using a two-steps planner [START_REF] Yamauchi | A frontier-based approach for autonomous exploration[END_REF], [START_REF] Simmons | Coordination for multi-robot exploration and mapping[END_REF], [START_REF] Stachniss | Exploring unknown environments with mobile robots using coverage maps[END_REF], MDP planner is able to plan for its path at the same time as it chooses a location to explore or an opportunity task to do.

To consider the multi-agent issue, MDPs have been extended to Decentralized MDPs (Dec-MDPs). Dec-MDPs is an expressive framework for cooperative teams of decision makers but computing a solution to Dec-MDPs has a high complexity [START_REF] Bernstein | The complexity of decentralized control of markov decision processes[END_REF]. This typically limits the scalability in terms of number of agents and of the size of the area to explore. However, new coordination mechanisms for several robots have been developed recently that take advantage of local interactions and coordination to solve Dec-(PO)MDPs [START_REF] Nair | Networked distributed pomdps: A synthesis of distributed constraint optimization and pomdps[END_REF], [START_REF] Mouaddib | Towards a formal framework for multi-objective multiagent planning[END_REF], [START_REF] Canu | Collective decision-theoretic planning for planet exploration[END_REF]. These methods represent a Dec-(PO)MDP as a set of interactive individual decision making problems and thus reduce its complexity. These interaction-based models for solving Dec-(PO)MDPs are based on the idea that an agent interacts only sometimes with some others. Thus the Dynamic Local Interaction Model (DyLIM) [START_REF] Canu | Collective decision-theoretic planning for planet exploration[END_REF] splits the Dec-POMDP into two parts: the individual one "ignoring" the others and the coordination aspect describing how the agent influences the ones which it is in interaction with. These approaches are very interesting as they can compute solutions for larger problems while keeping the Dec-(PO)MDP formalism.

To address the multi-robot exploration problem, we use the Dec-MDP formalism solved as a set of individual MDPs, one per robot. To consider the interactions, we define a distributed value function computed locally by each robot that minimizes the interactions while maximizing the exploration. We will show that our model overcomes the limits of others since it can deal with a large number of robots; it handles both the local and global coordinations; it is robust to communication failure.

B. Background on Markov Decision Processes

Dec-MDP [START_REF] Bernstein | The complexity of decentralized control of markov decision processes[END_REF] is an extension of MDP for decentralized control domains. A Dec-MDP is defined with a tuple < I, S, A, T, R, Ω, O > and we have:

• I the number of robots, S the set of joint states and A the set of joint actions2 ;

• T : S × A × S → [0, 1] a transition function; T (s, a, s ′ )
is the probability for the I robots of transitioning from state s to s ′ after doing joint action a; • R : S × A → ℜ a reward function mapping S × A to a real number that represents the robots' immediate reward for making joint action a while being in state s;

• Ω a set of observations and O an observation function can be left out if the states of agents are fully observable locally.

The goal of planning is to find a sequence of joint actions maximizing the long-term expected reward. Such a plan is called a policy π that is a mapping from S to A. An optimal policy π * specifies for each state s the optimal joint action to execute at the current step assuming the agents will also act optimally at future time steps. The value of an optimal policy is defined by the optimal value function V * that satisfies the Bellman optimality equation:

V * (s) = max a∈A (R(s, a) + γ s ′ ∈S T (s, a, s ′ )V * (s ′ )) (1)
where γ is the discount factor. We can see an MDP [START_REF] Puterman | Markov decision processes[END_REF] as a Dec-MDP where I = 1.

C. Distributed Value Functions for Multi-Robot Exploration

In our approach, we considered homogeneous robots, each of them having the same set of states and actions, and we solve the Dec-MDP as a set of individual MDPs: each robot constructs its exploration strategy locally while considering the others. A robot has access to a map updated with all explored areas and to the positions of the others. With these information, the robot can consider which areas could be explored by the other robots and thus reducing its interest in these areas. Formally, each robot computes its value function as the standard Bellman equation (eq. 1) augmented with this information.

Distributed value function (DVF) has been introduced in [START_REF] Schneider | Distributed value functions[END_REF] as a way to distribute reinforcement learning knowledge through different agents. In [START_REF] Babvey | Multi mobile robot navigation using distributed value function reinforcement learning[END_REF], the distributed approach enables robots to learn multiple behaviours concurrently in a mobile robots navigation approach. Assuming that agent i knows at each step the state s j ∈ S of each other agent j, this leads to the following DVF applied to the exploration issue and from the viewpoint of agent i:

∀s i ∈ S V i (s i ) = R explo (s i ) + γ max ai∈A s ′ ∈S T (s i , a i , s ′ )   V i (s ′ ) - j =i f ij P r (s ′ |s j )V j (s ′ )   (2)
This specifies that the expected gain of the robot i being in state s i and going to s ′ is reduced by what the other robots can expect to gain by visiting the same state s ′ . The expected gain of another robot j is valued with the exploration expected gain at s ′ , noted V j (s ′ ), weighted by the probability that robot j explores state s ′ from its current state s j , noted P r (s ′ |s j ). Thus if a robot j has a high expected value for a state and if the probability for this robot to attain this state from its current one is great, then this robot may intend to go and explore the surroundings of this state. DVF tries to choose the action with a high expected gain for i so the one for which the interest of the others may be low.

In other words, by locally computing DVFs et following resulting policies, the robots choose actions that minimize the interactions and that move the robots away from each other.

We now detail the different parts to calculate DVF. It requires to compute first data structures < S, A, T, R explo > of the model ( §IV). The exploration reward function R explo is computed with the reward propagation mechanism ( § IV-B.2). Then, the exploration expected gain of each other robots V j is estimated. Given our communication restrictions, the robots cannot exchange information about their value functions. However each robot i can compute V j by empathy. Additionally, since the robots we considered are homogeneous, this function is the same for each robot so this must be computed only once. This empathic value function is computed for each state s ∈ S with the standard value iteration algorithm and the exploration reward function R explo . To evaluate the probability P r (s ′ |s j ), an M DP j for each other robot j is used. M DP j has classical S, A, T structures of the model. But its reward function R j is calculated for each M DP j with rewards r j located at the current position s j of robot j. Using standard value iteration, the resulting value function V can be consistent with probability values: V (s) = P r (s|s j ). f ij is a weighting factor that determines how strongly the expected gain of agent j reduces the one of agent i. It allows for balancing the value function with respect to the rewards, and is chosen as maxR/maxV j .

Thus each robot computes strategies with DVF so as to minimize interactions. However it does not handle situations when the robots are close to each other that can happen for instance in the starting zone or in some narrow corridor. These situations with close interactions can be easily detected by computing the distance between the robots and its partners but require local coordination. Local coordination can be solved with a Multi-agent MDP (MMDP) [START_REF] Boutilier | Planning, learning and coordination in multiagent decision processes[END_REF] as the robots concerned by the interaction are close to each other. So joint policies are computed off-line for these specific joint states and followed when local coordination is detected.

IV. DESCRIPTION OF OUR MDP FRAMEWORK

The decision framework of our multi-robot exploration process is based on a set of MDPs, one per robot. Fig. 1 shows the global software architecture of our decision framework from the viewpoint of one robot. It is composed of a four layers grid from which are derived the data structures of one MDP model. A decision step consists in building the model, computing the policy from the distributed value function, and producing a smoothed trajectory. Classically, the planner stops after this and waits for the robot to arrive at the chosen location before starting again. Instead, we decide to allow the robot to plan continuously, updating its model and policy as it perceives changes in its environment. Indeed, continuous planning allows us to update quickly action plan if a target of opportunity is discovered or if the environment is dynamic. It also considers that information is gained en route: map is often explored before the robot reached its target. Another advantage is to react as soon as possible to the decisions of the others. However, this requires the decision step to be quick enough for online use. Given that the model will be updated at each decision step, we use the greedy approach that plans only for the immediate action. Following is the motivated description of the components of our architecture.

A. Four Layers Occupancy Grid

The first layer is the real world layer where the robots move. The second one is the pixels layer where raw sensor data are projected on the occupancy grid [START_REF] Elfes | Using occupancy grids for mobile robot perception and navigation[END_REF] using Bresenham's algorithm based on the current robot position and angle [START_REF] Gloannec | Unknown area exploration with an autonomous robot using markov decision processes[END_REF]. The occupancy grid represents the environment as a regular grid laid over the environment where each cell is initialized as unknown and updated as free (no obstacle) or occupied (something there) by the data acquisition process. The two last layers are computed from the occupancy grid and used to generate the data structures of the model.

States and rewards are based on the hexagonal grid. This grid clarifies the pixel layer by merging nearby data. Each hexagon is composed of a set of cells and is considered as unknown, free or occupied according to the value of its cells. This grid has nice geometrical properties: it allows for 6 neighbours with the same distance from any cells that simplifies the reward propagation algorithm ( § IV-B.2) and increases the movement capabilities of the robot as compared to a square grid. For the actions and transitions, a Voronoi diagram [START_REF] Aurenhammer | Voronoi diagrams -a survey of a fundamental geometric data structure[END_REF] is generated.

B. MDP Model 1) State Space:

The state space contains all possible locations of the robot and its orientation in the hexagonal grid (one location is an hexagon and it allows 6 orientations per location). An oriented location is referred as a pose in this paper. For a given exploration time, states are based on the current state of the hexagonal grid, including all the free hexagons.

2) The Reward Function: Since the objective is to explore unknown parts of the environment, the main reward component is based on the expected information gain in each pose. Various approaches for setting these rewards have been published [START_REF] Yamauchi | A frontier-based approach for autonomous exploration[END_REF], [START_REF] Simmons | Coordination for multi-robot exploration and mapping[END_REF]. Similarly to [START_REF] Stachniss | Exploring unknown environments with mobile robots using coverage maps[END_REF], we compute a reward value for each hexagon. However, instead of characterizing the entropy of the cell itself, we estimate the information the robot would gain if it was at this location with some heading. To compute this value, we simply propagate rewards in some radius around frontier hexagons, respecting line-ofsight constraints [START_REF] Gloannec | Unknown area exploration with an autonomous robot using markov decision processes[END_REF]. Our actual system currently uses a grid with 15 centimetres hexagons, and propagates frontier rewards up to 2 meters. Targets of opportunity are simply added to the reward function as they happen, so that they are shared as well as exploration tasks.

3) Action Space: The robot actions model the movement of the robot: go forward, turn left or right, and wait.

However, using only these actions and the hexagonal grid implies some troubles in cluttered space like a narrow corridor not oriented along one of the 6 hexagonal directions. In such a case the robot will have to zig-zag since it only goes from one hexagon to another. And if the corridor is narrow enough, this may prevent any traversal. To overcome this situation, another robot action is added: follow the Voronoi edge to next hexagon. Please note that the Voronoi diagram is not sufficient for planning the whole trajectory as many tasks have to be done far from the Voronoi edges (starting positions, ball-to-push position). Additionally, trajectories following the Voronoi diagram frequently are suboptimal. Besides synchronizing several robots is easier when actions take the same amount of time: in a Voronoi diagram, some node can be connected to very close neighbours and to very distant ones at the same time.

4) The Transition Function:

The transition function describes the expected outcomes of any action in any state. If the intended movement is allowed by the local safety clearance computed by the Voronoi diagram, the expected state will be reached with high probability. Otherwise, the state is not modified and a high penalty is added to the reward function for this state and this action. Allowed movements are not always deterministic because tight clearance may slow the robot down, or even make the expected move fail.

C. Smoothing the Trajectory

The hexagonal optimal trajectory is smoothed, aggregating series of actions into way-points that do not violate safety clearances computed by the Voronoi Diagram.

D. End of Exploration

End of exploration is detected simply by testing the expected value of the current best action for each robot. When it reaches zero, no more reward can be gained and we add a return reward to make the robot exit the area through its entry point.

V. EXPERIMENTAL PLATFORMS

Experimental results shown in this paper are from two main sources: experiments with two real robots and computer simulations with Player/Stage simulator.

A. Real Robots

The robot we use for exploration is a Wifibot3 µ-trooper M. This 6-wheels mobile robot embeds an Intel Core 2 Duo processor, 2GB RAM and 4GB flash. It is also equipped with an Hokuyo URG-30LX 4 Laser range scanner. The software running on-board this robot is based on a Data Distribution System (DDS) implementation from OpenSplice 5 . This middle-ware allows for several programs to run concurrently, even on different computers. In our architecture, that implies that various modules can run asynchronously: Laser acquisition, SLAM, Decision, Mobility and Object recognition.

The architecture allows the robots to exchange their laser scans and their poses. Thus each robot knows the areas explored by the others and updates its local map with local and distant scans. In particular, the SLAM module receives laser readings and provides the other modules and other robot with the robot pose (location and heading). It is based on [START_REF] Xie | A realtime robust slam for large-scale outdoor environments[END_REF]. The mobility module implements an advanced point and shoot algorithm, along with a backtrack feature that prevents the robot from being stuck, reverting back on its own trajectory. The point and shoot algorithm consists of turning to the desired heading and then going forward the specified distance. Here, the algorithm accepts a small initial angular error, and keeps correcting the heading drift as the robot goes forward. The decision module runs asynchronously, computing a new policy every second in average.

B. Simulated Robots

We use the Player/Stage6 [START_REF] Gerkey | The player/stage project: Tools for multi-robot and distributed sensor systems[END_REF] simulator with an architecture that mimics the real robots. DDS is replaced by an IPC (Inter Process Communication) shared memory segment. Laser acquisition is simulated by a "laser" virtual sensor tuned with the URG-30 properties. A "position" virtual device simulates both the SLAM module by providing odometric data and the mobility module by executing the point and shoot algorithm. Finally the decision module used on real robots can be used with the simulator without modification. We varied the number of robots from one to five and used two different simulated environments from Player/Stage (Fig. 2). Robots are initially in a line formation in the starting zone and to reduce the situations of local coordination at the beginning, each robot starts with 15 seconds of delay from its precedent. We plot how the coverage of the environment to explore evolves over time, while varying the number of robots. Fig. 3 and4 report the time it takes to cover 50, 70, 90, 95 and 100% of the environment. The EndM coverage corresponds to the end of the mission, i.e. when all the robots have returned to their starting poses after they detected the end of exploration.

VI. EXPERIMENTAL RESULTS

A. Simulated Robots

It is of interest to notice two stages in the coverage evolution: the beginning stage until 95% and the end stage consisting of 100% and the end of the mission. During the beginning stage, robots spread out to different areas and covered the space efficiently, as illustrated by paths followed by 2 and 3 robots in Fig. 5. However, there is a number of robots beyond which there is not much gain in the coverage and that depends on the structure of the environment [START_REF] Simmons | Coordination for multi-robot exploration and mapping[END_REF]. For instance in the autolab environment (Fig. 3), even if two robots perform significantly better than one robot, there is not much gain in having three or four robots. Indeed, two robots can share separate zones (Fig. 5b) but the gain of having more robots is low compared to the overlap in trajectories and the risk of local interactions ((Fig. 5c andd). In the hospital environment (Fig. 4), four robots seems to be the optimal Besides, beyond this number of robots, the end stage takes longer as robots end up interfering with one another to cover few last spots or to return to start. Thus during the end stage, local coordination cannot be avoided and the more robots are used, the longer the end stage may take as local interactions require bypasses, backtracks and stops to let pass.

B. Real Robots

We also performed experiments with our two µ-troopers. The video accompanying this paper 7 shows the exploration of the robots and some situations of local coordination successfully resolved. Resulting map of the area obtained at the end of the mission is in Fig 6.

VII. CONCLUSIONS AND FUTURE WORKS

In this paper, we address the problem of multi-robot exploration with a fully decentralized approach based on distributed value functions. Our approach considers a Decentralized MDP as a set of individual MDPs where interactions between MDPs are considered in the distributed value function. Thus each robot computes locally a strategy that minimizes the interactions between the robots and maximises the coverage of the team. Local coordination is also considered so as to resolve situations with close interactions. Experimental results show that this method is able to effectively coordinate a team of robots during exploration.

One interesting research direction and a planned restriction of the challenge is to consider communication loss constraints during the exploration. Our decentralized approach does not rely on perfect communication, but at reduced efficiency. In case the robots do not know at each time step their relative poses, our DVF approach can still consider the intentions of others from their last known poses. If in addition local maps are not updated, each robot will explore all targets. We want to investigate temporary network errors in more detail and to test our DVF approach extended to situations where communication between robots drops out, as introduced in our previous work [START_REF] Matignon | Distributed value functions for multi-robot exploration: a position paper[END_REF]. Besides, our system currently takes "randomly" pictures for the object recognition, i.e. it takes pictures at a specified rate along the trajectory planned for the exploration. Another perspective is to plan to perceive. Indeed robots can act to improve object detections at the same time they explore. We would like our robots to modify their strategies to both maximise the exploration and minimize false detections.

Fig. 1 .

 1 Fig. 1. The global software architecture of our decision framework for one robot.

Fig. 2 .

 2 Fig. 2. Simulation environments from Player/Stage with starting poses.

Fig. 3 .

 3 Fig. 3. Results from autolab environment (averaged over 5 simulations).

Fig. 4 .

 4 Fig. 4. Results from hospital environment (averaged over 5 simulations).

Fig. 5 .

 5 Fig. 5. Paths taken by the robots in the autolab environment.

Fig. 6 .

 6 Fig. 6. Resulting pixel map of the area explored. Pixels colour ranges from black (obstacle) to white (free). Gray shades represent the uncertainty.

A state of the problem can be written with a tuple s = (s 1 , ..., s I ) such that s j is the state of robot j. A i defines the set of actions a i of robot i.

www.wifibot.com

www.hokuyo-aut.jp

http://www.opensplice.com

http://playerstage.sourceforge.net/

Also available at http://lmatigno.perso.info.unicaen.fr/research

VIII. ACKNOWLEDGEMENTS

This work has been supported by the CAROTTE (Cartography by a robot of a territory) project that is a French national challenge funded by the NRA (French National Research Agency) and the DGA (Defense Procurement Agency) (ANR-09-CORD-103). The authors are members of the Robots Malins consortium which takes part in this challenge and would like to thank all their partners: GREYC, University of Caen Basse-Normandie; THALES Optronique S.A; INRIA Sophia, evolution team.


Mohamad El

Maroua Bouzid

Abdel-Illah Mouaddib

DEC-A*: a decentralized extension of A*

A* is the algorithm of finding the shortest path between two nodes in a graph. When the planning problem is constituted of a set of linked graphs, A* searches solution like if it is face of one graph formed by linked graphs. While researchers have developed solutions to reduce the execution time of A* in multiple cases by multiples techniques, we develop a new algorithm: DEC-A* which is a decentralized version of A*. A* uses a distance-plus-cost heuristic function to determine the order in which the search visits nodes in the tree. Our algorithm DEC-A* extends the evaluation of the distance-plus-cost heuristic be the sum of two functions : local distance, which evaluates the cost to reach the nearest neighbor node s to the goal, and global distance which evaluates the cost from s to the goal through other graphs. DEC-A* accelerates finding the shortest path by reducing the time and space complexity, while ensuring the privacy of graphs.

INTRODUCTION

Many problems of engineering and scientific importance can be related to the general problem of finding a shortest path through a graph. Examples of such problems include routing of telephone traffic, navigation through a maze, computer games, travel planning, etc. These kinds of problem can be represented by a graph constituted of a set of nodes and a set of edges. Nodes represents the different states of the domain (i.e. cities in the transportation problem) and edges represents the actions that can be executed to change the states (i.e. take a plane).

Let us take the travel example. Suppose that we have three cities: Montpellier, Lyon and Paris. Montpellier and Lyon are linked by a train; Lyon and Paris are linked by an airplane. In each city, we have a set of places linked by buses and metros. Suppose that a person wants to travel between Paris and Montpellier downtowns. This problem can be defined by a graph where nodes are the places in the cities and edges are the actions performed by buses, metros, airplane or train. In this case, A* algorithm can be used to search the shortest path. A* must be executed on one machine and cannot take advantage of the decentralized nature of the prob-lem. In additional it supposes that there is no privacy information and the graph of each city is observable from other cities.

In many cases, the systems for which we plan are naturally viewed as Multiagent (MA) systems. For example, the travel company is composed of multiple agents that perform the travel planning: the trains/airplanes that travel the passengers between airports/railway stations, and the local buses/metros that transport within a certain locality. One may pose the following question: "Can a decentralized planner, planning for such a system exploit its MA structure in order to improve its worst case time-complexity and preserves graphs privacy ? ". We think that answer is positive and this is what we will try to show you in this paper by our new DEC-A* algorithm.

The travel problem cited above can be modeled and solved in a decentralized manner. Instead of defining one graph that contains all places and links of cities and between them, an individual graph will be associated to each city. A set of links will be then defined between the set of graphs.

Our new algorithm DEC-A* extends the distance-pluscost heuristic function (f (s) = g(s) + h(s))to determine the order in which the search visits nodes in the tree. It determines also the order of triggering A* in the neighbors graphs.

The extended function f (s) which estimates the cost of the shortest path through s will be defined by the sum of three functions :

• g(s) which is the path-cost from the initial state to s.

• h local (s) which is the evaluation of the cost to reach the neighbor state1 s neighbor located on the (estimated) shortest path to the goal. • h global (s) which is equal to the estimation of the shortest path-cost to reach the goal from s neighbor .

The paper is structured as follows. The next secvtion defines the prelimianires of the decentralized architecture. The basic idea is illustrated in section 3. Section 4 illustrates a motivating example of our algorithm. The decentralized algorithm is developed in section 5. Section 6 studies the properties of the algorithm. The comparaision with the related works is presented in section ??. The paper is concluded in section 8 by summarizing the contribution of the paper and presents suggestions for future work.

prelimianires

The planning domain D is defined by a set of graphs < G 1 , ..., G n > and a set of links between graphs < l ij , ..., l kl >. Each graph G i is defined by a finite set of states S i and a finite set of actions Actions i that can be executed in a state s ∈ S i . c i (s, a) denotes the action cost of executing action a ∈ Actions i in state s ∈ S i , and succ i (s, a) denotes the resulting successor state. Each link l ij = s i → s j has two states s i , s j included in distinct graphs G i , G j ; i = j. c(lij) denotes the link cost, neighbor(G i ) denotes all the graphs linked with G i and S i neighbor denotes the set of neighbor states of the graph G i .

The planning problem is defined by init which denotes the start state, and goal which denotes the end states. init, goal ∈ {S 1 ∪ ... ∪ S n }.

In a graph G i , we refer to an action sequence as local path π i . In the domain D, the solution of the planning problem is a global path Π defined by a sequence of local path < π 1 , π 2 , ..., π n > linked by links < l 1,2 , ..., l n-1,n >.

BASIC IDEA

A planning agent A i is associated to each graph G i . A central agent A c plays the role of an interface between users and agents. A init (resp. A goal ) denotes the agent containing the initial (goal) state.

When a planning problem is submitted, each agent A i computes its global heuristic which estimates the cost of its shortest path to the goal through its neighbor agents.

Then, the agent A init containing init develops A* locally by minimizing f (s) described above until reaching s goal (if s goal ∈ G init ) or all neighbor states s neighbor of S neighbor are reached.

Each reached neighbor state s i activates at the other side a new A* execution on s j as new intial state and g(s j ) is initialized by the cost to reach it from init.

The last step cited above is repeated until reaching s goal .

MOTIVATING EXAMPLE

We use a path-planning problem on a connected grid-world of square cells (such as, for example, grid-world used in video games) as examples (Figure 1). All cells are either blocked (=black) or unblocked (=white). Our domain example is defined by sixteen grids delimited by horizontal and vertical red dashed-lines. Each grid G ij associated to an agent A ij is defined by 9 cells (a, b, c, d, e, f, g, h, i). The agent know its current cell, the goal cell, and which cells are blocked.

The agent can change its current cell to one of the four neighboring cells by executing one of the four possible actions ↑→↓←. Depending on its position and the number of blocked cells, each agent has maximum 12 links to move from one grid to another (a, b, g, i for the agent A 3,2 ). When the agent crosses a red line, it means that it executes a link action. The action cost for moving from an unblocked cell

DECENTRALISED ALGORITHM

In this section, we give two decentralized strategies of DEC-A*. The fist one is based on the global and local heurisitcs as explained in the introduction. The basic idea behind the second strategy is to reduce the time execution of DEC-A*, by computing off-line the lowest cost path between each couple of neighbor states of each agent.

First strategy Global distributed heuristic

The global distributed heuristic h g is computed per agent

A i . Let Π =< π 1 , l 1,2 , π 2 , ..., l n-1,n , π n > the shortest path from init to goal. Then, h g estimates the cost of the sub- plan < π i , l i,i+1 , ..., l n-1,n , π n >.
Algorithm 1 explains the general steps to compute the global heuristic. Firstly, each agent computes the cost of crossing it to reach the goal (i.e. cost(π i ) line 2)2 by calling Algorithm 2. Then, all the global heuristic are initialized by +∞ (3-5) and the Algorithm 3 is called (7) to compute the global heuristic h g of each agent (it starts recursively from A goal ).

Algorithm 2 computes firstly the distance between each neighbor state (4) and the init (5) (resp. goal (6)) state. Then, it selects its nearest neighbor state to init (8) and its nearest neighbor state to goal (9). Finally, the cost of crossing A i to reach the goal from init is estimated by the distance between this couple of states (10).

Algorithm 3 is a recursive procedure which diffuses the global heuristic from A goal to A init through other agents.

That's why Algorithm 3 is executed for the first time on (A goal ) in Algorithm 1. Each agent computes its global heuristic by minimizing the cost estimation to reach the goal by crossing it (3). The estimated cost of A to reach the goal through a neighbor agent (A i ) is equal to its last global heuristic h g (A i ), plus the cost of crossing it cost(A). If h g (A) is updated (4) then the neighbor agents will checks their g h to see if they can minimize it. Recursive procedure will turned until no heuristic value can be minimized.

Algorithm 1: Global heursitic computation HeuristicGlobal(A 1 , .., A n ) 1 V ector Cost < Agent >= costAgents {A 1 , .., A n } 2 for i = 1..n do 3 h g (A i ) = +∞ 4 end 5 h g (A goal ) = Cost(A goal ) 6 heuristicAgent(A goal ) 7 Algorithm 2: Cost of crossing agent costAgents(A 1 , .., A n ) 1 for i = 1..n do 2 d init = d goal = V ector(n) 3 foreach s min ∈ S min do 4 d init [s min ] = distance(s min , init) 5 d goal [s min ] = distance(s min , goal) 6 end 7 s min init = arg min si (d init (s i )/s i ∈ S min (A i )) 8 s min goal = arg min si (d goal (s i )/s i ∈ S min (A i )) 9 cost(A i ) = distance(s min init , s min goal ) 10 end 11 Algorithm 3: Recursive agent heurisitc procedure HeuristicAgent(A) 1 h = h g (A) 2 h g (A) = arg min Ai h g (A i ) + cost(A)/A i ∈ 3 neighbor(A) if h = h g (A) then foreach A j ∈ neighbor(A) do 4 HeuristicAgent(A j ) 5 end 6
Example The Figures 2 and3 illustrates the steps of computing the global decentralized heuristic for the problem illustrated in Figure 1. Firstly, the first line of algorithm 1 is executed. It calls Algorithm 2 to compute the cost of crossing each agent. Let us take the agent A 2 3 . It has four neighbor states : a, b, g and i. States a and b are linked to 2 2 , g to A 2 4 and i to A 3 3 . The distance from each neighbor to the init is placed in the top left and to the goal on the bottom right. The distance from node a to init is 5 and from node a to goal is 9.

State a is the nearest neighbor state to init and nodes g and i are the nearest states to goal (surrounded by a circle). A 2 3 has the choice between distance(a, g) = 2 and distance(a, i) = 4. It minimizes its cost and choice the value 2 placed in the rectangle A 2 3 , and so on for the other agents.

The agents costs are copied in the top left of Figure 3. Each square designs an agent. In the top right, the global heuristic of each agent is initialized by +∞ (lines 3-5 in Algorithm 1) and the goal agent A 3 4 initializes its global heuristic with its cost equal to 0 (line 6). The global heuristic h g of each agent is placed in the top right of the agent square.

A 3 4 diffuses its global heuristic to its neighbors A 3 3 , A 2 4 , A 4 4 (Algorithm 3). For example, h g (A 3 3 ) = min(∞, 2 + 0) = 2 (line 3); Then each agent having updated g h diffuses it to its neighbors (line 4-6). For example,

A 3 3 diffuses its g h to A 3 4 , A 2 3 , A 4 3 , A 3 2 . A 3
4 minimizes its g h by minimizing its old g h and the g h of reaching it from its neighbors A 2 4 with g h =4, A 3 3 with g h =2 and A 4 4 with g h =0 added to its cost (0) (min(0, 4+0, 2+0, 0+0, 0) = 0).

Agents coordination

In this section, we explain how agents proceed and coordinate to reach s goal .

Minimizing the cost to reach goal The basic idea behind the local heuristic h l is to help agent A i to leave its graph via the neighbor agent having the minimal cost to reach the goal.

To do this, the agent executes A* on its own graph from its initial state by using the function f (s) which estimates the cost of the cheapest solution through s.

Let s i to be the neighbor state linked by l ij to A j via s j where A j is the agent having the minimal global heuristic, then f (s) is defined by f (s) = h l (s) + c(l ij ) + h g (s) where :

• h l (s) = distance(s, s i ), • c(l ij ) the cost of l ij ,
• h g (s j ) the global heuristic of A j .

When the agent A reaches a neighbor state s i , it continues developing its graph to leave it by the second nearest neighbor state s 2 and so on until leaving all its neighbor states.

To do this, it does not re-executes A* from scratch but it uses the tree developed by A* to reach s i by updating the local and global heuristics (h l and h g ) values of developed states with respect to state s 2 . A continues executing its A* until reaching all the neighbor states.

Coordination between agents at the neighbor states level When an agent A i reaches a neighbor state s i linked to another neighbor state s j ∈ A j , it activates a new A* execution on A j . A j sets s j as its initial state and sets its path cost to:

g(s j ) = g(s i ) + c(l ij ).
Let T j to be the tree-search of A j . A j might be reached by another neighbor state s k . This means that our agent will have more than one initial (neighbor activation) state (s j and s k ). In this situation, two cases can be distinguished:

• s k / ∈ T j , in this case the agent adds s k to T j even if it does not have any link with the other nodes. Then, A* continues its execution on the set of node by minimizing function f (s) as above (section 5), until reaching all its neighbor states. Let T k the sub-tree-search of the treesearch of A j developed from s k . During states expansion, one tree-search, let us say T j , may create a state s including in the second , i.e. T k . Let g j (s) (resp. g k (s)) the path-cost of reaching s in T j (resp. T k ). If g j (s) ≥ g k (s) then the link that creates s in T j is pruned from its entering link in T j and linked to s in T k (vice-versa). By doing that, a new sub-tree-search is added to T k (state s and its child states). Finally, the pathcost of all s childs are updated. Example: Figure 4 illustrates such example (path-code is the left operand). Let us suppose that initially, the agent develops its tree from c, then develops node b (on the right of Figure 4). Suppose now that the agent is activated via node a which creates nodes b and d (On the left of Figure 4). We can see that node b is created by the two sub-tree. Since 6 = g right (b) > g lef t (b) = 4, then Then, b is pruned from the right tree and linked to the left one, and the path-costs are updated.

• s k ∈ T j , then g(s k ) = min(g j (s k ), g k (s k )).
When the cost-path of a state is changed, the costs of its child in the tree-search are updated (intra and inter agent).

All agents progress in parallel and coordinates until reaching the goal state s goal and having a first approximate solution Π i . Let g(π i ) its cost.

Then the goal agent diffuses this cost to all agents. Each one stops developing its states s having f (s) > g(Π 1 ). We call active agent an agent having at least a non-developed state.

When the goal state is reached by a new plan Π i+1 having a cost g(Π i+1 ) < g(Π i ), then g(Π i+1 ) is diffused to all active agents until reaching a step where no active agent exists. Then the optimal agent can be easily extracted. For readability reason, we will not give the complete execution, but multiple situations explaining the algorithm.

The agent A 2,1 triggers its A*. Between its neighbor agents, A 3,1 has the minimal global heuristic (6). Since A 2,1 is linked to A 3,1 with g, A 1 2 develops its graph as illustrated in the Figure 5 until reaching g.

By the same way, A* is triggered sequently by agents A 1 3 , A 2 3 , A 3 3 , and A 3 4 until reaching the goal states h with 17 as cost. This cost is diffused to all agents.

At the same time:

• A 2
3 revaluates f (s) for all its developed nodes to reach the second nearest state to goal, i. So A* is re-executed by A 2 3 from state a until reaching i and A 3 4 do the same to reach the goal. Since the cost of the new plan solution is 15, it is diffused and the new plan replace the first one.

• A* is triggered on A 1 1 from state g to reach i. Then from i, A 2 1 triggers A* on g. During A* execution, A 2 1 will reach state g and receive the new lowest cost-path founded, (15). Since, f (d) = 16 > 15, A 2 1 stops developing d.

Second strategy Offline local path cost

In this section, we develop another strategy to be used by DEC-A*. Its basic idea is to compute off-line the minimal cost path between each couple of neighbor states of each agent. This strategy is illustrated in Algorithm 4 and Algorithm 5. DEC-A* is initialized on the init and the goal states.

Fist of all, Algorithm 4 initializes by +∞ the g init (s n ) and g goal (s n ) for each agent. g init (s n ) and g goal (s n ) are the costs to reach each neighbor state s n from init and goal respectively.

Then, the initial (resp. goal) agent computes the optimal path from the initial (goal) state to each neighbor state lines 3-4 in Algorithm 4.

From each neighbor state in A init and A goal , the costs are diffused to the neighbor agents via links between their neighbor states (Algorithm 5).

Algorithm 5 explains how diffusing the costs from init to goal. The same algorithm is used to diffuse the costs from goal to init by replacing init with goal.

Since costs g init , g goal are diffused in parallel, it may intersect in a state s. This mean from s, we can construct a plan g Π constituted of two sub-path. The first one is constituted from init to s and the second from s to goal.

Let S neighbor to be the set of neighbor states of agent A and g min Π to be the minimum cost founded by the agents {A 1 , ..., A n } at instant t.

During diffusion, the costs are minimized for each s n (2-3) . If a state is reached from init and goal, then the diffusion by this neighbor states is stopped. If g min Π can be reminimized (6-9) then its new value is diffused to all agents.

In lines (11-14), the agent continues diffusing its g init via all its neighbor agents if it does not exceed g min Π . Otherwise, s n cannot reduce the optimal solution and it is deleted from S neighbor (16). In line 17, the agent is deactivated which mean that it cannot contribute to improve the solution if its S neighbor becomes empty.

When all the agents become inactivated (line 6 in Algorithm 4, the goal agent which stoks the best plan (line 9 in Algorithm 5) extracts the optimal path. This strategy supposes that the planning domain is static to be efficacy. It can be extended to find the optimal plan between a state in a set of initial state to one state in a set of goal state.

Algorithm 4: DEC-A* : second strategy DEC -A*(init, goal)

1 initialiseAgents() 2 dif f use init (A init , init) 3 dif f use goal (A goal , goal) 4 while true do 5 if ∀i, ¬activated(A i ) then Π = 6 A goal .extractSolution() end 7
Example In Figure 6, we illustrate a part of the execution of the second strategy to resolve the problem illustrated in 4. Firstly, each agent computes offline the cost of the optimal path between each couple of its neighbor states. For example, agent A 21 has three neighbor states, a, b, g.

It computes cost(a, b) = 1, cost(a, g) = 2, cost(b, g) = 3.
The initial agent A 21 computes the distance between the initial state a and its neighbor states b and c which are equal to 1 and 2. the goal agent A 43 computes also the distance between the goal state h and its neighbor states g and c which are equal to 1 and 3. As we can see, A 21 sets the value for reaching g from the intial state a with 2 and for reaching b with 1. A 43 also sets the value for reaching g from the goal state g with 1 and for reaching c with 3.

At the same time, A 21 and A 43 diffuses their costs :

Algorithm 5: Diffusing costs via neighbor states of agents dif f uses init (A, s) 1. A 21 diffuses costs respectively from a and b to g and h in A 11 (we omit this part here), and from g to a in A 31 . From the intial state, the cost of reaching a in A 31 is equal to ′ 3: cost of g(g) = 2 in A 21 , plus cost of link c(l ga ) = 1.

1 foreach s n ∈ S neighbor (A)\s do 2 g init (s n ) =min(g init (s n ), g init (s) + cost(s, s n )) 3 if (g goal (s n ) = +∞) then 4 g = g init (s n ) + g goal (s n ) 5 if g <

2.

A 43 diffuses costs respectively from g to i in A 42 , and from c to i in A 33 . From the intial state, the cost of reaching i in A 33 is equal to ′ 3: cost of g(c) = 3 in A 43 , plus cost of link c(l ci ) = 1 (similarly g(i) = 2).

A 31 , A 42 and A 33 continue diffusing their cost. In A 32 , costs from init and goal intersect in states b ([7, 10]) and g ([8, 7]). From this intersection, the optimal path having 15 as cost can be extracted from state g.

Completeness, optimality and complexity

In this section, we compare the complexity, optimality and completeness of A* and DEC-A* to prove the efficacy of our algorithm.

Complexity

The time and the space complexity of A* is exponential. It are equal to O(b m ) where b is the branching factor and m is the solution depth. Computation time is not, however, A*'s main drawback. Because it keeps all generated nodes in memory, A* is not practical for many large-scale problems.

The importance of our decentralized algorithm DEC-A* is to overcome the space problem by decomposing the computation space while also reducing the execution time.

In our approach, each graph can be associated to an agent. Agents can be deployed at multiple machines to execute their local A* in parallel. At first glance, the state space and the time execution will be divided between agents. Let l be

a b c c a c a f e f d e f d g h i g h i i g h i a b[1,] c a a b c a f e f d f d e g[2,] h i g h i i g h i a[3,] b[4,] c[5,] a[6,] b[7,10] ] g=17 a b c [,6] a c f f [,5] d g[5,] h[6,] i g [8,7] g=15 i [,7] g [,6] i [,4] g h i a b c a [,6] b c a b c [,3] a f d [,5] f d i g [,4] i [,2] g [,1] g 4 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2

Completeness

The completeness of A* is ensured because that, in the worst case, it develops all the possible states. DEC-A* is also complete by using the first or the second strategy, because it develops all the possible states except those having f (s) > cost(Π) where Π is the shortest founded plan. In this case, DEC-A* prunes state after finding a plan, so DEC-A* is complete.

Optimality

The optimality of A* is ensured if the heuristic function h is admissible. This means that it never overestimates the cost to reach the goal (i.e. f oreachnodes, h(s) < g(s)). A* finds the optimal path more quickly that h is close to g.

Our DEC-A* is also optimal because, except pruned path, it computes all the possible path and choice the optimal one. Pruned path does not prevent the optimality since they are pruned because their costs are more than the cost of the shortest path.

Messages number

RELATED WORKS

?? A number of classical graph search algorithms have been developed for resolving the problem of calculating the optimal sequence of actions that reach a goal state from an initial state on a weighted graph; two popular ones are: Dijkstras algorithm ( [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF]) and A* ((P. E. [START_REF] Hart | A formal basis for the heuristic determination of minimum cost paths[END_REF]).

Since discovering these algorithms, researchers working on our problem concentrate their interest on operating in real world scenarios when the planner do not have complete information. In this case, path generated using the initial information about the graph may turn out to be invalid or suboptimal as it receives updated information. Using the classical algorithms to reach the goal state by re-planning from scratch is a waste of computation. That's why, A number of extended algorithms from A* like (D*(Stentz 1995) D* light (Koenig and Likhachev 2002b) ARA* [START_REF] Likhachev | Ara*: Anytime A* with provable bounds on sub-optimality[END_REF]) was developed to take the previous solution and repair it to account for the changes to the graph. In the last decade, Sven koenig et al. are interested to solve a series of similar planning tasks faster than by solving the individual planning task in isolation, see: Incremental A* (Koenig and Likhachev 2002a), Real-Time Adaptive A* [START_REF] Sun | Real-time adaptive A[END_REF], Tree Adaptive A* [START_REF] Hernández | Tree adaptive A*[END_REF].

To the best of our knowledge, no one has worked on extending A* when the planning domain is constituted of a set of linked graphs. This means that finding the optimal path between two nodes in the domains should uses A* without taking advantage of the decentralization of the domain.

In contrast, there is a lot of works in artificial intelligence on developing distributed algorithms to resolve centralized or decentralized problems. We can cite the DEC-MDP [START_REF] Sigaud | Markov Decision Processes and Artificial Intelligence[END_REF] modeling decision-making in markovian process, multiagent automated planning based on STRIPS model [START_REF] Shoham | Multiagent Systems -Algorithmic, Game-Theoretic, and Logical Foundations[END_REF] or based on distributed CSP to coordinate between agents and local planning to ensure the consistency of these coordination points [START_REF] Nissim | A general, fully distributed multi-agent planning algorithm[END_REF].

Our extension algorithm DEC-A* is inspired from a new distributed multiagent planning approach proposed in [START_REF] Falou | A distributed planning approach for web services composition[END_REF]. In this approach, agents coordinates by proposing their best plans evaluated basing on local heuristic and global heuristic. The local heuristic estimates the distance to the goal. The global heuristic evaluates the importance of the plan taking into account the plans proposed by the other agents.

CONCLUSION AND FUTURE WORKS

In this paper, we proposed a dentralized extension of A*: the algorithm of finding the shortest path. The decentralized algorithm DEC-A* extends the heurisitc function to be the sum of two functions: a local heurisitc which estimates the cost of the local fragment of the solution, and a global heurisitc which estimates the sum of the costs of the next solution fragment.

Our DEC-A* is complete, optimal and its complexity is less than the complexity of A*.

In the future, we must implement and test DEC-A* to show its effectiveness.

If it is the case, We will see how can we extend DEC-A* to improve its efficacy to solve similar planning problems or planning with incomplete information by extending the algorithms like Incremental A* (Koenig and Likhachev 2002a) (to obtain Incremental DEC-A*), Real-Time Adaptive A* [START_REF] Sun | Real-time adaptive A[END_REF] (to obtain Real-Time Adaptive DEC-A*), Tree Adaptive A* [START_REF] Hernández | Tree adaptive A*[END_REF] (to obtain Tree Adaptive DEC-A*).

Finally, we must see how to extend all versions of DEC-A* from one intial and goal states, to multi intial and goal states.

  Figure 2: Global heuristic computation, step 1 2 0 4 0 2 2 3 1 2 2 2 1 4 4 0 0

Figure 5 :

 5 Figure 5: Search graphs

Figure 6 :

 6 Figure 6: Second strategy

The neighbor-states of a graph are their states linked by a link to another graph.

In the rest of this paper, when we explain algorithms, we use (x) and mean (line x)