Davide Frey

Arnaud Jegou

Anne-Marie Kermarrec

Social Market: Combining Explicit and Implicit Social Networks

The pervasiveness of the Internet has lead research and applications to focus more and more on their users. Online social networks such as Facebook provide users with the ability to maintain an unprecedented number of social connections. Recommendation systems exploit the opinions of other users to suggest movies or products based on our similarity with them. This shift from machines to users motivates the emergence of novel applications and research challenges. In this paper, we embrace the social aspects of the Web 2.0 by considering a novel problem. We build a distributed social market that combines interest-based social networks with explicit networks like Facebook. Our Social Market (SM) allows users to identify and build connections to other users that can provide interesting goods, or information. At the same time, it backs up these connections with trust, by associating them with paths of trusted users that connect new acquaintances through the explicit network. This convergence of implicit and explicit networks yields TAPS, a novel gossip protocol that can be applied in applications devoted to commercial transactions, or to add robustness to standard gossip applications like dissemination or recommendation systems.

Introduction

The advent of Online Social Networks (OSN) has shifted the core of Internet applications from devices to users. Explicit social networks like Facebook , or LinkedIn enable people to exploit real-world connections in an online setting. Collaborative tagging applications such as delicious, CiteULike, or flickr form dynamic implicit networks of users on the basis of their online activities, interest profiles, or search queries. Users can not only access and introduce new available content but they become themselves accessible through the online infrastructure. Existing online social networks can be grouped into two main categories: explicit and implicit. In explicit networks, users explicitly determine which other users they should be connected to. In Facebook or MySpace, they issue and accept friendship requests. In Twitter , they decide that they wish to follow the tweets of specific users. In all cases, the topology of the resulting network reflects the choices of users and often consists of links that already exist between real people. Explicit networks are therefore very useful in reinforcing and exploiting existing connections but provide little support for discovering new content [START_REF] Bender | Peer-to-peer information search: Semantic, social, or spiritual?[END_REF][START_REF] Ahn | Analysis of topological characteristics of huge online social networking services[END_REF]. Implicit networks fill this gap by taking an opposite approach which allows users to discover new content, and acquaintances [START_REF] Bertier | The gossple anonymous social network[END_REF]. Specifically, implicit networks form dynamic communities by collecting information about collateral activities of users, such as browsing websites or tagging documents, URLs, or pictures. A given user may or may not be aware of the other members of her own communities depending on the target application. Other users should be clearly visible if the purpose of the application is to discover new people, while they may be hidden for the sake of privacy when they are simply being used as proxies to access new interesting content. In either case, the ability to establish new social connections is key to identifying new and useful data.

Recent years have seen the emergence of a significant number of research efforts and applications exploring the power of each of these two paradigms. Nonetheless, a lot more can be achieved if both approaches are combined into a single framework. Consider the following example. John, who lives in London, bought two electronic tickets for a classical-music concert in Paris, a concert version of Berenice by Handel, but an unexpected event makes him and his friend unable to travel to Paris to attend the concert. The concert is tomorrow and John would like to sell the tickets to someone who can actually attend the event. Unfortunately, while John has many friends interested in classical music, they are all based in the United Kingdom. He does know a few people in Paris, but they are mostly colleagues or friends he met while traveling and who do not share his musical tastes. He tries calling a few of them but his best bet is Joseph, who claims to have a friend whose parents often go to classical-music concerts. Unfortunately, this friend of Joseph's is out of town and Joseph does not know how to reach his parents. As a last resort, John posts a message on a French classical music forum, linking to an EBay ad. However, none of the classical music fans on the forum are responsive enough and some of them even become suspicious that the electronic ticket being sold by this new forum user is actually a fake.

John's problem would be very easy to solve if he was able to contact someone that, albeit not knowing him directly, was at the same time interested in the concert and would trust him enough to buy an electronic ticket from him. This is exactly what can be achieved by combining the discovery potential of implicit networks, with the real-world guarantees provided by trusted social links in explicit ones. While implicit networks do not convey any kind of trust, explicit links almost always carry some kind of trust properties resulting from being friends, coworkers and so on.

In our example, the implicit network allows John to identify people that could be interested in the concert. Among these, he discovers François, a music teacher from Paris who is trying to buy two tickets for one of his students and himself. A cross check on the explicit network then allows John to assess François's trustworthiness. He finds out that François is actually the cousin of a French colleague of his wife. This allows the two to gain confidence in each other and thus complete a safe transaction without external help.

Combining the discovery capabilities of implicit networks with the trust and confidence that are inherent in friendship relationships is useful not only in the context of commercial transactions but also in applications like information dissemination, or recommendation. Consider a distributed news dissemination system [START_REF] Boutet | Whatsup: News, from, for, through, everyone[END_REF]. Users receiving an unusual news item will be more likely to be interested in it if the source or the user that forwarded it is associated with some level of trust. Similarly, recommendation systems can take into account the trust of users in other people's opinions.

The power of combining explicit and implicit social networks, however, has a cost. First, the enormous amount of information necessary to manage user profiles requires significant storage capacity as well as computing power to determine who the best users are for a given transaction. Second, the associated costs are equally enormous and can only be afforded by a few very large companies, and this, in turn, brings significant privacy problems. Modifications in the terms of service of websites like Facebook have already caused public uproars in multiple occasions. Most people are rightfully upset at the idea that their personal data may be collected by a company and sold to third parties for whatever reasons. The most promising way to continue to use personalized information is therefore to develop scalable decentralized solutions.

A class of protocols that appear to be particularly suited for this purpose are those based on the gossip paradigm. Initially introduced in the context of distributed databases, gossip protocols have rapidly shown their applicability in a large number of applications including data dissemination, overlay maintenance, and more recently social networks. In this paper, we extend existing work on interest-based gossip overlays [START_REF] Bertier | The gossple anonymous social network[END_REF] and propose Social Market, a solution for the identification of trusted social acquaintances.

Our main contribution in Social Market is TAPS (Trust-Aware Peer Sampling), a novel protocol that operates by directly incorporating trust relationships extracted from an explicit social network into the gossip-based overlay. This provides each user with a set of neighbors that are not only useful but that can also benefit from a high degree of trust. Through extensive simulations, we show that Social Market and TAPS achieve performances that are comparable to those obtained by protocols equipped with global system knowledge, while limiting the diffusion of sensitive trust information. This makes our solution directly applicable to situations like the social transaction example described above. Moreover, our results open new directions for making existing gossip-based applications more robust in the presence of unreliable users.

System Model and Problem Definition

Social Market (SM) is a novel distributed application enabling users to identify previously unknown social acquaintances that, at the same time, are similar to them and can be trusted through a chain of explicit social connections, the trusted path. Selecting similar users is crucial when searching for the right people for a given transaction, but also when building recommendation or datadissemination systems. Trust enables the implementation of transactions without external help and increases users' confidence in recommendation results. We consider a system consisting of a set of users equipped with interconnected computing devices that enable them to exchange information in the form of messages. Each user is associated with a user profile that characterizes her interest, her past behavior, her geographical location, and whatever other information the user wishes to add. The profile is essentially a vector of strings that can represent, for example, URLs, words, or phrases. We refer to each such string as a keyword. Each keyword in a profile is also associated with a counter, its weight, which counts how many times the keyword has been added to the profile. The weight basically measures how relevant a given keyword is with respect to the other keywords in the profile. Keywords can be added by the user, they can be extracted from her browsing history, as well as from her interaction with Social Market. To simplify notation, we refer to a user and her profile with the same symbol u ∈ U , where U is the universe of all user profiles. Profiles can be compared with each other using a standard similarity metric. Even though our solution can operate using any similarity metric, in the following, we make use of the well known cosine similarity [START_REF] Salton | Introduction to Modern Information Retrieval[END_REF], which measures normalized overlap.

