Madeline Cheah
email: cheahh2@uni.coventry.ac.uk

Siraj A Shaikh
email: siraj.shaikh@coventry.ac.uk

Jeremy Bryans
email: jeremy.bryans@coventry.ac.uk

Hoang Nga Nguyen
email: hoang.nguyen@coventry.ac.uk

Combining Third Party Components Securely in Automotive Systems

Keywords: automotive security, attack trees, secure design, security testing, Bluetooth

Vehicle manufacturers routinely integrate third-party components and combining them securely into a larger system is a challenge, particularly when accurate specifications are not available. In this paper, we propose a methodology for users to introduce or strengthen security of these composed systems without requiring full knowledge of commercially sensitive sub-components. This methodology is supported by attack trees, which allow for systematic enumeration of black box components, the results of which are then incorporated into further design processes. We apply the methodology to a Bluetooth-enabled automotive infotainment unit, and find a legitimate Bluetooth feature that contributes to the insecurity of a system. Furthermore, we recommend a variety of follow-on processes to further strengthen the security of the system through the next iteration of design.

Introduction

Automotive security has become an issue with the advent of smarter vehicles, which incorporate a large variety of external facing interfaces that could be used to maliciously affect vehicles. The context of our work is the way in which various components are combined to achieve the final vehicle product. Components are often generic with many general purpose features. This promotes their reuse, which drives overall costs within the supply chain down. Larger components are often provided as whole "off-the-shelf" subsystems (for example an infotainment unit), with each component originating with a different manufacturer. Within the automotive supply chain, system integrators often do not have the final detailed designs of the components, especially where these components represent intellectual property such as source code. Components for which no privileged information is available are often referred to as "black boxes" [START_REF] Liu | Software Vulnerability Discovery Techniques: A Survey[END_REF], with "white boxes" being those for which all information is available. This distinction becomes important when testing the integrated system [START_REF] Midian | Perspectives on penetration testing -Black box vs. white box[END_REF].

The contribution of this paper is a methodology for the secure combination of third party components. The methodology includes a systematic and semiautomated penetration testing process supported by attack trees. This leads to the identification of additional security requirements over and above the functional and integration requirements that already exist for the system, which can then be used to improve the design of the system with respect to security. The motive for beginning the process with testing is to acquire confidence with regard to the overall implementation. The testing process moves knowledge of the component along the black-white spectrum, where we can then extract requirements for secure behaviour in the given context to help mitigate security flaws. This is particularly valuable where a system contains many third party components of which even the original equipment manufacturer (OEM) may not have complete sight because of commercial sensitivities.

The remainder of this paper is structured as follows: we review related work in Section 2, followed by an outline of our proposed methodology in Section 3. We then apply this methodology to a case study in Section 4. We discuss the implications thereof and our conclusions in Section 5.

Related Work

There are comparative approaches to each of the stages of our methodology, and as such our survey has been divided into categories of gathering security requirements, threat assessment and attack trees, along with a brief discussion on the automotive specific cybersecurity standard J3061.

Security requirements Similar methods for gathering security requirements have been proposed by [START_REF] Fuchs | Identification of Security Requirements in Systems of Systems by Functional Security Analysis[END_REF], in that security requirements are linked to possible attacks. A key difference to our methodology however is that a functional model of the system is required, which is more information than is usually available in a black box system. Attack trees in a requirements gathering and actioning process are also used in the System Quality Requirements Engineering (SQUARE) methodology [START_REF] Gordon | System Quality Requirements Engineering (SQUARE) Methodology: Case Study on Asset Management System[END_REF]. However, use cases in this methodology concentrated on application to a company's procedures rather than embedded systems.

Threat assessment This process determines threats (defined as potential negative events that could compromise an asset) to the surface of the target system, typically by looking at the potential malicious actions. In the automotive domain, empirical studies have already shown that attacks on vehicular components are possible [START_REF] Checkoway | Comprehensive Experimental Analyses of Automotive Attack Surfaces[END_REF]. However, despite impressive experimental analyses, actions taken to compromise the vehicle and their results were not systematised. This, in addition to the "grey box" nature of automotive components led us to penetration testing for threat assessment, supported by attack trees, in order to determine the initial security state of the system relative to the target attack goal.

Attack trees Attack trees are diagrams modelling the potential actions of an attacker to reach an attack goal [START_REF] Schneier | Attack Trees: Modeling Security Threats[END_REF]. They have been discussed as a possible threat modelling technique in the automotive specific SAE cybersecurity standard J3061 [START_REF]Cybersecurity Guidebook for Cyber-Physical Vehicle Systems[END_REF], which draws from the "E-safety vehicle intrusion protected applications" (EVITA) project. It is for this reason that we have chosen to use this method. Furthermore, attack trees can help inform threat assessment even in an informal capacity [START_REF] Opdahl | Experimental comparison of attack trees and misuse cases for security threat identification[END_REF]. Formal methods such as attack graphs are not feasible as there is not enough up-front information about the target system.

These trees can be represented diagrammatically or textually. Logic gates (AND and OR) are also commonly used within these trees. Where AND is used, an attack (parent node) is considered complete only if all steps have been completed. Where OR is used, the parent node is complete if at least one of the steps is completed. These gates are also sometimes referred to as conjunctive and disjunctive refinements respectively [START_REF] Mauw | Foundations of Attack Trees[END_REF]. For application purposes, where temporal order may be a concern, sequential AND (SAND) could also be used.

A related approach is the formation of "anti-models" [START_REF] Van Lamsweerde | Elaborating Security Requirements by Construction of Intentional Anti-Models[END_REF], depicting how model elements may be threatened (analogous to attack trees). However, these anti-models are derived from the model of the system-to-be (with attendant high informational needs), which makes it less suitable for a black-box system. Even where there are methods that allow for only partial specifications (such as the framework based on Model Driven Engineering) [START_REF] Idrees | A framework towards the efficient identification and modeling of security requirements[END_REF], perfectly legitimate behaviour in those specifications could actually be a weakness in terms of the larger system boundary.

EVITA and J3061 EVITA elaborates on some of the possible usages of attack trees. Deliverable 2.3 also includes an outline in which security requirements could be traced back to the attack tree [START_REF]Deliverable D2.3 -Security requirements for automotive on-board networks based on dark-side scenarios[END_REF]. This is, broadly, along similar lines to our work (although we begin with less knowledge of functionality and other requirements). Additionally, the "dark-side scenario analysis", closest to our security testing process, places particular emphasis on risk assessment, whereas the purposes of our own methodology would be to identify specific insecurities relating to an attack goal without looking at the motivations behind it. J3061 [START_REF]Cybersecurity Guidebook for Cyber-Physical Vehicle Systems[END_REF] also outlines the use of attack trees (in reference to EVITA). The standard also notes that it may only be possible to consider high-level concepts early in the product development cycle. Security analysts or designers could use our methodology as a way of gathering low level requirements for the next design iteration.

In summary, many of the comparative methodologies reviewed above require in-depth knowledge of the system. Our proposed methodology addresses specifically the problem of a black box with many layers of obscurity, all of which may be individually secure, but may exhibit system-wide insecurities.

Proposed Methodology

The methodology adopted in this paper is as follows:

Step 1 -Security testing: Since full specifications are generally unavailable, we begin with security testing (more specifically penetration testing) to probe the black box. This is systematised using attack tree methodology. Initial attack trees are first defined relative to an attack goal. These goals can be as low level (flood an open port with data) or high level (denial of service) as needed and tailored to the target interface.

Step 2 -Inferring requirements: Requirements can be extracted from whichever attack proved successful through a process of inference, and is essentially a negation of observed undesirable behaviours found from testing. The determination of security requirements at this stage can be cross-referenced back to the attack tree. This allows for specific insecurities to be addressed as well as separation of security requirements from other types of requirements (known to be useful for interaction analysis [START_REF] Van Lamsweerde | Elaborating Security Requirements by Construction of Intentional Anti-Models[END_REF]).

Step 3 -Suggesting specifications: Once the requirements gathering phase is considered complete, possible specifications could be suggested using a process such as design space exploration. There may be a number of different design choices (and therefore specifications) that could be made to mitigate the threat. These derived specifications could be cross-referenced with other subsets of specifications (such as safety), and where there are contradictions, could help clarify design choices. Where there are no conflicts, the derived security specifications from our process could be added to the overall set of specifications.

