Félix Majou

Philippe Wenger

Damien Chablat

THE DESIGN OF PARALLEL KINEMATIC MACHINE TOOLS USING KINETOSTATIC PERFORMANCE CRITERIA

INTRODUCTION

Most industrial machine tools have a serial kinematic architecture, which means that each axis has to carry the following one, including its actuators and joints. High Speed Machining highlights some drawbacks of such architectures: heavy moving parts require from the machine structure high stiffness to limit bending problems that lower the machine accuracy, and limit the dynamic performances of the feed axes.

That is why PKMs attract more and more researchers and companies, because they are claimed to offer several advantages over their serial counterparts, like high structural rigidity and high dynamic capacities. Indeed, the parallel kinematic arrangement of the links provides higher stiffness and lower moving masses that reduce inertia effects. Thus, PKMs have better dynamic performances. However, the design of a parallel kinematic machine tool (PKMT) is a hard task that requires further research studies before wide industrial use can be expected.

Many criteria need to be taken into account in the design of a PKMT. We pay special attention to the description of kinetostatic criteria that rely on the conditioning of the Jacobian matrix of the mechanism. The organisation of this paper is as follows: next section introduces general remarks about PKMs, then is explained why PKMs can be interesting alternative machine tool designs. Then are presented existing PKMTs. An application to the design of a small-scale machine tool prototype developed at IRCCyN is presented at the end of this paper.

ABOUT PARALLEL KINEMATIC MACHINES

General Remarks

The first industrial application of PKMs was the Gough platform (Figure 1), designed in 1957 to test tyres 1 . PKMs have then been used for many years in flight simulators and robotic applications 2 because of their low moving mass and high dynamic performances. Since the development of high speed machining, PKMTs have become interesting alternative machine tool designs [START_REF] Treib | Similarity laws of serial and parallel manipulators for machine tools[END_REF][START_REF] Wenger | A Comparative Study of Serial and Parallel Mechanism Topologies for Machine Tools[END_REF] .

Figure 1. The Gough platform

In a PKM, the tool is connected to the base through several kinematic chains or legs that are mounted in parallel. The legs are generally made of either telescopic struts with fixed node points (Figure 2a), or fixed length struts with gliding node points (Figure 2b).

Singularities

The singular configurations (also called singularities) of a PKM may appear inside the workspace or at its boundaries. There are two types of singularities [START_REF] Chablat | Domaines d'unicité et parcourabilité pour les manipulateurs pleinement parallèles[END_REF] . A configuration where a finite tool velocity requires infinite joint rates is called a serial singularity. A configuration where the tool cannot resist any effort and in turn, becomes uncontrollable, is called a parallel singularity. Parallel singularities are particularly undesirable because they induce the following problems:

-a high increase in forces in joints and links, that may damage the structure, -a decrease of the mechanism stiffness that can lead to uncontrolled motions of the tool though actuated joints are locked.

Figures 3a and3b show the singularities for the biglide mechanism of Fig. 2b. In Fig. 3a, we have a serial singularity. The velocity amplification factor along the vertical direction is null and the force amplification factor is infinite.

Figure 3b shows a parallel singularity. The velocity amplification factor is infinite along the vertical direction and the force amplification factor is close to zero. Note that a high velocity amplification factor is not necessarily desirable because the actuator encoder resolution is amplified and thus the accuracy is lower.

Working and Assembly Modes

A serial (resp. parallel) singularity is associated with a change of working mode 6 (resp. of assembly mode). For example, the biglide has four possible working modes for a given tool position (each leg node point can be to the left or to the right of the intermediate position corresponding to the serial singularity, Fig. 4a) and two assembly modes for a given actuator joint input (the tool is above or below the horizontal line corresponding to the parallel singularity, Fig. 4b). The choice of the assembly mode and of the working mode may influence significantly the behaviour of the mechanism [START_REF] Chablat | Domaines d'unicité et parcourabilité pour les manipulateurs pleinement parallèles[END_REF] .

PKMs AS ALTERNATIVE MACHINE TOOL DESIGNS

Limitations of Serial Machine Tools

Today, newly designed machine tools benefit from technological improvements of components such as spindles, linear actuators, bearings. Most machine tools are based on a serial architecture (Figure 5), whose advantage is that input/output relations are simple.

Nevertheless, heavy masses to be carried and moved by each axis limit the dynamic performances, like feed rates or accelerations. That is why machine tools manufacturers have started being interested into PKMs since 1990.

PKMs Potentialities for Machine Tool Design

The low moving mass of PKMs and their good stiffness allow high feed rates (up to 100 m/min) and accelerations (from 1 to 5g), which are the performances required by High Speed Machining.

PKMs are said to be very accurate, which is not true in every case [START_REF] Wenger | A Comparative Study of Serial and Parallel Mechanism Topologies for Machine Tools[END_REF] , but another advantage is that the struts only work in traction or compression. However, there are many structural differences between serial and parallel machine tools, which makes it hard to strictly compare their performances.

Problems with PKMs

a) The workspace of a PKM has not a simple geometric shape, and its functional volume is reduced, compared to the space occupied by the machine [START_REF] Rehsteiner | Putting parallel kinematics machines (PKM) to productive work[END_REF] , as we can see on Fig. 6. b) For a serial mechanism, the velocity and force transmission ratios are constant in the workspace. For a parallel mechanism, in contrast, these ratios may vary significantly in the workspace because the displacement of the tool is not linearly related to the displacement of the actuators. In some parts of the workspace, the maximal velocities and forces measured at the tool may differ significantly from the maximal velocities and forces that the actuators can produce. This is particularly true in the vicinity of singularities. At a singularity, the velocity, accuracy and force ratios reach extreme values.

c) Calibration of PKMs is quite complicated because of kinematic models complexity [START_REF] Daney | Etalonnage géométrique des robots parallèles[END_REF] .

EXISTING PKMT DESIGNS

In this section will be presented some existing PKMTs.

Fully Parallel Machine Tools

What we call fully parallel machine tools are PKMs that have as many degrees of freedom as struts. On Fig. 7, we can see a 3-RPR fully parallel mechanism with three struts. Each strut is made of a revolute joint, a prismatic actuated joint and a revolute joint. Fully parallel machine tools with fixed length struts can have three, four or six legs. The Urane SX (Figures 9 and14) from Renault Automation is a three leg machine, whose tool can only move along X, Y and Z axes, and its architecture is inspired from the Delta robot [START_REF] Clavel | DELTA, a fast robot with parallel geometry[END_REF] , designed for pick and place applications. The Hexa M from Toyoda is a PKMT with six fixed length struts (Figure 10).

Other Kinds of PKMT

The Tricept 805 is a widely used PKMT with three variable length struts (Figures 6 and11). The Tricept 805 has a hybrid architecture: a two degrees of freedom wrist serially mounted on a tripod architecture.

Another non fully parallel MT is the Eclipse (Figure 12) from Sena Technology [START_REF] Ryu | ECLIPSE : an over-actuated parallel mechanism for rapid machining[END_REF][START_REF] Kim | A new parallel mechanism machine tool capable of five face machining[END_REF] . The Eclipse is an overactuated PKM for rapid machining, capable of simultaneous five faces milling, as well as turning, thanks to the second spindle.

DESIGNING A PKMT

A Global Task

Given a set of needs, the most adequate machine will be designed through a set of design parameters like the machine morphology (serial, parallel or hybrid kinematic structure), the machine geometry (link dimensions, joint orientation and joint ranges), the type of actuators (linear or rotative motor), the type of joints (prismatic or revolute), the number and the type of degrees of freedom, the task for which the machine is designed. These parameters must be defined using relevant design criteria.

Kinetostatic Performance Criteria are Adequate for the Design of PKMTs

The only way to cope with problems due to singularities is to integrate kinetostatic performance criteria in the design process of a PKMT. Kinetostatic performance criteria evaluate the ability of a mechanism to transmit forces or velocities from the actuators to the tool. These kinetostatic performance criteria must be able to guaranty minimum stiffness, accuracy and velocity performances along every direction throughout the workspace of the PKMT.