Sim(u 1 , u 2 ) = cos(u 1 , u 2 ) = u 1 u 2 ||u 1 || • ||u 2 ||
Users interact with Social Market by proposing items that they wish to exchange with other users. An item can be, for example, an object to sell, an object to buy, but it can also be a question that is being asked and that needs an answer. When a user u creates an item, she associates it with an item profile, similar to what is done in [START_REF] Bai | Personalized top-k processing: from centralized to decentralized systems[END_REF]. Structurally, an item profile is identical to a user profile. Upon creation, the system initializes the item profile to the corresponding user profile. The user then completes the creation by selecting which keywords from this profile clone should be kept, which should be removed, and which, if any, new keywords should be added.

In the example of Section 1, John creates an item for the Handel concert in Paris. Prompted with a profile that contains, among other things: computer science, cycling, mountaineering, violin, rock, and classical music, John decides to keep only violin and classical music in the item profile. He then adds two more keywords, Paris and Handel, and decides to keep only the latter in his user profile as he's not interested in being notified about other items associated with Paris. Once an item has been created, the goal of Social Market is to lead this item to meet other users who

-(i) are interested in the item, - (ii
) can be trusted and can trust the creator of the item, -(iii) can be reached through a trusted path on the social network (Figure 1a).

To make this possible, Social Market users can create explicit social links. While similar to friendship links in systems like Facebook, SM links also have an additional feature: trust. Upon establishing a link, users declare how much they trust each other by specifying a value in (0, 1]. The value of the trust link is similar to the degree of friendship/confidence specified in some existing social networks such as CouchSurfing1 . In particular, if user A assigns a value close to 0 to the link to a user B, it does not necessarily mean that A completely distrusts B, but it may simply mean that A does not know B enough to express a positive opinion.

In the following, we present our solution to address Social Market's goals. In this version of our work, we assume that two explicit friends always agree on a trust value for the link they share. This yields an undirected social graph with arc weights between 0 and 1. Extensions to the directed case as well as mechanisms to guarantee high levels of privacy and resilience to attacks are outside the scope of this paper and will be the subject of our future work.

Social Market

Identifying users that, at the same time, are interested in an item and towards whom it is possible to identify a trusted path requires an effective protocol to group users according to these two conflicting requirements. Recent research on gossip-based protocols has shown their effectiveness in building overlays that cluster nodes or users according to some distance function or similarity metric. In this section, we extend this research by presenting a novel protocol capable to provide each user or item with a set of neighbors that have highly similar profiles and to which there is a trusted social path. Because users and items are treated identically by our protocol, we refer to both with the term node.

Background: Gossip-Based Implicit Networks

Protocols for gossip-based clustering generally consist of two layers. The bottom one is a random peer sampling protocol (RPS) [START_REF] Jelasity | Gossipbased peer sampling[END_REF] which provides each node with a continuously changing view of the network. The properties of the RPS are such that the resulting topology, that is the union of all the RPS views, can be assimilated to a random graph. This makes the RPS effective in maintaining a connected overlay in the presence of disconnections and arrivals of new nodes. The top layer is also a gossip-based overlay maintenance protocol and is based on a variation of [START_REF] Voulgaris | Epidemic-style management of semantic overlays for content-based searching[END_REF]. Specifically, at each gossip exchange, a node selects its neighbors by choosing those with the best similarity values.

Social Market exploits a similar protocol structure. Instead of a random peersampling layer, it applies our novel trust-aware peer-sampling protocol, TAPS. TAPS provides the clustering protocol with candidate nodes that not only have similar interests but that can also be trusted. The clustering protocol then uses this information to select those that offer the best compromise between trust and interest similarity as shown in Figure 1a.

To summarize, each node maintains three data structures: the explicit view, the TAPS view, and the cluster view. The explicit view contains the node's explicit friends, while the other two are maintained by the TAPS and clustering protocols as described in the following.

Trust-Aware Peer Sampling

TAPS follows the general structure of a peer-sampling protocol described in [START_REF] Jelasity | Gossipbased peer sampling[END_REF]. Its goal is to populate the TAPS view with an ever-changing set of references to other nodes. Periodically, each node contacts a node selected from its TAPS view and the two exchange subsets of their respective views.

In a standard peer-sampling protocol, each view entry contains at least information on how to contact the corresponding node (eg. IP address and port), and an age or timestamp value indicating when the information in the entry was generated. In TAPS, we introduce additional fields. First, as in [START_REF] Bertier | The gossple anonymous social network[END_REF], we add a user profile. This makes it possible to cluster similar nodes together by computing the cosine similarity of their profiles. In addition, we include an inferred trust value, and a trusted path. The inferred trust value indicates the trust that a node can have in another node. If the other node is a friend in the explicit network, then the trust value corresponds to the one agreed upon when the friendship relationship was established. Otherwise, it is an inferred value that depends on the path that the trust information has taken during the gossip dissemination, the trusted path.

Trust Propagation. Each edge in a trusted path carries some amount of uncertainty about the trustworthiness of the target node even if all the nodes in the path fully trust each other. To model this, we define the inferred trust of a path as the product of the trust values of its edges, weighted by a trust transitivity coefficient, τ , expressing how much a node values other nodes' recommendations. Given a path u 1 , u 2 ..., u n with trust values t 1,2 , t 2,3 ..., t n-1,n , the inferred trust between u 1 and u n is

t1,n = τ n-2 i=n-1 i=1 t i,i+1 ,
Lower τ values cause trust to decay faster with path length. For example, with τ = 0.7 trust decays from 1 to 0.49 in only three hops.

The ability to perform trust inference is what makes TAPS the perfect candidate for building our Social Market application. In the following we describe the mechanisms that enable trust inference to be implemented in the context of a gossip-based overlay protocol.

Initialization and View Exchanges. An inference process can only produce results if it starts from some reliable initial values. In TAPS, these values are those that have been agreed upon at the creation of explicit friendship relationships. We therefore initialize the TAPS view by inserting one entry for each explicit neighbor. During the course of the protocol, these entries are exchanged with entries received from other nodes. Initially nodes providing new entries will be the node's explicit friends, then the node's friends' friends, and so on.

As the gossip process evolves, nodes collaborate in computing inferred trust values. Consider a node A exchanging profiles with another node B as shown in the top diagram of Figure 1b. A sends B a subset of its view as well as the value it has for t AB , the inferred trust between A and B. B uses this information to update the inferred trust values before adding the nodes to its own view. Specifically, let t AX be the trust A has in X, then B computes its own trust for X, t BX , as follows. First it verifies if it already has a value for t AB . If so, it keeps the highest value between the received one and its own. It then uses the selected t AB , to compute t BX as