Step 4 -Incorporation of specifications into existing processes: Agreed specifications can be sent down the supply chain. Alternatively, the end user could follow up with in-house model-based design and testing processes. We discuss the latter within the context of our case study (see Section 4). The reason for keeping such flexibility is to enable incorporation of this methodology into the wider processes that might be carried out by the end user.

Case Study: Automotive Infotainment Unit

For this paper we concentrate on the infotainment unit, where diverse technologies are integrated to deliver functionality such as hands-free communication. We demonstrate the proposed methodology using a case study below. Although this case study came from a single vehicle, it can be reasonably assumed that vehicles of the same make, model and age would share the same weaknesses as production lines are standardised.

Step 1 -security testing: The security testing process was focused on the Bluetooth interface because it is a viable attack vector [15], and because of its ubiquity in cars (an estimated nine million vehicles have implemented this technology [START_REF]GSMA: Connected Car Forecast: Global Connected Car Market to Grow Threefold within Five Years[END_REF]). As a vector, it can be used to mount many attacks [START_REF] Dunning | Taming the blue beast: A survey of bluetooth based threats[END_REF] ranging from denial of service to man-in-the-middle attacks. Implementations can also differ greatly, with various "profiles" available to customise the technology.

The building of the initial attack tree was manually guided, using known vulnerabilities in other Bluetooth applications and surveyed from literature and the National Vulnerability Database [START_REF]National Vulnerability Database 15[END_REF]. We then evaluated the Bluetooth interface of an automotive infotainment unit using this attack tree. A number of undesirable behaviours were found, including the ability to mount the filesystem of the infotainment unit and read its contents. This was possible because of the presence of the Object Exchange File Transfer Profile (OBEXFTP) service [START_REF]Bluetooth Specification: File Transfer Profile[END_REF]. We highlight this as an example for the remainder of the paper. Step 2 -inferring requirements: After having connected to the interface using a legitimate pairing and device (the connection, vehicle or device had not been tampered with in any way), we mounted the file system. Being able to mount the filesystem through Bluetooth could lead to injection of malware, directory traversal and data extraction, manipulation or destruction. As such it is undesirable behaviour, so our inferred requirement from this would be "no unauthorised external agency should be able to see or influence the vehicular operating system's filesystem".

Step 3 -suggesting specifications: Based on the case study attack tree, we could fulfil the requirement above by creating specifications that either (a) remove the ability to request files or data (could conflict with functional requirements); (b) remove the ability to mount the filesystem (may have functional or cost implications) or (c) allow the above, but remove support for extracting, deleting or creating (injecting) files (which would conflict with the required functionality of the FTP server role as specified by Bluetooth SIG [START_REF]Bluetooth Specification: File Transfer Profile[END_REF]).

Step 4 -model-based design and formal verification: Formal analyses of the Bluetooth protocol and its authentication and secrecy properties exist [START_REF] Chang | Formal analysis of authentication in bluetooth device pairing[END_REF]. However, we are not attacking the protocol, but rather probing the larger system in which it resides. This is an example of two components in themselves being secure, but exhibiting insecure behaviour when combined into a larger system. Additionally, all users of the Bluetooth system in this test vehicle are able to use all services offered regardless of who they are. Authentication thus becomes irrelevant. Therefore a more appropriate analysis would be reachability, to demonstrate that such an insecure system state could not be reached through the pathways dictated by the attack tree.

We use the process algebra CSP (Communicating Sequential Processes) to describe a specification of the inferred requirements. We choose CSP because it is able to represent and combine the message passing choreography expected by individual components. A complete introduction may be found in [START_REF] Roscoe | Understanding Concurrent Systems[END_REF].

The specification for the Bluetooth FTP is available [START_REF]Bluetooth Specification: File Transfer Profile[END_REF] and so we developed a small illustrative CSP model (figure 2). We then developed a suggested specification from our inferred requirement, such as never displaying the filesystem (see figure 3) which fails during the verification process with trace pair, connect, service discovery, advertise service, obexf tp.M ountF S, displayf s . If, however, we removed OBEXFTP, and assuming none of the other services offered the ability to mount a filesystem, it would verify correctly.

We use this exercise to show that the inferred requirement is not met by the standard FTP specification (that a server must respond to a request from a client for "Folder Listing Objects") and is, in fact, contradictory. Thus, any attempt to remove support whilst still maintaining the profile would be breaking Bluetooth's specification.

Here, the model and example specification is simplistic enough to make it selfevident that the removal of OBEXFTP would allow for successful verification. This exercise would add value provided: (a) the systems are sufficiently complex; (b) we can create a more accurate model of the system under investigation, or (c) there is more than one path to mount the filesystem (or, more generally, to achieve any other undesirable behaviour).

Discussion and Conclusion

Our methodology is suited for tiered supply chains, as there is no need to have complete specifications of the integrated item for security testing. It also reflects real world security issues that have arisen through the testing process. The attack tree methodology allows for systematisation and traceability, especially where design choices are concerned. These choices could also be cross-referenced against scenarios that were posited in attack trees but were not tested. Any security requirements gathered can be kept separate for interaction analysis and allows for reasoning about alternatives. The formal exercise could allow for clarification of ambiguities, and using a verifier leads to a higher level of confidence in the resulting design (albeit dependent on the model constructed). Limitations include the fact that the initial creation of the attack tree is manually guided although domain expert input in reviewing the tree and repeated testing over more vehicles would mitigate this. There is also a one-off cost of building these trees, although reuse is possible in future testing processes. As testing scope expands, trees could also become crowded, and so tree navigation will be essential. Problems with scalability could also be mitigated using mechanical tools such as design space exploration. Furthermore, the data available to construct the model at the end of the process directly impacts the quality of the model created.

In this paper, we have presented a methodology for securely combining third party components into a wider system and applied it in the context of an automotive head unit using the Bluetooth interface. We have found weaknesses through structured security testing, and using the case study of being able to mount the filesystem through Bluetooth, we demonstrated how to infer security requirements and suggest specifications. We have also recommended follow-on processes that we envisage end users would find constructive in strengthening the security of their systems. Future work would include refining the process by applying the methodology to a more significant case study, with different attack goals. Through both of these, we also aim to acquire enough information as to be more concrete with regards to formal processes. Ultimately, we wish to position this methodology in a larger design process such as that espoused by standards such as J3061.

Fig. 1 .

 1 Fig. 1. Attack tree focusing on extracting data via mounting the filesystem

Fig. 2 .Fig. 3 .

 23 Fig. 2. Small illustrative model of the OBEXFTP service

Acknowledgements. The authors would like to thank Olivier Haas (Coventry University) and Alastair Ruddle (HORIBA MIRA) for valuable comments.


Mourad Abbas
email: m_abbas04@yahoo.fr

Kamel Smaïli

Daoud Berkani
email: dberkani@hotmail.com

Kamel Smaili
email: smaili@loria.fr

TR-Classifier and kNN Evaluation for Topic Identification tasks

Keywords: TR-classifier, k Nearest Neighbors, Arabic corpus, topic vocabulary

come   L'archive ouverte pluridisciplinaire

I. INTRODUCTION

