Christian Glacet
email: christian.glacet@gmail.com

Nicolas Hanusse

David Ilcinkas

The impact of dynamic events on the number of errors in networks

Keywords: graph, network, dynamics, errors, routing information, distance changes

The impact of dynamic events on the number of errors in networks

Christian Glacet, Nicolas Hanusse, David Ilcinkas

Introduction

Everyone has already faced the problem of reaching a destination in an uncertain network. This is typically the case whenever one is in an unknown city, without a map, and aims at reaching, let us say, the closest cash machine. The only thing one can do is ask people in the street for some information on the direction. Unfortunately, there is no evidence that all the information one gets is reliable.

Nowadays, in a communication network, a corresponding situation can occur. Let us consider the routing task. Due to its dynamic (change of topology, time required to update local information) and its large-scale size, current networks are not immune to faults and crashes. It is no more realistic to blindly trust the data stored locally at each node. For instance, the Border Gate Protocol (BGP) used in Internet to route messages between autonomous systems implicitly assumes that some paths are known to reach any target. Ideally, these paths are as short as possible. Unfortunately, many messages do not reach their destination because no paths are temporally known although some paths could exist.

In the following, for a given target t, we informally refer to a liar as a node containing bad information about the location of t. A series of papers [START_REF] Hanusse | Searching with mobile agents in networks with liars[END_REF][START_REF] Hanusse | Memoryless search algorithms in a network with faulty advice[END_REF][START_REF] Hanusse | Locating a Target with an Agent Guided by Unreliable Local Advice[END_REF] tackles the problem of locating a target (node, resource, data, ...) in presence of liars.

A first model was introduced by Kranakis and Krizanc [START_REF] Kranakis | Searching with uncertainty[END_REF]. They designed algorithms for searching in distributed networks having the ring or the torus topology, when a node has a constant probability of being a liar. A more realistic model was proposed by Hanusse et al. [START_REF] Hanusse | Searching with mobile agents in networks with liars[END_REF]: the number of liars is a parameter k and during a routing query, the information stored at every node is unchanged.

The main performance measure is the number of edge traversals during a request. Several algorithms, either generic or dedicated to some topologies, and bounds are presented in [START_REF] Hanusse | Searching with mobile agents in networks with liars[END_REF][START_REF] Hanusse | Memoryless search algorithms in a network with faulty advice[END_REF][START_REF] Hanusse | Locating a Target with an Agent Guided by Unreliable Local Advice[END_REF] and are typically of the form O d + k O (1) (for path, grids, expanders, . . . ) or O k 3 log 3 n for bounded degree graphs, d being the distance between the source and the target.

In these papers, there is an implicit assumption: the number of liars is small. Our goal is to evaluate whether this is realistic or not. Starting from a network without any liar, we aim at estimating bounds on the number of liars obtained after few changes of topology. It turns out that this problem is related to the problem of estimating the number of distance changes after few edge/node deletions or insertions. We will show that the expected number of liars created by random nodes/edges removals is proportional to the diameter of the graph and its average degree. Sections 2 and 4 will respectively cover the related works and the presentation of our results, while sections 5, 6 and 7 will show the details of the proofs. Section 5 contains general results, Sections 6 and 7 respectively concern deletions and additions."

Related Works

The influence of topology changes in graphs has been studied in several works. In [START_REF] Chung | Diameter bounds for altered graphs[END_REF][START_REF] Schoone | Improved diameter bounds for altered graphs[END_REF], it has been proven that, in the worst case scenario, the deletion of M edges within a graph of diameter D induces a multiplication of the diameter by a factor O(M + 1). A lower bound of (M + 1)D -2M + 2 can be obtained, for odd D using the very simple example given in [START_REF] Chung | Diameter bounds for altered graphs[END_REF] Our work is also related to the computation of the most vital node of a shortest path [START_REF] Nardelli | Finding the most vital node of a shortest path[END_REF], that is the node whose removal results in the largest increase of the distance for a given pair of source/target, and the Vickrey pricing of edges [START_REF] Hershberger | Vickrey prices and shortest paths: What is an edge worth?[END_REF]. More precisely, the latter article shows a centralized algorithm that allows to find the most important node for a user that would like to send data over a given graph. This algorithm runs in time O(m + n log n) with a working memory of O(m).

Recently, some works on dynamic data structures for shortest paths/distance computation problems have been proposed. By dynamic, we mean that the data structures can tolerate some topology changes in a given network. A dynamic network model defines how the underlying graph changes/evolves over time.

More precisely, the following types of models are usually considered: or they give constant approximation [START_REF] Khanna | Approximate shortest paths avoiding a failed vertex: Optimal size data structures for unweighted graphs[END_REF][START_REF] Chechik | f-sensitivity distance oracles and routing schemes[END_REF]. The factor of approximation is:

(i) a stretch factor of the induced route in the case of routing approximations ; (ii) the ratio between the proposed distance over actual distance within the graph in the case of distance oracles. (s is a parameter of their oracle).

Throughout [START_REF] Chechik | f-sensitivity distance oracles and routing schemes[END_REF], all analyzes are made in the worst case, the one of a strong adversary that decides the worst forbidden set of nodes/edges, more generally, the worst possible dynamic scenario. This is sometimes a pessimistic vision of dynamics. For example if dynamics in a given network is resulting from material failures, then it is more likely that the adversary is making random choices.

Thus, as far as no attacks need to be modeled, it is interesting to have tools to analyze this kind of algorithm in the average case. This is why we study here a model of random failures: any sequence of M topological modifications has the same probability of occurrence. An estimation of the expected number of distance changes after M random modifications within a given network could be used for example to give update times of algorithms such as the one presented in [14, section 2.1]. In this work, King shows an algorithm that allows to maintain a shortest path tree up to date with a convergence time of O(D • κ)

with κ the number of distances to the root that have changed. The analysis we present here would allow to give the update time of King's algorithm within a random fault model.

Model

We consider a weighted and connected graph G = (V, E). We will use two different notions of distance, the classical one: d G (u, v), and the hop-distance which is equal to the minimum number of edges traversal that are required to

travel from u to v via a shortest path. The hop-distance is denoted hd G (u, v),
finally, the hop-diameter is equal to the maximal hop-distance over every pair of nodes.

Advice-Liar model

A particular node t of V is called destination, and every other node u ∈ V \{t} has an advice Adv(u) that points toward a neighbor node:

Adv(u) ∈ (Γ(u) ∪ {u})
with Γ(u) the set of neighbors of node u. If the node Adv(u) is on a shortest path from u to t then node u is said to be truthful, otherwise it is called a liar.

The set of all pieces of advice (a set of arcs)

A of cardinality n -1, called a configuration, induces an oriented sub-graph of G, noted G A = (V, A).
If the configuration of advice does not contain any liar, then it is said to be a truthful configuration. For any two nodes u and v in V , there exists an arc

(u, v) in G A ((u, v) ∈ A) if and only if Adv(u) = v. Whenever A is truthful, the graph G A is
a shortest path tree rooted at node t that covers V .

Dynamic Model

