F Bouillot
email: bouillot@lirmm.fr

P Nhat

N Béchet

S Bringay
email: bringay@lirmm.fr

D Ienco
email: dino.ienco@teledetection.fr

S Matwin

P Poncelet
email: poncelet@lirmm.fr

M Roche
email: mroche@lirmm.fr

M Teisseire

How to Extract Relevant Knowledge from Tweets?

Tweets exchanged over the Internet are an important source of information even if their characteristics make them difficult to analyze (e.g., a maximum of 140 characters; noisy data). In this paper, we investigate two different problems. The first one is related to the extraction of representative terms from a set of tweets. More precisely we address the following question: are traditional information retrieval measures appropriate when dealing with tweets?. The second problem is related to the evolution of tweets over time for a set of users. With the development of data mining approaches, lots of very efficient methods have been defined to extract patterns hidden in the huge amount of data available. More recently new spatio-temporal data mining approaches have specifically been defined for dealing with the huge amount of moving object data that can be obtained from the improvement in positioning technology. Due to particularity of tweets, the second question we investigate is the following: are spatio-temporal mining algorithms appropriate for better understanding the behavior of communities over time? These two problems are illustrated through real applications concerning both health and political tweets.

Introduction

In recent years, the development of social and collaborative Web 2.0 underlines the central and active role of users in collaborative networks. Blogs to spread diaries, RSS news to track last information on a specific topic, tweets to publish social actions, are now extremely widespread. Easy to create and manage these tools are used by Internet users, businesses or other organizations to communicate about themselves and the growing use of this technology starts to influence many aspect of the real life. Furthermore, this data represents an important source of information that can be exploited in the decision making process.

Since its introduction in 2006, the Twitter website 6 has become so popular that it is currently ranked as the 10 th most visited site over the world 7 . In January 2012, Twitter has been visited 2.5 billion times and in October 2011, more than 250 million tweets are posted every day with a user base of about 300 million people. Basically, Twitter is a platform for microblogging. It means that it is a system for sharing information where users can either follow other users who post short messages (i.e. 140 characters), or can be followed. When a user follows a person, the user receives all messages from this person, and in turn, when that user tweets, all his followers will receive the messages. Tweets are associated with meta-information that cannot be included in messages (e.g., date, location, etc.) or included in the message in the form of tags having a special meaning. For example the tag @username means that you are sending a message to a particular user, the # topic assigns a specific topic, RT means that the message was re-tweeted, i.e. send to all the followers. Actually, by taking into account all this meta-information, we can observe that tweets can be represented in a multidimensional way with, for instance, one dimension for the location, one dimension for the time, one dimension for the set of words used, etc. In this context, different systems were proposed to analyze this flow of information [START_REF] Sakaki | Earthquake Shakes Twitter Users: Real-time Event Detection by Social Sensors[END_REF][START_REF] Mathioudakis | Twittermonitor: trend detection over the twitter stream[END_REF][START_REF] Li | Twevent: Segment-based event detection from tweets[END_REF]. For instance, they can focus on event detection [START_REF] Li | Twevent: Segment-based event detection from tweets[END_REF], Name Entity recognition [START_REF] Li | Twiner: Named entity recognition in targeted twitter stream[END_REF], can combine different types of information such as timeline and sentiment features [START_REF] Tsolmon | Extracting social events based on timeline and sentiment analysis in twitter corpus[END_REF] or even analyze propagation from specific features such as hashtags [START_REF] Barbosa | Robust sentiment detection on twitter from biased and noisy data[END_REF].

Nevertheless all these approaches do not really exploit their multidimensional characteristics. In [START_REF] Bringay | Towards an on-line analysis of tweets processing[END_REF], we propose to address these multidimensional characteristics by focusing on datawarehouses [START_REF] Codd | Providing olap (on-line analytical processing) to user-analysts: An it mandate[END_REF] since they provide very efficient tool for the storage and analysis of multidimensional and historized data. Our main goal was to using the facilities provided by these tool to manipulate a set of indicators (measures) according to the different dimensions obtained from tweets and for which we can be provide some hierarchies. Furthermore associated operators (e.g., Roll-up, Drill-down, etc.) allow an intuitive navigation on different levels of the hierarchy. In this paper we focus on the problems associated with the definition of such measures when dealing with hierarchies and propose some extension that are well adapted to our concern. In order to illustrate how such a tool can be useful we report some results on experiments conducted on the health domain.

By using a multidimensional tool we are able to really help the end user to analyze the data over time. Nevertheless one problem remains. As we are provided with a huge amount of data, applying data mining techniques seems relevant to highlight knowledge hidden in the data. Among the different techniques we investigate if pattern mining approaches are appropriate to understand users' behaviors. More precisely we focus on trajectory mining algorithms to analyze behavior of communities of user. Basically they are defined for dealing with spatio-temporal data. We show that measures defined for tweet datawarehouse can also be used to define new kinds of trajectories related to tweet terms rather than spatial information. We illustrate some trajectories that can be extracted from the analysis of the evolution of French political communities8 over Twitter during 2012 which was particularly important for French political communities dues the two main elections: Presidential and Legislative.

The remainder of this paper is organized as follows. Section 2 investigates how multidimensional characteristics can be handled and focus on different kinds of useful measures. It also illustrates some results by using tweets related to diseases. We address the problem of pattern mining in Section 3. After a brief presentation of trajectory approaches we illustrate how these patterns can be useful to understand users' behaviors over time. Finally Section 4 concludes the paper and presents future work.

Towards a Datawarehouse for Analyzing Tweets

In this section we propose a minimal model for dealing with multidimensional characteristics of tweets. We mainly focus on three dimensions: the dimension Word corresponding to the set of words (or terms) that can be extracted from tweets, the dimension location that can be extracted from metadata and the time dimension. Furthermore we illustrate the model through tweets expressed in the health domain.

The Model

According to [START_REF] Pérez-Martínez | Contextualizing data warehouses with documents[END_REF], a fact table F is defined on the schema D = {T , . . . , T n , M } where T i (i = 1, .., n) are the dimensions and M stands for a measure. Each dimension T i is defined over a domain D partitioned into a set of categories C j . We thus have D = ∪ j C j . D is also provided with a partial order ⊑ D to compare the values of the domain D. Each category represents the values associated with a level of granularity. We note e ∈ D to specify that e is a value of the dimension D if there is a category C j ⊆ D such that e ∈ ∪ j C j . Note that two special categories are distinguished and are present on all dimensions: ⊥ D et ⊤ D ∈ C D corresponding respectively to the level of finer and higher granularity. In our approach, the partial order defined on the domains of the dimensions stands for the inclusion of keywords associated to the values of the dimensions. Thus, let e 1 , e 2 ∈ ∪ j C j be two values, we have e 1 ⊑ D e 2 if e 1 is logically contained in e 2 . Figure 2 illustrates the associated schema. We find the dimension location and the dimension time as ⊥ temps = day ≤ month ≤ semester ≤ year ≤ ⊤ temps . For the hierarchy, we use the MeSH (Medical Subject Headings) 9 National Library of Medicine's controlled vocabulary thesaurus. It consists of sets of terms naming descriptors in a twelve-level hierarchy that permits searching at various levels of specificity. At the most general level of the hierarchical structure are very broad headings such as "Anatomy" or "Mental Disorders". More specific headings are found at more narrow levels, such as "Ankle" and "Conduct Disorder". In 2011, 26,142 descriptors are available in MeSH. There are also over 177,000 entry terms that assist in finding the most appropriate MeSH Heading, for example, "Vitamin C" is an entry term to "Ascorbic Acid".

Some Proposed Measures

Traditionally, the T F -IDF measure (Term Frequency -Inverse Document Frequency), introduced by [START_REF] Salton | A vector space model for automatic indexing[END_REF], is a very useful measure that giving greater weight to the discriminant terms and can thus be well adapted to our concern. As a first step, it is necessary to compute the frequency of a term (Term Frequency) corresponding to the number of occurrences of the term in the document 10 . Thus, for the document d j and the term t i , the frequency of the term in the document is given by the following equation:

T F i,j = n i,j
k n k,j where n i,j stands for the number of occurrences of the term t i in d j . The denominator is the number of occurrences of all terms in the document d j .

The IDF (Inverse Document Frequency) measures the importance of the term in the corpus. It is defined as follows:

IDF i = log 2 |D| |{d j : t i ∈ d j }|
where |D| stands for the total number of documents in the corpus and |{d j : t i ∈ d j }| is the number of documents having the term t i .

Finally, the TD-IDF is obtained as follows:

T F -IDF i,j = T F i,j × IDF i
Nevertheless relying only on knowledge of the hierarchy in a cube does not always allow a good aggregation (i.e., corresponding to a real situation). For instance, the characteristics of the words in tweets are not necessarily the same in a State and in a City. In [START_REF] Bringay | Towards an on-line analysis of tweets processing[END_REF], in a very different context, we proposed a new measure called T F -IDF adaptative . This measure has been defined in order not to focus on the number of documents but rather to the number of documents for a specific class and take into account the level in the hierarchy. So in our case, this measure is well adapted for handling available hierarchies as it does not calculate the representative terms from the number of documents but rather from the desired class at a specific level. It is defined as follows:

T F i,j -IDF k i = n i,j k n k,j × log 2 |E k | |{e k j : t i ∈ e k j }|
where |E k | stands for the total number of elements of type k (in our example, k = {City, State, Country}) which corresponds to the level of the hierarchy that the decision maker wants to aggregate. |{e j : t i ∈ e j }| is relative to the number of elements of type k where the term t i appears. Thus, we define IDF adaptive as follows:

IDF C l i = log 2 m |{C l : t i ∈ C l }|
where m stands for the total number of communities. |{C l : t i ∈ C l }| is the number of communities C l where the term t i appears.

Actually, this adaptive measure can be easily generalized for taking into account the different level of the hierarchies as well as the information the user is interested in. Then it is possible to define a context C = n, l, type where n stands for one node in the hierarchy, l the level of the hierarchy the user would like to extract information and type corresponds to the type of information, i.e. element of a specific level (e.g. city) or tweets for this level. For a context C and a term t i , the Generalized IDF is defined as follows:

Generalized IDF C,i,j∈type = log 2 |type l | f (type)
where |type l | stands for the total number of elements of type type occurring in the scope of n at the level l of the hierarchy. f (type) is defined as:

f (type) = if type = Extension D |{d j : t i ∈ Extension D (n, l)}| else |{n k : ∃t i ∈ docs(n k l ) and n k l ∈ Ext(n, l)}|
Depending on the value of type, the f (type) function returns either the number of documents specified in the extension having the term t i or the number of nodes having at least one document with the term t i .

Finally, for a context C and a term t i , the Generalized TF-IDF is defined as:

Generalized T F -IDF C,i,j∈type = T F i,j × Generalized IDF i,j

Illustration

In this section we illustrate how such a model can be useful for the decision maker. To extract the tweets related to the vocabulary used in MeSH, we focus on the tweets related to "Disease" and request Twitter by using all the terms of the corresponding hierarchy. We thus collected 1,801,310 tweets from Janurary 2010 to February 2011 having at least one term of the Disease hierarchy. Experiments were performed by using PostgreSQL 8.4 with the Pentaho Mondrian 3.20 environment. Visualization are done by using the visualization set of tools provided by Google are Figure 3 shows the distribution of words hepatitis, leukomia and pneunomia over the period (excluding US). We can note that the word pneunomia appears a lot in the set of tweets in January 2009 and in February 2010. By using visualization tools it is possible to visualize the worldwide coverage of this disease (Figure 4). This coverage is obtained by fixing the location dimension and by examining the countries for which this word has been selected as more relevant for a country with our measures.

In Figure 4 we can notice that pneunomia has been extensively reported in tweets from Russia, India, Ecuador or Australia. News available at that period might be useful to better understanding this behavior. For instance, in the second week of January 2001, the British singer Trish Keenan died of pneumonia after contracting swine flu in Australia 11 and, in Ecuador, an alarm over cases of severe pneumonia similar to the H1N1 virus was triggered after that the Merced hospital has received 35 cases, 18 occurred in the first week of January, and reported that two people died. and just as serious 12 . In Russia also, In December of 2010, in Yurga /Kemerovo region, over 200 soldiers were taken to hospitals with a bad cold and several people were in critical condition: severe pneumonia 13 . All these events were extensively tweeted or re-tweeted in these countries.

Pattern Mining for Tweets

Usually pattern mining approaches focus on extracting different kinds of patterns (i.e. itemsets, sequences, trees, graphs, etc) hidden in the database. Using these patterns for analyzing tweets is one of the topic addressed by some research work. In this paper we investigate another kind of patterns coming from a very different context: spatio-temporal patterns. Our main objective is to highlight that knowledge extracting can be very useful for the decision maker. Basically, spatio-temporal patterns are defined in a totally different context (i.e spatiotemporal data) and aim to identify groups of moving objects for which a strong relationship and interaction exist within a defined spatial region during a given time duration. Recently, many patterns have been defined such as flocks [START_REF] Vieira | On-line discovery of flock patterns in spatiotemporal data[END_REF], convoys [START_REF] Jeung | Discovery of convoys in trajectory databases[END_REF], swarms, closed swarms [START_REF] Li | Movemine: Mining moving object databases[END_REF], moving clusters [START_REF] Jensen | Continuous clustering of moving objects[END_REF], group pattern [START_REF] Wang | Efficient mining of group patterns from user movement data[END_REF], etc.

Let us assume that we have a group of moving objects O DB = {o 1 , o 2 , . . . , o z }, a set of timestamps T DB = {t 1 , t 2 , . . . , t n } and at each timestamp t i ∈ T DB , spatial information14 x, y for each object. . Usually, in spatio-temporal mining, we are interested in extracting a group of objects staying together during a period of time. Therefore, from now, O = {o i1 , o i2 , . . . , o ip }(O ⊆ O DB ) stands for a group of objects, T = {t a1 , t a2 , . . . , t am } (T ⊆ T DB ) is the set of timestamps within which objects stay together. Let ε be a user-defined threshold standing for a minimum number of objects and min t a minimum number of timestamps. Thus |O| (resp. |T |) must be greater than or equal to ε (resp. min t ). Here we focus on two particular patterns to illustrate. Informally, a swarm is a group of moving objects O containing at least ε individuals which are closed each other for at least min t timestamps. For example, as shown in Figure 5a, if we set ε = 2 and min t = 2, we can find the following swarms ({o 1 , o 2 }, {t 1 , t 3 }), ({o 1 , o 2 }, {t 1 , t 4 }), ({o 1 , o 2 }, {t 3 , t 4 }), ({o 1 , o 2 }, {t 1 , t 3 , t 4 }). We can also note that these swarms are in fact redundant since they can be grouped together in the following closed swarm ({o 1 , o 2 }, {t 1 , t 3 , t 4 }). A convoy is also a group of objects such that these objects are closed each other during at least min t consecutive time points. For instance, on Figure 5, with ε = 2, min t = 2 we have two convoys ({o 1 , o 2 }, {t 1 , t 2 , t 3 , t 4 }) and ({o 1 , o 2 , o 3 }, {t 3 , t 4 }). Recently in [START_REF] Nhan | Get move: An efficient and unifying spatiotemporal pattern mining algorithm for moving objects[END_REF] we proposed Get Move an unifying approach for extracting all these kinds of patterns. Furthermore in [START_REF] Nhat | Mining time relaxed gradual moving object clusters[END_REF], we proposed new kinds of patterns, called gradual patterns. For instance, they can be useful to extract gradual trajectories such as: "From October to December the more time passes, the more Eagle are moving from Canada to Mexico" or "From June to July, the more the time goes by, the more people are going to Miami". All these approaches share the same pre-processing: a clustering algorithm is applied (e.g. DBSCAN) for extracting clusters grouping together objects closed to the same location. During our research we considered that the clustering can be applied in other dimensions. Recently, we defined a new project called PoloP 15 (Political Opinion Mining) which aims to cope with the analysis of the evolution of French political communities over Twitter during 2012 both in terms of relevant terms, opinions, behaviors. 2012 is particularly important for French political communities dues the two main elections: Presidential and Legislative. From the 12th December 2011 to the 19th June 2012, we thus obtained 2,122,012 tweets from 213,005 users. For 130,618 tweets, 232 users can unambiguously be assigned to a political party (i.e. user is a politician or an official political community account). By using our defined measures (C.f. Section 2.2), we can select for different political parties the set of relevant words at different periods (see Figure 6). In order to extract interesting trajectories for different parties we applied a clustering technique, for each party, on the top-k set of relevant terms over time. Thus, we group together users from the same party sharing the same words. Figure 7 illustrates a kind of trajectory that might be extracted from the political tweets. In February 2012, in one of the first debate, the focus of the French election campaign suddenly shifts from the economy to racism and national identity. For the right party, as we can notice, during the debate, most of used words are such that lots of party members shared the same words. Just after the debate, some right party users move to another cluster where words such as "national identity", "France" while other ones shift to other topic like "elections". Actually, during the debate the main trend was to motivate some electors from the extreme right. During this time, as we can notice, in the left party, as it is illustrated through the gradual pattern, the left party uses completely different kinds of words but just when right users behavior split.

Conclusions

In this paper we first proposed a new approach to analyze tweets from their multidimensional characteristics. The originality of our proposal is to define and manipulate cubes of tweets. We have shown that the analysis of tweets requires the definition of new measures and that a contextualization step is relevant. Then we investigated how pattern mining and more precisely trajectories can be useful for analyzing tweet user behaviors. Future work involves several issues. First we want to extend the proposed approach to take into account opinions or feelings expressed in the tweets. Furthermore, as too many trajectories can be extracted from tweets, we would like to investigate how the minimal description length can be used to report only the most relevant patterns, i.e. top-k patterns.

