Darko Dimitrov

Tomáš Dvořák

Petr Gregor
email: gregor@ktiml.mff.cuni.cz.

Riste Škrekovski

Gray Codes Avoiding Matchings †

Keywords: Gray code, hypercube, Hamiltonian path, Hamiltonian cycle, matching, fault tolerance

A (cyclic) n-bit Gray code is a (cyclic) ordering of all 2 n binary strings of length n such that consecutive strings differ in a single bit. Equivalently, an n-bit Gray code can be viewed as a Hamiltonian path of the n-dimensional hypercube Qn, and a cyclic Gray code as a Hamiltonian cycle of Qn. In this paper we study (cyclic) Gray codes avoiding a given set of faulty edges that form a matching. Given a matching M and two vertices u, v of Qn, n ≥ 4, our main result provides a necessary and sufficient condition, expressed in terms of forbidden configurations for M , for the existence of a Gray code between u and v that avoids M . As a corollary, we obtain a similar characterization for a cyclic Gray code avoiding M . In particular, in the case that M is a perfect matching, Qn has a (cyclic) Gray code that avoids M if and only if Qn -M is a connected graph. This complements a recent result of Fink, who proved that every perfect matching of Qn can be extended to a Hamiltonian cycle. Furthermore, our results imply that the problem of Hamiltonicity of Qn with faulty edges, which is NP-complete in general, becomes polynomial for up to 2 n-1 edges provided they form a matching.

Introduction

A (cyclic) n-bit Gray code is a (cyclic) ordering of all 2 n binary strings of length n such that consecutive strings differ in a single bit. It is named after Frank Gray, who in 1953 patented a simple scheme to generate such a cyclic code for every n ≥ 2 [7]. Since then, the research on Gray codes satisfying certain additional properties has received a considerable attention, and applications have been found in such diverse areas as data compression, graphics and image processing, information retrieval, signal encoding or processor allocation in hypercubic networks [START_REF] Savage | A survey of combinatorial Gray codes[END_REF].

Alternatively, an n-bit Gray code can be viewed as a Hamiltonian path of the n-dimensional hypercube Q n , and a cyclic Gray code as a Hamiltonian cycle of Q n . The applications of hypercubes in parallel computing [START_REF] Leighton | Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes[END_REF] inspired the investigation of Hamiltonian paths and cycles in hypercubes avoiding a given set of faulty edges. Chan and Lee [START_REF] Chan | On the existence of Hamiltonian circuits in faulty hypercubes[END_REF] proved that the problem whether Q n contains a Hamiltonian cycle avoiding a given set F of faulty edges is NP-complete. On the other hand, they showed that if |F| ≤ 2n -5, n ≥ 3, then such a Hamiltonian cycle exists if and only if each vertex is incident with at least two nonfaulty edges. This upper bound is sharp in the sense that for any n ≥ 3 there are 2n -4 faulty edges in Q n satisfying the above condition, but there is no Hamiltonian cycle avoiding them. Tsai [START_REF] Tsai | Linear array and ring embeddings in conditional faulty hypercubes[END_REF] obtained a similar result for Hamiltonian paths with given endvertices.

A related problem considers Hamiltonian cycles and paths in hypercubes passing through a set of prescribed edges. Caha and Koubek [START_REF] Caha | Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets[END_REF] observed that if a set P of prescribed edges extends to a Hamiltonian cycle, then it induces a subgraph consisting of pairwise vertex-disjoint paths. On the other hand, they showed that for any n ≥ 3 there is a set of 2n -2 edges, satisfying this necessary condition, but there is no Hamiltonian cycle of Q n containing them. This bound is sharp in the sense that if |P| ≤ 2n -3, n ≥ 2, the necessary condition is also sufficient for a Hamiltonian cycle of Q n passing through every edge of P [START_REF] Dvo | Hamiltonian cycles with prescribed edges in hypercubes[END_REF]. There is a similar result for Hamiltonian paths with prescribed endvertices if |P| ≤ 2n -4, n ≥ 5 [START_REF] Dvo Ř Ák | Hamiltonian paths with prescribed edges in hypercubes[END_REF]. A special case of the above problem, posed by Ruskey and Savage [START_REF] Ruskey | Hamilton cycles which extend transposition matchings in Cayley graphs of S n[END_REF], is when the prescribed edges comprise a matching of the hypercube. Kreweras [START_REF] Kreweras | Matchings and Hamiltonian cycles on hypercubes[END_REF] conjectured that every perfect matching of Q n , n ≥ 2, can be completed to a Hamiltonian cycle. Recently, the conjecture was proved by Fink [START_REF] Fink | Perfect matchings extend to Hamilton cycles in hypercubes[END_REF].

In this paper we study (cyclic) Gray codes avoiding a given set of faulty edges that form a matching. Given a matching M and two vertices u, v of Q n , n ≥ 4, our main result provides a necessary and sufficient condition for the existence of a Gray code between u and v that avoids M . As a corollary, we obtain a similar characterization for the existence of a cyclic Gray code avoiding M . In particular, in the case that M is a perfect matching, Q n has a (cyclic) Gray code that avoids M if and only if Q n -M is a connected graph.

Note that this complements the above quoted result of Fink. Furthermore, since our necessary and sufficient conditions are decidable in a polynomial time, our results imply that the problem of Hamiltonicity of Q n with faulty edges, which is NP-complete in general, becomes polynomial for up to 2 n-1 edges provided they form a matching.

After definitions and preliminary results in the next two sections, we study necessary conditions in Sections 4 and 5. The induction step of our construction is presented in Section 6, while the obtained results are summarized in Section 7. The study of initial cases n = 3 and n = 4, which involves a rather elaborate case analysis, can be found in Appendix A and B.

Preliminaries

In this text n is always a positive integer and [n] denotes the set {1, 2, . . . , n}. As usual, the vertex and edge sets of a graph G are denoted by V (G) and E(G), respectively. For a vertex v ∈ V (G) and a set E ⊆ E(G), let Gv denote the subgraph of G induced by V (G) \ {v}, and let G -E denote the graph with vertices V (G) and edges E(G) \ E. Similarly, for a pair of vertices x, y ∈ V (G) let G + xy denote the graph with vertices V (G) and edges E(G) ∪ {xy}. The distance of vertices u and v is denoted by d(u, v). The distance d(u, vw) of a vertex u and an edge vw is defined as the minimum of distances d(u, v) and d(u, w).

A path between a and b, denoted by P ab , is a graph consisting of pairwise distinct vertices a = x 1 , x 2 , . . . , x n = b and edges x i x i+1 for all i ∈ [n -1]. Note that if a = b, then n = 1 and we obtain the trivial path P aa consisting of a single vertex a. If P ab and P cd are vertex disjoint paths and b and c are adjacent vertices, then P ab + P cd denotes the path between a and d, obtained as a concatenation of P ab with P cd . A path P is called a subpath of a path P ′ if P forms a subgraph of P ′ . We say that paths

{P i } n i=1 are spanning paths of a graph G if {V (P i )} n i=1 partitions V (G). The n-dimensional hypercube Q n is the graph with vertex set V (Q n ) = {0, 1} n and edge set E(Q n ) = {uv | |∆(u, v)| = 1} where ∆(u, v) = {i ∈ [n] | u i = v i }. The dimension dim(uv) of an edge uv ∈ E(Q n ) is the integer d such that ∆(u, v) = {d}. For a vertex v ∈ V (Q n ) let v d denote the vertex of Q n such that vv d is an edge of dimension d.
All edges of the same dimension d form a layer (of dimension d) in Q n . Note that E(Q n ) is partitioned into n layers, each of size 2 n-1 . Moreover, for every d ∈ ∆(u, v), each path P uv contains an edge of dimension d . In other words, vertices u and v are separated by the layer of dimension d.

The

parity p(v) of a vertex v ∈ V (Q n ) is defined by p(v) = v mod 2 where v = n i=1 v i .
Note that vertices of each parity form bipartite sets of Q n . Consequently, p(u) = p(v) if and only if d(u, v) is even. We extend the definition of the parity to edges by putting for uv

∈ E(Q n ) p(uv) = p(u), if u < v ; p(v), otherwise. For every d ∈ [n] let Q d L and Q d R denote the subgraphs of Q n induced by the sets {v ∈ V (Q n ) | v d = 0} and {v ∈ V (Q n ) | v d = 1}
, respectively. The symbols L and R stand for 'left' and 'right', which corresponds to the presentation of

Q L and Q R in our figures. Note that both Q d L and Q d R are isomorphic to Q n-1 . Similarly, for a matching M in Q n put M d = {e ∈ M | dim(e) = d}, M d L = M ∩ E(Q d L )
, and

M d R = M ∩ E(Q d R ). Observe that (Q a i ) b j = (Q b j ) a i and (M a i ) b j = (M b j ) a i for every a, b ∈ [n]
and i, j ∈ {L, R}. Given a set F of faulty edges of Q n , we say that a subgraph of Q n avoids F if it forms a subgraph of Q n -F .

Some fundamental results

A classical result of Lewinter and Widulski [START_REF] Lewinter | Hyper-Hamilton laceable and caterpillar-spannable product graphs[END_REF] describes Hamiltonian paths in hypercubes with one faulty vertex.

Lemma 1 For any pairwise distinct vertices u, v, w in Q n such that p(u) = p(v) = p(w), there exists a Hamiltonian path of Q nw between u and v.

There is a similar characterization for hypercubes with at most one faulty edge, which follows from more general results of Tsai et al. [START_REF] Tsai | Fault-tolerant Hamiltonian laceability of hypercubes[END_REF]. It should be remarked that the special case of M = ∅ was firstly observed by Havel [START_REF] Havel | On Hamiltonian circuits and spanning trees of hypercubes[END_REF].

Lemma 2 For every n ≥ 3, vertices u and v of different parities, and a matching M of Q n with |M | ≤ 1, there exists a Hamiltonian path in Q n -M between u and v.

An extension of the above mentioned Havel's result was obtained in [START_REF] Dvo | Hamiltonian cycles with prescribed edges in hypercubes[END_REF].

Lemma 3 For every distinct vertices u, v, x, y of Q n such that p(u) = p(v) and p(x) = p(y), there exist spanning paths P uv , P xy of Q n .