In this study, we will consider separately the case of deletions and additions. The number of edges, respectively nodes, added or deleted from G is M (respectively M'). We will consider that the number of deletions/additions is dominated by the number of elements in G, M = O(m) and M = O(n). Moreover, since the reasoning for nodes and edges cases are very similar we will only present the problem for edges in detail.

For a given graph G = (V, E), the set of graphs G - G,M is defined has the set of graphs that can be obtained after M edge deletions in graph G:

∀G -= (V, E -) : G -∈ G - G,M ⇐⇒ [(E -⊂ E) ∧ (|E -| = |E| -M)]
Similarly we define G + G,M to be the set of graphs that can be obtained after M edge additions:

∀G + = (V, E + ) : G + ∈ G + G,M ⇐⇒ [(E + ⊃ E) ∧ (|E + | = |E| + M)]
Given the graphs G, and G ∈ G - G,M ∪ G + G,M , together with a truthful configuration A, we define the following sets:

• S(G, G ) as the set of nodes whose distance to t is different in G and G .

This will be denoted S if there is no ambiguity;

• K(G , A) as the set of liars in G . This will be denoted K if there is no ambiguity. The size of this set will often be denoted k.

The purpose of this paper is to analyze these sets, and in particular their size.

Remark. It is possible that some pieces of advice from A had to be changed after edge deletions. Indeed, for two nodes u and v, if (u, v) ∈ A and edge {u, v} is deleted, then within G -node u has a piece of advice that points toward a non-neighbor node. Therefore, since we consider that every node has to point toward a neighbor in its current graph, then u will have to pick a new advice among its neighbors. This new choice will depend on the model of adversary we will consider (adversary models will be discussed next). Also, if its neighborhood is empty then its advice will be a self loop Adv(u) = u whatever the model is.

It is also possible that graph G -is disconnected. In this case, every node that does not belong to the same component as t is considered a liar. Adversary model.. We will study the number of liars and distance changes under two models of adversary:

• Strong adversary model. This adversary models the worst case scenario, which can be seen as an attack on the network by an omniscient entity.

For a given graph G = (V, E), the strong adversary coordinates the choice of a truthful set of advice A among all possible sets of advice, together with the choice of the M edges to remove from/add to G with the objective of maximizing the number of liars k(G -, A) (respectively k(G + , A)). This means that in the general case, many liars can appear after an attacker removes (adds) a single communication link. That is why the rest of the paper focuses on random deletions (additions), that can be seen as a model of failure, where the probability for any node or link to fail is the same.

Moreover, for any node

u ∈ V , if Adv(u) = v and {u, v} / ∈ E -,

Under the random adversary

We will first present an upper bound on the expected number of liars after M edge deletions, then we will show that this upper bound is tight for some family of graphs, even if the graph stays connected after the deletions. More generally we can compute the number of errors for certain graphs or family of graphs. If we look at the internet autonomous system network in 2007, which had, according to DIMES maps [START_REF] Shavitt | DIMES maps -as relationships[END_REF], 17144 nodes, 46621 links and diameter 8, the expected number of liars created for every falling link is about 2.95 ( 8 × 17 / 47 ). More generally, many natural and artificial complex networks have scale-free properties. These networks are often modeled by random graphs that have constant average degree and logarithmic diameter [START_REF] Lu | The diameter of random massive graphs[END_REF] while some of them even have a smaller diameter [START_REF] Cohen | Scale-free networks are ultrasmall[END_REF]. Thus, in most common scalefree networks [START_REF] Wang | Complex networks: small-world, scale-free and beyond[END_REF] (transportation, world-wide web, AS relationships, Math. coauthorship, . . . ) every random edge deletion creates Θ(log n) liars are created on average. Remark that the bounds from Theorem 4.2 and Theorem 4.3 are tight for M n 2 . Secondly, we have considered the case of random edge additions and actually found that considering a single edge addition can already have a huge impact on distances and information stored at nodes.

Theorem 4.4. There exists a family of n-node unweighted graphs in which the expected number of liars and distance change created by a single edge addition is Θ(n).

This looks as bad news, but liars created by edge addition(s) do not create any cycle of advice, but simply miss new shortcuts. This means that routing would still be guaranteed whereas in the case of edge or node deletions routing can be compromised.

First Observations

Useful tool

The estimation of the number of distance changes and the number of liars is correlated with the probability of disconnecting a given path within a graph as we will see later on. The following Lemma and Corollaries concern path disconnections and will be used to prove both the lower and the upper bounds given in Section 4.2.

M-1 i=0   m -i i-1 j=0 m -j - m -j   (1)
Proof. In the following, the event E i is "the i-th edge deletion is the first deletion that disconnects the path P ". Also, the event C i is "the i-th deleted edge belongs to P ". The probability p of disconnecting path P is equal to: Proof. From Lemma 5.1 this probability is equal to equation (1):

p = M i=1 Pr(E i ) = M i=1 Pr C 1 ∧ C 2 ∧ . . . ∧ C i-1 ∧ C i = M-1 i=0   m -i i-1 j=0 m -j - m -j   Corollary
M-1 i=0   m -i i-1 j=0 m -j - m -j   .
Since M Proof. From Lemma 5.1 and the inequality M m 2 we have:

p = M-1 i=0   m -i • i-1 j=0 1 - m -j   M-1 i=0   m • i-1 j=0 1 - 2 m   m • M-1 i=0 1 - 2 m i
since by hypothesis M m • c for some constant c > 0, we have:

p m • M-1 i=0 1 - 2 m m 2 •c
The function 1 -1

x

x is non-decreasing on the interval [2, +∞) and has a value of 1/4 for x = 2. Therefore, in this interval, for c = 1/4, we have (1 -1 x ) x c . In our case x actually belongs to the given interval since Before using these corollaries to analyze the number of errors we will characterize what makes truthful nodes turn into liars.

How truthful nodes turn into liars

First, notice that edge deletions do not necessary imply the creation of liars, even if these deletions have an impact on the distances in the graph. For example, in an unweighted complete graph with n > 2, no liar can be created by a single edge deletion (u, v):

• if v = t, then Adv(u) in G is v and the distance from u to v in G -is 2,
thus every neighbor is closer to v than u and is therefore a truthful advice for u in G -;

• if v = t, then Adv(u) = t in both graphs and u is not a liar.

Nevertheless there exists a relationship between distance changes and the creation of liars. To define this relationship, let us consider two graphs G = (V, E) and G -= (V, E -) ∈ G - G,M together with the truthful set of advice on G, A.

Lemma 5.2. If a node u ∈ V is a liar in G -∈ G - G,M
then either its advice points toward a node v whose distance to the destination has changed or its advice has been changed due to a deletion. More formally:

∀ (u, v) ∈ A : u is a liar within G -=⇒ (v ∈ S(G, G -)) ∨ ({u, v} / ∈ E -)
Proof. Consider two nodes u and v such that v / ∈ S(G, G -) and {u, v} ∈ E -.

From both hypotheses, we know that the distance from u to t is the same in both G and G -. Since the set A of advice is truthful in G, and because a distance cannot decrease from G to G -, the advice of u is still correct.

We are now ready to show the impact of random edge deletions on the number of liars.

Edge Deletions Under the Random Adversary

As Lemma 5.2 shows liars come either directly from the deletion of the edge leading to their advice or from distance changes. We will therefore start by analyzing the number of distance change created by M random edge deletions on a graph G with advice set A G . We will denote A the modified advice set on the resulting graph G -(recall that some illegal pieces of advice needed to be randomly redirected in this model).

Impact on the number of distance changes

Under the random adversary, for a given node, the probability of changing its distance after M edge deletions can be bounded using the upper bound on the probability of disconnecting a given path (Corollary 5.1): Lemma 6.1. For any graph G = (V, E), and any graph G -= (V, E -) chosen uniformly at random in G - G,M , with M m 2 , the probability that a node u ∈ V has a different distance in G and G -is bounded as follows: • M. Therefore we have:

Pr [u ∈ S] M • hd G (u, t) m Proof. Distances d G (u,
Pr [d G (u, t) = d G -(u, t)] M • hd G (u, t) m
The upper bound on the number of distance changes given by Theorem 4.2 can be derived from this Lemma, by bounding for every node u its distance to t in G by the hop-diameter D of G.

Proof of Theorem 4.2, the part on |S|. Let us denote by X u the random variable that has value 1 if u ∈ S and 0 otherwise. Since expectation is linear, the size of the set S satisfies:

E (|S|) = u∈V E (X u ) = u∈V Pr(u ∈ S)
Thus the expectation of the number of distance changes after M edge deletions is:

E (|S|) u∈V M • hd G (u, t) m M • nD m

Impact on the number of liars

The following Lemma can be deduced from Lemmas 6.1 and 5.2: Lemma 6.2. Any node u ∈ V is a liar in graph G -with a probability at most:

Pr [u ∈ K(G -, A)] hd G (u, t) • M m
Proof. From Lemmas 6.1 and 5.2 it can be deduced that, for a given node u ∈ V such that (u, v) ∈ A, the probability for a node u of being a liar can be bounded as follows:

Pr [u ∈ K(G -, A)] Pr [v ∈ S] + Pr [{u, v} / ∈ E -] hd G (v, t) • M m + M m (hd G (u, t) -1) • M m + M m
Finally:

Pr [u ∈ K(G -, A)] hd G (u, t) • M m
From this Lemma we can show the upper bound on the total number of liars,

given by Theorem 4.2.

Proof of Theorem 4.2, the part on K. Let us set X s to be the random variable that has value 1 if s is a liar in G -and 0 otherwise. From Lemma 6.2 we can deduce that the expected number of liars in G -is:

E (|K(G -, A)|) = E   s∈V \{t} X s   = s∈V \{t} E (X s ) = s∈V \{t} Pr [u ∈ K(G -, A)] s∈V \{t} hd G (s, t) • M m s∈V \{t} D • M m
This gives the following upper bound on the number of liars:

E (|K(G -, A)|) M • Dn m
and concludes the proof of the second part of Theorem 4.2.

Remark on the case of node deletions. The expected number of liars created by M node deletions can be analyzed in the exact same way. First it can be shown that the probability of disconnecting every shortest path from a node u to a node t is upper bounded by M • hd G (u,t) n . Then, from that, the bound on the number of distance changes M D can be obtained, which finally gives that the number of liars is also upper bounded by M D.

Lower Bound

This section handles the proof of Theorem 4.3, which states that the lower bound on the number of liars after M random edge deletions can be up to Ω(M • nD m ) for some family of small-diameter unweighted graphs that we will define right away and show on Figure 4.

Graph settings.. It is desirable to have a lower bound that is not based on graph disconnections. In order to guarantee that, in the random model, it is needed to use a M-connected graph, so that M deletions would never disconnect the graph. For that purpose we will use a gadget-graph parametrized by its diameter, δ, and its connectivity, κ. We denote this graph by P δ,κ . It is composed of κ paths of length δ where, for every i ∈ [1, δ], the i-th node of every path is connected to the (i + 1)-th node of every other paths. For every i ∈ [1, δ + 1] and every j ∈ [1, κ], we will denote the i-th node of the j-th path by u i,j . The Target location and advice set.. Since the graph H is symmetric, we can consider, without lost of generality, that the target node t is located within graph G . Since the original configuration has to be truthful, every node u that belongs to G has its advice pointing toward node a. Impact of M random edge deletions.. Let us now focus on the case where an edge is deleted in the path X that links node a and a , this case is depicted in

G x 1 a a b b t G u i+1,1 u i+2,1 x i+1 x i x D-1 P = P D,3

Edge Addition Under the Random Adversary

We will show in this section that with the random adversary model, the expected number of liars after one single edge addition is Ω(n) for some family Also, every node that belongs to graph G t is connected to a fourth node, named c. The graph H is then built by connecting node a (respectively a ) to node c by a path of length D + 3. Figure 6 shows the graph H with some indications on node positions that will be used and detailed right after.

Let us now observe the configuration of advices in H when the destination node t belongs to graph G t . Any node u that belongs to G has two possible ways for exiting graph G in order to get closer to t, either through node a or node b.

Conclusion

This study shows that, in the context of routing, links and routers failures usually creates very few errors. More precisely it shows that the number of errors grows linearly (at most) with the diameter. It is promising in the case of dynamic routing since most networks where routing protocols are used have very small diameter. This result could be used to design dynamic protocols that decide to update their routing tables based on the tradeoff between the cost of update and the cost of dealing with existing errors. Such a protocol could make these decision using an estimated number of errors giving (local) observations on the probability of failure. In this context it would also be interesting to have a better understanding of the appearance of liars. For example, it can be important to know that some deletions create no liar at all. This actually happens with a probability p 0 1 -n/m, which is the probability of deleting no advice (and therefore preserving all distances). Nevertheless it is not trivial to give a tight bound on this probability, since it is possible that no liars are created when deleting an advice. This question would allow to know the average number of liars created conditioned on the event of creating at least one liar, and this second expectation E (k | at least 1 liar) could be much larger than the overall expected number of liars for some graphs. We can, using p 0 , state that

E (k | at least 1 liar) E (k) • m n .
It could be interesting to give a non trivial upper bound on this last expectation but it is not clear if it would be possible. More generally, it could be interesting to have a distributed algorithm estimating the amount of liars to decide if an update mechanism should be executed.

and showed in Figure 1 .Figure 1 :

 11 Figure 1: Lower bound example on the impact of dynamics on the diameter from [4].

  The real challenge is to propose an algorithm that can tolerate an arbitrary number of failures. The most general known result is the M-sensitivity distance oracle proposed by Chechik et al. in [3]. This oracle uses a data structure of size O M • s • n 1+1/s log n and allows to approximate distances for every pair of nodes up to a multiplicative factor O(s • M), with a query time in O M log 2 n

1 AFigure 2 :

 12 Figure 2: An example of an edge deletion (edge {x, t}) that creates n -(D + 1) liars and distance changes.

Figure 3 :

 3 Figure 3: Example of a single edge addition (edge {x, t}) that creates n -D liars and distance changes.

Theorem 4 . 2 .

 42 For any weighted graph G = (V, E) of hop-diameter D with n nodes and m edges, for a randomly located target, after M m 2 random edge deletions, the expected number of liars is E (k) M • nD m . Moreover, the expected number of distance changes is also upper-bounded by M • nD m . Finally the number of liars and distance changes after M node deletions is at most M D. As we said before, this kind of upper bound allows one to know, for example, the average update time of King's algorithm, which would be O D 2 M • n / m after M random edge deletions and O D 2 M after M random node deletions.

Theorem 4 . 3 .

 43 For every unweighted M-edge-connected graph G = (V, E) of diameter D and such that M n 2 , there exists a unweighted M-edge-connected H of diameter D + Θ(1) with n = Θ(|V |) nodes, m = Θ(|E|) edges and having G as a sub-graph, in which the expected number of liars after M deletions under the random adversary model is Ω M • (n -M) D m .

Lemma 5 . 1 (

 51 Probability of disconnecting a given path). For any path P composed of edges, within a graph G = (V, E) such that |V | = n and |E| = m, the probability of disconnecting P by deleting M random edges from E is equal to 2 :

5 . 1 ( 2 m

 512 General upper bound). For any path P composed of edges, within a graph G = (V, E) such that |V | = n and |E| = m, the probability of disconnecting P by deleting M m 2 random edges from E is upper-bounded by • M.

m 2 , 2 mCorollary 5 . 2 (

 2252 we have m-i for any i ∈ [0, M -1]. The product from equation (1) is always smaller than 1, therefore we immediately obtain the upper bound 2 m • M. Tightness of the bound). For any path P composed of m 4 edges, within a graph G = (V, E) such that |V | = n and |E| = m, the probability of disconnecting P by deleting M m 2 random edges from E is in Θ m • M when m • M ∈ O(1).

c

  This implies that p is in Ω m • M . Combining this with Corollary 5.1, we obtain the claimed result.

  construction of the graph, H, used for the lower bound is based on two copies, G = (V, E) and G = (V , E ), of any M-edge-connected graph. Every node of graph G (respectively G ) is connected to two nodes a and b (respectively a and b ). Nodes a and a are linked by a path X = {x 0 = a, x 1 , . . . , x D-1 , x D = a } of length D. Also, node b and b are linked by a graph P = P D,M as follows: for every j ∈ [1, M], an edge is added between nodes b and u 1,j and between nodes b and u D+1,j . Finally every node x i from path X is connected to M nodes, and each of these node is connected, for every j ∈ [1, M], to node u i+1,j . If D denotes the diameter of G, then graph H has: • diameter D + Θ(1); • n = 2|V | + Θ(DM) nodes; • and m = 2|E| + 4|V | + Θ(DM 2 ) edges. However notice that, since G is M-connected, m nM and n (D -1)M, thus m (D -1)M 2 . Therefore, we have n = Θ(|V |) and m = Θ(|E|).

Figure 4 :

 4 Figure 4: Graph used in the lower bound in the case of edge deletions.

Figure 5 .Figure 5 :

 55 Figure 5. If one of these edges is deleted then a shortest path A, from a to t, has the form a x i u i+1,• b with {x i , x i+1 } being the first edge that has been deleted from X. Whereas a shortest path B, from b to t, has the form b u i+1,• b . Notice that such paths A and B always exist since the graph H is M-connected. Since d(b, u i+1,• ) = i + 1 and d(a, x i ) + d(x i , u i+1,• ) = i + 2, the path A is longer than the path B, therefore any node from G that is still connected to b is a liar since its advice point toward node a. If such an event occur, then the number of liars created is at least |V | -(M -1), that is in Ω(n -M) when M

Figure 6 :

 6 Figure 6: An Ω(n) lower bound for the edge addition.

  of graphs. In order to prove the lower bound, we consider a graph H with O(n) nodes and diameter O(D) whose construction is based on three copies of any given n-node graph of diameter D, namely G, G and G t . Every node from graph G (respectively G ) is connected to two new nodes a and b (respectively a and b).

  The distances d H (a, t) and d H (b, t) have the followng values in graph H:d H (a, t) = d H (a, c) + 1 = D + 4 d H (b, t) = 2 + d H (a , t) = 2 + d H (a, t) = D + 6 Since d H (a, t) < d H (b,t) the shortest path from any node of graph G to t in H goes through node a. Therefore every node from G will have its advice pointing toward node a. Let us now add an edge {x, y} to graph H and call this new graph H + . The edge {x, y} has one of its extremities in G with constant probability and the other extremity, y, belongs to G t also with constant probability. Some distances have been changed by this edge addition, in particular there is a shortcut b x y c t which implies that: d H + (b, t) = min(4, d H (b, t)) = min(4, D + 6) = 4 Thus d H + (b, t) < d H + (a, t) and therefore, for any node u that belongs to G, the shortest path to node t in the graph H + goes through node b. Every node from G is then turned into a liar by adding the edge {x, y}. These nodes represent a constant proportion of nodes in graph H. Therefore the expected number of liars for a single random edge addition is in Θ(n), which concludes the proof of Theorem 4.4.

  Consider the graph H -described in the deletion case. In this graph H -, every node v ∈ V is at distance D + 1 from t and has its shortest path to t going through path A. Therefore, every such node v has its advice pointing to the first node of path A, node a and every node from B has its advice pointing toward G (the sub-graph used to construct H -earlier). Let us now consider the graph H which is graph H -plus one edge connecting path B back to t, adding back the edge {x, t} (this graph is the same H as tho one from the deletion case). It has diameter D, the advice of every node v ∈ V is a lie since the path from v to t via path A is one unit longer than the one going through B. Moreover, every node from path B turned to a liar for the same reason. In other words every node except nodes from A turn into a liar.Therefore the number of liars in this graph can be up to n -|A| = n -D.

	4. Contributions
	4.1. Under the strong adversary
	Under the strong adversary model the number of liars created is very high
	even for one single edge or node deletion and without graph disconnection:
	Theorem 4.1. Under the strong adversary, for one node or edge deletion (or addi-
	tion), the numbers of liars and distance changes can be at least n -D -O(1) even
	if the graph remains connected.

then this adversary can redirect the advice of node u to any node in the neighborhood of u in E -. • Random adversary. This model can be used to analyze the expected number of errors created by a set of random faults that happened in the network. For a given graph G = (V, E) and a given target node t, the random adversary chooses uniformly at random a set of advice A among all possible truthful sets of advice. It also chooses uniformly at random a set of M distinct edges within E for deletions or within V 2 \ E for additions. In other words it chooses a graph G uniformly at random within G - G,M for deletions (within G + G,M for additions). Moreover, for any node u ∈ V , if Adv(u) = v and {u, v} / ∈ E -, then this adversary redirects the advice of node u to a node chose uniformly at random within the neighborhood of u in graph the G -. Since the proof of this theorem is quite simple and short we will use it as a warm-up. This can be useful to better understand the model of dynamics and what is measured. Proof. The proof is based on Figures 2 and 3 that show lower bounds for the deletion and addition cases respectively. The proof is split in two parts: Deletion case:. Take any unweighted graph G = (V, E), of diameter D, and connect every node of this graph to the extremities a and b of two paths that both end in a new node t, one path A of length D and the other, B, of length D -1. In this graph H, every node v ∈ V is at distance D from t and has its shortest path to t going through path B. Therefore, every such node v has its advice pointing to the first node of path B, node b. Let us now consider the graph H -which is graph H minus the closest edge from t on path B, edge {x, t}. This graph has diameter D + 1, the advice of every node v ∈ V is necessary a lie since it goes to a dead-end. Moreover, every node from path B, except x, turns into a liar. Therefore the number of liars in this graph is n -|A| -| {x} | = n -D -1).

Addition case:.

  t) and d G -(u, t) are different if and only if for every shortest path P = {u 0 = u, u 1 , ..., u = t} at least one edge {u i , u i+1 } does not belong to E -. The probability of this happening is upper-bounded by the probability of deleting at least one edge in any given shortest path from u to t. In particular, it is upper-bounded by the probability of deleting at least one edge in the shortest path with the minimum number of hops, which is, from Corollary 5.1, less than or equal to hd G(u,t)

	m