OPIC identification has been sufficiently studied for Indo-European languages. Generally, the methods used are those of text categorization: Bayesian classifiers [START_REF] Tzeras | Automatic Indexing Based on Bayesian Inference Networks[END_REF][START_REF] Lewis | Comparison of two Learning Algorithms for Text Categorization[END_REF][START_REF] Moulinier | Is Learning Bias an issue on Text Categorization Problem?[END_REF], decision tree [START_REF] Lewis | Comparison of two Learning Algorithms for Text Categorization[END_REF][START_REF] Moulinier | Is Learning Bias an issue on Text Categorization Problem?[END_REF][START_REF] Fuhr | A rulebased Multistage Indexing Systems for Large Subject fields[END_REF], neural networks [START_REF] Wiener | A neural network approach to topic spotting[END_REF][START_REF] Ng | Feature selection perceptron learning, and a usability case study for text categorization[END_REF], kNN "k Nearest Neighbors" [START_REF] Creecy | Trading Mips and Memory for Knowledge Engineering: Calssifying Census Returns on the Connection Machine[END_REF][START_REF] Yang | Expert Network: Effective and Efficient Learning from Human Decisions in Text Categorization and Retrieval[END_REF], etc. Nevertheless, for Modern Standard Arabic, few works have been carried out [START_REF] El-Kourdi | Automatic Arabic Document Categorization Based on the Naïve Bayes Algorithm[END_REF][START_REF] Sawaf | Statistical Classification Methods for Arabic News Articles. Arabic Natural Language Processing[END_REF][START_REF] Abbas | Comparison of Topic Identification Methods for Arabic language[END_REF][START_REF] Abbas | Topic Identification by Statistical Methods for Arabic language[END_REF][START_REF] Rosso | Arabic Named Entity Recognition: An SVM-based Approach[END_REF]. The aim of this study is to evaluate two text categorization methods applied to Arabic documents. The first method is TRclassifer [START_REF] Abbas | Comparing TR-Classifier and kNN by using Reduced Sizes of Vocabularies[END_REF][START_REF] Abbas | A Trigger-based Classifier[END_REF][START_REF] Abbas | Topic Identification for Automatic Speech Recognition[END_REF], a new method based on triggers, and the second one is the famous k Nearest Neighbors. The concept of triggers has been largely used in statistical language modeling. Indeed, Triggers had been used to improve and generalize the Cache model [START_REF] Kuhn | A cache-based natural language model for speech recognition[END_REF]. The latter enhances the probability of a word w i when it occurs in its left context. A trigger model goes further and enhances the probability of a list of words which are correlated to w i [START_REF] Tillman | Selection criteria for word trigger pairs in language modeling[END_REF]. This means that for all the words which occur in the right context of a word, their probability will be increased. [START_REF] Tillmann | Word trigger and the EM algorithm[END_REF]. We take advantage of triggers and propose a new clustering method. The motivation behind the TR-classifier design is that the information found in the longer-distance history is significant [START_REF] Rosenfeld | Adaptive Statistical Language Modeling: A Maximum Entropy Approach[END_REF]. Indeed, for a topic identification task, the presence of the term "guitar" could trigger another list of terms: "music", "dance", etc. Hence, the main idea of TRclassifier is to represent each topic by triggers and triggered words which characterize each topic, and then facilitating the identification. The second method that we have used, is the well-known kNN. As this method is considered in [START_REF] Yang | A re-examination of text categorization methods[END_REF] as one of the topperforming classifiers, we selected it to compare its performance with that of TR-classifier.

The Arabic corpus used in our experiments is downloaded from the website of the Omani newspaper Alwatan; it is composed of more than 9000 articles. In section II, we give some details about both TR-classifier and kNN method. We talk, in Section III about some of Arabic language specificities. We present in IV and V respectively text preprocessing and evaluation measures. Section VI deals with corpus description, documents representation and vocabulary construction. Finally, experiments and results are exposed in section VII.

II. DESCRIPTION OF THE EVALUATED METHODS

A. An overview on the TR-Classifier

Let define the concept of Triggers before using it in TRclassifier. The triggers of a word w k are the set of words that have a high degree of correlation with it [START_REF] Abbas | Topic Identification for Automatic Speech Recognition[END_REF][START_REF] Rosenfeld | Adaptive Statistical Language Modeling: A Maximum Entropy Approach[END_REF][START_REF] Haton | Speech Recognition from signal to its interpretation[END_REF][START_REF] Lavecchia | Using interlingual triggers for machine translation[END_REF].

Given the following text: The main idea of the TR-classifier is based on computing the average mutual information of each couple of words which belong to the vocabulary V i . Triggers are couple of words that have a high value of (AMI) [START_REF] Tillman | Selection criteria for word trigger pairs in language modeling[END_REF][START_REF] Guodong | Interpolation of n-gram and mutual information based trigger pair language models for Mandarin speech recognition[END_REF]. They are considered important for a topic identification task. Each topic is then characterized by a number of selected triggers M, extracted from the topic training corpus T i .

Identifying topics by using TR-method consists in:

• Training step: Associating triggers to each word v k Є V i , where V i is the topic vocabulary of T i .

Selecting the best M triggers which characterize the topic T i .

• Test step: Identifying triggers of each word w k of the test document.

Computing Q i values by using the TR-distance given by ( 1):