To reach this goal, we use two complementary criteria: the conditioning of the Jacobian matrix J of the PKMT, called conditioning index, and the manipulability ellipsoid associated with J [START_REF]Fundamentals of Robotic Mechanical Systems[END_REF] . The Jacobian matrix J relates the joint rates to the tool velocities. It also relates the static tool efforts to the actuator efforts. The conditioning index is defined as the ratio between the highest and the smallest eigenvalue of J. The conditioning index varies from 1 to infinity. At a singularity, the index is infinity. It is 1 at another special configuration called isotropic configuration. At this configuration, the tool velocity and stiffness are equal in all directions. The conditioning index measures the uniformity of the distribution of the velocities and efforts around one given configuration but it does not inform about the magnitude of the velocity amplification or effort factors.

The manipulability ellipsoid is defined from the matrix (J J T ) -1 . The principal axes of the ellipsoid are defined by the eigenvectors of (J J T ) -1 and the lengths of the principal axes are the square roots of the eigenvalues of (J J T ) -1 . The eigenvalues are associated with the velocity (or force) amplification factors along the principal axes of the manipulability ellipsoid.

These criteria are used in Wenger [START_REF] Wenger | Kinematic analysis of a new parallel kinematic machine tool : the Orthoglide[END_REF] , to optimize the workspace shape and the performances uniformity of the Orthoglide, a three degree of freedom PKM dedicated to milling applications (Figure 13).

Technical Problems

If the struts of the PKMT are made with ballscrews, the PKMT accuracy may suffer from struts warping due to heating caused by frictions generated by ballscrews. This problem is met by hexapods designers that use ballscrews. Thus, besides manufacturing inaccuracies, the calibration of a PKMT will have to take into account dimensions variations due to dilatation. A good thermal evacuation can minimise the effects of heating.

In case PKMT actuators are linear actuators, magnetic pollution has to be taken into account so that chips clearing out is not obstructed. One technique, used by Renault Automation for the Urane SX, is to isolate the tool from the mechanism (Figure 14). At last, choosing fixed length or variable length struts influence the behaviour of the machine. Actuators have to be mounted on the struts in case of variable length struts, which increases moved masses. Fixed length struts do not have this problem, and furthermore allow the use of linear actuators, that bring high dynamic performances.

THE ORTHOGLIDE

A three-axis PKMT, the Orthoglide, was designed at IRCCyN Using the two kinetostatic criteria given in section 5.2. A small-scale prototype is under development (Figure 15). The theoretical kinematic analysis of the Orthoglide is described in Wenger [START_REF] Wenger | Kinematic analysis of a new parallel kinematic machine tool : the Orthoglide[END_REF] . The Orthoglide has been designed such that it has an isotropic configuration (the velocity and forces transmission factors are equal in each direction) in its workspace. Moreover the velocity and force transmission factors remain under prescribed values throughout the workspace. The paper describes how the kinetostatic criteria have been used to define the Orthoglide kinematics and geometry for machine tool applications (Figure 16).

The dimensions of the Orthoglide have been chosen for a 200*200*200 prescribed cartesian workspace, so that the velocity and force amplification factors remain between 0.6 and 1.7, which guarantees minimum performances inside the available workspace. Joint ranges have also been optimised to respect the limits chosen for the velocity and force transmission factors (Figure 17). One or two degrees of freedoms can be added to the Orthoglide either by: -mounting serially a one or two degree of freedom wrist, or -mounting an orienting branch on the base of the Orthoglide, leading to a left hand / right hand architecture.

CONCLUSIONS

The aim of this article was to introduce a few criteria for the design of PKMTs, which may become interesting alternatives for High Speed Machining, especially in the milling of large parts made of hard material, or for serial manufacturing operations on aeronautical parts.

Kinetostatic criteria seem to be well adapted to the design of PKMTs, particularly for the kinematic design and for the optimisation of the workspace shape, with regard to performances uniformity.

The kinetostatic criteria have been used for the design of the Orthoglide, a three-axis PKMT developed at IRCCyN. A small scale prototype is under development. A five-axis PKMT will be derived from the Orthoglide.

Figure 2a .

 2a Figure 2a. A bipod PKM Figure 2b. A biglide PKM

PP

  Figure 3a. A serial singularity Figure 3b. A parallel singularity

Figure 4a .

 4a Figure 4a. The four working modes Figure 4b. The two assembly modes

Figure 5 .

 5 Figure 5. A serial PPP machine tool

Figure 6 .

 6 Figure 6. Workspace sections of Tricept 805 (www.neosrobotics.com)

Figure 7 . 3 -

 73 Figure 7. 3-RPR fully parallel mechanismFully PKMT with six variable length struts are called hexapods. Hexapods are inspired by the Gough Platform. The first PKMT was the hexapod "Variax" from Giddings and Lewis presented in 1994 at the IMTS in Chicago. Hexapods have six degrees of freedom. One more recent example is the CMW300, a hexapod head designed by the Compagnie Mécanique des Vosges (Figure8).

Figure 8 .

 8 Figure 8. Hexapod CMW 300 (perso.wanadoo.fr/cmw.meca.6x/6AXES.htm)

Figure 9 .Figure 10 .

 910 Figure 9. Renault automation Urane SX (from "Renault Automation Magazine", n° 21, may 1999) Figure 10. Toyoda Hexa M (www.toyodakouki.co.jp)

Figure 11 .Figure 12 .

 1112 Figure 11. Tricept 805 from Neos robotics (www.neosrobotics.com) Figure 12. The Eclipse, from Sena Technology (macea.snu.ac.kr/eclipse/homepage.html)

Figure 13 .

 13 Figure 13. A section of Orthoglide's optimised workspace

Figure 14 .

 14 Figure 14. Urane SX tool is isolated from the mechanism that generates the motion (from "Renault Automation Magazine", n° 21, may 1999)

Figure 15 .

 15 Figure 15. PKMT prototype

Figure 16 .

 16 Figure 16. Kinematics of the Orthoglide Figure 17. Dimensions of the Orthoglide


Mathieu Luglia
email: mathieu.luglia@imbe.fr

Camille Fourrier

Catherine Keller

Sophie Gachet

Pierre Hennebert

Jean-Paul Ambrosi

Yves Noack

Virgile Calvert

Isabelle Giffard

Daniel Pavon

Bernard Angeletti

Stéven Criquet

The terrestrial red mud deposits in Provence : Ongoing researches in soil science

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Study Study sites sites

Framework Framework

These researches fit into the works coordinated by the Observatoire Hommes-Milieux (OHM) of Bassin Minier de Provence (BMP) and dedicated to vegetal covers and microbial communities of soils. They aim to study the terrestrial deposits of red muds resulting from past and current activities of alumina extraction.

Despite the red muds have been extensively studied about their industrial recycling potentials (Klauber et al., 2011), the studies on their environmental effects, especially on the biological component of soils, are far less numerous (Lombi et al., 2002;Garau et al., 2007Garau et al., , 2011Garau et al., , 2014;;Krishna et al., 2014) and, furthermore, lacking in the context of BMP. To this date, the various studies available in the literature emphasize the importance of the soil matrix in the modulation of biological responses when it is mixed with red muds. Therefore, this aspect is important to invest at the local scale in the prospect of a potential use of red muds as improvement to soils or to the development of artificial soils for various valuations (e.g. pollution control, remediation, rehabilitation).

  Township: Marseille (15 th district) Coord.: 43 20'26'' N / 5 21'52'' E Average alt.: 37 m Area: 37 570 m 2 La La Area La La Barasse Barasse ( (1 1) ) Township: Marseille (11 th district) Coord.: 43 17'6'' N / 5 29'35'' E Average alt.: 76 m Area: 49 980 m 2 La La Area La La Barasse Barasse ( (2 2) ) Township: Marseille (11 th district) Coord.: 43 16'32'' N / 5 28'47'' E Average alt.: 196 m Area: 68 700 m 2 1 2 Gardanne Coord Gardanne plant built in 1893 Coord.: 43 27'8'' N / 5 27'35'' E

