Philippe Lemoisson
email: philippe.lemoisson@cirad.fr

Guillaume Surroca
email: surroca@lirmm.fr

Clement Jonquet
email: jonquet@lirmm.fr

Stefano A Cerri
email: cerri@lirmm.fr

ViewpointS: capturing formal data and informal contributions into an adaptive knowledge graph

Keywords: knowledge representation, knowledge graph, semantic Web, social Web, collective intelligence, nature-inspired computational model, formal/informal knowledge, serendipitous learning

Formal data is supported by means of specific languages from which the syntax and semantics have to be mastered, which represents an obstacle for collective intelligence. In contrast, informal knowledge relies on weak/ambiguous contributions e.g., I like. Reconciling the two forms of knowledge is a big challenge. We propose a brain-inspired knowledge representation approach called ViewpointS where formal data and informal contributions are merged into an adaptive knowledge graph which is then topologically, rather than logically, explored and assessed. We firstly illustrate within a mock-up simulation, where the hypothesis of knowledge emerging from preference dissemination is positively tested. Then we use a real-life web dataset (MovieLens) that mixes formal data about movies with user ratings. Our results show that ViewpointS is a relevant, generic and powerful innovative approach to capture and reconcile formal and informal knowledge and enable collective intelligence.

Introduction

Formal data is supported by means of specific languages, e.g., the chemical description of an organic compound or the conceptual model of a relational database. Mastering the syntax and semantics of such a language is therefore a strong pre-condition for turning the data into knowledge. This happens to be a serious obstacle on the path towards shared understanding and collective intelligence. The phenomenon is well known in computer science: despite significant investment in modelling languages such as Unified Modeling Language, the dialog between final users and software analysts remains painful and sometimes sterile [START_REF] Anthony | 37 Things that Don't Work in Object-Oriented Modelling with UML[END_REF]. The phenomenon is even more accurate in multidisciplinary contexts. For example, when tight collaboration and mutual understanding is required between senior chemists and computer scientists building an electronic encyclopaedia [START_REF] Krief | Building the EnCOrE dictionary collaboratively: strategy and practice[END_REF][START_REF] Lemoisson | Interactive Knowledge Construction In The Collaborative Building Of An Encyclopedia[END_REF]. Cross connecting ontologies in order to obtain machine-readable data (the so called semantic Web) is a sticking point, due to the fact that each ontology's evolution is domain-dependent [START_REF] Karapiperis | Consensus building in collaborative ontology engineering processes[END_REF]. Even when the ontologies belong to the same domain (e.g., biomedicine), finding the right language (e.g., an ontology) for annotating a specific dataset is in itself a challenge as illustrated in [START_REF] Jonquet | Building a Biomedical Ontology Recommender Web Service[END_REF]. Shared understanding of formal data, i.e., yielding to the semantic Web (Berners- [START_REF] Berners-Lee | The Semantic Web[END_REF]) is a key issue, even more when societal problems require a multidisciplinary treatment. In contrast, informal knowledge relies on weak/ambiguous contributions such as "I recommend this paper" or "you should try with this keyword" or "on this topic, you should meet this researcher". Such contributions can never be assessed correct or fully reliable, nevertheless they do play a key role in our daily lives, even in our scientific lives, for instance when a colleague recommends a paper, or a subject of investigation, or another colleague. They express most of the time spontaneous answers to the basic need of socializing [START_REF] O'reilly | What is Web 2.0[END_REF]; it also happens that they are collected with a scientific purpose, e.g., when stakeholders are asked to draw in turn, on a shared map, their personal view about the local context [START_REF] Saquali | The PBRM (perception-based regional mapping): A spatial method to support regional development initiatives[END_REF]. Within the social Web, folksonomies and recommendations emerge on top of countless subjective personal views; these structures are unfortunately not actionable in the logical paradigm, because of their lack of semantics, and absence of centrally controlled coherence [START_REF] Mikroyannidis | Toward a social semantic web[END_REF][START_REF] Lux | From folksonomies to ontologies: employing wisdom of the crowds to serve learning purposes[END_REF]. Reconciling the two forms of knowledge is a big challenge and significant efforts have been made to bridge the gap between the so-called semantic and the social Web [START_REF] Edelman | Collective knowledge systems: Where the Social Web meets the Semantic Web[END_REF]. It is for instance a major issue for the Web science community today [START_REF] Hendler | Web Science: An interdisciplinary approach to understanding the World Wide Web[END_REF]. Facing this issue, [START_REF] Breslin | Social semantic Web[END_REF] envisage two options which might be called respectively "postformalizing" and "pre-formalizing" the informal content:

• The first option [START_REF] Bojārs | Using the Semantic Web for linking and reusing data across Web 2.0 communities[END_REF][START_REF] Chein | Graph-based Knowledge Representation: Computational Foundations of Conceptual Graphs[END_REF]) consists in translating social data into the semantic Web. Close to this first option, some authors [START_REF] Aberer | Emergent Semantics Principles and Issues[END_REF]) promote the bottom-up evolution of ontologies by synthetizing the results of user interactions, e.g., building a lexical resource by aligning the vocabularies of patients and health professionals [START_REF] Donald | Construction d ' un vocabulaire patient / médecin dédié au cancer du sein à partir des médias sociaux[END_REF]. However, the parallel and independent evolutions of social Web contents and ontologies make this kind of bridging delicate to maintain [START_REF] Uren | Semantic annotation for knowledge management: Requirements and a survey of the state of the art[END_REF]), [START_REF] Mika | Ontologies are us: A unified model of social networks and semantics[END_REF][START_REF] Mikroyannidis | Toward a social semantic web[END_REF]). • The second option consists in leveraging Web 2.0 services to feed the semantic Web, e.g., integrating structured data for describing movies when rating them [START_REF] Ankolekar | The two cultures: Mashing up Web 2.0 and the Semantic Web[END_REF]. However, spreading standards within the open world of Web 2.0 may seem challenging, if not questionable. To reconcile the two ecosystems however is the key of a collective knowledge system in the sense coined by Gruber in (Gruber 2008): a collective knowledge system provides tailored advice on top of collected knowledge, structured data and high level automated expertise able to bring in new levels of understanding.

In this paper we propose a brain-inspired knowledge representation approach where formal data and informal contributions are merged into an adaptive knowledge graph which is then topologically, rather than logically, explored and assessed. Our approach called ViewpointS aims at yielding such a system by: (i) merging informal and formal knowledge into a unified knowledge graph following the brain metaphor, (ii) empowering feedback and learning processes and (iii) providing means for assessing/qualifying the emerging collective knowledge. ViewpointS relies on three assumptions:

1. A viewpoint is a subjective connection between two objective knowledge resources; the aggregation of these connections between two given resources can be viewed as a synapse between two neurons; 2. The knowledge graph or "associative memory" formed by all the viewpoints (formal versus informal, proactive versus reactive) is a selectionist system evolving continuously according to user's interactions in the metaphor of a collective brain: each interaction is equivalent to the tuning of a synapse; 3. The topological structures which appear when adopting a user's perspective actualize assessable knowledge. Our conceptual framework is inspired from the social Web: it builds upon connections established by "agents" about "things" (resources or persons); moreover it records the provenance of each connection as a mean to ensure trustworthiness. Due to the associative nature of the memory built upon the connections, it continuous evolves along the interactions of the contributors. Rather than undertaking logical assessment (incompatible with informal content), we define perspectives (sets of quantification rules tuned to the interpretation of the user's context, which apply on the viewpoints) and topologically explore the knowledge map resulting from such an interpreted knowledge graph. In this paper, we propose and define the ViewpointS formalism supporting the storage, exploitation and assessment of collective knowledge. We firstly illustrate within a mock-up simulation, where the hypothesis of knowledge emerging from preference dissemination is positively tested. This proof of concept is then checked against a real-life web dataset (MovieLens) that mixes formal data about movies with user ratings. Our results show that ViewpointS is a relevant, generic and powerful innovative approach to capture and reconcile formal and informal knowledge as well as a step forward in assessing and exploiting collective intelligence. The rest of the paper is organised as follows. Section 2 presents our sources of inspiration within the state of the art. Section 3 gives a detailed presentation of the formalism supporting the storage, exploitation and assessment of knowledge. In section 4, a first proof of concept is given: we assess collective knowledge emerging from serendipitous learning through a mockup simulation called "The three princes of Serendip". In section 5, we validate our hypothesis by processing the MovieLens dataset about movies descriptions and ratings. We firstly exhibit the topological structure reflecting the formal knowledge about movies, then input informal knowledge issued from user ratings and study the plasticity of the topological structure under distinct perspectives. Finally, section 6 summarizes the key novel aspects and value added and discusses directions for future work.

Related work and inspirations

Starting from the question of 'knowledge', a major source of inspiration has been the Theory of Neuronal Group Selection [START_REF] Edelman | Selective networks capable of representative transformations, limited generalizations, and associative memory[END_REF]Edelman n.d.;[START_REF] Edelman | Collective knowledge systems: Where the Social Web meets the Semantic Web[END_REF] which recently re-appeared in the front scene under the name of 'connectome' (Seung 2012). According to this theory, the human brain is not a store of fixed or coded attributes to be called up and assembled as in a computer; instead, it results from a process of continual recategorisation within a network (the cortex) of about 30 billion neurons and 1 million billion synapses. One central and striking assumption in this theory is that most of the brain global/macro capacities rely on a single local/micro mechanism: the variation of the synapses' strengths as a feedback of individual value-systems to experience. In ViewpointS, the key idea is twofold: (i) the unit of knowledge is a connection (we call it viewpoint) between two knowledge resources (as defined in 3.1); and (ii) the wiring harness of viewpoints between a given pair of knowledge resources plays the role of 'synapse interconnecting two neurons'; we therefore call it synapse. We de facto abandon conceptual models such as [START_REF] Chein | Graph-based Knowledge Representation: Computational Foundations of Conceptual Graphs[END_REF] and rule-based approaches such as [START_REF] Noh | Learning the emergent knowledge from annotated blog postings[END_REF]). Instead we allow the emergence of collective knowledge in a selection process analogue to that described in (Edelman n.d.), by letting each individual reflect his/her own understanding and/or feedback through the emission of new viewpoints updating the synapses. Such selection processes exist in various contexts of the social Web: learning character recognition through Recaptchas [START_REF] Von Ahn | reCAPTCHA: human-based character recognition via Web security measures[END_REF], evolving folksonomies [START_REF] Krause | Playful Tagging -Folksonomy Generation Using Online Games[END_REF], building powerful semantics on top of lexical data [START_REF] Lafourcade | Making people play for Lexical Acquisition with the JeuxDeMots prototype[END_REF], recommending [START_REF] Adomavicius | Toward the next generation of recommender systems: a survey of the state-of-the-art and possible extensions[END_REF]. In this paper, we propose to implement a generic, context-free, selection process accepting both formal data and informal contributions. When going into the syntactic aspects, our starting point was from the recent shift in the Web paradigm bringing the contributor back in the loop [START_REF] O'reilly | What is Web 2.0[END_REF]. Bringing back the contributor can be done at a global/macro level through the notions of 'provenance' (https://www.w3.org/TR/prov-o) and 'named graphs' [START_REF] Carroll | Named graphs, provenance and trust[END_REF]). Or at the local/micro level by extending the traditional bipartite model of ontologies with a social dimension. For instance, [START_REF] Mika | Ontologies are us: A unified model of social networks and semantics[END_REF]) presents a tripartite model actor-concept-instance based on the commitment of a user in terms of classifying an instance as belonging to a certain concept. Quite emblematic of this local/micro level storage of the provenance is the social tagging system Flickr built upon three dimensional units representing agent/user contributions in terms of tags associated to resources/images: agent-resource-tag. It is interesting to note that contributor-centred views based on triples made their way simultaneously in the semantic and social Web, but with distinct goals and formalisms (Weinberger 2011). Whereas the triples of [START_REF] Mika | Ontologies are us: A unified model of social networks and semantics[END_REF] secured the possibility of structure and hierarchy by preserving the central notions of concept and instance, the triples of social tagging systems are deprived from any directly specified parent-child relationship and lead to folksonomies characterised by the absence of hierarchy and lack of semantics [START_REF] Mikroyannidis | Toward a social semantic web[END_REF] [START_REF] Lux | From folksonomies to ontologies: employing wisdom of the crowds to serve learning purposes[END_REF]. In ViewpointS, we started from a tripartite model agent-resource-tag generalizing Flickr by expressing 'the belief of an agent that the tag is appropriate with respect to the resource'. It should be noted that the classical denotation of viewpoints as beliefs, such as [START_REF] Self | Computational Viewpoints[END_REF][START_REF] Anthony | 37 Things that Don't Work in Object-Oriented Modelling with UML[END_REF] was deliberately oversimplified in order to yield a topological, rather than logical, exploitation of the "wisdom of the crowd" in a manner similar to [START_REF] Mika | Ontologies are us: A unified model of social networks and semantics[END_REF][START_REF] Markines | Evaluating similarity measures for emergent semantics of social tagging[END_REF][START_REF] Specia | Integrating Folksonomies with the Semantic Web[END_REF]. We then made one decisive step by replacing the triple agent-resource-tag by the more abstract triple agent-resource-resource in which agents may themselves be resources. Based on these complementary influences, we have set the conditions of a selection process operating on top of the agent-resource-resource triples by aggregating all the triples connecting two given knowledge resources into higher level binary links called synapses; those build knowledge maps where the notion of 'semantic proximity' can be defined. The notions of 'semantic similarity' or 'semantic proximity' are central in the contexts of annotation, disambiguation, concept alignment or information retrieval [START_REF] Harispe | The Semantic Measures Library and Toolkit : fast computation of semantic similarity and relatedness using biomedical ontologies[END_REF][START_REF] Lee | Comparison of ontology-based semantic-similarity measures[END_REF], [START_REF] Pedersen | Measures of semantic similarity and relatedness in the biomedical domain[END_REF]. As surveyed in [START_REF] Markines | Evaluating similarity measures for emergent semantics of social tagging[END_REF], various similarities can be defined within triples, sometimes recursively, e.g., in (Quattrone et al. n.d.): "two tags are similar in that they link similar resources and two resources are similar in that they are linked by similar tags". We made the hypothesis that any user's context could be translated into a set of quantification rules for the viewpoints and called such a set a perspective; this is in line with [START_REF] Kim | The state of the art in tag ontologies: a semantic model for tagging and folksonomies[END_REF] where it is written that "ontologies should be evaluated with respect to a particular goal, application or scenario rather than merely for the sake of an evaluation". Once a perspective is adopted, the initial heterogeneous semantics carried by the viewpoints are transformed into proximities within a knowledge map. As a consequence, the agents can use the viewpoints of others (transformed into proximities) when browsing knowledge maps and reversely update the knowledge graph through viewpoints expressing their feedback. Along these exploitation/feedback cycles, the shared knowledge is continuously elicited against the beliefs of the agents in a selection process supported by the evolving strength of synapses, as it happens in the brain [START_REF] Edelman | Collective knowledge systems: Where the Social Web meets the Semantic Web[END_REF]. We have previously demonstrated [START_REF] Lemoisson | Viewpoints: An Alternative Approach toward Business Intelligence[END_REF] the learning ability of a knowledge base implementing this conceptual framework and showed how it allows the search and discovery of knowledge through a search engine prototype for scientific publications (Surroca et al. 2014). We have also assessed the diffusion of preference systems resulting from this selection process (Surroca et al. 2015): we simulated 'proximity-guided serendipity' in the context of several scenarii parametrized by the degree of acceptance of resources outside one's own preference system.

Conceptual framework, formalism and knowledge assessment

In this section, we first present a conceptual framework, then a formalism where the formal and the informal merge into a unified and adaptive memory, and we finally propose means exploiting the topology of the memory in order to assess collective knowledge. This formalism has been implemented in Java; it is publicly available at: https://github.com/sifrproject/viewpoints_kernel

Conceptual framework

The ViewpointS approach elaborates upon the connections, established by the members of a community, between pairs of objects of interest called "knowledge resources". The highlevel ontology shown in Figure 1 introduces the knowledge resources and the roles they play. A knowledge resource can be:

• either an object, i.e., either a world entity such as a person, a company, a spatial entity, a monument … or a numeric entity hosted by a computer, such as a Web page or an algorithm, i.e., an entity belonging to the 'numeric matter' as coined by [START_REF] Vial | L'être et l'écran -Comment le numérique change la perception[END_REF]); • or a descriptor, i.e., a meaningful expression within a language such as a keyword, an item in an ontology, a topic. The distinction between objects and descriptors implicitly refers to the position adopted by J. Searle in (Searle 1969)1 . Besides, a knowledge resource may participate to knowledge construction through three possible roles: i) "tag": this role is played by descriptors qualifying objects, ii) "knowledge container": this role is played by objects embedding some knowledge or iii) "knowledge provider": this role is played by objects delivering knowledge. All knowledge resources are identified by an URI; numeric entities have URLs.2 All knowledge resources have a "preview": in the case of a numeric entity a preview service will be provided by the browser accessing the URL; in the case of world entities, at least one numeric preview is requested; in the case of descriptors, an simple explicit identifier stands for preview, e.g., "Fujiyama", "majestuous."

In the use cases we have handled so far, knowledge resources belong to five mutually exclusive classes:

• Legal person: world entity "performing acts and undertaking obligations" [START_REF] Carroll | Named graphs, provenance and trust[END_REF]; it can play two roles: "knowledge provider" when creating connections or "knowledge container" as a connectable object. • Artificial agent: numeric entity creating connections in the role of "knowledge provider" or playing the role of "knowledge container" as a connectable object. • Physical document: world entity playing the role of "knowledge container", such as a real book on a real shelf. • Numeric document: numeric entity playing the role of "knowledge container", such as a tweet or a Web page. • Descriptor: meaningful linguistic expression playing the role of "tag". In the following, we shall write agent to designate indifferently a legal person or an artificial agent, i.e., potential knowledge providers. The ViewpointS approach elaborates upon the connections established by agents between couples of knowledge resources. For instance, when an internaut tags an image with a keyword in Flick'r, we consider that an agent (the internaut) connects a numeric document (the image) to a descriptor (the keyword). In a similar way, when I upload in an open archive the reference of a book authored by myself, we consider that an agent (myself) connects a physical document (the book) to an agent (myself); in that latter case, the same agent plays the two roles of "knowledge provider" and "knowledge container". Each of these connections reflects the beliefs of a given agent/subject, i.e., it is subjective by nature; we reify/objective it and call it viewpoint. As illustrated in Figure 2, a viewpoint keeps track of the provenance of the connection (the agent playing the role of "knowledge provider"); it has a type 'q' ('index', 'author', 'like' …) and a time stamp 't'.

Formalism

Let R be a set of knowledge resources, let a1 be an agent taken in R, r2 and r3 two arbitrary elements of R, let t be a standard time stamp, let q be formed of two parts: i) a polarity indicating whether the proximity between the knowledge resources should be reinforced (positive polarity) or weakened (negative polarity) and ii) semantics, such as standard unambiguous semantic Web properties e.g., foaf:knows, cv:jobType. In this paper, we consider only positive polarities and shall therefore omit them e.g., we denote 'matches' instead of '(+, matches)'; q is called the type of the viewpoint,

The viewpoint (a1, {r2, r3}, q, t) stands for: the agent a1 believes at time t that r2 and r3 are related according to the semantics carried by the type q.

a1=EmitterOf(w); {r2,r3}=ConnectedBy(w).

We denote W the set of all viewpoints.

Let EDGES be the set of all links woven between the viewpoints and the knowledge resources:

EDGES={(a,w)| wÎW; a=EmitterOf(w)} È {(w,r)|wÎW; rÎConnectedBy(w)}.
The knowledge graph is the bipartite graph built by taking each viewpoint and linking it to its emitter and connected resources:

KGR,W = (RÈW, EDGES)
For instance, let G3, B7 and G5 (respectively a big green circle, a big blue square and a small green circle) be world entities, let peon-size be an agent detecting sizes, let princeBlue be an agent fond of blue, let 'big' and 'small' be descriptors, the four viewpoints illustrated in Figure 3 express the following knowledge:

peon-size believes that G3 matches 'big' peon-size believes that B7 matches 'big' peon-size believes that G5 matches 'small' princeBlue believes that princeBlue likes B7 In order to exploit the knowledge, we build perspectives defining rules for quantifying the viewpoints. It may be default rules adopted by a group of users in a recurrent context e.g., information retrieval, or specific rules filtering KGR,W according to preferences such as: ignoring the viewpoints anterior to a given date, privileging the viewpoints emitted by some agents or privileging viewpoints of a given type.

The preliminary step in building a knowledge map consists in grouping all the viewpoints connecting any given pair of knowledge resources into a higher level link called a synapse. We denote S the set of all synapses. We also consider the synapse function:

. synapse: R 2 ®2 W (r1,r2)®{wÎW|Connected(w)={r1,r2}} Setting a perspective U consists in defining rules for valuating each synapse. We consider two functions U map and U reduce and combine them into U synapse. . U map evaluates each viewpoint w of the synapse individually, as a function of 'q', 't' and 'EmitterOf(w)'.

. U reduce aggregates all the U map results into a single positive or null value; it may be a simple sum or a sophisticated function with a threshold or attenuation. U synapse is finally the composition of 3 functions:

. U synapse: R 2 ®Â+ IF synapse(r1,r2)==AE THEN U synapse (r1,r2)=0 ELSE U synapse(r1,r2)= U reduce( U map(synapse (r1,r2))) .

