Anne Toulet
email: anne.toulet@lirmm.fr

Emmanuel Roux
email: emmanuel.roux@ird.fr

Anne-Élisabeth Laques
email: anne-elisabeth.laques@ird.fr

Éric Delaître
email: eric.delaitre@ird.fr

Laurent Demagistri
email: laurent.demagistri@ird.fr

Isabelle Mougenot
email: isabelle.mougenot@umontpellier.fr

E Delaître

A semantic-based approach for landscape identification

Here we present an original method for the automation of landscape identification in a satellite image. There are two major challenges in this process. The first lies in the ability to take all expert knowledge into account for the full time it takes to analyze the image. The second is successfully structuring and persisting this knowledge so that it becomes interoperable and usable in the Semantic Web context. In this paper, we explain how the combination of several strategies associating image processing, the calculation of specific characteristics and inductive logic programming (ILP) can feed into the automation process, and how the integration of knowledge via the construction of dedicated ontologies can meet these challenges.

Introduction

Particular emphasis is placed upon successful landscape identification in satellite images, since the study of landscapes and their evolution over time is one approach of addressing major social, economic and environmental challenges [START_REF] Fahrig | Effects of habitat fragmentation on biodiversity[END_REF]. To identify landscapes, the geographer can use a variety of techniques: field missions, aerial photographs, mapping tools and satellite imagery. A geography expert will use all of these approaches to characterize different types of landscape and draw up a map. It is, however, a very time-consuming task. Satellite imagery is currently used as a faster and more focused way of obtaining much of this information. Access to images is facilitated by the exponential growth in their production and much wider availability. It is actually very difficult to extract knowledge automatically from satellite images. Indeed, satellite image analysis techniques remain limited and this work cannot be done without human input. One of our goals is therefore to facilitate the geographers task by automating landscape extraction from satellite images. This goal is a very big challenge: it is very complex to reproduce the different stages carried out by the geographer. To achieve this, it is necessary to implement several strategies that use knowledge from the subject area (landscape geography), satellite imaging and inductive logic programming. In this article, we present our approach and implement it to automatically extract landscapes on an area of the Brazilian Amazon. The second goal is to structure and persist all this knowledge via dedicated ontological modules so that it is interoperable and reusable in the context of the Semantic Web. Thus, the use of ontologies makes it possible to initiate an approach towards the production of FAIR data: Findable, Accessible, Interoperable and Reusable [START_REF] Wilkinson | The fair guiding principles for scientific data management and stewardship[END_REF]. Satellite images have been subject to different studies involving ontologies e.g. [START_REF] Belgiu | Ontology based interpretation of very high resolution imageriesgrounding ontologies on visual interpretation keys[END_REF][START_REF] Chahdi | Towards ontology reasoning for topological cluster labeling[END_REF][START_REF] Forestier | Knowledge-based region labeling for remote sensing image interpretation[END_REF]. These ontologies actually play a wide variety of roles. The high volume of data and the exclusively digital nature of the data extracted from the image means that ontologies have to be constructed and regularly used to supplement other approaches, for example with supervised classification or clustering. This point will be detailed in the section 2. In our study, ILP is used instead of the conventional classification techniques. By opting for ILP, we are able to apply an approach that combines statistical learning and logic programming and thus formulate hypotheses that involve several variables simultaneously to describe objects in our image. Another reason for our choice is that we can work -at ILP level and with the ontologies -with formalisms that are all underpinned by predicate logic, even though the calculating processes differ. The paper proceeds as follows. In section 2, we first present related works and explain the similarities and the differences with our work. In section 3, we present the approach we applied to achieve our objectives: we first set out the geographical context and the preliminary processing for satellite images; then we explain how landscapes are extracted using ILP; and finally, we describe how these different stages feed knowledge into the integration process via specific ontologies: one dedicated to geography (landscape ontology) and the other to data taken from the image (image ontology). In section 4, we describe a practical application to present our approach. For a given satellite image, we explain the preliminary processing and calculations required before describing how classification rules are obtained to categorize the landscapes in the image. We will also show how we use this processing to populate the image ontology. In section 5, we will go over the results obtained for landscape prediction and for the role played by the ontologies. In our conclusion, we discuss the perspectives for this type of work.

2 Review of related works

Satellite imagery domain

Making sense of data that take the form of raster images requires well-structured thinking that may be aided by logic-based approaches. Because of key goals to discover new associations between data and to learn reasoning patterns, some existing works [START_REF] Bayoudh | Structural knowledge learning from maps for supervised land cover/use classification: Application to the monitoring of land cover/use maps in french guiana[END_REF] adequately exploit ILP techniques due to the natural representation of relation and the use of background theories. Some other works [START_REF] Andrés | Ontology-based classification of remote sensing images using spectral rules[END_REF][START_REF] Arvor | Advances in Geographic Object-Based Image Analysis With Ontologies: a review of main contributions and limitations from a remote sensing perspective[END_REF][START_REF] Belgiu | Ontology-based classification of building types detected from airborne laser scanning data[END_REF] take benefit of ontologies and associated reasoning capabilities to extract meaning from the content of images. Acquiring new knowledge is very demanding especially within the context of satellite images and can be partially automated by applying a combination of machine learning techniques with ontology to improve the performances of these techniques. We aim to use an inductive and deductive approach that will lead to a mixed knowledge-based strategy to automate the classification of different landscapes from satellite imagery. We try to investigate whether a knowledge base that is incomplete by definition can be automatically enriched using ILP. Additionally, a major challenge is to extract knowledge from satellite images that would meet the experts requirements as experts views have become a matter of real concern. A few works [START_REF] Forestier | Coastal image interpretation using background knowledge and semantics[END_REF][START_REF] Nieland | An ontological system for interoperable spatial generalisation in biodiversity monitoring[END_REF] combine machine learning and deductive reasoning to boost creating, adapting and generalizing knowledge within the context of remote sensing. To our knowledge, there is no consistent approach using both ontologies and ILPs as in the work presented here.

Life sciences domain

At the opposite, in life sciences, different approaches combine in a very effective manner ILP and ontology-based methods to acquire new knowledge and to validate some biological hypothesis [START_REF] King | Applying inductive logic programming to predicting gene function[END_REF][START_REF] Nguyen | Knowledge discovery in variant databases using inductive logic programming[END_REF][START_REF] Ryeng | Microarray data classification using inductive logic programming and gene ontology background information[END_REF][START_REF] Sternberg | Gene function hypotheses for the campylobacter jejuni glycome generated by a logic-based approach[END_REF]. Existing controlled vocabularies in life sciences as Gene Ontology are of importance and constitute a real help to build such approaches. Although the approaches are similar, it is difficult to compare results in areas as different as satellite imagery and biomedicine.

This state of the art shows that our approach to extract knowledge in satellite image combining ontologies and ILP is quite new and original.

Methodological approach

The different steps of our work are summarized in Fig. 1. In this diagram, we explain the global approach that we implemented to move from a raw satellite image to services exploitable by the geographer. To achieve clarity and accuracy, we divide our approach in three parts: the input (data & knowledge), the enrichment process and the output. The first part ("Input") concerns all data and knowledge used to feed the process as well as the preliminary processing of satellite images. By preliminary processing, we mean classical remote sensing treatments. The expertise provided by the geographer guides these treatments and the calculations are build to replicate landscape metrics. The second step ("Enrichment process" ) describes how to extract knowledge from the pre-processed satellite image, using two complementary methods: Inductive Logic Programming (ILP) and knowledge modeling. The geographic knowledge is modelled in the landscape ontology. The results of the calculations made in the preliminary processing of the satellite image are coded so that they can be exploited by ILP to produce classification rules that can then be applied to identify landscapes in the image. What is more, the characteristics obtained by the calculations are used to populate the image ontology. What is original about this method is that it combines two symbolic approaches: an inductive approach (ILP) and a deductive approach (ontology-based reasoning). The geography expert intervenes at two levels: he is involved in the construction of the ILP Knowledge Base and provides the necessary elements for ontological modeling. The last step ("Output") shows what you get at the end of this process. At this point, it is possible to offer services adaptated to the geographer's needs: reasoning, consultation and cartography for example. Each of these steps will be described in the following sections: first, from a generic point of view, and then illustrated in an example.

Input data & knowledge

We begin by setting out the context of landscape geography as envisaged in our study and the preliminary processing applied to the image to fulfill our requirements.

Geographical context.

Technically speaking, landscape identification uses a number of criteria, including composition and configuration, measured using landscape metrics applied to landscape components [START_REF] Farina | Landscape Ecology in Action[END_REF]. At this level of observation, Landscape Components (LC) refer to a specific land use or what is known as the "patch" in ecology. It is the relationships between the various components that determine the classification of a Landscape Type (LT). The landscape metrics used in this study are classical in this context [START_REF] Enserink | Biological invaders sweep in[END_REF], such as composition, diversity or fragmentation. As an example, a forest ecosystem landscape may be made up of various landscape components in varying proportions and with specific configuration (terra ferme forest 90%, gallery forest 6%, secondary vegetation (wild land and fallow land) 2%, cassava field 2%). One of the difficulties lies in the fact that, in satellite images, there are no objects "naturally" identifiable as landscape components to which landscape metrics could be applied. Here we will explain the preliminary processing required to achieve this.