Notice that when i=0 the value of the product is equal to 1.

Partially supported by the ERCIM fellowship program.


Poincaré, Henri (1854-1912)French mathematician and scientist Scott A. Walter * Preliminary version of an article in Noretta Koertge (ed.), New Dictionary of Scientific Biography, Volume 6, pp. 121-125, New York, Charles Scribner's Sons, 2007. Poincaré, Jules Henri (b. Nancy, France, 29 April 1854;d. Paris, 17 July 1912), mathematics, celestial mechanics, theoretical physics, philosophy of science. For the original article on Poincaré by Jean Dieudonné see Volume 11.

Historical studies of Henri Poincaré's life and science turned a corner two years after the publication of Jean Dieudonné's original DSB article, when Poincaré's papers were microfilmed and made available to scholars. This and other primary sources engaged historical interest in Poincaré's approach to mathematics, his contributions to pure and applied physics, his philosophy, and his influence on scientific institutions and policy. The result of these new sources and updated historiography is a new Poincaré: if Poincaré's outstanding achievements in mathematics ensure his prominent position in the history of this subject, his corpus and intellectual legacy are known to extend well beyond mathematics proper, touching the core methods of theoretical physics, and central tenets of the philosophy of science. Increased recognition of the breadth of Poincaré's activity, from geodesy and electrical engineering to algebraic topology and the philosophy of space and time, is itself a prime result of Poincaré studies. A brief summary follows of the ways these studies have revised or enriched historical understanding of Poincaré's life and work.

