Serge Abiteboul
email: serge.abiteboul@inria.fremilien.antoine@inria.frjstoy@seas.upenn.edu

Émilien Antoine

Julia Stoyanovich

The WebdamLog System: Managing Distributed Knowledge on the Web *

Keywords: Datalog, Distributed, Declarative, Knowledge base

Ce papier traite de la gestion des bases de connaissances distribuées, dans des environnements où un grand nombres de pairs autonomes et hétérogènes collaborent pour réaliser des tâches. Les informations sont représentées par des faits et les tâches correspondent à des règles logiques. Nous utilisons le langage WebdamLog, une variante de datalog pour les données distribuées. Nous présentons l'implémentation d'un moteur WebdamLog et nous montrons son efficacité dans le cadre d'applications distribuées dans lesquels les pairs changent rapidement leurs base de connaissances. Notre implémentation s'appuie sur Bud pour l'évaluation standard de datalog. Le moteur WebdamLog étends Bud avec le support (1) de règles avec des prédicats non locaux dans le corps ; (2) de règles avec des variables pour les prédicats ou les noms des pairs ; (3) la gestion des délégations qui changent le programme des pairs distants.

Introduction

The need for a unified approach for the management of "distributed content" has been argued in a number of works such as P2P Content Warehouse [START_REF] Abiteboul | Managing an XML warehouse in a P2P context[END_REF], Dataspaces [START_REF] Franklin | From databases to dataspaces management[END_REF] and Data rings [START_REF] Abiteboul | The data ring: Community content sharing[END_REF]. Query and update facilities in a heterogeneous distributed environment consisting of autonomous peers form the backbone of such systems. Personal information management is often given as an important motivating example [START_REF] Franklin | From databases to dataspaces management[END_REF]. In [START_REF] Abiteboul | The data ring: Community content sharing[END_REF], we argued for the use of declarative languages to facilitate the adoption of our platform by non-technical users, for the purposes of data exchange.

In this work, we build on the insights of [START_REF] Abiteboul | The data ring: Community content sharing[END_REF] and [START_REF] Franklin | From databases to dataspaces management[END_REF] and propose to use WebdamLog [START_REF] Abiteboul | A rule-based language for Web data management[END_REF], a declarative high-level language in the style of datalog, to support the distribution of both data and knowledge (i.e., programs) over a network of heterogeneous peers.

Datalog, a prehistoric language by Web time, includes recursion, an essential aspect for managing graphs, notably the Web graph. In recent years, there has been renewed interest in applying languages in the datalog family for a range of applications, from program analysis, to security and privacy protocols, to natural language processing, to multi-player games. The arguments in favor of datalog-style languages are familiar ones: a declarative approach alleviates the conceptual complexity on the user, while at the same time allowing for powerful performance optimizations.

WebdamLog is a datalog-style language that emphasizes cooperation between distributed autonomous peers communicating in an asynchronous manner, and is well adapted to the evolution of the peers' knowledge over time. As we will see in Section 3, WebdamLog extends datalog in a number of ways, supporting updates [START_REF] Abiteboul | Datalog extensions for database queries and updates[END_REF][START_REF] Alvaro | Dedalus: Datalog in Time and Space[END_REF], distribution [START_REF] Abiteboul | The Active XML project: an overview[END_REF], negation [START_REF] Gelder | Negation as failure using tight derivations for general logic programs[END_REF], and, importantly, a novel feature called delegation [START_REF] Abiteboul | A rule-based language for Web data management[END_REF]. As a result, WebdamLog is neither as simple nor as beautiful as datalog. It is also more procedural, which is needed to capture real Web applications.

The rest of this paper is organized as follows. In Section 2, we illustrate the salient features of WebdamLog using an example motivated by personal information management. We give an overview of WebdamLog in Section 3, describe our implementation of the engine in Section 4, and present results of a preliminary experimental evaluation in Section 5. We conclude in Section 6.

Running example

Suppose that Alice and Bob are getting married, and their friends want to offer them an album of photos in which the bride and groom appear together. Such photos may be owned by friends and relatives of Alice and Bob. Owners of the photos may store them on a variety of services and devices, including, e.g., desktop computers, smartphones, Picasa, and Flickr.

Making a photo album for Alice and Bob involves the following steps: (1) Identify friends and relatives of Alice and Bob using Facebook and Google+; (2) Find out where they keep their photos and how to access these photos; (3) From among all photos, select those that feature both Alice and Bob, using, e.g., tags or face recognition software; (4) Ask Alice's friend Sue to verify that the gathered and filtered photos are appropriate for the photo album, which will be seen by the families of Alice and Bob on their wedding day; (5) Sue may realize that inappropriate photos of the couple come from Dave's Flickr stream, and may decide to exclude Dave from the set of sources.

As should be apparent from this example, a task of this kind would be much more manageable if it were executed automatically. Executing such a task involves a certain amount of reasoning on the part of the system, which can be encoded with declarative rules. For instance, the following rule computes the union of Alice's and Bob's Facebook contacts in relation source on Sue's peer:

[rule at sue] source@sue($name) :-friends@aliceFB($name) source@sue($name) :-friends@bobFB($name) using wrappers to Facebook for Alice and Bob.

For simplicity, we assume that a friend's name corresponds to the name of the peer that the particular friend uses as entry point to the system. This name is thus associated to a particular URL. We assume that, in particular, each peer keeps the localization data of the friend, e.g., where the friend keeps her photos. The following rule, at peer sue, delegates steps (2) and (3) to the peers corresponding to the friends of Alice and Bob:

[rule at sue] album@sue($photo,$name) :-source@sue($name), photoLocation@$name($peer), photos@$peer($photo), features@$peer($photo,alice), features@$peer($photo,bob)

The key feature of this rule is the use of the WebdamLog language to share the work. Let Dan be a friend, and so a possible source. Then Sue's peer will delegate the following rule to Dan's peer:

[rule at dan] album@sue($photo,dan) :-photoLocation@dan($peer), photos@$peer($photo), features@$peer($photo,alice), features@$peer($photo,bob) Now suppose that Dan uses both Picasa and Flickr. Then, Dan's peer will delegate to danPicasa, a wrapper for his Picasa account, the following rule (and a similar rule for Flick):

[rule at danPicasa] album@sue($photo,dan) :-photos@danPicasa($photo), features@danPicasa($photo,alice), features@danPicasa($photo,bob) Note how the tasks are automatically shared by many peers. Observe that when new friends of Alice or Bob are discovered (e.g., proposed by some known friends), Sue's album, which is defined intensionally, will be automatically updated. Observe also that, to simplify, we assume here that all peers use a similar organization (ontolog y). This constraint may easily be removed at the cost of slightly more complicated rules.

To allow for manual curation by Sue, it suffices to modify the definition of sources:

[rule at sue] source@sue($name) :-friends@aliceFB($name), not blocked@sue($name) source@sue($name) :-friends@bobFB($name), not blocked@sue($name) By inserting/removing facts in blocked@sue, Sue now controls who can participate. (A similar control can also be added at the photo level.) Observe that such updates result in modifying the programs running at the participating peers. The album evolves, controlled by Sue's updates as well as by the discovery of new friends of Alice or Bob, and of new sources of photos.We will use the example of this section throughout the paper to demonstrate the salient features of our approach.

Webdamlog Model

In this section, we briefly recall the semantics of WebdamLog from [START_REF] Abiteboul | A rule-based language for Web data management[END_REF]. We assume the existence of a countable set of data values (that includes a set of relation names and a set of peer names) and of a countable set of variables. Variables start with the symbol $, e.g. $x.

Here, $R, $R i are relation terms, $P, $P i are peer terms, $U, $U i are tuples of terms. We impose the safety condition that $R and $P must appear positively bound in the body and that each variable occurring in a negative literal must also appear positively bound in the body. We evaluate rules from left to right and require that any peer name $P i must be bound in a previous atom, i.e., we disallow broadcast.

Semantics Each peer p has a state consisting of some facts, some rules, and possibly of some rules that are delegated by other peers. Peers evolve by updating their base of facts, by sending facts to other peers, and by updating their delegations to other peers. So, both the set of facts and the set of delegated rules evolve over time. (To simplify, we assume that the set of rules specified locally is fixed.)

The semantics of a rule with head m@p(u) in a peer p ′ depends on the nature of the relation in its head: whether it is extensional (m@p in E) or intensional (m@p in I), and whether it is local (p=p ′ ) or not. We first consider rules in which all relations occurring in the body are local; we call such rules local rules. A subtlety lies in the use of variables for peer names. The nature of a rule may depend on the instantiation of these variables. For example, one instantiation of a particular rule may be local, whereas another may not be.

Local with local intensional head (datalog) These rules define local intensional predicates, as in classic datalog.

Local with local extensional head (local database updates) Facts derived by this kind of a rule are inserted into the local database. Note that, by default, like in Dedalus, facts are not persistent. To have them persist, we use rules of the form m@p(U ) :m@p(U ). Deletion can be captured by controlling the persistence of facts.

The two kinds of rules described above, containing only predicates of the local peer, are called fully local rules. These rules do not require network communication, and are not affected by problems due to asynchronicity of the network.

Local with non-local extensional head (messaging) Facts derived by rules of this kind are sent to other peers. For example, the rule:

[at mi] $m@$p($name, "Happybirthday! ′′ ) :today@mi($date), birthday@mi($name, $m, $p, $date) where mi stands for my iPhone, results in sending a Happy Birthday message to a contact on the day of his birthday. Observe that the name $p of the peer and the name $m of the message varies depending on the person.

Local with non-local intensional head (view delegation) Such a rule results in installing a view remotely. For instance, the rule [at mi] boyMeetsGirl@gossipsite($girl, $boy) :girls@mi($girl, $loc), boys@mi($boy, $loc) installs a join of two mi relations at gossipsite.

Non-local (general delegation) Consider the rule [at mi] boyMeetsGirl@gossipsite($girl, $boy) :girls@mi($girl, $loc), boys@ai($boy, $loc) where ai stands for Alice's iPhone. This results in installing, at gossipsite, a view t r@mi and a rule, defined as follows:

[at mi] t r@mi @ai($girl, $loc) :girls@mi($girl$loc)

[at ai] boyMeetsGirl@gossipsite($girl, $boy) :t r@mi @ai($girl, $loc), boys@ai($boy, $loc) Note that both rules are now local. Note also that, when girls@mi changes, this modifies the view at Alice's iPhone, possibly changing the semantics of boyMeetsGirl@gossipsite.

In [START_REF] Abiteboul | A rule-based language for Web data management[END_REF], we formally define the semantics of Webdamlog. We show that, unless all peers and programs are known in advance, delegation strictly increases the expressive power of the model. If they are known in advance, delegation does not bring any extra power. Of course, delegation is also useful in practice, because it enables obtaining logic (rules) from other sites, and deploying logic (rules) to other sites. Conditions for systems to converge are shown in [START_REF] Abiteboul | A rule-based language for Web data management[END_REF], and are extremely restrictive. Even in the absence of negation, a WebdamLog system will typically not converge because of asynchronicity.

The WebdamLog System

In this section, we describe the architecture of the WebdamLog system. We describe the implementation of the system, stressing the novel features compared to standard datalog engines.

System architecture

The WebdamLog language is motivated by previous works on the Web-damExchange system [START_REF] Abiteboul | A model for web information management with access control[END_REF]. There, we described a system we built that could automatically adapt to a variety of protocols and access methods found on the Web, notably for localizing data and for access control [START_REF] Antoine | Demo] Social Networking on top of the WebdamExchange System[END_REF]. In developing toy applications with [START_REF] Antoine | Demo] Social Networking on top of the WebdamExchange System[END_REF], we realized the need for a logic that could be used (i) to declaratively specify applications and (ii) to exchange application logic between peers. This motivated the introduction of WebdamLog, a language based on rules that can run locally and that can also be exchanged between peers.