Alusuisse Alusuisse Saint Saint--Louis Louis--les les--Aygalades Aygalades plant, 1964 plant, 1964 Pechiney Pechiney Gardanne plant, 1951 Gardanne plant, 1951 Alteo Alteo Gardanne plant Gardanne plant Bauxite Bauxite mining mining in Provence in Provence

This work is supported by the Observatoire Hommes-Milieux of Bassin Minier de Provence (OHM-BMP) and the LabEx DRIIHM (CNRS-INEE).

SFÉcologie SFÉcologie 2016 2016 --


Brice Govin
email: brice.govin@thalesgroup.com

Nicolas Anquetil
email: nicolas.anquetil@inria.fr

Anne Etien
email: anne.etien@inria.fr

Stephane Ducasse
email: stephane.ducasse@inria.fr

Arnaud Monegier
email: arnaud.monegier@thalesgroup.com

How Can We Help Software Rearchitecting Efforts? Study of an Industrial Case

Legacy software systems are valuable assets for organisations and are sometimes their main source of incomes. From time to time, renewing legacy software system architecture becomes necessary in order to offer them a new future. Migrating the architecture of a legacy software system is a difficult task. It involves understanding and aggregating a large set of data (the entire source code, dependencies, etc.); it may have a profound impact on the system's behaviour; and because it occurs very rarely in the life of a system, it is hard to gain experience in this domain. Based on the study of an industrial architecture migration case, we discuss how this essentially manual effort could be helped with automated tools and a better defined process. We identified several issues raised during the task, characterized their impact, and proposed possible solutions.

I. INTRODUCTION

Legacy software systems represent a significant part of companies' wealth. Maintainability of such systems has become an important goal for companies which own them. Software evolution activities can be classified in two: day to day evolution, where engineers correct bugs, implement new features, or adapt the system to new working conditions; and, much rarer, restructuring, where engineers need to completely re-think the architecture of a system because it seems no longer possible to adapt it in small steps. Because it occurs so rarely in the life of the system, restructuring software architecture is mostly a case-by-case activity. It is difficult to gain much experience in it and to improve its practice through the definition of a formal process.

In our specific case, the company we are working with wants to restructure a real-time, embedded, critical system. The system is an old (> 20 years) Ada system in the defence area. The goal is to modularise the system to ease day to day evolution and take advantage of technological improvements that were introduced since the creation of the system. The wished architecture is partially specified in the sense that high level components and main architectural rules have been defined. In this restructuring, there is no immediate change in the functionalities and one goal is to reuse existing code as much as possible.

The classical process for architecture restructuring is the horseshoe "process" [START_REF] Kazman | Requirements for integrating software architecture and reengineering models: Corum ii[END_REF]. However, this is a very generic one that defines high level operations. As such it has been specialised in various publications (e.g. [START_REF] Yu | Reverse engineering goal models from legacy code[END_REF]). A line of research try to generalise the target system into a Software Product Line [START_REF] Yu | Reverse engineering goal models from legacy code[END_REF] by abstracting variation points in the functionalities, this is not our case since we are keeping the same functionalities. Others focus on migrating toward a Service-Oriented Architecture [START_REF] Khadka | A structured legacy to soa migration process and its evaluation in practice[END_REF], which, again is not our case, since it has been decided to go for a component based architecture. The Component Recovery line of research is an old one (e.g. [START_REF] Allier | Restructuring object-oriented-applications into component-oriented applications by using consistency with execution traces[END_REF], [START_REF] Koschke | Atomic architectural component recovery for program understanding and evolution[END_REF]) but it typically only tries to extract the components without allowing to specify a wished architecture. Confronted to architecture restructuring in a real software architecture migration case, we found that existing literature often relies on hypotheses that were not true in our case.

In this paper we discuss a three steps process that we formalised from the activities of the software engineers in the project. We list the difficulties that arised when trying to automate some of these activities and possible solutions that we experimented. The efficacity of the different experiments are evaluated against an oracle resulting from the work of software engineers and ourselves on a part of the system.

Section II describes the problem of software architecture migration and the potential related solutions in the literature. Section III details the actions of the software engineers performing the restructuring and points out weaknesses of this project. Section IV presents a process formalising the actions taken by the software engineers and ideas to (partly) automate it. Finally, section VI draws lessons learned from this project and explains the future work.

II. BACKGROUND

As stated previously, the classical process for architecture restructuring is the Horseshoe process [START_REF] Kazman | Requirements for integrating software architecture and reengineering models: Corum ii[END_REF]. It is divided into three main parts: reverse engineering, re-engineering and forward engineering. The reverse engineering part aims to model and understand the current system architecture, the reengineering part aims to restructure the architecture of the system and the forward engineering part aims to re-implement the new architecture in the source code [START_REF] Gerardo | New frontiers of reverse engineering[END_REF]. In our project, the reverse engineering part is already handled by the Moose infrastructure [START_REF] Ducasse | Moose: an Extensible Language-Independent Environment for Reengineering Object-Oriented Systems[END_REF]. This offers us a model of the system with all its software elements (packages, procedures, types, variables) and their interdependencies (use of variables, invocation of methods, etc.). We will therefore focus on the re-engineering part. We found in the literature different approaches that can tackle this part, e.g. Software Architecture Transformation [START_REF] Barais | Software architecture evolution[END_REF]; migration towards Service-Oriented Architecture (SOA) [START_REF] Khadka | A structured legacy to soa migration process and its evaluation in practice[END_REF]; and Component Recovery [START_REF] Koschke | An incremental semi-automatic method for component recovery[END_REF].

A. Main Lines of Research

The phrase Software Architecture Transformation is defined in [START_REF] Kazman | Requirements for integrating software architecture and reengineering models: Corum ii[END_REF] as the line of research that aims at transforming the current architecture of a legacy system into a new one. Transformation between old and new architecture is done thanks to a set of "recipes" transformation between elements from the two different architectures [START_REF] Carrière | Software architectural transformation[END_REF]. This domain focuses on monitoring the impact of architectural changes on the overall quality of the system. It also only considers small architectural transformations that can be applied automatically and guarantees the executability of the resulting source code. This line of research does not concern us since the project we are involved with will completely restructure the system around an architecture radically different from the existing one.

Migration towards Service-Oriented Architecture (SOA) aims to "move the legacy system architecture to the more flexible SOA while preserving the original system data and functionality" [START_REF] Almonaies | Legacy system evolution towards service-oriented architecture[END_REF]. SOA migration approaches either address the technical perspective to expose legacy code as services, or determine the migration feasibility regarding the characteristics of the legacy system and the requirements of the target SOA system [START_REF] Khadka | A method engineering based legacy to soa migration method[END_REF]. We are not interested in the technical aspects because, in our case, the current and future systems are both implemented using the same technologies and we foresee no technical difficulties there. Moreover, components and services, even though they are close, have fundamental differences that would make it very difficult to reuse SOA migration approaches for component architecture migration.

On the other hand, SOA migration work, e.g. [START_REF] Almonaies | Legacy system evolution towards service-oriented architecture[END_REF], [START_REF] Khadka | A method engineering based legacy to soa migration method[END_REF], [START_REF] Idu | Migrating Legacy Applications: Challenges in Service Oriented Architecture and Cloud Computing Environments: Challenges in Service Oriented Architecture and Cloud Computing Environments[END_REF], introduced interesting techniques such as Concept Slicing to associate the existing source code with the services they extract. The idea behind Concept Slicing is to identify the source code associated with the implementation of a humanoriented "concept". The human oriented concept thus becomes a service and the code associated to it is used to implement that service. Concept slicing works by combining Concept Assignment solutions, that identify relevant pieces of code from a concept, with Program Slicing solution, that identify an executable piece of code.