Preliminary processing of satellite images.

The aim of the processing work is to obtain objects that can be likened to landscape components. The first step is therefore to produce a land use map that will be used to establish this kind of object in the image. Land use labels are used to categorize objects that can be likened to landscape components, such as "Water", "Vegetation" and "Forest" [START_REF] Richards | Remote Sensing Digital Image Analysis. An Introduction[END_REF]. However, the semantic level attained by this initial output is not high enough to take landscape structure into consideration. Most importantly, we are unable to apply landscape metrics directly to the objects obtained. Two questions are raised: how do you define the areas to which metrics should be applied, and what calculations should be defined in relation to landscape metrics? To respond to the first question, we place a grid on the image. The grid comprises a set of regular, square-shaped cells, the size of which is defined according to need. This procedure lets us identify well-defined arbitrary zones in the image, to which the metrics can be applied. When it comes to metrics, multiple tools are already included in remote sensing image processing software, such as ENVI1 or GRASS2 , and they can be used to make calculations for landscape metrics. We therefore replicate the geographers approach by applying these metrics to "landscape components" contained in each cell.

Enrichment process

Landscape extraction using ILP

Inductive logic programming is used to obtain landscape classification rules. In this section, we explain how these rules are produced.

Developing rules through automatic learning.

Inductive Logic Programming (ILP) was selected to induce rules capable of 'predicting' the classification of a cell as a landscape type, based on the landscape characteristics found in that cell. ILP was introduced by Muggleton [START_REF] Muggleton | Inductive logic programming[END_REF] and is an automatic learning method using examples (or a supervised learning method) and the formalism of first-order logic. As such, it is especially well suited to the discovery of relational knowledge within data. The value of this kind of method has been demonstrated for the identification of classification rules in the field of geographic and remote sensing data interpretation and processing [START_REF] Malerba | Empowering a gis with inductive learning capabilities: the case of ingens[END_REF][START_REF] Vaz | Spatial-yap: a logic-based geographic information system[END_REF].

Inductive Logic Programming (ILP): basic principles.

Inductive Logic Programming [START_REF] Lavrac | Inductive Logic Programming: Techniques and Applications[END_REF] works with • a knowledge base B expressed in first-order logic and describing a body of knowledge and a set of constraints; • a set of examples E split into two subsets E + and E -respectively, corresponding to positive and negative examples; • a description language L. ILP generates a "theory" (i.e. a set of rules), H, using the description language, L, and i) must cover positive examples E + and ii) must not cover negative examples E -. Among the existing inductive systems, the Aleph system [START_REF] Srinivasan | The aleph manual[END_REF] has been selected.

Information coding within the knowledge base.

Each landscape metric described above corresponds to a predicate in the knowledge base, i.e. a function that returns a response (true or false, or a constant) when adequate information is input. For example, the metric proportion of forest corresponds to the binary predicate forest proportion/2, applicable to a cell and returning the value of the proportion of forest in that cell. However, ILP can only reason with symbolic information. However, landscape metrics provide numerical data which therefore have to be recoded. The recoding method selected here is that put forward by [START_REF] Kavurucu | A comparative study on ilp-based concept discovery systems[END_REF]: for a given numerical data item, each value observed is recoded using inequalities that call on the characteristic values of the variable considered. In our application, these characteristics are the minimum (min), the 10th, 20th, . . . , 90th percentiles and the maximum (max) of the variable considered. Hence, each landscape metric corresponds to a predicate that can be used to test 20 inequalities. In the Prolog language used by the Aleph system, an inequality can be written as follows:

forest proportion qual(M, ≤ max):-forest proportion(M, X), X ≤ max
This coding is a good compromise between the loss of inherent information that occurs when converting numerical data to symbolic information, and the capacity for generalization during the learning process. Furthermore, it highlights significant value ranges [START_REF] Bayoudh | Structural knowledge learning from maps for supervised land cover/use classification: Application to the monitoring of land cover/use maps in french guiana[END_REF].

Example base and rule induction.

Given the goals set (i.e. the predicted classification of a given cell as a landscape type), ILP requires knowledge of the landscape characteristics of a significant number of cells, and the landscape type that they belong to. A cell that is associated with landscape metric values, and whose landscape type is known, therefore provides an example of a training set. It should be noted that a priori knowledge of landscape type classification can come from various sources; here it comes from a geographer's expertise. The learning process is launched for each individual landscape type. For a given landscape type, the cells belonging to that type are positive examples, and the remaining cells provide negative examples. The minimum accuracy of the rules is set at 0.7; it is established during the learning process using the ratio p/(p+n), where p and n correspond to the number of examples, respectively positive and negative, covered by the rule. This value is seen as a good compromise between the conflicting requirements of accuracy and of generalization of the rules induced. Finally, the maximum length of the premises of the rules is set at five literals because, in practice, this kind of value is considered to be the limit enabling correct reading of the results [START_REF] Michalski | Machine learning: An artificial Intelligence Approach, chap. a theory and methodology of inductive learning[END_REF].

Constructing the ontologies

An ontology can be used to model a specific area of knowledge in a formal, structured manner [START_REF] Gruber | A Translation Approach to Portable Ontology Specification[END_REF]. This modelling is based on the definition of concepts and relations between those concepts. One of the stated objectives is to enable knowledge sharing via a representation of an area of knowledge that is as consensual as possible. To define our ontologies, we use description logics, which are a language family able to represent a knowledge base for a given area. In description logics, two components make up the knowledge base: the terminological box (or TBox), which models the concepts, and the assertional box (or ABox), which represents instances. The description logics draw on first-order logic and result in inferential reasoning. These mechanisms are used to enrich the knowledge base by specifying new facts deduced from the original items through reasoning. We then chose to operationalize these formal ontologies in OWL2 (Web Ontology Language) [START_REF] Dean | OWL Web Ontology Language -Reference[END_REF], the language recommended by the W3C.

Landscape ontology.

Landscape ontology is the ontology of an area of knowledge, reflecting the geographer's expertise. It models concepts that depend on classification (landscape type and landscape component) in the form of a tree structure expressing the specialization of the concepts (the subsumption relationship) and all the properties linking or defining those concepts (the meronymy relationship and metrics). The model is then formalized using description logics. Let us take the deliberately simplified example of a "forest ecosystem" landscape type. This kind of landscape must contain the "forest" landscape component, but it may also include other component types. The landscape is also characterized by its low diversity and limited heterogeneity. In this example, we can see the concepts of landscape type and landscape component, each specialized by a sub-concept (here, forest ecosystem and forest, respectively). Here, we also need the properties "diversity" and "heterogeneity", defined as functional properties in the mathematical sense. More generally speaking, the landscape metrics defined in the ontology are all functional properties. In description logics, we will write:

Image ontology.

The image ontology is constructed to take into account various knowledge taken from the image, in connection with the landscape ontology. It is built as an application ontology, i.e. it is seen as a container for the cell descriptors obtained via the tasks run by the system. The concepts and relations in this ontology are obtained from preliminary processing and the calculation of the landscape characteristics. Most notably, it includes the key concept of 'cell'. The characteristics are assigned literal values. In section 4.3, we will see how this ontology is populated.

Application

Data

To illustrate the method, we have taken a Landsat 5 image acquired on 23 October 2009, covering part of Amazonia situated in the state of Pará, at the confluence of the Amazon and Río Tapajós. Five different types (LT1 to LT5) of landscape have been described and geolocated (Fig. 2). They are input into the example database used to generate rules via ILP. The aim is to search for these landscapes within the image (Fig. 3), applying the strategy set out here above.

Production of the land use map and grid.

There are different ways of producing land use maps [START_REF] Masse | Dveloppement et automatisation de mthodes de classification partir de sries temporelles d'images de tldtection -application aux changements d'occupation des sols et l'estimation du bilan carbone[END_REF]. We chose unsupervised classification (or clustering) using the k-means algorithm. The land use map ob-tained is made up of seven labelled classes (Fig. 4) over which we lay a grid of square cells that are then used to calculate the landscape characteristics (Fig. 5).

Production of the classification rules

To obtain the classification rules, we need to exploit the resulting characteristics, calculated on the basis of the cells used in the learning process. These cells are those contained in the five reference landscapes. The choice of metrics depends on the approach taken by the geographer. We establish in Table 1 the correspondences between the landscape metrics and the characteristics calculated in the satellite image:

Populating the image ontology