(

Where i stands for the i th topic. n is the size of the test document. The denominator is a normalization coefficient which represents the number of times ) , (

i k k w w AMI is computed. i k
w are triggers extracted from the test document d, and characterizing the topic T i .

A decision for labeling the test document with topic T i is obtained by choosing i which maximizes Q i .

The Average Mutual Information for a couple of words a and b is given by equation [START_REF] Lewis | Comparison of two Learning Algorithms for Text Categorization[END_REF]. The AMI measures well the correlation between words since its computation relies on different probabilities values which are presented by equation [START_REF] Lewis | Comparison of two Learning Algorithms for Text Categorization[END_REF]. The usefulness of a trigger pair is not determined only by a high correlation but by its frequency too. In fact, in order to understand the importance of the AMI, we present here the example provided in [START_REF] Rosenfeld | Adaptive Statistical Language Modeling: A Maximum Entropy Approach[END_REF]. If we consider the trigger (Brest -Litovsk) consisting of two rare words but highly correlated, and compare it to a much more common one (Stock -Bond) which is less correlated, then it may be preferable to select the latter, if we are constrained to incorporate only one of the two trigger pairs. We can see also in Section VII some examples of computed triggers.

B. K Nearest Neighbors

kNN has been applied to text categorization before two decades [START_REF] Masand | Classifying news stories using memory based reasoning[END_REF][START_REF] Yang | Expert Network: Effective and Efficient Learning from Human Decisions in Text Categorization and Retrieval[END_REF][START_REF] Iwayama | Cluster-based text categorization: a comparison of category search strategies[END_REF][START_REF] Yang | A re-examination of text categorization methods[END_REF]. Indeed, Yang compared it to a set of text categorization methods using the benchmark Reuters corpus (the 21450 version, Apte set) [START_REF] Yang | A re-examination of text categorization methods[END_REF]. It has been found that KNN is one of the top-performing methods after SVM [START_REF] Yang | A re-examination of text categorization methods[END_REF]. Many other researches have found that the kNN method achieves a high performance by using different data sets [START_REF] Yang | A re-examination of text categorization methods[END_REF][START_REF] Joachims | Text Categorization with Support Vector Machines: Learning with Many Relevant Features[END_REF][START_REF] Baoli | A Comparative Study on Automatic Categorization Methods for Chinese Search Engine[END_REF].

The TR-Classifier is an original method which leads to acceptable scores even with small vocabularies. The idea of comparing it to KNN aims to highlight whether its performance is better or worse than that of KNN, particularly when using small vocabularies. Let's note that, we are carrying out experiments in order to compare the TR-Classifier to other methods, such as SVM, M-SVM, genetic algorithms, etc.

The strategy of the kNN algorithm is quite simple, so that, to identify a topic-unknown document d, kNN ranks the neighbors of d among the training document vectors, and uses the topics of the k Nearest Neighbors to predict the topic of the test document d. The topics of neighbors are weighted using the similarity of each neighbor to d. In order to measure this similarity, the cosine distance is used, although other measures are possible, as the Euclidean distance. The cosine similarity is defined by [START_REF] Moulinier | Is Learning Bias an issue on Text Categorization Problem?[END_REF].

( ) ( ) ( ) ∑ ∑ ∑ = = = = V k V k ik jk V k ik jk i j d d d d D D sim 1 1 2 2 1 , (3)
where D j is the j th training document and D i is the i th test document. | V | is the size of the global vocabulary. d j and d i

) ( ) ( ) , ( log ) , ( b p a p b a p b a p P ab = ) ( ) , ( 2 b a b a b a ab P P P P b a AMI r r r r + + + = ) ( ) ( ) , ( log ) , ( b p a p b a p b a p P b a = ) ( ) ( ) , ( log ) , ( b p a p b a p b a p P b a = ) ( ) ( ) , ( log ) , ( b p a p b a p b a p P b a = ∑ ∑ - = - = 1 0 n l i k k i k i l n w w AMI Q ) ( ) , (
, represent the weights of the words belonging respectively to D j and D i . To assign the test document d to the correct topic, a cutoff threshold is needed [START_REF] Yang | A re-examination of text categorization methods[END_REF].

III. SOME SPECIFICITIES OF ARABIC

Arabic is a Semitic language which is written from right to left. Phonologically, it is composed of 28 consonantal phonemes and six vowels (long and short vowels). Short vowels "or diacritics" are omitted intentionally in most of texts.

Arabic is very inflectional compared to Indo-European languages. Indeed, nouns can be nominative ,مرفوع accusative منصوب or genitive .مجرور They can be singular, dual and plural. The dual is formed by adding " ان "

to the stem in the nominative case and " ين " in the genitive and accusative one. The plural is formed by the addition of " ون "

or " ين " to the stem according with the inflection case. In the feminine case, the suffix " ات " must be added. However, there are many other plural forms: حصان → ,أحصنة أرض → أراضي جندب, → جنادب .

In addition, in unvocalised arabic texts, we can find many words that can be written in the same form. Moreover, Arabic uses an agglutinative strategy to form surface tokens [START_REF] Benajiba | Arabic Named Entity Recognition: An SVM-based approach[END_REF]. If we take the example و درستھم "wadarrasathum", it is clear that the word stemming is more complex than its equivalent in English "and she has taught them". In fact, the sparseness of Arabic data decreases the efficiency of the training significantly [START_REF] Benajiba | Arabic Named Entity Recognition: An SVM-based approach[END_REF]. That is why tokenization is necessary to tackle this problem.

Another particularity of Arabic language is the absence of capital letters in the orthography which is considered as one of the most widespread problems faced to NER 1 systems [START_REF] Benajiba | Arabic Named Entity Recognition: An SVM-based approach[END_REF][START_REF] Benajiba | ANERsys: An Arabic Named Entity Recognition system based on Maximum Entropy[END_REF].

IV. TEXT PREPROCESSING

Text preprocessing is the basic stage needed for text categorization tasks. Its main objective is, in one hand to remove all the unnecessary particles and mistyping words and in another hand to transform document contents to a suitable form which can be used easily by different algorithms. In the following subsections, we present the most important operations.

A. Feature extraction

Features or types of information are extracted in order to be used by classifiers to find categories. For that, many 1 NER stands for Named Entity Recognition.

techniques are usually used such as removing stop-list words and stemming.

For Text Categorization purposes, the bag of words method is the most used. In fact, in the earliest work related to documents representation, Luhn [START_REF] Luhn | A statistical approach to mechanized encoding and searching of literary information[END_REF][START_REF] Luhn | The automatic creation of literature abstracts[END_REF] proposed the following ideas:

Luhn observed that authors emphasize an aspect of a subject by repeating certain words. They also usually use the same meaning of a word through a text. He also observed that only a limited number of words are used to express a particular idea. All these reasons conduct the community to reduce the space of representation of the original corpus that leads to good performance [START_REF] Lin | Robust automated topic identification[END_REF][START_REF] Lewis | An evaluation of phrasal and clustered representations on a text categorization task[END_REF].

For that, we proposed a stop-list of words that will be discarded from the document representation. This stop-list contains all the function words as: فيھا في، منه من، عليھم، على، etc. Furthermore, the definite articles in all their forms such as:

بالـ، ، فالـ ، كالـ ، ، الـ ،
are deleted. This pre-processing is easier for Indo-European languages for many reasons, among them we can mention the fact that definite articles and function words are isolated from the other words, and the plural form in Arabic has more variants than in French or English. For example, the plural forms of the two arabic words تلميذ and مدرسة are respectively ميذ ت and مدار س . However, for English, the equivalent is obtained simply by ending the two words by "s": student → students, school → schools. Nevertheless, on the contrary to Arabic, there are few irregularities for English, for example: man → men, woman → women, child → children.

B. Feature selection

Even though the stop-word removed and word stemming done, the dimensionality still high. That is why, it is necessary to select a subset of relevant features which allow to represent documents adequately.

Feature selection can be carried out by using various methods as Term Frequency, Document Frequency [START_REF] Yang | A comparative study on feature selection in text categorization[END_REF][START_REF] Ittner | Text categorization of low quality images[END_REF], Information Gain [START_REF] Yang | A comparative study on feature selection in text categorization[END_REF][START_REF] Sebastiani | Machine learning in automated text categorization[END_REF][START_REF] Mladenic | Machine learning on non-homogenous distributed text data[END_REF][START_REF] Brun | Topic detection and statistical language model adaptation for speech recognition[END_REF], Mutual Information [START_REF] Brun | Topic detection and statistical language model adaptation for speech recognition[END_REF][START_REF] Seymore | Nonlinear interpolation of topic models for language model adaptation[END_REF] and Transition Point Technique [START_REF] Pinto | Clustering abstracts of scientific texts using the transition point technique[END_REF]. In our experiments, we used Term Frequency.

V. EVALUATION MEASURES

In order to evaluate the classifiers performance, at least three standard measures are used, in this case: Recall, Precision and F1 measure. Recall is defined to be the ratio of correct assignments by the classifier divided by the total number of correct assignments. Precision is the ratio of correct assignments by the classifier divided by the total number of the system's assignments [START_REF] Luhn | A statistical approach to mechanized encoding and searching of literary information[END_REF]. The combination of the two measures with an equal weight gives the F1 measure, presented by the following expression: Other performance metrics which are used in many fields, could measure the classifiers' performance. False Acceptation Rate (FAR) which is defined to be the probability that the classifier incorrectly accepts the wrong document, and the False Rejection Rate (FRR) which is defined to be the probability that the classifier incorrectly rejects the desired document. Hence for a topic i T , FAR and FRR are given by the following expressions: The two measures take their values from 0 to 1. In fact, if FAR equals 0, then all documents are correctly labeled. On the contrary, the value 1 indicates that all documents are incorrectly labeled. However, we can decide that a classifier has a good performance if both FAR and FRR have jointly minimal values.

ecision
The plot of FAR against FRR is called the ROC curve (Receiver Operating Characteristic). The ROC curve of a perfect classifier would go through the point (0,0), it can be used to quickly visualize the quality of the classifier. In the Experiments and Results section, we will evaluate the TR-Classifier and kNN by using, in addition to Recall and Precision, ROC curves for some topics in order to highlight the difference in performance between the two classifiers. The idea behind using these metrics is to have a look at the evaluation from many different angles.

VI. CORPUS REPRESENTATION

We started by downloading Arabic texts from the archives of the Omani newspaper Alwatan of the year 2004. The size of the extracted corpus is about 10 millions terms which correspond to 9000 articles, distributed over six topics, in this case: Culture, religion, economy, local news, international news and sports. 90 % of these articles are reserved to training and the rest to the evaluation.

We should note that we have realized some elementary operations for topic identification, as eliminating insignificant words that do not bring any information, as function words, and also words whose frequencies are less than a definite threshold. We address in Table I the size of the entire corpus, before and after removing insignificant words.

The construction of the vocabulary has been made by using the term frequency method which gives good results though its simplicity [START_REF] Yang | A comparative study on feature selection in text categorization[END_REF]. Other terms selection methods as Mutual Information [START_REF] Seymore | Nonlinear interpolation of topic models for language model adaptation[END_REF] and Document Frequency lead also to a satisfactory performance.

The kNN method uses a general vocabulary, whereas the TR-classifier uses a vocabulary per topic, i.e., six topic vocabularies are built, in our case. We should note that these vocabularies are very small; indeed the size of each topic vocabulary is 300 terms. Nevertheless, they are composed of terms ranked from the maximum, to the minimum according to their frequencies. The reason behind the vocabularies size reduction is to make the topic identification process faster.

Documents need to be transformed to a compact vector form, and the dimension of the vector corresponds to the size of the vocabulary. Each word of the document is weighted by a definite value. The weights or vector components are those commonly used in text categorization, particularly for the TFIDF classifier [START_REF] Joachims | A probabilistic analysis of the rocchio algorithm with tfidf for text categorization[END_REF]. Hence, after removing insignificant words, we calculated both the frequency of each word "Term Frequency", and the Document Frequency of a word w, that means the number of documents in which the word w occurs at least once. The weight of each term results then from the product of Term Frequency and Inverse Document Frequency [START_REF] Joachims | A probabilistic analysis of the rocchio algorithm with tfidf for text categorization[END_REF][START_REF] Salton | Developments in Automatic Text Retrieval[END_REF][START_REF] Seymore | Using Story Topics for Language Model Adaptation[END_REF].

VII. EXPERIMENTS AND RESULTS

A. TR-Classifier Performance

As we mentioned in section III, TR-classifier uses a vocabulary per topic, and the words of each vocabulary are ranked according to their frequencies. In these experiments we used much reduced sizes of the six topic vocabularies, in this case: 100, 200 and 300 terms.

Hereafter, in Tables II andIII, we present the best triggers which characterize two different topics, in this case sports and culture. For example, the first important couple of words for the topic Culture is that for which the Average Mutual Information is higher, in this case: Culture → Meeting ( ثقافة → ملتقى ), followed by a list of triggers.

Otherwise, we notice that the obtained triggers as Team → National وطني( → منتخب ), Score → Competition ( منافسة → ,)رصيد Olympic → Athens ( اولمبية → أثينا ) describe well the topic Sports.

The evaluation of the TR-classifier has been made by varying both topic vocabularies sizes and triggers number N.

The choice of N = 20, with a topic vocabulary size 100, lead to an average recall rate equal to 71.55 %. For some topics, we achieved good results; nevertheless the performance is degraded for other ones. The fact that these topics had unsatisfactory Recall values is due to their variety. Indeed, splitting them to subtopics turns out to be convenient, even necessary to have a best performance. Otherwise, the three remaining topics are relatively identified, particularly topic "Sports" which had a Recall rate equal to 93.33 %.

In order to enhance the performance, we have conducted other experiments, in which we increased N. Indeed, when taking N = 40, average recall rate attains 79.44 %, which represents an improvement of 8 %. Values of N = 60 and N = 80 conducted respectively to a Recall of 82.33 % and 83.11 %. In this case, the improvement of the performance is very slight. Hence, we decided to use larger vocabularies: 200 and 300. The performance in terms of Recall by using a size of vocabulary 100 is presented in Figure 1.

Using a size of vocabulary 200 conducted to a slight improvement of Recall by nearly 1%. Nevertheless, this improvement necessitated to take N = 160 to reach 84 % in terms of Recall (See Figure 2). In order to show the performance of the two classifiers, we selected some topics for which we drew ROC curves.

VIII. CONCLUSION

In this paper, two methods of topic identification have been presented. Their performance has been tested on an Arabic corpus that we have constructed using many thousands of texts, downloaded from an online newspaper. One of these methods is the TR-Classifier: a new technique that we exposed in this paper and the second one is the well-known kNN.

The strong point of the TR-Classifier is its ability to realize better performance by using reduced sizes of topic vocabularies, compared to kNN. The reason behind this is the significance of the information present in the longer-distance history that TR-Classifier uses. Undoubtedly, kNN is one of the best methods which give satisfactory performance; nevertheless in the case of small vocabularies, as shown in the aforementioned experiments, its performance didn't exceed 76 % in terms or Recall. In perspectives, we aim to enhance the TR-Classifier performance by using greater sizes of vocabularies, though it outperforms kNN by 14 %, which is considered as a satisfactory result.

A

  large number of Taliban fighters may have crossed the border into Pakistan after pressure from U.S. and Afghan forces, Afghan officials said on Monday… In this example, the word Taliban may trigger Pakistan, Afghan and U.S. These words are triggered by Taliban. Consequently, if we are interested by retrieving articles TR-Classifier and kNN Evaluation for Topic Identification tasks Mourad Abbas, Kamel Smaili, and Daoud Berkani T concerning Taliban, the occurrence of the corresponding triggered words may concern an article about Taliban.

  probability that the words a and b are present in the same document. that the words a and b are not present in the same document. p(a) is the probability of the word a.

  For example درست could be equivalent to the following: Darastu → I have studied. Darasta → You have studied Darasti → You have studied Darasat → She has studied Darrastu → I have taught Darrasta → You have taught Darrasti → You have taught Darrasat → She has taught

Fig. 2 .

 2 Fig. 2. TR-Classifier performances using a vocabulary size 200 in terms of Recall and Precision

Fig. 1 .

 1 Fig. 1. TR-Classifier performances using a vocabulary size 100 in terms of Recall and Precision

Fig. 4 .

 4 Fig. 4. kNN performances versus number of neighbors

Fig. 5 .

 5 Fig. 5. TR-Classifier performances compared to kNN ones.

Fig. 6 .

 6 Fig. 6. ROC curves for the topics Culture/Religion.

Fig. 7 .

 7 Fig. 7. ROC curves for the topics Culture/Sports.

Fig. 8 .

 8 Fig. 8. ROC curves for the topics Local News/International News.

Fig. 9 .

 9 Fig. 9. ROC curves for the topics Local News/Sports.

Figures 6 ,

 6 Figures 6,[START_REF] Creecy | Trading Mips and Memory for Knowledge Engineering: Calssifying Census Returns on the Connection Machine[END_REF] 8 and 9 show that both TR-Classifier and kNN go through the point (0,0) for the selected topics. However ROC curves related to TR-Classifier are closer to the point (0,0) than kNN.

TABLE III .

 III THE TEN FIRST TRIGGERS CHARACTERIZING THE TOPIC SPORTS AND THEIR CORRESPONDINGS IN ENGLISH

sports Arabic English وطني → منتخب منافسة → رصيد اولمبية → أثينا دورة → أثينا نھائي → ربع عب → حارس مباريات → موسم ملعب → حارس شوط → حارس مسابقة → متر Team → National Score → Competition Olympic → Athens Tournament → Athens Final → quarter Player → Goalkeeper Match → Season Stadium → Goalkeeper Half-time → Goalkeeper Race → Meter

TABLE II

 II

		.
	THE TEN FIRST TRIGGERS CHARACTERIZING THE TOPIC CULTURE AND
	THEIR CORRESPONDINGS IN ENGLISH
		culture
	Arabic	English
	ثقافة → ملتقى	Culture → Meeting
	شاعر → قصيدة	Poet → Poem
	قصة → رواية	Novel → Story
	شخصية → مسلسل	Personage → Serial
	جمھور → م أف	Public → Movies
	معرض → تشكيلي	Exposition → Plastic
	فنان → مسلسل	Artist → Serial
	تشكيلي → لوحة	Plastic → Painting
	مسرح → فرقة	Theater → Group
	سينما → م أف	Cinema → Movies

Therefore, since the choice of vocabulary size 200 has not brought significant improvement compared with previous experiments, we continued with changing vocabulary size, and varying triggers number. We obtained better Recall values when using a vocabulary size of 300. Indeed, for N = 250, the best Recall rate achieved is 89.69 %. To see more clearly we show performance of the method in Figure 3.

B. kNN Evaluation

The main computation made by kNN is the sorting of training documents in order to find the k Nearest Neighbors for the test document. The value of k is usually optimized by several trials on the training and validation sets. In fact, if k is too large, small classes are overwhelmed by big ones. In practice, k is usually optimized by many trials on the training and validation data sets.

A general vocabulary is used by the kNN method. Thus we constructed it by concatenating the six topic vocabularies used in the previous experiment. The resulted size of this general vocabulary is 800 words. Thus, we selected empirically different values of k. Recall and Precision rates related to each value of k are presented respectively in Tables IV, V, VI and VII.

Experiments showed that the performance on average is enhanced by using small values of k. Indeed, for k=12, 8, 4, 3, average Recall rates are respectively: 71.11%, 72.55%, 75.66% and 75.88%, -See Figure 4 -. Nevertheless, the performance's evolution is different from one topic to another. Indeed, the performance for all topics is enhanced when k decreases excepting the topic Culture whose performances diminish. This is due on a big part, to its variety.

Overall, we should note that the kNN' performance is lower than those of TR-Classifier by nearly 14 % which is considered as an important difference between the two methods.

We can see clearly in Figure 5, the performance in terms of Recall of the two classifiers, for the six studied topics, in the case of using the size 300 for topic vocabularies and 800 for the general vocabulary. In 1979, he became Lecturer, Associated Professor then full Professor teaching signal processing and information theory in the Department of Electronics of NPS. During this period, his research activities involved the applications of signal processing and the source coding theory. In 1992, he joined the Department of Electrical Engineering of University of Sherbrooke, Canada, where he taught signal processing. He was a member of the Speech Coding team of the University of Sherbrooke. He has been conducting research in the area of speech coding and speech processing in adverse conditions.

In 1995, he backs to the Department of Electrical and Computer Engineering of the National Polytechnic, Algiers. His current research interests include signal and communications, information theory concepts and clustering and adaptive algorithms applied to speech and image processing. He is author of more than 150 papers.


Stanislas Brossette

Pierre-Brice Wieber

Collision avoidance based on separating planes for feet trajectory generation

In this paper, we present a formulation of the collision avoidance constraints that relies on the use of separating planes instead of a distance function. This formulation has the advantage of being defined and continuously differentiable in every situation. Because it introduces additional variables to the optimization problems, making it bigger and potentially slowing down its resolution, we propose a different resolution method that takes advantage of the independence of the variables, to form two subproblems that can be solved efficiently in an alternate problem fashion. We present some preliminary results using this approach in order to highlight its potential and promises in terms of convergence speed and robustness.

I. INTRODUCTION

When a legged robot takes a step, it is crucial to ensure that the trajectory of the leg, and in particular the trajectory of the feet, avoids unwanted collisions with the environment. In [START_REF] Kalakrishnan | Learning, planning, and control for quadruped locomotion over challenging terrain[END_REF] the collision-free feet trajectory of a four-legged robot is generated in the vertical plane containing the start and goal positions while staying away from the convex hull of the obstacles with a safety distance. That trajectory is later refined in order to avoid collisions with other parts of the legs, like the knee or shin. In humanoid robotics, most tasks require to consider collision avoidance, for walking tasks, the trajectory of the feet must avoid obstacles [START_REF] Nishiwaki | Planning and Control of a Humanoid Robot for Navigation on Uneven Multi-scale Terrain[END_REF], [START_REF] Kuffner | Footstep planning among obstacles for biped robots[END_REF], and for other tasks, such as ones performed in the context of multicontact locomotion, collisions need to be avoided between all the bodies of the robot that are not contact bearing and the environment. This impacts the formulations of problems of posture generation [START_REF] Brossette | Humanoid posture generation on non-Euclidean manifolds[END_REF] as well as motion planning and control [START_REF] Stasse | Real-time (self)-collision avoidance task on a hrp-2 humanoid robot[END_REF]. Collision avoidance can also be used with virtual obstacles, for example when the location of a potentially mobile obstacle is known with an uncertainty [START_REF] Bouilly | A numerical technique for planning motion strategies of a mobile robot in presence of uncertainty[END_REF].

In general, collisions are avoided by ensuring that the distance between bodies is always positive or greater than a safety distance. Schulman et al. [START_REF] Schulman | Motion planning with sequential convex optimization and convex collision checking[END_REF] presented in great details how to ensure collision avoidance in the context of motion planning and showcases applications on various scenarios with different robots. The distance between two objects is equal to the distance between their two closest points and finding those points is the tricky part. For general convex shaped objects, computing the location of the two closest points is most commonly done by using the Gilbert-Johnson-Keerthi (GJK) algorithm presented in [START_REF] Gilbert | A fast procedure for computing the distance between complex objects in three-dimensional space[END_REF]. The distance function for a pair of objects is based on the results of that algorithm, and a particularly important property of this function is that it is not continuously differentiable unless one of the objects is convex, and the other is strictly convex (proofs can be found in [START_REF] Gilbert | Distance functions and their application to robot path planning in the presence of obstacles[END_REF] and [START_REF] Escande | Continuous gradient proximity distance for humanoids free-collision optimized-postures[END_REF]). Non-differentiability of the distance function can lead to convergence issues when using smooth optimization(see [START_REF] Bonnans | Numerical optimization: theoretical and practical aspects[END_REF]). This issue is tackled in [START_REF] Escande | A strictly convex hull for computing proximity distances with continuous gradients[END_REF], where a method is proposed to generate (offline) a strictly convex approximation of the shape of an object with a bounding volume composed of patches of spheres and tori called STP-BV. That method requires the user to define a minimum radius of the STP-BV, which will impact the 'stiffness' of the evolution of the gradient of the distance functions.

Conversely to computing the distance between objects, it is often useful to compute the penetration depth between two colliding objects. Like during an optimization process, when at some iterations some objects are colliding and that quantity is useful to separate them. Or when solving scenarios involving virtual obstacles, with which a limited interpenetration can be tolerated. The abovementioned method for computing the distance between two object does not extend to situations where the objects are in collision and one needs to compute the interpenetration depth, which is the minimum translation needed to separate the objects. That quantity is usually computed using the Expanding Polytope Algorithm (EPA) [START_REF] Van Den Bergen | Collision detection in interactive 3D environments, ser[END_REF], which is not continuously differentiable. Both the distance and penetration functions involved in the constraint are non-differentiable [START_REF] Schulman | Motion planning with sequential convex optimization and convex collision checking[END_REF], and so is their sum. One must be especially careful when handling the transition point where the two objects are in contact without interpenetration.

Overall, the use of a distance function between objects to ensure collision avoidance is not particularly convenient. In this paper, we propose a different approach based on the idea that, in vertue of the 'Hyperplane separation theorem' [START_REF] Border | Separating hyperplane theorems[END_REF], if two convex objects are not colliding, there exists a plane separating them. Similar approaches are often used to detect interpenetration in computer graphics and to separate sets with Support Vector Machines [START_REF] Cortes | Support-Vector Networks[END_REF], but to our knowledge have never been used for the purpose of generating collisionfree trajectories in robotics. For each pair of objects, we search for a separating plane between them. The constraint of positive distance between two objects becomes a set of constraints requiring all the vertices of the objects to be above or below a separating plane. By relaxing this constraint, we show that it is possible to use this approach even when the objects are in interpenetration. Such a formulation has the advantage of being defined and differentiable in all cases(separated and interpenetrating objects), and being simpler than the usual method, using only one type of constraint and algorithm instead of two. Using this formulation, collision-free trajectory generation problems can be solved by a state-of-the-art nonlinear optimization solver, which we illustrate on some academic examples.

We aim at using this method to generate safe foot trajectory for humanoid robots. We present an alternative solving approach taking advantage of the structure of our collision avoidance constraint, in which, instead of solving one nonlinear problem, we decompose the resolution into two simpler problems. A nonlinear problem in the variables associated with the locations of the objects, that can become a quadratic problem(QP) is common cases, and a linear problem(LP) in the variables associated with the locations of the separating planes, those problems are then solved alternatively, which drastically reduces the computation times.

II. COLLISION AVOIDANCE CONSTRAINT WITH SEPARATING PLANES

A. Collision avoidance constraint

Given two bodies A and B, which convex hulls are respectively composed of the sets of vertices

V A = {v a 0 , • • • , v a ma } and V B = {v b 0 , • • • , v b m b }.
We define a plane P by its normal n and its orthogonal distance d to the origin of the world O. We illustrate these notations is figure Fig. 1. A plane P = { n, d} separating A and B must satisfy the following constraints:

   ∀v ∈ V A , v • n ≥ d ∀v ∈ V B , v • n ≤ d n = 1 (1)
Solving problem (1) allows to ensure that the plane P is between A and B if they are separated. When they are in interpenetration, the problem (1) is unfeasible. To deal with that infeasibility and ensure that the problem is always feasible, we can considere using an elastic mode by adding a relaxation term r to our constraints, which gives the following problem:

min. n,d,r r s.t.    ∀v ∈ V A , 0 ≤ v • n -d + r ∀v ∈ V B , 0 ≤ -v • n + d + r n = 1 (2)
When the problem (1) is feasible, r is null, otherwise, r's minimization will drive the plane to minimize the violation of both constraints of problem (1) simultaneously. The solution is then the plane P : { n, d} such that a translation of A by r n and of B by -r n makes the two objects separated by P . In other words, it gives the minimum penetration depth 2r and the direction of the penetration is given by n.

When imposing collision avoidance constraints, it is usual to require a safety distance 2β between the objects, our formulation straightforwardly extends to account for that:

0 ≤ v • n -d + r becomes β ≤ v • n -d + r (3)

B. Collision avoidance constraint in continuous-time trajectory

The constraint presented above allows to ensure the separation of two objects instantaneously. However, when generating a collision-free trajectory, ensuring that collisions are avoided instantaneously at every time step does not guarantee that there is no collision inbetween time steps.

In order to ensure that a collision-free trajectory exists between successive body positions B(t k ) and B(t k+1 ), we require that a plane P jk exists that separates each obstacle O j (defined by its position o j and set of vertices W j ) from the convex hull of the two successive bodies, which approximates the volume swept by B during the time interval [t k , t k+1 ], as illustrated in figure Fig. 2. Like in [START_REF] Schulman | Motion planning with sequential convex optimization and convex collision checking[END_REF], we ignore the effect of rotations of B on the swept volume as their influence in minor and can be encompassed conservatively by the use of a safety distance. This is equivalent to finding a plane that separates B(t k ) from O j and B(t k+1 ) from O j simultaneously. r jk denotes the relaxation term associated with the collision avoidance constraint with O j during time interval [t k , t k+1 ]. We denote x the set of problem's variables, such that x(t k ) = x k and the locations of a vertex v of B at time t is v(x(t))

The continuous-time collision avoidance problem is:

min. j,k r jk        ∀v ∈ V B , β ≤ v(x k ) • n jk -d jk + r jk ∀v ∈ V B , β ≤ v(x k+1 ) • n jk -d jk + r jk ∀w ∈ W j , β ≤ -(o j + w) • n jk + d jk + r jk n jk = 1 (4)

C. Complete nonlinear problem

By adding a cost function f (x) and concatenating the continuous-time collision avoidance constraints on all time interval, we can formulate a problem on the whole trajectory of a body B as an optimization problem: min.

x,d,n

f (x) + α R r s.t. ∀j, k        ∀v ∈ V, 0 ≤ v(x k ) • n jk -d jk + r jk ∀v ∈ V, 0 ≤ v(x k+1 ) • n jk -d jk + r jk ∀w ∈ W j , 0 ≤ -(o j + w) • n jk + d jk + r jk n jk = 1
(5) Due to the relaxation of the collision avoidance constraints, if a collision-free trajectory is not found, the result is a trajectory that minimizes penetrations. The choice of norm used on r governs the way the amount of penetration is minimized. With an l1-norm, the sum of all penetrations is minimized, while with an infinity-norm . ∞ , only the maximum penetration is minimized, disregarding all smaller penetrations. Using the l1-norm . 1 requires the addition of as many variables r jk as there are pairs {j, k}. Using the infinity-norm . ∞ a single variable r is sufficient. A careful choice of the coefficient α R allows to penalize exactly the violation of the non-collision avoidance constraint.

III. RESOLUTION

A. Resolution with NLP

In its generic form, the nonlinear problem ( 5) can be solved with a state-of-the-art nonlinear solver. To be rid of the n j = 1 constraints, we used PGSolver [START_REF] Brossette | Humanoid posture generation on non-Euclidean manifolds[END_REF], a nonlinear solver on manifolds and search for a solution on a manifold where the variables representing the normals n are elements of S 2 and thus always have unit-norm. In Fig. 3, we present a result obtained by solving [START_REF] Stasse | Real-time (self)-collision avoidance task on a hrp-2 humanoid robot[END_REF], where the cost function f approximates the total distance traveled by the body, with b k (x) denoting the 3D position of B at time t k :

f (x) = k b k+1 (x) -b k (x) 2 (6)
In this example, the trajectory is discretized in 8 time-steps for a body B going from position b I (blue) to position b F (green) while avoiding collisions with a cubic obstacle O 0 (red). One can observe how the separating planes are located: When possible, the planes coincide with the faces of the obstacle, some planes are tilted to allow reducing the distance between successive objects while maintaining collision avoidance. Solving problem (5) as is with a nonlinear solver is convenient, but it is fairly slow (see section IV). This is most likely due to the fact that it works with the entire set of variables: bodies and planes locations and all the nonlinear constraints. In the next section, we propose a different resolution method in which the variables are separated.

B. Resolution with alternate problems

We consider simplifying this problem by formulating two separate subproblems in which the variables related to the bodies {x} and the planes {n, d} are alternately fixed, and solving those two problems iteratively until a solution is found.

We denote PBP(n, d) the problem with fixed planes, and PBB(x) the problem with fixed bodies. By construction, PBP(n, d) is a linear program that can be efficiently solved by an LP algorithm. PBB(x) is a nonlinear problem, that can be solved by a nonlinear solver. In some cases, like for foot trajectory planning, it can be formulated as a quadratic problem with linear constraints, thus making it efficiently solvable with a QP algorithm.

We propose to use a method of alternate problems to solve [START_REF] Stasse | Real-time (self)-collision avoidance task on a hrp-2 humanoid robot[END_REF]. This consists in computing PBP(n, d) for a given set of planes locations, solving it to obtain a set of bodies locations that will be used to compute PBB(x). Solving PBB(x) gives new values of planes locations to compute the next iteration of PBP(n, d). And repeating this process until convergence, as described in algorithm 1.

Algorithm 1 Alternate problems resolution

Initialize n and b while not converged do compute PBB(x) {n, d} ←solve PBB(x) compute PBP(n, d) {x} ←solve PBP(n, d) end while 1) Problem with fixed bodies: When bodies variables are fixed, problem (5) can be formulated as a linear program. All the constraints remain expressed in the same way, except for the norm-1 constraint on the normal's variables n j . Enforcing the norm of n j to be 1 cannot be done exactly with linear constraints. But in fact, the amplitude of the vector n j does not matter, as long as it is not null. Only the direction of n j and the product d j n j describe perfectly the plane P j . Indeed, a plane described by {n j , d j } is equivalent to one described by {αn j , dj α } for any nonnull α. To ensure that n j is nonnull and maintains a norm of the magnitude of 1, we bound the scalar product between its current value n j (which is a problem's variable) and its value obtained as result of the previous iteration denoted n prev j (which is a constant). The lower bound n min needs to be strictly positive and the upper bound can be 1. Additionally, to prevent divergence of the components of n j , they can all be bounded between -1 and 1.