We call knowledge map and denote U KMR,S the undirected labelled graph interpreting KGR,W through the perspective U. The vertices are the knowledge resources. An edge is built for each U synapse (r1,r2)>0. One single KGR,W will therefore be interpreted into several distinct U KMR,S depending on the perspective adopted. In order to exhibit knowledge in U KMR,S, we exploit its topology with standard graph algorithms taking into account the perspective U. We firstly consider a metric semantic distance called SBPD (for "shortest bounded path distance"). SBPD scans all the paths between two given resources, using Dijkstra's algorithm for exploration, filters all paths exceeding a threshold and computes the shortest path. Therefore, the worst case complexity of the algorithm is O(|W|²|R|²); however this complexity is not reached because the spreading is cut as soon as the distance exceeds the bound. Alternative distances can be defined, such as MBPD (for "multi bounded paths distance"). MBPD scans all the paths between two given resources, filters those exceeding a threshold, computes the synapse equivalent to the maximal flow and then computes the distance according to this synapse. We use the following definitions: Given a perspective U and a distance U Y defined on R 2 , given a knowledge resource 'r', given a parameter 'm', we call neighbourhood of 'r' and we denote U,m Y-neighbours(r) the set of all knowledge resources such as: U Y(x, r)£ m. 'm' is called the radius of the neighbourhood.

KG R,W U KM R,S U synapse(r 1, r 2 )=5 U perspective U map U map(w 1 )=2 U map(w 2 )=3 U map(w 3 )=0 U reduce U reduce(2,3,0)=5 r 1 r 2 r 1 r 2 w 1 w 2 w 3

Assessment of the collective knowledge

Assessing knowledge may seem a hazardous enterprise in a context characterized by weak semantics. Whereas standard measurements exist in the case of explicit information retrieval (e.g., precision at position 'n', mean average precision, and normalized discount cumulative gain, as listed in [START_REF] Qin | LETOR: A benchmark collection for research on learning to rank for information retrieval[END_REF])), it is hopeless to try and assess the relevance of a knowledge resource when it is encountered serendipitously. Similarly, whereas knowledge acquisition can be measured in face of explicit pedagogical objectives, these measures do not apply to informal contexts. Assessing informal learning remains an open issue, despite a great deal of research work [START_REF] Sefton-Green | Literature Review in Informal Learning with Technology Outside School[END_REF]. Our objective in this section is to provide a generic measure for assessing knowledge in the absence of any explicit conceptual schema, i.e., relying upon the topology only. Let us suppose a use case where internauts are browsing through a movie dataset, guided only by the proximities between knowledge resources. If the immediate neighbours of each currently displayed object/movie are statistically of same descriptor/genre, internauts will tend to visit movies 'of same genre', i.e., they will learn 'genres' despite they do not use the concept of 'genre' in their browsing. This phenomenon is typical of recommender systems [START_REF] Adomavicius | Toward the next generation of recommender systems: a survey of the state-of-the-art and possible extensions[END_REF], [START_REF] Yamaba | On a serendipity-oriented recommender system based on folksonomy[END_REF]. We may therefore consider that according to the settings of this use case, the objects/movies are "sorted by" descriptors/genres.

In a more general way, we study how a collection 'O' of knowledge resources (e.g., a collection of objects) can be sorted according to another collection 'K' (e.g., a collection of descriptors). The idea is the following: if close elements of 'O' are locally homogeneous with respect to 'K', i.e., have similar elements of 'K' in their respective neighbourhoods, then 'the collection O is sorted according to the collection K'. We take the following definition: Let U be a perspective, let U Y be a distance defined on R 2 , let 'm' be the radius of neighbourhoods, let O={oi}iÎ|O| and K ={kj}jÎ|K| be two collections of knowledge resources, we denote K(oj) the vector {k j (oi)}jÎ|K| of dimension |K| such that k j (oi)=number of occurrences of 'kj' in U,m Y-neighbours(oi). U,m,K localHomogeneity(O)is the average value of cosine similarity (K(o1), K(o2)) computed upon all the pairs(o1,o2)verifying U Y(o1,o2)£ m. If U,m,K localHomogeneity(O)=1, we have an information: when two elements of O are U,m Yneighbours, they are also U,m Y-neighbours of the same elements of K, i.e. they are "described identically by K"; if U,m,K localHomogeneity(O)=0, we have no information about the description of O by K. In this definition, the radius 'm' stands for the precision of the knowledge map; our hypothesis is that the radius is a key factor in the knowledge assessment. We firstly test this hypothesis on a mock-up in section 4, and then on a real Web dataset in section 5.

Learning colours: "The three Princes of Serendip" simulation

Objective of the simulation

The objective of the simulation is three-fold: a) illustrate how the ViewpointS formalism captures formal data and informal contributions into an adaptive knowledge graph; b) topologically assess knowledge emerging from serendipitous preference dissemination; c) study the importance of the radius in the knowledge assessment. "The three Princes of Serendip" is a simulation based on a knowledge graph populated with coloured geometrical objects (denoted 'objects' in the following), descriptors and agents.

The formal knowledge is represented by connecting the objects to descriptors about shapes and sizes ('square', 'triangle', 'circle', 'big', 'medium', 'small'). The colours are not formally represented. Serendip is a world where the notion of colour is absent: the descriptors 'red', 'blue', 'green' do not exist in the knowledge graph. However three agents (the princes), each with the ability to discriminate one specific colour, disseminate their respective preferences via viewpoints; these serendipitous connections stand for the informal knowledge. In this section, we firstly illustrate the formalism, and then track the progressive apparition of the notion of colour, as a consequence of the dissemination of the princes' preferences.

In the Serendip simulation, we adopt the default perspective U 0 : i) each viewpoint is weighted 1 and ii) the aggregation function computing the value of synapses is the sum function.

Description of the simulation

The simulation involves two kinds of agents: the peons and the princes. The formal knowledge about shapes and sizes is represented by viewpoints of type vps:matches emitted by peon-size and peon-shape. Doing so, they weave at t0 an initial graph where each object is connected to two descriptors qualifying its size and its shape. The lower part of Figure 5 illustrates six viewpoints expressing this formal knowledge:

(peon-size,{G5,small}, vps:matches,t0) (peon-size,{B7,big}, vps:matches,t0) (peon-size,{G3,big}, vps:matches,t0) (peon-shape,{G5,circle}, vps:matches,t0) (peon-shape,{B7,square}, vps:matches,t0) (peon-shape,{G3,circle}, vps:matches,t0)

The upper part of Figure 5 illustrates the knowledge map under the perspective U 0 . The informal knowledge about colours is represented by viewpoints of type vps:likes emitted by the princes of Serendip, namely princeRed, princeGreen and princeBlue. Each prince has the ability to discriminate one specific colour and will react only to this colour during his serendipitous explorations. This is simulated by encoding the colour in the names of the geometrical objects: R (for "Red"), G (for "Green"), and B (for "Blue"). The lower part of Figure 6 illustrates an extension of the previous knowledge graph resulting from the input of three viewpoints by the princes:

(princeGreen,{princeBlue,G5}, vps:likes,t1) (princeGreen,{princeBlue,G3}, vps:likes,t2) (princeBlue,{princeBlue,B7}, vps:likes,t3)

Figure 6: The princes emit informal knowledge

The upper part of Figure 6 illustrates the updated knowledge map under the perspective U 0 . We compare in Figure 7 the neighbourhood of G5 before (left side) and after (right side) the interactions of the princes. Using SBPD, the new path added on the right side of Figure 7 by the new neighbour 'princeGreen' is not shorter that the initial path: the distance between 'G3' and 'G5'is '2' on both sides; as a consequence the SBPD distance remains unchanged.

Formal knowledge only Formal knowledge + informal knowledge

SBPD(G3,G5)=2 1 SBPD-neighbours(G3)= {small, circle} MBPD(G3,G5)=2 1 MBP-neighbours(G3)= {small, circle} SBPD(G3,G5)= 2 1 SBPD-neighbours(G3)= {small, circle, princeGreen} MBPD(G3,G5)=1 1 MBPD-neighbours(G3)= {small, circle, princeGreen, G5}
Using MBPD, we have MBPD(G3,G5)=2 on the left whereas MBPD(G3,G5)= 1/((2*2)/(2+2))=1 on the right; as a consequence the MBPD distance decreases when the informal knowledge input by princeGreen appears. We adopt in the next section a protocol simulating a continuous flow of informal knowledge emitted by the princes in order to study this aspect in more details and test our hypothesis concerning the importance of the precision.

Protocol and measurements

We consider a set of 270 geometrical objects so that each of the 27 combinations of size, shape and colour is represented 10 times. 'small', 'medium', 'big' are encoded in the object names by 's', 'm', 'b'; 'square', 'triangle', 'circle' by 'q', 't', 'c' and 'red', 'green', 'blue' by 'R', 'G', 'B', e.g., 'bBq205'is a big blue square.

We firstly initialise the knowledge graph by the formal knowledge of shapes and sizes provided extensively by peon-size and peon-shape.

Then the three princes deliver the informal knowledge along N cycles "cycles" of interactions simulating serendipitous trips. A "cycle" is defined as follows:

-a cycle consists in N trips "trips" -a trip consists in: i) choosing a prince randomly with the probabilities p Red for princeRed, p Green for princeGreen, p Blue for princeBlue and ii) let the chosen prince choose an object at random and then go through N interactions "interactions" -an interaction of one prince consists in: i) evaluating the current object and ii) choosing a new object within the U,m Y-neighbours of the current object with a distribution of probabilities corresponding to their respective proximities; this corresponds to a serendipitous exploration in breadth.

evaluating an object consists in emitting a viewpoint of type vps:likes in case its codedcolour corresponds to the preference of the prince.

In the whole simulation the chosen perspective is U 0 described above, the distance function is SBPD described above.

The measurements are applied at the end of each cycle. Let us denote O the population of all objects. Let us denote 'Shapes' the collection of descriptors {'square', 'triangle', 'circle'}. In order to assess formal knowledge, we measure:

U0,m,Shapes localHomogeneity(O)
In order to assess informal knowledge, we assimilate the princes to the colours they prefer and denote 'Colours' the collection {'princeRed', 'princeGreen', 'princeBlue'}. We measure:

U0,m,Colours localHomogeneity(O)
Two series of runs of the simulation, designated by RUN1,m an RUN2,m, are presented hereunder, where 'm' is the radius. RUN1,m corresponds to a balanced activity of the three princes (pRed= pGreen= pBlue= 33,33%) i.e., the three colours are equally diffused. RUN2,m corresponds to the exclusive activity of princeRed (pRed= 100%) i.e., only the implicit knowledge of the red colour is diffused. 'm' takes the values: '1.5', '2', '2.5', '3', '3.5' and '4'.

Results and discussion

Figure 8 illustrates the two series of parallel runs. Each RUNi,m is illustrated by two curves respectively measuring U0,m,Shapes localHomogeneity(O), and U0,m,Colours localHomogeneity(O) along 12 cycles corresponding to successive flows of contributions from the princes expressing their preferences (informal knowledge). In the discussion, we simply denote

Shapes lH(O)and Colours lH(O).

A first observation is that the minimum for both measures is 0.33 whatever the radius 'm', except in the RUN2,m with m>2. This is a direct consequence of the symmetry of this toy example: 0.33 is the probability of having an object with same shape, or same colour, in the neighbourhood of a given object when all the knowledge about shapes and colours has been symmetrically expressed.