Datalog evaluation has been intensively studied, and several open-source implementations are available. We chose not to implement yet another datalog engine, but instead to extend an existing one. We use the Bud [START_REF]Bloom programming language[END_REF] system because of its support for asynchronous communication, and because its scalability has been demonstrated in real-life scenarios such as Internet routing.

WebdamLog simulation in Bud The Bud system supports a powerful datalog-like language introduced in [START_REF] Peter | Consistency analysis in Bloom: a CALM and collected approach[END_REF]. Indeed, we see Bud (and use it) as a distributed datalog engine with updates and asynchronous communications.

A WebdamLog computation consists of a sequence of stages, with each stage involving a single peer. Each stage of a WebdamLog peer is in turn simulated by a three-step Bud computation, described next. Note that we use the word stage for WebdamLog and step for Bud. Step 1, inputs are collected from the external world, including input messages from other peers, clock interrupts and host language calls. Step 2, the time is frozen; the union of the local store and of the batch of events received since the last stage is taken as an extensional database, and the program is run to fixpoint. Step 3, outputs are obtained as side effects of the program, including output messages to other peers, updates to the local store, and host language callbacks.

Observe that the fixpoint computation is executed at Step 2. It is performed by a local datalog engine over a fixed set of extensional relations and a fixed set of rules with no deletion. Deletion messages may be produced at Step 3, along with updates to the set of rules (for different reasons that we will explain further), and so this occurs outside of the datalog fixpoint computation. Relations appearing in the rules are implemented as Bud collections. Bud distinguishes between three kinds of key-value sets: A table keeps a fact until an explicit delete order is received. We use tables to support WebdamLog extensional relations. A scratch is used for storing results of intermediate computation, and is emptied at the beginning of Step 1. We use scratch collections to implement WebdamLog intensional relations. A channel provides support for asynchronous communication. It records facts that have to be sent to other peers, and messages related to installing or removing delegations.

Since communication is asynchronous, there is no guarantee as to when a fact written to a channel will be received by a remote peer. This is a departure from "pure" WebdamLog that essentially captures asynchronicity by considering only that the peers are fired in an arbitrary order. It is shown in [START_REF] Abiteboul | A rule-based language for Web data management[END_REF] that communication delays can easily be captured in WebdamLog by introducing peers modeling the network. Also, in WebdamLog, facts in a peer are consumed by the engine at each firing of the peer. To make facts persistent, they have to be re-derived by the peer at each stage. This is captured in our implementation by assuming that rules re-derive extensional facts implicitly, unless a deletion message has been received. A subtlety is that deletions local to a peer are also sent to the local peer itself using a channel. For this reason, it is a bit tricky to guarantee that local deletion messages are received by the peer before the next stage is started.

Implementing WebdamLog rules We now describe how WebdamLog rules are implemented on top of Bud. We distinguish between 4 cases. As for the semantics of WebdamLog (see Section 3), whether a rule in a peer p is local (i.e., all relations occurring in rule body are p-relations) plays an important role. The last case focuses on the use of variables for relation and peer names. For the first 3 cases, we thus ignore such variables.

Basic case. This is the case with local rules with either an extensional relation or a local intensional relation in the head. Such WebdamLog rules are implemented by identical Bud rules. In the case of an extensional head, this takes care of messages for local updates and messages to other peers, and in the case of a local intensional head, of local deduction as in datalog.

Local with non-local intensional head. From an implementation viewpoint, this case is somewhat tricky. We illustrate it with an example. Consider an intensional relation s 0 @q defined in the distributed setting by the following two rules:

[at p1] s 0 @q(X,Y):r 1 @p 1 (X,Y)

[at p2] s 0 @q(X,Y):-r 1 @p 2 (X,Y)

Intuitively, the two rules specify a view relation s 0 @q at q that is the union of two relations r 1 @p 1 and r 1 @p 2 from peers p 1 and p 2 , respectively. However, Bud does not support views. A naive implementation would materialize relation s 0 at q, and would then have p 1 and p 2 send update messages to q. Now suppose that a tuple 0, 1 is in both r 1 @p 1 and r 1 @p 2 . Then it is correctly in s 0 @q. Now suppose that this tuple is deleted from r 1 @p 1 . Then a deletion message is sent to q, resulting in wrongly deleting the fact from s 0 @q.

The problem arises because the tuple 0, 1 originally had two reasons to be in s 0 , and only one of the reasons disappeared. To avoid this problem, we should record the provenance of the fact 0, 1 in s 0 @q. For now, we can implement the following Bud rules at p 1 , p 2 to fix the problem: [at p1] s 0p1 @q(X,Y):r 1 @p 1 (X,Y)

[at p2] s 0p2 @q(X,Y):r 1 @p 2 (X,Y) allowing to join these two relations locally with [at s] s 0 @q(X,Y):s 0p1 @q(X,Y) [at s] s 0 @q(X,Y):s 0p2 @q(X,Y) Note that relations s 0p1 and s 0p2 may be either intensional, in which case the view is computed on demand, or extensional, in which case the view is materialized.

Non-local rules. We now consider non-local rules with extensional head. (Non-local rules with intensional head are treated similarly.) An example of such a rule is:

[at p] r 0 @q(X 0 ):r 1 @q 1 (X 1 ),. . . ,r i @q i (X i ),. . . with q 1 = . . . = q i-1 = p, q i = q = p, and with each X j denoting a tuple of terms. If we consider atoms in the body from left to right, we can process at p the rule until we reach r i @q(X i ). Peer p does not know how to evaluate this atom, but it knows that the atom is in the realm of q. Therefore, p rewrites the rule into two rules, as per definition of delegation in WebdamLog:

[at p] mid@q(X mid ) :r 1 @p(X 1 ),. . . ,r i-1 @p(X i-1 ) [at q] r 0 @q(X 0 ) :mid@q(X mid ), r i @q(X i ),. . . where mid identifies the message, and notably encodes, (i) the identifier of the original rule, (ii) that the rule was delegated by p to q, and (iii) the split position in the original rule. The tuple X mid includes the variables that are needed for the evaluation of the second part of the rule, or for the head. Observe that the first rule (at p) is now local. If the second rule, installed at q, is also local, no further delegations are needed to complete the computation. Otherwise, a new rewriting happens, splitting the rule at q, delegating the second part of the rule as appropriate, and so on.

Observe that an evolution of the state of p may result in installing new rules at q, or in removing some delegations. Deletion of a delegation is captured by updating the predicate guarding the rule. Insertion of a new delegation modifies the program at q. Note that in Bud the program of a peer is fixed, and so adding and removing delegations is a novel feature in WebdamLog. Implementing this feature requires us to modify the Bud program during step 1 of the WebdamLog stage.

Finally, we consider relation and peer variables. In all cases presented so far, WebdamLog rules could be compiled statically into Bud rules. This is no longer possible in the final case. In particular, observe that, if the peer name in an atom in the body of a rule is a variable, then the system cannot tell before the variable is instantiated whether the rule is local or not. In general, we cannot compile a WebdamLog rule into Bud before all peer and relation variables are instantiated. This is considered in the fourth case.

Relation and peer variables. To illustrate this case, consider a rule of the form r 0 @p(X 0 ):r 1 @p($X), . . . ,$X@p(X i ),. . . , where r 0 @p is extensional and $X is a variable. This particular rule is relatively simple since, no matter how the variable is instantiated, the rule falls into what we called the basic case. However, it is not a Bud rule because of the variable relation name $X.

Recall that WebdamLog rules are evaluated from left to right, and a constraint is that each relation and peer variable must be bound in a previous atom. (This constraint is imposed by the language.) Therefore, when we reach the atom $X@p(X i ), the variable $X has been instantiated.

To evaluate this rule, we use two WebdamLog stages of the peer. In the first stage, we bind $X with values found by instantiating r 1 @p($X). Suppose that we find two values for $X, say t 1 and t 2 . We always wait for the next stage to introduce new rules (there are two new rules in this case). More precisely, new rules are introduced during step 1 of the WebdamLog computation at the next stage. In the example, the following rules are added to the Bud program at p: r 0 @p(X 0 ):-t1@p(X i ),. . . , r 0 @p(X 0 ):-t2@p(X i ),. . . , Even in the absence of delegation, having variable relation and peer names allows the Web-damLog engine to produce new rules at run time, possibly leading to the creation of new relations. This is a distinguishing feature of our approach, novel to WebdamLog and to our implementation.

This example uses a relation name variable. Peer name variables are treated similarly. Observe that having a peer name variable, and instantiating it to thousands of peer names, allows us to delegate a rule to thousands of peers. This makes distributing computation very easy from the point of view of the user, but also underscores the need for powerful security mechanisms. Developing such mechanisms is in our immediate plans for future work.

Experimental Evaluation

Our ongoing experimental evaluation aims to demonstrate that WebdamLog programs can be executed efficiently in a highly dynamic distributed setting. We present results demonstrating that rule rewriting and delegation can be implemented efficiently. Other experiments we performed are mentioned at the end of the section. Because of space limitations, they could not be detailed here. They are discussed in [START_REF]WebdamLog engine[END_REF].