As we have seen above, the image ontology models the cells and the properties that correspond to landscape characteristics. Each of these properties is used to associate a cell with the value obtained from the calculation of a given characteristic. We thus obtain information calculated cell by cell, which then instantiates the ontology by populating the ABox. We can take the example of an individual from the cell class -identified by m59 -which, as a proportion of the forest, has a value of 0.287. In logical form, this is written as follows:

Cell Top Cell(m59) ≤ 1 f orest prop (functional property) f orest prop(m59,"0.287")
As such, all cells in the ontology are described by a set of attributes that correspond to the metric values calculated during preliminary processing. Each cell is georeferenced using latitude/longitude centroid coordinates, as well as its geometrical representation as a polygon. In GeoSPARQL3 , the polygon has a literal value expressed as geo:gmlLiteral. In addition, the classification rules specify the cell's landscape type: this information is added to the cell description. In the image ontology, we therefore have a very comprehensive range of information. We can also note that the structure of the ontology means we can add as many additional attributes as we like, for example texture or vegetation index.

Results and discussion

Results

Characteristics of the ruleset and performance.

Six grids were generated, made up of square cells with sides measuring from 32,640 m to 1,020 m (system of nested cells for a multi-resolution approach). The large grids (32,640 m, 16,320 m and 8,160 m) proved to be poorly suited to the surface area of the landscapes making up the learning base. Calculations were therefore made on the grids measuring 1,020, 2,040 and 4,080. The most useful results were obtained for the 1,020 and 2,040 grids, with little difference between them. Here we present the 2,040 grid. Respectively 1, 3, 1, 6 and 4 rules for landscape types LT1 to LT5 were induced for the full learning set made up of 300 cells with sides measuring 2,040 metres. Here is an example of the kind of rule obtained: landscape type(A,t p5) : -turbidWater prop(A, eq0), f orest prop(A, le0 009).

This rule means that a cell A belongs to LT5 if its proportion of turbid water is zero and its proportion of forest is below 0.009. While the rules induced are easy to read and intelligible, even for someone who is not expert in the learning method, the prediction results vary according to the landscape type considered. Table 2 shows sensitivity and specificity 4 , calculated using the full learning set and via crossed validation (average, minimum and maximum values). The accuracy of the predic- tion calculated using the full learning set comes to 94.7%. Stratified 10-fold crossvalidation resulted in an estimated 58.6% precision accuracy with a maximum (and a minimum) of 71.0% for the ten subsets (respectively 45.7%). The results obtained for sensitivity are particularly good, reaching 76.3% for landscape type 1 and exceeding 60% for types 3 and 5 (respectively 63.8 and 61.9%). Landscape type 2 is especially difficult to predict with a success rate of just 15%, which is mainly explained by the limited number of related examples [START_REF]GBIF: Global biodiversity informatics facility[END_REF], but also by less clear-cut identification and characterization by the expert (in his own view). Other tests were run to produce rules using ILP. The spatial adjacency relationship, where two cells are only adjacent if they share a side, was thus coded in the learning process knowledge base, along with the multi-resolution character (inclusion relationships from one cell to another). This final learning strategy, exploiting contiguity information and the multi-resolution character of the spatial information, appears particularly relevant: it corresponds to the way in which the expert geographer comprehends the territory, using different mapping products with varying geographic reach and resolution. However, the inclusion of spatial relations and multi-resolution to produce classification rules did not demonstrate any real improvement in results.

Figure 6 shows the landscapes that feed the learning base for ILP, and Figure 7 illustrates the prediction results for the complete study area. The prediction results, most of which fall outside the reference landscape zone, lead to consistent characterization of the territory, the relevance of which is confirmed a posteriori by the expert.

Ontology modules.