Example 1 Figure 1

 11 illustrates the location dimension having a hierarchy such that ⊥ location = City ≤ State ≤ Country ≤ ⊤ location . The values of the dimension are dom(Localisation) = {New York, Albany, Los Angeles, Northeastern, California, United States, ...} divided into these categories (levels of granularity) as follows: City = {N ewY ork, Albany, Los Angeles}, State={Northeastern,

Fig. 1 .

 1 Fig. 1. A part of the hierarchy associated to the location dimension.

Fig. 2 .

 2 Fig.2. An example of a schema for dealing with tweets in the health domain.

Fig. 3 .

 3 Fig. 3. Distribution of the use of words pneumonia, hepatitis and leukemia over the period (top) and for January and February (bottom).

Fig. 4 .

 4 Fig. 4. Distribution of the use of the word pneunomia.

Fig. 5 .

 5 An example of swarm and convoy where c1, c2, c3, c4 are clusters.

Fig. 6 .

 6 Fig. 6. An example of the most relevant words of parties: (a) Left Party and (b) Right Party.

Fig. 7 .

 7 Fig. 7. An example of a trajectory that can be extracted from tweets.

http://twitter.com

http://www.alexa.com/topsites

This work is a part of the PoloP Project (Political Opinion Mining) which aims to cope with the analysis of the evolution of French political communities over Twitter during 2012 both in terms of relevant terms, opinions, behaviors.

http://www.nlm.nih.gov/pubs/factsheets/mesh.html

Here document is used to be compliant with the original definition of the T F -IDF measure and refers to a tweet in our context.

http://www.flutrackers.com/forum/showthread.php?t=158136

http://www.flutrackers.com/forum/showthread.php?t=156585

Spatial information can be, for instance, GPS location.


Introduction

The MORECO Action plan defines the implementation and experimentation of the MORECO methodology by the project partners (PP) within seven MORECO pilot sites. In order to get a general overview on the planned pilot activities and to assure their coherence with the MORECO methodology, an ex-ante evaluation has been realized by project partner PACTE, based on an inventory of all the actions and activities planned by the project partners. This report presents the action plans of 7 pilot sites and the results of the ex-ante evaluation of the MORECO action plan and its related pilot activities.

The pilot activities will apply the defined MORECO Methodology, which aims to develop an integratedmultidisciplinary planning approach towards mobility and residential costs (the MORECO approach).

The overall aim of the pilot activities is to obtain:

• better knowledge on mobility and land use issues,

• better awareness and sensitization on strategic links between mobility practises and residential strategies of households and urban planning issues,

• better governance at different scales (from the local to European scale) and between different types of stakeholders within the pilot sites.

In accordance to MORECO methodology, the pilot activities will mainly focus on

• the experimentation and implementation of innovative tools, facilitating awareness rising and the integration of concerns of Mobility and Residential Costs into local/regional governance,

• the stimulation of new local/regional governance dynamics by fostering the sensitization of the local/regional stakeholders and stimulating new cooperation between them.

MORECO Target Groups

The MORECO pilot activities foresee the implementation and experimentation of the MORECO methodology, using innovative tools which have especially been developed for the MORECO project and focusing on three target groups:

1.

Households and related sub-groups, such as residential construction companies, banks and Housing subsidy bodies, including counselling services. Tools: Cost calculator (CC), stress-test, smartphone-app, GIS, seminars, brochures etc.

MORECO Governance-approach

Beyond the mere implementation and experimentation of the MORECO tools, the pilot activities will pay attention to governance issues within the pilot sites.

As already indicated, the tool implementation is supposed to stimulate new local/regional governance dynamics. A minima, the pilot activities will sensitize local/regional stakeholders for MORECO issues.

In best case, new cooperation between the stakeholders and new forms of governance will come out of the tool implementation process.

The project partners are supposed to consider the issue of "governance" in a triple manner:

• Pay attention to the specific local/regional governance context and practices in each PP's pilot sites (existing local/regional governance context of the MORECO tools implementation and use),

• reflect on the way MORECO tools may be best implemented in these specific governance contexts (MORECO tools within the local/regional governance context),

• make sure that MORECO tools constitute an effective contribution to the existing governance and decisional processes (MORECO tools for the local/regional governance).

The pilot activities correspond to three levels/steps:

• Adaptation of the tools to the local context (i.e. in adequacy with local regional statistics) and implementation of the tools (to make the tool work),

• Make sure that the tools are used by the local/regional stakeholders (by collaborating with the local/regional stakeholders),

• Identification of the effective impacts of the MORECO methodology on decision, debate, perception, governance processes (what does it change, why and how?).

www.moreco-project.eu Page 5 of 17 5

MORECO Pilot Sites

The MORECO project includes seven pilot sites within four countries:

Ex-ante Evaluation

The foreseen pilot activities have been evaluated during autumn 2012 by PP PACTE.

Aim of the Ex-ante Evaluation

This evaluation aimed at:

• ensuring close reference of actions to methodology and to tool-frameworks,

• providing a comparable overview and documentation of pilot actions in WP6 for all partners,

• ensuring close reference of actions to Application form AF,

• serving as a basis for further evaluation of the pilot activities (in WP5 ex ante + in WP7) ,

• providing all necessary information to set up a transnational MORECO GOVERNANCE POLICY (in WP7), based on the results of the action plans.

www.moreco-project.eu Page 6 of 17 6

Evaluation Method

The ex-ante evaluation of the pilot sites has been realized in two distinctive steps:

1. Collection of information in order to make an inventory of the pilot activities planned by the project partners within their respective pilot sites. This collection has been based on two successive and complementary questionnaires:

A first questionnaire on the planned pilot activities had to be filled in by the PP's (spring 2012, see appendix 1).

An additional survey had been launched in order to assure that the pilot activities might be monitored and evaluated during and after the implementation process (autumn 2012, see appendix 2). C. Creation of a basis for a comparative analysis of pilot activities within the different pilot sites, regarding the different issues and objectives of the MORECO methodology and aiming at elaborating a transnational MORECO governance approach (WP6 and 7). This comparative analysis will aim at:

• Activity evaluation, based on the quantitative indicators of the Application Form (AF),

• Efficiency evaluation, based on the qualitative indicators (in order to appreciate usefulness of tools),

• Medium and long term impact evaluation of the use of MORECO tools and governance.

The data base on the PP's activities and associated tasks is intended to be completed by the project partners all along the implementation phase of their action plan.

The Collected Data

The pilot activities of all seven pilot sites are described in detail in the common MORECO pilot www.moreco-project.eu Page 7 of 17 7 activities database. The following information have been gathered:

The pilot activities per site and partner, including information on the concerned WP and the period of its implementation.

A synthetic description of each activity (eventually differentiated by steps/actions), including the description of:

• the concerned target group(s),

• the main objective(s),

• the type of tool(s) which will be used.

Quantitative indicators as mentioned in the Application Form (AF). (Most of indicated values are still estimations. They will progressively be replaced by effective values).

Qualitative indicators related to the implementation of the actions. They will be completed during the WP6 phase.

Qualitative indicators conceived to evaluate the effects of MORECO tools and methodologies on transport and urbanization governance processes. These indicators and results will be used in WP7.

Classification of the Pilot Activities

The pilot activities and associated actions (or tasks) are in line with the objectives and methodology of the MORECO project. Nevertheless, specific conditions in the pilot sites (i.e. governance and planning issues) lead the project partners to set up actions which are adapted to the specific regional context.

Approaches then may vary. For example, a particular MORECO tool may be applied to more target groups than initially planned. Moreover, the use of a same tool may have different purposes depending on the pilot site (e.g. awareness rising or fostering new governance).

In order to obtain an overview and to produce a global analysis of the action plans, a classification of the planned actions/tasks, corresponding to the pilot activities, has been established on the basis of three criteria: main target group, main objective, main tool used. In order to take into account particular cases, additional or mixed categories have been created. The table below indicates the established classifications:

MAIN TARGET GROUPS

Households households, househunter households, web-users, associations of inhabitants

Policy makers mayors, local or regional decision makers, transport authorities

Planners and experts planners, transport experts and transport providers, journalists, scientists, NGO

Private actors bankers, building companies, ICT companies ...

All of them

MAIN OBJECTIVES

Sensitization

Analysis of the MORECO Pilot Site Actions

All in all, 120 actions/tasks linked to 30 major pilot activities have been identified within the seven pilot sites. Some pilot activities are concerned by a single action; others integrate up to 8 actions/tasks.

Thus, all indicted actions do not correspond to the same amount of work.

The three graphs below show the distribution of actions according to the three criteria (target groups, objective and used tool). They give some meaningful information about the very nature of the pilot actions/tasks.

Table 1: Characteristics of the pilot activity actions

While households and private actors are The category "Several of them" corresponds generally to specific MORECO promotion actions.

The objectives of the actions differ according the concerned target groups, as shown in the graphs below. Enable to see that this hypothesis can evolve from one objective to the other. Expertise actions are mostly dedicated to the policy makers or/and Planners&experts. They are very often concerned together, but never in association with other target groups, such as the households and private economic actors. This observation leads to think that concerned actions referred to different kinds of expertise.

Once more, the actions dedicated to cooperation mainly concern policy makers and planners & experts together.

Households and private actors appear to be not really concerned by this issue. The link with actual practises of governance in pilot sites will have to be considered.

Transfer of knowhow corresponds to a very few number of actions and is mainly addressing policy makers and planners & experts. Knowledge and know how clearly have to be developed and improved before being transferred to "non-specialist" and "non-decisional" actors.

www.moreco-project.eu Page 13 of 17 13

The dozen of actions oriented towards operational services are mainly dedicated to households and, more generally, to civil society.

In order to analyse the use of the MORECO tools in terms of target groups and objectives, the graphs below compare the use of the three MORECO tools and point out differences and complementarities.

Table 3: Use of the MORECO-tools

Cost calculator applications are obviously planned in order to produce better awareness of mobility costs and its impacts, in order to influence either households or political decisions.

Symmetrically actions centred on GIS applications and spatial/analysis concern the binomial "politician and expert". The tools use thus appears to be closely and inevitably linked with the thematic approaches and expertises.

www.moreco-project.eu Page 14 of 17 14

Actions dedicated to the elaboration of political tools mainly focus on policy makers and planners & experts. It concerns either the very public governance, associating all the categories of actors, or spheres of strategic decision, grouping politicians, public managers and experts.

The last graph points out the PP's use of the MORECO issues. The diversity of the partners in terms of status, competencies and interests is clearly an opportunity for improving the efficiency of tools within governance processes.

Table 6

A real difference and complementarity between more technically and more politically oriented project partners can be observed.GIS is an intermediate approach, mixing technical expertise and more qualitative methodologies for governance.

Conclusion

In summary, the analysis of the characteristics of the 120 actions constituting the action plans confirm close reference to the MORECO methodology and its three complementary objectives:

better knowledge on mobility and land use issues, better awareness and sensitization about strategic links between mobility practises and residential strategies of households and urban planning issues, better governance at different scales and between different types of stakeholders within the pilot sites.

Considering the target groups, we can retrieve the different aimed categories : households, experts, political decision makers, and private stakeholders involved in transport and housing. Some evolutions can be observed regarding the initial orientations:

The first observation does concern the range of stakeholders:

Many actions are dedicated simultaneously to planners and political decision makers. This observation is valid for all the partners and seems to show that the duo «planner & expert/politican» is a common figure.

According to the foreseen activities and regional contexts, some new types of stakeholders, which have not been identified initially, have been added by the PP's, such as other types of experts:

journalists, academic scholars or specialized associations. Also new types of private actors have been identified

This diversification of the range of stakeholders is the result of the action planning process of the PPs and should be seen as an enrichment of the MORECO project.

The second observation is related to the use of the tools within the pilot sites. In fact, the three initially foreseen MORECO-tools (cost calculator, GIS-maps and communication tools) are at the heart of the pilot activities of all PP's. Here again, the range has been enlarged by complementary tools and methods, especially concerning the use of internet and new communication technologies.

The main objectives of the MORECO project are clearly pursued by all pilot activities. The data base allows a differentiated analysis:

• Sensitization/awareness rising (31 % of all 120 actions) is the most frequent type of action and aims all stakeholders equally.

• Expertise actions (24 %) are mostly dedicated to policy makers or/and planners & experts.

• Cooperation in order to foster new forms of governance integrating MORECO concerns is an important issue (20 %).

• Transfer of knowhow corresponds to a few numbers of actions (11 %) and is mainly addressing policy makers and planners & experts.

• Finally, the actions oriented towards operational services (9 %) are mainly dedicated to households and, more generally, to civil society. Moreover, the data basis has been constituted in a manner that allows it to serve as a basis for evaluation during and after the implementation phases (WP6 and WP7). A set of qualitative indicators allowing to assess the experimental process and its outcomes will be filled in by the PP's during and after their pilot activities. It should thus provide the basic information for the setting up of a transnational MORECO GOVERNANCE POLICY (WP7) and the MORECO white book.

  Target Groups ......................................................................................................... 1.2. MORECO Governance-approach............................................................................................. EVALUATION .............................................................................................................. 3.1. Aim of the Ex-ante Evaluation .................................................................................................. 3.2. Evaluation Method .................................................................................................................... 3.3. The Collected Data ................................................................................................................... 3.4. Classification of the Pilot Activities ........................................................................................... 3.5. Analysis of the MORECO Pilot Site Actions ........................................................................... Annex 1: Questionnaire "Pilot Activities" ................................................................................ 5.2. Annex 2: Pilot Activities Additional Questionnaire .................................................................. 5.3. Annex 3: Action Plans of 7 Pilot Sites .................................................................................... 5.4. Annex 4: Overview of Pilot Actions ........................................................................................

2.

  Spatial Planners and mobility actors (= planners, transport providers, consultants, planning authorities) Tools: Informational maps, based on Geographical Information System -GIS 3. Policy-Makers (= politicians, approving or law preparing authorities) Tools: guideline and training/consultant tools, as communication media www.moreco-project.eu Page 4 of 17 4

  2. Creation and analysis of a common data basis on the PP's pilot activities (on basis of the additional survey) with three complementary purposes: A. Creation of an operational tool in order to allow and facilitate the follow-up of the implementation of the pilot activities by the PP's B. Creation of a shared framework allowing to evaluate the pilot activities all along, regarding three types of indicators : • AF quantitative activity indicators, • Qualitative indicators addressing tool implementation and governance issues, • Qualitative outcome indicators, allowing to evaluate and critically assess the pilot activities.

  mostly treated as distinct target groups, policy makers and Planners & experts are very often addressed together within a single action. Politicians and "their experts" thus appear as a kind of "decisional couple". Economic actors only are a sub-target group. The MORECO methodology clearly appears as an upstream and experimental approach. Most emphasis is made on sensitization and aware-ness rising of the various actors, on the improvement of knowledge, the initiating of cooperation, and, less often, on the knowledge transfer and implementation of operational services. www.moreco-project.eu Page 11 of 17 11 In accordance to the previous point, political tools dedicated to sensitization, communication and mediation are at the heart of many of the actions. Technical tools, such as cost calculator and GIS, still need to be developed and disseminated. This is one of MORECO's goals. The category "other tools" corresponds to various other tools such as smartphone application for mobility or focus group discussions.

  which has been elaborated on the basis of the survey reveals close reference of actions to the Application Form AF. It provides a comparable overview and documentation of pilot actions in WP6 for all partners. It shall be used as an open source to ensure transparency. It also shall allow the PP's to adjust actions during the implementation phase of the pilot activities.

Table 1 : Informational structure of the pilot ctivities

 1

www.moreco-project.eu Page 8 of 17 8 www.moreco-project.eu Page 9 of 17 9

Table 2 : Objectives of the pilot activity actions Sensitization

 2

actions are aiming all types of actors. Nevertheless, two target groups are particularly concerned: the households and private actor categories. www.moreco-project.eu Page 12 of 17 12

Table 7 : Objectives and target groups per pilot site

 7

	Nevertheless it appears
	that the different tools
	can be used for very
	different purposes (left
	column). MORECO tools
	are clearly at the service
	of the various registers
	and steps of governance
	processes.
	This diversity of
	functions can logically be
	observed regarding the
	concerned target groups.
	Some partners cover the
	whole "spectrum" of
	actors, others appear to
	be more concentrated on
	particular target groups
	(right column).

www.moreco-project.eu Page 16 of 17 16


Jean-Christophe Filliâtre

Andrei Paskevich

Aaron Stump

The 2nd Verified Software Competition: Experience Report

We report on the second verified software competition. It was organized by the three authors on a 48 hours period on November 8-10, 2011. This paper describes the competition, presents the five problems that were proposed to the participants, and gives an overview of the solutions sent by the 29 teams that entered the competition.

Introduction

Competitions for high-performance logic-solving tools have played a prominent role in Computational Logic in the past decade or so. Well-established examples include CASC (the competition for first-order provers) [START_REF] Sutcliffe | The State of CASC[END_REF], the SAT Competition and SAT Race [START_REF] Schulte | Special Issue on the SAT 2005 Competitions and Evaluations[END_REF], and SMT-COMP (the Satisfiability Modulo Theories Competition) [START_REF] Barrett | 6 years of SMT-COMP[END_REF]. Many other logic-solving fields have also developed competitions in recent years, with new ones coming online yearly. The reason for this interest is that competitions provide a high-profile opportunity for comparative evaluation of tools. Competitions are good for competitors, who have a chance to increase the visibility of their work by participation in the competition. This is true especially, but not at all exclusively, if they do well. Competitions are good for the field, since they attract attention from a broader audience than might otherwise be following research progress in that area. Finally, competitions are good for potential users of logic-solving tools, who have a chance to see which tools are available and which seem to be doing well on various classes of problems.

Competitions have recently been introduced in the field of deductive software verification. The 1st Verified Software Competition was held in 2010, affiliated with the "Verified Software: Theories Tools and Experiments" (VSTTE) conference [START_REF] Klebanov | The 1st Verified Software Competition: Experience report[END_REF]. A similar recent event was the COST IC0701 Verification Competition, held in 2011 [START_REF] Bormer | The COST IC0701 Verification Competition[END_REF]. These two competitions were quite alike in spirit and organization: The objective was to verify behavioral correctness of several algorithms in a limited amount of time (30-90 minutes per problem), and the participants were free to choose the language of specification and implementation. Another contest of verification tools was the SV-COMP 2012 competition [START_REF] Beyer | Competition on Software Verification (SV-COMP)[END_REF], dedicated specifically to fully automated reachability analysis of C programs.

In this paper, we describe the 2nd Verified Software Competition, affiliated with VSTTE 2012. The purposes of this competition were: to help promote approaches and tools, to provide new verification benchmarks, to stimulate further development of verification techniques, and to have fun [START_REF]The 2nd Verified Software Competition[END_REF]. In the end, 29 teams competed to solve 5 problems designed by the organizers over a period of three days in early November, 2011. Their solutions, written using a total of 22 different tools, were then judged by the organizers, over the course of the following month. We chose not to make a total ranking list public, but instead identified 6 teams earning gold, silver, or bronze medals. The medalists were announced at VSTTE 2012 (Philadelphia, January 28, 2012) and the 2 gold-medalist teams were each given a 15-minute slot at the conference to present their solution.

The rest of this paper is organized as follows. Section 2 gives an overview of the competition. Then Section 3 describes the five problems and, for each, discusses the solutions that we received. Finally, Section 4 lists the winners and draws some lessons from this competition.

Competition Overview

Schedule

We have chosen to hold the competition over a 48 hours period in order to include more challenging problems than it was feasible for an on-site competition. One source of inspiration for us was the annual ICFP programming contest.

The competition was organized during Fall 2011, with the following schedule:

-Sep 30/Oct 7/Nov 1: the competition is announced on various mailing lists; -Nov 8, 15:00 UTC: the competition starts (problems are put on the web); -Nov 10, 15:00 UTC: the competition ends (solutions are sent by email); -Dec 12: winners are notified privately; -Jan 28: medalists are announced at VSTTE 2012 and other participants are sent their score and rank privately.

Technical Organization

The competition website [START_REF]The 2nd Verified Software Competition[END_REF] was hosted as a subpage of the VSTTE 2012 website. A Google group was created for the organizers to make announcements, and for the participants to ask questions prior and during the competition and to make their solutions public after the competition if they wish. An email address was created for the participants to submit their solutions.

Rules

The full description of the competition is available at the competition website [START_REF]The 2nd Verified Software Competition[END_REF]. The main rules were the following:

team work is allowed, but only teams up to 4 members are eligible for the first prize; any software used in the solutions should be freely available for noncommercial use to the public; software must be usable on x86 Linux or Windows; participants can modify their tools during the competition.

Participants

The competition gathered 79 participants, grouped in 29 teams as follows:

-8 teams of size 1, -6 teams of size 2, -4 teams of size 3, -10 teams of size 4, -1 team of size 9.

Participants were from North America, Europe, and Asia, as depicted in Fig. 1. Participants used the following systems, in alphabetic order (the number between parentheses indicates how many teams used that system): ACL2 (1), Agda (3), ATS (1), B (2), BLAST (1), CBMC (1), Coq [START_REF] Adriano | A new algorithm for minimum cost binary trees[END_REF], Dafny [START_REF] Dahlweid | VCC: Contract-based modular verification of concurrent C[END_REF], Escher (1), Guru (1), HIP (1), Holfoot (1), Isabelle (2), KeY (1), KIV (1), PAT (1), PML (1), PVS (3), Socos (1), VCC (2), VeriFast (1), Ynot (1). 9 teams used at least two different systems.

Evaluation Process

We approached the rather daunting task of hand-evaluating the solutions as follows. Our goal was to determine the medalists first, and then go back and provide additional feedback as time permitted to all competitors. So we first triaged the solutions by determining their maximum possible score; that is, maximal points each could possibly earn, based on the parts of the problems it claimed to have solved. For example, only 5 teams claimed to have solved all parts of all the problems. We then heuristically started with the top 8 teams, and each of the organizers closely evaluated their solutions.

The evaluation process was as follows:

1. Read the submission to check that the formal specification conforms to the problem statement. 2. Check the formal proof:

(a) Run the tool on the input files and check the output (proof found or correctly replayed). (b) Manually introduce errors in code or specification (for example, extend loop bounds or weaken a precondition) and rerun the tool to check that input files are not accepted anymore.

As a result of this evaluation, each task was attributed a fraction of its total "worth". We subtracted points based on our assessment that the solution for some part of a problem fell short in some way. Despite some points being taken away, we were already able to determine our medalists from the first-chosen 8 teams, since no other team had a maximum possible score that could possibly beat the actual score we assessed for the bronze medalists. After we determined the winners, we then divided the remaining solutions among ourselves, to provide written feedback to each team on its solution. Each team was emailed the comments for its solution, once all had been inspected by at least one organizer.

Problems and Submissions

Prior to the competition, we prepared 8 problems of various difficulties. Each problem was solved using Why3 [START_REF] Bobot | The Why3 platform[END_REF] and was independently tested by our colleagues Claude Marché and Duckki Oe. Finally, we picked up the following 5 problems:

1. Two-Way Sort (50 points) -sort an array of Boolean values 2. Combinators (100 points) -call-by-value reduction of SK-terms 3. Ring Buffer (150 points) -queue data structure in a circular array 4. Tree Reconstruction (150 points) -build a tree from a list of leaf depths 5. Breadth-First Search (150 points) -shortest path in a directed graph We selected the problems and assigned the scores according to the time we ourselves and the testers spent devising solutions to them. The three problems we did not include were: Booth's multiplication algorithm, permutation inverse in place, and counting sort. The former two problems seemed too difficult for a 48-hour competition and the third one was too similar to problems 1 and 3. two_way_sort ( a : array of boolean ) := i <-0; j <-length ( a ) -1; while i <= j do if not a [ i ] then i <-i +1 elseif a [ j ] then j <-j -1 else swap (a , i , j ) ; i <-i +1; j <-j -1 endif endwhile Fig. 3. Problem 1: Two-Way Sort.

In hindsight, we could have chosen more difficult problems, as the top-ranked participants completed all tasks without much trouble.

Each problem consists of a program to be verified, according to a set of verification tasks ranging from mere safety and termination to full behavioral correctness. A pseudo-code with an imperative flavor is used to describe the programs, but the participants were free to turn them into the language of their choice, including purely applicative languages.

Figure 2 gives an overview of the solutions we received, on a per-problem basis. The remainder of this section describes the problems in detail and provides some feedback on the solutions proposed by the participants.

Problem 1: Two-Way Sort

The first problem we considered to be easy, and was supposed to be a warm-up exercise for the participants. A pseudo-code to sort an array of Boolean values is given (see Fig. 3). It simply scans the array from left to right with index i and from right to left with index j, swapping values a[i] and a[j] when necessary. The verification task are the following:

1. Safety: Verify that every array access is made within bounds. 2. Termination: Prove that function two_way_sort always terminates. 3. Behavior: Verify that after execution of function two_way_sort, the following properties hold: (a) array a is sorted in increasing order; (b) array a is a permutation of its initial contents. Fig. 2 confirms that Problem 1 was the easiest one. Yet we were surprised to see a considerable number of quite laborious solutions, in particular regarding the definition of a permutation (task 3b). We were expecting the participants to pick up such a definition from a standard library, but almost no one did so. Various definitions for the permutation property were used: explicit lists of transpositions together with an interpretation function, bijective mapping of indices, equality of the multisets of elements, etc.

terms t ::= S | K | (t t) CBV contexts C ::= | (C t) | (v C) values v ::= K | S | (K v) | (S v) | ((S v) v) [t] = t (C t1)[t] = (C[t] t1) (v C)[t] = (v C[t]) C[((K v1) v2)] → C[v1] C[(((S v1) v2) v3)] → C[((v1 v3) (v2 v3))]
One team used the BLAST model checker to perform tasks 1 (safety) and 2 (termination). Some participants spotted that the loop test i <= j can be safely replaced by i < j (and proved it).

Problem 2: Combinators

Problem 2 is slightly different from the other ones. Instead of providing pseudocode to be verified, this problem simply gives a specification and requires the participants to first implement a function, and then to perform some verification tasks. Namely, the problem defines call-by-value reduction of SK-terms (see Fig. 4) and then proposes one implementation task:

1. Implement a unary function reduction which, when given a combinator term t as input, returns a term t such that t → * t and t →, or loops if there is no such term. and three verification tasks:

1. Prove that if reduction(t) returns t , then t → * t and t →.

2. Prove that reduction terminates on any term that does not contain S.

3. Consider the meta-language function ks defined by

ks 0 = K, ks (n + 1) = ((ks n) K).
Prove that reduction applied to the term (ks n) returns K when n is even, and (K K) when n is odd.

One subtlety regarding this problem is that function reduction may not terminate. Hence implementing it is already challenging in some systems; that is why implementation is a task in itself. Another consequence is that verification task 1 is a partial correctness result. Tasks 2 and 3 were slightly easier, in particular because it is possible to exhibit a termination argument for reduction when applied on S-free terms.

A common error in submissions was forgetting to require a value on the left hand-side of a context (v C). Indeed, in absence of a dependent type to impose this side condition in the definition of the data type for contexts, one has to resort to an extra well-formedness predicate and it was sometimes accidentally omitted from specifications. Regarding verification task 1, another error was to prove that the returned term was a value without proving that values are irreducible.

One team provided an improved result for verification task 2, showing that any S-free term necessarily reduces to a term of the shape K (K (K . . . )). Another team proved as a bonus that reduction of SII(SII) diverges (with I being defined as SKK).

Problem 3: Ring Buffer

With problem 3, we are back with traditional imperative programming using arrays. A bounded queue data structure is implemented using a circular array (see Fig. 5) with operations to create a new queue, to clear it, to get or remove the first element, and to add a new element. The verification tasks are the following:

1. Safety. Verify that every array access is made within bounds. The challenge of this problem is to come up with a nice specification of the first-in first-out semantics of the queue (task 2). Most participants defined the model of the queue as a list, either as a ghost field in the ring_buffer record itself, or as a separate logical function. Some participants, however, opted for algebraic specifications (i.e. showing head(push(b, x)) = x and so on). Note that verification task 3 does not require a modular proof using the model defined for the purpose of verification task 2. Thus a mere calculation is accepted as a valid answer for task 3; that solution was used by several participants. This problem appeared to be the second easiest one, judging by the number of perfect solutions, see Fig. 2. Though it was not explicitly required, some solutions are generic w.r.t. the type of elements (and then instantiated on type int for task 3). Some participants replaced the mod operation by a test and a subtraction, since b.first + b.len and b.first + 1 cannot be greater than 2b.size -1. This was accepted.

Problem 4: Tree Reconstruction

There is a little story behind the fourth problem. It is the last step in Garsia-Wachs algorithm for minimum cost binary trees [START_REF] Adriano | A new algorithm for minimum cost binary trees[END_REF]. It can be stated as follows: given a list l of integers, you have to reconstruct a binary tree, if it exists, such that its leaf depths, when traversed in order, form exactly l. For instance, from the list 1, 3, 3, 2 one reconstructs the binary tree The last problem is a traditional breadth-first search algorithm to find out the shortest path in a directed graph, given a source and a target vertex. The graph is introduced as two abstract data types, respectively for vertices and finite sets of vertices, and a function succ to return the successors of a given vertex:

type vertex type vertex_set succ ( v : vertex ) : vertex_set
The code for the breadth-first search is given in Fig. 7. Then the verification tasks are the following:

1. Soundness. Verify that whenever function bfs returns an integer n this is indeed the length of the shortest path from source to dest. A partial score is attributed if it is only proved that there exists a path of length n from source to dest. 2. Completeness. Verify that whenever function bfs reports failure there is no path from source to dest.

One difficulty is that the graph is not necessarily finite, thus the code may diverge when there is no path from source to dest. This was done purposely, to introduce another partial correctness task (as in problem 2). However, some participants asked during the competition if they may assume the graph to be finite, in particular to assume vertices to be the integers 0, 1, . . . , n -1, and sometimes even to use an explicit adjacency matrix for the graph. We answered positively to that request. We also received solutions for this problem that did not rely on this assumption.

Another request was the possibility to rewrite the inner loop of the code (which updates sets V and N) using set operations (union, difference, etc.). We also agreed. On second thought, the problem would have been nicer if stated this way, that is with the inner loop replaced by the following two assignments:

N <-union (N , diff ( succ ( v ) , V ) ) ; V <-union (V , succ ( v ) ) ;
This fifth problem has the lowest number of perfect solutions: 9 out of 29 submissions. A group of 6 excellent submissions with tied scores emerged from our evaluation. Thus we opted for 6 medalists (2 bronze, 2 silver, 2 gold) to avoid discriminating between solutions that were too close. The medalists are:

Competition Outcome

Gold medal (600 points):

-Jared Davis, Matt Kaufmann, J Strother Moore, and Sol Swords with ACL2 [START_REF] Kaufmann | ACL2 Version 4.3[END_REF][START_REF] Kaufmann | Computer-Aided Reasoning: An Approach[END_REF]. -Gidon Ernst, Gerhard Schellhorn, Kurt Stenzel, and Bogdan Tofan with KIV [START_REF] Reif | Proving system correctness with KIV 3.0[END_REF]. Silver medal (595 points):

-K. Rustan M. Leino and Peter Müller with Dafny [START_REF] Rustan | Dafny: An Automatic Program Verifier for Functional Correctness[END_REF].

-Sam Owre and Natarajan Shankar with PVS [START_REF]The PVS system[END_REF][START_REF] Owre | PVS Language Reference[END_REF]. Bronze medal (590 points):

-Ernie Cohen and Micha l Moskal with VCC [START_REF] Dahlweid | VCC: Contract-based modular verification of concurrent C[END_REF].

-Jason Koenig and Nadia Polikarpova with Dafny [START_REF] Rustan | Dafny: An Automatic Program Verifier for Functional Correctness[END_REF].

Lessons Learned

Evaluation. Probably, the most important conclusion we arrived at during the competition was that evaluation of submitted solutions is a non-trivial and, to some extent, subjective process. This is what sets deductive verification competitions apart from programming contests (where the success can be judged using series of tests) and prover competitions (where a proof trace can be mechanically verified by a trusted certification procedure). In our case, a solution consists of a formal specification of the problem and a program to solve it, both written in some system-specific language. It is the responsibility of a verification system to check that the program satisfies the requirements posed by the specification, and, to a first approximation, we can trust the verification software to do its job correctly. Even then a user (and a judge is nothing but an exigent user) must have a good knowledge of the system in question and be aware of the hidden assumptions and turned-off-by-default checks -an issue we stumbled on a couple of times during evaluation. What is more difficult, error-prone, and time-consuming is checking that a submitted specification corresponds to our intuitive understanding of the problem and its informal description written by humans and for humans. We found no other way to do it than to carefully read the submissions, separating specification from proofs and program code, and evaluating its conformance to our requirements. In this respect, it is not unlike peer-reviewing of scientific publications. Additionally, every system proposes its own language: sometimes quite verbose, sometimes employing a rather exotic syntax, sometimes with specification parts thinly spread among hundreds of lines of auxiliary information. Here we must commend the solutions written for PVS and Dafny for being among the easiest ones to read.

Advice to future organizers. To help improve the evaluation process, we would recommend to organizers of future competitions to gather a kind of "program committee" to which reviewing of submissions could be delegated. Such a committee would benefit from having experts in as many different tools as possible, to help provide more expert reviews of submitted solutions. While a common specification language is out of the question (as the main interest of the contest lies in comparing diverse approaches to formalization), we can strive for more rigid problem descriptions, down to first-order formulations of desired properties. We, as a community, should also push verification system developers towards wellstructured and easily readable languages, with a good separation of specification from implementation and proof. Indeed, future organizers might consider requiring the specification of each part of a problem to be clearly indicated, either in comments or even better, by placing the specifications in separate files.

Advice to future competitors. The single biggest issue we had in evaluating solutions was just understanding the specifications of the theorems. One has little choice but to trust the verification tool which claims the solution is correct, but we cannot escape the need to judge whether that solution solves the stated problem or falls short in some way (for example, by adding an assumption that was not explicitly allowed, or by incorrectly formulating some property). So anything a competitor can do to make it as clear and comprehensible as possible what the specification is will help making judging easier and more likely less error-prone. Sometimes even determining which parts of a set of proof scripts or files constitute the specification was challenging. And of course, any special notation or syntax for a tool should be carefully (but briefly) introduced in the README for the submission (and/or possibly inline in the submission itself, where it is first used). Finally, a few submissions we evaluated were not based on plain text files, but rather required a specialized viewer even to look at the solutions. This posed problems for us, particularly when the viewer was only available on one platform (e.g., Windows). We recommend that all tools based on specialized viewers have some kind of export feature to produce plain text, at least for the statements of theorems proved.

Problem difficulty. When several independent problems are proposed, it is not easy to estimate their relative difficulty in an unbiased manner. The solution that you devise for your problem is not necessarily the best or the simplest one: we were pleasantly surprised to see some participants find more elegant and concise formulations of our algorithms and specifications than those we came up with ourselves (cf. the inner loop in problem 5). Also, what is hard to do in your system of choice might be easy with some other tool. It is always better to draw in several independent and competent testers, preferably using different systems, before the competition.

Verification tasks. An interesting class of verification problems is related to termination issues. Even for systems that admit diverging programs it is not always possible to specify and prove non-termination on a certain input (and we did not include any such task in our problems). Somewhat paradoxically, the systems that are based on logics with total functions (such as Coq) are better suited for this task, as some indirection is required anyway to describe a diverging computation (for example, a supplementary "fuel" parameter).

Conclusion

Organizing this competition was a lot of fun -and it seems it was so for the participants as well, which was one of our goals. But it was also a lot of work for us to evaluate the solutions. Obviously this format cannot be kept for future competitions, especially if we anticipate on an even greater number of participants. Alternatives include on-site competitions in limited time (to limit the number of participants), peer-reviewing of the solutions (to limit the workload), and servers with pre-installed verification software (to avoid the installation burden).

Fig. 1 .

 1 Fig. 1. Geographical distribution of the participants.

Fig. 4 .

 4 Fig. 4. Problem 2: Combinators.

2 .

 2 Behavior. Verify the correctness of the implementation w.r.t. the first-in first-out semantics of a queue. 3. Harness. The following test harness should be verified. test ( x : int , y : int , z : int ) := b <-create (2) ; push (b , x ) ; push (b , y ) ; h <-pop ( b ) ; assert h = x ; push (b , z ) ; h <-pop ( b ) ; assert h = y ; h <-pop ( b ) ; assert h = z ;

Fig. 5 .

 5 Fig. 5. Problem 3: Ring Buffer.

Fig. 7 .

 7 Fig. 7. Problem 5: Breadth-First Search.

4. 1

 1 And the Winners Are...

Acknowledgments. A large number of people contributed to the success of this competition. We would like to thank: our beta-testers Claude Marché and Duckki Oe; VSTTE 2012 chairs Ernie Cohen, Rajeev Joshi, Peter Müller, and Andreas Podelski; VSTTE 2012 publicity chair Gudmund Grov; LRI's technical staff.

type tree Leaf () : tree Node ( l : tree , r : tree ) : tree type list is_empty ( s : list ) : boolean head ( s : list ) : int pop ( s : list ) but there is no tree corresponding to the list 1, 3, 2, 2. A recursive function to perform this reconstruction is given (see Fig. 6; R.E. Tarjan is credited for this code [7, p. 638]). Then the verification tasks are the following:

1. Soundness. Verify that whenever function build successfully returns a tree, the depths of its leaves are exactly those passed in the argument list. 2. Completeness. Verify that whenever function build reports failure, there is no tree that corresponds to the argument list. 3. Termination. Prove that function build always terminates. 4. Harness. The following test harness should be verified:

-Verify that build applied to the list 1, 3, 3, 2 returns the tree Node(Leaf, Node(Node(Leaf, Leaf), Leaf)). -Verify that build applied to the list 1, 3, 2, 2 reports failure.

One difficulty here is to prove completeness (task 2). Another difficulty is to prove termination (task 3), as it is not obvious to figure out a variant for function build_rec. On the contrary, verification task 4 (harness) turns out to be easy as soon as one can execute the code of build, as in harness for problem 3.

A delightful bonus from the ACL2 team is worth pointing out: To demonstrate that function build is reasonably efficient, they applied it to the LISP code of function build_rec itself, as each S-expression can be seen as a binary tree.


Olivier Stasse
email: olivier.stasse@aist.go.jp

Ee Neo

Florent Sian
email: flo-rent@laas.fr

Takeshi Lamiraux

Abderrahmane Sakaguchi
email: sakaguchi.t@aist.go.jp

Yokoi Kheddar
email: kheddar@ieee.org

Kazuhito

Kazuhito Kheddar
email: kazuhito.yokoi@aist.go.jp

Yokoi

Architectures and models for humanoid robots in collaborative working environments

Keywords: humanoid robotic, collaborative working environment, pattern architecture

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

I. INTRODUCTION

Humanoid robots due to their high redundancy, high number of sensors have a high versatility. For this reason they are considered as a generic robotic platform which can be used in different set-ups. They are already a number of real-life applications demonstrating this versatility: HRP-1S driving a back-hoe [START_REF] Yokoi | A tele-operated humanoid robot drives a backhoe in the open air[END_REF], HRP-1S performing plant maintenance using a network of RFIDs [START_REF] Kawauchi | A plant maintenance humanoid robot system[END_REF], HRP-2 bringing semi-autonomously a can from a fridge or grasping various objects [START_REF] Neo | Operating humanoid robots in human environments[END_REF], Asimo acting as a receptionist [START_REF] Sakagami | The intelligent asimo: system overview and integration[END_REF]. On the other hand, nowadays efficient collaborative working environments are a necessity for companies to stay competitive. For some, such as Walmart the know-how related to such applications is the main source of advantages over competitors. Integrating robots into such kind of collaborative environment is therefore a necessity and might also be a way to overcome some of the current limitations.

This paper intends to propose a survey in current humanoid architectures to highlight the current limitations in human/robot collaborative work, and their integration in nowadays Collaborative Working Environments (CWE).

II. FUNCTIONAL ARCHITECTURE

1) The scenario: A user through the Internet asks to a company for a product, or a service to be realized. The client's request is handled by the intra-network. The plan to provide the product or the service is then handled by the appropriate scheduler and send to the production unit. In this case, the production unit is the robot and the operator working together to realize the client request. To achieve this, the robot autonomously perceive the environment, localize itself, recognizes and tracks visually the objects needed for the task.