The cost of delegation. In the following experiments, our emphasis is on measuring the Web-damLog overhead in dealing with delegations. Recall the steps performed by each peer at each WebdamLog stage, described in Section 4. We can break down each step into WebdamLog-specific and Bud-specific tasks as follows: in the first step(1) inputs are collected: (a)Bud reads the input from the network and populates its channels. (b)WebdamLog parses the input in channels and updates the dependency graph with new rules. This step is needed for semi-naive evaluation . Second step(2): (a) time is frozen WebdamLog and Bud invalidate the ∆ of each relation that needs to be re-evaluated during fixpoint. ∆ are used by the semi-naive evaluation algorithm to optimize its computation. Bud invalidates ∆ according to instance updates, while WebdamLog invalidates ∆ according to program updates. (b) Bud performs semi-naive fixpoint evaluation for all invalidated relations, taking the last ∆ for differentiation. Third step(3): Outputs are obtained (a) WebdamLog builds packets of rules and updates to send. (b) Bud sends packets.

We report the running time of WebdamLog as the sum of steps (1b) and (3a), and the running time of Bud as the sum of steps (1a), (2b) and (3b). We report the running time of step (1b) separately, since it involves both WebdamLog and Bud, and we refer to this step as mixed. All running times are expressed as % of the total running time. For each experiment, we show that the running time of WebdamLog-specific phases is reasonable compared to the over-all running time.

For the experiments, we use 3 different machines running (i) the Ruby 1.8.7 virtual machine, (ii) the Bud system, and (iii) the WebdamLog engine described in Section 4. The machines have the following configurations (1) Intel Core i5 M540 @2.53GHz CPU, 4GB RAM, running Ubuntu 12.04; (2) Intel Core 2 Duo U7600 @1.2GHz CPU, 2GB RAM, running Ubuntu 12.04; (3) Intel Xeon 5160 @ 3.00GHz CPU, 1GB RAM, running Mandriva 2010.0.

To ensure that the observed trends are not due to differences in hardware / OS between the peers, we execute each experiment using all possible assignments of peers to machines, for a total of 6 possible assignments. Further, to reduce variability due to noise, we execute each experiment 5 times per peer assignment. Therefore, we executed a total of 30 runs for each experiment. We observed that assignment of peers to machines did not significantly impact running times, and so we report an average measure for each peer.

For the experiments in this section, we use WebdamLog rules involving only extensional relations, both in the head and in the body. We also support rules with intensional relations in the head and in the body. But for such rules, an essential optimization consists in deriving only the relevant data and delegated rules. We intend to conduct experiments with such rules when our system supports optimizations in the style of Magic Set.

Non-local rules. In the first experiment, we evaluate the running time of a non-local rule with an extensional head. Rules of this kind involve delegation. The following rule computes the join of relations rel1@peer1 and rel2@peer2, and then installs the result, projected on the last column, in join@peer3:

[at peer1] join@peer3($Z) :-rel1@peer1($X,$Y), rel2@peer2($Y,$Z)

Relations rel1@peer1 and rel2@peer2 each contain 1000 tuples that are pairs of integers, with values drawn uniformly at random from the 1 to 100 range. In the next table, we report the total running time of the program at each peer, as well as the break-down of the time into Bud, WebdamLog, and mixed.

The portion of the over-all time spent on WebdamLog computation on peer1 is fairly high at 7.9%. However, this is because the total processing time at peer1 is low, and much of the processing is spent on rule rewriting, to delegate the join to peer2. The portion of the over-all time spent on WebdamLog computation on peer2 is lower, because this peer spends more time computing the join. Peer peer3 spends a significant portion of the time in the mixed step, because the bulk of this peer's work involves installing a new rule, to be populated by the result of the join. Relation and peer variables. In the second experiment, we evaluate the execution time of a WebdamLog program for the distributed computation of a union. The following rule uses relation and peer variables and executes at peer p:

[at p] union@p($X) :-peers@p($Y,$Z), $Y@$Z($X)
We assume that there exists an extensional relation peers@p, with each tuple corresponding to a valid combination of peer name and relation name. In our experiment, peers@p contains 12 tuples and 3 distinct peers, i.e., the rule computes the union of 12 relations, 4 per peer. Each relation participating in the union contains 500 tuples, each with a single integer column, and with values for the attribute drawn independently at random from the 1 to 100 range. We record the performance of p, where the union is computed, and of the other two peers, remote1 and remote2, that are sending their entire relations to p.

WebdamLog overhead peaks at around 13% on p, since this peer has to dynamically create and install 12 new rules. Nonetheless, this overhead is manageable. As expected, the running time on both remote peers is low, and the WebdamLog portion of the computation is insignificant.

This section was only meant as an illustration of the on-going experiments we are conducting. For instance, we are also performing the following experiments [START_REF]WebdamLog engine[END_REF]: (i) We compare the querying and maintenance costs of materialized views to that of delegation-supported views; and (ii) We evaluate the gains achieved by using provenance graphs to support deletions of facts and rules.

Conclusion

This paper presents an implementation of the WebdamLog language introduced in [START_REF] Abiteboul | A rule-based language for Web data management[END_REF]. We demonstrate the feasibility of an approach based on WebdamLog to support exchanges of data and rules between peers that evolve very rapidly in a distributed and dynamic environment. To benefit from previous datalog optimization and efficient network communication, we rely on Bud to support the basic functionality of distributed datalog. We show how to realize the higher level features of WebdamLog, notably delegation, on top of Bud, using logical rule rewriting.

The use of declarative languages, in particular datalog extensions, for distributed data management has been advocated in [START_REF] Abiteboul | The Active XML project: an overview[END_REF][START_REF] Abiteboul | The data ring: Community content sharing[END_REF][START_REF] Hellerstein | The declarative imperative[END_REF]. Several systems have been developed based on the declarative paradigm [START_REF] Grumbach | a rule-based language for distributed programming[END_REF][START_REF] Loo | Implementing declarative overlays[END_REF][START_REF] Loo | Declarative networking: language, execution and optimization[END_REF], with performance comparable to that of systems based on imperative languages. Our implementation uses the Bud system [START_REF]Bloom programming language[END_REF]. The language Dedalus [START_REF] Alvaro | Dedalus: Datalog in Time and Space[END_REF] has been proposed as a formal foundation for Bud. We prefer here to use the language WebdamLog, in particular because it features delegation.

In the future we expect to demonstrate the use of our system with a much larger number of peers. As our ongoing research, we are exploring how various datalog performance optimization techniques, such as query-subquery, may be extended and applied to our setting.

* This work has been partially funded by the European Research Council under the European Community's Seventh Framework Programme (FP7/2007-2013); ERC grantWebdam, agreement 226513. http://webdam.inria.fr/


Rayar Frédéric

RAMEL Jean Yves

Jimenes Rémi
email: remi.jimenes@gmail.com

Exploiting Document Image Analysis in the Humanities

Introduction

With the growing popularity of the Internet and web based technologies, digital libraries and archives are becoming increasingly interested in the mass digitization and transcription of ancient documents in order to render them available to a much wider class of users. The usefulness of transcribing the information they contain is well recognized. However, the software required to produce satisfactory automatic transcriptions is not currently available. Commercial Optical Character Recognition (OCR) systems are unsuited to deal with either the often impaired quality of ancient documents (worn by use, torn, stained, etc.) or the difficulties presented by non standard fonts.

This context provided the motivation to set up, in collaboration with the Centre d'Études Supérieures de la Renaissance (CESR ) of Tours [1], the Pattern Redundancy Analysis for Document Image Indexing and Transcription (PaRADIIT) research project [START_REF]PaRADIIT Project[END_REF]. Further details on this project can be found on the PaRADIIT website and in a previous publication [START_REF] Jean | Interactive Indexation and Transcription of Historical Printed Books[END_REF].

Content Extraction and Typographic Studies

With the experience acquired in the PaRADIIT project, it became clear to us that our layout analysis software could easily be used to extract graphical contents such as initial letters, portraits, ornamental bands, etc. The website set up by the Bibliothèques Virtuelles Humanistes (BVH) team of the CESR [4] provides an example of how the innovative technical tools developed by our team have been and continue to be used to answer the specific requirements of current research in the humanities; in this case, by supplying the means of extracting and indexing many different types of graphical contents found in ancient French books [START_REF]See, for example, the BVH portrait gallery[END_REF].

This work led us to think about developing indexing tools which could be applied to texts, and, more specifically, to letters. Our aim here was to extract data from Early Modern books in order to create new font packages that could be used to further research in the history of printing materials. Relevant criteria were determined with the help of works by typography historians such as H. D. L. Vervliet [6a], [6b]. Figure 1 shows an XML schema of these criteria. Following this specification step, a Font Creation Tool was embedded in one of the project's software programs. A screenshot of this tool is shown in Figure 2. Sampling of Early Modern fonts and character styles is currently underway at the CESR.

Figure 1. XML Schema of a Font Indexing Criteria Model

<?xml version="1.0" encoding="utf-16"?> <!--RETRO Model file--> <Model> <Metadata> <Book Author="" Title="" Place="" PrinterOrPublisher="" Date="" Format="" /> <Copy Library="" CallNumber="" Digitalization="" Copyright="" CataloguerName="" /> </Metadata> <Transcription Character="" Unicode="" /> <Image Filename="" Folder="" Page="" Resolution="" /> <Thumbnail Name= Width="" Height="" PositionX="" PositionY="" /> <Typography IsSmallCap=" Type="" Alphabet="" Family="" SubFamily="" BodyHeight=""

Thickness="" /> <Description References="" Engraver="" Comments="" /> </Model> From the outset, these new font packages appeared to us to offer various possibilities in terms of exploitation.

Our first idea, influenced by our OCR expertise, was to use them as input for Optical Font Recognition (OFR) systems, OCR mono font systems, or OCR loop systems incorporating knowledge exploitation, in order to significantly improve the quality of transcriptions made from ancient books.

A second possibility for exploitation was rapidly pinpointed in the digital humanities field. The identification of typographic materials clearly has potential for specialists researching various aspects of printing, notably its aesthetic (i.e. the thickness and shapes of printing types) and economic history. Our font indexing tools may also shed new light on the book trade during the Renaissance by furthering research on the circulation of printing tools and materials. Up until the mid 16 th century, printing types often passed from workshop to workshop, printers frequently selling or lending types to fellow printers. Afterwards, the printing materials trade came to be dominated by a small number of important type foundries based in Antwerp, Frankfurt and Paris. The identification of fonts used in the 17 th and 18 th centuries consequently promises to help establish the influence of each of these type foundries in Europe right up until the "graphic revolution" of the late 18 th century (initiated by Baskerville and pursued by Bodoni, Fournier, and then Didot).