Two ontology modules were built. The landscape ontology that "captures" the geographer's work and thus represents the conceptual modelling of an area of knowledge. And the image ontology that contains all the information obtained from the satel- lite image and the ILP activity: georeferenced cells, landscape characteristic values and prediction results. The image ontology also extends the core ontology found in GeoSPARQL [START_REF] Battle | Enabling the geospatial semantic web with parliament and geosparql[END_REF], facilitating coverage of the cell geometry. Some links connecting the two ontological modules have already been explored. Initial work involved developing synergies between the geographer's expertise concerning a landscape type, as described in the landscape ontology, and the information on the cells classified by ILP as belonging to that landscape type. As such, we define adequate CON-STRUCT queries in SPARQL language [START_REF] Kostylev | Construct queries in sparql[END_REF], which produce new representations of the knowledge contained in the image ontology, making it more consistent with the content of the landscape ontology. Depending on the data searched, the information can be exploited in several ways. We can then look into what identifies the transition from one landscape to another by focusing on the boundary cells. The screen shot shown in Figure 8 shows the result of a CONSTRUCT query (LT1 type cells predominantly containing "forest" or "sparse forest" type landscape components (or patches) that we translate as cells in the forest ecosystem. These cells are shown in green in the study zone 5 . In the landscape ontology, the forest ecosystem is described as a landscape that is predominantly covered by forest, with little diversity. The different shades of green illustrate the diversity of the patches found in the cells. The forest component is omnipresent in the dark green cells. The light green cells show greater diversity with intermediate patches of water or vegetation. The cells with a richer range of landscape components are frequently found at the boundaries of the forest ecosystem landscape and diversity is therefore a good indicator of a change of landscape, at least where the forest ecosystem is concerned. The content of the two ontological modules can also be linked to open external data sources, also represented using Semantic Web standards. Hence, in Figure 8, the cells are viewed on an Openstreetmap background map [START_REF]OSM: Openstreetmap[END_REF]. The geographical entities defined in OSM may be exploited via their RDF6 representation [START_REF] Auer | Linkedgeodata: Adding a spatial dimension to the web of data[END_REF] to better clarify the contours of the landscapes. Likewise, the ecological data can also contribute to better comprehension of landscapes through their ecosystem aspects. As such, data that comes from the observation of occurrences of living species can also be integrated into landscape characterization. We provide the example of data on the study zone found on the GBIF portal [START_REF]GBIF: Global biodiversity informatics facility[END_REF].

Discussion

The first objective was to automate landscape identification in a satellite image as far as possible. The second objective was to express and persist all that knowledge via dedicated ontological modules so that it is interoperable and reusable in the context of the Semantic Web. These objectives were attained by combining different approaches, most notably associating ILP and ontologies. Furthermore, we have obtained data that has been greatly enriched compared to the image's initial content and restructured in Semantic Web format. As we have demonstrated, this restructuring opens up possibilities for the exploitation of the web of data. All these results thus validate our approach. The method now needs perfecting and we have a number of proposals in this respect, for example:

• refining landscape description (the geographer's work) to improve the learning base used by ILP to produce the rules; • in the process of obtaining classification rules, making the most of the topological relations and cell multi-resolution; • in ontological modelling, using adjacency relations between cells by making use of the GeoSPARQL model; • using other open data sources, for example GeoNames7 .

We have demonstrated all the potential of an approach that takes symbolic induction mechanisms to partially populate an applicative ontology. The usual data mining methods applied when processing an image, for example supervised classification, treat the input attributes as dimensions that are independent of one another. In this respect, ILP, which establishes dependencies between attributes, is better equipped to take advantage of the spatial organization of radiometric values within the cells seen as a set of connected pixels. Spatial analysis requires the processing of spatial entities according to their descriptors but also according to the descriptors of the adjacent entities and the relationships with those adjacent entities. We were thus able to extract the predicates involving several descriptors (for example, the proportion of each landscape component, diversity or fragmentation) to analyze landscape types as closely as possible. However, it now remains for us to enrich the ILP activities by including topological relationships, either within the same grid of cells or within nested cells. Likewise, we will continue to develop the cell and landscape ontologies. Most notably, the spatial relationships between cells will be described within the cell ontology and we also expect to work on new descriptors (such as texture). Finally, the links used to exploit the application ontology alongside the landscape ontology will be reinforced. The aim is to continue to develop conversion rules using SPARQL so that we are able to take a regularity on the cell ontology graph and extract a regularity from the landscape ontology graph, and vice versa. This bidirectional approach will enable us, on the one hand, to reconcile image data with the geographer's expertise and, on the other hand, potentially further the expert's knowledge according to the image's content.

Conclusion

We have presented a hybrid approach that draws on both expert knowledge formalized in ontological modules and new knowledge developed through symbolic learning. The goal is to work as closely as possible to the geography expert's reality while developing knowledge acquired via ILP. We have set out some encouraging initial results on the ability to automate the extraction of interesting patterns in a satellite image. We intend to enrich the ontological representation, especially in terms of metric description to develop the potential of reasoning mechanisms. The approach described in this paper can be improved upon as concerns the precision of the results, but it has helped us fulfil our objectives: achieving a shift towards automated landscape extraction from a satellite image while structuring, perpetuating, enriching and establishing interoperability of the knowledge and data exploited throughout the process, clearly tailoring it for the Semantic Web.

Fig. 1

 1 Fig. 1 Overall approach

Fig. 2

 2 Fig. 2 The 5 labelled landscapes. Fig. 3 Lansat Image 2009.

Fig. 4

 4 Fig. 4 Land use map.Fig.5Grid.

Fig. 6

 6 Fig. 6 Learning landscapes. Fig. 7 Prediction results.

Fig. 8

 8 Fig. 8 Forest ecosystem cells on an OSM background map

Table 1

 1 Equivalence between landscape metrics and characteristics in the image.

	Expert geographer	Characteristics calculated in the cells
	Composition	Proportion of each class present
	Diversity	Specific richness (no. of classes present)
	Heterogeneity	Shannon index H = -∑ N k=1 p k • ln(p k )
	Fragmentation: patch surface area	Average surface area of objects
	Shape	Perimeter/area: average measured

Table 2

 2 Predication results for the 2,040-metre resolution grid.

			TP1	TP2	TP3	TP4	TP5
	Full learning	Sensitivity	0,98	0,73	0,97	0,93	0,96
	set	Specificity	0,98	1,00	0,97	0,99	0,99
	Crossed validation average	Sensitivity	0,76 [0,40; 1,00] [0,00; 1,00] [0,33; 0,83] [0,30; 0,62] [0,25; 0,80] 0,15 0,64 0,46 0,62
	[min; max]	Specificity	0,92 [0,82; 1,00] [0,80; 1,00] [0,73; 0,89] [0,60; 0.90] [0,75; 0,94] 0,92 0,82 0,75 0,83

Environment for Visualizing Images, the software commercialized by EXELIS

GRASS GIS, GIS freeware from the GRASS Development Team

geospatial standard defined by OGC (Open Geospatial Consortium)

Sensitivity: capacity of the classifier to predict belonging to an LT class, given that the objects in question belong to that LT / Specificity: capacity of the classifier to predict non-belonging to an LT class, given that the objects in question do not belong to that LT.

Visualization makes use of the Javascript OpenLayers library

OSM data was previously collected in RDF format in the LinkedGeoData project

GeoNames : http://www.geonames.org/

Acknowledgements This work was achieved within the COCLICO project funded by the French National Research Agency (grant ANR-12-MONU-0001).


Sébastien Briot
email: sebastien.briot@ens.insa-rennes.fr

Vigen Arakelian
email: vigen.arakelyan@insa-rennes.fr

G C G M Ea3913

Optimal Force Generation in Parallel Manipulators for Passing through the Singular Positions

Keywords: parallel manipulators, singularity, dynamics, force management, trajectory planning

It is known that a parallel manipulator at a singular configuration can gain one or more degrees of freedom and become uncontrollable. That is it might not reproduce a stable motion along a prescribed trajectory. However, it is proved experimentally that there is possible passing through the singular zones. This was simulated and shown on numerical examples and illustrated on several parallel structures. In this paper, we determine the optimal dynamic conditions generating a stable motion inside the singular zones. The obtained results show that the general condition for passing through a singularity can be defined as follows: the end-effector of the parallel manipulator can pass through the singular positions without perturbation of motion if the wrench applied on the end-effector by the legs and external efforts of the manipulator are orthogonal to the twist along the direction of the uncontrollable motion. This condition is obtained from the inverse dynamics and analytically demonstrated by the study of the Lagrangian of a general parallel manipulator. Numerical simulations are carried out using the software ADAMS and validated by experimental tests.

Introduction

Parallel manipulators have experienced an increase in popularity in recent years due to their higher rate of acceleration, payload to weight ratio, stiffness and low effective inertia compared to those of serial manipulators. However they have some drawbacks, like a small workspace and special singular zones in it. Thus, in the presence of singular positions, the workspace of the parallel manipulators, which is less than that of serial manipulators, becomes even smaller and limits their functional performance. The studies of singularity have had different stages of development. The previous works on this problem is reported in a great number of publications and can be classified by different criteria. They can be arranged, by example, in three major groups, which are distinguished by historical evolution and are characterized by study of the singularity from kinematic, kinetostatic and dynamic points of view.

The physical interpretation of a singularity in kinematics refers to those configurations of parallel manipulators in which the number of degrees of freedom of the mechanical structure changes instantaneously, either the manipulator gains some additional, uncontrollable degrees of freedom or loses some degrees of freedom. In this case the singularity analysis can be carried out on the base of the properties of the Jacobian matrices of the mechanical structure (i.e. when the Jacobian matrices relating the input speeds and the output speeds become rank deficient [START_REF] Gosselin | Singularity analysis of closed-loop kinematic chains[END_REF][START_REF] Ma | Architecture singularities of parallel manipulators[END_REF][START_REF] Ottaviano | Singularity analysis of CaPaMan: a three-degree of freedom spatial parallel manipulator[END_REF][START_REF] Wen | Singularities in three-legged platform-type parallel mechanisms[END_REF]), by using Grassmann geometry [START_REF] Merlet | Singular configurations of parallel manipulators and Grassmann geometry[END_REF] or screw theory [START_REF] Bonev | Singularity analysis of 3-DOF planar parallel mechanisms via Screw Theory[END_REF][START_REF] Hunt | Special configurations of robot-arms via screw theory[END_REF]). However, it was observed that close to a singular configuration, a parallel manipulator loses its stiffness and its quality of motion transmission, and as a result, its payload capability. For this purpose, a kinetostatic approach has been applied for the evaluation of the quality of motion transmission in the singular zones of parallel manipulators. The quality of motion transmission of parallel manipulators was successfully studied in [START_REF] Kim | Forward/inverse force transmission capability analyses of fully parallel manipulators[END_REF][START_REF] Kim | Force transmission analyses with dimensionally homogeneous jacobian matrices for parallel manipulators[END_REF][START_REF] Lee | Workspace and force-moment transmission of a variable arm type parallel manipulator[END_REF][START_REF] Weiwei | Study on force transmission performance for planar parallel manipulator[END_REF]. The quality of motion of manipulators with three degrees of freedom has been evaluated by means of a kinetostatic indicator, which is similar to the pressure angle [START_REF] Alba-Gomez | Consistent kinetostatic indices for planar 3-DOF parallel manipulators, application to the optimal kinematic inversion[END_REF]. In [START_REF] Arakelian | Increase of singularity-free zones in the workspace of parallel manipulators using mechanisms of variable structure[END_REF], the pressure angle was used as an indicator of the quality of motion transmission and the nature of the inaccessibility of singular zones by parallel manipulators are shown.

The further study of singularity in parallel manipulators has revealed an interesting problem that concerns the path planning of parallel manipulators under the presence of singular positions, i.e. the motion feasibility in the neighborhood of singularities. In this case the dynamic conditions can be considered in the design process. One of the most evident solutions for the stable motion generation in the neighborhood of singularities is to use redundant sensors and actuators [START_REF] Alvan | On the control of the spatial parallel manipulators with several degrees of freedom[END_REF][START_REF] Collins | The singularity analysis of an parallel hand controller for force-reflected teleoperation[END_REF]Dasgupta and Mruthyunjaya 1998a;[START_REF] Glazunov | Parallel manipulator control while intersecting singular zones[END_REF]). However, it is an expensive solution to the problem because of the additional actuators and the complicated control of the manipulator caused by actuation redundancy. Another approach concerns with motion planning to pass through singularity [START_REF] Bhattacharya | Comparison of an exact and approximate methode of singularity avoidance in platform type parallel manipulators[END_REF]Dasgupta and Mruthyunjaya 1998b;[START_REF] Hesselbach | Aspects on the design of high precision parallel robots[END_REF][START_REF] Kemal Ider | Inverse dynamics of parallel manipulators in the presence of drive singularities[END_REF][START_REF] Jui | Path tracking of parallel manipulators in the presence of force singularity[END_REF][START_REF] Nenchev | Dynamic analysis of parallel manipulators under the singularity-consistent parameterization[END_REF][START_REF] Perng | Inverse kinematic solutions for a fully parallel robot with singularity robustness[END_REF], i.e. a parallel manipulator may track a path through singular poses if its velocity and acceleration are properly constrained. This is a promising way for the solution of this problem. However only a few research papers on this approach have addressed the path planning for obtaining a good tracking performance but they have not adequately addressed the physical interpretation of dynamic aspects.

In this paper the dynamic condition for passing through the singular positions is defined in general. It allows the stable motion generation inside in the presence of singularity by means of the optimum force control. The disclosed condition can be formulated as follows: «In the presence of a type 2 singularity, the platform of the parallel manipulator can pass through the singular positions without perturbation of motion if the wrench applied on the platform by the legs and external forces is orthogonal to the direction of uncontrollable motion». In other terms, the condition is that the work of applied forces and moments on the platform along the uncontrollable motion is equal to zero. This condition is obtained from the inverse dynamics and analytically demonstrated by the study of the Lagrangian of a general parallel manipulator. The obtained results are illustrated by numerical simulations and validated by experimental tests.