A last related line of research named Component Recovery, or Component Identification, automatically organises the software elements of a system into components. Component recovery corresponds to the detection of subsystems [START_REF] Schwanke | An intelligent tool for re-engineering software modularity[END_REF], it works by clustering the nodes of a dependency graph of the application [START_REF] Allier | Restructuring object-oriented-applications into component-oriented applications by using consistency with execution traces[END_REF], [START_REF] Koschke | Atomic architectural component recovery for program understanding and evolution[END_REF], [START_REF] Seriai | Enactment of components extracted from an object-oriented application[END_REF] into independent components. Yet because they work on structural information (a graph of dependencies between the elements of the system), they can only extract structurally coherent components whereas they should include human and domain knowledge in the process to be able to extract business components [START_REF] Gear | Component reconn-exion[END_REF], [START_REF] Wang | A survey of business component identification methods and related techniques[END_REF]. Another issue with existing Component Recovery techniques is that they do not accept a predefined target architecture, but focus on extracting what they consider the best possible components. In our case, the target architecture is already partly defined and we already know what the main components (more abstract ones) should be and even for some of them what sub-components they should contain. We are not aware of a Component Recovery approach that would suit this requirement.

B. Extraction of components from existing source code

Although the existing Component Recovery approaches do not apply to our project, they offer some useful techniques.

All the techniques are based on the idea of representing the source code as a dependency graph where the nodes are software elements and the vertices are dependencies between them [START_REF] Allier | Restructuring object-oriented-applications into component-oriented applications by using consistency with execution traces[END_REF], [START_REF] Koschke | Atomic architectural component recovery for program understanding and evolution[END_REF], [START_REF] Seriai | Enactment of components extracted from an object-oriented application[END_REF]. Any given approach will work at a specific level of abstraction and consider a small number of software element kinds, Koschke [START_REF] Koschke | Atomic architectural component recovery for program understanding and evolution[END_REF] calls them Quarks, "the smallest significant element at the architectural level". For example, Allier and Seriai [START_REF] Allier | Restructuring object-oriented-applications into component-oriented applications by using consistency with execution traces[END_REF], [START_REF] Seriai | Enactment of components extracted from an object-oriented application[END_REF] work with classes and Koschke [START_REF] Koschke | Atomic architectural component recovery for program understanding and evolution[END_REF] with subprograms, user defined types and variables (in a C program). On the other hand, the example of SOA migration shows that it might be necessary to work at a very fine-grained level. This is the case when program slicing is used to extract executable services.

From the dependency graph, software elements are clustered to form components. The clustering tries to maximise dependencies within a component (known as Cohesion) and minimise dependencies between components (known as Coupling). Many different metrics have been proposed to compute Cohesion and Coupling and we will not consider them in this paper.

Finally we should add that Johnson [START_REF] Johnson | Mining legacy systems for business components: An architecture for an integrated toolkit[END_REF] noted the necessity of an iterative process.

III. DESCRIPTION OF THE PROJECT

We are accompanying a large company which undertook a big software migration project where the architecture of the subject system will be completely redesigned. This section describes the project, Section III-A explains the context of the project; Section III-B details the informal process followed by the re-engineers. Section III-C points out the weaknesses of this informal process.

A. Context of the Migration

The migration project is to restructure a real-time, embedded, critical system in the defence area. The system is old (> 20 years), big (> 300 KLOC) written in Ada 83. It counts around 1 500 packages and 15 000 subprograms gathered into modules. Table I summarises main characteristics of this system and Figure 1 gives a general idea of the existing software architecture. It should be noted that this existing architecture was not explicit prior to the project and has been reconstructed as part of a reverse engineering effort. This reverse engineering effort has been done by engineers inside the company and none of the authors have participated. The problems identified with this system are:

• This is a real time system developed a long time ago with the best techniques of that time. As such, a strong emphasis was placed on the processing with little consideration for a high level data model. The company now wishes to correct this situation by defining and using high level, business oriented, data structure that could possibly be shared with other systems in the company. • The legacy system uses a communication system, that is a proprietary middleware, based on messages exchanges. Since its installation, new communication standards have been defined, that the company wants to use. Instead of using an event based communication system (messages), interactions should be based on shared data. • Changes in the physical environment of the system are foreseen in the near future, and there is a concern whether these changes could be easily accommodated in the existing system. For example, the Algorithm layer (Figure 1) regularly interacts directly with the physical devices.

The company now wishes to have a more modular system that will constraint the impact of any of these changes to a small portion of the system. • The legacy system adopts a layered architecture. However, communication and dependencies between layers are frequent and not only between two adjacent layers. • Ultimately, there is a hope to be able to reuse some of the components of the target architecture in other systems of the company in the same business domain. Again, this implies having a more modular system, with betterdefined components and data structures. With these requirements in view, some high level components were defined by domain experts and structured in the target architecture sketched out in Figure 2. The target architecture is only partially specified in the sense that these high level components and main architectural rules were defined, but the exact content of the composite components (i.e. the small boxes within the big ones) was not clear at the start of the project. In this restructuring, all functionalities should remain the same. One goal is to reuse existing code as much as possible and what parts of the existing code should map to what components (composite or atomic) is to be decided by the restructuring project.

The planned architecture has two levels: a component can either be composite (large boxes in Figure 2), and contain other components, or atomic (smaller boxes), and be associated to current code. A few architectural rules were defined to constraint relationships between components, such as a strict three layer architecture (+ the physical device layer) where any layer can only interact with the layers directly above or below it (therefore Business layer cannot interact with Interface layer).

B. Existing Activities in Details

The restructuring relies on manual code analysis. A brief overview of the Ada language is given here to help the reader understand the activities taking place in this project.

The Ada entities of interest are: packages, subprograms and instructions. Packages contain entities that can be packages, subprograms or instructions. Subprograms contain only subprograms or instructions. Instructions are elementary entities (e.g. subprograms calls).

The software engineers study the source code to allocate software elements to one of the 16 pre-defined composite components. They do this by actually assigning software elements to potential atomic components within the composite components. Two tasks are therefore performed concurrently: assign software elements to the composite components and decomposing these into a number of atomic components. Software engineers try to allocate entire packages to a given atomic component. Yet studying it, they may consider that a part of it, maybe a subprogram, will need to be assigned to another atomic component (but always in the same composite component); they may sometimes even go down to assigning instructions (always subprogram invocations) to another atomic component.

From this informal process, we identified two interesting characteristic. First, they work at very different levels of abstraction, from coarse grained elements (packages) to very detailed ones (single instruction). To the best of our knowledge, we have not seen a proposition in the literature that allows to work with such a wide range of entities. Second, they adopted an iterative approach that tends to refine the results, working first on packages, then on subprograms and eventually on instructions.

Allocating Packages: Based on their understanding of the source code, the re-engineers select a set of packages that are likely to answer the responsibility of a component. The packages imported by each of these initial packages are normally allocated to the same component. Exceptions occur when an imported package has already been allocated to some other component. In that case, a deeper analysis of the package is performed, by looking at the comments in the source code, to resolve the conflict.

In case of doubt, another possibility is available: a library component gathering all the packages that could not be allocated to one single component.

Allocating Subprograms and Subprograms Invocations: Subprograms and subprograms invocations may be moved from one atomic component to another but only between sibling components (meaning they remain in their composite component). Re-engineers' analysis of the packages content relies on structural information such as dependencies between subprograms, and instructions in order to identify flows of execution. One must recall that we are dealing with a real time system which implies that functionalities or task within this system are first class citizens that receive a large part of the developers' attention. In comparison with more traditional information system, it seems that data received less attention during the system initial development. It is actually one of the goal of the system to correct this fact and identify high level, business, data structures that could possibly be reused in other related systems.

The analysis of the software engineers also relies on their knowledge of the system, their experience in the domain, the identification of features in the source code and the extraction of the source code associated to a feature. They are basically applying a concept slicing to determine the instructions that perform a specific feature and then allocate theses instructions to the component that should implement this feature. Respect of the mandatory / prohibited relationships between components are also used in the allocation of subprograms and subprograms invocations.

Code Rewriting: In accordance with the allocation, reengineers rewrite the existing code to make the legacy software system work with its new architecture. Classic V-cycle is the basis of this part and it is done in parallel with the previous step.

At the moment, this project is ongoing, atomic components have been identified in all 16 composite components. Many packages and subprograms have been allocated to their composants, but all the work is not done yet and the final step of rewriting the code to actually build the new system did not start yet.

C. Existing Approach Weaknesses

This informal process mostly relies on a comprehension of the legacy system by the re-engineers. A deep knowledge of each entity (package, subprogram or subprograms invocations) is required. Consequences are twofold.