Inventory work also prepares the ground for the encoding and displaying of special characters and eventually their integration in Unicode Standard and Private Use Areas. This kind of work is already being carried out in the framework of projects like the Medieval Unicode Font Initiative (MUFI) [START_REF] Mufi | [END_REF], focusing on medieval manuscripts, and appears to be providing stimulus in typography research [START_REF] André | The Cassetin Project Towards an Inventory of Ancient Types and the Related Standardised Encoding[END_REF], [START_REF]CESR BVH Exploratory Project[END_REF]. Discussions with experts in literary fields may well provide other ideas about exploitation potential. Pursuing the idea of enabling the results of our work to further research in the humanities, we started to think about developing an online platform. This platform would not only enable users to consult digitized ancient books, but also to access the layout analysis and text transcriptions of these books. Simple search options using words and expressions taken from existing transcriptions have already been implemented. These could be complemented by alternative methods of searching contents, such as word spotting [START_REF] Pratim | An efficient Coarse to Fine Indexing Technique for Fast Text Retrieval in Historical Documents[END_REF].

The Font Creation Tool presented above and others typography oriented tools, such as measurement of body height, could be embedded in this platform. The creation of an annotation environment, aimed at enabling experts to actively collaborate and participate in the creation and management of digital humanities resources, is currently being studied.

In order to make this platform as easy to use as possible, we have adopted a user friendly web interface, with classic online library functions. Figure 3. shows a screenshot of our Book Explorer prototype [START_REF]Online Historical Book Explorer prototype[END_REF].

Figure 2 .

 2 Figure 2. Screenshot of a Font Model Creation Tool

Figure 3 .

 3 Figure 3. Screenshot of our Online Book Explorer Prototype

Acknowledgments

The work presented here was supported by the Google Digital Humanities Research Awards received by the Computer Science Laboratory of Tours RFAI team (2010 2012).


Nicolas Perrin

Christian Ott

Johannes Englsberger

Olivier Stasse

Florent Lamiraux

Darwin G Caldwell

A Continuous Approach to Legged Locomotion Planning

Legged locomotion planning can often be reduced to the search of finite sequences of contacts between the robot and the ground. We address this problem, using an original, continuous approach. We first demonstrate how this intrinsically discrete problem can be made continuous, and then present two applications: an experiment of vision-based reactive footstep planning with the DLR-Biped robot, and a simulation of non-gaited locomotion planning with a hexapod robot.

Introduction

The general problem of locomotion planning for legged robots takes place in a stratified configuration space. When a contact with the ground is made or released, the system moves from a submanifold of the configuration space to another one, and the equations of motion change in a discrete manner. As pointed out in [Goodwine, 1997], this discontinuous nature is one of the most important characteristic of legged robots (and other "stratified systems").

In an attempt to solve the locomotion planning problem in a computationally efficient way, simplified models are often used, and they should also have a discontinuous nature, at least to some extent.

Completely continuous models have been used in previous work (see [START_REF] Yoshida | Planning 3D collision-free dynamic robotic motion through iterative reshaping[END_REF], [START_REF] Kanoun | Planning foot placements for a humanoid robot: A problem of inverse kinematics[END_REF], [START_REF] Dalibard | Small-space controllability of a walking humanoid robot[END_REF]), but they always fail to capture some important features of the legged robots, such as for example their ability to step over obstacles.

In [Goodwine, 1997], small-time local control-lability is obtained for some stratified systems thanks to an extension of the Chow-Rashevskii theorem ( [START_REF] Bullo | Geometric Control of Mechanical Systems[END_REF], [Sastry, 1999]). As a result, some classic algorithms such as [START_REF] Lafferriere | Motion planning for controllable systems without drift[END_REF]] can be applied to locomotion planning for legged robots (see also [START_REF] Harmati | Motion planning algorithms for stratified kinematic systems with application to hexapod robot[END_REF]), but it essentially consists of converting initial sliding motions into feasible walking motions. Again, this means that the stepping over abilities of the robot are not well captured. Continuous models are however interesting because they make possible the use of conventional and efficient motion planning algorithms that suppose smooth configuration spaces (e.g.

PRM [START_REF] Kavraki | Probabilistic roadmaps for path planning in highdimensional configuration spaces[END_REF], RRT [LaValle and Kuffner, 2000]).

Up to now, the state-of-the-art solution to obtain fast algorithms that take into account the discontinuous nature of the problem is to choose footsteps before computing motions. Depending on the context and on the robot, a heuristic is defined and used to search for finite sequences of footsteps. Once a sequence of footsteps has been constructed, the next phase is to find a feasible continuous motion of the robot that follows this sequence. This kind of approach amounts to dealing with the discrete and continuous natures of the problem separately. It has been used extensively for humanoid robot navigation plan-ning ( [START_REF] Kuffner | Footstep planning among obstacles for biped robots[END_REF], [START_REF] Bourgeot | Path-planning and tracking in a 3d complex environment for an anthropomorphic biped robot[END_REF], [START_REF] Chestnutt | Planning biped navigation strategies in complex environments[END_REF], [START_REF] Chestnutt | Footstep planning for the honda asimo humanoid[END_REF], [START_REF] Gutmann | Real-time path planning for humanoid robot navigation[END_REF]), for locomotion planning for a hexapod [START_REF] Hauser | Motion planning for a six-legged lunar robot[END_REF], or for more general multi-contact planning problems [START_REF] Bouyarmane | Multi-contact stances planning for multiple agents[END_REF] (in that case, instead of footsteps, sequences of stances are searched for). To search for finite sequences of footsteps, as conventional motion planning algorithms cannot be applied, graph search algorithms such as A* are used instead.

In this paper, we present an original approach that enables us to take into account the discrete aspects of the problem while doing the motion planning in a smooth configuration space. Our work shares similarities with [START_REF] Boissonnat | Motion planning of legged robots[END_REF] where a connection is established between the free space of a spider robot and the free space of a half-disk robot moving by translation and rotation amidst obstacles. In this latter work however, the goal was to solve exactly the motion planning problem for the spider. Our goal is different since we aim at efficiently using samplingbased motion planning algorithms through the definition of weak collision-freeness. Our work is also more general than [START_REF] Boissonnat | Motion planning of legged robots[END_REF].

In Section 2, we define the problem of "flea motion planning" and show an efficient algorithm which serves as an example to illustrate our approach. In Section 3, we demonstrate a general theorem that can be used to transform discrete motion planning problems into continuous ones. In Section 4 and Section 5, we apply this theorem to perform visionbased reactive footstep planning with the DLR-Biped robot, and give also a thorough description of our software architecture. The planning is done on a discretized heightmap of the environment. This implementation gives strong connections between our work and [START_REF] Eldershaw | Motion planning of legged vehicles in an unstructured environment[END_REF] where the complexity of the task of planning steps for a legged robot is also reduced by using first a continuous highlevel planner. The main advantage of our work over [START_REF] Eldershaw | Motion planning of legged vehicles in an unstructured environment[END_REF] is the theoretical soundness of our equivalence between the existence of highlevel and "foot-level" paths. In Section 6, we show that the same approach can be easily adapted to locomotion planning for a hexapod robot. Finally, in obstacle "shortcut jump"

Figure 1: The "flea motion planning problem". On the left: from a collision-free sequence of flea jumps to a continuous "weakly collision-free" path for the disk. On the right: converting a continuous weakly collision-free path of the disk into a sequence of flea jumps, using a greedy algorithm.

Section 7, we conclude and discuss about future work.

An efficient algorithm for flea motion planning

In this section we consider the simple example of flea motion planning, which has been introduced in [START_REF] Perrin | Real-time footstep planning for humanoid robots among 3d obstacles using a hybrid bounding box[END_REF] to illustrate the method used in [START_REF] Perrin | Weakly collisionfree paths for continuous humanoid footstep planning[END_REF] and [START_REF] Perrin | Real-time footstep planning for humanoid robots among 3d obstacles using a hybrid bounding box[END_REF] to convert footstep planning into classical continuous motion planning. The flea is represented by a point in a 2D environment; C = R 2 is the configuration space. There are obstacles in this 2D environment such that the free space F is an open set. The Boolean-valued function κ : C → {true, false} of collision-freeness in C is defined for any s ∈ C by κ(s) ⇔ s ∈ F. The flea can make jumps in any direction and of any length strictly less than l max > 0. The goal is to find a sequence of jumps from a location (x A , y A ) ∈ F to a location (x B , y B ) ∈ F such that every intermediate configuration of the flea is in F. The discontinuous nature of this flea motion planning problem is similar to the discontinuous nature of the problem of finding sequences of footsteps for legged robots.

To solve this problem efficiently, we first prove an equivalence between the discontinuous motion of the flea, and the continuous motion of an open disk, but with a new notion of collision-freeness. So, let us assume that a sequence of jumps has been found, and that it corresponds to the sequence of configurations p 1 = (x 1 , y 1 ), p 2 , p 3 , . . . , p n = (x n , y n ), with (x 1 , y 1 ) = (x A , y A ) and (x n , y n ) = (x B , y B ). We consider the continuous motion s : [0, 1] → R 2 of an open disk of diameter l max defined by linear interpolation between each (x i , y i ) and (x i+1 , y i+1 ) for i = 1, 2, . . . , n -1, as depicted in Figure 1 (on the left). An interesting property of this continuous disk motion is the following (it is a direct consequence of the upper bound l max on the length of jumps):

Property 2.1. For all t ∈ [0, 1], the configuration s(t) of the disk contains at least one of the flea configurations p 1 , p 2 , . . . , p n . This property suggests the definition of a new notion of collision-freeness: Definition 2.1. We say that a disk configuration (x, y) is collision-free if there exists at least one flea configuration (i.e. point) inside the disk which is collision-free. We call this new notion of collisionfreeness the "weak collision-freeness", and say that the disk configuration is "weakly collision-free". Conversely, if all the flea configurations inside the disk are in collision (i.e. the disk does not intersect the free space), we say that the disk is in "strong collision". We say that a continuous path of disks configurations is weakly collision-free if all the configurations along that path are weakly collision-free.

Figure 2 illustrates this definition. We can reformulate Property 2.1: Theorem 2.1. If there exists a finite sequence of collision-free jumps from (x A , y A ) to (x B , y B ), then there also exists a weakly collision-free continuous path of the open disk of diameter l max from (x A , y A ) to (x B , y B ).

We prove that the converse is true: Theorem 2.2. If there exists a weakly collision-free continuous path of the open disk of diameter l max from (x A , y A ) to (x B , y B ), then there exists a finite sequence of collision-free jumps from (x A , y A ) to (x B , y B ). Proof. Intuitively, the reason for this theorem to hold is that since the path is weakly collision-free, the free space intersects every configuration of the disk along that path. And because the disk is of diameter l max , it follows that in order to progress along the intersection between the free space and the area swept by the disk, the flea never has to make jumps larger than l max , and therefore it can go from one end of the path to the other.