A second observation is that Shapes lH(O)always decreases along the cycles. We interpret it as a competition between the sorting by shapes and the sorting by colours.

A third observation is that Colours lH(O)is always higher in RUN1,m compared to RUN2,m. This can be interpreted as: "the graph learns/sorts colours better when 3 teachers are promoting 3 colours than with 1 teacher is favouring 1 colour". Going into to the discussion about the key values of the radius 'm' in the U0 perspective:

-as long as m<2, the formal knowledge is undetectable (the synapses linking two objects of same shape through peon-shape are bounded by '1'; peon-shape never qualifies twice a given object, thus SBPD distances are ³2, see Figure 7) . Only the informal knowledge is detected (each prince is allowed to qualify a given object several times, which yields shorter distances). -when 2£m<4, the formal knowledge is detected ( Shapes lH(O) takes high values at cycle0); the competition starts between the two sortings. -when m>2, the informal knowledge becomes messy because of the great number of close neighbours brought in by the reiterate evaluations of the princes. -when m³4, the minimum 0.33 is reached for both measures. Even the formal knowledge becomes messy because objects of different shapes become neighbours by transitivity: the local homogeneity is lost. For instance, consider the path bBq5-square-bBq2-big-bGt7 linking a 'big blue square' to a 'big green triangle' through another 'big blue square', firstly because of the shape, then because of the size, SPBD (bBq5, bGt7)=4; as a consequence, a blue square and a green triangle are neighbours.

We can summarize this part of the discussion by saying that in the U0 perspective, 1£m<2 is the relevant radius range for sorting the objects by colours, whereas 2£m<4 is relevant for sorting the objects by shapes.

Recapitulating the answers to our initial questions:

-the serendipitous preference dissemination by the princes yields a (informal) knowledge of colours that comes in competition with the (formal) knowledge of shapes; -this phenomenon can be observed only when adopting the relevant "precision" (radius). The next section is aimed at checking our hypotheses against real data.

The MovieLens experiment

Objective of the experiment

In this section, we take a Web dataset where formal knowledge issued from explicit semantics is mixed with informal knowledge issued from social contributions: MovieLens (http://datahub.io/dataset/movielens). The complete dataset consists of 100.000 movies and 1.000.000 ratings which have been collected by the GroupLens Research Project at the University of Minnesota. Their data have played the role of experimental matter for many authors such as [START_REF] Peralta | Extraction and integration of movielens and imdb data[END_REF][START_REF] O'connor | Clustering items for collaborative filtering[END_REF][START_REF] Harpale | Personalized active learning for collaborative filtering[END_REF], mostly in the context of studies about collaborative filtering methods for recommendation. A corpus of sophisticated measurements and analyses is available in different research works such as [START_REF] Jung | Attribute selection-based recommendation framework for short-head user group: An empirical study by MovieLens and IMDB[END_REF]. In this section, we experiment with three objectives: a) to illustrate how a Web dataset can be transcribed into a knowledge graph; b) to illustrate the role of perspectives in the topological sorting of objects; c) to assess concurrence or complementarity between a classification of movies by 'genres' and a classification through 'ratings'.

Modelling the MovieLens data

Figure 9 has been borrowed from [START_REF] Peralta | Extraction and integration of movielens and imdb data[END_REF] to describe the conceptual schema of the Web dataset. The red frames show the matching with Figure 10. The red frame shows the matching with Figure 9. The systematic use of standard unambiguous semantic Web properties in the transcription process, e.g., mo:genre, foaf:gender, automatically provides a shared language, than can be exploited for building specific perspectives. For instance, the prefix 'mo:' identifies the Movie Ontology (www.movieontology.org) which unambiguously defines the meaning of the resources and properties used within this dataset. By systematically using such tags, we enable ViewpointS to embrace the semantic Web standards and import/export RDF representations.

Protocol and measurements

We take an extract of the original dataset: 1682 movies rated by 943 commenters providing 5.000 ratings. We firstly initialise the knowledge graph by transcribing the formal knowledge. There are 1682 movies and 943 users. Each movie is linked to one or more of the 18 genres (2 genres is the average) and to one year; each user is linked to one age, one gender, and one occupation. Measures (cycle0, m=1) and Measures (cycle0, m=2) are operated immediately after this initialization, where'm' denotes the radius chosen for computing neighbourhoods. We then arbitrary split the ratings into 5 subsets of 1000 ratings to be input as informal knowledge. Each run of the experiment will consist in transcribing these subsets one by one along five successive cycles. Measures (cyclei, -Ui,m,Genres localHomogeneity(M) -Ui,m,Ratings localHomogeneity(M)

In this experiment, the distance function is SBPD; 'm' denotes the radius chosen for computing neighbourhoods. Three series of RUNs designated by RUN1,m , RUN2,m and RUN3,m are presented hereunder. Each RUNi,m corresponds to a perspective Ui. Whatever Ui, the U reduce function is the sum; the perspectives differ only by the U map functions.

U1 corresponds to priority given to formal knowledge, i.e., vpml:rating are weighted 1 by U map and all other viewpoints are weighted 3.

Results and discussion

The upper part of Figure 11 presents the 6 runs RUN1,1 to RUN3,2; the lower part of the figure presents RUN1,1, RUN2,2 and RUN3,2 in more details.

Ui,m,Genres localHomogeneity(M) and Ui,m,Ratings localHomogeneity(M) are drawn for each run. We first compare the values for cycle0, when ratings are absent of the knowledge graph. In the perspective U1, U map='3' for viewpoints of type mo:genre yielding strong synapses between movies and genres. In consequence, the suitable radius for observing Genres lH(M) is 'm=1', not 'm=2'. When we use the radius 'm=2' in the computation of SBPD, distinct genres become close by transitivity through movies, so that movies become in turn close by transitivity through genres; movies' neighbourhoods become heterogeneous in genres i.e., Genres lH(M) becomes low.

In the perspectives U2 and U3, U map='1' for viewpoints of type mo:genre. The suitable radius for observing Genres lH(M) is 'm=2', not 'm=1'. When we use the radius 'm=1'in SBPD, movies stay far from genres, thus movies of same genre are not brought into in the same neighbourhood by transitivity; movies' neighbourhoods stay heterogeneous in genres i.e., Genres lH(M) stays low.

Looking at cycle1 to cycle5, we observe that both 'm=1' and 'm=2' are suitable, although Ratings lH(M) is better observed when 'm=1'.

According to this preliminary observations, only RUN1,1, RUN2,2 and RUN3,2 (lower part of Figure 11) can be used for comparing the simultaneous evolutions of Genres lH(M) and Ratings lH(M).

We observe that Genres lH(M) always decreases while Ratings lH(M) always increases. The curves (approximatively) intersect at:

0.32 for RUN1,1 0.35 for RUN2,2 0.34 for RUN2,3 This intersection varies little with the perspective; the highest value '0.35' is nevertheless obtained in the balanced perspective U2. This is quite similar to what has been observed in section 4: the graph better exhibits "knowledge" in balanced conditions (note: what is balanced here in the knowledge map resulting from the perspective chosen, whereas in the Serendip simulation, it was the knowledge graph itself resulting from the princes' interactions) This experiment on a non-symmetrical dataset shows concurrence and complementarity between a classification of movies by 'genres' and a classification through 'ratings'. This is analog to the competition between shapes and colours in the Serendip simulation. It can be interpreted as "genres and ratings are independent sorting dimensions". Moreover, the intersection of curves occurs between cycle3 and cycle4, i.e., after approximatively 5000*3/5=3000 viewpoints of type vpml:ratings, to be compared with 2893 viewpoints of type mo:genre. This can be interpreted as: "ratings are as powerful as genres for sorting movies". Whereas all the curves of the Serendip simulations corresponded to various values of the radius within a single perspective, both the perspective and the radius vary in the MovieLens experiment. A second important result is a refinement of our previous hypothesis: given a perspective, given a question (may a collection O be sorted according to a collection K?), the radius is a key element for answering. Knowledge maps and their topological exploitations via localHomogeneity prove to be useful tools for assessing collective knowledge. Moreover by observing the evolution of a given knowledge map along the interaction of users, we may envisage assessing collective learning.

Conclusion and perspectives

We have presented a model and formalism where both the explicit semantics of the linked data and the informal contributions of Web 2.0 users can be expressed as fine-grained subjective units of knowledge called viewpoints. The set of all viewpoints form an adaptive knowledge graph, which can be put in perspective and yield knowledge maps. We have defined two distances based on the viewpoints' evaluation and aggregation: SBPD and MBPD, and proposed 'localHomogeneity' as a topology-based measure for assessing emergent knowledge. When simulating "The three Princes of Serendip", we have proved the potential of our measurements to capture both the explicitly reified knowledge and the implicit knowledge hidden behind subjective contributions; we have also proved informal learning by watching the evolutions of a knowledge map. We then have tested the approach against real Web data by experimenting with the MovieLens dataset. We have shown the ability of our model to capture the semantics of the data, and compared the impact of the subjective contributions (the ratings) on the formal knowledge under different perspectives. Doing so, we have stepped forward in assessing and exploiting collective intelligence in contexts accepting both formal and informal data. We are currently working on the design of an API offering intuitive browsing of the knowledge and one-click feedback exploiting the context. We are also in search of a benchmark such as those offered on LETOR [START_REF] Qin | LETOR: A benchmark collection for research on learning to rank for information retrieval[END_REF] to evaluate the efficiency of our distance in terms of information retrieval. Finally, in order to automatically elicit the best radius with respect to given question, we are experimenting with genetic algorithms. The next step in our agenda is to prove the concept in real life scenarios, i.e., to invite users to elicit knowledge collectively by using the ViewpointS approach. Evaluation and quality of the knowledge [START_REF] Lichtenstein | Wikipedia model for collective intelligence: a review of information quality[END_REF] will be crucial metrics in those scenarios. Two use cases are planned, both oriented towards cross-disciplinary discoveries: one in the agronomics domain, the other in the biomedical domain, both in the context of ongoing research projects.

Figure 1 :

 1 Figure 1: Knowledge resources

Figure 2 :

 2 Figure 2: The subjective connection called "viewpoint"; the blue arrow gives the provenance, 'q' gives the semantics, 't' gives the time stamp

Figure 3 :

 3 Figure 3: A knowledge graph KGR,W

Figure 4

 4 Figure4illustrates this interpretation process with a perspective U 0 where the aggregation function computing the value of synapses is the sum.

Figure 4 :

 4 Figure 4: Building a knowledge map U KM R, S

Figure 5 :

 5 Figure 5: The peons emit formal knowledge

Figure 7 :

 7 Figure 7: Impact of the informal knowledge SBPD and MBPD are successively used for computing the distances. Under U 0 , all the synapses, consisting of a single viewpoint weighted 1, are valued 1.

Figure 8 :

 8 Figure 8: Compared evolutions of formal knowledge (shapes) versus informal knowledge (colours)

Figure 9 :

 9 Figure 9: The MovieLens conceptual schema To illustrate the transcription of this schema in ViewpointS, we take three examples: • (formal) movie description: the viewpoint (AA-MovieLens,{movieX, genreY}, mo:genre,t)transcribes the fact: the artificial agent 'AA-MovieLens' connects the object 'movieX' to the descriptor 'genreY'• (formal) commenter profile: the viewpoint (userX,{userX,occupationY},cv:jobType,t) transcribes the fact: the legal person 'userX' connects himself to the descriptor 'occupationY'• (informal) rating: the viewpoint (userX, {movieY, ***}, vpml:rating,t) transcribes the fact: the legal person 'userX' connects the object 'movieY' to the descriptor '***' Figure10illustrates the ViewpointS model; the ratings link together two subgraphs representing respectively the formal knowledge of movies' descriptions and users' profiles. The red frame shows the matching with Figure9. The systematic use of standard unambiguous semantic Web properties in the transcription process, e.g., mo:genre, foaf:gender, automatically provides a shared language, than can be exploited for building specific perspectives. For instance, the prefix 'mo:' identifies the Movie Ontology (www.movieontology.org) which unambiguously defines the meaning of the resources and properties used within this dataset. By systematically using such tags, we enable ViewpointS to embrace the semantic Web standards and import/export RDF representations.

Figure 10 :

 10 Figure 10: The ViewpointS model for MovieLens

  m=1) and Measures (cyclei, m=2) are operated at the end of each cycle. Measures (cyclei, m) are specified as follows: Let us denote M the population of the 1682 movies, let us denote Genres the collection of 18 genres provided by MovieLens, let us denote Ratings the collection {*, **, ***, ****, *****}, we compute:

  U2 corresponds to balanced importance of formal versus informal knowledge, i.e., all viewpoints are weighted 1. U3 corresponds to priority given to informal knowledge, i.e., vpml:rating are weighted 3 and all other viewpoints are weighted 1. KG Objects : 1682 'MovieId' + 943 'UserId' Descriptors: 127 formal knowledge: 7471 viewpoints among which 2893 viewpoints of type mo:genre informal knowledge: 5000 viewpoints N cycles =5 'm'=radius RUN1,m perspective U1 formal knowledge: U map(viewpoint)='3' informal knowledge: U map(viewpoint)='1' RUN2,m perspective U2 formal & informal knowledge: U map(viewpoint)='1' RUN3,m perspective U3 formal knowledge: U map(viewpoint)='1' informal knowledge: U map(viewpoint)='3'

Figure 11 :

 11 Figure 11: Compared evolutions of formal knowledge (genres) versus informal knowledge (ratings)

According to J. Searle: i) there is a real world that exists independently of us, independently of our experiences, our thoughts, our language; ii) we have direct perceptual access to that world through our senses, especially touch and vision; iii) words in our language have reasonably clear meanings and can be used to refer to or talk about real objects of the world.