We shall also employ the following lemma on the existence of a Hamiltonian path passing through a prescribed edge, which is a special case of more general results of Caha and Koubek [START_REF] Caha | Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets[END_REF].

Lemma 4 For every two vertices u, v and an edge e of Q n such that p(u) = p(v) and e = uv, there exists a Hamiltonian path of Q n between u and v passing through e.

We conclude this section with a simple observation.

Proposition 1 For every matching M in Q n with |M | = 2 there exists a dimension d ∈ [n] such that |M d L | = |M d R | = 1.
Proof: We argue by induction on n. Since the case n ≤ 2 is obvious, assume that n ≥ 3 and choose an arbitrary

d ∈ [n] \ {dim(e) | e ∈ M }. If |M d L | = |M d R | = 1
, we are done. Otherwise it must be the case that M = M d i for some i ∈ {L, R} and hence by the induction hypothesis, there exists We shall see in the next section that half-layers are obstacles that cannot be overcome. More precisely, we shall see in Lemma 6 that there is no Hamiltonian cycle avoiding a half-layer. The need to treat half-layers as a special case motivates the following definitions.

d ′ ∈ [n] \ {d} such that |M d ′ L | = |(M d i ) d ′ L | = 1 = |(M d i ) d ′ R | = |M d ′ R | as required. ✷ 4 Half-layers A matching M in Q n , n ≥ 2, is called a half-layer in Q n if M consists
Given a matching

M in Q n , we call d ∈ [n] • a main dimension of M in Q n if M d contains a half-layer in Q n ;
• a splitting dimension for M if M d i does not contain a half-layer in Q d i for both i ∈ {L, R}.

Now we show that the main dimension is uniquely determined. (ii) d is the unique main dimension of M a i in Q a i for every a ∈ [n] \ {d} and i ∈ {L, R} provided n ≥ 3.

Proof: Since for every edge uv ∈ E(Q n ) of dimension d ′ = d we have p(u) = p(v), it follows that at least one of u, v must be incident with an edge of M d . Hence uv ∈ M and consequently, M d L = M d R = ∅. This, together with the fact that M d contains a half-layer and therefore must be nonempty, verifies part (i).

To see why (ii) holds, note that if n ≥ 3, then a half-layer in Q n contains a half-layer in both Q a L and Q a R by definition. It follows that d is a main dimension of M a i in Q a i while the uniqueness follows from part (i).

✷

A matching M in Q n is called aligned if there exists a dimension d ∈ [n] such that |M d L | ≤ 1 and |M d R | ≤ 1.
Otherwise, it is called unaligned. Note that a matching containing a half-layer is always aligned by Proposition 2(i). For aligned matchings our problem is easy, as we shall see in the next section. But this is not the case with unaligned matchings. For them, we use the following lemma.

Lemma 5 If M is an unaligned matching in Q n , n ≥ 4, then there are at least two splitting dimensions for M .

Proof: First note that if every a ∈ [n] is a splitting dimension for M , we are done. Hence we can assume that this is not the case, i. e., there exist distinct a, b ∈ [n] such that b is the main dimension of M a L in Q a L . Case 1: b is not a splitting dimension for M . Then there exist i ∈ {L, R} and d ∈ [n] \ {b} such that d is the main dimension of M b i . Assume that d = a. Then Proposition 2 (ii) implies that d is also the main dimension of

(M b i ) a L in (Q b i ) a L . It follows that (M a L ) b i = (M b i ) a
L contains a half-layer. On the other hand, as b is the main dimension of M a L , Proposition 2 (i) reveals that M a L contains only edges of dimension b and therefore (M a L ) b i = ∅. This, however, leads to a contradiction since a half-layer is always nonempty. Hence we conclude that d = a.

Now choose an arbitrary c ∈ [n] \ {a, b} and j ∈ {L, R} and suppose that M c j contains a half-layer in Q c j . Using Proposition 2 (ii) again, a and b are the main dimensions of (

M b i ) c j and (M a L ) c j in (Q b i ) c j and (Q a L ) c j , respectively. Since (M b i ) c j = (M c j ) b i and (M a L ) c j = (M c j ) a L , part (ii)
of Proposition 2 implies that a and b are also main dimensions of M c j in Q c j , while part (i) then reveals that a = b, which is a contradiction with our assumption. Hence c must be a splitting dimension for M . It follows that there exist n -2 ≥ 2 splitting dimensions in this case.

Case 2: b is a splitting dimension for M . In this case we need to show that there exists another splitting dimension for M , different from b. Assume, by way of contradiction, that this is not the case. Then for any c ∈ The next lemma gives necessary conditions for a Gray code avoiding a given matching.

[n] \ {b} there exists i ∈ {L, R} such that M c i contains a half-layer. Recall that b is the main dimension of M a L in Q a L . If c = a, then Proposition 2 (ii) implies that b is the main dimension of (M a L ) c i = (M c i ) a L in (Q a L ) c i and therefore b is also the main dimension of M c i in Q c i . Hence we conclude that for any c ∈ [n] \ {b} there exists i ∈ {L, R} such that b is the main dimension of M c i in Q c i . Since M is
Lemma 6 Let M be a matching and u, v vertices of Q n . If there exists a Hamiltonian path in Q n -M between u and v, then

(i) p(u) = p(v); (ii) for every d ∈ ∆(u, v) there exists an edge e ∈ E(Q n ) \ M of dimension d such that d(u, e) is odd; (iii) for every d ∈ [n] \ ∆(u, v) there exist two edges in E(Q n ) \ M of dimension d of different parities;
(iv) M contains no almost-layer with a free pair {u, v}.

Proof: Claims (i)-(iii) follow from the facts that in a hypercube the number of vertices of odd parity equals the number of vertices of even parity, and that the parity of vertices on every path alternates. To verify (iv), observe that if M is an almost-layer with a free pair {u, v} ⊆ V (Q d L ), then every path

P uv in Q n -M avoids either all vertices of V (Q d L ) \ {u, v}, or all vertices of V (Q d R )
, and therefore cannot be Hamiltonian.

✷

We say that a triple (u, v, M ) is a configuration in Q n if M is a matching in Q n and u and v are vertices of different parities, i. e., condition (i) of Lemma 6 holds. Since we do not need to distinguish between vertices u and v, we consider the configurations (u, v, M ) and (v, u, M ) to coincide. If, moreover, conditions (ii)-(iv) of Lemma 6 hold, we say that the configuration (u, v, M ) is admissible.

The conditions (ii) and (iii) of Lemma 6 can be unified into one condition using a slight modification of the concept of a half-layer. Note that since a half-layer contains only edges of the same parity, the distances of a given vertex to edges of a given half-layer must also have the same parity. If the distance of a vertex u to edges of a half-layer M in Q n is odd, we say that M is an odd half-layer for the vertex u. (ii) M contains no almost-layer with a free pair {u, v}.

The next lemma shows that these conditions are also sufficient for the existence of a Hamiltonian path in Q n , n ≥ 4, provided that M is aligned.

Lemma 7 Let M be an aligned matching, and let u and v be vertices of

Q n , n ≥ 4 . If (u, v, M ) is an admissible configuration, then Q n -M contains a
1: v ∈ V (Q d R ). Since (u, v, M
) is an admissible configuration, there exists a vertex w ∈ V (Q d L ) such that p(u) = p(w) and ww d ∈ M . Note that then also p(w d ) = p(v). Now, by Lemma 2, there exist Hamiltonian paths

P uw of Q d L -M d L and P w d v of Q d R -M d R . Then P uv := P uw + P w d v is the required Hamiltonian path. Case 2: v ∈ V (Q d L ).
Here, we consider the following subcases. Subcase 2.1:

M d L = ∅. Since (u, v, M ) is an admissible configuration, there are vertices x, y ∈ V (Q d L ) such that p(x) = p(y), xx d ∈ M , yy d ∈ M ,
and {u, v} = {x, y}. Apply Lemma 2 to obtain a Hamiltonian path

P x d y d of Q d R -M d R .
Note that as p(u) = p(v) and p(x) = p(y), we can assume that also p(u) = p(x) and p(v) = p(y), interchanging x and y if necessary.

We conclude the subcase with the following construction. If {u, v} ∩ {x, y} = ∅, then apply Lemma 3 to obtain spanning paths P ux and P vy of Q d L and put P uv := P ux + P x d y d + P yv . Otherwise it must be the case that |{u, v} ∩ {x, y}| = 1. Assume without a loss of generality that v = x and u = y. Then apply Lemma 1 to obtain a Hamiltonian path P uy of Q d Lv and put P uv := P uy + P y d x d + P xx . In both cases we obtained the required Hamiltonian path.

Subcase 2.2: M d L = {e}. If e = uv, then put xy = e and apply the construction of Subcase 2.1. So, we may assume that e = uv. Since (u, v, M ) is an admissible configuration, there is a vertex y ∈ V (Q d L ) \ {u, v} such that yy d ∈ M . Assume without a loss of generality that p(u) = p(y). Finally, put x = v and apply the construction of Subcase 2.1 in order to conclude this case. ✷ Note that the above lemma does not hold for n = 3, see e. g. configurations (e), (f) or (g) in Figure 1. The case of small dimensions is analyzed separately in Appendix A and B.

Gray codes in hypercubes of higher dimensions

In this section we use AL(u, v, M, Q n ) to denote the fact that a matching M contains an almost-layer in Q n with a free pair {u, v}. Recall that if AL(u, v, M, Q n ) holds, then there exists d such that M d consists of all edges of dimension d except uu d and vv d . The following simple observation is used later.

Proposition 4 Let M be a matching which contains an almost-layer A with a free pair {u,

v} in Q n , n ≥ 4. (i) If AL(u, w, M, Q n ) holds, then v = w.
(ii) If at least one of vertices x, y is incident with an edge of A, then AL(x, y, M, Q n ) does not hold.

Note that the assumption n ≥ 4 is for part (ii) essential, as it fails to hold in the case that M is the perfect matching of Q 3 depicted in Figure 2 [START_REF] Leighton | Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes[END_REF]. Now we are ready to resolve the case of matchings not containing a half-layer.