t BX = τ t AB t AX .
During the course of dissemination, a node A will inevitably receive multiple references for the same node X. Each of these may arrive from a different neighbor and carry a different trust value. In the presence of multiple trust values for the same reference, a node always selects the largest. However, two references for the same node may also contain slight differences in the node's profile, and in this case, the node should keep the most recent information. To balance these two needs, when A receives a reference to a node X, it chooses the highest trust value between the one in its view and the one it received, and combines it with the most recent profile. Because τ < 1, choosing the largest trust value guarantees that nodes always selects the most direct trust values, thus converging towards shorter and shorter trusted paths. Nonetheless, some nodes may still be unable to infer the trust of other nodes through the best social paths.

To enhance the chances of a successful trust inference, a node initiates gossip exchanges not only towards nodes in its TAPS view but also to those in its explicit neighbors. These additional gossip exchanges are executed every T exp TAPS cycles and cause nodes to exchange entries from the unions of their TAPS and explicit views. Explicit-view exchanges increase the probability that nodes can infer trust through the shortest available paths.

Managing Trust Paths. When exchanging trust information with each other, nodes also update the associated path information. Specifically, when a node A receives a reference to node X from node B, it computes the associated path p AX by concatenating p AB and p BX . Maintaining paths up to date is not only necessary to enable users to enforce correct transactions in the social market application, but it is also useful to correct the degradation of trust values caused by possible loops in the inferred paths.

Consider the situation depicted in the bottom diagram of Figure 1b. Node X holds a reference to D with a trust value t XD and a path going through Y and sends it to A. Node A should combine this with the trust value it has for node X, t AX , also obtained through Y . However, this would lead to a path that uselessly goes twice through node Y and once through X.

Node A can prevent this by short circuiting the path, thus computing a more accurate trust value. The problem is that the information received from X only contains the identifiers of the nodes in the path and not their trust values. Including such values in the path would allow the re-computation of trust, but at the cost of disclosing trust information to third parties.

We therefore replace the re-computation of trust with the computation of a lower bound. Specifically, A knows that the aggregated impact on trust of the segment Y X cannot be greater than τ n , n being the number of useless links in the path, each link being counted once for each time it is traversed (n=2 in this case). It can therefore conclude that the trust value of node D as seen from A, T AD is at least:

t AD ≥ t XD t AX τ n .
This makes it possible to increase the accuracy of trust inference without disseminating private trust information to third parties.

Clustering Trusted Nodes

Our Trust-Aware Peer Sampling protocol provides each node with a continuously changing set of nodes along with their inferred trust values. This constitutes a source of information for our clustering protocol, a variation of the well-known Vicinity protocol [START_REF] Voulgaris | Epidemic-style management of semantic overlays for content-based searching[END_REF]. This protocol maintains a cluster view that collects the nodes that offer the best compromise between trust and similarity.

Filling the Cluster View. In order to fill its cluster view, each node periodically selects the node with the oldest timestamp and exchanges the content of its view with it. Upon receipt of another node's view, a node X combines the received view, its own view, and its own TAPS view, and selects the entries that are associated with the best trade-off between similarity and trust. Specifically, for each entry N , X computes a score s XN as follows

s XN = Sim(X, N ) 2-t XN , ∈ [0, 2]
where , the trust weight, determines the importance of trust in the trade-off. To speed up convergence, nodes also update their cluster views when they receive new information through the TAPS protocol. In this case, they simply combine the received TAPS view with the current cluster view and extract the nodes with the best trade-off between trust and similarity. The selected nodes replace those that were previously in the cluster view.

Trust Verification. The decentralized nature of our trust-inference protocol can allow nodes to cheat on their trust values when communicating with nodes that are not direct friends. For example, in Figure 1b (bottom), node D could try to enter A's cluster by making A believe that it has a high-trust link to node Y.

To prevent this, each node verifies the trust values of the entries in its cluster view, once they have remained in the view for at least c cycles. 2 To achieve this, A asks D to forward a verification message back to A along the trusted path. The message starts with a trust value of 1. Nodes along the path multiply the message's value by τ and by their trust for the node received the message from. Y thus multiplies 1 by τ t Y D in the example. In the absence of colluding nodes, this process causes the verification message to reach A with the correct value for t AD thereby invalidating D's cheating attempts.

Evaluation

We evaluated the effectiveness of our approach by means of extensive simulations on several data traces obtained from real social networks. In the following we first present the details of our setting, and then discuss our results.

Setting

We evaluated our protocol on real data traces consisting of 3000 users extracted from the Facebook and Digg social websites. The Facebook trace3 contains friendship links and a list of social interactions. To obtain a treatable subset for our experiments, we first cleaned up the trace by removing all users that had only one friendship link, as they would be too isolated to benefit from our social platform. We then selected the user with the largest number of interactions and proceeded in a spiral fashion by selecting her friends, then the friends of her friends, and so on, until we reached 3000 users. We associated each of these users with a random user profile from the Digg social network. We obtained these profiles by crawling Digg in late 2010.

Friendship links in the Facebook trace and profiles in the Digg trace provided the base explicit links and profiles for our experiments. On top of them, we built several traces by varying the trust patterns between the nodes. We distinguish our traces into two groups: binary and multi-valued. In both, we made the assumption that the number of interactions between two nodes is a measure of trust (this assumption is not part of the protocol itself).

Binary Traces. In binary traces we assigned a binary trust value to each link in the data set. Specifically, we sorted the friends of each user according to the number of interactions she had with them. Then, for a user with |N | friends, we assigned a trust value of 1 to the β|N | directed links with the largest number of interactions. Because, this process creates asymmetric trust values, we then set the symmetric trust value of each link as the logical OR of the two asymmetric values. These lead to the proportions of trusted links depicted in Figure 2a.

Multivalued Traces. While binary traces provide a simple experimental setting, reality tends to be more complex. Thus, we also considered traces with trust values of 1, 0.8, 0.5, and 0. Similar to the binary case, we sorted each user's friends by the number of interactions and assigned a trust value of 1 to the top γ 1 |N |, a value of 0.8 to the following γ 0.8 |N | and so on, leading to the three traces shown in Figure 2b.

Terms of Comparison

We compared the performance of our Social-Market solution against several alternatives. First, we considered best, an ideal systems that, powered with global knowledge, always provides each user with the set of neighbors that offer the best combination of similarity and trust. This allows us to asses TAPS's ability to reach similar results in a decentralized way. Then we considered oracle: this consists of a standard similarity-based implicit network [START_REF] Bertier | The gossple anonymous social network[END_REF], augmented with an oracle that provides each user with the best trusted path to her neighbors. Oracle therefore maximizes profile similarity at the cost of possibly lower trust values.

We also compared against two variations of our protocol. Full-trust is a version in which nodes exchange complete trust information along with trusted paths. This makes it possible to short-circuit long paths more accurately than as described in Section 3.2 at the cost of disclosing trust values. Full-Trust is only shown in multi-valued traces as it is equivalent to TAPS in binary ones. TAPS no-bound is instead a version of TAPS in which nodes do not attempt to short-circuit cycles thus yielding less accurate trust computation. Finally, unless otherwise specified, we ran our simulations using default values for τ and . τ = 0.75 provides a good balance between trust decay and path length ( 0.56 at 3 hops, 0.23 at 6). = 1 gives instead a fair tradeoff between trust and similarity.

Results