n min ≤ n prev j • n j ≤ 1 (7)
We obtain the following relaxed linear problem:

min. n,d,r r s.t. ∀j, k        ∀v ∈ V : 0 ≤ v(x k ) • n jk -d jk + r jk ∀v ∈ V : 0 ≤ v(x k+1 ) • n jk -d jk + r jk ∀w ∈ W j : 0 ≤ -w • n jk + d jk + r jk n min ≤ n prev jk • n jk ≤ 1 (8)
Notice that the problems for each {j, k} are only coupled by the relaxation variable. We can separate them into M independent LP problems of smaller sizes.

∀j, k              min. n jk ,d jk ,r jk r jk s.t.        ∀v ∈ V : 0 ≤ v(x k ) • n jk -d jk + r jk ∀v ∈ V : 0 ≤ v(x k+1 ) • n jk -d jk + r jk ∀w ∈ W j : 0 ≤ -w • n jk + d jk + r jk n min ≤ n prev jk • n jk ≤ 1 (9)
When r jk is positive, it is a measure of interpenetration, whereas when it is negative, it is a measure of the minimum distance between the plane and the two objects it separates. Therefore, by removing the norm on r jk in the cost function, the separating plane is driven to maximize that distance and thus placing the plane at equidistance from both objects it separates.