Lemma 8 Let u, v ∈ V (Q n ), n ≥ 4, such that p(u) = p(v) and let M be a matching in Q n containing no half-layer. Then Q n -M contains a
Notice that also p(w d ) = p(v). We claim that w can be chosen so that neither AL(u, w,

M d L , Q d L ) nor AL(w d , v, M d R , Q d R ) holds. Indeed, if M d L contains an almost-layer A in Q d L
with a free pair {u, w}, then each edge of A contains one vertex that can play the role of w in [START_REF] Caha | Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets[END_REF]. Hence there are still |A| = 2 n-2 -2 > 2 choices for w, and M d R may contain an almost-layer in Q d R with a free pair {w d , v} for no more than one of them by Proposition 4(i).

It remains to apply the induction to obtain Hamiltonian paths P uw and

P w d v of Q d L -M d L and Q d R -M d R
, respectively, and finally put P uv := P uw + P w d v to conclude this case.

Case

2: v ∈ V (Q d L ). Consider the following subcases. Subcase 2.1: AL(u, v, M d L , Q d L ) holds. Since M d L contains an almost-layer A with 2 n-2 -2 > 3 edges, Proposition 4(ii) implies that there must be an edge xy ∈ A such that M d R contains no almost-layer in Q d
R with a free pair {x d , y d }. Thus, by the induction hypothesis, there are Hamiltonian paths P uv and

P x d y d of Q d L -(M d L \ {xy}) and Q d R -M d R
, respectively. Note that by Lemma 6, the path P uv passes through the edge xy, and hence there are subpaths P ux and P yv of P uv such that P uv = P ux + P yv . It remains to put P uv := P ux + P x d y d + P yv to complete this subcase.

= 2|A| = 2 n-1 -4 > 2 n-2 = |V (Q d L )|/2 = |V (P L uv )|/2
and hence there exist x, y ∈ S that are neighbors on P L uv . Then, it follows by Proposition 4(ii) that

AL(x d , y d , M d R , Q d R )
|M d | ≥ |V (P L uv )|/2 = 2 n-2 . ( 2
)
If this inequality is strict, then |M | ≤ 2 n-1 implies that |M d ′ | < 2 n-2
, contrary to (2), and hence the claim holds. Thus we can assume that

|M d | = |M d ′ | = 2 n-2 . (3)
This means that

|M d | = |V (P L uv )|/2
, which together with the assumption of this subcase implies that |{xx d , yy d } ∩ M d | = 1 for each pair x, y of neighbors on P L uv . Since the parity of consecutive vertices on P L uv alternates, it follows that if uu d ∈ M d , then xx d ∈ M d for each vertex x ∈ V (P L uv ) with p(u) = p(x). However, this would mean that M contains a half-layer, contrary to our assumption. Since the same reasons apply to the endvertex v, we conclude that neither u nor v are incident with an edge of M d . Applying the same argument to the dimension d ′ , it follows that

|M d | + |M d ′ | ≤ |V (Q n ) \ {u, v}|/2 = 2 n-1 -1, contrary to (3). ✷ 7
The main results

Now we are ready to formulate the necessary and sufficient conditions for (cyclic) Gray codes avoiding a given matching. Note that the conditions are expressed in terms of half-layers and almost-layers, which were defined in Sections 4 and 5, respectively.

Theorem 1 Let M be a matching, and let u and v be vertices of Q n , n ≥ 4. Then Q n has a Gray code between u and v that avoids M if and only if M contains no odd half-layer for u or v and no almost layer with a free pair {u, v}.

Proof: Recall that (u, v, M ) is an admissible configuration if and only if the left side of the equivalence holds, by Proposition 3. The necessity is settled by Lemma 6. The sufficiency follows from Lemma 7 in the case M contains a half-layer, and from Lemma 8 otherwise. ✷

It should be noted that for n = 3 the problem is fully described by Lemma 9 in Appendix A, and for n ≤ 2 it is trivial.

Corollary 1 Let M be a matching in Q n , n ≥ 4. Then Q n has a cyclic Gray code that avoids M if and only if M does not contain a half-layer.

Proof: Observe that the following two equivalences hold.

• Q n -M contains a Hamiltonian cycle ⇐⇒ Q n -M contains a Hamiltonian path P uv for some edge uv ∈ E(Q n );

• there exists an admissible configuration (u, v, M ) for some edge uv ∈ E(Q n ) ⇐⇒ M does not contain a half-layer.

The corollary now follows from Theorem 1. ✷

Corollary 2 Let M be a perfect matching in Q n . Then the following three statements are equivalent:

(i) Q n has a Gray code avoiding M ;

(ii) Q n has a cyclic Gray code avoiding M ;

(iii) Q n -M is connected.
Proof: First observe that clearly (ii) =⇒ (i) and (i) =⇒ (iii). Hence it only remains to prove that (iii) =⇒ (ii). To that end, notice that for any perfect matching

M of Q n , M contains a half-layer in Q n ⇐⇒ M forms a layer of Q n ⇐⇒ Q n -M is disconnected.
The validity of the implication (iii) =⇒ (ii) for n ≥ 4 now follows from Corollary 1, the case n = 3 may be verified by inspection of parts ( 9) and (10) of Figure 2, and the case n ≤ 2 is trivial. ✷

Appendix A: Gray codes in Q 3

At this point it only remains to settle the initial cases n = 3 and n = 4. Note that we were able to use computer search to verify the main result of this part, namely Lemma 14, which is needed for the induction basis in the proof of Lemma 8. However, considering the difficulties in independently verifying computer-aided proofs, here we provide arguments that may be verified without a computer assistance. This involves a rather elaborate case analysis, but we believe that in this case it is indispensable. A configuration (u, v, M ) in Q n is good if there is a Hamiltonian path of Q n -M between u and v. Otherwise it is bad. In this terminology, our aim is to characterize all good configurations.

A configuration

(u, v, M 1 ) contains a configuration (u, v, M 2 ) if M 1 ⊇ M 2 .
A bad configuration is minimal if it does not contain any other bad configuration. An admissible configuration is maximal if it is not contained in any other admissible configuration. Similarly, a matching is maximal if it is not contained in any other matching.

We start with the list of all minimal bad configurations in Q 3 .

Lemma 9 Let u and v be vertices of different parity and let M be a matching in Q 3 . Then there is a Hamiltonian path of Q 3 -M between u and v unless (u, v, M ) contains one of the bad configurations depicted in Figure 1.

u v v v v (a) (b) (c) (d) (e) (f) (g) u v u v v u u u u
Fig. 1: The minimal bad configurations in Q3.

Proof: First observe that each configuration (u, v, M ) in Figure 1 is bad. Note that M is presented with dashed lines. Moreover, observe that there are no two configurations in Figure 1 such that the first one contains the other one. Now we show that the configuration (u, v, M ) is either good or contains one of the bad configurations in Figure 1. The hypercube Q 3 has 10 non-isomorphic matchings, including the empty one, depicted in Figure 2(1)- [START_REF] Leighton | Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes[END_REF]. Note that in this figure the edges of the matchings are presented with dashed lines. So M is one of the following cases in Figure 2.

(1), ( 2): In these cases M has at most one edge, thus the configuration (u, v, M ) is good by Lemma 2.

(3), ( 6): Observe that if u ∈ {u 1 , u 2 } and v ∈ {v 1 , v 2 }, then the configuration (u, v, M ) is good. Otherwise it contains a configuration of type (a), (b), or (c) in Figure 1.

(

): Observe that the configuration (u, v, M ) is good unless it equals (u 1 , v 1 , M ) or (u 2 , v 2 , M ) 4
which are of type (d) in Figure 1.

(5): Observe that the configuration (u, v, M ) is good unless it equals (u 1 , v 1 , M ), (u 1 , v 2 , M ), or (u 2 , v 2 , M ) which are of type (e) or (f) in Figure 1.

(7): In this case Q 3 -Mxy is a Hamiltonian cycle. Thus the configuration (u, v, M ) is good if uv is an edge on this cycle. Furthermore, if the configuration (u, v, M ) equals (u 1 , v 1 , M ) or (u 2 , v 2 , M ), observe that it is also good. Otherwise it contains a configuration of type (e) or (f) in Figure 1.

v 1 u 1 v 1 u 1 (1) (2) (3) (4) (5) (6) (7) (8) (9) ( 10
)
u 2 v 2 v 1 u 1 u 2 v 2 u 2 v 2 u 1 v 2 v 1 u 2 u 1 v 1 v 1 u 1 v 2 u 2
x y Fig. 2: All matchings in Q3 up to isomorphism. [START_REF] Havel | On Hamiltonian circuits and spanning trees of hypercubes[END_REF]: Observe that if uv ∈ M , then the configuration (u, v, M ) is good. Furthermore, it is also good if d(u, v) = 3 and {u, v} = {u 1 , v 1 }. Otherwise it contains a configuration of type (e), (f), or (g) in Figure 1.

(

): In this case Q 3 -M is disconnected so (u, v, M 9
) is a bad configuration. Observe that it contains a configuration of type (a), (b), or (c) in Figure 1.

(10): In the last case Q 3 -M is a Hamiltonian cycle. Thus the configuration (u, v, M ) is good if uv is an edge on this cycle. Otherwise it contains a configuration of type (e) or (f) in Figure 1.

This completes the analysis of all cases and establishes the lemma. ✷

The following two lemmas will be useful for inquiry of Q 4 in the next section. The first lemma applies typically for configurations (u, v, M ) such that both u and v belong to a same subcube

Q d L or Q d R which contains at most 2 edges of M .
Lemma 10 Let u and v be vertices of different parity and let e 1 and e 2 be distinct edges in Q 3 . Then there is a Hamiltonian path of Q 3 between u and v that (i) contains exactly one of e 1 and e 2 ; or (ii) avoids both e 1 , e 2 but contains an edge xy such that x ∈ e 1 and y ∈ e 2 .

Proof: Suppose first that u and v are at distance 3. From Figure 3(1) it is obvious that all Hamiltonian paths between u and v are isomorphic. Moreover, each of them contains one edge of the upper level, one edge of the lower level, and five edges of the middle level. Considering few cases, regarding the levels that contain e 1 and e 2 , it is easy to find a suitable path.

Suppose now that uv is an edge of Q 3 . We distinguish three cases: Case 1: Edges e 1 and e 2 are adjacent at some vertex x. If x = u, then assume that e 1 = uy = uv and apply Lemma 1 to find a Hamiltonian path of Q 3u between y and v. Extending this path with the edge e 1 = uy we obtain a Hamiltonian path of Q 3 between u and v that contains e 1 and avoids e 2 . If x = v, then proceed similarly. Otherwise we have x / ∈ {u, v}. The Hamiltonian path between u and v that avoids e 1 from Lemma 2 contains e 2 since it passes through the vertex x.