In the semantic web vision, a Uniform Resource Locator (URL) is a specific type of Uniform Resource Identifier (URI) to identify web addresses.

Acknowledgements

This work was supported in part by the French National Research Agency under JCJC program, grant ANR-12-JS02-01001, as well as by University of Montpellier, CNRS and Cirad.


Franco Fusco

Olivier Kermorgant

Philippe Martinet

Improving Relaxation-based Constrained Path Planning via Quadratic Programming

Many robotics tasks involve a set of constraints that limit the valid configurations the system can assume. Some of these constraints, such as loop-closure or orientation constraints to name some, can be described by a set of implicit functions which cause the valid Configuration Space of the robot to collapse to a lower-dimensional manifold. Sampling-based planners, which have been extensively studied in the last two decades, need some adaptations to work in this context. A proposed approach, known as relaxation, introduces constraint violation tolerances, thus approximating the manifold with a non-zero measure set. The problem can then be solved using classical approaches from the randomized planning literature. The relaxation needs however to be sufficiently high to allow planners to work in a reasonable amount of time, and violations are counterbalanced by controllers during actual motion. We present in this paper a new component for relaxation-based path planning under differentiable constraints. It exploits Quadratic Optimization to simultaneously move towards new samples and keep close to the constraint manifold. By properly guiding the exploration, both running time and constraint violation are substantially reduced.

Introduction

Sampling-based planning techniques have been successfully exploited to solve a number of problems involving a wide variety of systems, such as mobile robots and manipulators. They rely on the construction of a graph, either in the form of networks [START_REF] Kavraki | Probabilistic roadmaps for path planning in high-dimensional configuration spaces[END_REF] or trees [START_REF] Steven | Rapidly-exploring random trees: A new tool for path planing[END_REF], trying to approximate the valid Configuration Space (CS) of a system. Nodes, corresponding to configurations, are generated randomly and validated in a further step by checking for collision. In many situations the sampling process and the construction of edges -which represent motions between pairs of configurations -require simple operations. Random samples can be obtained by drawing each component independently from a given random distribution, while local motions are often created using linear interpolation.

However, many robotics tasks impose a number of constraints on the system. As an example, a domestic robot carrying a tray loaded with objects should ensure that during its motion the platter remains horizontal. These constraints cause the valid configuration space to reduce to a lower-dimensional manifold implicitly defined by constraint equations. This introduces many challenges in the planning problem, mainly due to the fact that classical samplers and local routers cannot be exploited any more.

In order to deal with this added complexity, new tools have been developed to generate and connect samples inside the constraint manifold. Early studies focused on closed kinematic chains [START_REF] Howard Yakey | Randomized path planning for linkages with closed kinematic chains[END_REF] and used the Gradient Descent algorithm to enforce loop-closure on random invalid samples. Cortes et al. introduced the Random-Loop Generator [START_REF] Cortes | Sampling-based motion planning under kinematic loop-closure constraints[END_REF], a sampling technique designed to produce valid samples for closed-loop mechanisms.

Planning under task-space constraints was investigated in [START_REF] Stilman | Task constrained motion planning in robot joint space[END_REF], which introduces Tangent Space Sampling and First-Order Retraction in order to sample feasible joint configurations. The CBiRRT (Constrained Bi-directional Rapidlyexploring Random Tree) planner [START_REF] Berenson | Manipulation planning on constraint manifolds[END_REF] uses the Jacobian pseudo-inverse in a similar way to the Tangent Space Sampling in order to project an infeasible sample on the valid manifold defined by end-effector pose constraints.

Further methods have been designed to explore an approximation of the constraint manifold, based on high-dimensional continuation. AtlasRRT [START_REF] Jaillet | Path planning under kinematic constraints by rapidly exploring manifolds[END_REF] focuses on the joint construction of Atlases and of a bi-directional RRT to approximate and explore the constraint manifold. A similar strategy is exploited in [START_REF] Kim | Tangent bundle rrt: A randomized algorithm for constrained motion planning[END_REF], defining a set of tangent spaces that locally approximate the manifold. A generalized framework based on Atlases is proposed in [START_REF] Voss | Atlas+ x: Sampling-based planners on constraint manifolds[END_REF]. It extends several existing randomized planners to the exploration of constrained manifolds.

Other recent works [START_REF] Bonilla | Samplebased motion planning for soft robot manipulators under task constraints[END_REF][START_REF] Bonilla | Noninteracting constrained motion planning and control for robot manipulators[END_REF] use the concept of relaxation, consisting in allowing a small constraint violation during planning. This technique has been mainly exploited to plan motions for compliant systems, using a control action during trajectory execution to steer robot's state close to the constraint manifold. The planning phase is therefore solved via standard techniques from the sampling based domain, since the valid CS is no longer a zero-measure set.

Such approach requires a trade-off between the quality of a planned path and planning time. In fact, if the allowed constraint violation is too small, the topology of the valid Configuration Space changes to a set of extremely narrow passages and the planning time increases significantly. Furthermore, the technique is highly dependent on system's compliance and on controller's ability to reconfigure a robot in feasible states during the motion. Thus, many practical scenarios involving rigid robots cannot exploit relaxation, since they would require a higher quality path directly from the planning step.

In this paper we propose a new approach inspired by relaxation techniques that allows to generate in a short amount of time paths with lower constraint violation. The algorithm uses Quadratic Programming (QP) to locally perform motions in the relaxed CS, with the objective of keeping configurations close to the original manifold while extending to a random sample. We exploit the Jacobian matrix of the constraints to locally linearize the manifold and guide the exploration towards valid states. Thanks to smaller violation tolerances, the necessity of a control action during execution can be reduced, allowing a broader range of robots to exploit these techniques.

The remainder of this paper is organized as follows: differentiable constraints and the concept of relaxed Configuration Space are introduced in Section 2.1, while in Section 2.2 the technique used to perform local motions inside the relaxed CS is detailed. The router is integrated in a randomized planner, which is presented in Section 2.3. Experiments have been conducted in simulation considering different setups, to demonstrate the generality of our approach. We show in Section 3 that the technique allows to rapidly find paths featuring small constraint violation.

Planning Algorithm

In this section we present the proposed planner based on QP to enforce a set of constraints while planning. In order to connect two configurations, the local router is asked to accomplish two tasks concurrently: drive the system toward a given sample and keep the error associated with constraints as small as possible.

We formulate such problem as a Sequential Quadratic Optimization, wherein each step aims at changing the current configuration to a sample that is nearer to the target one, while enforcing the constraints. In addition, the displacement of each coordinate of the configuration vector is bounded. This allows to obtain a discrete set of intermediate configurations, and to consistently check for collisions along the path.

We introduce the constraints in Section 2.1, while the local path planner is detailed in Section 2.2. The connection routine is integrated in a complete Sampling-Based Planner based on the RRT-Connect algorithm [START_REF] Kuffner | RRT-connect: An efficient approach to single-query path planning[END_REF], which is presented in Section 2.3. It attempts to generate new samples and to connect them to the existing graph using the local planner. Post-processing operations can finally be performed to enhance the quality of the resulting path, if any is found.

Differentiable Constraints

We consider the case of an n-dimensional Configuration Space C ⊂ R n , the configuration vector being denoted as q = q 1 • • • q n T . Each coordinate is assumed to be bounded in a range [q i,min , q i,max ]. A set of n c constraints is also considered, each one being described by a differentiable function

C i : C → R (i = 1, • • • , n c ).
Altogether, they define the constrained Configuration Space as:

C C = {q ∈ C : C i (q) = 0 ∀i} (1)
To approximate the valid set defined by all constraints we introduce n c constants ε i > 0, which quantify the maximum allowed violation of each constraint at a given configuration q. These constants need to be set manually by the user depending on the required quality of the planned path. We then define the relaxed Configuration Space C R :

C R = {q ∈ C : -ε i ≤ C i (q) ≤ ε i ∀i} (2)
In order to shorten the notation in following sections, we stack all constraints in the n c -dimensional vector e = C 1 (q) • • • C nc (q)

T . We finally recall that the constraints are assumed to be differentiable. Under this assumption, we introduce the Jacobian matrix J e = ∂e ∂q , whose i-th row is given by the gradient of the constraint C i .

The original planning problem is then formulated as finding a discrete sequence of points in C R which approximate a valid path in C C . The exploration, as detailed in the following section, is guided by the use of J e to locally approximate the manifold implicitly defined by the constraints.

Local Motions using Quadratic Programming