In order to avoid numerical issues, the solution plane is replaced by an equivalent plane with unit-norm normal before computing the next problem:

{n jk , d jk } ← n jk n jk , d jk n jk (10)
This prevents the norms of the n jk vectors to gradually converge towards zero.

Then the value of d jk can be changed as in [START_REF] Bonnans | Numerical optimization: theoretical and practical aspects[END_REF] so that the planes are located as close as possible to the obstacle, giving as much freedom as possible for the choice of location of the bodies in PBP(n, d).

d jk = max w∈Wj ((w + o j ) • n jk ) (11)
2) Problem with fixed planes: When the planes are fixed, the third set of constraint of problem ( 5) can be reduced to a single constraint as follows:

∀w ∈ W j , 0 ≤ -(o j + w) • n jk + d jk + r jk becomes max w∈Wj (w • n jk ) ≤ -n jk • o j + d jk (12)
The problem to solve becomes: min.

x,r

f (x) + α R r s.t. ∀j, k      ∀v ∈ V, 0 ≤ v(x k ) • n jk -d jk + r jk ∀v ∈ V, 0 ≤ v(x k+1 ) • n jk -d jk + r jk max w∈Wj (w • n jk ) ≤ -n jk • o j + d jk + r jk (13)
This problem can be solved with a state-of-the-art nonlinear solver.