Early Career

Consider, to begin with, Jean Dieudonné's evaluation of the young Poincaré's spotty education in higher mathematics, gleaned from Poincaré's published correspondence with Lazarus Fuchs and Felix Klein and since then confirmed, on one hand, by studies of Poincaré's qualitative theory of differential equations, and on the other hand, by analyses of the manuscripts submitted by Poincaré for the Grand prix des sciences mathématiques in 1880, and discovered by Jeremy Gray a century later. These manuscripts, written between 28 June and 20 December 1880, show in detail how Poincaré exploited a series of insights to arrive at his first major contribution to mathematics: the discovery of the automorphic functions of one complex variable (called "Fuchsian" and "Kleinian" functions by Poincaré). In particular, the manuscripts corroborate Poincaré's introspective account of this discovery (1908), in which the real key to his discovery is given to be the recognition that the transformations he had used to define Fuchsian functions are identical with those of non-Euclidean geometry.

The manuscripts of 1880 also shed light on the origins of Poincaré's conventionalist philosophy of geometry. Even at this early point in his career, Poincaré understands geometry to be the study of groups of transformations. Such a view recalls Klein's Erlangen program (1872), but where Klein's approach was projective and hierarchical, that employed by Poincaré in 1880 was entirely metrical, and free of hierarchy, rendering unlikely any direct influence of Klein's Program. The influence of Eugenio Beltrami, however, is apparent in Poincaré's disk model of hyperbolic geometry, a model he later employed in the service of his conventionalist philosophy of geometry.

Foundations of Geometry

Poincaré was elected to the geometry section of the Paris Academy of Sciences on 31 January 1887 (at age thirty-two), and that same year published his first paper on the foundations of geometry. Impressed with the writings of Sophus Lie and Hermann Helmholtz on the so-called Riemann-Helmholtz-Lie-Poincaré problem of space, Poincaré characterized plane geometries by considering intersections of a plane with a certain quadric, and formulating a common set of axioms. In this way, "straights" and "circumferences" of hyperbolic geometry are made to correspond, for example, to straights and circumferences (circles) of Euclidean geometry, and the available theorems depend on the chosen quadric. (He later popularized this insight in terms of a "translation dictionary" for Euclidean and non-Euclidean geometry). Extending his purview to the geometry of space, Poincaré held hyperbolic geometry and Euclidean geometry both to be adequate to the task of describing physical phenomena. Darwinian evolution had provided humans only with the general notion of a group; consequently, if humans regularly employed Euclidean geometry instead of hyperbolic geometry, this was by virtue of the simplicity and convenience of the former, the motion of solids corresponding roughly to the Euclidean group. Experience provided the "occasion" for this choice to be made, in that employment of Euclidean geometry was an outcome contingent upon the behavior of light rays and solids on Earth.

A few years later, Poincaré explained further that the choice of hyperbolic geometry entailed non-standard laws of physics, thereby rendering his view equivalent in essentials to that of Helmholtz (1876). For Poincaré, the empirical equivalence of the two possible points of view -Euclidean geometry plus ordinary physics, or hyperbolic geometry plus some unspecified, alternative physics -ruled out an empirical foundation of the geometry of physical space. He regretted that Helmholtz -the champion of methodological empiricism -had not made this point clear. Few scientists found compelling Poincaré's extreme view of the geometry of physical space, but philosophers (including Paul Natorp, Aloys Müller, Moritz Schlick, and Rudolf Carnap) were swayed by the clever arguments advanced in its favor, which shaped later debates on the conventionality of the spacetime metric in general relativity.

Poincaré's contributions to relativity theory have given rise to priority claims on his behalf, because he presented a theory mathematically indistinguishable from that of Albert Einstein, four weeks earlier than Einstein. In fact, Poincaré made a crucial step in 1900 toward Einstein's 1905 redefinition of physical time and space, when he realized that the validity of the principle of relativity for electromagnetic phenomena depended on a certain definition of the time coordinate in uniformly-moving systems (H.A. Lorentz's "local time"), realized by an exchange of light-signals between co-moving observers relatively at rest. Like Einstein, Poincaré elevated the principle of relativity to a postulate in 1905; unlike Einstein, he retained the notion of a luminiferous ether (thus obviating the need for Einstein's light postulate). In addition, he characterized the Lie-algebra of the Lorentz group, and derived the first two Lorentz-covariant laws of gravitation. Along the way, Poincaré provided the four-vectors for Hermann Minkowski's four-dimensional spacetime theory (1908), but deplored the latter's Einsteinian view of space and time coordinates, advocating in its place an interpretative convention equivalent to the postulation of Galilean spacetime.

In practice, Poincaré applied the principle of relativity as one prong of a twopronged method for the discovery of relativistic laws: whatever laws happen to describe the behavior of natural phenomena, these laws are required to be covariant with respect to a certain group of transformations. The first prong left him with an infinite number of candidate laws, all covariant with respect to the Lorentz group. The second prong placed a constraint on the search domain: for velocities that are small with respect to that of light, the relativistic law should correspond to that of classical physics. While Poincaré applied his covariance-pluscorrespondence method only to the case of Lorentz-covariant laws of gravitation, his approach is applicable to any group of transformations, and any principle of correspondence. Upon further formal elaborations from Minkowski and Arnold Sommerfeld, Poincaré's method became a touchstone of theoretical physics.

Work on Trajectories

Interest in Poincaré's innovative contributions to the theory of dynamical systems has expanded, with the rise of chaos theory in the 1970s, and the archival discovery of the first version of Poincaré's submission for the King Oscar II of Sweden competition to solve the n-body problem in celestial mechanics (1889). The published version of Poincaré's paper on the restricted three-body problem (1890) contains the first mathematical description of a chaotic trajectory in a dynamical system, or what Poincaré referred to as a doubly-asymptotic (and later, homoclinic) trajectory, but this extraordinary result is absent from the original, prize-winning version of the paper. In its place is a hastily-written corollary concerning unstable periodic solutions of differential equations, the flaw in which Poincaré discovered while preparing his manuscript for publication. In a moment of inattention Poincaré convinced himself of the convergence of the power series expansion of certain periodic solutions, which pointed to well-behaved asymptotic trajectories. In fact, the published version shows that the series in question belongs to the class of asymptotic series he had defined in 1886 (known later as a Poincaré expansion), and that in light of his recurrence theorem, the behavior of the corresponding trajectories becomes quite complicated (or in modern terms, chaotic). The significance of these doubly-asymptotic trajectories was not generally recognized at first, perhaps in part because Poincaré soft-pedaled his discovery, the child of an oversight in the original submission that was a huge embarrassment both for him, and for those who awarded him the prize (Karl Weierstrass, Charles Hermite, and Gösta Mittag-Leffler).

While the fate of doubly-asymptotic trajectories, neglected for decades, is extreme, relative neglect befell other results obtained by Poincaré in algebraic topology and mathematical physics. There were several reasons for this, including an allusive writing style, and a lack of follow-through. As his former student Émile Borel put it in 1909, Poincaré was "more a conqueror than a colonist". A selfmade mathematician in the French style, Poincaré took on no doctoral students, formed no school, and delivered lectures incomprehensible to all but a handful of auditors. With the aid of student note-takers, however, he published a complete series of lectures on mathematical physics and celestial mechanics, the technical sophistication and logical coherence of which were much admired; they effectively disseminated Poincaré's mathematical methods and problem-solving style.

Physics and Philosophy