In order to evaluate a local path between two configurations, we solve sequentially a number of QP problems. Our iterative algorithm exploits a single step to perform a short motion towards the goal while keeping e as close to zero as possible. The problem is formalized as follows: two samples q a ∈ C R (initial configuration) and q b ∈ C (final state) are considered. During the process, we denote with q (j) the configuration obtained after the j-th iteration (such that q (0) = q a ). We then select a proper value of q (j+1) , i.e., the next way-point of the local path from q a to q b , by solving the quadratic optimization problem

q (j+1) = arg min x∈C Q (j) x -v (j) 2 Q (j) ∈ R m×n , v (j) ∈ R m (3)
subject to a set of p linear inequalities in the form:

A (j) x ≤ b (j) A (j) ∈ R p×n , b (j) ∈ R p (4)
We use the superscript (j) to underline that Q, v, A and b are evaluated using only values coming from the previous iteration, thus being constant quantities during the (j + 1)-th step.

In the sequel, we firstly show how to derive the expression of matrices contained in (3) and ( 4), and afterwards the iterative scheme is detailed.

Objective and Linear Inequalities. Since the final goal of the iterative scheme is to reach q b -or at least to move as close as possible to it -the considered objective function should contain a term that reaches its minimum in correspondence of the given configuration. In addition, a further contribution should be considered to enforce the constraints. A candidate function satisfying both requirements could be:

f q (j+1) = q (j+1) -q b 2 + α e (j+1) 2 (5)
wherein the constant parameter α ∈ R nc×nc is a positive definite diagonal matrix used as a weighting factor to modulate the "priority" associated to the second task. The term e (j+1) , corresponding to constraints violation evaluated at q (j+1) , is however generally non-linear in the configuration vector, and does not fit the quadratic formulation of (3). However, the function can be linearized around q (i) , using the Jacobian matrix J e introduced in Section 2.1:

e (j+1) -e (j) J (j) e q (j+1) -q (j) (6)
After injecting the linearized error in [START_REF] Jaillet | Path planning under kinematic constraints by rapidly exploring manifolds[END_REF], the objective can be re-written in a matrix form compatible with (3), thus obtaining:

Q (j) = I n α J (j) e v (j) = q b α J (j) e q (j) -e (j) (7)
Regarding the set of linear inequalities, we choose to reduce the search interval according to two factors. The first one imposes upper and lower bounds to each component of the configuration vector:

q min ≤ q (j+1) ≤ q max (8)
The second set of inequalities that is considered limits the local motion of each coordinate to a symmetric interval centered in q (j) :

q (j) -β k ∆q ≤ q (j+1) ≤ q (j) + β k ∆q (β ∈ (0, 1) and k ∈ N) (9)
In this relation, the entries of ∆q ∈ R n , all being positive, correspond to the allowed step of each coordinate, while β k is used to tune the size of the allowed interval. This constraint is justified by two reasons. On one hand the sequential optimization relies on the linearized error dynamics. The approximation must be kept consistent, and therefore the configurations q (i) and q (i+1) should not differ too much. If the new configuration is too far away from the initial one, the constraint error could exceed the tolerance, even if the linearized one is null, as depicted in Fig. 1. The use of the coefficient β k allows to resize the step size during the optimization, and its use is detailed in next section. On the other hand, in many practical planning problems some non-differentiable constraints could be considered as well. They should be verified at each iteration, and a large step size could bear the system to "jump" over small invalid regions. As an example, in our approach we perform discrete collision checking, by verifying the validity of a configuration at each iteration. With the set of inequalities (9) we try to avoid situations wherein collisions with small obstacles are not detected.

Sequential Optimization

The overall local motion routine, called QPMove, is reported in algorithm 1. It performs a Sequential Optimization by solving at each step a QP instance as formulated in the previous section.

An iteration starts with the evaluation of the matrices defining the objective and the inequalities. Then, the inner cycle (between lines 8 and 16) is executed to solve the current QP instance. The obtained solution is tested by checking Fig. 1. From an initial configuration (orange) lying on the constraint -the black continuous line -the optimization would move the system to an invalid configuration (in blue). If the motion is limited to the small yellow rectangle, there are higher chances to still fall inside the relaxed region (surrounded by the dashed gray lines).

constraints violation at the new configuration. This is a fundamental step: since constraints are linearized during the procedure, a resulting sample will only ensure an approximation of the error to be optimized. On the other hand, a component of the actual error could fall outside its valid range [-ε i , ε i ]. To better enforce bounding constraints when such situation occurs, k is incremented by one unit and the optimization step is repeated. This shrinks the valid range of motion, possibly leading q (j+1) to lie inside C R . Nonetheless, the procedure is limited up to a maximum value of k, in order to prevent the algorithm from spending too much time on some critical samples.

Algorithm 1 QP-based Motion Validator (QPMove)

1: QPMove(qa, q b ) : 2: q (0) ← qa 3: f (0) ← +∞ 4: f (1) ← +∞ 5: for j=0 to jmax do 6:

k ← 0 7: Q (j) , v (j) , A (j) ← INIT QP ITERATION(q (j) , q b ) 8: do 9:
if k > kmax then 10:

return "failure", q(j)

11:

end if

12:

b (j) ← GET QP B VECTOR(q (j) , k) 13:

q (j+1) , f (j+1) ← SOLVE QP INSTANCE(Q (j) , v (j) , A (j) , b (j) )
14:

e (j+1) ← EVALUATE ERROR(q (j+1) ) 15: k ← k + 1

16:

while not(-ε ≤ e (j+1) ≤ ε)

17:

if IN COLLISION(q (j+1) ) then

18:

return "failure", q(j)

19:

end if

20:

if f (j+1) ≤ fmin then

21:

return "success", q b 22:

end if 23: if f (j+1) ≤ f (j) and f (j+1) ≥ f (j) -∆f (-) then

24:

return "failure", q(j + 1)

25:

end if 26: q (j) ← q (j+1) 27:

f (j) ← f (j+1)
28: end for 29: return "failure", q(jmax)

The remaining part of the main loop is instead used to check the progresses done between two iterations. As briefly mentioned in the previous section, we propose to handle non-differentiable constraints -in particular, collision detection -by checking them at each new sample. Thus, after having solved the current QP instance, the validity of the sample is tested. If any violation is detected, the algorithm stops and returns the last validated sample.

A second criterion verifies instead if the objective value f (j+1) has become small enough, and in case the algorithm is stopped since the goal configuration has been reached with the error being sufficiently small.

A known problem of quadratic minimization is the existence of local minima. To detect stationary points, the algorithm computes the difference between the objective after subsequent iterations: if the improvement is below a given threshold ∆f (-) , the algorithm returns with the status "failure". It must be noted that due to the linearization the objective could get worse between successive iterations, and thus local minima are checked only if the objective is improving.

Since a proper tuning of the objective thresholds could be hard in practice, a maximum number of iterations is exploited as the last strategy to prevent the routine to waste too much computation time.

The proposed motion component requires more computation efforts and longer run time compared to the simpler technique of linear interpolation, usually exploited in the relaxation context. Nonetheless, its ability of following constraint manifold's curvature proved to effectively counter-balance the drawbacks. Fig. 2 shows some comparative examples in a 2-Dimensional Configuration Space. In the first case (Fig. 2(a)) the valid set defined by the constraint is a circle. Even with a high relaxation factor, linear interpolation would fail to connect the two shown samples, since it would try to follow a straight line path that is incompatible with the curved constraint. In practical scenarios, the relaxation would be way smaller, making it even harder to connect configurations. The example depicted in Fig. 2(b) shows another feature of QPMove: even when attempting to reach an invalid sample, a valid motion can still be performed inside C R . We also show in Fig. 2(c) the motion that would be produced by a projection approach like the one exploited in the CBiRRT planner. To reach the goal more samples are necessary, with a more irregular spacing between adjacent samples.

QPlan

The component QPMove described in the previous section was used as part of a complete path-planner named QPlan. The algorithm exploits a bidirectional RRT [START_REF] Kuffner | RRT-connect: An efficient approach to single-query path planning[END_REF] to explore the constraint manifold, and runs post-processing techniques to enhance the quality of a path. We detail in the following how the typical components of a randomized planner were integrated.

Sampling. A State Sampler produces new configurations which could potentially become leaves of the trees being expanded by the planner. When moving on a manifold, samples should satisfy the constraints imposed on the system. Motions generated in CR by QPMove (red), linear interpolation (green) and a projection approach (black). Start configurations are represented as blue circles, while the goals as blue squares. In (a), the Constrained Configuration Space is represented by a circular arc, while in (b) and (c) by a sinusoidal wave. Linear interpolation can only produce a short path in the first case thanks to a large relaxation, while no new samples can be generated in the sinusoidal region. QPMove (b) produces less samples, which are better distributed than in the case of a projection approach (c).

However, QPMove does not necessarily need valid samples to extend one tree. In fact, an infeasible goal could be passed as q b . The algorithm would not converge to the given configuration, but it could still produce valid motions toward new points in the Constraint Manifold. The advantage of this choice is a faster sampler, since the simple uniform sampling technique can be used.

Trees Extension. The extension step of a bidirectional RRT works by selecting a random configuration and its nearest neighbor from the current tree. A motion is then attempted from the latter to the random sample, but limiting its length to a maximum value.

We rather adopt the greedy version of this algorithm, sometimes referred to as RRT-ConnConn [START_REF] Lavalle | Rapidly-exploring random trees: Progress and prospects[END_REF]. This variant tries to extend a branch until either an invalid state is reached or the connection is successfully performed.

Since QPlan is able to find a discrete set of way-points, it could be useful to insert all intermediate configurations in the tree. However, this could bear to an over-populated tree. Therefore, only one generated configuration out of N is inserted in the tree, and only if its distance from the previously added sample is higher than a given threshold.

Post-processing. As we handle constraints using a relaxation approach, their violation will not be completely nullified along local paths. Post-processing is used to refine an obtained solution by enforcing the constraints at each intermediate sample. If a path is found by the planner, the sequence of joint way-points is re-built, and a local QP optimization is run on each sample. The procedure is similar to the one exploited in QPMove, with two differences: rather than setting inequalities that enforce space bounds, a much smaller range is considered. In practice, inequalities (8) are replaced by: q raw -dq ≤ q (j+1) ≤ q raw + dq [START_REF] Steven | Rapidly-exploring random trees: A new tool for path planing[END_REF] where q raw is the path configuration before optimization, and dq is a vector containing small values allowing the error to be minimized without moving too far away from q raw . In addition, we set as goal configuration the raw initial sample itself. It further constrain the system to only locally change its state.

In addition, a certain number of short-cutting attempts is performed, in order to reduce path's length and simplify the solution.

Simulation Results

We present in this section results obtained from simulations on several different setups with the implemented algorithm. The planner has been implemented using the components provided by OMPL, the Open Motion Planning Library [START_REF] Ioan | The Open Motion Planning Library[END_REF], and integrated in the ROS [START_REF] Quigley | ROS: an open-source robot operating system[END_REF] framework in the form of a MoveIt! [START_REF] Sucan | Moveit![END_REF] planning plugin.