The state of the human collaborator is estimated in order to synchronize with him the realization of the task. This might be achieved through various ways and considering several modalities: local force control, human posture identification through vision, sensor on the human and external sensors (motion capture, network of cameras). This is can be used for a re-synchronization on the mission planning. Once the product or the service is realized, the information is send back to the IT application. The accounting service can then generate the bill and send it to the customer. The same process can be realized when the customer is calling the support service for problems, or modification of his order.

2) The overall architecture: Figure 1 describes an overall functional architecture to achieve collaborative work with a humanoid robot. In order to achieve such scenario, usually such structure possesses 5 functional parts: 1) an autonomous one, 2) an optional remote brain, 3) an intelligence shared with other robots so called ambient intelligence, 4) an interaction with the other services of the information system, 5) the Internet.

Such pattern of architecture depicted in figure 1 can be found at different stages with humanoid robots such as Asimo [START_REF] Sakagami | The intelligent asimo: system overview and integration[END_REF] [START_REF] Ceravola | Researching and developing a real-time infrastructure for intelligent systems -evolution of an integrated approach[END_REF], and HRP-2 [3][6].

III. AUTONOMOUS HUMANOID ROBOT

This section describes the proposed architecture to achieve minimal autonomy for a humanoid realizing collaborative work with a human.