Impact of Trust Density. We start our performance comparison by examining the results obtained in the various traces with a trust transitivity of τ = 0.75. Our results, depicted in Figure 2c, show the average score values in the cluster views with TAPS as well as with its competitors as percentages of best's scores. TAPS's performance is either comparable or better than that obtained by Oracle with the use of global knowledge. As expected, TAPS is particularly good whenever the social network has a limited proportion of high-trust links (binary-0.4 and multi-valued-1 and -2). This can be explained by observing that Oracle always selects the nodes with the best cosine similarity and is therefore penalized in networks where the density of high-trust links is lower. With smaller τ values, we observed that TAPS outperforms Oracle in all the considered traces. With very high values of τ trust decays more slowly. In this case, an protocol like Oracle that first finds the most similar nodes and then searches for a trusted path may be viable. However, it should be noted that Oracle achieves this through global knowledge. A distributed protocol to compute trusted paths would probably be either very costly or ultimately equivalent to TAPS in networks characterized by a high trust density. Moreover, such a protocol would remain inapplicable in situations where the density of trusted links is low, as shown in Figure 2c.

Impact of Trust Weight. Next, we evaluate the impact of the trust-weight factor on the performance of TAPS and its competitors. Figure 4 shows the result in the binary (left) and multi-valued (right) traces respectively. Both plots show that the benefits of a protocol like TAPS become more important as more weight is placed on the trust between nodes. With values of above 1, TAPS performs better than Oracle even when considering its no-bound version. In addition, the plots show that the importance of short-circuiting cyclic paths is greater when the value of is small. This is because smaller values make it possible for the protocol to select nodes that are farther away in the social network, which, in turn, makes the presence of cycles more likely.

Graph Properties of TAPS. To better understand the behavior of TAPS, we conclude our evaluation by examining the properties of the TAPS overlay from a graph-theoretical perspective. First we observe that convergence speed is comparable to that obtained with standard protocols: views reach 90% of their scores within 15 cycles and completely converge after 80. Then we examine our TAPS and clustered overlays in terms of clustering coefficient and in-degree distribution to assess how close they are, respectively, to a random and a clustered graph.

Figure 5a shows the cumulative distributions of the local clustering coefficients of the nodes in our TAPS, and cluster views (TAPS and TAPS-cluster) and compares them to those of a standard peer sampling protocol (RPS) and a standard clustering protocol that does not consider trust (RPS-cluster). The plot (in logarithmic scale) shows that, according to expectations, the TAPS topology is slightly more clustered, and thus less uniformly random, than a standard RPS topology. Conversely, our cluster topology is slightly less dense than the one based on pure similarity.

The in-degree distribution shown in Figure 5b also shows some differences with respect to traditional protocols. In this case, the difference is more accentuated between TAPS and the RPS than for the corresponding clustered overlays. The in-degree distribution of TAPS is in fact slightly skewed because nodes that are not trusted by many others tend to have fewer neighbors. This is indeed a desirable property as untrusted nodes could potentially harm the system through illicit behaviors. Moreover, while these differences are inherent in the trust-dependence of the TAPS overlay, their small absolute value suggests that TAPS could probably replace traditional protocols in a number of applications.

Related Work

The concept of trust in explicit social networks has been exploited in domains ranging from peer-to-peer security to recommendation systems. SybilGuard [START_REF] Yu | Sybilguard: defending against sybil attacks via social networks[END_REF] and SybilLimit [START_REF] Yu | Sybillimit: a near-optimal social network defense against sybil attacks[END_REF] propose protocols that exploit trust relationships between friends to protect peer-to-peer systems from sybil attacks. Reliable Email [START_REF] Garriss | Re: Reliable email[END_REF] uses a similar approach to build an email-whitelisting system based on friendto-friend relationships, while Ostra [START_REF] Mislove | Ostra: leveraging trust to thwart unwanted communication[END_REF] exploits social trust to limit the incidence of unwanted communication in messaging and content-sharing systems.

NABT [START_REF] Liu | P2p trading in social networks: the value of staying connected[END_REF] proposes the use of trust between friends to prevent freeriding behaviors using a more efficient form of tit-for-tat based on indirect trust relationships. NABT's credit-based approach can be viewed as a basic form of trust inference between friends of friends. A more advanced approach to trust-inference is adopted by SUNNY [START_REF] Kuter | Sunny: a new algorithm for trust inference in social networks using probabilistic confidence models[END_REF], a centralized protocol that takes into account both trust and confidence to build a Bayesian network. Even if SUNNY is centralized, its confidence-based idea could lead to interesting improvements for TAPS.

A number of research efforts have instead investigated the use of trust links to improve the performance of recommendation systems. [START_REF] Wang | Bayesian network trust model in peer-to-peer networks[END_REF] uses an approach similar to that of [START_REF] Kuter | Sunny: a new algorithm for trust inference in social networks using probabilistic confidence models[END_REF], while TrustWalker [START_REF] Jamali | Trustwalker: a random walk model for combining trust-based and item-based recommendation[END_REF] combines trust and item-based collaborative filtering. TaRS [START_REF] Massa | Trust-aware recommender systems[END_REF] builds a recommendation system capable of operating both with global and with local trust metrics. Global trust metrics [START_REF] Brin | The anatomy of a large-scale hypertextual web search engine[END_REF] predict a global reputation value for each node. Local trust metrics [START_REF] Massa | Controversial users demand local trust metrics: an experimental study on epinions.com community[END_REF], on the other hand, take an approach similar to ours and compute trust values that are dependent on the target user.

Despite the mole of work on social trust, Social Market is, to the best of our knowledge, the first system to propose the use of trust relationships to build a decentralized interest-based marketplace. Similarly, TAPS is the first attempt to combine explicit and implicit social networks into a single gossip protocol. Existing research on gossip protocols has addressed a number of problems including data dissemination [START_REF] Birman | Bimodal multicast[END_REF], aggregation [START_REF] Jelasity | Gossip-based aggregation in large dynamic networks[END_REF], and overlay construction and maintenance [START_REF] Jelasity | T-Man: Gossip-based overlay topology management[END_REF][START_REF] Voulgaris | Epidemic-style management of semantic overlays for content-based searching[END_REF]. In this context, the two contributions that are most closely related to our work are [START_REF] Datta | Godisco: selective gossip based dissemination of information in social community based overlays[END_REF], which uses gossip to disseminate news in explicit networks, and [START_REF] Bertier | The gossple anonymous social network[END_REF], which proposed the use of gossip for implicit ones.

Conclusions and Future Directions

We presented Social Market (SM), a novel distributed application designed to enable trusted collaborative actions between similar people in a social-network environment. We proposed a solution to the challenges posed by SM in the form a novel trust-aware peer-sampling protocol, TAPS, which creates an RPS-like overlay taking into account the mutual trust expressed by users when joining an explicit social network. Our experimental results show that, combined with a clustering protocol, TAPS is highly effective in providing users with high-quality implicit acquaintances that not only share similar interests but are also reachable through a verifiable trusted path. This makes Social Market a promising platform for the development of decentralized user-to-user transactions and warrants further investigation into the use of trust to secure existing gossip protocols.

Our promising results encourage us to extend Social Market and TAPS in a number of ways. First, we are examining the possibility of using asymmetric trust values as opposed to symmetric ones. This would make it possible to render trust information more private as users would not need to disclose to their friends the trust they have for them. Second, even though the gossip nature of TAPS makes it inherently self healing, we are considering solutions to maintain the quality of trust paths even during churn by having nodes rely on trusted peers to disseminate information while disconnected. Finally, we plan to explore the use of multiple redundant trusted paths as a way to limit the effects of colluding nodes, which cannot be tolerated by this version of the protocol. These improvements will enable us to integrate TAPS in our existing prototype applications as a way to reinforce the trust of users in disseminated information, recommendations, and ultimately in the implementation of a real-world social-market platform.

  Fig. 1