During all experiments, the selection of a proper value of the parameter β was done by trial and error. A value between 0.7 and 0.85 gave the best results in practice. Relaxation constants ε i were set to ensure a reasonably small violation of constraints. Their numerical value is reported later for each experiment. A first set of tests was performed considering a 3-Dimensional point (x, y, z) constrained to the surface of a sphere (Fig. 3(a)) and of a torus (Fig. 3(b)), in presence of obstacles forming narrow passages. The constraints are written in the two setups as C(x, y, z) = x 2 + y 2 + z 2 -R 2 and C(x, y, z) =

x 2 + y 2 -r 1 2 + z 2 -r 2
2 , R being the radius of the sphere and r 1 , r 2 the radii defining the torus. We compared the performances of QPlan with a classical relaxation technique, considering different tolerances. Although the algorithm presented in [START_REF] Bonilla | Samplebased motion planning for soft robot manipulators under task constraints[END_REF] uses RTT* [START_REF] Karaman | Sampling-based algorithms for optimal motion planning[END_REF], we implemented it using the RRT-Connect algorithm for a meaningful comparison of run times. We exploited a sampler that uniformly generates samples over the manifold in order to reproduce the proposed setup. As reported in Table 1, our approach is considerably faster than a simple relaxation technique when the allowed tolerance becomes small 3 . Some tests were run on a more complex test-case, which had been proposed in [START_REF] Voss | Atlas+ x: Sampling-based planners on constraint manifolds[END_REF]. A five-links kinematic chain rooted at the origin is considered (see Fig. 3(c)). Each link is parametrized by a 3D point, for a total number of 15 degrees of freedom. Five constraints are set to fix the distance between pairs of adjacent joints, while a further constraint requires chain's tip to move on a spherical surface. An additional constraint can be set to fix the vertical coordinate of the first point. While QPlan can effectively find paths for this system, standard relaxation techniques require either a higher tolerance or longer execution time. The results shown in Table 2 were obtained considering all links having a length of 0.2 m, and the constraint sphere a radius of 0.6 m. The tolerances have been fixed to 0.005 m 2 for the five distance constraints, to 0.025 m 2 for the tip and 1 mm for the vertical constraint. It is also worth to note that the run-time is at the same order of magnitude of the Atlas-based planners, according to the results given in [START_REF] Voss | Atlas+ x: Sampling-based planners on constraint manifolds[END_REF]. Other tested scenarios involve a Barrett arm solving a maze (Fig. 3(d)) and some dual arm systems cooperatively displacing an object (Figures 3(e), 3(f) and 3(g)). We do not report running times obtained with standard relaxation techniques, since they require a much higher planning time for equal relaxation factors.

During the maze-solving test three constraints are applied to the end-effector so as to keep the stick grasped by the arm vertical and in contact with labyrinth's floor. This scenario is particularly challenging for the planner, since many obstacles are encountered during planning. As explained in Section 2.3, we do not use a specific Sampler to generate new configurations. This might lead the robot to attempt many motions toward configurations that are completely unreachable either due to constraints or to obstacles. Using a more involved sampling technique may instead improve the performances. Another factor that greatly influences the planning time is the choice of the relaxation constants. In a first instance, we considered very strict tolerances on both stick position and orientation: 1 cm of error for the altitude and 0.05 rad for roll and pitch constraints. The chances to find a solution in a short amount of time are quite low, as shown in Table 3. However, further tests were conducted by allowing orientation constraints to be violated with at most 0.2 rad, and optimizing them in the post-processing phase. With this more tolerant setup, the planning time is slightly reduced.

In the dual-arm setups, relative translation and rotation of the end-effectors are forbidden in order to maintain a fixed relative transformation between tip frames. The challenge here comes from the high number of both Degrees of Freedom and constraints.

Conclusions

We have presented a new approach based on Quadratic Programming that can effectively generate paths while dealing with a set of constraints. Our approach takes advantage of relaxation to enlarge the range of valid configurations while planning and of analytic description of constraints to guide local motions. As a drawback, the proposed algorithm features many parameters which need to be tuned in order to guarantee good performances. The relaxation factor plays a relevant role: if constraint violations are not too strict, the search can proceed faster. Nonetheless, with an increased tolerance robots would need higher control action to re-project the samples back to the manifold. Finally, in our contribution we focused only on the planning step, verifying that paths generated by the algorithm can be found quickly and with better constraint enforcement. As a future line of work, experiments with a real robot should be performed to confirm the validity of the proposed approach.

  Fig.2. Motions generated in CR by QPMove (red), linear interpolation (green) and a projection approach (black). Start configurations are represented as blue circles, while the goals as blue squares. In (a), the Constrained Configuration Space is represented by a circular arc, while in (b) and (c) by a sinusoidal wave. Linear interpolation can only produce a short path in the first case thanks to a large relaxation, while no new samples can be generated in the sinusoidal region. QPMove (b) produces less samples, which are better distributed than in the case of a projection approach (c).

Fig. 3 .

 3 Fig. 3. Different tests with QPlan: a 3D point moving respectively (a) on a sphere and (b) on a torus, (c) a five-links chain whose tip is constrained to a sphere, (d) a Barrett arm solving a maze, (e) a UR10 and a Kuka LWR4 moving a plate, (f) PR2 moving a box, (g) PR2 displacing an object with a hole.

Table 1 .

 1 Average planning time in seconds over 100 runs of sphere and torus setups. We used R = 1 m, r1 = 1 m, r2 = 0.5 m. The relaxation factor ε is given in m 2 .

	Algorithm	ε	Sphere Torus
	Relaxation	10 -2 0.214 0.477 10 -3 8.785 14.632
	QPlan	10 -2 0.104 0.027 10 -3 0.120 0.218

Table 2 .

 2 Results

		with the five-links chain,
	under 6 or 7 constraints. The actual run-
	time of the first algorithm is unknown,
	since no plans were found before a time
	limit of 10 s.
	Algorithm nc = 6 nc = 7
	Relaxation > 10	> 10
	QPlan	0.080 0.087

Table 3 .

 3 Planning time of the tests involving different manipulators.

	Scene	Avg. Min. Max.
	Barrett maze (0.05 rad) 4.034 0.669 13.828
	Barrett maze (0.2 rad) 3.446 0.426 13.162
	UR10 + LWR4	0.819 0.084 4.085
	PR2 box	4.338 1.036 10.395
	PR2 cylinders	0.866 0.202 2.322

A relaxation factor ε = 10 -3 m 2 on a sphere with unitary radius corresponds to constrain the points to lay at most 0.5 mm from the surface. The same factor gives a maximum distance of 1mm from a torus having r1 = 1 m, r2 = 0.5 m.


Gilles Pagès

Fabien Panloup

SUPPLEMENT TO "WEIGHTED MULTILEVEL LANGEVIN SIMULATION OF INVARIANT MEASURES"

1. Proof of [PP18, Lemma 2.1]. Prior to the proof of Lemma 2.1, we need to prove this first technical lemma which will be used to estimate in a precise way the coefficients W R+1 and W R+2 involved in the asymptotic mean square error of the ML2Rgodic estimator in Theorems 2.1 and 2.2 of [START_REF] Pagès | Weighted multilevel langevin simulation of invariant measures[END_REF].

LEMMA 1.1. Let R ≥ 2 be an integer.and let (x r ) r=1,...,R be pairwise distinct real numbers. Then the unique solution (y r ) r=1,...,R to the solution to the R × R-Vandermonde system R r=1

x -1 r y r = c -1 , = 1, . . . , R, is given by

(1.1) y r = R s=1,s =r (x r -c) R s=1,s =r (x r -x s ) . Moreover, R r=1 y r x R r = c R - R r=1 (c -x r ) and (1.2) R r=1 y r x R r = c R + R r=1 x r + c R r=1 (c -x r ).
(1.3) Proof. The above Vandermonde system Vand(x r , r = 1 : R)w = [0 -1 ] =1,R can be explicitly solved by the Cramer formulas since its right hand side is of the form [c -1 ] 1≤ ≤R for some c ∈ R. Namely (the column vector [c -1 ] 1≤ ≤R replaces the r th column of the original Vandermonde matrix). Then, elementary computations show that it yields the announced solutions.

To compute the next two sums, we start from the following canonical decomposition of the rational fraction

1 R r=1 (X -1 xr-c ) = R r=1 1 (X -1 xr-c ) s =r ( 1 xr-c -1 xs-c )
.

Setting X = 0 yields after elementary computations

R r=1 y r (x r -c) R = (-1) R R r=1 (x r -c).
Now, using that (y r ) r=1,...,R solves the above Vandermonde system, we get

R r=1 y r (x r -c) R = R r=1 y r R k=0 R k (-1) R-k x k r c R-k = R k=0 R k (-1) R-k c R-k R r=1 y r x k r = c k if k<R = R r=1 y r x R r + c R 1 -1 R -1 so that R r=1 y r x R r = c R -(-1) R R r=1 (x r -c) = c R - R r=1 (c -x r ).
The second identity follows likewise by differentiating the above rational fraction with respect to X and then setting X = 0 again.

Proof of [PP18, Lemma 2.1]. (a) We introduce the auxiliary variables and parameters

(1.4) W r = q 1 q r+1 a W r+1 M r-1 , x r = M -(r-1) q 1 q r+1 a , r = 1, . . . , R -1.
Then (W r ) 1≤r≤R-1 is solution to the system (2.17) of [START_REF] Pagès | Weighted multilevel langevin simulation of invariant measures[END_REF] if and only if

(W r ) 1≤r≤R-1 is solution to R-1 r=1 W r x -1 r = 1 1 -M -, = 1, . . . , R -1.
imsart-aap ver. 2012/08/31 file: supplement_ML2Rgodic.AAP.tex date: December 13, 2017

Expanding 1 1 -M -= k≥0 1 M k 1 M k( -1
) yields by linearity of the above system that it suffices to solve the sequence of (R-1)×(R-1)-Vandermonde systems.

(V k ) ≡ R-1 r=1 W k,r x -1 r = M -k( -1) , = 1, . . . , R -1, k ≥ 0.
As the x r are pairwise distinct, (V k ) has a unique solutions given by

W k,r = R-1 s=1,s =r x s -M -k x s -x r , r = 1, . . . , R -1.
with the usual convention ∅ = 1 Consequently, for every r = 2, . . . , R,

W r = k≥0 1 M k W k,r = k≥0 1 M k R-1 s=1,s =r x s -M -k x s -x r , r = 1, . . . , R -1.
Coming back to the weights of interest finally yields the expected formula.

One derives from the definition of W R+1 (see (2.18) of [START_REF] Pagès | Weighted multilevel langevin simulation of invariant measures[END_REF]), using the auxiliary variables, that

W R+1 = q -aR 1 1 + (M -R -1) W R with W R = R-1 r=1 W r x R-1 r
and the x r are given by (1.4). Following the lines of (a), we derive that

W R = k≥0 1 M k W R,k
where the identity (1.2) established in the above lemma 1.1 yields

W R,k = M -k(R-1) - R-1 r=1 (M -k -x r ).
Finally