Let us denote by d 2 the Euclidean distance in R 2 , and by D (x,y) the open disk of center (x, y) and diameter l max . For a point s ∈ C we denote by d obs (s) = inf{d 2 (s, o)|o ∈ C \ F} its distance to the obstacles. For a configuration (x, y) of the disk we define: δ obs (D (x,y) ) = sup{d obs (s)|s ∈ D (x,y) }. A configuration (x, y) is weakly collision-free if and only if δ obs (D (x,y) ) > 0. Let us consider a weakly collisionfree continuous path s : [0, 1] → R 2 from (x A , y A ) to (x B , y B ). We pose d inf = 1 2 inf{δ obs (D s(t) )|t ∈ [0, 1]}. By continuity of t → δ obs (D s(t) ), we have d inf > 0. By uniform continuity of s, there exists 0

< ǫ < 1 such that ∀t ∈ [0, 1-ǫ], d 2 (s(t), s(t+ǫ)) < min(d inf , l max ).
Let us now consider t ∈ [0, 1-ǫ] and a collision-free configuration s of the flea in D s(t) . First, we know that there exists s ′ ∈ D s(t) such that d obs (s ′ ) > d inf . Besides, since D s(t) is of diameter l max , we have d 2 (s, s ′ ) < l max , and thus the flea can jump from s to s ′ . Then, since we have d 2 (s(t), s(t + ǫ)) < min(d inf , l max ), there exists s ′′ ∈ D s(t+ǫ) such that d 2 (s ′ , s ′′ ) < min(d inf , l max ). It follows that s ′′ is collision-free, and the flea can jump from s ′ to s ′′ . So we have proved that if s is a collision-free configuration of the flea in D s(t) with t ∈ [0, 1 -ǫ], it is always possible to reach a collision-free configuration in D s(t+ǫ) with at most 2 jumps. By iteration, we deduce that a collision-free configuration s α ∈ D s(1) can be reached after a finite number of jumps. We have d 2 (s α , (x B , y B )) < l max , and therefore the flea can jump directly from s α to (x B , y B ). This concludes the proof, and an example of sequence of jumps obtained from a weakly collision-free continuous path of the disk can be seen on the right side of Figure 1.

Together, Theorem 2.1 and Theorem 2.2 form an equivalence between the weakly collision-free paths of the disk and the collision-free sequences of jumps of the flea. It turns out that this equivalence gives an efficient algorithm to solve the flea motion planning problem. Indeed, instead of looking for a dis-continuous sequence of jumps, we can first look for a continuous path of the disk, and that can be done with any conventional motion planning algorithm, provided that we implement new collision checks using Definition 2.1. Besides, in the case of flea motion planning these "weak collision" checks are very easy to implement with a morphological operation of erosion of the obstacles by an open sphere of radius lmax 2

(see [Serra, 1983]): the disk D (x,y) is in strong collision with the obstacles if and only if its center (x, y) is inside the eroded obstacles. So, once the eroded obstacles are obtained, we can use any classical motion planning algorithm to find a short weakly collision-free path for the disk. To actually convert this continuous path into a finite sequence of jumps, we can apply the greedy approach already used in [START_REF] Perrin | Real-time footstep planning for humanoid robots among 3d obstacles using a hybrid bounding box[END_REF] which consists in repeatedly trying to jump from the current disk D s(t) to a disk D s(t ′ ) with t ′ as large as possible and obtained by dichotomy. This can result in "shortcut jumps", as shown in Figure 1 (on the right). Figure 3 illustrates the whole method with a simple example where the obstacles are polygonal (in that case we can actually find the shortest path for the disk in polynomial time: see [de Berg et al., 2000], ch. 15).

Using such a transfer towards continuous motion planning has several benefits.

For the flea motion planning problems, other more direct approaches are also very efficient, and for example it would be easy to naively adapt the RRT algorithm to grow trees of discrete sequences of jumps. But for more complicated problems such as footstep planning, adapting RRT is not an easy task because it is not always clear how to extend a node towards a sample configuration. For this reason the current state-of-the-art method is to choose in advance a finite set of possible steps and then use A*-like algorithms to search for sequences of steps towards a goal ( [START_REF] Kuffner | Footstep planning among obstacles for biped robots[END_REF], [START_REF] Bourgeot | Path-planning and tracking in a 3d complex environment for an anthropomorphic biped robot[END_REF], [START_REF] Chestnutt | Planning biped navigation strategies in complex environments[END_REF]], [START_REF] Chestnutt | Footstep planning for the honda asimo humanoid[END_REF]).

Although adjustments have been considered (see [START_REF] Chestnutt | An adaptive action model for legged navigation planning[END_REF]), starting by manually selecting a finite number of possible steps is not very satisfying and leads to several problems such as limited stepping capabilites. The approach we present in sections 4 and 5 is based on a similar equivalence as the one formed by theorems 2.1 and 2.2, and it enables to deal with fully continuous stepping capabilities in an efficient and theoretically sound way.

For a hexapod, a large set of possible steps would be required in order to obtain decent stepping capabilities, and therefore methods based on A*-like algorithms are difficult to apply. This problem can be circumvented by using fixed gaits, but they are less efficient in complex environments. The method we propose in Section 6 is again based on an equivalence that transforms the problem into a fully continuous one, and it enables to very quickly find sequences of steps even in quite complex environments.

We have also implemented our continuous approach (with RRT used to plan continuous paths) for some random instances of 2D flea motion planning, and after comparison the results obtained indicate that a proper implementation of our approach has the potential to outperform a naive adaptation of RRT, especially in simple environments. What's more, since in our approach each edge of the tree grown by the RRT algorithm represents not one, but a whole set of potential sequences of jumps, the trees obtained are significantly smaller than trees of similar covering obtained with a naive adaptation of RRT, and this can be very useful for operations such as nearest neighbor search or tree transformations.

An equivalence between some discrete and continuous motion planning problems

In this section we demonstrate a general result that can be applied in particular to flea motion planning to obtain the equivalence between the discrete sequences of jumps and the continuous weakly collisionfree paths of the disk. First, let us introduce some notation and definitions.

We will only consider metric configuration spaces, and denote by dist() their distance functions. Let C be a metric configuration space. For s ∈ C and r > 0, we denote by S(s, r) the open sphere of center s and radius r. F, the free space, is always as-sumed to be an open subset of C. We denote by κ the Boolean-valued function of collision-freeness: F = {s ∈ C|κ(s)}. We denote by d obs the function from C to R + defined by d obs (s) = inf{dist(s, o)|o ∈ C \ F}, and for any non-empty bounded set E ⊂ C, we define δ obs (E) = sup{d obs (s)|s ∈ E}.

We now give a definition of discrete and continuous motion planning problems. It is by no means a general definition, but we will only consider this type of problems.

Definition 3.1 (continuous motion planning problems). INPUT: C, κ: mapping from C to {true, false}, s i ∈ F and s f ∈ F. OBJECTIVE: find a continuous path (s(t)) t∈[0,1] such that ∀t ∈ [0, 1], κ(s(t)) (we call "valid" such a continuous path), and such that s(0) = s i and s(1) = s f . We will also consider slight variants of these problems where the initial and final configurations are not fixed but must simply belong to some sets.

For discrete motion planning, there is an additional relation R that defines a relationship between consecutive configurations. Definition 3.2 (discrete motion planning problems). INPUT: C, κ: mapping from C to {true, false}, R: mapping from C × C to {true, false}, s i ∈ F and s f ∈ F. OBJECTIVE: find a finite sequence of configurations (s 1 , s 2 , . . . , s n ) such that ∀k ∈ {1, . . . , n -1}, κ(s k ), κ(s k+1 ), and R(S k , S k+1 ) (we call "valid" such a finite sequence), and such that s 0 = s i and s n = s f . Remark: in the rest of the paper, without ambiguity we will use the adjective "valid" to denote various types of "acceptable" configurations, paths or sequences. It will sometimes just mean "collision-free" or "weakly collision-free", and sometimes a variant of one of these notions, plus possibly additional restrictions.

The objective of the equivalence we are about to prove is to convert discrete motion planning problems into equivalent continuous motion planning problems, but not on the same configuration space, and with a different notion of collision-freeness.

The equivalence is stated below with Theorem 3.1, which has been introduced and proven in [Perrin, 2012] with slightly different hypotheses. Another more general equivalence is studied in [Perrin, 2012], but it has less direct applications. Similar equivalence theorems between discrete and continuous motion planning problems are not common in the literature, but we can mention [START_REF] Alami | Two manipulation planning algorithms[END_REF] where a reduction property shows that for some class of manipulation problems, the existence of a solution path with discrete "grasp" and "release" events is equivalent to the existence of a path where the grasp is continuously modified.

So, let us consider a discrete motion planning problem, entirely defined by the metric configuration space C, its free space F, the relation R and s i and s f .

We denote by P(C) the set of subsets of C. We assume that there exists another metric configuration space Ω and a function f : Ω → P(C) such that the five following properties are verified:

1. The function δ obs • f is continuous.

2. For all ǫ > 0 there exists η > 0 such that ∀ϕ, ϕ ′ ∈ Ω verifying dist(ϕ, ϕ ′ ) < η, the set f (ϕ) ∩ f (ϕ ′ ) is non-empty and it intersects all the spheres S(s, ǫ) such that s ∈ f (ϕ).

3. ∀ϕ ∈ Ω, f (ϕ) is such that ∀(s, s ′ ) ∈ f (ϕ) 2 , R(s, s ′ ).
4. For any (s, s ′ ) ∈ C 2 such that R(s, s ′ ), there exists ϕ ∈ Ω such that s ∈ f (ϕ) and s ′ ∈ f (ϕ).

5. ∀(s, s ′ , s ′′ ) ∈ C 3 such that R(s, s ′ ) and R(s ′ , s ′′ ), and ∀ϕ 0 ∈ Ω such that s ∈ f (ϕ 0 ) and s ′ ∈ f (ϕ 0 ), there exists a continuous path from ϕ 0 to a configuration ϕ 1 verifying s ′′ ∈ f (ϕ 1 ), such that for any configuration ϕ along this path, we have

s ′ ∈ f (ϕ). This property is illustrated in Fig- ure 4.
Example 3.1. In the case of the flea motion planning problem of Section 2, Ω = C = R 2 , f : s → D s satisfy the above properties.