First, the process is fully manual leading to time consumption and possible error creation. Due to the significant size of the legacy system, the full content of each package cannot be analysed in details by humans. Consequently, in the package allocating stage, the re-engineers use imported packages declarations to navigate dependencies from a given package. However, these declarations may be a super set of the actual dependencies. Unrelated packages are analysed together whereas they have no connected responsibilities and their analysis should be postponed.

Second, the process mostly relies on the skills of very few re-engineers who know the software enough. This deep knowledge eases their task, by enabling them to eventually skip the analysis of entities. However, their analysis strongly depends on the coding convention, making the process strongly dependent on the legacy software system. Consequently, the process is ad hoc and is difficult to reproduce on another legacy system or with another engineer.

IV. A PROPOSED TOOL SUPPORTED PROCESS

To help overcome these weaknesses, we are working on formalizing a restructuring process and developing tools to automate it. Our solution is based over an existing industrial tool using the Moose technology [START_REF] Ducasse | Moose: an Extensible Language-Independent Environment for Reengineering Object-Oriented Systems[END_REF]. Our hopes are: to validate the work already done and/or identify possible erroneous decisions; To speed up the remaining of the project; To prepare for envisioned future similar efforts in the company. While describing this process, we will highlight decision points (DP ) that we evaluated to understand which solution was the best and what consequences they could bring.

Our process consists in an iterative refinement of the allocation of software elements to components: In a first step, packages will be assigned to components, possibly resulting in conflicting assignments. We then go down to the level of subprograms to decompose the conflicting packages into coherent "sub-packages", and decompose composite components into atomic components. Finally we propose to go down to decomposing subprograms by allowing to assign some of their instructions to different atomic components. This last step assumes one would do subprogram extraction refactorings.

The process does no try to create components as often seen in past research, but relies on the knowledge of software engineers in their business domain to propose meaningful components and assign software elements to these components. This knowledge is reinforced by structural information (dependencies between elements) and the identification of special elements.

At the start of each iteration, a model of the system (or of a part of the system) is built with the software elements to be allocated (called architectural quarks following the convention in [START_REF] Koschke | Atomic architectural component recovery for program understanding and evolution[END_REF], i.e. the smallest significant elements) and their relationships (or dependencies). Each iteration then consists in asking the software engineers to identify core quarks and assign them to components. From these core quarks, we navigate the dependencies between all quarks to assign them to the components. The main decision points (DP ) in evaluating our process and its automation will therefore be, at each iteration (or level): (i) how to choose the right core quarks; (ii) what dependencies to follow (or how to follow the dependencies as will be explained further down); and (iii) how to resolve conflicting assignments. Note that it is not mandatory to solve every conflict during a given step. Thus, at the end of an iteration, some conflicts might still exist.

Finally, we must note that our process does not yet address the code rewriting step.

A. First iteration: Package allocation

This first iteration aims to allocate packages into composite components. At the architectural level of this iteration, the quarks are Ada packages. The edges of the dependency graph are the dependencies between packages as when one package imports another one.

The software engineers helped us to identify simple rules that allowed to identify the core packages of each composite components (DP 1 c * ). There can be as little as one core per component. It was easy for the software engineers to select them. Actually, the choice of the composite components of the wished architecture already implicitly relied on the identification of important part of the system that were easy to map to some packages. For the system under study, it was possible to define rules, based on naming convention and the presence of some specific software elements (an Ada * DP 1 c stands for Decision Point for Core quarks at iteration 1.

procedure named run), allowing to automatically identify core packages for each high level component. We experimented two alternative solutions for DP 1 c : the packages indicated by the software engineers (see above) and random choice of packages. Obviously, the second one will give poorer results, but it may be a specificity of this project that high level composite components and core packages seemed very clear to the software engineers.

The dependency graph is navigated from each core, following its dependencies recursively (see Figure 3). Each reached node is allocated to the same component as the core. Obviously, the same node may be reached from different cores because several packages depend on it (e.g. the triangle and diamond elements on the right of the figure) resulting in conflicting quarks (multi-core conflict). It may also occur that some quarks are never reached from the cores resulting in another type of conflict (isolation conflict as for the dotted elements on the left of the figure).

We experimented with three solutions for Decision Point DP 1 d † : First the dependency relationships can be Ada declared imports between packages (Ada instruction with). Second they can be what we call referenced imports which are the declared imports that are actually necessary in the code to make it compile (as in many languages, the compiler does not check that a declared import is actually necessary). This is one point where an automated tool has an advantage over manual analysis in identifying the imports that are really required. The referenced imports are guaranteed to be a subset of the declared imports. Third, dependencies between packages can be the same referenced imports, but this time followed upward and downward, that is to say we look on what packages the core quarks depend (as for the two other solutions), but we also include in the component, the packages that depend on the core quarks.

Re-engineers may solve conflicts manually according to their knowledge of the application. They are helped by information about the packages e.g. their names, their comments or all the dependent packages in the dependency graph. In this iteration, conflicts resolution is not required since the iteration is used to set out the architecture migration process.

We experimented with two solutions for Decision Point DP 1 r ‡ : first and as currently done by the software engineers, the "resolution" of multi-core conflicting packages may be to assign them to a special component called the Library. The rational is that packages that are required by more than one component need to be accessible from everywhere. In this first solution, we propose to resolve isolation conflict by following the dependencies from the isolated packages towards the core packages (note that the isolated packages are those that could not be reached from any core towards them). This part is similar to the third choice for DP 1 d . A second option that we evaluated for DP 1 r was to leave the components in conflict and evaluate them as if they were Fig. 3. Example of navigation and conflicts actually member of both components (multi-core conflict) or of no component at all (isolation conflict).

B. Second Iteration: Subprograms allocation

This second iteration aims to refine the allocations done in the first iteration by defining atomic components in the composite components and allocating subprograms to these atomic components. The dependency graph is build from subprograms (the quarks) and the dependencies between them are invocations. Again the iteration starts by choosing core quarks and allocating them to components following transitively the dependencies.

Allocation is always considered within a composite component, which means that subprograms in a package will always remain within the composite component of their package, but two subprograms of one package may be allocated to two different atomic components.

We experimented with only one composite component in this iteration.