Fig. 2 :

 2 Fig. 2: Trust values distribution for different traces (left), impact of trust density (right).Impact of Trust Transitivity. Figure3confirms the above observation by examining the impact of trust transitivity, τ , on performance in the binary-0.8 (left) and in the multi-value-1 traces. Results show that the performance of TAPS is particularly good when trust decays faster. A faster decay gives more importance to nodes that are closer in the social network even if they may have poorer similarity values. This suggests that a protocol like TAPS becomes more and more important when it is being used for important transactions and in situations in which people can tolerate only limited amounts of risk.

  Figure3confirms the above observation by examining the impact of trust transitivity, τ , on performance in the binary-0.8 (left) and in the multi-value-1 traces. Results show that the performance of TAPS is particularly good when trust decays faster. A faster decay gives more importance to nodes that are closer in the social network even if they may have poorer similarity values. This suggests that a protocol like TAPS becomes more and more important when it is being used for important transactions and in situations in which people can tolerate only limited amounts of risk.

Fig. 3 :

 3 Fig. 3: Impact of τ in the binary (left) and multi-valued (right) traces.

Fig. 4 :

 4 Fig. 4: Impact of in the binary (left) and multi-valued (right) traces.

  Fig. 5: Cumulative distributions of the local clustering coefficients (left) and of the in-degree (right) distributions for TAPS-based and standard protocols.

www.couchsurfing.org is a social community supporting the exchange of accommodation between its users.

Similar to[START_REF] Bertier | The gossple anonymous social network[END_REF], we choose c = 5.

Network A at http://current.cs.ucsb.edu/facebook/index.html.

Acknowledgments This work is supported by the ERC Starting Grant GOSSPLE number 204742. We are grateful to Guang Tan for his initial contributions, as well as to the anonymous reviewers for their constructive suggestions.


Pierre Riteau
email: pierre.riteau@irisa.fr

Kate Keahey
email: keahey@mcs.anl.gov

Christine Morin
email: christine.morin@inria.fr

Bringing Elastic MapReduce to Scientific Clouds

Keywords: MapReduce, Cloud Computing, Elastic MapReduce, Hadoop

The MapReduce programming model, proposed by Google, offers a simple and efficient way to perform distributed computation over large data sets. The Apache Hadoop framework is a free and open-source implementation of MapReduce. To simplify the usage of Hadoop, Amazon Web Services provides Elastic MapReduce, a web service that enables users to submit MapReduce jobs. Elastic MapReduce takes care of resource provisioning, Hadoop configuration and performance tuning, data staging, fault tolerance, etc. This service drastically reduces the entry barrier to perform MapReduce computations in the cloud. However, Elastic MapReduce is limited to using Amazon EC2 resources, and requires an extra fee. In this paper, we present our work towards creating an implementation of Elastic MapReduce which is able to use resources from other clouds than Amazon EC2, such as scientific clouds. This work will also serve as a foundation for more advanced experiments, such as performing MapReduce computations over multiple distributed clouds.

INTRODUCTION

The MapReduce programming model [START_REF] Dean | MapReduce: Simplified Data Processing on Large Clusters[END_REF] proposed by Google offers a simple way to perform distributed computation over large data sets. Users provide a map and a reduce function. The map function takes a set of input key/value pairs, and produces intermediate key/value pairs. The reduce function merges intermediate key/value pairs together to produce the result of the computation. This programming model became popular because it is simple yet expressive enough to perform a large variety of computing tasks, from data mining to scientific computations. This programming model is backed by a large framework that takes care of scheduling tasks to workers, sharing data through a distributed file system, handling faults, etc. The Apache Hadoop [START_REF]Apache Hadoop[END_REF] project develops a free and opensource implementation of the MapReduce framework. This framework is heavily used by companies such as Yahoo! and Facebook to perform thousands of computations per day over petabytes of data [START_REF] Thusoo | Data warehousing and analytics infrastructure at Facebook[END_REF]. However, managing a Hadoop cluster can require some expertise, especially when scaling to a large number of machines. Moreover, users wanting to perform MapReduce computations in cloud computing environments need to instantiate and manage virtual resources, which further complicates the process.

To lower the entry barrier for performing MapReduce computations in the cloud, Amazon Web Services provides Elastic MapReduce [START_REF]Amazon Elastic MapReduce[END_REF]. Elastic MapReduce is a web service to which users submit MapReduce jobs. The service takes care of provisioning resources, configuring and tuning Hadoop, staging data, monitoring job execution, instantiating new virtual machines in case of failure, etc. However, this service has a number of limitations. First, it is restricted to Amazon EC2 resources. Users are not able to use Elastic MapReduce with resources from other public clouds or from private clouds, which might be less expensive. This is especially true for scientists who can have access to scientific clouds [START_REF] Keahey | Science Clouds: Early Experiences in Cloud Computing for Scientific Applications[END_REF]. Moreover, Elastic MapReduce is provided for an hourly fee, in addition to the cost of EC2 resources. This fee ranges from 17% to 21% of the EC2 resource cost. Second, users are not able to use all types of instances provided by Amazon. For instance, it is not possible to use spot instances, even though this could lead to a substantial cost reduction [START_REF] Chohan | See spot run: using spot instances for MapReduce workflows[END_REF]. It is also impossible to use a different virtual machine image than the one provided by Amazon, which is based on Debian 5.0.

Providing an implementation of Elastic MapReduce without these limitations would make it much easier for scientists to take advantage of resources from scientific clouds. Moreover, it can serve as a foundation for MapReduce research, such as evaluating MapReduce computations over multiple clouds. In this paper, we present our ongoing work towards creating this implementation.

AMAZON ELASTIC MAPREDUCE

Amazon Elastic MapReduce is part of the Amazon Web Services infrastructure. After signing up (and providing a credit card number), users can submit MapReduce jobs through the AWS management console (a web interface), through a command line tool, or by directly calling the web service API (libraries to access the Elastic MapReduce API are available for programming languages such as Java and Python).

Users interact with Elastic MapReduce by submitting job flows. Before executing a job flow, Elastic MapReduce provisions a Hadoop cluster using Amazon EC2 resources. Then, the service executes bootstrap actions, which are scripts specified by users. These actions allow users to provide some level of customization of the Hadoop appliance. A job flow contains a sequence of steps, which are executed in order. Internally, each step corresponds to a Hadoop job. After all steps are executed, the cluster is shut down. Users can ask for the cluster to be kept alive, which can be useful for debugging job flows, or submitting multiple job flows without waiting for cluster provisioning and paying extra usage (instance cost is rounded up to the hour).

Typically, input data is fetched from Amazon S3. Intermediate data is stored in HDFS, the Hadoop Distributed File System. Output data is saved in Amazon S3, since the HDFS file system is destroyed when the Hadoop cluster is terminated.

DESIGN AND IMPLEMENTATION

Our Elastic MapReduce prototype, which is work in progress, currently implements a subset of the Amazon Elastic MapReduce service. Users are able to submit job flows and query job flow statuses. The corresponding API calls are Run-JobFlow and DescribeJobFlows. Job flows written using SQL-like languages (Hive and Pig) are not supported yet.