A. Previous work

There already exists a number of integrative architectures for humanoid robots with impressive capabilities. Namely, Inoue, Inaba, Kagami, Kuffner and Nishiwaki [START_REF] Nishiwaki | The experimental humanoid robot h7: a research platform for autonomous behavior[END_REF] developed such a system on top of the humanoid robot H7. Their system was already able to detect an object using a stereoscopic system [START_REF] Kagami | Vision-based 2.5d terrain modeling for humanoid locomotion[END_REF], plan the trajectory autonomously and walk. The robot was able to knee to grasp the object and walk on stairs. The work of Okada deserves very much interest especially for a complete integration [START_REF] Okada | Integrated system software for hrp-2 humanoid[END_REF] which would aim at having HRP-2 acting as a kitchen maid [START_REF] Okada | Vision based behavior verification system of humanoid robot for daily environment tasks[END_REF]. His work is also one of the first to consider the problem of planning manipulation tasks [START_REF] Gravot | Cooking for humanoid robot, a task that needs symbolic and geometric reasonings[END_REF] in the context of such complex real applications. For their primitive task executions they do use a task formulation approach. Recent work by Bolder et al. [START_REF] Bolder | Visually guided whole body interaction[END_REF] demonstrates ASIMO walking and generating reactively full body motion towards objects tracked visually.