In the event where f is quadratic and the positions of the vertices are linear in the variables x k , the problem (13) becomes a quadratic program, which can be solved efficiently with a QP solver, and more simplifications of the problem can be made. For example, when the location of the vertices can be defined only with the position b k of the body at time

t k : ∀v ∈ V : v(x k ) = b k + v ( 14
)
Then a modification similar to [START_REF] Escande | A strictly convex hull for computing proximity distances with continuous gradients[END_REF] can be applied to the first two sets of constraints of ( 13), giving: min.

x,r

f (x) + α R r s.t. ∀j, k        -min v∈V k (v • n jk ) ≤ n jk • b k -d jk + r jk -min v∈V k+1 (v • n jk ) ≤ n jk • b k+1 -d jk + r jk max w∈Wj (w • n jk ) ≤ -n jk • o j + d jk + r jk (15)
This problem can be simplified further by eliminating the constant d jk across the constraints of problem [START_REF] Cortes | Support-Vector Networks[END_REF] to get problem (16):

lb k max w∈Wj (w • n jk ) + n jk • o j -min v∈V k (v • n jk ) lb k+1 max w∈Wj (w • n jk ) + n jk • o j -min v∈V k+1 (v • n jk ) min. x,r f (x) + α R r s.t. ∀j, k lb k ≤ n j • b k + r jk lb k+1 ≤ n jk • b k+1 + r jk (16)
With the formulation (16) the problem features only three linear constraints per separating plane.