When a new job flow request is received and after its parameters are validated, the service contacts a cloud on behalf of the user to provision a Hadoop cluster. A Hadoop cluster is composed of a master node and multiple slave nodes. The master node runs the NameNode service (the meta data server of the HDFS file system) and the JobTracker service (which receives and schedules jobs to slave nodes). Slave nodes run the DataNode service (which provides data storage to HDFS) and the TaskTracker service (which executes map and reduce computations). By leveraging the EC2 API to provision Hadoop clusters, our implementation is able to get resources from most clouds managed by open-source toolkits (Nimbus, OpenNebula, Eucalyptus).

Once an Hadoop cluster is provisioned and configured, each step in the job flow is executed as a Hadoop job. Steps specify input data and output locations, usually as S3 URLs. Hadoop supports getting and storing data directly from Amazon S3. This means it is possible to provide our Hadoop clusters with input data from Amazon S3, like in Amazon Elastic MapReduce. However, since traffic from Amazon S3 to the outside world is charged to users, this would incur a high cost. Also, bandwidth constraints between Amazon S3 and the cloud running the Hadoop cluster would reduce performance. We assume that clouds used with our Elastic MapReduce implementation will typically have a storage service available. For instance, both Nimbus [START_REF]Nimbus[END_REF] and Eucalyptus [START_REF] Nurmi | The Eucalyptus Open-Source Cloud-Computing System[END_REF] provide S3 implementations (respectively called Cumulus and Walrus). Currently, our system fetches input data from a local repository using Boto, a Python library supporting the S3 API, and stores it in HDFS. Similarly, output data is stored into the local repository after a step is finished. We are currently investigating how we can configure or modify Hadoop to use an alternate S3 repository.

For validating our prototype, we execute job flows on resources provisioned from the Nimbus [START_REF]Nimbus[END_REF] cloud running of the University of Chicago FutureGrid cluster.

RELATED WORK

Gunarathne et al. [START_REF] Gunarathne | MapReduce in the Clouds for Science[END_REF] proposed a MapReduce implementation built on top of Microsoft Azure cloud services. Their work advocates for using MapReduce systems on other clouds than Amazon EC2. Chohan et al. [START_REF] Chohan | See spot run: using spot instances for MapReduce workflows[END_REF] propose using spot instances to execute MapReduce jobs. Spot instances are Amazon EC2 instances which have a variable cost, depending on infrastructure load, and can be killed at any time. We plan to study spot instance usage in our implementation.

CONCLUSION AND FUTURE WORKS

In this paper, we presented our ongoing work towards creating an Elastic MapReduce implementation that allows users to take advantage of resources other than Amazon EC2 instances, such as resources from scientific clouds. Our system takes care of provisioning Hadoop clusters and submitting jobs, allowing users to focus on writing their MapReduce application rather than managing cloud resources. In the near future, we will evaluate our implementation compared to Amazon Elastic MapReduce, for example by analyzing cluster instantiation time, performance, and cost. We also plan to use our system to experiment with MapReduce jobs over multiple distributed clouds.


V Padois
email: vpadois@enit.fr

J-Y Fourquet
email: fourquet@enit.fr

P Chiron
email: pchiron@enit.fr

M Renaud
email: renaud@laas.fr

On contact transition for nonholonomic mobile manipulators

This work is devoted to planning and execution of complex missions in Robotics. Robotics has evolved from an industrial, repetitive framework to application domains with much more variability of tasks, with increasing complexity in uncertain environment. This is clearly the case for Service Robotics e.g. but even industrial robots have now to work in environment not totally calibrated for the task they have to perform. The result is that the classical decomposition in static ordered local tasks cannot apply in presence of such a variability. It has a poor dynamic performance and cannot cope with uncertainties. Our work is organized around a complex mission: "Go to the blackboard and write" for mobile manipulators that have capabilities of locomotion and manipulation. It is a simple and intuitive example of a complex mission that relies on different sensors, exhibits different operating modes and needs to switch between different feedbacks and set-points. Our approach is based on Hybrid Dynamical Systems. It is focused on dynamical sequencing of control laws that ensures good transients, robustness and allows to update the mission at every transition from one mode to another. Simulation have been realized with matlab Simulink and Stateflow toolboxes and experimental validation is developed within the G en om controller on the h2bis nonholonomic mobile manipulator.

Introduction

For many years, research community in robotics has proposed numerous solutions allowing manipulators and, more recently, mobile manipulators to solve specific tasks. In the literature, contributions concerning the motion in free space of the endeffector, whose location is denoted ξ, are clearly separated from the ones dealing with constrained motion for which contact force f is imposed together with ξ. In the first ones, it is assumed that no contact force can occur whereas the second category considers that the contact is realized from the beginning. Regarding manipulators, many modeling issues -at dynamic and kinematic level -and related control schemes can be found in reference textbooks [START_REF] Spong | Robot Dynamics and Control[END_REF][START_REF] Sciavicco | Modelling and control of robot manipulators[END_REF][START_REF] Khalil | Modeling, Identification and Control of Robots[END_REF]. Methods and models have also been proposed to deal with the control of mobile manipulators. Modeling issues can be found in [START_REF] Bayle | Kinematic modelling of wheeled mobile manipulators[END_REF][START_REF] Campion | Structural Properties and Classification of Kinematic and Dynamic Models of Wheeled Mobile Robots[END_REF] and control issues are exposed in [START_REF] Umeda | Hybrid position/force control of a mobile manipulator based on cooperative task sharing[END_REF][START_REF] Yamamoto | Control and coordination of locomotion and manipulation of a wheeled mobile manipulator[END_REF]. Thus, the approach generally adopted when considering a complex problem is to decompose it in a sequence of elementary subproblems, and then to solve independently each subproblem. This approach has the merit to permit the study of each step of the sequence in a simple way since it disregards the other steps. It is particularly suited when the environment can be adapted to the task and when this task is repetitive enough to deserve ad hoc tuning. These features are usual in an industrial framework that requires a low versatility of the robotic system. Now, new directions, both in service and manufacturing robotics, lead to embed these techniques in missions where uncertainty and variability are much more important. Wheeled locomotion, for instance, naturally produces positioning uncertainty. Environment is less calibrated and tasks are less repetitive. At the same time, it seems pertinent to build the solution from the library of classical methods by chaining them dynamically. So, it is necessary to adapt and combine existing strategies for local tasks in order to realize complex missions with good transients. Even if the objectives of our work are more general, the work presented here is sufficiently rich to point out problems and features of a more generic complex mission in robotics. It is organized around one kind of mission: From an imposed end-effector location, a free space motion is followed by a trajectory tracking over a surface along which a normal force is imposed, and around one kind of system: A nonholonomic mobile manipulator, kinematically redundant, built from a serial arm mounted on a wheeled mobile platform. This system is equipped with a force sensor that measures contact forces at the end-effector. We made the choice of a description based on the Hybrid Dynamical Systems formalism where switchings among a finite number of modes occur when particular events are detected. Modes are linked to different set-points and control laws. The emphasis is made on the dynamical nature of the sequence of elementary modes and more particularly on the contact transition problem (i. e. transition from free space to constrained effector motion). This issue has been emphasized very early for manipulators [START_REF] Paul | Problems and research issues associated with the hybrid control of force and displacement[END_REF] but only a little number of authors has actually studied it (e. g. [START_REF] Mills | Control of robotic manipulators during general tasks execution: A discontinuous control approach[END_REF][START_REF] Hyde | Controlling Contact Transition[END_REF][START_REF] Walker | Impact configurations and measures for kinematically redundant and multiple armed robot systems[END_REF]). These works mainly deal with stability issues and impact modeling. Recently, Yu and Pagilla [START_REF] Yu | A Switching Control Scheme for Constrained Robot Tasks[END_REF] have presented a method that allows to cope with geometric uncertainties of the contact surface location. Doh et al. [START_REF] Doh | On hard contact force control[END_REF] have also proposed a specific control law that aims at avoiding large bounces during hard contact transitions. With regard to mobile manipulators, the contact transition problem is an emerging field of research that has not been extensively studied yet. Nonetheless, one can refer to the work of Nagatani et al. [START_REF] Nagatani | Door-opening behaviour of an autonomous mobile manipulator by sequence of action primitives[END_REF] focused on static chaining of primitives ("Open the door") but also to the work of Kang et al. [START_REF] Kang | Utilization of inertial effect in damping-based posture control of mobile manipulator[END_REF] focused on the utilization of inertial effect when controlling holonomic mobile manipulators.