The paper is organized as follows. The next section presents theoretical aspects of the examined problem. Based on the Lagrangian formulation, the condition of force distribution is defined, that allows the passing of any parallel manipulator through the type 2 singular positions.

In Section 3, two applications illustrate the obtained theoretical results. In section 4, the numerical simulations carried out using the software ADAMS are validated by experimental tests.

Optimal dynamic conditions for passing through type 2 singularity

Let us consider a parallel manipulator of m links, n degrees of freedom and driven by n actuators.

The Lagrangian dynamic formulation for a parallel manipulator can be expressed as:

λ B q q T L L                 dt d  , (1)
where, -  is the vector of the input efforts;

-L is the Lagrangian of the manipulator;

- T n q q q ] ,..., , [ 2 1  q and T n q q q ] ,..., , [ 2 1      q
represent the vector of active joints variables and the active joints velocities, respectively;

- T z y x ] , , , , , [     x and T z y x ] , , , , , [           v
are trajectory parameters and their derivatives, respectively; x, y, z represent the position of the controlled point and  and  the rotation of the platform about three axes a   a  and a  ;

-  is the Lagrange multipliers vector, which is related to the wrench applied on the platform by:

p W A T    (2)
where,

- A and B are two matrices relating the vectors v and q  according to q B Av  

. They can be found by the closure equations with respect to time.

- W p is the wrench applied on the platform by the legs and external forces [START_REF] Khalil | A novel solution for the dynamic modeling of Gough-Stewart manipulators[END_REF], which is defined as:

                           p p p n f x v W L L dt d . ( 3
)
where f p is the force along the directions of the global frame and n p is the torque about the axes

a   a  and a  
The term W p can be rewritten in the base frame using a transformation matrix D [START_REF] Merlet | Parallel Robots[END_REF]):

) ( 0 p R p W D W  (4) with p R W 0
is the expression of the wrench W p in the base frame, and

           3 3 3 3 3 3 3 3 R 0 0 I D (5)
where I 33 , 0 33 and R 33 are respectively the identity matrix, the zero matrix and the transformation matrix between axes a   a  and a  and the base frame, whose dimensions are 33.

By substituting ( 5) into (1), one can obtain:

p R b W J W 0 T    , q q W b               L L  dt d ( 6
)
where

  B A J R 1 0  
is the Jacobian matrix between twist t of the platform (expressed in the base frame) and q  , D A A R  0 is the expression of matrix A in the base frame.

For any prescribed trajectory x(t), the values of vectors q   , q  and q can be found using the inverse kinematics. Thus, taking into account that the manipulator is not in a type 1 singularity [START_REF] Gosselin | Singularity analysis of closed-loop kinematic chains[END_REF], the terms W b and p R W 0 can be computed. However, for a trajectory passing through a type 2 singularity, the determinant of matrix J tends to infinity.

Numerically, the values of the efforts applied by the actuators become infinite. In practice, the manipulator either is locked in such a position of the end-effector or it generates an uncontrolled motion. That is the end-effector of the manipulator could produce a motion, different to the prescribed trajectory.

It is known that a type 2 singularity appears when the determinant of matrix A R 0 vanishes, in other words, when at least two of its columns are linearly dependant [START_REF] Merlet | Parallel Robots[END_REF].

Let us rewrite the matrix A R 0 as:

             66
where  j are the coefficients, which in general can be functions of q p (p = 1, …, n). It should be noted that the vector t s =    2 , …,  6 ] T represents the direction of the uncontrollable motion of the platform in a type 2 singularity.

Rewriting (8) in a vector form, we obtain:

   6 1 j j j 0 N  , N j = [a 1j , a 2j , …, a 6j ] T , j = 1, …, 6 (9)
where N j represents the j-th column of matrix

A R 0 .
By substituting (9) into (2), we obtain

j T j W  λ N , j = 1, …, 6 (10)
where W j is the j-th row of vector p R W 0 .

Then, from ( 9) and (10) the following conditions are derived:

          6 1 6 1 0 j j j j T j j W   λ N (11)
The right term of eq.( 11) corresponds to the scalar product of vectors t s and Otherwise, the dynamic model is not consistent. Obviously, in the presence of a type 2 singularity, the displacement of the end-effector of the manipulator has to be planned to satisfy (11).

Let us illustrate the considered problem by examples.

Illustrative examples

In this section, two examples are chosen to illustrate the obtained theoretical results discussed above. The first example presents a planar 5R parallel manipulator, which allows obtaining relatively simple mathematical models for demonstrating the expected results by numerical simulations. The second example presents a parallel manipulator which was developed in the I.N.S.A. of Rennes. This example was chosen for validation of numerical simulations carried out by the software ADAMS on the built prototype.

Example 1: Planar 5R parallel manipulator

In the planar 5R parallel manipulator, as shown in Fig. 1, the output point is connected to the base by two legs, each of which consists of three revolute joints and two links. In each of the two legs, the revolute joint connected to the base is actuated. Thus, such a manipulator is able to position its output point in a plane. As shown in Fig. 1, the actuated joints are denoted as A and E with input parameters q 1 and q 2 . The common joint of the two legs is denoted as C, which is also the output point with controlled parameters x and y. A fixed global reference system xOy is located at the center of AE with the yaxis normal to AE and the x-axis directed along AE. The lengths of the links AB, BC, CD, DE are respectively denoted as L 1 , L 2 , L 3 and L 4 . The positions of the centers of masses S i of links from joint centers A, B, D and E are respectively denoted by dimensionless lengths r 1 , r 2 , r 3 and r 4 , i.e. .

The singularity analysis of this manipulator [START_REF] Liu | Kinematics, singularity and workspace of planar 5R symmetrical parallel mechanism[END_REF] shows that the Type 2 singularities appear when legs 2 and 3 are parallel (Fig. 2).

In both cases, the gained degree of freedom is an infinitesimal translation perpendicular to the legs 2 and 3. However, if L 2 = L 3 , the gained degree of freedom in case (b) becomes a finite rotary motion about point B.