Intuitively, f is the crucial function that transfers the viewpoint from states that move discretely in a Figure 4: A continuous path from ϕ 0 to ϕ 1 . continuous space C to sets of potential states whose "continuous" motions in P(C) are governed by states moving continuously in Ω. Depending on the discrete problem, finding such a function f and a proper space Ω can be more or less difficult, and although some insight is given in [Perrin, 2012], it is beyond the scope of the present paper.

The aim of the five properties of f is to obtain the same kind of equivalence as the one formed by theorems 2.1 and 2.2 of Section 2. They are needed in the proofs of Theorem 3.2 and Theorem 3.3.

On Ω, we define a new notion of collision-freeness κ Ω : Definition 3.3 (κ Ω ). ϕ ∈ Ω verifies κ Ω (ϕ) if and only if the intersection between f (ϕ) and the free space is non-empty, i.e. ∃s ∈ f (ϕ) such that κ(s).

Under the above assumptions, the following theorem holds: Theorem 3.1. There exists a valid finite sequence from s i to s f in C if and only if there exists a continuous path

(χ(t)) t∈[0,1] ∈ Ω [0,1] such that s i ∈ f (χ(0)), s f ∈ f (χ(1)), and ∀t ∈ [0, 1], κ Ω (χ(t)).
This theorem is an equivalence that generalizes the one formed by theorems 2.1 and 2.2. We prove the two implications of this equivalence in the next two sections (theorems 3.2 and 3.3).

From a valid discrete sequence in

C to a valid continuous path in Ω Theorem 3.2. If there exists a valid sequence (s 1 = s i , s 2 , . . . , s n = s f ), then there exists a valid con-

tinuous path (χ(t)) t∈[0,1] such that s 1 ∈ f (χ(0)), s 2 ∈ f (χ(0)), s n-1 ∈ f (χ(1)) and s n ∈ f (χ(1)).
Proof. We prove this implication by induction on n, the size of the valid sequence. For n = 2, we have R(s i , s f ), and there exists ϕ ∈ Ω such that s i ∈ f (ϕ) and s f ∈ f (ϕ). The stationary path such that ∀t ∈ [0, 1], χ(t) = ϕ, is valid.

Let us now assume that the result is true for any sequence of size n ≥ 2, and consider a valid sequence of size n + 1:

(s 1 = s i , s 2 , . . . , s n+1 = s f ). Let (χ(t)) t∈[0,1] ∈ Ω [0,1] be a valid path such that s 1 ∈ f (χ(0)), s 2 ∈ f (χ(0)), s n-1 ∈ f (χ(1)) and s n ∈ f (χ(1)). We have R(s n-1 , s n ) and R(s n , s n+1 ), so there exists a continuous path (ϑ(t)) t∈[0,1] ∈ Ω [0,1] from χ(1) to a configuration ϕ f ∈ Ω verifying s n+1 ∈ f (ϕ f )
, such that for any configuration ϑ along this path, we have s n ∈ f (ϑ), and thus κ Ω (ϑ). Appending this path to the path (χ(t)) t∈[0,1] gives us a valid continuous path, and this conludes the proof of Theorem 3.2.

From a valid continuous path in Ω

to a valid discrete sequence in C Theorem 3.3. If there exists a valid continuous path (χ(t)) t∈[0,1] ∈ Ω [0,1] with s i ∈ χ(0) and s f ∈ χ(1), then there exists a valid sequence (s 1 = s i , s 2 , . . . , s n = s f ).

Proof. The second property of f implies that for any ǫ > 0, there exists N ∈ N * such that the sequence (χ(0/N ), χ(1/N ), . . . , χ(N/N )) verifies the following property: ∀k ∈ {0, . . . , N -1}, for any configuration s ∈ f (χ(k/N )), the sphere S(s, ǫ) intersects the non-empty set

f (χ(k/N )) ∩ f (χ((k + 1)/N )). Be- sides, since F is an open set, we have: ∀t ∈ [0, 1], δ obs (f (χ(t))) > 0. And t → δ obs (f (χ(t))) is contin- uous, so there exists d inf > 0 such that ∀t ∈ [0, 1], δ obs (f (χ(t))) > d inf .
It follows that for ǫ small enough, for all t ∈ [0, 1] there exists s t ∈ f (χ(t)) collision-free and such that the sphere S(s t , ǫ) is entirely inside F. We thus deduce that all the sets f (χ(k/N )) ∩ f (χ((k + 1)/N )) have a non-empty intersection with F. Using the property that two elements s, s ′ of the same set f (χ(t)) are always such that R(s, s ′ ), we can construct a valid sequence (s 1 , s 2 , . . . , s N +2 ) such that s 1 = s i , s N +2 = s f , and ∀k ∈ {2, . . . , N + 1},

s k ∈ f (χ((k -2)/N )) ∩ f (χ((k - 1)/N )
. Such a construction is illustrated in Figure 5, and it concludes the proof of Theorem 3.3, and Theorem 3.1.

In the two next sections, we present applications of Theorem 3.1 to more practical problems.

Application to vision-based reactive footstep planning

In this section we apply Theorem 3.1 to the problem of footstep planning for humanoid robots. In previous work [START_REF] Perrin | Weakly collisionfree paths for continuous humanoid footstep planning[END_REF], [START_REF] Perrin | Real-time footstep planning for humanoid robots among 3d obstacles using a hybrid bounding box[END_REF]), we used a similar approach, but without establishing a link with a more general theorem such as Theorem 3.1, and with several significant differences. In particular, the approach presented in this section is designed to efficiently use input heightmaps acquired by stereo vision, while in [START_REF] Perrin | Weakly collisionfree paths for continuous humanoid footstep planning[END_REF] and [START_REF] Perrin | Real-time footstep planning for humanoid robots among 3d obstacles using a hybrid bounding box[END_REF] 3D models of the obstacles were assumed to be known in advance.

In sections 4.1 to 4.4, we show how to apply Theorem 3.1 so as to obtain an efficient algorithm for planning sequences of steps on heightmaps. Then, in section 5, we describe our decentralized architecture for real experiments of reactive footstep replanning with the DLR-Biped robot. Obstacle avoidance is safe if every obstacle is included in the heightmap, but not all environments can be represented by heightmaps, and in previous work, we addressed this issue by using a hybrid bounding box [START_REF] Perrin | Real-time footstep planning for humanoid robots among 3d obstacles using a hybrid bounding box[END_REF]) to Figure 6: On the left the outer and inner disks are displayed, the latter one being a bit greater than the width of the foot. As shown on the right, the region between the inner and outer circles does not necessarily have to be in contact with the ground for a location to be safe. perform full-body obstacle avoidance in complex environments.

Construction of the map of safe foot locations

Let us assume that a discretized heightmap of the environment is known, that is to say a matrix H = (h i,j ) 0≤i≤k1,0≤j≤k2 , with h i,j = h(x i , y j ) (we use a fixed resolution along the x and y axes). Our first objective is to build a map of the locations where the feet of the robot can safely land. To keep a low dimensionality and simplify the application of Theorem 3.1, we assume that the robot has circular feet. Since the real robot (the DLR-Biped) has in fact rectangular feet, we consider two disks, the inner and outer disks, as shown in Figure 6. For every location (x a , y b ) in the map, we first find the maximum height h m among all the values of h(x i , y j ) such that (x i , y j ) is inside the outer disk centered at (x a , y b ). Then, we only consider the locations (x i ′ , y j ′ ) inside the inner disk centered at (x a , y b ), and we verify that all the heights h(x i ′ , y j ′ ) are above h m -τ , where τ is a very small threshold determined experimentally. If this property is verified, we consider the location (x a , y b ) as safe, and associate it with a height close to h m which depends on the values of H inside the inner disk. This verification ensures us that most of the part of the foot inside the inner disk is in contact with an almost flat and horizontal region of the ground. Once this verification has been made for all the locations in H, we obtain a new matrix M that stores all the safe landing locations together with the height at which the foot should land. Figure 7 illustrates the construction of the matrix M for an example heightmap built from a stereo image pair.

Application of Theorem 3.1

In this section we explain how we apply Theorem 3.1 to footstep planning. For now, we do not take into account the height of the footsteps, and use the configuration space C = (SE(2)) 2 (one element of SE(2) for each foot, specifying the position of its center and its orientation). We use Ω = SE(2), and denote elements of SE(2) by triples (x, y, θ). We also define the "difference" between two angles θ and θ ′ as the value dif a (θ, θ ′ ) = θ ′ -θ + 2πn with n ∈ Z minimizing |θ ′ -θ + 2πn|. On C, we use a distance of the form:

dist(((x l , y l , θ l ), (x r , y r , θ r )), (( with A > 0 and B > 0.

x ′ l , y ′ l , θ ′ l ), (x ′ r , y ′ r , θ ′ r ))) = A. d 2 ((x l , y l ), (x ′ l , y ′ l )) + B. |dif a (θ l , θ ′ l )| + A. d 2 ((x r , y r ), (x r , y ′ r )) + B. |dif a (θ r , θ ′ r )|,
f is a function that maps elements of Ω to sets of configurations in C. The sets f (x, y, θ) are similar to the object Φ defined in [START_REF] Perrin | Weakly collisionfree paths for continuous humanoid footstep planning[END_REF]. They are based on two subsets of R 2 , f LEF T (x, y, θ) and f RIGHT (x, y, θ), which depend on two parameters, r and h. f LEF T (x, y, θ) and f RIGHT (x, y, θ) are symmetric portions of a disk, and are defined as shown in Figure 8. We also define f LEF T (x, y, θ) and f RIGHT (x, y, θ), subsets of SE(2) that depend on two parameters α in > 0 and α out > 0, as follows:

f LEF T (x, y, θ) = {(x, y, β)|(x, y) ∈ f LEF T (x, y, θ) ∧ - α in 2 ≤ dif a (θ, β) ≤ α out 2 } f RIGHT (x, y, θ) = {(x, y, β)|(x, y) ∈ f RIGHT (x, y, θ) ∧ - α out 2 ≤ dif a (θ, β) ≤ α in 2 }
Finally, we have:

f (x, y, θ) = f LEF T (x, y, θ) × f RIGHT (x, y, θ) (1)
It can be shown that for any open free space F ⊂ C, f verifies the two first assumptions required for Theorem 3.1 to apply. Indeed, the function f basically only rotates and translates the fixed set f LEF T (0, 0, 0) × f RIGHT (0, 0, 0); hence, the sets f (x, y, θ) are modified in a continuous manner, and consequently δ obs • f is continuous. Besides, the simple geometry of the open sets f (x, y, θ) explains why for s and s ′ very close in SE(2), f (s) ∪ f (s ′ ) and f (s) ∩ f (s ′ ) are very close in the sense of the Hausdorff distance, which implies the second assumption required by Theorem 3.1.