The first option for DP 2 c (choosing of core quarks for iteration #2) is again to follow the indications of the software engineers. (They were less clear cut this time). Several atomic components of the composite component considered for this evaluation were named by the software engineers from one package of the same composite component. All the subprograms of such packages were an obvious choice as core quarks for their respective atomic components. In other cases, we tried to rely on subprogram naming convention to choose core quarks for other atomic components.

For Decision Point DP 2 d , we relied on invocation between subprograms as stated above. We considered three options (not all mutually exclusive): only using downward invocation from the cores to other subprograms; using both upward and downward invocations; and/or considering what variables the subprograms use. The last option is based on the hypothesis that some variables are "indicators" of atomic components. By identifying these variables, we want to assign subprograms that use them to the components, This iteration will also result in conflict that may be resolved by the software engineers or left for the next iteration.

C. Third Iteration: subprograms invocations allocating

This iteration aims to resolve some of the conflicts left in the previous iteration by decomposing the subprograms and assign individual instructions (extracted in new subprograms) to atomic components. As for the manual process, the instructions considered here are invocation (subprogram calls) instructions.

We identified some conflicting subprograms that act as "dispatcher" between several atomic component: The flow of execution reaches them and they channel it toward the appropriate atomic component after a series of tests. Such dispatcher subprograms are often in conflict in that they appear to be assignable to several atomic components, usually all the components to which they may dispatch the flow of control. One idea is to try to decompose these dispatchers so that each flow of execution is concentrated in its atomic component and the dispatching done earlier in the flow of execution.

We neither had the time nor enough data yet to experiment solutions for this step.

V. EXPERIMENT DESCRIPTION

We presented a process to help software engineers restructure a software system. At each iteration of the process, we identified decision points and proposed solutions. We compare these solutions to an oracle corresponding to the manual work of the software engineers after possible modifications.

We first present the oracle before discussing in detail each proposed solution and see their respective efficiency and what impact they have on the result.

A. Oracle

The manual work described in section III-B is considered the oracle. The target architecture is composed of 16 composite components. One of them is the Library component and is used to gather all the packages that are needed (i.e. imported by a package) by several composite components. The engineers allocated 1 537 packages on to the 16 composite components. 408 packages, out of the 1 537 packages of the application, were allocated to the Library. 593 packages have been categorised as messages and are treated by the engineers during the second iteration. This first step took about two weeks long to four engineers to complete. This first assignment of packages into composite components is the base for our oracle (evaluation of our first step solutions).

At the time of this writing, the engineers finished defining all the atomic components belonging to the composite components. However, few of these atomic components have been populated by software elements (packages, subroutines, instructions). The engineers focused on two of the 16 composite components, and their atomic components are considered complete. These two composite components and their atomic components are used to evaluate the results of our second step solutions. This part of the oracle took some time to establish as it requires a more in depth study of the packages and their subprograms. Each of these two composite components took one person/month to complete. The software engineers established a first classification that was too low level (not sufficiently abstract). After reworking they merged some of the atomic components originally identified together.

Unfortunately, we could not establish a meaningful oracle for the evaluation of the third step solutions.

B. Evaluation of solutions

Evaluation of all proposed solutions will be computed against the oracle. We use Precision and Recall metrics, also summarised in the F-Score metric. For any possible allocation of quarks in components:

• Precision = % of quarks allocated to a component in the evaluated solution that are in the same component in the oracle.

• Recall = % of quarks allocated to a component in the oracle that are in the same component in the evaluated solution.

• F-Score = 2*(precision*recall)/(precision + recall) Typically, one may achieve better precision (all allocated quarks are in their right component) by lowering the recall (very few quarks are actually allocated to any component). The opposite is also true. For this reason, the F-Score metrics offers a balanced value of both metrics together.

The result we give are the arithmetic mean of the metrics values over all components.

For reference, we give the results of the first allocation of software elements into atomic components made by the engineers (Table II). They later improved this work, but considering their initial result can give some ground of comparison to rank the quality of the automated solutions. These results may be compared to what we did on the second iteration of our process (see Section V-D. The results are not perfect and show how difficult it can be for human experts to allocate software elements into components. C. Proposed Solutions For Iteration 1 DP 1 c : Software engineers identified 64 packages as the core quarks for the 16 composite components. As mentioned in Section V-C, we could easily define rules to automatically identify the core packages based on naming convention of the packages and the presence of some specific software elements (an Ada procedure named run). This is due to the fact that the composite components match high level features of the system which themselves each correspond to some easily recognizable package.

DP 1 d : We experimented three solutions: • Declared imports between packages (Ada instruction with), going from core packages to the packages they import (and transitively); • Referenced imports which are the declared imports backed up by some actual use of the package content, going from core packages to the packages they import (and transitively); • Up/Down imports which are the referenced imports going from core packages to the packages they import (and transitively) and also from core packages to the packages that import them (and transitively). Both paths (up and down) are followed completely from cores without going back. In other terms directions are not mixed. DP 1 r : We experimented two solutions: • With library where packages in conflict are allocated to a special component called the library (precision and recall are computed for this special component as well as the other); • No library where packages are allowed to remain in conflict and are considered allocated to several composite components and the library components is empty which already means precision and recall will be lower. The first conclusion is that precision is much better when we resolve conflict by assigning packages to the library component. This was expected as this library contains 1 001 packages in the oracle that will all hurt the precision metrics if they were not allocated to their library component. Recall is better if we do not assign conflicting packages to the library because it gives a chance to some packages that should not be in the library to be actually allocated to their component. Overall, the loss in precision largely outweighs the gain in recall as shown by the F-Score.

We also see that referenced imports are better than declared imports in terms of precision. The explanation must be that some packages are indeed imported where they are not needed and this introduces noise. As expected this improve in precision is made at the expense of the recall but the F-Score still is better for referenced imports. This, therefore, seems to be the solution of choice.

Finally, considering referenced imports both downward and upward from the core packages significantly lowers the results. The explanation is that much more packages can be reached from any core with this solution. Some of them may be correct hits, but many more should not have been reached thus hurting precision. For line 3, recall also diminishes drastically, because with more packages reached from any core, many end up in conflict and are therefore allocated to the library component instead of their right component.

Because of its size (two third of all the packages of the application), including the library in the comparison could impact the precision, recall and F-Score. We decided then to make two comparisons for our chosen solution (line 2 of table VI): a comparison that includes the packages of the library; a comparison that does not include the packages of the library. Table IV shows that precision ad F-Score are increased without taking the library into account in the comparison while recall is stable (only a decreasing of on but it is mostly due to the fact that metrics are rounded). Precision is stable for each composite component, except for the composite F. We took a deeper look at this composite and it appears that packages are coming from the others composite. However no general rule can be found to handle this effect. Although recall fluctuates between 70% and 100%, leading the F-Score to also fluctuates, these two metrics stay above 70%

D. Proposed Solutions For Iteration 2

In this Iteration, quarks are subprograms that are allocated to atomic components. One decision in this iteration is that we would not go back on the previous results and leave subprograms in the composite component where their parent packages are allocated. But two subprograms in the same package may be allocated to two different atomic components (within the same composite component). For the evaluation of our solution, we only consider two specific composite components that were fully treated by the software engineers.

DP 2 c : Based on some indications by the software engineers, rules were defined using a naming convention on the subprograms to identify core subprograms of some atomic components (the name of the atomic components can be found in the name of some subprograms). In other cases, one package was identified as central to an atomic component and all its subroutines were consequently chosen as core quarks for this component. This work was performed without the direct help or monitoring of the software engineers and therefore, we cannot ensure that our chosen cores are the best we could have defined for each atomic component. The rational was that we wanted to see how well we could do with a more limited understanding of the system. We did had to correct some of our rules after a first try when we obtained results that were not those expected. We believe, this kind of iterative refinement of the core quarks selection is normal and reflects actual working conditions when the software engineers would not have a perfect understanding of the existing system.

DP 12 d : We experimented two solutions: • Downward invocations between subprograms, going from core subprograms to the subprograms they call (and transitively); • Up/Down invocations going from core subprograms to the subprograms they call (and transitively) and also from core subprograms to the subprograms that call them (and transitively). DP 2 r : We experimented three solutions: The first line of result is not very good due to a large number of subprograms in conflict.

Result of the second line are a slightly better, showing that resolving conflicts with endemic variables can improve precision. Unfortunately, there are actually few such variables.

The third line brings much better precision with very little impact on recall. This is due to the fact that we have a larger set of endemic variables at the beginning, when only few subprograms are allocated to an atomic component. This suggest that we might want to more permissive when computing endemic variables.

The fourth line is interesting because it brings an increase in recall when compared to the first one. This was expected as we gather more subprograms, taking the ones called by the core quarks and the ones that call the core quarks. Precision is low because, as for iteration 1 (Section V-C), a lot more nodes are reached from any core, including some that should not be.

When introducing conflict resolution with the help of endemic variables, we observe the same phenomenon as for line 2: higher precision, lower recall.

Finally, the last experiment raises agin the recall, while not affecting precision. tis gives the best F-Score over all six experiments.

Results for this iteration are encouraging, but still not satisfying. They are definitely worse than the first try of the experts. However, they were obtain which much less efforts (automated solutions) and by people with a lesser understanding of the system (we are not experts).

We are still working on this iteration to try to get more satisfying results. One direction of possible improvement would be to continuue working on the variables, either by loosening the constraint for endemic variables, or finding other interesting data. We noticed for example some "dispatching" subprograms (see also Section IV-C) that allow to distribute the flow of execution over several atomic components. They do this by looking at the value of specific variables. Identifying these variables and the values of interest could help us improve our results, somehow as endemic variables already helped us.

VI. CONCLUSION AND FURTHER WORK

A large company called us to follow and help in its legacy software migration project. The legacy software had modularisation problems that led the company to decide for a restructuring of the system architecture. The project started, before we stepped in, by the definition of a wished, target architecture at a rather high abstraction level. Then, the engineers and architects performed an informal software architecture migration process from which we pointed out weaknesses that could prevent its reproduction in another migration.

We decided to propose a tool-supported process that remedies these weaknesses. We based the definition of our process on the informal one that we witnessed in the project. Our tool supported solution is an iterative process that combines dependency graph extraction, data uses analysis, and domain knowledge of the re-engineers to select core elements that serve as seed for components. While other research only work with a fixed kind of software elements (typically classes or procedures), our process works with different kinds (packages and subprograms for now).

We identified several points of decision in our process and proposed possible choices at each point. These choices were then evaluated to see which one made more sense.

The next steps of our work will be to improve our results in the second iteration and/or concentrate on the third step that is intended to resolve the conflicts left in the second one. Our main hopes for now will be to analyze data usage in the subprograms to either allocate them to their correct component or understand how to split them into different subprograms each going more clearly into one atomic component.

Fig. 1 .

 1 Fig. 1. Simplified representation of the existing software architecture

Fig. 2 .

 2 Fig. 2. Simplified representation of the target component-based architecture

•

  No action where subprograms are left in conflict. Contrarily to the previous iteration, in this case we consider that subprograms in conflict are not allocated to any atomic component. This is somehow similar to saying they are allocated to a kind of "library atomic component" although such atomic component does not really exist. The subprograms in conflicts are left to be disambiguated in the next iteration of the process;• Variable uses (post) where some variables were identified that are only used within an atomic component (we say they are endemic to this component). Using these variables, we try to resolve subprograms in conflict by looking if they refer to any of these variables and if so, allocating them to the atomic component related to this variable. • Variable uses (during) where we worked again with variables endemic to an atomic component. But this time, we try to resolve conflicts immediately as they arise during propagation from the cores. If we could resolve the conflict, this allowed us to propagate one step further the allocation to a component. In this setting, the set of endemic variables is recomputed at each step of the propagation and gradually shrink, but it is larger at the beginning, allowing to allocate more subprograms to atomic components.

† DP 1 d stands for Decision Point for Dependency relationship at iteration 1.‡ DP 1 r stands for Decision Point for Resolving conflicts at iteration 1.

ACKNOWLEDGEMENT

We wish to express all our gratitude to people at Thales for helping us understanding their system and evaluating our results.


Damien Chablat
email: chablat@cim.mcgill.ca

Philippe Wenger
email: philippe.wenger@lan.ec-nantes.fr

REGIONS OF FEASIBLE POINT-TO-POINT TRAJECTORIES IN THE CARTESIAN WORKSPACE OF FULLY-PARALLEL MANIPULATORS

The goal of this paper is to define the n-connected regions in the Cartesian workspace of fully-parallel manipulators, i.e. the maximal regions where it is possible to execute pointto-point motions. The manipulators considered in this study may have multiple direct and inverse kinematic solutions. The N-connected regions are characterized by projection, onto the Cartesian workspace, of the connected components of the reachable configuration space defined in the Cartesian product of the Cartesian space by the joint space. Generalized octree models are used for the construction of all spaces. This study is illustrated with a simple planar fully-parallel manipulator.

INTRODUCTION

The Cartesian workspace of fully-parallel manipulators is generally defined as the set of all reachable configurations of the moving platform. However, this definition is misleading since the manipulator may not be able to move its platform between two prescribed configurations in the Cartesian workspace. This feature is well known in serial manipulators when the environment includes obstacles (Wenger,91). For fully-parallel manipulators, point-to-point motions may be infeasible even in obstaclefree environments. For manipulators with one unique solution to their inverse kinematics (like Gough-platforms), one configuration of the moving platform is associated with one unique joint configuration and the connected-components of the singularityfree regions of the Cartesian workspace are the maximal regions of point-to-point motions (Chablat,98a). Unfortunately, this re-sult does not hold for manipulators which have multiple solutions to both their direct and inverse kinematics. For such manipulators which are the subject of this study, the singularity locus in the Cartesian workspace depends on the choice of the inverse kinematic solution (Chablat,97) and the actual reachable space must be firstly defined in the Cartesian product of the Cartesian space by the joint space. The goal of this paper is to define the N-connected regions in the Cartesian workspace of fully-parallel manipulators, i.e., the maximal regions where it is possible to execute any point-to-point motion. The N-connected regions are characterized by projection, onto the Cartesian space, of the connected components of the manipulator configuration space defined in the Cartesian product of the Cartesian space by the joint space. Generalized Octree models are used for the construction of all spaces. This study is illustrated with a simple planar fullyparallel manipulator.

Preliminaries

Some useful definitions are recalled in this section.

Fully-parallel manipulators Definition 1.

A fully-parallel manipulator is a mechanism that includes as many elementary kinematic chains as the moving platform does admit degrees of freedom. In addition, every elementary kinematic chain possesses only one actuated joint (prismatic, pivot or kneecap). Besides, no segment of an elementary kinematic chain can be linked to more than two bodies (Merlet,97).

In this study, kinematic chains, also called "leg" (Angeles,97), will be always independent.

Kinematics

The input vector q (the vector of actuated joint values) is related to the output vector X (the vector of configuration of the moving platform) through the following general equation :

F(X, q) = 0 (1)
Vector (X, q) will be called manipulator configuration and X is the platform configuration and will be more simply termed configuration. Differentiating equation ( 1) with respect to time leads to the velocity model

At + B q = 0 (2)
With t = [w, ċ] T , for planar manipulators (w is the scalar angularvelocity and ċ is the two-dimensional velocity vector of the operational point of the moving platform), t = [w] T , for spherical manipulators and t = [w, ċ] T , for spatial manipulators (ċ is the three-dimensional velocity vector and ẇ is the three-dimensional angular velocity-vector of the operational point of moving platform). Moreover, A and B are respectively the direct-kinematics and the inverse-kinematics matrices of the manipulator. A singularity occurs whenever A or B, (or both) can no longer be inverted. Three types of singularities exist (Gosselin,90):

det(A) = 0 det(B) = 0 det(A) = 0 and det(B) = 0

Parallel singularities

Parallel singularities occur when the determinant of the direct kinematics matrix A vanishes. The corresponding singular configurations are located inside the Cartesian workspace. They are particularly undesirable because the manipulator can not resist any effort and control is lost.

Serial singularities

Serial singularities occur when the determinant of the inverse kinematics matrix B vanishes. By definition, the inversekinematic matrix is always diagonal: for a manipulator with n degrees of freedom, the inverse kinematic matrix B can be written like in equation (3). Each term B j j is associated with one leg.

A serial singularity occurs whenever at least one of these terms vanishes.

B = Diag [B 11 , ..., B j j , ..., B nn ] (3)
When the manipulator is in serial singularity, there is a direction along which no Cartesian velocity can be produced.

Postures

The postures are defined for fully-parallel manipulators with multiple inverse kinematic solutions (Chablat,97). Let W be the reachable Cartesian workspace, that is, the set of all reachable configurations of the moving platform ( (Kumar,92) and (Pennock, 93)). Let Q be the reachable joint space, that is, the set of all joint vectors reachable by the actuated joints.

Definition 2. For a given configuration X in W , a posture is defined as a solution to the inverse kinematics of the manipulator.

According to the joint limit values, all postures do not necessarily exist. Changing posture is equivalent to changing the posture of one or several legs.

Point-to-point trajectories

There are two major types of tasks to consider : point-topoint motions and continuous path tracking. Only point-to-point motions will be considered in this study.

Definition 3. A point-to-point trajectory T is defined by a set of p configurations in the Cartesian workspace : T

= {X 1 , ..., X i , ...., X p }.
By definition, no path is prescribed between any two configurations X i and X j .

Hypothesis : In a point-to-point trajectory, the moving platform can not move through a parallel singularity.

Although it was shown recently that in some particular cases a parallel singularity could be crossed (Nenchev,97), hypothesis 1 is set for the most general cases.

A point-to-point trajectory T will be feasible if there exists a continuous path in the Cartesian product of the Cartesian space by the joint space which does not meet a parallel singularity and which makes the moving platform pass through all prescribed configurations X i of the trajectory T .

Remark : A fully-parallel manipulator with several inverse kinematic solutions can change its posture between two prescribed configurations. Such a manoeuver may enable the manipulator to avoid a parallel singularity (Figure 1). More generally, the choice of the posture for each configuration X i of the trajectory T can be established by any other criteria like stiffness or cycle time (Chablat,98b). Note that a change of posture makes the manipulator run into a serial singularity, which is not redhibitory for the feasibility of point-to-point trajectories.

The generalized octree model

The quadtree and octree models are hierachical data structures based on a recursive subdivision of the plane and the space, respectively (Meagher,81). There are useful for representing complex 2-D and 3-D shapes. In this paper, we use a generalization of this model to dimension k, with k > 3, the 2 k -tree (Chablat,98a). This model is suitable for Boolean operations like union, difference and intersection. Since this structure has an implicit adjacency graph, path-connectivity analyses and trajectory planning can be naturally achieved.

When k > 3, it is not possible to represent graphically the 2 k -tree. It is necessary to project this structure onto a lower dimensional space (quadtree or octree). For a n-dof fully-parallel manipulator, the Cartesian product of the Cartesian space by the joint space defines generalized octree with dimension 2n. When n = 3 (respectively n = 2), the projection onto the Cartesian space and the joint space yields octree models (respectively quadtree models).

2 The moveability in the Cartesian workspace Definition 4. The N-connected regions of the Cartesian workspace are the maximal regions where any point-to-point trajectory is feasible.

For manipulators with multiple inverse and direct kinematic solutions, it is not possible to study the joint space and the Cartesian space separately. First, we need to define the regions of manipulator reachable configurations in the Cartesian product of the Cartesian space by the joint space W.Q.

Definition 5. The regions of manipulator reachable configurations R j are defined as the maximal sets in

W.Q such that R j ∈ W.Q, R j is connected, R j = {X, q} such that det(A) = 0
In other words, the regions R j are the sets of all configurations (X, q) that the manipulator can reach without meeting a parallel singularity and which can be linked by a continuous path in W.Q.

Proposition : A trajectory T = {X 1 , ..., X p } defined in the Cartesian workspace W is feasible if and only if :

∀X ∈ {X 1 , ..., X p } ∃q i ∈ Q, ∃R j such that (X i , q i ) ∈ R j
In other words, for each configuration X i in T , there exists at least one posture q i and one region of manipulator reachable configurations R j such that the manipulator configuration (X i , q) is in R j .

Proof : Indeed, if for all configurations X i , there is one joint configuration q i such that (X i , q i ) ∈ R j then the trajectory is feasible because, by definition, a region of manipulator reachable configurations is connected and free of parallel singularity. Conversely, if for a given configuration X i , it is not possible to find a posture q i such that (X i , q i ) ∈ R j , then no continuous, parallel singularity-free path exists in W.Q which can link the other prescribed configurations.

Theorem : The N-connected regions W N j are the projection Π W of the region of manipulator reachable configurations R j onto the Cartesian space :

W N j = Π W R j
Proof : This results is a straightforward consequence of the above proposition.

The N-connected regions cannot be used directly for planning trajectories in the Cartesian workspace since it is necessary to choose one joint configuration q for each configuration X of the moving platform such that (X, q) is included in the same region of manipulator reachable configurations R j . However, the N-connected regions provide interesting global information with regard to the performances of a fully-parallel manipulators because they define the maximal regions of the Cartesian workspace where it is possible to execute any point-to-point trajectory.

A consequence of the above theorem is that the Cartesian workspace W is N-connected if and only if there exists a Nconnected region W N j which is coincident with the Cartesian workspace :

W N j = W

Example: A Two-DOF fully-parallel manipulator

For more legibility, a planar manipulator is used as illustrative example in this paper. This is a five-bar, revolute (R)closed-loop linkage, as displayed in figure 2. The actuated joint variables are θ 1 and θ 2 , while the Output values are the (x, y) coordinates of the revolute center P. The passive joints will always be assumed unlimited in this study. Lengths L 0 , L 1 , L 2 , L 3 , and L 4 define the geometry of this manipulator entirely. The dimensions are defined in table 1 in certain units of length that we need not specify.

y A P(x, y) B x q 2 D C L 3 q 1 L 4 L 2 L 1 L 0 Figure 2. A two-dof fully-parallel manipulator L 0 L 1 L 2 L 3 L 4 θ 1min θ 1max θ 2min θ 2max 7 8 5 8 5 0 π 0 π Table 1. The dimensions of the RR-RRR studied
As shown in table 1, the actuated joints are limited. The Cartesian workspace is shown in figure 3. We want to know whether this manipulator can execute any point-to-point motion in the Cartesian workspace. To answer this question, we need to determine the the N-connected regions.

Singularities

For the manipulator studied, the parallel singularities occur whenever the points C, D, and P are aligned (Figure 4). Manipulator postures whereby θ 3 -θ 4 = kπ denote a singular matrix A, and hence, define the boundary of the joint space of the manipulator. For the manipulator at hand, the serial singularities occur

Postures

The manipulator under study has four postures, as depicted in figure 6. According to the posture, the parallel singularity locus changes in the Cartesian workspace, as already shown in figure 1.

The N-connected regions

It turns out that the Cartesian workspace of the manipulator at hand is not N-connected, e.g. the manipulator cannot move its platform between any set of configurations in the Cartesian workspace. In effect, due to the existence of limits on the actuated joints, not all postures are accessible for any configuration in the Cartesian workspace. Thus, the manipulator may loose its ability to avoid a parallel singularity when moving from one configuration to another. This is what happens between points X 1 and X 2 (Figure 3). These two points cannot be linked by the manipulator although they lie in the Cartesian workspace which is connected in the mathematical sense (path-connected) but not N-connected. In fact, there are two separate N-connected regions which do not coincide with the Cartesian workspace and the two points do not belong to the same N-connected region (Figures 7 and8). Physically, any attempt in moving the point P from X 1 to X 2 will cause the manipulator either cross a parallel singularity or reach a joint limit.

In effect, point X 1 is accessible only in the manipulator configuration shown in figure 9a because of the joint limits. When moving towards point X 4 , the manipulator cannot remain in its initial posture because it would meet a parallel singularity (Figure 9b). Thus, it must change its posture, let say at X 3 (Figure 9c). The only new posture which can be chosen is the one depicted in figure 9d because any other posture would make the manipulator meet a parallel singularity (Figure 9e). Then, it is apparent that the manipulator cannot reach X 1 from X 4 since joint A attains its limits (figure 9f).

If we change the values of the joint limits (θ 1min = θ 2min = -π), the Cartesian workspace is now N-connected since the

Conclusions

The aim of this paper was the characterization of the Nconnected regions in the Cartesian workspace of fully-parallel manipulators, i.e. the regions of feasible point-to-point trajectories. The word feasible means that the manipulator should be able to move between all prescribed configurations while never meeting a parallel singularity. The manipulators considered in this study have multiple solutions to their direct and inverse kinematics. The N-connected regions were defined by first determining the maximum path-connected, parallel singularity-free regions in the Cartesian product of the Cartesian workspace by the joint space. The projection of these regions onto the Cartesian workspace were shown to define the N-connected regions.

The N-connectivity analysis of the Cartesian workspace is of high interest for the evaluation of manipulator global performances as well as for off-line task programming.

Further research work is being conducted by the authors to take into account the collisions and to characterize the maximum regions of the Cartesian workspace where the manipulator can track any continuous trajectory.

Figure 1 .

 1 Figure 1. Singular (left) and a regular (right) configurations (the actuated joints are A and B)

  Figure 3. The Cartesian workspace

Figure 4 .

 4 Figure 4. Example of parallel singularity

Figure 6 .

 6 Figure 6. The four postures

Figure 7 .

 7 Figure 7. The first N-connected region of the Cartesian workspace when 0.0 ≤ θ 1 , θ 2 ≤ π

Figure 8 .Figure 9 .

 89 Figure 8. The second N-connected region of the Cartesian workspace when 0.0 ≤ θ 1 , θ 2 ≤ π

Figure 10 .

 10 Figure 10. The N-connected regions of the Cartesian workspace when -π ≤ θ 1 , θ 2 ≤ π