W R+1 = q -aR 1   1 + (M -R -1) k≥0 1 M kR 1 - R-2 r=0 1 -M k-r q 1 q r+2 a   .
imsart-aap ver. 2012/08/31 file: supplement_ML2Rgodic.AAP.tex date: December 13, 2017

Noting that k≥0

1

M kR = 1 1-M -R completes the proof this claim.
The computation of W R+2 follows likewise, starting from the identity (1.3).

(b) In the starting system (2.17) of [START_REF] Pagès | Weighted multilevel langevin simulation of invariant measures[END_REF] for the weights q a( -1) r no longer depends on r and can be cancelled in each equation. This leads to the system

W 1 = 1, 1 + (M -( -1) -1) R r=2 M -(r-2)( -1) W r = 0, = 2, . . . , R.
After a standard Abel transform, we get that W r = w r + • • • + w R where the w r are solution to the Vandermonde system

R r=1 M -(r-1)( -1) w r = 0 -1 , = 1, . . . , R.
Note that these weights corresponds to those coming out when dealing with M L2R for regular Monte Carlo (see [START_REF] Lemaire | Multilevel Richardson-Romberg extrapolation[END_REF]) under a weak error expansion condition at rate α = 1.

As for the boundedness, first note that the "small" weights w r read w r = b R -r /a r , r = 1, . . . , R, with

a r = r k=1 (1 -M -k ) and b r = (-1) r M -r(r-1) 2 a -1 r .
One straightforwardly checks that a r ↓ a ∞ = k≥1 (1 -M -k ) > 0 and

B ∞ = r≥1 |b r | < +∞. As a consequence ∀ R ∈ N * , ∀ r ∈ {1, . . . , R}, |W (R) r | ≤ B ∞ a ∞ < +∞.
Finally, the same Abel transform shows that

W R+i = R a(R+i) R r=1 M -(r-1)(R+i-1) w r , i = 1, 2,
and one concludes by formula (1.2) and (1.3) from Lemma 1.1. 2

2. An additional bias term. In this part of the appendix, we focus the bias induced by the approximation

Γ ( ) nr Γ nr ≈ q -a r Γ ( ) n Γ n (with γ n = γ 1 n -a , a ∈ (0, 1)),
that we use to build some universal weights (W (R) r ) r=1,...,R (by universal, we mean that they do not depend on n). We have the following lemma:

imsart-aap ver. 2012/08/31 file: supplement_ML2Rgodic.AAP.tex date: December 13, 2017 LEMMA 2.2. Assume that γ n = γ 1 n -a with a ∈ (0, 1).

(a) Let χ ∈ (0, 1) and L ∈ N such that La < 1. Then, for every n

≥ n 0 = 6 1 1-a χ , Γ ( ) χn Γ χn -χ -a( -1) Γ ( ) n Γ n ≤ 3 1 + 1 -a 1 -a(R + 1) γ -1 1 n 1-a χ -a χ 1-a -3n a-1 ≤ 6 2 -aL 1 -aL γ -1 1 χ -1-a( -1) 1 n 1-a . (2.5) (b) Set Bias (1) (a, R, q, n) = R =2 Γ ( ) n 1 Γ n 1 -q -a( -1) 1 Γ ( ) n Γ n W 1 + R r=2 m r, W r Γ ( ) nr Γ nr -q -a( -1) r Γ ( ) n Γ n c
where m r, = (M -( -1) -1)M -(r-2)( -1) . We have:

|Bias (1) (a, R, q, n)| ≤ C a,q,r n 1-a ,
where

C a,q,r = 6 2 -a(R + 1) 1 -a(R + 1) W ∞ q -1 * R =2 (γ 1 q -a * ) -1 1 + R r=2 m r, |c |
with q * = min 1≤r≤R q r and W ∞ = sup r∈{1...,R},R≥2 W (R) r . Furthermore, if q 1 = . . . = q R = 1 R , then Bias (1) (a, R, q, n) = 0.

REMARK 2.1. Note that since a < 1/2, n 1-a = o(n -1 2 ) so that this term is negligible at the first and second orders of the expansions obtained in this paper. Finally, it is worth noting that this term is equal to 0 when the q i are equal to 1 R , case where, in addition, the W r , r = 1 . . . , R have a simple closed form given by formulas (2.22) and (2.23) of [PP18, Lemma 2.1].

Proof. First, we derive by a comparison argument with integrals n 0 x -a dx and

n+1 1 x -a dx that (2.6) n 1-a -2 1 -a ≤ n k=1 k -a ≤ n 1-a 1 -a , n ≥ 1, a ∈ (0, 1).
imsart-aap ver. 2012/08/31 file: supplement_ML2Rgodic.AAP.tex date: December 13, 2017

Elementary computations then show that, for every a ∈ 0, 1 R , χ ∈ (0, 1), and every n ≥ 1, every integer ∈ {1, . . . , R + 1}

Γ ( ) χn Γ χn -χ -a( -1) Γ ( ) n Γ n ≤ 3γ 1 Γ χn 1 1 -a + χ -a 1 -a
Using that u → u 1-a is (1 -a)-Hölder, we derive from the left inequality in (2.6) that Γ χn ≥ γ 1 (χn) 1-a -3 1-a so that, for every n ≥ 6

1 1-a χ , Γ ( ) χn Γ χn -χ -a( -1) Γ ( ) n Γ n ≤ 3 1 + 1 -a 1 -a(R + 1) γ -1 1 n 1-a χ -a χ 1-a -3n a-1 ≤ 6 2 -a(R + 1) 1 -a(R + 1) γ -1 1 n 1-a χ -1-a( -1) . (2.7) Now, since W ∞ < +∞ (see [PP18, Lemma 2.1(b)]
), we deduce by plugging the above inequality in Bias (1) (a, R, q, n) that, for every n ≥ 6

1 1-a q * , |Bias (1) (a, R, q, n)| ≤ 6 2 -a(R + 1) 1 -a(R + 1) 1 n 1-a W ∞ q -1 * R =2 (γ 1 q -a * ) -1 1 + R r=2 m r, |c |.
When q r = 1 R , r = 1, . . . , R,

Bias (1) (a, R, q, n) = R =2 Γ ( ) n 1 Γ n 1 - q-a( -1) 1 Γ ( ) n Γ n W 1 + R r=2 W r m r, c = 0 since W is solution to (2.17) of [PP18]. 3. Proof of of [PP18, Proposition 7.6]. (i) Setting T = 1 ρ log(1/ε) leads to |E[f (X T )] -ν(f )| ≤ c 1 ε.
Thus, for such a T , it remains, for a given ε to show that this is possible to build Υ(T, R, N) in such a way that Υ(T, R, N) -E[f (X T )] 2 ≤ Cε (where C is independent of ε) with a cost of computation proportional to ε -2 log(ε 2 ) when β = 1 and to ε -2 when β > 1. This property is now classical but in our context in the Finite Horizon Multilevel literature (see e.g. [START_REF] Giles | Multilevel Monte Carlo path simulation[END_REF]), but here, we certainly have to take into account the dependence in T : we recall that

Υ(T, R, N) -E[f (X T )] 2 2 = m h2 1-R ,T 2 + R r=1 Var(Y (r) 1 ) N r where m h,T = E[f ( Xh T )] -E[f (X T )].
Under the assumptions of the proposition, we have

|m h2 1-R ,T | ≤ c 2 h2 1-R so that R = (log 2) -1 log(1/ε) leads to |m h2 1-R ,T | ≤ c2 ε with c2 = 2c 2 h.
Let us now consider the variance component in terms of the computational cost.

Optimizing the choice can be made by minimizing the effort E(T, R, h, N), i.e. the product of the cost of simulation by the variance. Here,

E(T, R, h, N) = T h N 1 + 3 R r=2 2 r-2 N r R r=1 Var(Y (r) 1 ) N r .
The equality case in the Schwarz Inequality shows that this above product is minimal when the terms in both sums are proportional, i.e. when there exists λ> 0 such that ∀r ∈ {1, . . . , R}, 2 r N r = λ Var(Y Under the third assumption(on the variance), Var(Y

(r) 1 ) ≤ (1+2 β 2 )c 3 h β 2 2 -β(r-1) 2 so that R r=1 Var(Y (r) 1 ) N r ≤ (1 + 2 β 2 )c 3 (2h) β 2 2 1 2 λ -1 2 R r=1 2 (r-1) 1-β 2 = (1 + 2 β 2 )c 3 (2h) β 2 2 1 2 λ -1 2 2 R 1-β 2 -1 2 1-β 2 -1 ≤ C β,h λ -1 2 2 R 1-β 2 1 β =1 + R1 β=1
(with the usual convention 1 R -1 1-1 = R when β = 1). We may now fix λ in such a way that the variance contribution to the quadratic error be proportional imsart-aap ver. 2012/08/31 file: supplement_ML2Rgodic.AAP.tex date: December 13, 2017 to ε. Up to a constant only depending on h and β, we have

R r=1 Var(Y (r) 1 ) N r ε 2 if √ λ ε 2 C β,h λ -1 2 2 R 1-β 2 1 β =1 + R1 β=1 -1 .
The above property combined with what precedes implies that the global MSE is bounded by Cε 2 if we set

N r = 2 -r β+1 2 ε -2 log(1/ε) if β = 1 2 -r β+1 2 ε -2 if β > 1.
To complete the proof of this first part, it remains to note that with these choices of T , R and N r , the computational cost for the simulation is equal to

T h N 1 + 3 R r=2 2 r-2 N r α -1 ε -2 log 3 (1/ε)) if β = 1 α -1 ε -2 log(1/ε)) if β > 1.
(ii) We have to prove that the three conditions of (i) hold true under (C s ). First, applying Itô's formula to e 2αt X x t -X y t 2

S , shows, owing to Assumption (C s ), that

E[ X x T -X y T 2 S ] ≤ x -y 2 S e -2αT
. Using the Lipschitz continuity of f , the stationarity property and the previous inequality yield

E[f (X x T )] -ν(f ) = R d E[f (X x T ) -f (X y T )]ν(dy) ≤ [f ] 1 R d E[ X x T -X y T 2 S ]ν(dy) ≤ [f ] 1 e -αT R d
x -y S ν(dy)

where [f ] 1 denotes the Lipschitz constant of f . Assumption (c) is also obtained by exploiting the contractive properties derived from (C s ). The proof follows the lines of [START_REF] Lemaire | Estimation récursive de la mesure invariante d'un processus de diffusion[END_REF], Theorem IV.1 applied with p = 2 and the function V (x) := |x| 2 S . This yields in particular that β = 2 and the time-independence of c 3 . Note that finally, since β = 2 and f is Lipschitz, we can control the weak error as follows:

|E[f (X T )] -E[f (ξ h T )]| ≤ [f ] 1 E[ X T -ξ h T S 2 ] ≤ c 3 [f ] 1 h.
imsart-aap ver. 2012/08/31 file: supplement_ML2Rgodic.AAP.tex date: December 13, 2017

imsart-aap ver. 2012/08/31 file: supplement_ML2Rgodic.AAP.tex date: December 13, 2017