Structuring and planning the mission

In our approach a mission is described by k modes or local tasks, and by a switching pattern that describes the sequencing of the local tasks. The switching pattern can be represented using a finite state machine. States corresponds to modes and transitions are activated by events: time elapsed or detection of a sensor threshold value. Using this formal description and the mission parameters, a first off-line planning step leads to "a perfect plan" that describes the ideal temporal evolution of the variables to control (i. e. the set-points or trajectories to track) and contains the calculated threshold values and time windows needed to define the transition conditions between modes. A state machine is then instantiated with these values. During the mission, this instantiated state machine creates indicators used to switch between the different phases of the plan and among a set of control schemes. At each transition, the "perfect plan" is updated thanks to the different signals and values of the variables describing the mission (e. g. the relative location of the end-effector in the environment frame is updated at contact time). This update allows to cope with uncertainties due to poor parameter estimations of both the robot (drift of the platform, sensors resolution) and the environment. Thus, transition from a task to the following one occurs asynchronously but in a predictable time (or space) interval. Any large drift in the transition date or in the value of a controlled variable corresponds to an anomaly that cannot be interpreted as the result of these uncertainties and leads to a premature stop of the mission. We consider the case of mobile manipulators composed of a mobile platform with two independent driving wheels and a serial manipulator with n b joints. Such a system is depicted on figure 1 in a planar (right) or in a 3-dimensional version (left). This latter is the one used for the experiments. It has velocity controlled joints with high ratio gear reduction (i. e. the torque at each joints cannot directly be controlled) and so needs to rely on kinematic control schemes. Thus, we hereafter present some kinematics modeling results regarding mobile manipulators based on Bayle et al. work [START_REF] Bayle | Kinematic modelling of wheeled mobile manipulators[END_REF][START_REF] Bayle | Manipulability of wheeled mobile manipulation: application to motion generation[END_REF]. Nonetheless, dynamics are taken into account in impact reduction control scheme. The configuration of such a mobile manipulator is completely defined using vector q = [ q b q p ] T where q b = [ q b1 . . . q bn b ] T and q p = [ θ r θ l x Op y Op ϑ ] T respectively represent the manipulator configuration and the platform configuration. Its end-effector location (i. e. location of

Modeling of a mobile manipulator

R EE = (O EE , -→ x EE , -→ y EE , -→ z EE ) in R = (O, -→ x , -→ y , -→ z )
) can be described using a minimal set of parameters ξ = [ ξ 1 . . . ξ m ] T . ξ is expressed as a non linear function of q. Differentiating it, the relation between ξ and q is given by: ξ = J(q) q with J(q) a m × n matrix and n = n b + 5.

(1)

In addition, the rolling without slipping constraint acting on the platform's wheels is nonholonomic and so, components of q cannot vary independently. Then, one can define a vector u = [ u b u p ] of independent parameters (i. e. taking the nonholonomic constraints into account) such as: q = T (q)u.

Defining J(q) = J(q)T (q) equation ( 1) becomes: ξ = J(q)u. This equation completely describes the mobile manipulator kinematics. This model is called instantaneous posture kinematic model in [START_REF] Bayle | Modélisation et commande cinématiques des manipulateurs mobiles à roues[END_REF]. A natural choice for u ∈ R n (n = n b + 2) is u b = q b and u p can be chosen as [ θr θl ] T or [ v ω] T where v and ω are respectively the linear and angular velocities of the platform.

When m < n, the mobile manipulator is said to be kinematically redundant. This property provides the capability to choose a particular kinematic control vector u among those giving the prescribed end-effector velocity ξ by using the relation:

u = J(q) ξ + (I -J(q) J(q))z, (2)
where J(q) is any generalized inverse of J(q) and z any n × 1 vector. Note that, among the generalized inverses, authors generally choose the pseudo-inverse [START_REF] Doty | A theory of generalized inverses applied to Robotics[END_REF] and that the second right-hand term of equation ( 2) gives rise to the so-called "internal motion" control term since it does not provide any end-effector velocity.

Control schemes and use of the redundancy for the "Go to the blackboard and write" mission

An ad hoc decomposition of this mission is given by the finite state machine on figure 2.

Figure2. High-level finite state machine for the "go to the blackboard and write mission"

Operational kinematic control

Operational kinematic control uses a two stages control structure. The first stage is at the actuator level. Each actuator has its own velocity control loop. In our case, these controllers are digital PID regulators. The second stage is at end-effector level. Given ξ * and ξ * desired end-effector speed and location to track, and a positive definite weighting matrix W reg , the control vector defined by:

u = J(q) ( ξ * + W reg (ξ * -ξ)) + (I -J(q) J(q))z, (3)
ensures an asymptotic decreasing of e = ξ * -ξ toward 0 and z is chosen such as to minimize a scalar function (a potential function) P(q) [3].

Hybrid speed / force controller

The hybrid speed / force controller is a modified version of the well known work by Raibert and Craig [START_REF] Raibert | Hybrid position/force control of manipulators[END_REF].

Figure3. Hybrid speed / force scheme control.

Once the contact established, the robot's end-effector cannot independently exert a displacement and a force in the same direction. One has to choose the direction to be position or speed controlled and the direction to be force controlled. -→ n c being the unit vector normal to the environment surface at contact point, a smart choice for the reference frame R is -→ x = --→ n c . Thus, one can create a m × m diagonal selection matrix S where ones or zeros are placed on the diagonal respectively to indicate whether the component of ξ corresponding to the line in S is speed or force controlled. The control vector is then calculated as the sum of three terms:

u = u s + u f + u r with (4)
u s = J(q) S ξs , u f = J(q) (I -S) ξf and u r = (I -J(q) J(q))z.

(

) 5
ξs and ξf are the control vectors whose simple versions are given by:

ξs = ξ * + W regs (ξ * -ξ), and ξf = W reg f (f * -f ), (6)
where W regs and W reg f are two positive definite weighting matrices. A block description of this control scheme is given by figure 3.

Use of redundancy

We expose here a set of functions to optimize using the internal motion. Many other functions may be used but these ones seem to be relevant according to the considered mission.