In the problem of footstep planning, the relation R should define the stepping capabilities of the robot, i.e. R(s, s ′ ) should be verified if and only if we can go from the configuration s to the configuration s ′ in one step. Yet, it is more convenient to deal with sequences of two steps (because both footprints can be modified), so we will use a relation R such that R(s, s ′ ) is verified if and only if it is possible to go from s to s ′ with two steps (we fix rules so that these two steps are unambiguously defined by s and s ′ ). The relation R will of course not capture the real stepping capabilities of the robot, but it must be a conservative approximation. This means that the steps allowed by R should always be feasible on the robot, and R should not be too restrictive so as not to under-exploit the robot capabilities.

For s, s ′ ∈ C, we actually define R(s, s ′ ) as follows:

R(s, s ′ ) ≡ ∃ϕ ∈ SE(2), s ∈ f (ϕ) ∧ s ′ ∈ f (ϕ) (2)
We do not prove it here, but this definition implies the validity of the fourth and fifth assumptions required by Theorem 3.1 (for the fourth assumption, it is a direct consequence of the definition of R; for the fifth assumption, it is a consequence of some geometric properties of f ). So, in order to approximate the stepping capabilites of the robot in a conservative way, we can tune the parameters r, h, α in and α out . The configurations that can be used by the robot with this definition of R are described in Figure 9 (with the left foot used as a reference). Attention must be paid to the fact that the restrictions imposed by R are not only on the configurations between steps: they are also on the transitions between configurations (see [START_REF] Perrin | Weakly collisionfree paths for continuous humanoid footstep planning[END_REF] for a visual description of these restrictions). On Figure 9, we can see that the maximum distance between the centers of the feet is r, while h limits the closeness of the feet. The orientation of the right foot relatively to the left one is comprised between -α out and α in .

To adjust the values of r, h, α in and α out , we use an empirical approach. The first constraint is that these values should lead to steps without selfcollisions. Due to the particular structure of the legs of the DLR-Biped, a self-collision can easily occur when its feet are turned inward, even just slightly: see Figure 10. For this reason, we use asymmetric constraints on the foot orientations, and set α in to 1 • and α out to 15 • . Furthermore, we sample many configurations of the robot with both feet on the ground (and at the same height), obtaining the results shown in Figure 11. The left foot being used as a reference, each point represents a position of the center of the right foot, and for each location, we test several orientations ranging from -α out to α in . The configuration of the robot legs is set by inverse kinematics. In Figure 11, the points inside the region defined by the thick line segments are the ones for which there exists at least one orientation so that self-collisions almost occur, i.e. some body of the left leg is at most at distance 2cm from a body of the right leg. The other points are "safe" configuration, and we must choose h so that only safe configurations can occur. That's why we set h = 20cm. Besides, the steps allowed by R should be executed without failure by the control algorithm. This limits the maximum length of steps, hence it limits r. With the values of α in , α out and h already set, we test various gaits and various step lengths to tune r. The value chosen according to these tests is r = 32cm. Using such parameters leads to the validity of the third assumption required by Theorem 3.1: for any (x, y, θ) ∈ Ω = SE(2), and any s, s ′ ∈ f (x, y, θ), it is actually possible to go from s to s ′ with two steps, without falling and without self-collisions.

Hence, all the assumptions of Theorem 3.1 are verified, and we can apply it. This means that in order to look for sequences of steps, we can reason in the smooth configuration space Ω = SE(2). The new notion of collision on this space is κ Ω , verified for (x, y, θ) ∈ Ω if and only if there exists a configuration s ∈ C inside f (x, y, θ) such that the centers of both left and right foot are at safe locations (which can be checked with the matrix M ). Thanks to Theorem 3.1, we know that any valid continuous path in Ω can be converted into a finite sequence of valid steps. Figure 12 illustrates an example of such con- Figure 11: This shows how the values h and r (see Figure 9) have been computed for the DLR Biped: the left foot is kept at the zero position and orientation, and each sample point corresponds to a position of the center of the right foot. For each of these sample points, stances obtained with different orientations of the right foot ranging from -15 • to 1 • have been tested. The points inside the region defined by the thick line segments are the ones for which some orientation of the right foot can bring the robot very close to self-collisions. h must be chosen so as to exclude this region, while r can be set as large as the walking control algorithm allows it.

version, from a valid continuous path in SE(2) to a finite sequence of valid steps (for the sake of clarity, on Figure 12 we use and display inner disks smaller than the ones corresponding to the dimensions of the DLR-Biped).

There is however a problem remaining: so far we haven't introduced any verification that would prevent the robot from walking on stairs with large step height. Thus, we add a new test in κ Ω : for a configuration (x, y, θ) ∈ Ω to be valid (collision-free), there must not only be a valid configuration s ∈ f (x, y, θ), there must also be a valid configuration in f (x, y, θ) such that the minimum height z of both feet locations (these heights are stored in the matrix M ) verifies the following property: no point inside the disk of center (x, y) and radius r + ρ (where ρ is a small positive constant) is above z +m ST AIR , where m ST AIR > 0 is an empirically defined constant that depends on the robot capabilities and roughly denotes the maximum height of steps on which the robot can walk. This constraint also prevents the robot from walking close to high obstacles while still allowing it to step over small obstacles (of height less than m ST AIR ).

Construction of the matrix M κ Ω

The tests κ Ω are more complex than usual collision checks. In this section we describe the construction of a matrix M κΩ that stores the results of the tests for every location of the discretized heightmap.

Let us consider a location (x a , y a ) in the discretized map. For the tests κ Ω , the orientation matters, so the matrix M κΩ will be 3-dimensional. We use a 1 • precision, and thus to every location (x a , y b ) correspond 360 tests whose results must be stored in M κΩ : (x a , y b , 0 • ), (x a , y b , 1 • ), . . . , (x a , y b , 359 • ). For every location (x a , y b ) in the discretized map, we perform a computation to find all the orientations β such that κ Ω (x a , y b , β) is verified. First of all, we Finding orientations β such that f RIGHT (x a , y b , β) contains a given safe location. compute the maximum height z max inside the disk of center (x, y) and radius r + ρ (see previous section). We only consider safe locations that are above height z max -m ST AIR . As shown on Figure 13, for every such safe location l we can easily find the interval of angles β such that l is inside f RIGHT (x a , y b , β) (resp. f LEF T (x a , y b , β)). By scanning the locations inside the disk of center (x, y) and radius r (and outside disk of center (x, y) and radius h) in a smart order (and without the at a distance from (x a , y a ) less than h), we can manage to compute the union of these intervals in an efficient way. Afterwards, it is easy to fill the 360 values in M κΩ associated with the location (x a , y a ). After repeating this process for all the locations in H, we obtain the full matrix M κΩ , which can be used to compute the tests κ Ω in constant time.

Footstep planning simulation

Algorithm 1 sums up the 4 steps of the main loop of our footstep planning algorithm. After the discretized heightmap of the environment has been received, we first construct the matrix M , and then the matrix M κΩ .

The fact that these matrices are constructed at every iteration of the loop might seem unefficient, but it has actually several advantages. The main one is that it is very well suited for parallel computations (but Algorithm 1 1: while (true) do 2:

Receive the updated heightmap matrix H.

3:

Construct the matrix M that stores safe foot locations.

4:

Construct the matrix M κΩ .

5:

If needed, perform motion planning in SE(2), using M κΩ for collision checks. Then, use a greedy approach (similar to the of the rithm for flea motion planning: see Section 2) convert the continuous path into a finite sequence of steps. 6: end while we do not use parallel computations in the impledescribed in the present paper). Thanks to the matrix M κΩ , the complex collision checks κ Ω can be evaluated extremely quickly, and thus, the path planning itself is very fast (it is done in SE(2), a space with only 3 dimensions). As a result, the most time-consuming part of the computation is the construction of the two matrices M and M κΩ . Unlike classical motion planning algorithms which are difficult to parallelize (see for example [START_REF] Pan | g-Planner: Real-time motion planning and global navigation using GPUs[END_REF]), it is straight forward to make the construction of M and M κΩ parallel. Besides, the time required for the construction of M and M κΩ does not vary a lot, while the randomness in most motion planning algorithms makes their duration hard to predict. It follows that our approach is well suited for systems with hard realtime constraints.

Figure 14 shows a simulation of footstep planning. We use a kinematic model of the DLR-Biped, but there is no physics simulation. The robot starts in an initial configuration and must find a sequence of steps toward a goal. The heightmap used is the same as the one displayed in Figure 7. We resend it at every iteration of the loop of Algorithm 1, and the matrices M and M κΩ are rebuilt from scratch every time. The heightmap is a 200 by 200 matrix, which means that for M κΩ , 200 × 200 × 360 = 14, 400, 000 values have to be computed and filled at each iteration. For the motion planning, we use the RRT-Connect algorithm [START_REF] Kuffner | RRT-Connect: An efficient approach to single-query path planning[END_REF] from the OMPL library [START_REF] Ompl | The Open Motion Planning Library[END_REF] to find paths in SE(2), and Figure 14: A simulation of footstep planning. Below the snapshots are displayed maps of safe locations (the matrix M ) with additional data. In the first row below the snapshots are shown the sets f LEF T (ϕ) ∪ f RIGHT (ϕ) for milestones ϕ ∈ SE(2) chosen by the RRT-Connect algorithm, for a part of the last path found. In the second row are shown "traces" of these sets along the paths. In the row at the bottom, we also display the footprints resulting from the greedy conversion to finite sequences of steps. then use a greedy approach (as explained in Section 2) to convert them into finite sequences of steps. Thanks to the matrix M κΩ (collision checks in constant time), the motion planning is very fast, so we actually repeat this process (RRT-Connect + greedy conversion) 10 times, and keep the shortest sequence of steps. To obtain short sequences of steps, some more efficient strategies are made possible by our novel continuous approach, such as trajectory optimization on the path found in SE(2) (see for example [START_REF] Park | ITOMP: Incremental trajectory optimization for real-time replanning in dynamic environments[END_REF]), or kinodynamic planning (see for example [START_REF] Sucan | Kinodynamic motion planning by interior-exterior cell exploration[END_REF]). The use of such strategies seems promising but is out of the scope of this paper.

Simultaneously to motion planning, on the same computer, a walking pattern generator is simulated on another thread. It takes as input the sequence of future steps, which is updated at each iteration. The communication between the planning and control threads simulates the communication protocol used for the experiments on the real DLR-Biped, explained in the next section.