Significantly for the historical development of electrodynamics, Poincaré's 1890 lectures on James Clerk Maxwell's theory of electromagnetism were the first to appear in German and the second to appear in French (other than translations of Maxwell's 1873 Treatise). Poincaré emphasized the Scottish physicist's abstract and powerful Lagrangian approach and proved his remark that if a phenomenon admits of one mechanical explanation, it admits of an infinity of such explanations. He also transformed Maxwell's single-fluid theory into a two-fluid theory, to the irritation of certain Maxwellians, and misrepresented its notions of charge and current. Nonetheless, his streamlined, inductive approach appealed to physicists in Britain as on the Continent, and furthered the cause of Maxwell's theory and British abstract dynamics.

For the general reader, Poincaré explained the cosmic consequences of his discoveries in the dynamics of systems, for the foundations of the second law of thermodynamics, the question of determinism, and the stability of the Solar system. Starting in the 1890s, Poincaré laid out in dozens of popular articles a coherent scientific worldview informed by contemporary research in mathematics and physics, and a familiarity with the writings of the leading physicist-philosophers: Maxwell, Helmholtz, Ernst Mach, and Heinrich Hertz. To Poincaré's surprise, his epistemological reflections were enrolled by Catholic intellectuals in an effort to undermine scientific authority. This placed him in the delicate position of having to explain the value of a science whose pretension to absolute truth he had systematically destroyed.

Technological advances issuing from fundamental discoveries in physics were readily apparent in Poincaré's time, some of which he celebrated (including wireless telegraphy, and the use of x-ray images in medical diagnostics). Nonetheless, he located the value of science not in its utility, or even in its power to relieve human suffering, but in its capacity to awaken the intellect: "to see," or at least, someday, "to let others see." The unity and progress of science were linked for Poincaré; the unity derived not from any shared method of investigation, a wholly illusory notion, but from the shared mathematical structures of the physical world. Progress, on the other hand, was realized by overcoming the obstacles inherent in the methodological disunity of science. In practice, overcoming such obstacles meant adopting the most general point of view possible of the problem at hand, an approach he employed regularly himself.

While scientific progress in Poincaré's sense is possible, it is by no means inevitable, nor does it lead to absolute truth in the long run. Objectivity itself is a social construct for Poincaré: without discourse, he wrote, there can be no objectivity. All science is not discourse, although some of Poincaré's contemporaries understood him to be a nominalist. Laws describing natural phenomena are elaborated pragmatically, in the sense that scientists' choices remain free, but are guided by experience. Mathematics is a science apart for Poincaré because the structure of the natural numbers is intuitively given (in a non-Kantian sense), while the natural sciences depend on a theory of measurement requiring the real numbers and arithmetical operations. Progress in mathematics is itself possible due to the principle of induction, which Poincaré understood to be a synthetic a priori judgment. Attempts to provide a logical foundation for mathematics by Bertrand Russell and Alfred North Whitehead were doomed to failure, Poincaré argued, because their constructions necessarily involved circular reasoning.

Reputation

The brilliance of Poincaré's contributions to mathematics, celestial mechanics, and mathematical physics was recognized by scientific academies across Europe and in the United States, most of which counted Poincaré as a foreign member by the end of the nineteenth century. The mathematical community was unanimous in its recognition of his accomplishments, the combined depth and breadth of which none could reasonably hope to emulate. This intellectual ascendancy had no counterpart in the French institutional domain, where Poincaré was visibly less skilled than some of his peers in securing his objectives. At the height of his scientific authority in 1907, he stood for the position of Perpetual Secretary for the Physical Sciences at the Paris Academy of Sciences, with the backing of members of the physics section. Faced with opposition from the chemistry and mineralogy sections, he withdrew his candidacy, in order to avoid the humiliation of a loss, or a narrow win. In return for his retreat, Poincaré's opponents endorsed his candidacy to join the Académie Française, where he was elected in 1908.

A second setback occurred in 1910. Following a highly-concerted campaign, Poincaré garnered a record number of nominations for the Nobel prize in physics, for the most part in view of his advances in partial differential equations of mathematical physics. Support for his candidacy issued largely from France and Italy, with the British holding back, partly out of concern over a second de facto extension of the prize domain, this time to cover work in mathematical physics, only one year after it had been awarded for applied physics (wireless telegraphy). In the end, the Royal Swedish Academy chose to recognize the work of another theorist, Johannes Diderik van der Waals.

While he did not win the Nobel prize, Poincaré cut an authoritative figure among physicists, even in areas of physics he had ignored, such as the theory of black-body radiation. In the fall of 1911, he took an active part in the First Solvay Council, dedicated to the discussion of problems in molecular and kinetic theory, along with twenty of Europe's leading experimental and theoretical physicists. A few weeks after the meeting, inspired by what he had learned, he proved the quantum hypothesis to be a sufficient and necessary condition for Planck's law.


Arthur Dufay

Pascal Lecocq

Romain Pacanowski

Jean-Eudes Marvie

Xavier Granier

Cache-friendly micro-jittered sampling

Figure 1: Rendering times comparison (left) on the path tracing-algorithm between a Cranley-Patterson de-correlation method as reference and our micro-jittering approach on the San-Miguel scene (10,495,880 tris, 3 bounces/path). Our method reduces substantially the rendering times for equal numbers of paths per pixel (right), while preserving the visual convergence of any low-discrepancy sequence (middle).

Motivation

Monte-Carlo integration techniques for global illumination are popular on GPUs thanks to their massive parallel architecture, but efficient implementation remains challenging. The use of randomly decorrelated low-discrepancy sequences in the path-tracing algorithm allows faster visual convergence. However, the parallel tracing of incoherent rays often results in poor memory cache utilization, reducing the ray bandwidth efficiency. Interleaved sampling [START_REF] Keller | Interleaved sampling[END_REF] partially solves this problem, by using a small set of distributions split in coherent ray-tracing passes, but the solution is prone to structured noise. On the other hand, ray-reordering methods [START_REF] Pharr | Rendering complex scenes with memory-coherent ray tracing[END_REF]] group stochastic rays into coherent ray packets but their implementation add an additional sorting cost on the GPU [Moon et al. 2010] [Garanzha and[START_REF] Garanzha | Fast ray sorting and breadth-first packet traversal for gpu ray tracing[END_REF].

We introduce a micro-jittering technique for faster multidimensional Monte-Carlo integration in ray-based rendering engines. Our method, improves ray coherency between GPU threads using a slightly altered low-discrepancy sequence rather than using ray-reordering methods. Compatible with any low-discrepancy sequence and independent of the importance sampling strategy, our method achieves comparable visual quality with classic decorrelation methods, like Cranley-Patterson rotation [START_REF] Kollig | Efficient multidimensional sampling[END_REF], while reducing rendering times in all scenarios.

Keywords: path-tracing, ray coherence, sampling, jittering Concepts: •Computing methodologies → Ray tracing; * Joint first authors.

† firstname.lastname@technicolor.com ‡ firstname.lastname@institutoptique.fr Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for thirdparty components of this work must be honored. For all other uses, contact the owner/author(s). c 2016 Copyright held by the owner/author(s). SIGGRAPH '16, July 24-28, 2016, Anaheim, CA, ISBN: 978-1-4503-4282-7/16/07 DOI: http://dx.doi.org/10.1145/2897839.2927392

Micro-jittered sampling

Our approach leverages the coherency naturally present in 3D scenes with constrained Cranley-Patterson rotation. Cranley-Patterson rotation de-correlates samples by adding a random offset in each dimension of a single random sequence. However, the parallel evaluation of the i-th ray sample within a block of threads often results in random access to 3D space region, causing memory cache misses.

Core idea. Because close pixels have higher probability to share the same visible surface characteristics, the parallel tracing of nearly similar rays on first bounces tends to follow similar paths in space, increasing thread data coherency. Based on this simple observation, our micro-jittering strategy consists in restricting Cranley-Patteron rotation to micro-jitters within a small volume of size µ using a signed random uniform distribution ξ. (eq.1).

yi = xi + µ (seq,N ) ξ, ξ ∈ [-0.5, 0.5) s (1)
To prevent the apparition of structured noise, or any bias, µ is adaptively chosen to ensure that the de-correlated sequences uniformly draw samples within the unit hypercube see Figure 2. This depends on a constant K representative of the star-discrepancy of the random sequence, and N , the sampling count.

µ (seq,N ) = KD * seq N -1/s (2)
As the result, each indexed sample in each de-correlated sequence orbits around its original position, increasing the probability to address the same region of space while preserving (mostly) the discrepancy property of the sequence.

Our method shares some similarities with the uniform jitter sampling method described by [START_REF] Ramamoorthi | A theory of monte carlo visibility sampling[END_REF]] and devised for area-light visibility computations. However our approach is somewhat different. We focus on performance rather than visibility and preserve the noise property by micro-jitter random sequences in a domain based on their discrepancy characteristics. Figure 2: Illustration of the micro-jittered approach: 128 samples (blue dots) of a two-dimensional Halton sequence (a) de-correlated by micro-jittering 1× (red dots) and 150× (c,d) within a small area of size µ. Setting µ too small may result in a bad coverage of the decorrelated integration domain (c). To prevent any bias or structured noise, we adaptively choose µ according to the sampling count and the star-discrepency of the sequence to evenly cover the domain.

Results

We implemented the micro-jittering approach in an in-house GPU path-tracer and in a modified version of Blender Cycles (GPU and CPU). We compared our approach against Cranley-Patterson rotation method in terms of visual quality and rendering performances.

Comparisons were done on 3D scenes of various complexity, several low-discrepancy sequences and different sampling count. In all scenarios, our method delivers superior rendering performances while providing comparable visual quality. As the sampling rate increases, our method perform faster, converging to coherent pathtracing performances without its inherent flaw. In some scenarios, our method can achieve speed-up factors up to 2×. We also successfully applied our method to screen-space rendering techniques. In a ray-marched SSAO implementation, our micro-jittering approach also improves rendering times without altering the visual quality.

Our method is simple, easy to implement and can drastically reduce rendering times for high-demanding stochastic ray-tracing applications with random memory accesses.

Figure 3: Interior scene rendered with 10000 paths/pixel, 4 diffuse/glossy bounces and 24 transmissions bounces using a sobol sequence. The reference image was generated using a classic Cranley-Patterson de-correlation method. The image referenced as "ours" was generated using our micro-jittered sampling technique. Both rendering times are reported from a NVIDIA 980Ti GPU.

Acknowledgments

We would like to thank Gaël Sourimant for its implementation and experimentations of the micro-jittering method in a SSAO context. We also thank the anonymous reviewers for their valuable comments and feedback.

Scene credits: the San-Miguel scene in teaser-left was modeled by Guillermo M. Leal Llaguno. The London NH museum in middle was modeled by Alvaro Luna Bautista and Joel Andersdon. The interior 3D model from figure ?? is coming from the chocofur store (store.chocofur.com).


Stefano Mafrica

Alain Servel

Franck Ruffier

Optic-Flow Based Car-Like Robot Operating in a 5-Decade Light Level Range*

In this paper, we present (i) a novel bio-inspired 1-D OF sensor which is robust to high-dynamic-range lighting conditions and independent of the visual patterns encountered, and (ii) a low-cost car-like robot called BioCarBot, which estimates its velocity and steering angle by means of an Extended Kalman Filer (EKF) using only the OF measurements delivered by two downward-facing sensors of this kind. Indoor experiments were carried out, in which the robot was driven in the closed-loop mode, using a proportional integral (PI) controller based on the velocity and steering angle estimates. The results presented here show that our novel OF sensor can deliver a wide range of high-frequency (333 Hz) OF measurements (from 1 to 10 rad s ) with a relatively high resolution (up to 0.05 rad s ) in a 5-decade high-dynamic range of light levels. Neither the refresh rate nor the resolution of the OF sensors presented here depended on either the visual patterns or the lighting conditions, and could be theoretically set at whatever value required. o s ) with a relatively high resolution (up to 0.05 rad s ). It is also worth noting that (i) the refresh frequency of the LMS was constant and did not depend on either the band-pass filter or the visual patterns encountered, and (ii) the resolution was nearly constant and could be theoretically set at any value.

I. INTRODUCTION

The sensing techniques traditionally used for motion estimation in the fields of mobile robotics and automobile, such as wheel odometry, inertial measurement units (IMUs) and global navigation satellite systems (GNSSs), such as standard or differential GPSs, often suffer from drift, low resolution, high noise levels and limited applicability [START_REF] Panzieri | An outdoor navigation system using GPS and inertial platform[END_REF], [START_REF] Georgiev | Localisation methods for a mobile robot in urban environments[END_REF].