B. Perception 1) Range finder:

Although a large number of sensors exist in the market, size constraint limit the range of sensors which can be used inside a humanoid robot. For this reason, only small-size laser can be found inside humanoids robot [START_REF] Stachniss | How to learn accurate grid maps with a humanoid[END_REF]. One of the current limitation is the fact that this sensor is limited to one scan line. They were also some work realized with the 3D time-of-flight sensor [START_REF] Knoop | Sensor fusion for 3d human body tracking with an articulated 3d body model[END_REF]. The limitation with such sensor is the noise and the sensitivity to illumination conditions.

2) Vision: In general vision stays by large a contender to provide information on the surrounding environment [START_REF] Sumi | 3d object recognition in cluttered environments by segment-based stereo vision[END_REF] [15] [START_REF] Goerick | Towards incremental hierarchical behavior generation for humanoids[END_REF]. Visual servoing has also made possible to design robust control law for motion generation [START_REF] Mansard | Visually-guided grasping while walking on a humanoid robot[END_REF]. Nowadays chipsets and stereo cameras [START_REF] Kagami | Vision-based 2.5d terrain modeling for humanoid locomotion[END_REF] can be easily integrated inside the head of humanoid robot. The known limitations of classical vision algorithms regarding the robustness under the illumination changes, and condition are slowly overcome by an increasing integration of different approaches. Therefore it is now possible to find real-time SLAM system [START_REF] Davison | Monoslam: Real-time single camera slam (submitted)[END_REF]. working inside humanoid robots. Tracking or recognition of objects can be realized. The main drawback is usually the CPU consumption related to advanced robotic vision system. Even though it is often argued that the CPU speed is increasing at a very rapid pace, it is usually used to address new vision problems which take advantages of this computational power. This is especially true with the very active classification community building huge bag of features databases. However it is clear that those databases are still quite limited to the current capability of a human agent in a collaborative working environment. One way of overcome this limitation is to use cluster of PCs [START_REF] Ude | Distributed visual attention on a humanoid robot[END_REF] [START_REF] Fitzpatrick | Towards long-lived robot genes[END_REF] usually called the remote brain as depicted at bottom right of figure 1. The very active community of human pose detection also used cameras as input, mostly because of the current cost of such sensor. For all these reasons, it is very likely that vision will still be an important source of information for humanoid robot system in the future.