Case 2: Edges e 1 and e 2 are at distance 1. If the edge uv is adjacent to both e 1 and e 2 , then we have two non-isomorphic cases in Figures 3(2)-(3) with desired Hamiltonian paths. Otherwise, we may assume that x ∈ e 1 , y ∈ e 2 , and y / ∈ {u, v} for some edge xy. The Hamiltonian path between u and v that avoids e 1 from Lemma 2 contains e 2 or xy since it passes through the vertex y.

R M = {4, 4, 0, 0} R M = {4, 2, 2, 0} R M = {4, 4, 0, 0} R M = {4, 2, 2, 0} R M = {4, 1, 1, 1} (2) (3) (4) (5)
Fig. 6: All maximal unaligned matchings M of Q4 with m(M ) = 4.

a 1 (1) (2) (3) (4) (5)
R M = {3, 2, 1, 1} R M = {3, 3, 1, 0} R M = {3, 3, 1, 0} R M = {3, 2, 1, 1} R M = {3, 2, 1, 1} a 2 a 4 a 3 b 2 b 4 b 1 b 3 a 1 a 2 b 2 b 1 b 3 b 4 a 4 a 3 a 1 a 2 a 3 a 4 b 2 b 1 b 4 b 3 Fig. 7: All maximal unaligned matchings M of Q4 with m(M ) = 3. (1) (2) (3) (4)
R M = {2, 2, 2, 2} R M = {2, 2, 2, 0} R M = {2, 2, 2, 2} R M = {2, 2, 2, 0} a 1 a 2 a 3 a 4 b 1 b 2 b 4 b 3 Fig. 8: All maximal unaligned matchings M of Q4 with m(M ) = 2. (1) (2) (3)
Fig. 9: All sets M d with 4 edges in a maximal unaligned matching M of Q4.