Several approaches based on visual odometry have therefore been recently developed, using standard cameras [START_REF] Chhaniyara | Optical Flow Algorithm for Velocity Estimation of Ground Vehicles: A Feasibility Study[END_REF], [START_REF] Killpack | Visual odometry and control for an omnidirectional mobile robot with a downward-facing camera[END_REF] and optical-mouse sensors [START_REF] Kim | Robust velocity estimation of an omnidirectional mobile robot using a polygonal array of optical mice[END_REF], [START_REF] Ross | Toward refocused optical mouse sensors for outdoor optical flow odometry[END_REF] as well as custom-made optic flow (OF) sensors [START_REF] Nagai | Noncontact position estimation device with optical sensor and laser sources for mobile robots traversing slippery terrains[END_REF], [START_REF] Yi | Afocal Optical Flow Sensor for Reducing Vertical Height Sensitivity in Indoor Robot Localization and Navigation[END_REF]. In particular, applications using downward-facing visual sensors have been widely used to estimate the velocity and the distance traveled, since the visual patterns and light conditions encountered are more uniform, and they make it possible to use visual sensors such as optical mice.

On the one hand, most of the solutions based on standard cameras, such as those presented in [START_REF] Chhaniyara | Optical Flow Algorithm for Velocity Estimation of Ground Vehicles: A Feasibility Study[END_REF], [START_REF] Killpack | Visual odometry and control for an omnidirectional mobile robot with a downward-facing camera[END_REF], have disadvantages such as failing to cope with high-dynamic-range lighting conditions and their low-frequency, high computationalcost image processing, which means that only a small range of low velocity measurements can often be obtained. These *This work was supported by CNRS Institutes (Life Science; Information and Engineering Science and Technology), Aix-Marseille University, ANRT (Association Nationale de la Recherche et de la Technologie), PSA Peugeot Citroën via the OpenLab agreement entitled "Automotive Motion Lab". 1 stefano.mafrica@mpsa.com; alain.servel@mpsa.com two issues can be improved by using high-dynamic-range (HDR), high-frequency cameras, but these solutions would require even larger computational resources and would be too expensive for most robotic and automotive applications.

On the other hand, solutions based on optical mice, such as those presented in [START_REF] Kim | Robust velocity estimation of an omnidirectional mobile robot using a polygonal array of optical mice[END_REF], [START_REF] Ross | Toward refocused optical mouse sensors for outdoor optical flow odometry[END_REF], are very cheap and deliver highfrequency measurements but have the main disadvantage of having to operate very close to the ground to be able to work properly, and are therefore unsuitable for uneven-terrain applications. In addition, these sensors are usually highly sensitive to the lighting conditions and like standard cameras, deliver measurements in a rather small velocity range.

Solutions based on custom laser or LED-lighted OF sensors, such as those presented in [START_REF] Nagai | Noncontact position estimation device with optical sensor and laser sources for mobile robots traversing slippery terrains[END_REF], [START_REF] Yi | Afocal Optical Flow Sensor for Reducing Vertical Height Sensitivity in Indoor Robot Localization and Navigation[END_REF], have been developed in order to reduce the sensitivity to height and improve the performances while traveling over terrains of various kinds, but no tests were run by these authors under various lighting conditions and under the robot's normal driving conditions.

Several versions of Local Motion Sensors (LMSs) providing alternative solutions to standard visual sensors have been developed at our laboratory [START_REF] Ruffier | Bio-inspired optical flow circuits for the visual guidance of micro air vehicles[END_REF]- [START_REF] Expert | Flying over uneven moving terrain based on optic-flow cues without any need for reference frames or accelerometers[END_REF] to obtain 1-D OF measurements in various velocity and luminosity ranges, using methods based on findings obtained on the fly's visual system [START_REF] Franceschini | Facets of vision[END_REF].

In this paper, we present (i) a novel bio-inspired OF sensor giving measurements which are robust to high-dynamicrange lighting conditions and do not depend on the visual patterns encountered, and (ii) a low-cost car-like robot called BioCarBot, which estimates its velocity and steering angle by means of an Extended Kalman Filer (EKF) using only the OF measurements delivered by two downward-facing sensors of this kind (see Fig. 1). To test the performances of the OF sensors and the method presented here for estimating the velocity and the steering angle, some indoor experiments were carried out, which consisted in driving the robot on circular trajectory in the closed-loop mode using a proportional integral (PI) controller based on the velocity and steering angle estimates obtained.

The results presented here show that our novel OF sensor is robust to high-dynamic-range lighting conditions (in a 5decade range with sharp changes of up to 2 decades within 0.5 s), delivering a wide range of high-frequency (333 Hz) OF measurements (from 1 to 10 rad s , i.e. 50 to 550 In Sec. II, we will first introduce the principles underlying an elementary LMS before describing the method and the hardware used to construct our novel OF sensor. In Sec. III, we will present the BioCarBot robot, the mathematical modeling used to estimate the robot's velocity and steering angle, and the estimation and control scheme implemented on the robot. In Sec. IV, we will present and discuss the results obtained in the indoor experiments performed. Some conclusions will be reached in the last section.

II. NEW IMPLEMENTATION OF THE LOCAL MOTION SENSOR

A. Principles Underlying a LMS

A defocused lens placed in front of 2 photoreceptors determines the interreceptor angle ∆ϕ between the 2 photoreceptors' axes and gives them a Gaussian angular sensitivity with an acceptance angle ∆ρ (Fig. 2(a)), on similar lines to what occurs in many insects' eyes [START_REF] Franceschini | Facets of vision[END_REF]. A visual contrast moving in front of the LMS will induce a time lag τ between the photoreceptors' output signals (Fig. 2(b)). After measuring this time lag, the optic flow can be computed as follows [START_REF] Ruffier | Bio-inspired optical flow circuits for the visual guidance of micro air vehicles[END_REF]:

ω(t) = ± ∆ϕ τ (t) , (1)
where the sign depends on the sensor's axis orientation and on which of the two signals is delayed. The acceptance angle ∆ρ, namely the full width at halfheight of the Gaussian curve, determines the cut-off frequency of the low-pass spatial filter.

B. New Method for Computing the OF

To compute the OF measurement ω, the time lag τ between 2 neighboring-pixels' output signals was estimated using a cross-correlation method inspired by the Reichardt-Hassenstein model [START_REF] Reichardt | Sensory Communication[END_REF]. First the 2 pixels' output signals (V P h1 , V P h2 ) were sampled and band-pass filtered (V P h1 , V P h2 ), and the following pseudo-algorithm was then applied (Fig. 2(c),(d)): 1) delay one of the 2 filtered signals by the time τ i ; 2) compute the Pearson correlation coefficients between the delayed (e.g. V P h1 (t -τ i )) and non-delayed signal (e.g. V P h2 (t)) in a fixed time window w P h ;

3) repeat step 1 and 2 for every τ i (i = 1, . . . , n) in a fixed time window w τ ; 4) set τ at a value equal to the time lag τ k giving the maximum cross-correlation coefficient, as long as this maximum is greater than a fixed value ρ thr ; 5) compute ω using the equation (1) (or set it at NaN if the maximum cross-correlation coefficient is less then ρ thr ). The threshold value of the cross-correlation coefficients ( thr ) directly determines the reliability and the robustness of the OF measurements: the higher thr is, the more reliable and robust the measurements will be, but in the presence of noise, the lower the refresh rate will be.

The time window of the signals (w P h ) determines the bandwidth of the OF measurements, as the time lag τ must be nearly constant during this time in order to obtain a strong correlation, whereas the number of samples (n) in the time window determines the reliability of the correlation coefficients: the smaller w P h is, the larger the bandwidth will be, and the higher n is, the higher the reliability will be.

The time window of the time lags (w τ ) determines the range of the OF measurements (ω min = ∆ϕ τm , ω max = ∆ϕ τ0 ), whereas the difference between two consecutive time lags (∆τ = τ i+1 -τ i ) determines the resolution of the OF measurements (∆ω = ω i+1 -ω i ). In order to obtain a constant resolution ∆ω, the time lags were chosen as follows:

τ i = ∆ϕ |ω * i | ,
where ω * i are the desired OF measurements, which are linearly separated by the required resolution ∆ω * . The signals can then be delayed by a time τ i elapsing between two sampling steps, by linearly interpolating the signals sampled.

C. Hardware Implementation

In this study, we used the auto-adaptive silicon retina presented in [START_REF] Mafrica | A bio-inspired analog silicon retina with michaelis-menten auto-adaptive pixels sensitive to small and large changes in light[END_REF] soldered onto a tiny printed circuit board (PCB) with an optical lens casing mounted onto it (Fig. 3).

The M 2 APix pixel, which stands for Michaelis-Menten Auto-Adaptive Pixel, can auto-adapt in a 7-decade range and responds appropriately to small contrasts, such as ±2%, as well as large changes in light, such as ±3 decades [START_REF] Mafrica | A bio-inspired analog silicon retina with michaelis-menten auto-adaptive pixels sensitive to small and large changes in light[END_REF]. , where τ k is the time lag giving the maximum cross-correlation, as long as this maximum is greater than thr (which is usually set at 0.99). The sign of ω depends on the sensor's axis orientation and on which signal is delayed. Fig. 3.

Picture of the auto-adaptive silicon retina comprising the 12 M 2 APix pixels [START_REF] Mafrica | A bio-inspired analog silicon retina with michaelis-menten auto-adaptive pixels sensitive to small and large changes in light[END_REF] soldered onto a tiny PCB and the optical lens casing mounted onto it.

In the chip used here, the analog low-pass filter had a cutoff frequency of 100 Hz (instead of 300 Hz used in [START_REF] Mafrica | A bio-inspired analog silicon retina with michaelis-menten auto-adaptive pixels sensitive to small and large changes in light[END_REF]), giving a minimum sampling frequency of 200 Hz in order to prevent the occurrence of aliasing.

The optical lens used here was taken from a Raspberry-Pi camera (focal length: 2 mm), while the lens casing was custom made using a 3D printer to precisely adjust the distance between the plane of the lens and that of the pixels during the calibration phase. The interreceptor angle ∆ϕ and the acceptance angle ∆ρ were measured at ∆ϕ ≈ ∆ρ ≈ 3.6 o , as occurs in some diurnal insects [START_REF] Land | Visual acuity in insects[END_REF], using a similar method to that presented in [START_REF] Expert | Outdoor field performances of insect-based visual motion sensors[END_REF].