C. Problem initialization

Because the problem to solve is non-convex, we cannot escape the risk of finding a local minima as solution. Therefore, it is important to guide the resolution towards a satisfactory minima. This can be done by wisely choosing the initial guess. An obvious initial guess for the positions of the bodies is a sequence of evenly spaced positions on a straight line between the initial and final position. This initialization can then be modified depending on the application. For example, in the case of planning a foot trajectory for a walking robot, we can add a vertical motion of the foot that goes as high as the maximum height of a step h max .

b 0 k = b I + k b F -b I N + h max sin kπ N z (17)
Once the initial guess for the bodies position is computed, we can infer an initial guess for the planes by positioning them between the obstacle and the pair of bodies that they are meant to separate.

n jk = b k +b k+1 2 -o j d jk = (o j + n jk 2 ) • n jk n jk n jk ← n jk n jk (18)

D. Convergence criterion

The optimization process can be stopped when a stationary position is found, e.g. when the solutions of PBB and PBP are the same (or close enough in norm) across two successive iterations. Once a stationary point is found for PBB, it is possible that the solutions of PBP are not stationary. In that case, two successive PBP are identical(because the positions of the bodies are unchanged), except for the constraint [START_REF] Schulman | Motion planning with sequential convex optimization and convex collision checking[END_REF] which depends on the normal found in the previous iteration of PBP. Because of this constraint, a cycling on the solutions of PBP can occur, in which case, a stationary point can never be found. All the elements in such a cycle are solutions of the problem. Thus, we consider that a solution is reached once the positions of the bodies (solutions of PBB) are stationary.

IV. RESULTS AND EXPERIMENTATIONS

In this section, we present some results obtained with the proposed approach. All the computations of the following experiments are performed on a single thread of an Intel(R) Core(TM) i7-3840QM CPU at 2.80GHz, with 16Go of RAM. In the cases of resolution with alternate problems, one iteration of the algorithm counted per loop of the algorithm, e.g. PBB and PBP are solved at each iteration. Our goal is to solve problems of foot trajectory planning for humanoid robots. In such problems, only the translations of the foot are usually searched for and the locations of the vertices of the foot can be obtained through [START_REF] Border | Separating hyperplane theorems[END_REF]. Thus, in this section, we only focus on that type of problems in which PBP(n, d) is a QP. In all the following problems, the cost function is chosen to be a combination of the distance traveled by the bodies and their jerks:

f (x) = α P b k+1 -b k 2 + α J ... b k 2 (19)
A. Large cube avoidance

In this first example, we consider the problem of a collision-free trajectory planning for a foot stepping above a large cubic obstacle(red). The feet is represented by a rectangular prism, its initial(blue) and final(green) positions are on opposite sides of the cube, and the initial velocities and accelerations are null. A (linear) constraint requiring the bodies to be above the ground(yellow plane) is added to the problem. The left picture represents the initial guess, and the right one the solution found. A resolution of this problem with a nonlinear solver took 26 iterations, each of these iterations requiring the resolution of a QP more than twice larger than the one solved in the alternate resolution. A QP of size n is solved in approximately o(n 3 ), thus, solving a single QP that is twice larger should take about 8 times longer. In practice, the problem is solved in 5ms with the alternate problem method and 100ms with the nonlinear solver. The resolution method that we proposed in section III-B is thus much faster than a resolution with nonlinear solver as presented in section III-A.

B. Path through a small opening

Reaching convergence can become more difficult with problems where the initial guess violates the constraints, e.g. penetrates the obstacles. In order to study the robustness of our method to poor initialization, we design an environment such that the optimal trajectory for the bodies goes through a small opening between obstacles, and the initial guess proposed in section III-C is in collision with several obstacles. The alternate resolution finds a solution in only 10 iterations while the nonlinear solver takes 81 iterations to converge. Effectively taking respectively 4ms and 3.71s to converge. This example shows that even with a complex scenario where a good initial guess is difficult to find, the alternate resolution approach is still able to find a solution and is robust to penetrations in the initial guess.

Furthermore, the narrowness of the opening in which the body must pass would be an issue for an approach using STP-BV because it relies on the use of a bounding volume that makes the body thicker, thus potentially preventing it from crossing tight fitting openings. Methods based on a distance and interpenetration calculation are also likely to fail in that kind of situations because when crossing the opening, the distance function of the collision avoidance constraint would reach a gradient discontinuity. Our method overcomes those issues.

C. Virtual obstacle

A slight modification of our problems formulation allows to easily setup a form of hierarchy between the obstacles of the problem. Some obstacles can be considered as virtual ones, in the sense that they are avoided if possible, but only if avoiding them does not impact negatively the avoidance of non-virtual obstacles. This can be a useful feature in real scenarios where some obstacles are actually virtual, like the comfort zone of a human. Whereas others, like a physical wall that cannot be avoided shouldn't be considered as virtual. We discriminate through virtual and non-virtual obstacles by manipulating the relaxation terms. We consider two different relaxation terms r o and r v , respectively obstacles and virtual obstacles. They replace the relaxation terms used in the constraints of problem(16), and the cost function is changed to emulate a lexicographic optimization: lex min.( r o , r v , f (b)). This is achieved by using an exact penalization of the terms of the cost function: min. b,ro,rv

f (b) + α o r o + α v r v (20)
We illustrate this in the following problem where two obstacles(one virtual and one non-virtual) are too close to each other for the feet to pass through the gap between them. We present the solutions to two problems that differ by the choice of the right or left obstacle to be virtual. One can observe that in both cases the solution trajectory violates the non-collision constraint only with the virtual obstacle.

V. CONCLUSION

In this proceeding, we present a formulation of the collision avoidance constraint that is based on the notion of separating planes, instead of a distance between objects, as is usually done. The collision avoidance between two bodies is ensured by the existence of a separating plane between them. Unlike usual methods, our approach formulates the same way whether the bodies are separated or in interpenetration, and is continuously differentiable, which is an appreciated feature when running smooth optimization algorithms. Optimization problems featuring this type of constraints can be solved as is with nonlinear solvers, but we also propose an alternative resolution method to solves them more efficiently by separating the problem into two subproblems that can be solved iteratively until convergence. We tested our method on several problems of trajectory planning. The use of our custom resolution method with our collision avoidance constraint formulation shows very promising results in terms of robustness and convergence speed. This indicate that such methods could potentially be used on more complex problems, and may be fast enough to be used online to compute and update trajectories for real robots and in particular for computing feet trajectories for walking robots.

Fig. 1 .

 1 Fig. 1. Illustration of the collision avoidance constraint between bodies A and B separated by plane P = { n, d}

Fig. 2 .

 2 Fig. 2. Illustration of the collision avoidance constraint between successive bodies B j1 and B j2 and obstacle O j0

Fig. 3 .

 3 Fig. 3. Result obtained by resolution of the nonlinear problem with PGSolver

Fig. 4 .

 4 Fig. 4. left: initial guess; right: solution found after 6 iterations

Fig. 5 .

 5 Fig. 5. left: initial guess; right: solution found after 10 iterations

Fig. 6 .

 6 Fig. 6. Solution trajectories to problems with virtual obstacles. Virtual obstacles are in orange and non-virtual ones in red

Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP*, LJK, 38000 Grenoble, France This work has been funded by the PSPC Romeo

project and EU H2020 Comanoid Research and Innovation Action (RIA).The authors thank Adrien Escande for his advice and fruitful conversations on the topic of this contribution.