Manipulability maximization:

The manipulability notion was first introduced for manipulators (cf. [START_REF] Yoshikawa | Foundations of robotics -Analysis and Control[END_REF] for a detailed presentation of this notion) but was also extended to mobile manipulators in [START_REF] Bayle | Manipulability of wheeled mobile manipulation: application to motion generation[END_REF]. The different manipulability measures are quantitative indicators representing the ease to instantly move the end-effector in any direction. Maximizing any of these indicators tends to avoid singular configuration of the system and thus to avoid high joints speed. Impact force reduction: During the transition tasks, it is interesting to re-configure the mobile manipulator using internal motion so as to give it good inertial properties.

Results concerning holonomic mobile manipulators are presented in [START_REF] Kang | Utilization of inertial effect in damping-based posture control of mobile manipulator[END_REF]. The notion of impulse force F is used in [START_REF] Walker | Impact configurations and measures for kinematically redundant and multiple armed robot systems[END_REF] and is defined as:

F = lim ∆t→0 t+∆t t f (s)ds, ( 7
)
where t is the impact time. Using the dynamic model of the system (i. e. the model establishing the relation between physical effects of motion, actuating torques and contact forces at end-effector level), the magnitude F of F is expressed as:

F = -(1 + e)v T impact n c n T c C(q)n c . (8)
v T impact is defined as the linear speed of the end-effector at the impact time, e is the restitution coefficient (i. e. a physical characteristic of the contact) and C(q) is an inertia-related matrix.

To minimize F , one can:

• plan a low impact speed but uncertainties in the plan execution may lead to higher values than the planned one, • maximize, using internal motion, n T c C(q)n c which is configuration dependent. It directly acts on the inertial properties of the manipulator.

Collision avoidance:

Techniques to avoid obstacles have extensively been studied in the case of mobile robots. However, the problem to solve here is more complicated since the end-effector is constrained by the manipulation task. Hence, to avoid collision of the platform with the surface of contact, the potential function to maximize is chosen as the distance between the surface and point O p .

Experimental system and simulation results

Experiments are being developed on the system depicted on left figure 1. In order to easily test different control structures and schemes, we also developed a simulator using Matlab and Simulink. We hereafter detail the experimental and simulation frameworks and we then present some results obtained using the simulator.

Experimental framework

The mobile platform is actuated using two independent driving wheels (i. e. an HILARE type platform). The manipulator is a 6R serial arm called GT6A. The whole system, H2bis, is controlled using on board calculators equipped with the real time operating system VxWorks and running on Motorola 68000 and Apple Power PC cards. Control algorithms are implemented using G en om, a generator of software control modules developed, as well as the robot, in the RIA team of the LAAS laboratory. At actuator level, the control sampling time is 5ms (the smaller one admitted by the control modules) whereas at operational level we chose it to be either 10 or 20ms. The 6-axis GIROBO force / torque sensor bandwidth is 100Hz.

Simulation framework

Robot: The robot is modeled at kinematic and dynamic levels as a continuous system. Actuators (dc motors) are modeled as second order linear systems and we take into account load torques due to dynamic effects of motion or due to contact. We also take into account saturations of the actuators. Sensors: Force sensor inaccuracy is modeled together with additive noise. Force signal is sampled with a period of 10ms to reflect the effects of its limited bandwidth. Contact: Contact between the end-effector and the environment is locally modeled either as a {spring // damper} system (i. e. Kelvin-Voigt visco-elastic model) or as a spring system. When running simulations, we consider that the values of the parameters characterizing the contact are unknown or poorly estimated. Controllers: Actuators' controllers are modeled as digital PID regulators whose sampling time is 5ms. The operational level controller is also implemented as a digital controller. We consider its sampling time as an off-line tunable parameter whose minimum value is 10ms.

"Go to the blackboard and write": Simulation results

System depicted on right figure 1 is chosen for simulation. ξ is chosen as the endeffector position and u = [ qb1 qb2 θr θl ] T . The reference frame is attached to the blackboard whose surface is defined by equation x = 0. Thus, f is defined as the vector whose components are the normal and tangential force to the blackboard. Once the contact established, the normal direction is force controlled whereas the tangential direction is speed controlled.

Impact force reduction Simulation whose parameters are described in table 1 illustrates the effects of using kinematic redundancy to reduce impact peak force. 3) whereas the second one uses a potential function aiming at minimizing impact forces (cf. equation ( 8)). This potential is activated during a given period of time ∆T p around the planned impact time. Figure 4 (left) shows that force overshoot is decreased from 80% to 20% of the final desired value. Figures 4 (right) and 5 show how internal motions generated by the potential modify the evolution of each coordinate. Inertial characteristics depend on the arm configuration and it is expected that the use of this particular potential mainly affects the manipulator generalized coordinates. Indeed, q b1 and q b2 are the more influenced by the internal motion resulting from the chosen potential. However, the other coordinates are also modified since motion of the platform must compensate for manipulator motion.

According to the current configuration, the action of a potential may cause rough variations of generalized velocities that could be inconsistent with the velocity bounds of the system. Hence, the potential is introduced here with a time-varying coefficient ensuring velocity continuity and allowable velocities and accelerations for the system.

Conclusion

The aim of this study was to propose a method to control dynamic contact transition for nonholonomic mobile manipulators. The method is based on the decomposition of complex mission in elementary tasks to sequence. A particular attention is paid to transition phases. A simulator, taking into account the physical system's constraints, was developed and allows to test different control structures and schemes. The obtained results show the efficiency of the proposed method. In particular, a smart use of the kinematic redundancy of the system allows to correctly control the contact transition phase. The principle of the proposed approach was validated using simulation and is being confirmed using experiments currently developed on robot H 2 bis.

Further developments are also led to propose a systematic method to generalize the sequence and scaling of different potential functions in a same mission.

Figure1.

  Figure1. (left) H2bis: a 3-dimensional mobile manipulator; (right) A planar mobile manipulator.

T 3 Table1.Figure4.

 3 Figure4. Impact force reduction: (left) Normal contact force comparison. (right) Robot configuration at impact time.

Figures 4 and 5

 5 Figures 4 and 5 have been obtained with two simulations: the first one is such that z = 0 in equation (3) whereas the second one uses a potential function aiming at minimizing impact forces (cf. equation (8)). This potential is activated during a given period of time ∆T p around the planned impact time. Figure4(left) shows that force overshoot is decreased from 80% to 20% of the final desired value. Figures 4 (right) and 5 show how internal motions generated by the potential modify the evolution of each coordinate. Inertial characteristics depend on the arm configuration and it is expected that the use of this particular potential mainly affects the manipulator generalized coordinates. Indeed, q b1 and q b2 are the more influenced by the internal motion resulting from the chosen potential. However, the other coordinates are also modified since motion of the platform must compensate for manipulator motion. According to the current configuration, the action of a potential may cause rough variations of generalized velocities that could be inconsistent with the velocity bounds of the system. Hence, the potential is introduced here with a time-varying coefficient ensuring velocity continuity and allowable velocities and accelerations for the system.

Figure5.

  Figure5. Impact force reduction: Effects on the position and speed of the different robot's bodies.

Acknowledgment: This work is partially supported by the French cnrs Robea program within the project Dynamic sequencing of multi-sensor based tasks for complex motions execution in mobile robotics.