3) Sound: Another important source of information and exchange with humans is speech recognition and synthesis [START_REF] Neo | A humanoid robot behavioral operation system using natural language -the construction of a lexicon of behaviors and its triggering system based on body information[END_REF]. With stereo, or an array of, microphones, it is possible to localize in 3D a sound and therefore to drive the attention of the humanoid robot. It can also be used to control the robot over the realization of a complex mission [START_REF] Dominey | Real-time cooperative behavior acquisition by a humanoid apprentice[END_REF][21] and even to teach the robot a sequence of actions [START_REF] Dominey | Real-time cooperative behavior acquisition by a humanoid apprentice[END_REF]. The embed-ability can be overcome by the use of FPGA board. A weak point is sometimes the sensitivity to noise which can be overwhelming in noisy or crowded environments. In such case, multi-modal techniques including vision for instance help to solve the problem [START_REF] Kemp | Handbook Of Robotics[END_REF].

4) Tactile and force sensors: Tactile sensors are very important for humanoid robots because they are the ones allowing a direct interaction with objects and humans. There are several examples of humanoids using tactile sensors specifically for the hands [START_REF] Mizuuchi | Development of musculoskeletal humanoid kotaro[END_REF] [START_REF] Kaneko | Development of multifingered hand for life-size humanoid robots[END_REF]. Such sensors are very important to handle properly objects, and to interact safely with humans. Two teams demonstrated humanoids with skin used for whole body motion [START_REF] Nagakubo | A deformable and deformation sensitive tactile distribution sensor[END_REF], [START_REF] Minato | Cb 2 : A child robot with biomimetic body for cognitive developmental robotics[END_REF]. They were used to realized lifting of heavy objects [START_REF] Ohmura | Humanoid robot which can lift a 30kg box by whole body contact and tactile feedback[END_REF], and to perform direct interaction with humans [START_REF] Minato | Cb 2 : A child robot with biomimetic body for cognitive developmental robotics[END_REF]. Indeed the use of skin might be one way to implement human-safe behaviors, as the robot will be able to sense any physical interaction with its own body. The main problem of the information of this sensor is the computational power involved by the number of sensors scattered on the body. Finally the current cost of flexible skin might slow down the wide acceptance of such sensor.

Force sensors are also very important for humanoid robots, as a large number of them following Honda's P-1 rely on force sensor to enforce the robot's stability. The main limitation of such sensors is their cost as they need to support the impact, and the weight of the robot when landing on the floor. Force sensor are also used to interact passively with humans. They have been used recently by a humanoid HRP-2 to push a table with a 50 kg load [START_REF] Stilman | Learning object models for whole body manipulation[END_REF].

In the previous example although force is taking into account, the robot is controlled in velocity. A control scheme taking into account force, and generating torque, has been investigated by Sentis and Khatib [START_REF] Sentis | Synthesis of whole-body behaviors through hierarchical control of behavioral primitives[END_REF], Ott at DLR [START_REF] Albu-Schäffer | A unified passivitybased control framework for position, torque and impedance control of flexible joint robots[END_REF]. with very promising theoretical and practical results. However current walking humanoid technology is in general based on DC motors and harmonic drive for embedability issues. The uses of such control frameworks involves a precise identification of the dynamical parameters. Such identification is in general very difficult and can be invalid due to the stress imposed to the motors while the robot is walking.

C. Action

1) Control: Proposed initially by Nakamura to control highly redundant robot, the stack of tasks has recently regained some interest for motion generation targeted to humanoid robot. The main interest of this formulation is that it allows to give priority to independent controllers in an elegant fashion while avoiding a complete failure of the system if some tasks are incompatible [START_REF] Mansard | Task sequencing for sensor-based control[END_REF][30][33] [START_REF] Dariush | Whole body humanoid control from human descriptors[END_REF].

Its force based counterpart proposed by Khatib used with current humanoid platform such as Asimo implies to be able to convert a force to a position based controller [START_REF] Khatib | Torque-position transformer for task control of position controller robots[END_REF]. This framework has however some defects: it cannot handle per se unilateral constraint. Such constraints are usually handled through a potential function (see [START_REF] Khatib | Real-time obstacle avoidance for manipulators and mobile robots[END_REF] for joint limits, and [START_REF] Stasse | Real-time (self)-collision avoidance task on a hrp-2 humanoid robot[END_REF] for self-collision avoidance). The problem related to the potential function is that any motion making the robot going away from the limit is projected in the nullspace (orthogonal) space, and therefore is not applied. Going away from such limit is therefore usually quite slow. The other problem is the possible discontinuity of the speed when the number of constraints activated vary. The change of dimension might create discontinuities which are not welcome while interacting with humans.

2) Stability: Stability is very important for humanoid robot not to fall down. In order to have humanoid robots working and interacting with humans it is clear they have to comply with this constraint. It is true while transporting an object with a humanoid robot. The main difficulty consist in finding a criterion for which it is possible to have a realtime trajectory generation. In the past few years numerous algorithms based on the popular ZMP criteria have been proposed to solve this problem in real-time [START_REF] Kajita | Biped walking pattern generation by using preview control of zero-moment point[END_REF][39] [START_REF] Terada | Real-pattern generator allowing height modification[END_REF]. However the ZMP assumes that both feet are on a horizontal plane. Recently a new criteria has been proposed allowing to go over this limitation by taking into account multiple contacts [41][42]. This might help notably to interact more closely with the environment. But there is no algorithm yet to generate motion in real-time considering this new criteria [START_REF] Hirukawa | A pattern generator of humanoid robots walking on a rough terrain[END_REF]. One of the challenge regarding humanoid robotics is the recovery from a fall. Kanehiro and al. [START_REF] Kanehiro | The first humanoid robot that has the same size as a human and that can lie down and get up[END_REF], [START_REF] Hirukawa | The human-size humanoid robot that can walk, lie down and get up[END_REF], [START_REF] Kanehiro | Getting up motion planning using mahalanobis distance[END_REF] shown that it was possible to have a full size humanoid robot to get up from the ground while lying down. However the main challenge is still the limitation of the impact when falling. If Fujiwara et al. [START_REF] Fujiwara | Ukemi: falling motion control to minimize damage to biped humanoid robot[END_REF] proposed some controllers in this direction, the technical solution is not totally satisfactory regarding the overall stress put on the mechanic. Either new mechanical design with compliant material should be consider, either the robot should react against disturbances. Some algorithms have been proposed to generate foot-steps maintaining the overall stability of the robot [START_REF] Nishiwaki | Short cycle pattern generation for online walking control system of humanoids[END_REF] under perturbation. New control scheme against strong perturbations have been investigated by Wieber [START_REF] Wieber | Trajectory free linear model predictive control for stable walking in the presence of strong perturbations[END_REF] recently.