III. BIOCARBOT: A BIO-INSPIRED VISUALLY-GUIDED CAR-LIKE ROBOT

A. The Robot

Figure 1 shows a picture of: the BioCarBot robot, one of the 2 LMSs used and the indoor testing environment equipped with a Vicon motion-capture system.

The main structure of the BioCarBot robot was based on the low-cost 2WD Racecar Kit provided by Minds-I Robotics. The kit was composed of a 1/10th-scale car body (419 × 203 × 114 mm), one Hitec HS-311 standard servo coupled to a steering hub, one 5000-rpm DC motor connected to a 300-A electronic speed controller (ESC), one 7.2-Volt 3000-mAh Ni-Cd rechargable battery, one mechanical slip differential and four 90mm-diameter crawler wheels. We replaced the 23500-rpm DC motor and the four 66mmdiameter wheels included in the original kit in order to provide the robot with a higher control resolution at low velocity and the ability to drive over uneven terrains.

The embedded electronics include one Nanowii board (Flyduino) featuring a ATmega32u4 16-MHz CPU microcontroller (Atmel) and a MPU-6050 inertial measurement unit (IMU) comprising a 3-axis gyroscope and a 3-axis accelerometer (InvenSense) and one Overo IronSTORM computer-on-module (COM) (Gumstix) featuring a 1-GHz CPU DM3730 processor (Texas Instruments) comprising an ARM Cortex-A8 architecture and a C64x digital signal processor (DSP).

Thanks to the modularity of the robot's structure, 2 identical LMSs (Fig. 3(b)) were attached to the robot's frame on both sides of its body, aligned with the rear wheel axis (Fig. 1(a)). To facilitate the sensors' installation, we used the same testing board which was used in the study presented in [START_REF] Mafrica | A bio-inspired analog silicon retina with michaelis-menten auto-adaptive pixels sensitive to small and large changes in light[END_REF] to connect the LMSs to the Nanowii board (Fig. 1(b)). An OSRAM BPX65 photodiode connected to an analog amplifier circuit was also included on the testing board next to the LMS in order to measure the effective illuminace of the scene scanned by the sensor.

To obtain the ground-truth values, the 3-D robot's pose ([X Y Z α β γ] T ) was measured by means of a Vicon motion-capture system [START_REF] Manecy | X4-MaG: A Low-Cost Open-Source Micro-Quadrotor and its Linux-Based Controller[END_REF] which detected the position of the infrared markers attached to the robot's frame (see Fig. 1(a),(c)).

B. Modeling

As the robot's velocity was relatively low and the robot did not have any suspension system, we focused here on the 2-D kinematic model for a car-like robot moving on a flat surface. Figure 4 shows the kinematic diagram of the BioCarBot with the 2 LMSs installed on both sides, as depicted in Fig. 1(a). Let us take the inertial frame < I > having the x and y axes lying on the local ground plane, with the robot's body frame < B > placed in the middle of the rear wheels' axis. Two LMSs were placed at x l = [x l y l z l ] T and x r = [x r y r z r ] T with respect to < B > (x l = x r = 0 mm, y l = -y r = 140 mm, z l = z r = 125 mm), respectively, facing downwards at a height of h l , h r , respectively, from the ground (h l = h r = h = 175 mm) (Fig. 1(a),4(a)). As the sensors' frames < l >, < r > were taken to be parallel to the body frame < B >, we can consider all the position and velocity vectors projected onto < B >.

The OF produced by the visual motion of the ground with respect to the sensor can be measured using the method presented in section II-B based on the no-skidding hypothesis, which guarantees that V x >> V y with any velocity vector V = [V x V y 0] T located near the line passing through the two rear wheel/ground contact points. Therefore, the OF measured between the i -1-th and i-th pixels of each LMS can be written as follows:

ω i = - V ix sin 2 ϕ i h , (2)
where

V i = [V ix V iy 0] T is the velocity vector of the intersection point x i = [x i y i z i ] T (y i ≈ 0, z i ≈ -h)
between the i-th pixel axis and the ground plane (Fig. 4(b)).

Since the two LMSs are fixed to the robot so that the rows of pixels are aligned with the x-axis of < B > (Fig. 4(a)), all the position vectors x i of each LMS have the same y coordinate, namely y l and y r on the left and right sides, respectively. Therefore, according to the Ackermann steering geometry [START_REF] De Luca | Feedback control of a nonholonomic car-like robot[END_REF], the following equations hold:

     V l ix = V l = V -y l Ω V r ix = V r = V -y r Ω Ω = tan φ L V , (3)
where L(= 255 mm) is the distance between the rear and front wheel axes (Fig. 1

where ϕ l m , ϕ r m are the orientation of the pixel's axis corresponding to the median OF values ω l m , ω r m , respectively. Lastly, the dynamics of V and φ, which mostly depend on the dynamics of the DC motor and the steering servo, respectively, were identified as two independent first-order systems using the Vicon's measurements:

ξ ≈ Aξ + Bu = f (ξ, u). ( 5
)
where

A = diag(a 1 , a 2 ), B = diag(b 1 , b 2 ).
Since the identified time constant describing the dynamics of V when it was decreasing was nearly twice as high as when it was increasing, the values of A and B were identified using only the slower time constants as follows:

a 1 = -b 1 = -2.15, a 2 = -b 2 = -4.87.
It is worth noting that the values of V and φ could be computed algebraically by inverting equation ( 4), however this estimation would not be accurate enough to perform a closed-loop control on V, φ due to the noise and the quantization of the OF measurements. We therefore estimated V, φ by means of an Extended Kalman Filter (EKF) based on equation ( 5) and (4), as described in the next subsection.

C. Estimation and Control

In order to obtain a robust continuous estimation of the robot's longitudinal velocity and steering angle (V, φ), an Extended Kalman Filter (EKF) based on a discrete approximation for the model presented in (5),(4) was implemented, taking the median value of the OF measurements (ω l m , ω r m ) to be actual measurements.

The first-order discrete approximation for the model presented in ( 5) was taken to be as follows:

     ξ k = f (ξ k-1 , u k-1 , w k-1 ) = = [f (ξ k-1 , u k-1 ) + w k-1 ]∆t + ξ k-1 ζ k = ĥ(ξ k , ν k ) = h(ξ k ) + ν k , (6)
where the index k denotes the k-th sampling period (i.e., t = k∆t); w, ν denote the model and the measurement noise, respectively, and they are assumed to be independent white noises and to have normal probability distributions, i.e. p(w) ∼ N (0, Q) and p(ν) ∼ N (0, R), where

Q = diag(σ 2 V , σ 2 φ ), R = diag(σ 2 l , σ 2
r ) are covariance matrices.1 At each sampling period, the steps involved in the EKF can be summarized as follows:

) ξ- k = f ( ξk-1 , u k-1 , 0) 2) P - k = F k P k-1 F T k + W k QW T k 3) K k = P - k H T k (H k P - k H T k + V k RV T k ) -1 4) ξk = ξ- k + K k (ζ k -ĥ( ξ- k , 0)) 5) P k = (I -K k H k )P -1 k where F = ∂ f ∂x = ∆tA + I, H = ∂ ĥ ∂x 2 , W = ∂ f ∂w = ∆tI, V = ∂ ĥ ∂ν = I
are Jacobian matrices; P, P -are the error covariance matrix and its "a priori" estimate, respectively; and I is the identity matrix.

The initial estimate ξ0 was set at zero, while the initial estimate P 0 was set at the identity matrix.

As we have no measurements of the real motor and steering control input u, we took it to be equal to the output of the controller, i.e. u k-1 = ξk-1 (see equation ( 7)).

When there were no measurements on at least one of the robot's sides, i.e. no ω l m or ω r m , the Kalman gain K k was set at zero, so that it was still possible to have an estimation of ξ k based on the "a priori" prediction ξk . In that case, a timeout was set at 0.5 s, after which the EKF was reinitialized and the robot was stopped.

The robot's longitudinal velocity and steering angle (ξ = [V, φ] T ) were controlled in closed loop using the estimated values ( ξ = [ V, φ] T ) by means of a proportional and integral (PI) controller, as shown in Fig. 5.

The output from the PI controller can be written as follows:

ξ = K P (ξ * -ξ) + K I (ξ * -ξ), (7)
where K P = diag(0.5, 0.4) and K I = diag(2.5, 2).

IV. EXPERIMENTAL RESULTS

Experiments were carried out indoors using various floor patterns and trajectories to test the performances of the OF sensors as well as the estimation and control method presented in the previous section.

(L -y l tan φ) sin 2 ϕ l m -(1 + tan 2 φ)y l V sin 2 ϕ l m (L -yr tan φ) sin 2 ϕ r m -(1 + tan 2 φ)yrV sin 2 ϕ r m
In what follows, the M 2 APix output signals were sampled at ∆t = 3 ms by the integrated ADC (see [START_REF] Mafrica | A bio-inspired analog silicon retina with michaelis-menten auto-adaptive pixels sensitive to small and large changes in light[END_REF] for details), acquired by the Nanowii board via SPI communication and transmitted to the computer-on-module (COM) via serial communication (see section III for details). The OF algorithm presented in Sec. II-B as well as the estimation and control scheme shown in Fig. 5 were run at the same rate on the COM. The Linux-based program running on the COM was entirely generated in the Matlab/Simulink environment using the RT-MaG toolbox [START_REF] Manecy | X4-MaG: A Low-Cost Open-Source Micro-Quadrotor and its Linux-Based Controller[END_REF], a custommade toolbox for real-time applications developed at our laboratory. The host-PC program which conveys the control set points V * , φ * to the robot (COM) and receives data from the robot (COM) and the Vicon system was also developed in the Matlab/Simulink environment using the RT-MaG toolbox.

To implement the OF algorithm, we set (see section II-B for details of the parameters):