(

Q d

L there are at most four vertices that are not matched by M d L . Hence m(M ) ≤ 4. On the other hand, every maximal matching in Q 4 contains at least 6 edges [START_REF] Forcade | Smallest maximal matchings in the graph of the d-dimensional cube[END_REF], hence at least 2 edges from M are of a same dimension. This implies that m(M ) ≥ 2. So m(M ) ∈ {2, 3, 4}.

Let G L and G R be the graphs obtained from Q d L and Q d R , respectively, by removing all vertices incident with M d . Note that G L and G R are isomorphic, so let us write simply G when it is clear from the context for which of the graphs we speak. Since M is maximal, both M d L and M d R are maximal matchings of G. To show that M is one of the matchings in Figures 678 Note that in the following figures the isomorphic graphs G L and G R are presented in a mirrored way, so the matchings M d R and the maximal matchings of G are also presented in a mirrored way. Case 1: m(M ) = 4. Since M is unaligned, there are three non-isomorphic combinations of four edges in M d ; see Figure 9. We consider now three possibilities.

Subcase 1.1: M d is as in Figure 9(1). Obviously, there is only one maximal matching of G. Thus M d L and M d R are uniquely determined and the matching M is as in Figure 6(1). Subcase 1.2: M d is as in Figure 9(2). There are two maximal matchings of G depicted in Figure 10. By symmetry, we may assume that M d L is as in Figure 10(1). Now, if M d R is also as in Figure 10(1), the matching M corresponds to Figure 6(3). And, if M d R is as in Figure 10(2), then M corresponds to Figure 6(2).

Subcase 1.3: M d is as in Figure 9(3). There are two maximal matchings of G depicted in Figure 12. By the maximality of M , it follows that M d L and M d R are not both as in Figure 12(2). Now, if both of them are as in Figure 12(1), we infer Figure 6(4). Finally, if one of them is as in Figure 12(1), and the other one as in Figure 12(2), we infer Figure 6(5).

Case 2: m(M ) = 3. Since M is unaligned, there are two non-isomorphic combinations of three edges in M d which are depicted in Figure 11. Consider now these two cases separately.

Subcase 2.1: M d is as in Figure 11(1). There are three maximal matchings of G depicted in Figure 13. By symmetry, we may assume that if M d L is as in Figure 13(x), then M d R is as in Figure 13(y) where 1 ≤ x ≤ y ≤ 3. Moreover, since M is a maximal matching, we infer x = y. We have the following

(1) (2)
Fig. 11: All sets M d with 3 edges in a maximal unaligned matching M of Q4.

(2) (1) Fig. 12: All maximal matchings of G in Subcase 1.3.

(1) (2) (3)
Fig. 13: All maximal matchings of G in Subcase 2.1.

( possibilities for the pair (x, y):

) (2) (3) 1
(1, 3): The matching M is as in Figure 7(1);

(2, 3): The matching M is as in Figure 7(2);

(1, 2): This case is isomorphic to the case [START_REF] Caha | Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets[END_REF][START_REF] Dvo | Hamiltonian cycles with prescribed edges in hypercubes[END_REF]. Indeed, consider the isomorphism of Q 4 that interchanges vertices a i and b i in Figure 7(1) for every i ∈ [START_REF] Dvo Ř Ák | Hamiltonian paths with prescribed edges in hypercubes[END_REF] and fixes all other vertices.

Subcase 2.2: M d is as in Figure 11(2). There are four maximal matchings of G depicted in Figure 14. By symmetry, we may assume that if M d L is as in Figure 14(x), then M d R is as in Figure 14(y) where 1 ≤ x ≤ y ≤ 4. Moreover, since M is a maximal matching, it follows that x = y. Thus, we have the following possibilities for the pair (x, y):

(1, 4): The matching M is as in Figure 7(3);

(2, 4): The matching M is as in Figure 7(4); [START_REF] Dvo | Hamiltonian cycles with prescribed edges in hypercubes[END_REF][START_REF] Dvo Ř Ák | Hamiltonian paths with prescribed edges in hypercubes[END_REF]: The matching M is as in Figure 7(5);

(1, 2): This case does not occur since M is a maximal matching;

(1, 3) and (2, 3): These cases are isomorphic to the cases [START_REF] Chan | On the existence of Hamiltonian circuits in faulty hypercubes[END_REF][START_REF] Dvo Ř Ák | Hamiltonian paths with prescribed edges in hypercubes[END_REF] and [START_REF] Caha | Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets[END_REF][START_REF] Dvo Ř Ák | Hamiltonian paths with prescribed edges in hypercubes[END_REF], respectively. Indeed, consider the isomorphism of Q 4 that interchanges vertices a i and b i in Figures 7(4) and 7(3) for every i ∈ [START_REF] Dvo Ř Ák | Hamiltonian paths with prescribed edges in hypercubes[END_REF] and that fixes all other vertices. 16(1), or both as in Figure 16(2) since k(M ) = 3. Thus, one of them is as in Figure 16(1), and the other one as in Figure 16(2). Hence M corresponds to Figure 8(1). Subcase 3.2: k(M ) = 2. Thus M d is as in Figure 15(2). There are seven maximal matchings of G depicted in Figure 17. Observe that neither M d L nor M d R is as in Figures 17( 6)- (7) since k(M ) = 2. Furthermore, neither M d L nor M d R is as in Figure 17(5) since all matchings of G in Figures 17( 1)-( 5) contain at least one edge of e 1 or e 2 and k(M ) = 2. By symmetry, we may assume that if M d L is as in Figure 17(x),then M d R is as in Figure 17(y) where 1 ≤ x ≤ y ≤ 4. Moreover, x = y since M is a maximal matching. We have the following possibilities for the pair (x, y):

(1, 2): The matching M is as in Figure 8(4); [START_REF] Dvo | Hamiltonian cycles with prescribed edges in hypercubes[END_REF][START_REF] Dvo Ř Ák | Hamiltonian paths with prescribed edges in hypercubes[END_REF]: This case is isomorphic to the case (1, 2). Indeed, consider the isomorphism of Q 4 that interchanges vertices a i and b i in Figure 8(4) for every i ∈ [START_REF] Dvo Ř Ák | Hamiltonian paths with prescribed edges in hypercubes[END_REF] and fixes all other vertices.

(1, 3), [START_REF] Caha | Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets[END_REF][START_REF] Dvo Ř Ák | Hamiltonian paths with prescribed edges in hypercubes[END_REF], [START_REF] Chan | On the existence of Hamiltonian circuits in faulty hypercubes[END_REF][START_REF] Dvo | Hamiltonian cycles with prescribed edges in hypercubes[END_REF], and (2, 4): These cases do not occur since M is a maximal matching.

(

) (3) (2) 1
Fig. 15: All sets M d with 2 edges in a maximal unaligned matching M of Q4.

(1)

(2)

(3) (4) (5)
Fig. 16: All maximal matchings of G in Subcase 3.1.

(

) (2) (3) (4) (5) (6) 1
e 2 e 1 Fig. 17: All maximal matchings of G in Subcase 3.2.

( Subcase 3.3: k(M ) = 1. Thus M d is as in Figure 15(3). There are five maximal matchings of G depicted in Figure 18. Observe that neither M d L nor M d R is as in Figure 18(5) since m(M ) = 2. By symmetry, we may assume that if M d L is as in Figure 18(x), then M d R is as in Figure 18(y) where 1 ≤ x ≤ y ≤ 4. We have the following possibilities for the pair (x, y):

) (2) (3) (4) 1
(1, 2): The matching M is as in Figure 8(2); [START_REF] Dvo | Hamiltonian cycles with prescribed edges in hypercubes[END_REF][START_REF] Dvo Ř Ák | Hamiltonian paths with prescribed edges in hypercubes[END_REF]: The matching M is as in Figure 8(3);

(1, 1), [START_REF] Caha | Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets[END_REF][START_REF] Dvo | Hamiltonian cycles with prescribed edges in hypercubes[END_REF], [START_REF] Caha | Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets[END_REF][START_REF] Dvo Ř Ák | Hamiltonian paths with prescribed edges in hypercubes[END_REF], (2, 2), (2, 3), and (2, 4): These cases do not occur since m(M ) = 2;

(3, 3) and (4, 4): These cases do not occur since M is a maximal matching.

Note that the choice of the dimension d was not determined uniquely. Therefore, to conclude the proof, we need to verify that the matchings in Figures 678 and(u, v, M ) is admissible, it follows from the definition that (u, v, M ∪ {e}) is also admissible. But this contradicts the assumption that (u, v, M ) is a maximal admissible configuration. ✷ Now we are ready to find a Hamiltonian path of Q 4 -M between u and v if (u, v, M ) is admissible configuration. The following lemma serves as a basis of induction in the next section.

Lemma 14 Let M be a matching in Q 4 and u, v ∈ V (Q 4 ). If (u, v, M ) is admissible, then there is a Hamiltonian path of Q 4 -M between u and v.

Proof: If M is aligned, we can use Lemma 7 which holds for every n ≥ 4. Thus, it remains to consider admissible configurations (u, v, M ) only with unaligned matching M .

Assume that (u, v, M ) is a maximal admissible configuration, otherwise introduce new edges in M . Notice that with this procedure M stays unaligned. By Lemma 13, the matching M is maximal. Thus m(M ) ∈ {2, 3, 4} and M corresponds to one of the matchings in

∈ V (Q L ) and v ∈ V (Q R ) or vice versa.
In what follows, we distinguish three cases regarding m(M ). In each case we consider good/bad configurations in Q L and Q R . Then, regarding the position of vertices u and v, we look separately in Q L and Q R for paths that can be combined into a Hamiltonian path of Q 4 -M between u and v.

Case 1: m(M ) = 4. Applying Lemma 9, observe that Figure 20(1)-( 5) shows all bad configurations in Q L or Q R for each of the five maximal unaligned matchings M with m(M ) = 4 depicted in Figure 6, respectively. Vertices u and v that form a bad configuration (u, v, M L ) in Q L or (u, v, M R ) in Q R are encompassed by a solid elliptic curve, the matching M is represented by dashed edges, whereas other edges of Q 4 are omitted for the sake of clarity. For example, in Figure 20(2) we have two bad configurations in Q L and two bad configurations in Q R .

Subcase 1.1: Vertices u and v are separated. Assume that u ∈ V (Q L ) and v ∈ V (Q R ). We distinguish the following two possibilities.

1.1.1: M is as in Figure 20(1) and u or v is incident with M d . By symmetry, we may assume that u = a. Observe in Figure 21 that the statement of the lemma holds for each v ∈ V (Q R ) of different parity than u. The Hamiltonian paths are presented by bold edges.

1.1.2: M is as in Figure 20(2)-( 5) or none of u and v is incident with M d . Let w ∈ V (Q L ) be a vertex of different parity than u such that it is incident with M L . Then, v and w R are also of different parities. Observe in Figure 20(2)-( 5) that the vertices w and w R are in no bad configuration in Q L and Q R , respectively. Thus the configurations (u, w, M L ) and (v, w R , M R ) are good.

Hence there is a Hamiltonian path P uw of Q L -M L , and a Hamiltonian path

P w R v of Q R -M R . The desired Hamiltonian path of Q 4 -M is P uw + P w R v .
Subcase 1.2: Both vertices u and v are in Q L . Note that M L is of size 2, thus denote by e 1 , e 2 these two edges. By Lemma 10, there is a Hamiltonian path P uv that either contains precisely one of e 1 and e 2 , or avoids both e 1 , e 2 but contains an edge adjacent to both e 1 , e 2 . Let xy ∈ E(Q L ) be that contained edge. Observe in Figure 20(1)-( 5) that there is no bad configuration (w, z, M R ) in Q R such that w L and z L are both incident with e 1 or e 2 . Thus the configuration (x R , y R , M R ) is good.

Hence there is a Hamiltonian path P x R y R of Q R -M R . The desired Hamiltonian path of Q 4 -M is P ux + P x R y R + P yv where P ux and P yv are disjoint subpaths of P uv , assuming that x is closer to u on P uv than y.

Subcase 1.3: Both vertices u and v are in Q R . If M is as in Figure 20(1)-( 4), we have symmetry to the previous subcase. However, if M is as in Figure 20(5), then M R contains only one edge e 1 . Then just put e 2 = bc and proceed symmetrically as in Subcase 1.2.

Case 2: m(M ) = 3. Applying Lemma 9 observe that Figure 19(1)-( 5) shows all bad configurations in Q L or Q R for each of the five maximal unaligned matchings M with m(M ) = 3 depicted in Figure 7, respectively. We consider the following possibilities.

Subcase 2.1: Vertices u and v are separated. Again, assume that u ∈ V (Q L ) and v ∈ V (Q R ). We distinguish the following two possibilities.

2.1.1: M is as in Figure 19(1) and u is not incident with M L . Observe in Figure 22 that for each u ∈ V (Q L ) that is not incident with M L , there are spanning paths P uw L and P b L c L of Q 4 -M L . By Lemma 11, there is a Hamiltonian path P wv of Q R + bc that contains the edge bc and avoids M R .

Hence a desired Hamiltonian path of Q 4 -M is P uw L + P wb + P b L c L + P cv where P wb and P cv are disjoint subpaths of P wv , assuming that b is closer to w on P wv than c.

2.1.2: M is as in Figure 19(2)-( 5) or u is incident with M L . Let x, y ∈ V (Q L ) be vertices of different parity than u that are incident with M L . We can always choose such x, y since |M L | = 2. Observe in Figure 19(1) that each bad configuration in Q L includes at most one vertex incident with M L . Similarly,

Proposition 2

 2 Let d be a main dimension of a matching M in Q n , n ≥ 2. Then, (i) M contains only edges of dimension d. Consequently, d is the only main dimension of M .

  an unaligned matching, there must exist i ∈ {L, R} such that M b i contains two distinct edges e 1 , e 2 . Note that both dim(e 1 ) and dim(e 2 ) are different from b. By Proposition 1 there must be a dimension d ∈ [n]\{b} such that |M d j ∩{e 1 , e 2 }| = 1 for each j ∈ {L, R}. But then each M d j contains an edge of dimension distinct from b, which by Proposition 2 (i) means that b cannot be the main dimension of M d j , contrary to the conclusion of the previous paragraph. ✷ 5 Admissible configurations A nonempty matching M is called an almost-layer (of dimension d) in Q n if there exist vertices u, v ∈ Q d L of different parities such that M consists of all edges of dimension d except uu d and vv d . Pairs {u, v} and {u d , v d } are called the free pairs of M .

Proposition 3 A

 3 configuration (u, v, M ) is admissible if and only if the following holds (i) M contains no odd half-layer for u or v; and

  Hamiltonian path between u and v. Proof: Since M is an aligned matching, there exists d ∈ [n] such that |M d L | ≤ 1 and |M d R | ≤ 1. Without a loss of generality assume that u ∈ V (Q d L ) and consider the following two cases: Case

  Hamiltonian path between u and v unless M is an almost-layer in Q n with a free pair {u, v}. Proof: We argue by induction on n. Since the case n = 4 is settled by Lemma 14 in Appendix B, assume that n > 4. If M is aligned, the statement follows from Lemma 7. If M is unaligned, then by Lemma 5, there is d ∈ [n] such that M d i contains no half-layer in Q d i for both i ∈ {L, R}. Without a loss of generality assume that u ∈ V (Q d L ). To obtain the desired Hamiltonian path P uv of Q n -M , consider the following two cases: Case 1: v ∈ Q d R . Since M does not contain a half-layer, there is a vertex w ∈ V (Q d L ) such that p(u) = p(w) and ww d ∈ M .

Subcase 2 . 2 :

 22 AL(u, v, M d L , Q d L ) does not hold. First apply the induction hypothesis to obtain a Hamiltonian path P L uv of Q d L -M d L . Next, distinguish the following two possibilities. Subcase 2.2.1: {xx d , yy d } ∩ M = ∅ for some pair x, y of neighbors on P L uv . We claim that vertices x and y can be chosen so that AL(x d , y d , M d R , Q d R ) does not hold. To verify the claim, suppose, by way of contradiction, that M d R contains an almost-layer A in Q d R with a free pair {x d , y d }. Denote by S the set of vertices z of Q d L such that z d is incident with an edge of A. Then |S|

Fig. 3 :

 3 Fig. 3: An illustration for Lemma 10.

Fig. 10 :

 10 Fig. 10: All maximal matchings of G in Subcase 1.2.

  , we first consider the set M d and then the combination of sets M d L and M d R . The matchings M d , M d L and M d R in the following figures are represented by dashed lines, the edges of the graph G are bold, and the remaining edges are dotted.

Fig. 14 :

 14 Fig. 14: All maximal matchings of G in Subcase 2.2.

Case 3 :

 3 m(M ) = 2. Let k(M ) be the minimal distance of distinct edges of M of a same dimension, i. e., k(M ) = min{d(e 1 , e 2 ) | e 1 , e 2 ∈ M i for some i ∈ [4] and e 1 = e 2 }. We assume that M d contains edges at distance k(M ), otherwise choose d accordingly. For each k(M ) ∈ [3] we have M d in Figure 15. Subcase 3.1: k(M ) = 3. Thus M d is as in Figure 15(1). There are five maximal matchings of G depicted in Figure 16. Observe that neither M d L nor M d R is as in Figures 16(3)-(5) since k(M ) = 3. Moreover, M L d and M R d are not both as in Figure

Fig. 18 :

 18 Fig. 18: All maximal matchings of G in Subcase 3.3.

  Figures 6-8 by Lemma 12. Let d ∈ [4] be a dimension with the maximal number of edges from M , i. e., |M d | = m(M ). Now, as d is fixed, for the sake of simplicity, let us omit d in the notions of Q d L , Q d R , M d L , and M d R . Furthermore, for x ∈ V (Q R ) and y ∈ V (Q L ) let x L and y R denote their corresponding vertices in the opposite subcube, i. e., x L = x d and y R = y d . We say that vertices u and v are separated if u

Fig. 19 :

 19 Fig. 19: All bad configurations in QL or QR for each maximal unaligned matching M in Q4 with m(M ) = 3.

Fig. 20 :Fig. 21 :Fig. 22 :Fig. 23 : 4 Fig. 24 :

 20212223424 Fig. 20: All bad configurations in QL or QR for each maximal unaligned matching M in Q4 with m(M ) = 4.

  exactly of all edges of dimension d and parity p for some d ∈ [n] and p ∈ {0, 1}. Observe that each layer is partitioned into two half-layers, each of size 2 n-2 . Moreover, if a perfect matching of Q n contains a half-layer, then it actually is a layer of Q n .

  does not hold. As in Subcase 2.1, it remains to apply the induction to obtain a Hamiltonian path P x d y d of Q d R -M d R and put P uv := P ux + P x d y d + P yv , where P ux and P yv are the subpaths of P L uv satisfying P L uv = P ux + P yv . Subcase 2.2.2: {xx d , yy d } ∩ M = ∅ for each pair x, y of neighbors on P L uv . By Lemma 5 there exists another splitting dimension d ′ = d and we claim that Subcase 2.2.2 for d ′ cannot occur. To verify the claim, first observe that

  are non-isomorphic. Define the mark of M to be the collection R M = {|M d |} d∈[n] . Clearly, matchings with different marks are not isomorphic. So we need to examine only matchings with different marks in Figures6-8. This can be easily verified by the reader. Since d(e 1 , e 2 ) is odd, d(e 3 , e 4 ) is odd, e 1 , e 2 , e 3 , e 4 are not in M ∪ {e},

✷

Lemma 13 Let (u, v, M ) be a maximal admissible configuration in Q n with an unaligned matching M . Then M is maximal with respect to inclusion.

Proof: Suppose on the contrary that M is not maximal, i. e., M ∪ {e} is a matching for some edge

e ∈ E(Q n ) \ M . Let d be the dimension of e. Since M is unaligned, we have |M d L | ≥ 2 or |M d R | ≥ 2,

so we may assume that M d L contains edges x 1 x 2 and x 3 x 4 . Let e i = x i x d i for i ∈ [4].

Acknowledgements

The authors are grateful to the anonymous referee whose constructive comments helped to improve the clarity of this paper.

† Partially supported by the Czech-Slovenian bilateral grant MEB 090805. Partially supported by the Czech Science Foundation Grant 201/08/P298. § The work of this author was partially supported by Slovenian ARRS Research Grant P1-0297. 1365-8050

Case 3: Edges e 1 and e 2 are at distance 2. If e 1 = uv, apply Corollary 4 to find a Hamiltonian path between u and v that contains edge e 2 . If e 2 = uv, proceed similarly. Otherwise the configuration (u, v, {e 1 , e 2 }) is bad since it is of type (a), (b), or (c) in Figure 1. Thus the Hamiltonian path between u and v that avoids e 1 from Lemma 2 contains e 2 . This completes the analysis of all cases. ✷

The second lemma applies for example when M d R = {ab, cd} as in Figure 4 Lemma 12 Let M be a maximal unaligned matching in Q 4 . Then m(M ) ∈ {2, 3, 4} and M is isomorphic to one of the matchings in Figures 678.

Thus among eight vertices of observe in Figure 19(2)-( 5) that each bad configuration in Q L includes no vertex incident with M L . Thus both configurations (u, x, M L ) and (u, y, M L ) are good. Moreover, observe in Figure 19(1)-( 5) that for at most one z ∈

Therefore, there is a Hamiltonian path P uw of Q L -M L , and a Hamiltonian path

Subcase 2.2: Vertices u and v are both in Q L or both in Q R . We distinguish the following two possibilities.

2.2.1:

M is as in Figure 19(1) and both u and 23 that the statement of the lemma holds. Otherwise, by Lemma 11, there is a Hamiltonian path P uv of Q R + bc that contains the edge bc and avoids M R . Observe in Figure 19(1) that the configuration

Thus there is a Hamiltonian path

The desired Hamiltonian path of Q 4 -M is P ub + P b L c L + P cv where P ub and P cv are disjoint subpaths of P uv , assuming that b is closer to u on P uv than c.

2.2.2:

M is as in Figure 19(1) and both u and v are in Q L , or M is as in Figure 19(2)-( 5). We proceed similarly as in Subcase 1.2. Assume that u, v ∈ V (Q L ), otherwise interchange the roles of Q L and Q R . Let M L = {e 1 , e 2 }. By Lemma 10, there is a Hamiltonian path P uv that either contains precisely one of e 1 and e 2 , or avoids both e 1 , e 2 but contains an edge adjacent to both e 1 , e 2 . Let xy be that contained edge. Observe in Figure 19(1)-( 5) that there is no bad configuration (w, z, M R ) in Q R such that w L and z L are both incident with e 1 or e 2 . Thus the configuration

Hence there is a Hamiltonian path

The desired Hamiltonian path of Q 4 -M is P ux + P x R y R + P yv where P ux and P yv are disjoint subpaths of P uv , assuming that x is closer to u than y on the path P uv .

Case 3: m(M ) = 2. Applying Lemma 9 observe that Figure 24(1)-( 4) shows all bad configurations in Q L or Q R for each of the four maximal unaligned matchings M with m(M ) = 2 depicted in Figure 8, respectively.

Subcase 3.1: Vertices u and v are separated. Assume that u ∈ V (Q L ) and v ∈ V (Q R ). We distinguish the following three possibilities.

3.1.1: M is as in Figure 24(1) and u or v is incident with M d . Assume that u = a, the other case is symmetric. Observe in Figure 25 that the statement holds for each v ∈ V (Q R ) of different parity than u.

3.1.2: M is as in Figure 24(4) and {u, v} = {d, e}. Observe in Figure 26 that the statement holds.

3.1.3:

The remaining possibilities; that is, M is as in Figure 24(1) and none of u and v is incident with M d , or M is as in Figure 24(2)-( 4) and {u, v} = {d, e}. A vertex w ∈ V (Q L ) is free if it has a different parity than u and is not incident with M d .

We claim that there is a free vertex w ∈ V (Q L ) such that the configurations (u, w, M L ) and (v, w R , M R ) are good.

Suppose first that M is as in Figure 24(1)-( 3). Observe from the same figure that the configuration (u, x, M L ) is bad for at most one free vertex x. Similarly, the configuration (v, y R , M R ) is bad for at most one free vertex y. Since there are three free vertices, the claim holds in this case.

Suppose now that M is as in Figure 24 Observe in Figure 24(4) that the configurations (u, x, M L ) or (v, x R , M R ) are bad for at most three free vertices x, since {u, v} = {d, e}. Hence the claim holds in all cases.

Therefore, there is a Hamiltonian path P uw of Q L -M L , and a Hamiltonian path

Subcase 3.2: Vertices u and v are both in

We distinguish the following five possibilities.

3.2.1: M is as in Figure 24(1) and the configuration (u, v, M L ) is bad. We have three non-isomorphic cases: both, precisely one, or none of u and v is incident with M L . Observe in Figure 27 that the statement holds for each of these three possibilities.

3.2.2:

M is as in Figure 24(1) and the configuration (u, v, M L ) is good. We have two non-isomorphic cases: uv ∈ M L and uv / ∈ M L . Observe in Figure 28 that the statement holds for both of these cases.

3.2.3:

M is as in Figure 24(2) and {u, v} = {b, c} or {u, v} = {x 3 , x 4 }. Observe in Figure 29 that the statement holds.

3.2.4: M is as in Figure 24(2)-( 4), the configuration (u, v, M L ) is good, and {u, v} = {x 3 , x 4 }. Then there is a Hamiltonian path P uv of Q L -M L .

We claim that P uv contains an edge xy ∈ P uv such that xx R / ∈ M d , yy R / ∈ M d , and the configuration

First, if M is as in Figure 24(3) or 24(4), put x = x 1 or x = x 2 , respectively, and choose y to be any neighbor of x on P uv . Observe in Figure 24

Thus the claim holds in this situation. Now M is as in Figure 24(2). Since {u, v} = {x 3 , x 4 }, we have x 3 / ∈ {u, v} or x 4 / ∈ {u, v}, say x 3 / ∈ {u, v}. Thus the Hamiltonian path P uv contains the edge x 3 x 4 . Put x = x 3 and y = x 4 and observe in Figure 24(2) that the claim is established.

Hence, by the claim, there is a Hamiltonian path

Finally, the desired Hamiltonian path of Q 4 -M is P ux + P x R y R + P yv where P ux and P yv are disjoint subpaths of P uv , assuming that x is closer to u than y on the path P uv .

3.2.5: The remaining possibility; that is, M is as in Figure 24(2)-( 4), the configuration (u, v, M L ) is bad, and {u, v} = {b, c}. Choose an edge xy ∈ M L such that the configurations (u, v, M L \ {xy}) and (x R , y R , M R ) are good. Observe in Figure 24 and Figure 1 that such an edge exists.

Thus there is a Hamiltonian path P x R y R of Q R -M R . Since the configuration (u, v, M L ) is bad but the configuration (u, v, M L \ {xy}) is good, there is a Hamiltonian path P uv that contains edge xy and avoids M L \ {xy}. The desired Hamiltonian path of Q 4 -M is P ux + P x R y R + P yv where P ux and P yv are disjoint subpaths of P uv , assuming that x is closer to u than y on the path P uv . This completes the proof of the lemma. ✷


Gilberto Echeverria

Séverin Lemaignan
email: slemaign@laas.fr

Arnaud Degroote

Simon Lacroix
email: slacroix@laas.fr

Michael Karg
email: kargm@in.tum.de§pierrick.koch@unicaen.fr

Pierrick Koch

Charles Lesire
email: charles.lesire@onera.fr

Serge Stinckwich
email: serge.stinckwich@ird.fr

Simulating complex robotic scenarios with MORSE

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Simulations are an essential component in robotics research, allowing the evaluation and validation of many sorts of developments before their integration on-board real robots. For such validations to be useful, the simulation must provide enough fidelity with respect to the real world, within the requirements of the considered robotics application. Creating a fully realistic simulation in every aspect remains nearly impossible and sometimes can also be seen as an inconvenience. Therefore numerous simulators are focused on a given specific aspect (e.g. terramechanics to study locomotion, contact forces to study manipulation, realistic photo-rendering to study vision algorithms, ...).

The MORSE simulator presented here is not targeted to the study of a specific domain of robotics, but is rather meant as a tool that can be used to test and evaluate integrated robot software, i.e. the suite of processes required to autonomously achieve complex missions. Using Blender to simulate photo-realistic 3D worlds and the associated physics engine, it brings enough realism to evaluate complete sets of software components within a wide range of application contexts.

The simulator is designed to be useful under varied environments, and provides features to adapt itself to existing robotic architectures, without imposing any changes on them to connect with MORSE. It has modular components that are versatile and configurable, to permit software-in-the-loop testing of robotics software. Input from several researchers has guided the evolution of this tool to satisfy the requirements of different labs, while keeping to its design principles. MORSE works on all major software platforms: win32, Linux and OS X. It is developed as an open-source project with a BSD 3-clause license. 6The outline of this paper is as follows: Section 2 reviews other comparable robotics simulators, and Section 3 introduces the main design principles of MORSE. Section 4 is the heart part of the article: it depicts the main features of MORSE, each being exemplified with the projects for which they were developed. Finally Section 5 gives the conclusion and future plans for the simulator.

Related Work

The Player/Stage/Gazebo [START_REF] Rusu | Extending Player/Stage/Gazebo towards cognitive robots acting in ubiquitous sensor-equipped environments[END_REF] is a well known robotics suite. It is a full set of tools that include the Player communication layer and two integrated simulators: Stage [START_REF] Gerkey | The Player/Stage Project: Tools for Multi-Robot and Distributed Sensor Systems[END_REF] is basically a 2D simulator optimized for navigation on flat and closed environments. One of its advantages is the capability to handle very large numbers of simplified robots [START_REF] Vaughan | Massively Multi-robot Simulation in Stage[END_REF]. However, it is not ideal for more complex scenarios, specially in 3D space. The more recent Gazebo [START_REF] Koenig | Design and Use Paradigms for Gazebo, An Open-Source Multi-Robot Simulator[END_REF] was developed to cover these shortcomings. It has received an important boost in its development with its integration into the ROS platform, and has thus become the most commonly used robotics simulator. It integrates very well with ROS and Player, but connectivity with other middlewares requires additional programming.

The Unified System for Automation and Robot Simulation (USARSim) [START_REF] Carpin | USARSim: a robot simulator for research and education[END_REF] shares many design concepts with MORSE. It was initially developed as a simu-lator for search and rescue operations, uses the Unreal Engine gaming platform and is built with the concept of modular components. It is widely used as an evaluation tool for the well known RoboCup competitions. However, it uses an adhoc interface to communicate with external software and does not support some of the most common robotics middlewares. The Unreal Development Kit (UDK) used is a closed-source library and is not available on every platform.

Webots [START_REF] Michel | Webots: Professional mobile robot simulation[END_REF] is a popular commercial simulator. It provides a full programming environment to create customized robots and environments, but the interface to construct new components and robots is unintuitive and complex, requiring searching trough data trees to adjust physical and geometrical parameters. It also has an integrated code editor, but the control programs created in it must later be converted and transferred to the final robot platform.

Another commercial simulator is V-REP [START_REF] Freese | Virtual robot experimentation platform v-rep: a versatile 3d robot simulator[END_REF], with a large variety of components and sensors available. It allows scripting of the components using the LUA language. Being modular, it allows for copy-and-paste functionality of the components. However, it provides no native method for communication with middlewares; such functionality must be provided by the user in the form of add-ons.

MORSE Architecture Overview

The Modular Open Robots Simulation Engine (MORSE) is a library of Python scripts that run on the Blender Game Engine (BGE) to interface a 3D virtual environment with external robotics software. Its main design principles have been described in [START_REF] Echeverria | Modular open robots simulation engine: Morse[END_REF], they are quickly recalled here.

The BGE is used as the base platform for the graphical display of the simulated world and the physics simulation, using the Bullet physics library. The simulation is organized as a main core of control functionality that initializes and coordinates the events in the BGE, and a collection of components that can be used to assemble a robot with sensors and actuators. A variety of communication tools allow each of the MORSE components to connect with external robotics software through middlewares. MORSE has support for some of the most commonly used robotics middlewares nowadays, including ROS [START_REF] Quigley | ROS: an open-source Robot Operating System[END_REF], Pocolibs [START_REF]Pocolibs: Posix communication library[END_REF] and YARP [START_REF] Metta | YARP: yet another robot platform[END_REF]. Other middlewares are regularly being added, mainly driven by the needs of new users. This process is simple, as existing middleware bindings can be used as templates for the new ones.

MORSE sensors and actuators are minimalistic in their functionality and completely middleware agnostic. They can provide similar data as their real world counterparts, but some of them have multiple variants that can work at different levels of realism and abstraction. The data employed by the components can be altered through the use of components called modifiers. These add noise or change the data as required to better match the data with real sensors/actuators (for instance, transforming the coordinate frame used by Blender into the Universal Transverse Mercator coordinate system, or adding noise to images captured by Blender cameras). When a simulation scene is created, the components are linked to middlewares as specified in a configuration script, and the necessary functionality is added to the components to be able to transmit/receive data through the middleware as data streams or synchronous/asynchronous requests. The whole data flow in MORSE can be seen in the diagram of Fig. 1.

Fig. 1: Overview of the data flow in MORSE, between the simulated world in Blender and the external robotics software MORSE can be easily extended by adding new components that inherit from the existing base classes. All components are programmed in Python, since this is the language that Blender uses for its scripts. However, when coding components that require a faster processing time, they can be implemented in C/C++ and interfaced with Python using Swig.

Morse Main Features

Blender Integration

Being based on the Blender 3D [START_REF]Blender 3D[END_REF] modeling software, any object, robot or environment can be created and immediately be made ready to use in MORSE. Many file formats for 3D models can be imported directly into Blender, further increasing the range of elements that can be used. The high level of graphical detail is specially useful for realistic looking simulations, and very important when doing image processing from simulated video cameras. It is convenient to have simulation environments recreating the terrain and buildings of real experimentation sites. Transforming the 2D map of a building into a 3D model is straightforward in Blender. However, outdoor terrains for experiments in field robotics are more difficult to create by hand. We have developed additional plug-ins for Blender that read Digital Elevation Map (DEM) files and create the appropriate 3D meshes. Adding normal maps and aerial photography for textures creates very realistic simulated environments. Figure 2 shows the modeling capabilities of Blender exploited in MORSE to create robots and environments from DEM data.

Component Library and Scene Construction

MORSE provides a collection of components that can be used to construct robots with various configurations. Sensors recover data from the simulated world and store it. This is done using the Blender predefined interfaces for the BGE and Python scripts. For example, GPS read the absolute coordinates of the sensor in the Blender world, laser scanners use ray tracing operations of z-buffers to generate range images and cameras use renders from the perspective of the Blender camera to produce images. Parameters that determine how the sensors gather data can be adjusted, such as range, resolution, image sizes, etc.

Actuators carry out actions within the simulated world. They provide motion to the robots through several methods and algorithms, or control moving parts such as robotic arms or pan-tilt units. In most cases, the motions are implemented using the functions in Blender to add a certain linear and angular speed to an object. Robotic arms consist of a series of articulated segments, and use the Blender armature system to determine the degrees of freedom at each joint. They can be operated either by direct control of the angles at each joint or by control of the end effector with Inverse Kinematics (using iTaSC [START_REF] Smits | iTASC: a tool for multi-sensor integration in robot manipulation[END_REF], a constraints-based IK solver available for the BGE).

Robots are the platform upon which all sensors and actuators must be mounted in order to function. They currently have no behavior of their own, but define the physical shape and properties like mass, friction and collision bounds used by the Bullet physics library to compute the interactions with the environment.

The component library also includes other objects that can be used in the simulation, from large outdoor environments, to furniture and small items. All of these can be imported from individual Blender files into a simulation scenario.

Building and configuration of scenarios are done with a set of Python classes provided by MORSE, known as the Builder API. The Builder API provides an internal domain-specific language (DSL) that completely hides the somewhat complex interface of Blender from the user, so that those unfamiliar with Blender can directly configure MORSE using Python scripts. Scripts can then be tracked on a version control system to follow changes and apply patches. The API offers classes to add robots, sensors and actuators, to position, rename and configure any of the parameters used by these components, to include additional objects (furniture, obstacles, etc.) and to add middleware bindings, modifiers and services for each component.

Adjustable Levels of Realism

Many components come in several versions, which produce more or less realistic behavior, and can be chosen depending on the objective of the simulation and processing that will be applied to the data.

Ground robots can consist of rigid bodies for chassis and wheels using physical constraints to give realistic movement based on the speeds of the wheels. Alternatively, some robots are handled as a single rigid box sliding over the ground when the details of the motion of the robot are not important. For aerial and submarine robots the physics are limited to collision detection, but they are not affected by gravity, and there is no simulation of air or wind currentsbut external dynamic models can be linked to MORSE for such purposes. The associated actuators offer the choice between controlling the speeds of wheels independently, controlling the motion of a robot as a whole with linear and angular velocities, giving direct waypoint coordinates for destination or "teleporting" a robot to a desired location.

Some sensors provide almost identical raw data as their real counterparts, which can then be processed to extract relevant information, and later used to make decisions. When the processing of data is not of interest to the experiment, alternative sensors can be used that provide higher level data, extracted directly from the BGE scenario, and avoid costly processing. The clearest example of this are the cameras: the regular video camera generates renders of the Blender scene, and outputs images to be processed by software. This generates much data, and can slow down the simulation when rendering for several cameras at once. A new sensor called the semantic camera uses Blender functions to determine the names and global 3D position of the objects within the view frustum of the camera. It directly outputs this data, making the simulation of object detection faster and avoiding the use of image processing algorithms.

As a practical example, researchers from ONERA use MORSE to evaluate online probabilistic decision-making on an autonomous UAV. In a first scenario [START_REF] Teichteil-Königsbuch | A Generic Framework for Anytime Execution-driven Planning in Robotics[END_REF], MDP-based policy optimization allows the UAV to find a suitable zone for an emergency landing. MORSE video camera sensors are used to feed the raw image data into the land mapping algorithm. On a second scenario [START_REF] Carvalho Chanel | POMDP-based online target detection and recognition for autonomous UAVs[END_REF], a POMDP model is used to optimize the probability to track and intercept an identified target among others. As the objective is to evaluate the optimized strategy, processing simulated images is not necessary. Hence, instead of using a video camera sensor, the semantic camera is used to identify the location of the target, adding some errors with modifiers to simulate both the sensor and the detection and identification processes.

Middleware Configurations

Research laboratories use different middlewares to connect the processes within their robots. In order to be usable with any architecture, MORSE enforces a clear separation between components and middlewares. When a simulation is started, the bindings between sensors/actuators and middlewares are read from the configuration script, and it is only then that components acquire the functions necessary to communicate with the outside world. This separation means that any middleware can be integrated with MORSE, by simply providing the scripts to marshal MORSE data in the expected format. Middlewares currently supported include ROS, MOOS, Pocolibs, YARP and raw TCP/IP sockets. Information exchange between the simulator and the robotics software can be done by a constant data stream, or via request/reply interfaces.

MORSE permits using different middlewares within a single simulation scenario with heterogeneous systems. This is exemplified in the Action project [START_REF] Boumghar | An information-driven navigation strategy for autonomous navigation in unknown environments[END_REF] developed by the LAAS and ONERA labs. It consists in the cooperation of ground and air robots to patrol a zone, locate and follow moving targets. Each lab provides an existing robotics platform with two different architectures: LAAS employs Segway RMP 400 land robots, using the G en oM [START_REF] Mallet | Recent developments of the GenoM robotic component generator[END_REF] architecture, while ONERA works with Yamaha R-Max helicopters based on OROCOS [START_REF] Bruyninckx | The Real-Time Motion Control Core of the Orocos Project[END_REF]. The simulation uses Pocolibs to communicate with G en oM , and YARP to talk with OROCOS.

MORSE has been chosen as the simulator platform for a French research robotic project called ANR-PROTEUS, thanks to its middlewares versatility and the facility to integrate it with existing architectures. The PROTEUS project supports a model-driven engineering approach based on a domain-specific language and a robotic ontology [START_REF] Dhouib | Control architecture concepts and properties of an ontology devoted to exchanges in mobile robotics[END_REF] and aims at providing a toolchain for robotic development from modeling to software simulation and deployment on real robots. PROTEUS is based on open-source softwares like the Eclipse Modeling Project, the ROS middleware and MORSE simulator. Several robot models are currently under construction (Wifibot, ECA Camelon, and Thales R-Trooper).

Component Overlays for Specific Software Architectures

Besides the components and middlewares available, it is further possible to adapt these elements to better fit an existing architecture and allow true software-inthe-loop functionality. MORSE components provide dedicated I/O interfaces. In many cases, the interface methods will not be the same as those used in an actual device, although the component has the same functionality. For instance, an actuator may have two separate functions to modify its linear and angular velocities, while the corresponding MORSE component uses only one function with the two parameters.

To avoid creating additional components, MORSE implements the notion of component overlays. Following the well-known adapter pattern, they are implemented as special components that override (or wrap) the default behavior to make it match a different architecture. In the case of middlewares, it is possible to either use the default serialization methods provided by MORSE, or write additional serialization functions as extra scripts, specific for single components. Overlays are implemented as Python scripts that provide an interface between the real component being simulated and the equivalent sensor available in MORSE. These features have been used to connect MORSE with an existing Unmanned Aerial Vehicle (AUV) control architecture [START_REF] Barbier | An Onboard Software Decisional Architecture for Rapid Environmental Assessment Missions[END_REF] without modifying the code in either the original architecture or MORSE.

Multi-node and Hybrid Simulation

The simulation of multiple robots in the complex environments permitted by MORSE is very demanding on computational and graphics resources. A scenario with several robots equipped with video cameras and other sensors, plus the robotics software all running on the same computer will slow down the system considerably. MORSE offers the possibility of running multiple instances of the same simulation scenario in separate computers, coordinated by a central server program, called the multi-node manager. This manager has been implemented using TCP/IP socket communication, and also using High Level Architecture (HLA) [START_REF] Kuhl | Creating computer simulation systems: an introduction to the high level architecture[END_REF] for more strict time management. While every node shows all of the robots, each node will only be in charge of controlling a limited number of them. The movements of robots and specific objects in one node are sent to the multinode manager, which in turn collects the updated positions across all nodes and redistributes the information, so that all nodes can immediately reflect the changes. The multi-node server also synchronizes the time and events across all nodes. This can be used to slow down the simulation in all nodes, by making them wait for the synchronization message. However, at the current time it is not possible to accelerate the simulation speed from the multi-node server.

This functionality was developed for applications that require a large amount of robots. Our use case is the rescue robotics project Rosace [START_REF] Lacouture | Rosace: Agent-based systems for dynamic task allocation in crisis management[END_REF]. Its main objective is the coordination of robotic agents in search and rescue operations in the case of a disaster. In this scenario, terrestrial robots must be able to locate human victims, provide support for the victims and avoid dangerous areas. The robots in the team are to be equipped with different payloads, and take autonomous decisions on which of them should perform different tasks in the mission, such as searching, providing a communications relay, and helping victims directly. For this project, two or three robots can be handled by a single simulation node, and synchronized with those in other nodes. Special sensors in MORSE are used to determine the distance and visibility between robots, and this information is used to simulate loss of connectivity between them. The victims to be saved are internally considered as robots with scripted behavior, so that their status and position is also synchronized by the multi-node manager.

Additionally, the multi-node system permits the deployment of hybrid simulations. A 3D environment that closely represents the real experimentation site is used. Real robots report their updated positions to the multi-node server, which reflects the changes on a dummy robot in the simulation, so that other simulated robots can see it and interact with it. In the Action project, a real ground robot moves around while the simulated helicopter can follow it using video cameras. The robots communicate in the same way in full simulation or in real life. The use of HLA makes it possible to synchronize the heterogeneous systems in both the simulated and the real world. Note however that the real robots are not able to "see" the simulated ones with their cameras -but this could be achieved using an augmented reality scheme that would modify the data gathered by the real robots.

The Human Avatar

For human-robot-interaction scenarios, we require a way to combine the reactive and sometimes unpredictable behavior of a human interacting with its environment with a simulated robot. Therefore the human avatar of the MORSE simulator has been equipped with an intuitive control that enables users to act upon the simulated environment. Inspired by modern 3D-computer games, the user takes a third-person perspective behind the human avatar to move around as shown in Fig. 3 (left). While moving around, the camera tries to avoid the objects and walls placed between the camera and the human avatar to prevent occlusions. All objects that can be interacted with can be displayed by pressing a key on the keyboard (also illustrated in Fig. 3). When the user decides to interact with an object, the camera switches to a first-person perspective and offers an interface showing possible actions the user can take when pointing to specific objects, as shown in Fig. 3 (right). Those actions at the moment include picking up and releasing objects, opening and closing drawers and cupboards and switching on and off specific objects like a light or an oven. The motions of the avatar are animated using Blender armatures, inverse kinematics, and predefined movement loops. The avatar can be controlled much like a character in a videogame, using either the mouse and keyboard or a combination of the Microsoft Kinect and the Nintendo Wiimote. This enables users to perform pick and place actions in simulated worlds while at the same time the simulated robot(s) can be controlled through the supported robotic middlewares.

The human avatar is meant to be used in personal robotics scenarios. In these, complex robots are expected to collaborate with humans to carry out ordinary household tasks, such as cleaning, serving food or aiding humans to navigate an environment. Robots used in these experiments are equipped with one or two arms, and are capable of grasping objects. They are also expected to react to the actions of their human collaborator, using video cameras, motion detectors or telemetry to determine the location, pose and attitude of the human. This can be done at two different levels of abstraction. Using the video cameras to recognize the human and its pose can be done realistically, with the associated computational cost and uncertainties. Alternatively, the avatar can directly export the position of all of its joints, and feed them back to the robot, simulating a full motion capture system and avoiding the processing costs.

An example use case in this scenario is the testing and validation of humanaware navigation planners of service robots in human-centered environments at TU Munich. In this case, a simulated human tracking system provides the human pose to the robot while the robot navigates in the environment in a way that is safe and legible for the human [START_REF] Kruse | Exploiting human cooperation in human-centered robot navigation[END_REF]. In this project, MORSE has not only been used as a powerful tool for testing human-aware navigation strategies before carrying out experiments with real humans: it has also been used to evaluate them as Lichtenthäler et al. show in [START_REF] Lichtenthaeler | Increasing Perceived Value Between Human and Robots -Measuring Legibility in Human Aware Navigation[END_REF] by video-based user studies. After successful testing and evaluation, the human-aware navigation was applied using real robots and humans resulting in a safe and reliable behavior of the robot.

Summary and Future Work

We have presented the main features developed within the MORSE simulator, following the requirements of a variety of projects in robotics research. The design and architecture of MORSE has proved to be flexible and powerful enough to allow researchers to use it under various circumstances to test their robotics algorithms. Users can customize the existing components according to their needs, or develop new ones when necessary, by describing their behavior in Python scripts. All new developments done on top of MORSE are made available to the whole community, thanks to the open source license of the simulator.

MORSE allows for quick integration with an existing architecture (multiple middlewares, modular components and component overlays), heterogeneous robots (mixing components and middlewares), multiple robot simulation (multinode synchronization) and human-robot interaction (high abstraction level sensors and human avatar).

Further work is planned to increase the usefulness of MORSE: for humanrobot-interaction experiments, it is ideal to have a deeper immersion when using the human avatar. A planned feature is to provide stereo images of the simulation to the user wearing special goggles. This can trivially be done from Blender, with some separation of the images produced for the two eyes. Increased integration with motion reading devices, such as Microsoft Kinect can also make the experience more natural, by allowing a finer control over the human avatar. Another planned work is to be able to couple MORSE simulations with other physical simulation engines thanks to the HLA support. Further development is also necessary to give users more control over the speed of the simulation, by adjusting the base execution frequency of the BGE.

Fig. 2 :

 2 Fig. 2: Left: Modeling of an R-Max robotic helicopter. Right: Robots on a terrain imported from a Digital Elevation Map; the view from a camera mounted on a helicopter robot is shown in the top right frame

Fig. 3 :

 3 Fig. 3: Left: third-person view of the human component that is used to navigate in the environment, displaying the names of objects that the human can interact with. Right: first-person perspective of the human avatar that indicates a possible "pick-up-action" with the bread.

User documentation and additional information are available at http://morse. openrobots.org, and the source code can be downloaded from http://github. com/laas/morse.git.

Acknowledgments This work has been partially supported by the DGA funded Action project (http://action.onera.fr), the STAE foundation Rosace project (http://www.fondation-stae.net) and the ANR-PROTEUS project (http: //anr-proteus.fr/)