In order to simplify the analytic expressions, we consider that the gravity effects are along the z-axis and consequently the input torques are only due to inertia effects. To simplify the computation, it is also preferable to replace the masses of moving links by concentrated masses [START_REF] Seyferth | Massenersatz duch punktmassen in räumlichen getrieben[END_REF][START_REF] Wu | On the dynamic balancing of multi-DOF parallel mechanisms with multiple legs[END_REF]. For a link i with mass m i and its axial moment of inertia I i , we have:

                                 i i i i i i i i i i i I m m m m L r L r r r 0 ) 1 ( 0 1 0 1 1 1 3 2 1 2 2 2 2 , (i = 1, 2, 3, 4) (12)
where m ij (j = 1, 2, 3) are the values of the three point masses placed at the centers of the revolute joints and at the center of masses of the link i.

In this case, the kinetic energy T can be written as:

) ( 2 1 2 2 2 2 4 4 2 3 3 2 2 2 2 1 1 D D C C B B S S S S S S S S m m m D  
. The terms m ij (i = 1, 2, 3, 4) are deduced from the relation ( 12), V Si is the vector of the linear velocities of the center of masses S i ; V B , V C and V D are the vectors of the linear velocities of the corresponding axes.

The input torques can be obtained from (6):

p b W J W T R 5    (14)
taking into account that for examined manipulator:

D D B B b F J F J W T T   , (15)
where,

       0 cos 0 sin 1 1 1 1 q L q L B J ,         2 4 2 4 cos 0 sin 0 q L q L D J , ( 16
) C B B F   1 1 C B m m   , C D D F   3 2 C D m m   , ( 17
)                       1 1 2 1 1 1 1 1 sin cos cos sin q q q q q q L    B  ,                       2 2 2 2 2 2 2 4 sin cos cos sin q q q q q q L    D  ,        y x     C  (18) 2 2 2 2 1 1 1 ) 1 ( r m m r m m S B S B     , ) 1 ( 2 2 2 1 r r m m S C   , ( 19
) ) 1 ( 3 3 3 3 r r m m S C   , 2 3 3 2 4 4 2 ) 1 ( r m m r m m S D S D     . ( 20
)
The term W p is given by:

D C B p W    3 2 1 C C C m m m    , ( 21
) 2 3 3 2 2 2 2 r m m r m m S C S C    . ( 22
)
and the Jacobian matrix J 5R by:

R R R 5 1 5 5 B A J   , (23)
where,

                    2 4 2 4 1 1 1 1 22 21 12 11 5 sin cos sin cos 2 q L y a q L x q L y a q L x a a a a R A , (24)
          ) cos sin ( 0 0 ) cos sin ( 2 22 2 21 4 1 12 1 11 1 5 q a q a L q a q a L R B . ( 25
)
and we determine t s in according with (8):

T ] cos , sin [ 1 1     s t (26)
Thus, the examined manipulator can pass through the given singular positions if the wrench W p determined by ( 21) is orthogonal to the direction of the uncontrollable motion t s described by ( 26).

Let us now consider the motion planning, which makes it possible to satisfy this condition.

For this purpose the following parameters of manipulator's links are specified: With regard to the prescribed trajectory generation, the point C should reproduce a motion along a straight line between the initial position C 0 (x 0 , y 0 ) = C 0 (0.1, 0.345) and the final point

L 1 = L 2 = L 3 = L 4 = 0.25 m; r 1 = r 2 = r 3 = r 4 = 0.5; a = 0.2 m; m 1 = m 4 =
C f (x f , y f ) = C f (-0.1, 0.145) in t f = 2 s.
Thus, the given trajectory can be expressed as follows:

                  ) ( ) ( ) ( ) ( ) ( ) ( 0 0 0 0 y y t s y x x t s x t y t x f f x (27)
However, the manipulator will pass by a type 2 singular position at point C s (x s , y s ) = C s (0, 0.245) (Fig. 3).

Developing the condition for passing through the singular position (11) for the planar 5R parallel manipulator at point C s , we obtain:

0 6 3 ) 48 248 ( 2 2 2 1 1    y m y x L m C C     (28)
Then, taking into account that the velocity and the acceleration of the end-effector in initial and final positions are equal to zero, the following nine boundary conditions are found: From ( 28) -( 37), the following eighth order polynomial trajectory planning is found:

s (t 0 ) = 0, ( 29
)
s (t f ) = 1, ( 30
)
s (t s = 1 s) = 0.5, (31) 0 ) ( 0  t s  , (32) 0 ) (  f t s  , (33) 1 ) /( ) /( ) ( 0 0      x x x y y y t s f s f s s    , ( 34
) 0 ) ( 0 0   s t s     . (35) 0 ) (   f f s t s     . ( 36
) ) 6 ) ( 3 /( ) 48 248 ( ) ( 2 0 2 2 1 1 C f s s C s s m x x y x L m s t s            . ( 37
  8 7 6 5 4 3 12606 . 0 07101 . 1 58909 . 3 72792 . 5 84228 . 3 25851 . 0 t t t t t t t s        (38)
Thus the generation of the motion by the obtained eighth order polynomial makes it possible to pass through the singularity without perturbation and the input torques remain in the limits of finite values, which are validated by numerical simulations carried out by the ADAMS software (Fig. 4).

Thus, we can assert that the obtained optimal dynamic conditions assume the passing of the manipulator's end-effector through the singular position. Now, we would like to show that, in the case of the generation of the motion by any trajectory planning without meeting the adopted boundary conditions, the end-effector is not able to pass through the singular position. For this purpose the generation of motion between initial and final positions, let us generate by a fifth order polynomial trajectory planning:

  5 4 3 1875 . 0 9375 . 0 25 . 1 t t t t s    (39)
The obtained numerical simulations carried out by the software ADAMS are given in Fig. 5.

We can see that, when the manipulator is close to the singular configuration (for t s = 1 s), the values of the input torques tend to infinity.

Example 2: PAMINSA (Parallel Manipulator of the I.N.S.A.)

The second example presents a parallel manipulator, which was invented and developed at the I.N.S.A of Rennes (Arakelian et al. 2006). The particularity of this architecture is in decoupling of the displacements of the platform in the horizontal plane from the translations along the vertical axis. The advantages of such an approach was disclosed in [START_REF] Arakelian | Design and prototyping of new 4-, 5-and 6-DOF parallel manipulators based on the copying properties of the pantograph linkage[END_REF]Briot et al. 2007b) and the singularity analysis is discussed in (Briot et al. 2007a;Briot and Arakelian 2007;[START_REF] Arakelian | Singular positions of a PAMINSA parallel manipulator[END_REF].

The previous studies have revealed that there are type 2 singularities in the workspace of the symmetrical architecture of PAMINSA. Let us illustrate the proposed approach for the PAMINSA with 4 degrees of freedom (Fig. 6).

Each leg of this manipulator is realized by a pantograph mechanism (Fig. 7) with two input points 3 i and 8 i , and an output point 5 i (i = 1, 2, 3). Each input point 8 i is connected to the rotating drive M i by means of a prismatic guide mounted on a rotating link. This kind of architecture allows for generation of motion in the horizontal plane by the use of rotating actuators M 1 , M 2 , M 3 , and the vertical translations by means of the linear actuator M v . Thus, the displacements (x, y, ) of the platform in the horizontal plane xOy, that are translations along the x and y-axes and rotations about the z-axis, are independent of vertical translations z. This implies that the kinematic models controlling the displacement of the manipulator can be divided into two parts:

-a model for the displacements in the horizontal plane, which is equivalent to a 3-RPR manipulator;

-a model for the translations along the vertical axis equivalent to the model for the vertical translations of a pantograph linkage.

The type 2 singularities of such a manipulator appear when [START_REF] Arakelian | Singular positions of a PAMINSA parallel manipulator[END_REF]Briot et al. 2007a):

a) the three legs of the manipulators are parallel, which is impossible for the developed PAMINSA manipulator.

b) the orientation of the platform is equal to

) / ( cos 1 b pl R R 
, where R pl and R b correspond respectively to the lengths PC i and OM' i (Fig. 8). In this case, the manipulator gains one infinitesimal rotation around one vertical axis. c) the platform is located in a circle defined by

 cos 2 2 2 2 2 b pl b pl R R R R y x     (40)
In this case, the manipulator gains one finite rotation about one vertical axis (Cardanic self motion) (Briot et al. 2007a). For both cases (b) and (c), the direction of the unconstrained motion can be represented by the twist t s = [0, 0, 1, x W , y W , 0] T , where x W and y W corresponds to the planar coordinates of the intersection point of the wrenches R i applied on the platform by the three legs of the manipulator (Fig. 8).

Let us now study the inverse dynamics of the PAMINSA. The potential energy V can be written as:

    3 1 i leg pl i V V V ( 41
)
where V pl is the potential energy of the platform and i leg V is the potential energy of the leg i (i = 1, 2, 3).

By further considering that the coordinates of the all points of the pantograph linkages can be found as a linear combination of the coordinates of points 3 i , 5 i and 9 i , one can express the terms V pl and i leg V as follows:

z g m V pl pl  (42) 4 3 9 2 5 1 v v v i v i v leg C q C z C z C V i     (43)
Here, C vj (j = 1, 2, 3) are constant terms whose dimension is equivalent to a mass multiplied by the gravitational acceleration g, m pl is the mass of the platform with a payload, and z 5i and z 9i are the altitude of joints 5 i and 9 i . The expressions of the coordinates of joints 5 i and 9 i are given in appendix A. The expressions for C vj (j = 1, …, 4) are given in appendix B.

We consider that the links are perfect tubes. Therefore the tensor of inertia I j of the link B ji at the center of masses will be written as:

           ) ( ) ( ) ( 0 0 0 0 0 0 j ZZ j YY j XX j I I I I , with ) ( ) ( j ZZ j YY I I  (44)
Thus, the kinetic energy T of the manipulator can be represented as:

    3 1 i leg pl i T T T , ( 45
)
where T pl is the kinetic energy of the platform, T legi is the kinetic energy of the leg i, as:

  2 2 2 2 ) ( 2 1      pl pl pl I z y x m T     ( 46
)
where I pl is the axial moment of inertia of the platform about the vertical axis.

) ( ) ( ) ( i c v i c v c i i c i i i i c i i i c i c i i c trans q C q z C q C z z C y y x x C z y x C z C y x C T i                             (48) i rot
T is the kinetic energy of the rotating links.

Note that there are two types of rotations (see, Fig. 7):

-rotation due to the actuators M i (i = 1, 2, 3) (angle q i ), which is about the vertical axis, -rotations due to the displacement of the pantograph in the linkage plane (angles  i and  i denoted as the angles between the direction of the passive slider and the links B 4i and B 3i respectively).

Thus, the kinetic energy of the rotating links can be written as:

) cos sin cos sin ( 2 11 2 12 2 9 2 10 13 2 2 10 2 9 i c i c i c i c c i i c i c rot C C C C C q C C T i                 (49)
The expressions for C cj (j = 1, …, 13) are given in appendix C. The input torques can be obtained from (6):

p b W J W T PAM    ( 50
)
where the terms J PAM , W b and W p are presented in appendix D.

The following parameters of manipulator's links are specified for the trajectory generation:

the radii of the circles circumscribed to the base and platform triangles are respectively equal to R b = 0.35 m and R pl = 0.1 m;

magnification factor of the pantograph: k = 3;

gravitational acceleration g is equal to 9.81 m/s 2 .

- terms of the inertia matrices of the links of the pantograph linkages: The point P is desired to make a motion x(t) along a straight line between points P 0 (x 0, y 0 ) = P 0 (0, 0) and point P f (x f , y f ) = P f (0.3, 0) in t f = 2.4 s. However, the manipulator will pass through a type 2 singular position at point P s (x s , y s ) = (0.25, 0) (Fig. 9). In order to carry out a comparative analysis for the optimized and not optimized dynamic conditions for passing through type 2 singularity, it has been considered two cases. The first is such a movement on the given trajectory, which is calculated from condition (11), and the second is an arbitrary motion.

At first let us consider an optimized trajectory which allows satisfying the condition (11), i.e.

the force W p should be perpendicular to the to the twist t s [0, 0, 1, 0, 0.1, 0] T defining the direction of the unconstrained motion. Developing the expression (11) for the PAMINSA at point P s , we obtain:

z y z x y x z y x z y x z y x                        
                    (51)
Now considering that the end-effector of the manipulator moves along a straight line directed along the x-axis, we can note that )