In the simulation shown on Figure 14, the robot first has to find its way through small stairs, and after a few seconds, a bump is artificially introduced in the heightmap, forcing the robot to quickly find another path toward the goal. For 10 trials of this simulation on an Intel(R) Core(TM) i7 1.60GHz CPU, we measure at each iteration (of the loop of Algorithm 1) the time required for the construction of the matrices M and M κΩ . Figure 15 displays the mean time together with the standard deviation for those 10 trials, and only for the first 11 iterations of the loop (after that, the robot had reached or almost reached the goal in every trial). The first iteration takes a bit longer (2.4s in average) because of the initial memory allocation. The variations of the computation times are mostly due to the thread that does the walking pattern generation and the 3D display. For the same 10 trials, we also measure the time required at every iteration for motion planning, i.e. the 10 executions of the RRT-Connect algorithm, each followed by a greedy conversion of the path found in SE(2) into a finite sequence of steps. Path planning is performed at every iteration, even if the environment has not changed since the previous iteration. Since the robot is getting gradually closer to the goal, motion planning becomes easier, which explains the decreasing tendency of the computation times that can be seen in Figure 16. At the first iteration, the robot has to find a sequence of steps that goes across the small stairs, which explains why motion planning takes substantially more time. A second peak can be observed at the third iteration: it is usually the iteration before which the bump appears in the heightmap. The average time for motion planning is always less than 0.33s. This means that one execution of RRT-Connect followed by the greedy conversion takes in average no more than 33ms.

5 A decentralized software architecture for reactive footstep planning

In this section we describe the decentralized software architecture that we used for real experiments on the DLR-Biped. Unlike control or vision, motion planning is a task that can be done at a relatively low frequency, and it does not need to interact quickly with the robot sensors. For this reason, we perform motion planning on a computer which is not embedded in the robot. The advantage of this approach is that it reduces the onboard computational load and energy consumption. The drawback is that it would not be suitable if the robot were to explore an unknown environment with significant communication delay (or no communication at all).

We use a total of 3 computers: 2 on the robot, and one remote computer for the footstep planning. On the robot, there is one computer for the control, and one for the vision.

The role of the vision computer is to build the heightmap matrix H. In the simulation, the size of this matrix was 200 by 200, but in the real experiment we use a 100 by 100 matrix in order to make the vision algorithms faster. The resolution is 4cm, which means that the size of the area covered by the heightmap is 4m by 4m. Stereo image pairs are frequently obtained by the robot cameras and used to locally update the values of the heightmap matrix. In the areas where no data has been acquired yet, we assume a flat floor. The heightmap is updated about every second, but this update does not necessarily include data from a stereo image pair obtained one second before: the delay can vary roughly between 1 and 3 seconds. Whenever the heightmap file is being modified, we use a mutex to block any attempt at reading the file. Details on the stereo vision algorithm can be found in [A. Stelzer et al., 2012].

The control algorithm is based on capture point dynamics [START_REF] Englsberger | Bipedal walking control based on capture point dynamics[END_REF], and its purpose is to execute a list of steps received from the planner. Every step has an identifier. The control also needs to send some information to the planner: it frequently sends the identifier of what we call the "last unmodifiable step" (LUS). This step depends on many parameters of the control algorithm, for example the walking speed. If the robot walks slowly, even the current step might be modifiable. But if the robot walks fast, it might have to execute at least the next two steps as they are currently planned. Since the LUS is difficult to predict precisely, we use a simple definition verified empirically. Knowing the LUS, the planner can decide from where (in the sequence of steps currently planned) to replan when necessary.

When a sequence of steps is found by the planner, only a constant number of steps is sent to the control. For example, only the first 7 steps of the sequence are sent (unless the sequence contains less than 7 steps). Every time a new list of steps is sent, both the planner and the controller update the "sequence of steps currently planned" (SSCP). During an iteration of the loop of Algorithm 1, replanning is done if the SSCP does not reach the current goal, or if it is not valid anymore in the current environment described by the matrix H. Since only a few steps are sent at each iteration, the SSCP grows progressively toward the goal. The advantage of this is that as the initial state for the replanning gets closer to the goal, motion planning becomes easier and better solutions can be expected in the same amount of time. Before starting the replanning, the planner decides which step of the SSCP will define the initial state. The sequence of steps found must be concatenated after this step in order to update the SSCP. Therefore, whenever a new list of steps is sent to the controller, the planner also indicates the identifier of the step after which the list must be concatenated. Of course, this identifier must never be before the LUS. As we have seen in the previous section, the computation time of our footstep planning algorithm does not vary a lot, and therefore, knowing approximately the duration of one step, we can use an appropriate margin to avoid the case where the SSCP would have to be modified before the LUS. For example, if the computation time for the planning is always much shorter than the duration of one step, it is safe to always replan only after the step following the LUS.

Figure 17 summarizes the communications between the 3 computers.

Figure 18 shows the result of an experiment on the DLR-Biped. On a flat surface, the robot first plans a sequence of steps toward a goal location. On its way to the goal, some obstacles are suddenly put in front of the robot which then updates the heightmap with the stereo vision algorithm and quickly replans a new sequence of steps.

6 Application to legged locomotion planning for a hexapod robot

In this section, we show that we can also apply Theorem 3.1 in to use a continuous approach for planning the walking motion of a hexapod robot (cf. Figure 19). Our objective is to make the hexapod walk on uneven terrain with non-gaited locomotion planning (which is typically computationally costly). Again, the uneven terrain is described by a heightmap matrix which is used to set the height of the contact positions. We ignore the contact orientations, so we use (R 2 ) 6 as the configuration space (it is easy to define a heuristic that sets a unique wholebody configuration from the 6 contact positions; in particular, we require the robot main body to remain horizontal). Here is how we define the valid states: from the heightmap we infer what locations are allowed for individual contacts similarly as in the previous section (except that we only consider one disk per leg, not an interior and an exterior disk), and for a configuration in (R 2 ) 6 , we require our heuristic to lead to a valid whole-body configuration that does not collide with the heightmap. Figure 21: The algorithm presented in this section can be slightly improved so as to allow locomotion on more complex terrains. The motion accross this terrain was planned in 0.33s.

We try to apply Theorem 3.1 with the configuration space Ω = SE(2). For a configuration (x, y, θ), we define f (x, y, θ) as the set of configurations in (R 2 ) 6 such that each contact belongs to an open disk, as shown on Figure 19 (it is important that the disks are disjoint). With this assumption, we first replace κ by heuristic checks: for a configuration s ∈ f (x, y, θ), κ(s) is verified if the contacts are safe (i.e. the heightmap is almost flat around their locations), if the maximum height difference between two contacts with the ground is less than some threshold, and if the maximum height of the heightmap in the "robot zone" (i.e. the convex hull of the contacts) is not much higher than the height of the contacts. We consider transitions where all the 6 legs are moved at the same time, and we say that a transition from s ∈ (R 2 ) 6 to s ′ ∈ (R 2 ) 6 is allowed if and only if there exists (x, y, θ) ∈ SE(2) such that s ∈ f (x, y, θ) and s ′ ∈ f (x, y, θ). With this restriction, we can verify that the conditions of Theorem 3.1 apply (only the fifth property is difficult to verify), and thus we can use the equivalence to convert our problem of locomotion planning into a continuous motion planning in SE(2) (we use again the library OMPL and the algorithm RRT-Connect to perform motion planning). Once the conversion of a continuous path is done, we obtain a finite sequence of transitions for which the 6 foot locations are changed at each transition. It is not difficult to convert it into a sequence of feasible transitions where at most 3 feet are moved at the same time (but sometimes 2, or just one). This original technique for legged locomotion planning is convenient and fast: in the example described in Figure 20 where the hexapod must go across an uneven and challenging terrain, the whole planning (continuous planning and two-stage conversion into a discrete sequence of steps) was done in 57ms on an Intel(R) Core(TM) i7 1.60GHz CPU. The algorithm can even be improved so as to change the hexapod's orientation according to the current height of its legs, which enables it to cross even more challenging terrains. The motion accross the terrain shown on Figure 21 was planned in 0.33s. However, we cannot directly use the same method to solve planning problems as complex as the ones considered in [START_REF] Hauser | Motion planning for a six-legged lunar robot[END_REF], but it is an interesting compromise between gaited methods and more complex approaches such as [START_REF] Hauser | Motion planning for a six-legged lunar robot[END_REF].

Conclusion

The main contribution of this paper is to define a set of conditions that make discrete motion planning for legged robot equivalent to continuous motion planning in a dedicated configuration space using the notion of weak-collision freeness. This equivalence provides a new way to reason about planning discrete actions in continuous spaces.

We have successfully applied the technique to various systems and it has revealed rather efficient in terms of computation. Furthermore, we believe that it can have applications beyond footstep or multicontact planning, such as for example in dextrous manipulation or hybrid systems.

Figure 2 :

 2 Figure 2: Weak collision-freeness.

Figure 3 :

 3 Figure 3: An efficient algorithm for flea motion planning.

Figure 5 :

 5 Figure 5: From a valid continuous path (χ(t)) t∈[0,1] ∈ Ω [0,1] to a valid finite sequence of configurations in C.

Figure 7 :

 7 Figure 7: On the left is displayed the heightmap of an environment containing some small stairs. The points in the purple zone in the map on the right are the safe foot locations in this environment.

Figure 8 :

 8 Figure 8: f LEF T (x, y, θ) and f RIGHT (x, y, θ).

Figure 9 :

 9 Figure 9: The configurations allowed by the definition of R according to equation (2).

Figure 10 :

 10 Figure 10: Due to the structure of the DLR-Biped legs, self-collisions are likely to occur when its feet are turned inward.

Figure 12 :

 12 Figure 12: Conversion: from a valid continuous path in SE(2) to a valid finite sequence of steps.

  Figure 13:

Figure 15 :

 15 Figure 15: Average time and standard deviation for the construction of the matrices M and M κΩ , at each iteration of the loop of Algorithm 1 (10 trials).

Figure 16 :

 16 Figure 16: Average time and standard deviation for motion planning in SE(2) and the conversion to finite sequences of steps, at each iteration of the loop of Algorithm 1 (10 trials).

Figure 17 :

 17 Figure 17: Communications between the 3 computers for vision, control and planning.

Figure 18 :

 18 Figure 18: An experiment of reactive footstep planning with the DLR-Biped

Figure 19 :

 19 Figure19: At the top: the hexapod in front of an uneven terrain it just crossed (cf. Figure20). The real version of this hexapod does not exist, but its legs have the same structure as the legs of the DLR-Biped. At the bottom: the six open disks that restrict the configurations and steps of the hexapod (each leg must have its contact with the ground within its assigned disk).

Figure 20 :

 20 Figure 20: The motion accross this challenging terrain was planned in 57ms.