3) Natural interaction with user: A constraint important in the case of interaction with humans, is the necessity for the robot to perform motion which are not frightening. This aspect implies for instance to plan motion taking into account psychological constraints. This approach has been investigated in the frame of the Cogniron European Project [START_REF]Cogniron: The cognitive robot companion[END_REF]. When communicating with a human it is also important for a robot to reinforce multimodal communication by proper body motion [START_REF] Kanda | Development and evaluation of interactive humanoid robots[END_REF].

D. Decision

In this paragraph decision is seen widely as to solve the problem of finding the sequence of tasks to perform in order to realize a mission. In the context of collaborative working environment, a robot can benefit from information available on the IT system. For instance, instead of trying to solve by itself the overall realization of the mission, a robot can follow the processes described in quality document, and synchronize itself with a human performing such work. The problem then amounts to the analysis of such document and its translation into an appropriate sequence of tasks for the robots. Then the robot has to plan the motion to realize.

1) Decision planning: Decision planning usually considers a set of skills which are acquired functionalities such as a controller with a specific set of parameters, the capability to plan a trajectory,... On the other hand a task is specified as a set of subgoals which are reached through primitive actions. A recurrent problem with such approach is the creation of the primitive actions from the available controllers on the robot. They are usually created in an ad hoc manner depending on the targeted application or the controllers. Although they are several works in trying to build those primitives automatically [START_REF] Jenkins | Performance-derived behavior vocabularies: Data-driven acqusition of skills from motion[END_REF], the question of scalability to real-life applications is still open. Of particular interest in our situation is the work of Drumwright [START_REF] Drumwright | Toward a vocabulary of primitive task programs for humanoid robots[END_REF] with ASIMO which consider work measurement systems. Such systems are methods developed to measure the time spend into primitive occupational tasks. Drumwright's method then maps such primitives into a system called the Task Matrix. More recently, Neo et al. [START_REF] Neo | A humanoid robot behavioral operation system using natural language -the construction of a lexicon of behaviors and its triggering system based on body information[END_REF] proposed a behavioral system grounded in natural language instructions, allowing on-line whole body motion generation. Gravot et al. [START_REF] Gravot | Cooking for humanoid robot, a task that needs symbolic and geometric reasonings[END_REF] proposed to mix symbolic and geometric reasoning for a HRP-2 humanoid to act as a cook. A high level planner decides of the task to realize from a recipe database and a hierarchical task description. The position failing for the environment modelling triggers a partial re-plan of the solution. This work proposes a connection with the problem of motion planning.

2) Motion planning: Motion planning is quite challenging for humanoid robot for several reasons: the high degree of freedom for humanoid robots usually implies a possible combinatorial explosion of the configuration space. Dynamic stability such as ZMP or CoP, implies to expand even more the robot state space, and the constraint to be taken into account. So far, successful approaches decouple the problem of obstacles avoidance in the environment and stability. Kuffner et al [START_REF] Kuffner | Footstep planning among obstacles for biped robots[END_REF] proposed to generate a collision free trajectory and to adjust the time parameter to make the trajectory dynamically stable. Bourgeot et al [START_REF] Bourgeot | Path-planning and tracking in a 3D complex environment for an anthropomorphic biped robot[END_REF] and later Chesnutt et al [START_REF] Chesnutt | Footstep planning for the honda asimo humanoid[END_REF] proposed to discretize the space of feasible steps of the robot and check against collision with a set of feasible steps. Yoshida et al. [START_REF] Yoshida | Smooth collision avoidance: Practical issues in dynamic humanoid motion[END_REF] proposed an iterative method. Each steps starts by planning or reshaping the humanoid upper body motion, it then uses a preview control based pattern generator to obtain a dynamically stable motion. If there is no collision with a sufficient margin the trajectory is accepted, otherwise it iterates. Although not realtime, the latter method was used to plan a trajectory with the robot handling a 2m bar in a complex environment. It was recently extended to plan pivoting of large objects [START_REF] Yoshida | Whole-body motion planning for pivoting based manipulation by humanoids[END_REF].

IV. AMBIENT INTELLIGENCE

The aim of ambient intelligence is to provide an environment able to sense people and provide services accordingly [START_REF] Remagnino | Ambient intelligence: A new multidisciplanary paradigm[END_REF]. A robot entering such environment establishes a two way relationship by providing and accessing services and information. The previously cited work [21][22] is a first step into interacting with a humanoid robot in a natural manner. A less explored research area is the interaction of humanoid robots with ambient intelligence. To the authors knowledge the first tentative along this line is the work of Sakagushi et al. [START_REF] Sakaguchi | Intelligent-ambience robot cooperation -closing door with humanoid robot[END_REF]. It shows, from an architectural viewpoint, that for some specific behaviors such as closing the door of a fridge, it is possible to use indifferently a mobile base or a humanoid robot. From this result, the next phase is to understand how a robot is functionally equivalent to another from the ambient intelligence system viewpoint. When a humanoid robot is inside an environment, the level of ambient intelligence achievable depends upon its communication capabilities (hardware, network protocols) with the surrounding environment. When the level of compatibility is zero, the humanoid robot relies solely on its autonomous capabilities, and the basic set mentioned in section III is necessary. When the hardware and the network protocols are compatible, the interaction with the rest of the environment make necessary to match the robot's ontology and the one of the environment. There is no standard yet corresponding to this in the robotic community, but section VI indicates some solutions. The reason is that the services externalized by the humanoid robot are mostly related with its decision layer capabilities. Thus all the problems induced by the choice of primitives and their composition are present. Moreover the comprehension of the informations provided by the environment for the robot to achieve its task relies again on the agreement of common protocols. Chibani et al. [START_REF] Chibani | Context aware service agents for ubiquitous robots applications[END_REF] proposed an algorithm to semantically discover context services in order for two agents to interact with each others. Such mechanism completed with activity recognition [START_REF] Yang | Activity recognition for the digital home[END_REF] would allow a humanoid robot to perform high-level actions for a human.

V. REMOTE INTERACTION

Remote Interaction in this context embeds communication through the Internet as depicted in the left upper-part of figure 1. One of the interactions is tele-operation, which is already used to maneuver robots in far away situations such as the ISS, or in situations where human-life can be endangered. It is also a mean to overcome the current limitation of robot capabilities regarding autonomous decision making. When the robot is unable to perform a mission because he faces an unknown situation he can call a human for help. This can be especially useful for robots aimed at helping aging people, or persons with low-mobility. Tele-operating a humanoid robot while performing a collaborative work is challenging because several constraints have to be taken into account: safety of the human co-worker, stability of the robot, realization of the task, taking into account the limitation of the robot and the quality of the information involved during decision-making. Mixing autonomous behaviors based on vision and speech recognition with tele-operation, Neo [START_REF] Neo | Whole-body motion generation integrating operator's intention and robot's autonomy in controlling humanoid robots[END_REF][3] demonstrated a humanoid robot able to recognize orders, detected visually the pose of a fridge and a can, and bring back the can to the person. Based on this technology we have demonstrated in collaboration with Technical University of Munich [START_REF] Peer | Intercontinental multimodal tele-cooperation using a humanoid robot[END_REF] that it is possible to teleoperate the humanoid robot HRP-2 with a telepresence device providing stereoscopic visual feedback and force feedback, while performing a collaborative task with another human on a remote site located in Japan.

The other kind of remote interaction are realized through the access to remote services. Among them it is possible to download CAD models of object locally identified through RFID or bluetooth connection. The robot could also use Google Images to relate words provided by a user to visual representation [START_REF] Fergus | Learning object categories from google image search[END_REF]. This calls for protocols which are described in the new section.

VI. INTEGRATION IN COLLABORATIVE WORKING ENVIRONMENT

Nowadays IT infrastructure are moving towards Service Oriented Architectures (SOA) [START_REF] Bosch | Service orientation in the enterprise[END_REF] because they provide a great flexibility. This flexibility is used in conjunction with Business Process Model to model the overall production inside a company [START_REF] Steffen | Full life-cycle support for end-to-end processes[END_REF]. The most salient feature of this approach is to re-introduce non technical decision maker in the modeling process. Technically the ontology related to the services provided is usually defined by the protocol Web Service Description Language (WSDL). The communication protocol used to perform data-exchange and remote procedure call are XML-RPC or SOAP. Recently new protocols emerged specifically to allow devices to connect seeminglessly to such SOA environment: UPnP and Devices Profile for Web Services (DPWS). They implement a service discovery mechanism, providing standardized service classes, event notification and secure communications (for DPWS). Several EU projects proposes devices and open source implementations of this protocol [START_REF]Socrades[END_REF] [START_REF]Soda[END_REF]. We do think that following this standard will foster the introduction of robots in CWE, and fix some issues raised recently in the robotic community regarding software development [START_REF] Bruyninckx | Robotics software: The future should be open[END_REF].

VII. CONCLUSION

In this paper we proposed a pattern of architecture depicted in figure 1. For each of the sub-system we described current approaches used in human-size humanoids, and described the current technical locks. We described our current solution in trying to tackle those problems, and the future directions to put humanoid robots in Collaborative Working Environment.

Fig. 1 .

 1 Fig. 1. A general framework to realize a collaborative task in a collaborative environment.

This work is supported from the ROBOT@CWE EU CEC project, Contract No. 34002 under the 6th Research program www.robot-at-cwe.eu.