( s t y  = ) ( s t z  = ) ( s t y  = ) ( s t z  = ) ( s t   = ) ( s t    = 0
. Thus, the relationships, which satisfy the passing through of the singular positions, taking into account that the velocity and the acceleration of the platform in the initial and final positions are equal to zero, can be expressed by the following boundary conditions:

x(t 0 ) = x 0 , (52)

x(t f ) = x f , ( 53
)
x(t s = 2s) = x s , (54) 0 ) ( 0  t x  , ( 55
) 0 ) (  f t x  , ( 56
) 0 ) ( 0  t x  , ( 57
) 0 ) (  f t x  , ( 58
) 05 . 0 ) (   s s x t x   m/s, (59) 1
.32583 ) (    s s x t x     m/s². (60)
In this case, a motion for passing of the platform through the singular position can be found from the following eighth order polynomial form:

  However, a trajectory obtained by ( 61) cannot be reproduced by the prototype because of the capability of drivers' deceleration. Therefore, the trajectory was divided into two parts, i.e., the first sixth order polynomial trajectory assumes the motion from an initial to the singular position (P 0 P s ) and the second sixth order polynomial trajectory from singular to the final position (P s P f ). The core of the problem is same but it allows for generating motions for the prototype.

Thus, the trajectory planning equations can be written as: Thus, the motion obtained from the following sixth order polynomial equations (65) allows for passing through the singularity without perturbation, and the input efforts take on finite values (Fig. 10).

     6 6 5 5 4 4 3 3 0 0 t b t b t b t b x x x t x s       for t  t s ; (62)     ) ) ( ) ( ) ( ) ( ) ( ( 6 6 5 5 4 4 2 2 1 s s s s s s f s t t c t t c t t c t t c t t c x x x t x             for t > t s . ( 63
It can be seen that the input torques remain in the limits of finite values, but, by the end of the motion there is an increase of the input efforts, caused by a quick deceleration to stop the manipulator before it reaches the workspace boundary. It will be shown further that in the case of the motion generated by any trajectory planning without meeting the adopted boundary conditions ( 52) -( 60), the manipulator platform is not able to pass through the singular position.

For this purpose, the generation of motion between initial and final positions is carried out by a fifth order polynomial trajectory planning.

In this case, for  

m 0  t y ,   m 45 . 0   t z and   0  t 
, the fifth order polynomial trajectory planning is the following:

  5 4 3 023 . 0 137 . 0 217 . 0 t t t t x    (66)
The obtained input efforts computed by the software ADAMS are represented in Fig. 11.

It can be noted that, while the manipulator passes through the singular configuration (for t s ≈ 1.8 s), the value of the input torques tend to infinity.

Let us now validate the obtained results by experimental tests.

Experimental validation of obtained results

For validating the results of the previous section, we have carried out experimental tests on the prototype of the PAMINSA developed in the I.N.S.A. of Rennes (Fig. 12). At first, we have applied an arbitrary fifth order control law and observed the reproduction of motion during the displacement of the platform. The obtained trajectory is shown in Fig. 13 (dotted line).

The different positions are classified by time. For positions from (a) to (d), the platform moves towards the singular zone but yet it is outside of it. In this case, the reproduction of the real trajectory is similar to the desirable. At position (e), the manipulator enters the singular zone, which is close to the circle of the theoretical singular loci, and starts an uncontrollable motion.

Thus, since the motion generation is carried out by non optimized dynamic parameters, the platform moves along an unplanned trajectory (see positions (e) -(h) in Fig. 13).

Next, we have implemented the sixth order control laws as it was shown in the previous section and observed the behavior of the platform during the displacement (Fig. 14). The different positions are classified by time. During all these displacements, the manipulator retains its orientation and passes through the singular configuration without any perturbation.

Thus, we can note that the obtained optimum dynamic conditions allow the passing of the manipulator through the singular position.

Conclusion

At a singular configuration, a manipulator can gain one or more degrees of freedom, and at such a configuration it may becomes uncontrollable, i.e. it may not reproduce stable motion with prescribed trajectory. Nevertheless it is approved that there are several motion planning techniques, which allow passing through these singular zones. These approaches are simulated by numerical examples and illustrated on several parallel structures. It is a promising tendency for the solution of this problem. However, the attention was focused only on control aspects of this problem and very little attention has been paid to the dynamic interpretation, which is a crucial factor for governing the behavior of parallel manipulators at the singular zones.

In this paper we have found the optimal dynamic conditions, for making the pass through the type 2 singular configurations possible. The general definition of the condition for passing through the singular position is formulated as follows: in the presence of type 2 singular configuration, the platform of a parallel manipulator can pass through the singular positions without perturbation of motion if the wrench applied on the platform by the legs and external efforts are orthogonal to the direction of the uncontrollable motion, or in other words, if the work of applied forces and moments on the platform along the uncontrollable motion is equal to zero.

This condition has been verified by numerical simulations carried out with the software ADAMS and validated by experimental tests on the prototype of four degrees of freedom parallel manipulator PAMINSA.

It should be noted that the formulated general conditions ensure any given trajectory generation in the manipulator workspace. We would like to point out that the trajectory is not imposed and only the conditions of force generation must be satisfied.

Thus, the passing of any parallel manipulator through the singular positions by the proposed technique is carried out by optimal generation of inertia forces. Hence, it is impossible to stop the manipulator in the singular locus and to start again from fixed position.

We would like to mention that we studied the optimal redistribution of forces only in singular positions of the manipulator but it should be noted that there are zones close to these positions, in which the manipulator loses the quality of motion. For more reliable generation of motion, it is desirable to ensure the given condition of force generation not only in the singular positions of the manipulator but also in the zones near to these positions. It should be also mentioned that a future development of our work is the study of the difficulties of controlling parallel robots in the neighbourhood of singular configurations.

Finally, it should be noted that for the case of non controllable external forces applied on the platform the proposed technique cannot be used. Therefore, the most prominent field of the industrial application is a "fast pick and place" manipulation, when the generation of motion is determined by input, gravitational and inertia forces.

APPENDIX A

Coordinates of points 3 i , 5 i and 9 i (i = 1, 2, 3):

                     k z R R z y x i i b i b i i i / sin cos 5 3 3 3   ,                                   c i pl i pl i i i L R
F B A X i   9 , ) 2 /( ) ( E K D F    , C E D K 4 2   , ) 1 ( 2    B E , ) ( 2 8 A X B D i   , 2 8 2 8 2 3 2 A X A X L C i i B     , ) /( 8 5 i i X k z B  , ) 2 /( ) ( 8 2 5 2 8 2 5 2 3 2 4 i i i i B B X k z X X L L A      , ) 1 /( 5 8    k X X i i , 2 3 5 2 3 5 5 ) ( ) ( i i i i i y y x x X    
.

APPENDIX B

Expressions of terms C vj (j = 1, …, 4): x y q z q z q q q z q z q q q z q z q q , for j = 3, 4, 7, 8

                                           7 , 4 , 3 , 2 7 , 1 3 2 4 5 1 2 2 j j j Bj Bj B j v k m k m m k m m g C ,                 2 2 ) 2 ( ) 1 ( 8 4 7 3 9 7 4 2 B B B B v m m k m m k k m k m m k g C , 2 1 3 B v m g C  ,          2 2 1 2 2 4 B B B v m m m L g C . APPENDIX C Expressions of terms C cj (j = 1, …, 13):                        2 8 2 2 7 4 2 2 3 2 8 2 7 5 2 4 1 )) 1 ( 2 ( )) 1 ( 2 ( ) 1 ( 4 )) 1 ( 2 ( ) 2 ( ) 1 ( )) 1 ( ( 2 1 k m k k k m m k k k m k m k k m m k m C B B B B c                                            4 4 2 1 4 3 2 2 7 , 1 2 5 7 , 4 , 3 , 2 2 2 B j Bj j Bj j j c m k m k m m k m C                  4 4 4 4 ) 2 ( ) 1 ( 2 1 8 2 7 4 2 2 3 9 2 7 2 4 2 3 B B B B c m k m m k k m m k m k m k C                      ) 1 ( 2 ) 1 ( 2 ) 1 ( 2 ) 1 ( 2 ) 2 ( ) 1 ( ) 1 ( 2 2 1 8 2 7 4 2 2 3 2 7 2 4 4 k m k k k m m k k k m k k m k m k C B B B B c                2 2 ) 2 ( 2 ) ) 1 (( 4 2 1 4 2 3 7 7 4 5 B B B c m k k m m m m k C 8 1 6 B c m C  , k m C B c
3 3 2 1 1 d PC d PC d PC A ,                      k k k 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 2 1    B with 2 3 5 2 3 5 ) ( ) ( i i i i i y y x x      ,     T i i i T PCi PCi PCi z z y y x x z y x      5 5 5 , , , , i PC and   T i i i q q 0 sin cos  d (for i = 1, 2, 3).
i S T i S i S T i S i S T i S i S T i S i S T i S i S T i S i i T i i T i i T i i T i i T i F J F J F J F J F J F J F J F J F J F J F J W Q Q Q Q Q Q Q Q Q Q Q b              ) ( 7 7 8 8 3 3 4 4 7 7 3 1 4 4 9 9 5 5 8 8 i S T i S i S T i S i S T i S i S T i S i T i i i T i i T i i T i i T i F J F J F J F J F J F J F J F J F J F W X X X X X X X X X P p             with                                      1 3 3 3 3 3 1 3 3 3 3 3 X 0 0 0 0 J  T i i i T T i i i i z y x z y x z y x ] , , [ ] , , [ ] , , [ 5 5 5 5 5 5 5 , i i k 5 8 1 0 0 1 1 1 X 4 4 1 4 1 4 4 1 4 1 X J 0 0 0 0 0 J                  ,                 1 3 3 3 3 1 1 2 3 2 Q 0 0 0 0 0 J 1 3i , i i 3 2 Q Q J J  , T T B i qi i T B i qi i T B i qi i i L L L                                                                            3 1 3 1 1 2 P 3 1 1 2 P 3 1 1 2 P 3 1 Q 0 0 0 Rot R 0 0 Rot R 0 0 Rot R 0 J 3 3 3 2 3 1 9 ) , ( ) , ( ) , ( y y y       ,               0 0 0 0 sin cos 0 cos sin i i i i qi q q q q P R , i i i B i i i L q 8 3 ε 9 ) , ( X X 1 3 1 3 1 3 1 2 P X J J 0 0 0 0 R Rot J                         z ,               i i i i i     sin 0 cos 0 0 0 cos 0 sin ε P R ,                       i i i B i B i B i B i i k k L L L L 5 1 4 3 4 3 1 1 cos cos sin sin X 3 1 2 1 X X J 0 0 J J        ,                      i i i i i z y x 0 0 X J , i T T B i qi i T B i qi i T B i qi i i k L k L k L 9 4 3 4 2 4 1 4 / ) , ( / ) , ( / ) , ( Q 3 1 3 1 1 2 P 3 1 1 2 P 3 1 1 2 P 3 1 Q J 0 0 0 Rot R 0 0 Rot R 0 0 Rot R 0 J                                                                             y y y       , i i i B i i i k L q 9 4 4 / ) , ( X X 1 3 1 3 1 2 P 1 3 X J J 0 0 0 R Rot 0 J                          z ,               i i i i i      sin 0 cos 0 0 0 cos 0 sin P R , T T B i qi i T B i qi i T B i qi i i k L k L k L                                                                            3 1 3 1 1 2 P 3 1 1 2 P 3 1 1 2 P 3 1 Q 0 0 0 Rot R 0 0 Rot R 0 0 Rot R 0 J / ) , ( / ) , ( / ) , ( 4 3 4 2 4 1 7 y y y       , i i i B i i i k L q 8 4 7 / ) , ( X X 1 3 1 3 1 2 P 1 3 X J J 0 0 0 R Rot 0 J                          z ,              i i i i S 1 Q 4 3 Q Q Q J 0 J J J 9 5 4 5 . 0 ,             0 3 2 1 i i i i    1 2 1 2 1 2 1 2 1 Q 0 0 0 0 J ,             i i i i S 1 Ω 9 5 4 5 . 0 X 6 3 X X X J 0 J J J , i i i i i q q   X 1 X J J              0 0 cos 0 sin 0 ,              i i i i S 2 7 4 3 5 . 0 Q 4 3 Q Q Q J 0 J J J ,             0 3 2 1 2 i i i i    1 2 1 2 1 2 1 2 Q 0 0 0 0 J ,             i i i i S 2 Ω 7 4 3 5 . 0 X 6 3 X X X J 0 J J J , i i i i i q q  
        Bji T i i Bj i i Bji T i i i qi Bj i i Bji T i i Bj i i i qi Sji q q q q q q    with  i =  i if j = 4, 7,  i =  i if j = 3, 8 and   T i i i i i Bji q q q    cos sin     Ω .
In these expressions,  ij represents the Krönecker symbol ( ij = 1 if j = i and  ij = 0 if j  i).

FIGURE CAPTIONS

Fig. 1 .

 1 Fig. 1. Kinematic chain of the planar 5R parallel manipulator.

  Fig. 2. Second kind of singularities of the planar 5R parallel manipulator.

  Fig. 3. Initial, singular and final positions of the planar 5R parallel manipulator.

  Fig. 4. Input torques of the planar 5R parallel manipulator in the case of the eight order

Fig. 6 .

 6 Fig. 6. PAMINSA with 4 DOF.

Fig. 7 .

 7 Fig. 7. Kinematic chain of each leg.

Fig. 8 .

 8 Fig. 8. Example of Type 2 singular configuration

  lengths of the links of the pantograph linkages: L B1 = 0.308 m, L B2 = 0.442 m, L B3 = L B8 = 0.42 m, L B4 =k L B7 = 0.63 m, L B5 = 0.0275 m, L B10 = 0.3635 m; masses of the joints of the pantograph linkages: m 2 = 0.214 kg, m 3 = 0.338 kg, m 4 = 0.262 kg, m 5 = 0.233 kg, m 7 = 3.08 kg, m 8 = 0.305 kg, m 9 = 0.259 kg; mass of the platform: m pl = 2.301 kg; masses of the links of the pantograph linkages: m B1 =1.221 kg, m B2 = 0.921 kg, m B3 = 0.406 kg, m B4 = 0.672 kg, m B7 = 0.107 kg, m B8 = 0.403 kg, m B10 = 0.436 kg;term of the inertia matrix of the platform:

Fig. 9 .

 9 Fig. 9. Displacement of the PAMINSA along the prescribed straight line (planar projection).

Fig. 10 .

 10 Fig. 10. Input efforts of the PAMINSA in the case of the sixth order polynomial trajectory

Fig. 12 .

 12 Fig. 12. The prototype of PAMINSA developed in the I.N.S.A. of Rennes.

Fig. 13 .

 13 Fig. 13. Trajectory reproduction on the PAMINSA during the displacement of the platform

Fig. 14 .

 14 Fig. 14. Trajectory reproduction on the PAMINSA during the displacement of the platform

  i = (-5/6, -/6, /2),

J

  PAM = A -1 B is the global Jacobian matrix where matrice A and B are:

Fig. 1 .

 1 Fig. 1. Kinematic chain of the planar 5R parallel manipulator.

Fig. 2 .

 2 Fig. 2. Second kind of singularities of the planar 5R parallel manipulator.

Fig. 3 .

 3 Fig. 3. Initial, singular and final positions of the planar 5R parallel manipulator.

Fig. 4 .

 4 Fig. 4. Input torques of the planar 5R parallel manipulator in the case of the sixth order

Fig. 5 .

 5 Fig. 5. Input torques of the planar 5R parallel manipulator in the case of the fifth order

Fig. 6 .

 6 Fig. 6. PAMINSA with 4 DOF.

Fig. 7 .

 7 Fig. 7. Kinematic chain of each leg.

Fig. 8 .

 8 Fig. 8. Example of Type 2 singular configuration (horizontal projection of the examined

Fig. 9 .

 9 Fig. 9. Displacement of the PAMINSA along the prescribed straight line (planar projection).

Fig. 10 .

 10 Fig. 10. Input efforts of the PAMINSA in the case of the sixth order polynomial trajectory

Fig. 11 .

 11 Fig. 11. Input efforts of the PAMINSA in the case of the fifth order polynomial trajectory

Fig. 12 .

 12 Fig. 12. The prototype of PAMINSA developed in the I.N.S.A. of Rennes.

Fig. 13 .

 13 Fig. 13. Trajectory reproduction on the PAMINSA during the displacement of the platform with

Fig. 14 .

 14 Fig. 14. Trajectory reproduction on the PAMINSA during the displacement of the platform with