• the threshold on the cross-correlation coefficients thr = 0.99; • the number of pixels signals samples n = 70, giving a signal time window for the cross-correlation computation w P h = n∆t = 0.21 s; • the number of time lags m = 30, because a larger number would cause saturation of the CPU load since the algorithm's implementation was not optimized. Depending on the velocity range required, the time lag window w τ ranged from 6.3 ms to 63 ms in order to obtain OF measurements ω i ranging from 1 rad s to 10 rad s and a resolution ∆ω * required ranging from 0.1 rad s to 0.3 rad s . The elements of the measurements covariance matrix (R) and the process covariance matrix (Q) of the EKF were set at about ( ∆ω * 2 ) 2 and 0.01 2 , respectively. 3The ground-truth values were computed from the Vicon measurements ([X Y Z α β γ] T ) as follows (see section III for details): • φ truth = arctan(L γ V truth ); • ω l i truth = (y l γ-V truth ) sin 2 ϕi h (same for ω r i truth using y r ).

• V truth = Ẋ2 + Ẏ 2 ;
Figure 6 shows the results obtained indoors when the robot was driven on the floor shown in Fig. 1(c) on a circular trajectory, keeping a constant steering angle while varying the velocity from 0.3 to 1.3 m s . The OF resolution ∆ω * required was set at 0.3 rad s . First it should be noted that although the error in the OF measurements increased slightly with the velocity and depended on whether the velocity was increasing or decreasing (Fig. 6(a),(c),(e),(f)), the overall error distribution was nearly Gaussian with a quasi-zero mean (Fig. 6(d),(g)).

The average standard deviation of the errors in the OF measurements was σl = 0.18 rad s , σr = 0.25 rad s , giving a standard deviation of the error in the OF median values σ l m = 0.15 rad s , σ r m = 0.22 rad s , which is about half of ∆ω * , as was to be expected.

Secondly, it is worth noting that the robot adopted the required velocity and steering angle, giving the precision of the estimates σ V = 0.03 m s , σ φ = 0.02 rad (Fig. 6(h),(i),(j)) and a maximum error in the position of about 30 cm after 3 laps (solid line in Fig. 6(b)). When the robot was driven in the open-loop mode, however, i.e. without applying the control scheme presented in Fig. 5, it started to drift at a very early stage, going off the carpet after 6 s (dotted line in Fig. 6(b)).

Figure 7 gives the results obtained indoors when the robot was driven on the floor shown in Fig. 1(c) on a circular trajectory, keeping a constant velocity and steering angle under dynamically changing lighting conditions. The OF resolution ∆ω * required was set at 0.1 rad s . First we varied the incoming sunlight by up to 2 decades, giving a maximum luminosity of about 7000 Lux (I ph ≈ 7 × 10 -5 A), by slowly closing the 8 blinds (from 0 to 40 s), and then we varied the artificial lighting by about 2 decades, both slowly and rapidly, by varying the neon ceiling lights and then switching them off (from 40 to 85 s). The robot was then driven for a while with only the Vicon cameras' LED lights switched on (from 85 to 119 s), corresponding to a luminosity of about 0.5 Lux (average I ph of about 5 × 10 -10 A), before switching the neon lights on again (Fig. 7(j)). The light levels tested therefore covered a 5-decade range (I ph from about 3 × 10 -10 to 7 × 10 -5 A).

The OF measurements did not depend on either the average light level or the changes in the light, except in the case of a few very large, sudden changes (e.g. those occurring at t ≈ 5, 85, 119 s). The overall error distribution was nearly Gaussian with a quasi-zero mean (Fig. 7(b),(c),(e),(f)), giving the average standard deviation of the errors in the OF measurements σl = 0.07 rad s , σr = 0.08 rad s and the standard deviation of the error in the OF median values σ l m = 0.06 rad s , σ r m = 0.06 rad s , which is about half of ∆ω * , as was to be expected.

The robot adopted the required velocity and steering angle, giving the estimate precision σ V = 0.008 m s , σ φ = 0.013 rad (Fig. 7(g),(h),(i)) and a maximum error in the position of about 20 cm after 6 laps (Fig. 7(k)).

V. CONCLUSION

The low-cost car-like robot called BioCarBot presented in this paper is able to estimate its velocity and steering angle by means of an Extended Kalman Filer (EKF), using only the OF measurements delivered by two novel downward-facing LMSs. These novel LMSs have the following advantages over those presented, for instance, in [START_REF] Sabiron | Low-speed optic-flow sensor onboard an unmanned helicopter flying outside over fields[END_REF], [START_REF] Expert | Flying over uneven moving terrain based on optic-flow cues without any need for reference frames or accelerometers[END_REF]:

• the OF measurements are robust to high-dynamic-range lighting conditions (in a 5-decade range with sharp changes of up to 2 decades within 0.5 s) and do not depend on the visual patterns encountered; • the refresh rate of the OF measurements is constant and relatively high (333 Hz), and does not depend on the bandwidth of the band-pass filter; • the resolution on the OF measurements is nearly constant and relatively high (up to 0.05 rad s ), and can be set at whatever value required;

• the OF measurement range is relatively wide (from 1 to 10 rad s , i.e. 50 to 550 o s ) and can also be adjusted as required.

Although we focused here only on the information provided by the LMSs, data provided by other sensors (such as wheel encoders, IMUs and GPSs) could be integrated in order to achieve greater robustness and eventually obtain a precise robot's positioning.

Outdoor tests involving various ground and lighting conditions and various trajectories are now under way.

Fig. 1 .

 1 Fig. 1. (a) Picture of the BioCarBot robot. (b) Picture of one of the 2 OF sensors used on the robot. (c) Picture of the indoor testing environment equipped with a Vicon motion-capture system.

Fig. 2 .

 2 Fig. 2. (a),(c) Principles underlying a 2-pixel LMS. The optic flow produced by a contrast moving in front of the LMS can be computed taking ω(t) = ∆ϕ τ (t) , where ∆ϕ is the interreceptor angle and τ is the time lag between the two photoreceptors' output signals [9]. (b),(d) Block diagram of the novel OF algorithm inspired by the Reichardt-Hassenstein model [14]. After band-pass filtering the photoreceptors' outputs, one of the two signals is delayed by a time τ i in a fixed time window and the Pearson cross-correlation coefficient i between the delayed and non-delayed signals is computed. The OF is then computed taking ω = ± ∆ϕ τ k

Fig. 4 .

 4 Fig. 4. (a) Kinematic diagram of the robot moving on a flat surface. (b) Kinematic diagram of one OF sensor.

  (a)), and Ω, V, φ are the robot's angular velocity, longitudinal velocity and steering angle, respectively (Fig.4(a)).By substituting the median value of the OF measurements of each LMS ω l m , ω r m into (2) and combining equations (2) and (3), we obtain the following equation relating the output ζ = [ω l m ω r m ] T to the state ξ = [V φ] T : y l tan φ)V sin 2 ϕ l m hL (L-yr tan φ)V sin 2 ϕ r m hL = h(ξ),

Fig. 5 .

 5 Fig. 5. Block diagram of the estimation and control scheme.

1

 1

Fig. 6 .

 6 Fig. 6. Results obtained indoors when the robot was driven on the floor shown in Fig. 1(c) on a circular trajectory, keeping a constant steering angle while varying the velocity from 0.3 to 1.3 m s . (a) Measurements (dots) and ground-truth values (solid lines) of the left OF: each color corresponds to the OF produced between 2 neighboring pixels. (b) Reference (dashed line) and ground-truth robot's trajectory in the closed-loop (solid line) and open-loop (dotted line) mode. (c) Difference between the measurements and the ground-truth values shown in Fig. 6(a). (d) Distribution of the errors shown in Fig. 6(c). (e) Median values (dots) and ground-truth values (solid lines) of the OF produced on the left (dark blue) and right (light blue) sides. Some measurements were missing on the right side between 33 and 34 s because the robot was driving along the border between the patterned and white areas (see Fig. 1(c)). (f) Difference between the median values and the ground-truth values shown in Fig. 6(e). (g) Distribution of the errors shown in Fig. 6(f). (h) EKF estimates (dots), ground-truth (solid lines) and reference values (dashed lines) of the robot's longitudinal velocity (dark green) and steering angle (light green). (i) Difference between the EKF estimates and the ground-truth values shown in Fig. 6(h). (j) Distribution of the errors shown in in Fig. 6(i).

Fig. 7 .

 7 Fig. 7. Results obtained indoors when the robot was driven on the floor shown in Fig. 1(c) on a circular trajectory, keeping a constant velocity and steering angle under dynamically changing lighting conditions. (a) Measurements (dots) and ground-truth values (solid lines) of the left OF: each color corresponds to the OF produced between 2 neighboring pixels. (b) Difference between the measurements and the ground-truth values shown in Fig. 7(a). (c) Distribution of the errors shown in Fig. 7(b). (d) Median values (dots) and ground-truth values (solid lines) of the OF produced on the left (dark blue) and right (light blue) sides. (e) Difference between the median values and the ground-truth values shown in Fig. 7(d). (f) Distribution of the errors shown in Fig. 7(e). (g) EKF estimates (dots), ground-truth (solid lines) and reference values (dashed lines) of the robot's longitudinal velocity (dark green) and steering angle (light green). (h) Difference between the EKF estimates and the ground-truth values shown in Fig. 7(g). (i) Distribution of the errors shown in Fig. 7(h). (j) Photo-current responses of the photodiode placed next to the LMSs on the left side. The current values were computed taking I P h = I dark (e 8.8V out -1), where I dark (≈ 0.1 nA) is the dark current and Vout is the amplifier's output voltage, and the light values in Lux were estimated using the current-to-illuminance curve given in the photodiode's datasheet. (k) Robot's reference (dashed line) and ground-truth (solid line) trajectories.

The hypothesis that the components of the model and the measurement noise had normal and uncorrelated distributions was adopted on the basis of what was observed statistically during several experimental tests with trajectories of various kinds (see section IV).

The values of R were sometimes adjusted after performing some calibration tests since the standard deviation of the LMS on the right side was always slightly larger than on the left, probably because the pixels' signals were more noisy.

ACKNOWLEDGMENTS

We are most grateful to M. Boyron and J. Diperi for their involvement in the electronic and mechanical design of the sensors and the robot. We also thank S. Viollet, A. Manecy and F. Colonnier for their helpful suggestions and comments during this study, E. Vanhoutte for the photographs, S. Allano and F. Guillemard for their assistance and J. Blanc for correcting and improving the English manuscript.