Effects of pyrolytic and petrogenic polycyclic aromatic hydrocarbons on swimming and metabolic performance of zebrafish contaminated by ingestion

Keywords: trophic exposition, petroleum hydrocarbons, critical swimming speed, aerobic metabolic rate, sub-lethal concentration

Depending on their origins, polycyclic aromatic hydrocarbons (PAH) are characterized by different chemical properties. Petrogenic PAH (e.g. from fossil fuels) and pyrolytic PAH (e.g. those produced by incineration processes) are therefore expected to affect organisms differently. The impact of trophic exposure to these PAH was investigated on swimming and metabolic performance of zebrafish Danio rerio. Two-month-old juveniles and six-month-old adults were individually challenged following a swimming step protocol. While pyrolytic exposure did not affect fish whatever the duration of exposure, it appeared that petrogenic PAH impaired adults' performance. Indeed, the active metabolic rate in petrogenic PAHcontaminated adults was significantly reduced by 35%, and critical swimming speed by 26.5%. This was associated with cardiac abnormalities, which are expected to contribute to the reduction of oxygen transport, particularly during intensive effort. These results may be due to the different composition and toxicity of PAH mixtures.

Introduction

Locomotion performance in fish is considered to be a relevant biological function contributing to survival (e.g. [START_REF] Graham | Aspects of shark swimming performance determined using a large water tunnel[END_REF][START_REF] Jones | Evaluation of the swimming performance of several fish species from the Mackenzie River[END_REF][START_REF] Plaut | Critical swimming speed: its ecological relevance[END_REF][START_REF] Stobutzki | An analysis of the sustained swimming abilities of preand post-settlement coral reef fishes[END_REF][START_REF] Swanson | Swimming performance of Delta smelt: maximum performance, and behavioral and kinematic limitations on swimming at submaximal velocities[END_REF], since it is related to predator-prey interactions, food research and migration [START_REF] Drucker | Pectoral fin locomotion in the striped surfperch. I. Kinematics effects of swimming speed and body size[END_REF][START_REF] Hammer | Fatigue and exercise tests with fish[END_REF][START_REF] Plaut | Critical swimming speed: its ecological relevance[END_REF][START_REF] Reidy | Postexercise metabolic rate in Atlantic cod (Gadus morhua) and its dependence upon the method of exhaustion[END_REF][START_REF] Videler | Fish Swimming[END_REF][START_REF] Walker | Do faster starts increase the probability of evading predators?[END_REF][START_REF] Watkins | Predator-mediated selection on burst swimming performance in tadpoles of the Pacific tree frog, Pseudacris regilla[END_REF]). Critical swimming speed (i.e.

the maximal velocity a fish can reach during a swimming step protocol, U crit ;[START_REF] Hammer | Fatigue and exercise tests with fish[END_REF] is frequently employed as an indicator of swimming capacities in a varying environment (e.g. [START_REF] Beamish | Swimming capacity[END_REF]. Since U crit notably depends on the maximal ability of fish to provide energy during sustained swimming activity, these studies are often associated with the assessment of metabolic performance, which contribute to a better view of the environmental impact.

Aerobic metabolic scope (AMS; [START_REF] Brett | The respiratory metabolism and swimming performance of young sockeye salmon[END_REF][START_REF] Fry | The effects of the environment on animal activity[END_REF][START_REF] Fry | The effect of environmental factors on the physiology of fish[END_REF]) is defined as the difference between (i) the active metabolic rate (AMR), which is the highest metabolic rate the organism can sustain under maximal activity and (ii) the standard metabolic rate (SMR), the metabolic rate necessary to maintain vital functions and measured under resting conditions. Metabolic and swimming performance are known to be modulated by a set of environmental parameters, such as temperature [START_REF] Blier | Does aerobic capacity set a limit on fish growth rate?[END_REF][START_REF] Farrell | Cardiorespiratory performance during prolonged swimming tests with salmonids: a perspective on temperature effects and potential analytical pitfalls[END_REF][START_REF] Rome | The effect of temperature and thermal acclimation on the sustainable performance of swimming scup[END_REF], dissolved oxygen [START_REF] Diaz | Overview of hypoxia around the world[END_REF][START_REF] Diaz | A global perspective on the effects of eutrophication and hypoxia on aquatic biota[END_REF] or pollutants [START_REF] Johansen | Increasing ocean temperature reduces the metabolic performance and swimming ability of coral reef damselfishes[END_REF][START_REF] Lefrançois | Influence of ambient oxygenation and temperature on metabolic scope and scope for heart rate in the common sole Solea solea[END_REF][START_REF] Marit | Persistent effects on adult swim performance and energetics in zebrafish developmentally exposed to 2,3,7,8-tetrachlorodibenzo-p-dioxin[END_REF][START_REF] Shingles | Effects of sublethal ammonia exposure on swimming performance in rainbow trout (Oncorhyncus mykiss)[END_REF][START_REF] Schurmann | Effects of temperature, hypoxia and activity on the metabolism of juvenile Atlantic cod[END_REF][START_REF] Thomas | Effects of chronic dietary selenomethionine exposure on repeat swimming performance, aerobic metabolism and methionine catabolism in adult zebrafish (Danio rerio)[END_REF].

This study aimed at investigating responses of fish exposed to environmentally relevant concentrations of PAH through the assessment of AMS and U crit as indicators of the physiological state of the organism [START_REF] Fry | The effects of the environment on animal activity[END_REF]. The increase of anthropogenic activities in coastal areas induces discharges of PAH in aquatic ecosystems. Due to their high liposolubility, PAH are typically adsorbed by organic matter or marine sediments, bioaccumulated by organisms at the lowest trophic levels (e.g. invertebrates; [START_REF] Bustamante | Bioaccumulation and metabolisation of 14C-pyrene by the Pacific oyster Crassostrea gigas exposed via seawater[END_REF][START_REF] O'connor | Trends in chemical concentrations in mussels and oysters collected along the US coast: update to 2003[END_REF] and transferred through trophic chains [START_REF] Hylland | Polycyclic aromatic hydrocarbon (PAH) ecotoxicology in marine ecosystems[END_REF][START_REF] Vignet | Chronic exposures to pyrolytic and petrogenic mixtures of PAHs through diet produce physiological disruptions in zebrafish -Part I: Survival and growth[END_REF]. Past studies on fish have demonstrated that hydrocarbon exposure causes a decrease of U crit . For instance, Danio rerio showed a 15% and 22% reduction of U crit while exposed to crude oil (Hicken et al., 2011) and TCDD (2,3,7,8-tetrachlorodibenzo-p-dioxin;[START_REF] Marit | Persistent effects on adult swim performance and energetics in zebrafish developmentally exposed to 2,3,7,8-tetrachlorodibenzo-p-dioxin[END_REF], respectively. Moreover, PAH could induce damage of tissues and/or organs involved in oxygen transport (e.g. fish gills, [START_REF] Fasulo | Toxicity of Foroozan crude oil to ornate wrasse (Thalassoma pavo, Osteichthyes, Labridae): ultrastructure and cellular biomarkers[END_REF]mussel gills, Cappello et al., 2013). This could induce a decrease of AMR as observed by [START_REF] Davoodi | Effects of exposure to petroleum hydrocarbons upon the metabolism of the common sole Solea solea[END_REF] after acute PAH exposure of Solea solea. In addition, the implementation of detoxification processes which are energy costly have already been demonstrated. These processes are likely to increase costs of maintenance and, consequently, SMR. The consequent potential reduction of AMS would reflect a decrease in the capacity of fish to sustain energy-demanding activities.

The effects of PAH mixtures were tested on zebrafish Danio rerio (F. Hamilton, 1822) contaminated by ingestion. Both pyrolytic PAH (PY-PAH, resulting from the combustion of organic matter) and petrogenic PAH (HO-PAH, originated from fossil fuels; [START_REF] Hylland | Polycyclic aromatic hydrocarbon (PAH) ecotoxicology in marine ecosystems[END_REF] were considered in the present study. Present as complex mixtures in the environment, PY-PAH and HO-PAH show different chemical properties and may induce various effects on aquatic life. The main hypothesis was that chronic exposure to PY-PAH and HO-PAH would impair AMS by increasing SMR and/or reducing AMR. The consequent potential reduction of AMS would indicate a decrease in the capacity of the fish to support oxygen-demanding activities beyond SMR and consequently a reduction of U crit . In addition, PAH may induce anatomic impairments due to teratogenic effects [START_REF] Hawkins | Carcinogenic effects of some polycyclic aromatic hydrocarbons on the Japanese medaka and guppy in waterborne exposures[END_REF][START_REF] Myers | Related lesions and exposure to relationships between hepatic neoplasms toxic chemicals in marine fish from the U.S. West Coast[END_REF].

Swimming and metabolic functions were explored, as well as the cardiac and skeletal muscle structures, as two key tissues involved the tested functions.

Materials and methods

General production of zebrafish

Pairs of zebrafish (wild-type Tuebingen strain, TU) were reared together in 10 L tanks in the laboratory. Aquaria were filled with a mix of osmosis and filtered tap water which was characterized by the following parameters: temperature 28 ± 0.5 °C, conductivity 300 ± 50 µS.cm -1 , oxygen saturation ≥ 80%, pH 7.5 ± 0.5. Fish were reared with a photoperiod of 14 h light/10 h dark. Ammonia, nitrite and nitrate remained within recommended ranges [START_REF] Lawrence | The husbandry of zebrafish (Danio rerio): a review[END_REF]. The fish were fed twice daily with uncontaminated commercial dry food (INICIO Plus, BioMar, France) and once by Artemia sp. nauplii (Ocean Nutrition, Belgium), occasionally supplemented with red sludge worms (Boschetto, Poland).

Over a period of one month, spawn was obtained from pairs weekly following the protocol described in Lucas et al. (2014a) and [START_REF] Vignet | Chronic exposures to pyrolytic and petrogenic mixtures of PAHs through diet produce physiological disruptions in zebrafish -Part I: Survival and growth[END_REF]. Briefly, the day before spawn was collected, these fish couples were isolated in 1 L breeding tanks (Aqua Schwarz, Germany).

After collection, fertilized and normally developed eggs were selected using a binocular microscope. Spawn was then mixed to avoid any parental influence. From 2 weeks onwards, fish were kept in groups of 30 individuals in 10 L aquaria in the same specific rearing system described above.

Food contamination protocol

Artificial dry food (INICIO Plus, BioMar France) was spiked with mixtures of PAH as described in detail by [START_REF] Vignet | Chronic exposures to pyrolytic and petrogenic mixtures of PAHs through diet produce physiological disruptions in zebrafish -Part I: Survival and growth[END_REF]. Briefly, the pyrolytic fraction (PY) was extracted from natural sediment sampled at the site of Oissel (Seine Bay, France), while the petrogenic fraction (HO) was extracted from heavy Erika fuel oil. For both types of PY and HO mixtures, quantification of the 16 individual PAH of the US EPA list was made, according to a protocol described in [START_REF] Budzinski | Evaluation of sediment contamination by polycyclic aromatic hydrocarbons in the Gironde estuary[END_REF] and [START_REF] Cachot | Characterization of toxic effects of sediment-associated organic pollutants using the lambda transgenic medaka[END_REF]. The food was then spiked with the extracted PY or HO fractions according to a protocol adapted from [START_REF] Vicquelin | A new spiked sediment assay using embryos of the Japanese medaka specifically designed for a reliable toxicity assessment of hydrophobic chemicals[END_REF].

The target concentration was 15000 ng.g -1 of food and based on the sum of the 16 PAH from the US EPA list in dry weight. This corresponds to three times the PAH concentration organisms may be exposed to in their natural environment [START_REF] Cachot | Evidence of genotoxicity related to high PAH content of sediments in the upper part of the Seine estuary (Normandy, France)[END_REF][START_REF] Cailleaud | Seasonal variations of hydrophobic organic contaminant concentrations in the water-column of the Seine Estuary and their transfer to a planktonic species Eurytemora affinis (Calanoida, copepoda). Part 1: PCBs and PAHs[END_REF][START_REF] Payne | Long term monitoring for oil in the Exxon Valdez spill region[END_REF]. This high concentration was used to highlight the toxicological effects on the physiological performances investigated in this study. It is called X in the rest of the manuscript. Food size was adapted to the developmental stage of D. rerio. A control treatment was also considered, and consisted of feeding groups of fish with uncontaminated food, treated only by the solvent dichloromethane. This solvent was used to improve PAH incorporation into the food, and then evaporated. PAH compositions and concentrations in the diet are described in detail in Table 1.

Zebrafish PAH exposure protocol

Contamination through food was conducted by feeding zebrafish larvae twice a day with one of the treatments (i.e. control and X for both types of contamination PY and HO). The diet started from the first meal (5 days post fertilization, dpf) until the age at the test: 2 months and 6 months for juveniles and adults, respectively. In accordance with the protocols in [START_REF] Vignet | Chronic exposures to pyrolytic and petrogenic mixtures of PAHs through diet produce physiological disruptions in zebrafish -Part I: Survival and growth[END_REF], larvae were fed ad libitum and then, starting from 2 months old, the ration of food was decreased by 5% to 2% of the biomass in each tank in order to maintain constant growth.

For all fish, brine shrimp were distributed as complementary food once a day.

PY exposure took place during the second semester of 2011 and HO exposure was carried out in summer 2013. Quantification of hydroxylated metabolites in larvae at 15 dpf indicated a dose-dependent increase of metabolites, confirming successful contamination (total concentrations of hydroxylated metabolites for PY-PAH: control = 9.1 ng.g -1 of tissue, X = 275 ng.g -1 ; [START_REF] Vignet | Chronic exposures to pyrolytic and petrogenic mixtures of PAHs through diet produce physiological disruptions in zebrafish -Part I: Survival and growth[END_REF].

For the X treatment tested, the average concentrations found were 136 ng.g -1 for PY larvae and 42 ng.g -1 for HO larvae, while it was 2 or 4 ng.g -1 in the PY and HO control fish, respectively [START_REF] Vignet | Chronic exposures to pyrolytic and petrogenic mixtures of PAHs through diet produce physiological disruptions in zebrafish -Part I: Survival and growth[END_REF]). It appears that PAH concentration is higher for PY than for HO.

Aerobic metabolic scope and critical swimming speed 2.4.1. Experimental set-up

For both types of contamination (i.e. PY-and HO-PAH), two identical 170 mL swimming respirometers (Loligo Systems, Denmark) were used to assess the swimming and metabolic performance of fish. Each swimming respirometer was composed of (a) a swimming chamber, where the fish was placed to be tested, (b) a motor fitted with a three-bladed propeller to control water flow and (c) honeycomb placed at each side of the swimming chamber to laminarize the water flow. Each swimming respirometer was submerged in a 20 L buffer tank, and filled with temperature-controlled (i.e. 28 °C) and oxygenated mixed water as in the rearing system. The oxygen consumption (MO 2 in mg O 2 .g -1 .h -1 ) associated with the activity of fish was measured by intermittent-flow respirometry [START_REF] Steffensen | Some errors in respirometry of aquatic breathers: how to avoid and correct for them[END_REF]. Water supply in each swimming respirometer was provided by flush pumps, which controlled water flow from the buffer tank to the swimming respirometer. This allowed alternation between phases of oxygen renewal and phases of MO 2 measurement with a cycle of 5 : 20 min. In addition, a peristaltic pump was used to create a continuous water flow from the respirometer to the oxygen probe (flow through an oxygen minisensor, PreSens, Germany). The probe was connected to an oxymeter (Microx, PreSens, Germany) to record the level of dissolved oxygen in the water every 5 s. The probe was calibrated once at the beginning of the swim test using 0% and 100% air saturation for a controlled temperature of 28 °C.

Experimental protocol

The fish were starved 24 h before being transferred individually to a swimming respirometer.

They were then individually submitted to a swimming challenge. Each experimental trial consisted of challenging two fish in parallel exposed to one of three treatments: (i) fish fed by the control food and (ii) fish exposed to PY-or HO-PAH. Each individual was submitted to a short acclimation swimming period (~5 min) during which the velocity was increased to 2 body lengths per second (BL.s -1 ). Then, fish were left undisturbed with a water flow of 0.5 BL.s -1 for 2 h to permit recovery from handling stress. The swimming challenge started by increasing water flow by steps of 1.5 BL.s -1 from 0.5 to 6.5 BL.s -1 and steps of 0.75 BL.s -1 to the end of the test. Each step lasted 20 min, during which fish MO 2 was measured. The experiment stopped when the fish fatigued, i.e. when it did not manage to swim against the current and stay on the honeycomb. Speed was then decreased to 0.5 BL.s -1 for a recovery period of 1.5 h. Fish were then removed from the swimming respirometer and anaesthetized using benzocaine (50 mg.L -1 ). Standard and total length, mass and sex of each individual were determined; characteristics of the fish tested in the swim tunnel are described in Table 2.

Before and after each trial, a blank measurement was performed to quantify microbial oxygen consumption in the swimming respirometer. The average of these two values was subtracted from the measured oxygen consumption. Each fish was tested once.

Calculations

Critical swimming speed

The critical swimming speed U crit was calculated according to the formula of [START_REF] Brett | The respiratory metabolism and swimming performance of young sockeye salmon[END_REF]:

U crit = U t + t 1 .t -1 .U 1 Equation (1)
Where U t (in BL.s -1 ) is the highest velocity maintained for an entire step, t 1 (in min) is the time spent until the exhaustion of fish at the last step, t (in min) is the swimming period for each step (i.e. 20 min in the present study) and U 1 is the increment velocity (0.75 or 1.5 BL.s -1 ).

Oxygen consumption (MO 2 )

Oxygen consumption MO 2 is expressed in mg O 2 .g -1 .h -1 and calculated using the following formula:

MO 2meas = Δ[O 2 ].V.Δt -1 .M meas -1 Equation (2)
where Δ[O 2 ] (in mg O 2 .L -1 ) is the variation in oxygen concentration during the measurement period Δt (in h), V (in L) is the volume of the respirometer minus the volume of the fish and M meas (in g) is the fish mass measured.

An allometric relationship exists between oxygen consumption and body mass, which permits correction of MO 2meas using the following formula:

MO 2cor = MO 2meas .(M meas .M cor -1 ) 1-b Equation (3)
where MO 2cor (in mg O 2 .g -1 .h -1 ) is the oxygen consumption related to a standard fish of 1 g (M cor ), MO 2meas (in mg O 2 .g -1 .h -1 ) is the oxygen consumption estimated for experimental fish whose mass was M meas (in g) and b is the allometric scaling exponent describing the relationship between oxygen consumption and body mass. A previous study of Lucas et al.

(2014a) estimated b in zebrafish D. rerio from the relationship between AMR and body mass, i.e. b AMR , and from the relationship between SMR and body mass, i.e. b SMR . We used b AMR = 0.926 for the correction of AMR and b SMR = 0.965 for the correction of SMR.

Standard metabolic rate, active metabolic rate and aerobic metabolic scope

Oxygen consumption is known to increase exponentially with swimming speed [START_REF] Brett | The respiratory metabolism and swimming performance of young sockeye salmon[END_REF].

The following equation can be therefore fitted on data and allows the assessment of SMR:

MO 2 = SMR.exp bU Equation ( 4)

where MO 2 is the oxygen consumption (in mg O 2 .g. -1 .h -1 ), SMR is the intercept (i.e. the MO 2 when U = 0 BL.s -1 ), b is a constant and U is the swimming speed (in BL.s -1 ).

AMR is evaluated as the maximum oxygen consumption measured during the swimming challenge. AMS is the difference between AMR and SMR. U crit , SMR, AMR and AMS were assessed for each fish except for HO-PAH-exposed juveniles. No SMR data were indeed recorded for these individuals, because of the small size of the fish (relative to the swim tunnel volume) and the low quality of the oxygen signal. The HO exposure impaired the growth of fish exposed to [START_REF] Vignet | Chronic exposures to pyrolytic and petrogenic mixtures of PAHs through diet produce physiological disruptions in zebrafish -Part I: Survival and growth[END_REF]) and consequently HO-PAH-exposed juveniles were smaller than PY-PAH-exposed juveniles (Table 2).

Histological analysis

Analysis occurred after the swimming challenge, in older fish: 3-month-old juveniles for both types of contamination, 9-month-old adults for PY-PAH and 7-month-old adults for HO-PAH.

A total of 20 juveniles per treatment (i.e. control and X) were analysed for PY-and HO-PAH exposure. In adults, 30 fish per treatment were observed for PY-PAH, and 25 fish were observed for HO-PAH. Fish were euthanized with a lethal dose of benzocaine (100 mg.l -1 ; Sigma-Aldrich), fixed in 4 % formalin for 2 weeks, dehydrated and embedded in paraffin wax [START_REF] Daouk | Long-term food-exposure of zebrafish to PCB mixtures mimicking some environmental situations induces ovary pathology and impairs reproduction ability[END_REF]. For each fish, 4 serial 4 µm-thick sections spaced from from about 250 µm, were routinely stained with haematoxylin-eosin-saffron (HES). The histological appearance of cardiac and skeletal muscles of fish was then observed using a a bright-field microscope (Nikon Eclipse 90i, Champigny, France) equipped with 2X, 4X, 10X, 20X and 40X objectives and a SPOT digital camera (AZ microscope, London, UK). Lesions were systematically recorded by a skilled veterinary pathologist (member of the the European College of Veterinary Pathologists).

Statistical analysis

Statistical analysis was carried out using GraphPad Prism software. For AMR, SMR, AMS and U crit , normality and homoscedasticity were checked using Kolmogorov-Smirnoff and Bartlett tests, respectively, for each duration of exposure and for each type of contamination (i.e. PY and HO). Student's t-tests were used to compare individuals exposed to the control treatment with individuals exposed to PAH. Chi-square tests were used to compare histological anomalies (i.e. cardiac and skeletal muscle structures) between control fish and those exposed to PY-PAH or HO-PAH. For all tests, the results were considered to be significantly different when p < 0.05.

Results

U crit

Whatever the duration of exposure, no significant difference was found between fish exposed to control or PY-PAH (Student's t-test, degrees of freedom (dof) = 41 and p = 0.34 for juveniles; dof = 26 and p = 0.40 for adults; Fig. 1A). On the contrary, U crit decreased significantly in both HO-PAH-contaminated juveniles and adults compared to controlexposed individuals (Student's t-test: dof = 24 and p = 0.011, dof = 28 and p = 0.01, respectively; Fig. 1B). Xpe=8082.5±305 µg.g -1 of dry food (table 1). U crit was evaluated in juvenile and adults. Results are expressed as mean values ± standard deviation. For a given type of PAHs (PY or HO) and a given duration, * indicates a significant difference in U crit between control and 3X treatment.

Aerobic metabolic scope, standard and active metabolic rate

For PY-PAH contamination, no significant difference was found between contaminated fish and the control whatever the metabolic rate observed: SMR (Fig. In D. rerio which ingested HO-PAH-contaminated food, the lack of SMR data for juveniles did not allow estimation of SMR and AMS for this stage. In adults, SMR did not differ significantly between control and contaminated fish (Fig. 2B; Student's t-test: dof = 27 and p = 0.35). On the contrary, AMR was significantly impaired, but only in adults (Student's t-test: dof = 20 and p = 0.43, dof = 27 and p = 0.006, for juveniles and adults, respectively; Fig. 2B), as was AMS (Student's t-test: dof = 27 and p = 0.003).

Histological analysis

During histopathological examination, no anomalies were observed in skeletal muscle for either PY-or HO-PAH exposure. While no heart damage was observed for PY-PAH exposure, 4 out of 25 fish exposed to HO-PAH for 7 months displayed generalized oedema that severely thickened the peritoneum all around the abdominal cavity. Significant heart impairments were associated with this oedema: the pericardium appeared dilated with fluid and the heart was very small and rounded with a thin ventricular wall (Fig. 3; chi-square test, dof = 1 and p = 0.002). These lesions are characteristic of cardiac insufficiency with secondary collection of fluid in connective tissue and body cavities. and more rounded heart with a thin ventricular wall), generalized oedema and collection of fluid in body cavities indicating a functional cardiac insufficiency. These lesions may induce a reduction of cardiac performance and capacity to transport oxygen. This may limit aerobic metabolism, especially during high levels of activity, such as occurs during swimming [START_REF] Farrell | Effects of temperature on cardiovascular performance[END_REF][START_REF] Farrell | Cardiorespiratory performance during prolonged swimming tests with salmonids: a perspective on temperature effects and potential analytical pitfalls[END_REF][START_REF] Fry | The effects of the environment on animal activity[END_REF][START_REF] Fry | The effect of environmental factors on the physiology of fish[END_REF][START_REF] Claireaux | Linking swimming performance, cardiac pumping ability and cardiac anatomy in rainbow trout[END_REF][START_REF] Priede | Metabolic scope in fishes[END_REF].

Even if U crit was reduced in HO-PAH juveniles, no impairment of AMR or cardiac function was observed. It is worth noting that U crit depends on both aerobic and anaerobic metabolism [START_REF] Webb | Swimming[END_REF], which could explain the results observed. However, the anaerobic part of the metabolism required to attain U crit was not assessed in the present study, nor was oxygen debt after the swimming test (e.g. [START_REF] Vagner | The effect of acute hypoxia on swimming stamina at optimal swimming speed in flathead grey mullet Mugil cephalus[END_REF]. Indeed, it would have been interesting to assess whether reduction of Ucrit was associated to a different sollicitation of anaerobic metabolism in juveniles and adults' Contrary to the HO-PAH mixture, exposure to PY-PAH did not impair fish metabolic and swimming performance or cardiac anatomy. The lack of effect could be explained by the fact that organisms that suffer long-term chronic environmental stress can present physiological adaptations to maintain their homeostasis. Chronic exposure to PY-PAH may have induced such adaptations in D. rerio.

Whatever the type of exposure, no effect was observed on SMR. The range of observed values are in agreement with previous studies carried out for the same species and with a similar experimental approach (SMR = 0.19 mg O 2 .g -1 .h -1 in [START_REF] Barrionuevo | O 2 consumption and heart rate in developing zebrafish (Danio rerio): influence of temperature and ambient O 2[END_REF]mean ± s.d., SMR = 0.31 ± 0.11 and 0.35 ± 0.16 mg O 2 .g -1 .h -1 in juveniles and adults, respectively, in Lucas et al., 2014a[START_REF] Lucas | Trophic contamination by pyrolytic polycyclic aromatic hydrocarbons does not affect aerobic metabolic scope in zebrafish Danio rerio[END_REF].

Even though the concentration of PAH and their metabolite compounds was not assessed in juveniles and adults in this study, they were estimated in 15 dpf larvae exposed to HO-or PY-PAH, and ranged between 42 ng.g -1 and 136 ng.g -1 , respectively [START_REF] Vignet | Chronic exposures to pyrolytic and petrogenic mixtures of PAHs through diet produce physiological disruptions in zebrafish -Part I: Survival and growth[END_REF].

It is likely that PAH metabolite concentration increased proportionally with the duration of exposure. However, the present results suggest that the level of contamination tested was not sufficiently extreme to induce significant variation in SMR in our experimental conditions., PAH exposure did not induce supplementary costs of maintenance due to detoxification processes in zebrafish [START_REF] Lannig | Temperature-dependent stress response in oysters, Crassostrea virginica: pollution reduces temperature tolerance in oysters[END_REF][START_REF] Lucas | Trophic contamination by pyrolytic polycyclic aromatic hydrocarbons does not affect aerobic metabolic scope in zebrafish Danio rerio[END_REF][START_REF] Sokolova | Interactive effects of metal pollution and temperature on metabolism in aquatic ectotherms: implications of global climate change[END_REF]Wilson et al., 1994), which is contrary to one of the initial hypotheses.

The different impairment of the types of PAH mixture the fish were exposed to could be explained by their different chemical properties depending on the composition of individual PAH [START_REF] Vignet | Chronic exposures to pyrolytic and petrogenic mixtures of PAHs through diet produce physiological disruptions in zebrafish -Part I: Survival and growth[END_REF]. It is worth noting that toxicity depends on individual intrinsic properties of each component and their interactions with enzymatic systems in organisms.

Mainly characterized by four-to six-ring PAH and 5% of methylated compounds, PY-PAH could induce less toxic effects than HO-PAH despite its higher concentration (Table 1).

Indeed, HO-PAH mixtures were characterized by three-and four-ring PAH, and 47% of methylated compounds, which are considered to be more toxic for organisms (Di Giulio and Hinton, 2008;[START_REF] Hall | Anthracene reduces reproductive potential and is maternally transferred during long-term exposure in fathead minnows[END_REF][START_REF] Hylland | Polycyclic aromatic hydrocarbon (PAH) ecotoxicology in marine ecosystems[END_REF][START_REF] Tuvikene | Responses of fish to polyclic aromatic hydrocarbons[END_REF]. In addition, adults that were exposed to PAH for 6 months were therefore expected to contain more PAH metabolites than juveniles, which coped with PAH exposure for only 2 months. This may contribute to the fact that exposure to HO-PAH induced a significant reduction of AMR in adults and not in juveniles. However, this pattern was not observed in juveniles and adults exposed to PY-PAH (Fig. 1B) as well as in the similar study of [START_REF] Lucas | Trophic contamination by pyrolytic polycyclic aromatic hydrocarbons does not affect aerobic metabolic scope in zebrafish Danio rerio[END_REF].

Conclusion

Our results suggest that, contrary to HO-PAH, PY-PAH have no direct effect on aerobic metabolism and swimming performance. Lucas et al. (2014b) have observed impairment of metabolic performance and cardiac activity on the progeny of PY-PAH-contaminated D. rerio parents. The parental effect of PAH exposure appears to be an important subject to study.

This study on swimming performance and associated energetic costs will be completed by investigations regarding escape performance. This type of swimming depends on anaerobic metabolism, as well as on sensorial and locomotion performance. Moreover, interfering with some physiological mechanisms, PAH could be narcotic, inducing lethargic behaviour and impairing the swimming performance of fish [START_REF] Wassenberg | Synergistic embryotoxicity of polycyclic aromatic hydrocarbon aryl hydrocarbon receptor agonists with cytochrome P4501A inhibitors in Fundulus heteroclitus[END_REF]. All these studies will permit a global view of the impact of this type of trophic contamination across zebrafish generations.

Wilson, R.W., Bergman, H.L., Wood, C.M., 1994. Metabolic costs and physiological consequences of acclimation to aluminum in juvenile rainbow trout (Oncorhynchus mykiss). 1: Acclimation specificity, resting physiology, feeding, and growth. Can. J. Fish.

Aquat. Sci. 51, 527-535.

Fig. 1

 1 Fig. 1 Critical swimming speed (U crit ) of zebrafish exposed to control (white bars) or to PAHs from pyrolytic (A) or petrogenic (B) origins (in grey). PAHs concentrations in food was 3X; the environmental reference concentrations X corresponding Xpy=17305±4798µg.g -1 and

  2A; Student's t-test: dof = 32 and p =0.40, dof = 26 and p = 0.46, for juveniles and adults, respectively), AMR (Fig. 2A; Student's t-test: dof = 34 and p = 0.29, dof = 26 and p = 0.44 for juveniles and adults, respectively) and AMS (Student's t-test: dof = 34 and p = 0.29, dof = 26 and p = 0.44 for juveniles and adults, respectively).

Fig. 2 .

 2 Fig. 2. Standard metabolic rate (SMR), active metabolic rate (AMR) and aerobic metabolic scope (AMS) of zebrafish Danio rerio exposed to control food (white bars) containing, pyrolytic (A) or petrogenic (B) PAHs (grey bars). PAH concentrations in food was X; the environmental referenceconcentrations corresponding to Xpy=17305±4798µg.g -1 and Xpe=8082.5±305 µg.g -1 of dry food (table1). Aerobic metabolic rate was estimated at two life stages: juvenile and adults . . Results are expressed as mean values ± standard deviation. For a given type of PAHs (PY or HO) and a given duration, * indicates a significant difference in AMR between control and X treatment.

Fig. 3

 3 Fig. 3 Heart of zebrafish exposed to control condition of food (A) or to PAHs from petrogenic origin (B). Compared to a control fish, some fish exposed to PAHs displayed a large pericardial cavity with a small rounded heart. at: atrium; ba: bulbus arteriosus; p: pericardium; sv: sinus venosus; vt: ventricle. Hemalun-Eosin-Saffron. Bars = 200 µm.

Acknowledgements

The authors are grateful to Didier Leguay and Michel Prineau for their help during the experiment. All experiments were carried out at Ifremer (Plateforme d'Ecophysiologie des Poissons), La Rochelle station, France. This study was financially supported by the ANR project ConPhyPoP (CES 09_002) and JL received a doctoral grant from the Regional Council of Poitou-Charentes. This study was conducted under the approval of the Animal Care Committee of France under the official licence to Marie-Laure Bégout (17-010).

Discussion

Under these experimental conditions and at the two life stages tested, trophic exposure to PAH differently impaired the fish depending on the type of PAH, i.e. PY or HO, and the considered traits. AMR and U crit were indeed influenced by HO-PAH, but SMR was not.

First, for a general comparison, swimming performance data were in the range of what other authors have observed in D. rerio, since average U crit ranged between 10 and 16.5 BL.s -1 in control individuals (e.g. U crit = 13 BL.s -1 in [START_REF] Plaut | Swimming metabolism of wild-type and cloned zebrafish Brachydanio rerio[END_REF]; U crit = 15.5 BL.s -1 in [START_REF] Plaut | Critical swimming speed: its ecological relevance[END_REF]; U crit = 18 BL.s -1 in [START_REF] Palstra | Establishing zebrafish as a novel exercise model: swimming economy, swimming-enhanced growth and muscle growth marker gene expression[END_REF].

AMR values in control fish ranged between 0.9 and 1.6 mg O 2 .h -1 .kg -1 , i.e. 30 to 60 lower compared with other studies in the same species [START_REF] Thomas | Dietary selenomethionine exposure in adult zebrafish alters swimming performance, energetics and the physiological stress response[END_REF], Lucas et al., 2014a[START_REF] Lucas | Trophic contamination by pyrolytic polycyclic aromatic hydrocarbons does not affect aerobic metabolic scope in zebrafish Danio rerio[END_REF]. Such differences observed in AMR estimation could be explained by differences in the general physiological status of the tested zebrafish (e.g. related to age, thermal acclimatization, rearing conditions), as well as in the protocols used. It is also worth noting that [START_REF] Peake | Fatigue is a behavioural response in respirometer confined smallmouth bass[END_REF] underlined the importance of behavioural regulations in assessing fish performance through swimming challenges. They suggested that behaviour, rather than physiological exhaustion, participates in the fatigue observed in fish tested in a swim flume, thereby increasing the variability of the measured parameters (i.e. AMR and U crit ).

Focussing on contamination, HO-PAH exposure induced a significant decrease of 15 and 26.5% of U crit in zebrafish exposed for 2 and 6 months, respectively. A similar pattern was observed in the literature regarding pollutant effects [START_REF] Cheng | Acute and sublethal toxicities of rotenone in juvenile rainbow trout (Oncorhynchus mykiss): swimming performance and oxygen consumption[END_REF][START_REF] Hicken | Sub-lethal exposure to crude oil during embryonic development alters cardiac morphology and reduces aerobic capacity in adult fish[END_REF][START_REF] Howard | Swimming performance of juvenile coho salmon (Oncorhynchus kisutch) exposed to bleached kraft pulpmill effluent[END_REF]Marit andWeber, 2011, 2012;[START_REF] Thomas | Dietary selenomethionine exposure in adult zebrafish alters swimming performance, energetics and the physiological stress response[END_REF]. In HO-PAH adults, this was associated with a significant reduction of AMR, cardiac lesions (i.e. a smaller


On the Kinetostatic Optimization of Revolute-Coupled Planar Manipulators

Proposed in this paper is a kinetostatic performance index for the optimum dimensioning of planar manipulators of the serial type. The index is based on the concept of distance of the underlying Jacobian matrix to a given isotropic matrix that is used as a reference model for purposes of performance evaluation. Applications of the index fall in the realm of design, but control applications are outlined. The paper focuses on planar manipulators, the basic concepts being currently extended to their three-dimensional counterparts.

Introduction

Various performance indices have been devised to asses the kinetostatic performance of serial manipulators. Among these, the concepts of service angle [START_REF] Vinogradov | Details of Kinematics of Manipulators with the Method of Volumes[END_REF], dexterous workspace [START_REF] Kumar | The Workspace of a Mechanical Manipulator[END_REF] and manipulability [START_REF] Yoshikawa | Manipulability of Robotic Mechanisms[END_REF] are worth mentioning. All these different concepts allow the definition of the kinetostatic performance of a manipulator from correspondingly different viewpoints. However, with the exception of Yoshikawa's manipulability index [START_REF] Yoshikawa | Manipulability of Robotic Mechanisms[END_REF], none of these considers the invertibility of the Jacobian matrix. A dimensionless quality index was recently introduced by Lee [START_REF] Lee | A Pratical Quality Index Based on the Octahedral Manipulator[END_REF] based on the ratio of the Jacobian determinant to its maximum absolute value, as applicable to parallel manipulators. This index does not take into account the location of the operation point in the end-effector, for the Jacobian determinant is independent of this location. The proof of the foregoing fact is available in [START_REF] Angeles | Fundamentals of Robotic Mechanical Systems[END_REF], as pertaining to serial manipulators, its extension to their parallel counterparts being straightforward. The condition number of a given matrix is well known to provide a measure of invertibility of the matrix [START_REF] Golub | Matrix Computations[END_REF]. It is thus natural that this concept found its way in this context. Indeed, the condition number of the Jacobian matrix was proposed by Salisbury [START_REF] Salisbury | Articulated Hands: Force Control and Kinematic Issues[END_REF] as a figure of merit to minimize when designing manipulators for maximum accuracy. In fact, the condition number gives, for a square matrix, a measure of the relative roundoff-error amplification of the computed results [START_REF] Golub | Matrix Computations[END_REF] with respect to the data roundoff error. As is well known, however, the dimensional inhomogeneity of the entries of the Jacobian matrix prevents the straightforward application of the condition number as a measure of Jacobian invertibility. The characteristic length was introduced in [START_REF] Angeles | Kinematic Isotropy and the Conditioning Index of Serial Manipulators[END_REF] to cope with the above-mentioned inhomogeneity. Apparently, nevertheless, this concept has found strong opposition within some circles, mainly because of the lack of a direct geometric interpretation of the concept. It is the aim of this paper to shed more light in this debate, while proposing a novel performance index that lends itself to a straightforward manipulation and leads to sound geometric relations. Briefly stated, the performance index proposed here is based on the concept of distance in the space of m × n matrices, which is based, in turn, on the concept of inner product of this space. The performance index underlying this paper thus measures the distance of a given Jacobian matrix from an isotropic matrix of the same gestalt. With the purpose of rendering the Jacobian matrix dimensionally homogeneous, we resort to the concept of posture-dependent conditioning length. Thus, given an arbitrary serial manipulator in an arbitrary posture, it is possible to define a unique length that renders this matrix dimensionally homogeneous and of minimum distance to isotropy. The characteristic length of the manipulator is then defined as the conditioning length corresponding to the posture that renders the above-mentioned distance a minimum over all possible manipulator postures. This paper is devoted to planar manipulators, the concepts being currently extended to spatial ones.

Algebraic Background

Given two arbitrary m × n matrices A and B of real entries, their inner product, represented by (A, B), is defined as

(A, B) ≡ tr(AWB T ) ( 1
)
where W is a positive-definite n × n weighting matrix that is introduced to allow for suitable normalization. The entries of W need not be dimensionally homogeneous, and, in fact, they should not if A and B are not. However, the product AWB T must be dimensionally homogeneous; else, its trace is meaningless. The norm of the space of m × n matrices induced by the above inner product is thus the Frobenius norm, namely,

A 2 = tr(AWA T ) (2a)
Moreover, we shall be handling only nondimensional matrix entries, and hence, we choose W non-dimensional as well, and so as to yield a value of unity for the norm of the n × n identity matrix 1. Hence,

W ≡ 1 n 1 (2b)
The foregoing inner product is thus expressed as

(A, B) ≡ 1 n tr(AB T ) (2c)
Henceforth we shall use only the Frobenius norm; for brevity, this will be simply referred to as the norm of a given matrix.

When comparing two dimensionless m × n matrices A and B, we can define their distance d(A, B) as the Frobenius norm of their difference, namely,

d(A, B) ≡ A -B (3a)
i.e.,

d(A, B) ≡ 1 n tr[(A -B)(A -B) T ] (3b)
An m × n isotropic matrix, with m < n, is one with a singular value σ > 0 of multiplicity m, and hence, if the m × n matrix C is isotropic, then

CC T = σ 2 1 (4)
where 1 is the m × m identity matrix. Note that the generalized inverse of C can be computed without roundoff-error, for it is proportional to C T , namely,

(CC T ) -1 C T = 1 σ 2 C T (5)
Furthermore, the condition number κ(A) of a square matrix A is defined [START_REF] Golub | Matrix Computations[END_REF] as

κ(A) = A A -1 (6)
where any norm can be used. For purposes of the paper, we shall use the Frobenius norm for matrices and the Euclidian norm for vectors. Henceforth we assume, moreover, a planar n-revolute manipulator, as depicted in Fig. 1, with Jacobian matrix J given by Angeles [START_REF] Angeles | Fundamentals of Robotic Mechanical Systems[END_REF]

J =    1 1 • • • 1 Er 1 Er 2 • • • Er n    (7)
where r i is the vector directed from the center of the ith revolute to the operation point P of the end-effector, while matrix E is defined as

E =    0 -1 1 0    (8)
i.e., E represents a counterclockwise rotation of 90 • . It will prove convenient to partition J in the form

J =    A B   
with A and B defined as

A = 1 1 • • • 1 and B = Er 1 Er 2 • • • Er n
Therefore, while the entries of A are dimensionless, those of B have units of length. Thus, the sole singular value of A, i.e. the nonnegative square root of the scalar of AA T , is √ n, and hence, dimensionless, and pertains to the mapping from joint-rates into end-effector angular velocity. The singular values of B, which are the nonnegative square roots of the eigenvalues of BB T , have units of length, and account for the mapping from joint-rates into operationpoint velocity. It is thus apparent that the singular values of J have different dimensions and hence, it is impossible to compute κ(J) as in eq.( 6), for the norm of J, as defined in eqs.(2a & b), is meaningless. The normalization of the Jacobian for purposes of rendering it dimensionless has been judged to be dependent on the normalizing length [START_REF] Paden | Optimal Kinematic Design of 6R Manipulator[END_REF]. As a means to avoid the arbitrariness of the choice of that normalizing length, the characteristic length L was introduced in [START_REF] Ranjbaran | The Mechanical Design of a Seven-Axes Manipulator with Kinematic Isotropy[END_REF]. Since the calculation of L is based on the minimization of an objective function that is elusive to a straightforward geometric interpretation, namely, the condition number of the normalized Jacobian, the characteristic length has been found cumbersome to use in manipulator design. We introduce below the concept of conditioning length to render the Jacobian matrix dimensionless, which will allow us to define the characteristic length using a geometric approach. In the sequel, we will need the partial derivative of the trace of a square matrix N with respect to a scalar argument x of N. The said derivative is readily obtained as

∂ ∂x tr(N) = tr ∂N ∂x (9a)
Moreover, in some instances, we will need the partial derivative of a scalar function f of the matrix argument N with respect to the scalar x, which is, in turn, an argument of N. In this case, the desired partial derivative is obtained by application of the chain rule:

∂f ∂x = tr ∂f ∂N ∂N T ∂x (9b)
In particular, when f (N) is the kth moment N k of N with respect to x, defined as

N k ≡ tr(N k ) (9c)
the partial derivative of N k with respect to x is given by

∂N k ∂x = ktr N k-1 ∂N T ∂x (9d)
Furthermore, we recall that the trace of any square matrix N equals that of its transpose, i.e., tr(N T ) = tr(N) (10a) and, finally, the trace of a product of various matrices compatible under multiplication does not change under a cyclic permutation of the factors, i.e., if A, B, and C are three matrices whose product ABC is possible and square, then tr(ABC) =tr(BCA)= tr(CAB)

The summation appearing in the right-hand side of the above expression is known as the first moment of S with respect to the origin O from which the position vectors stem. The second moment of S with respect to C is defined as a tensor M, namely,

M ≡ n 1 (p k -c)(p k -c) T (12)
It is now apparent that the root-mean square value of the distances { d k } n 1 of S, d rms , to the centroid is directly related to the trace of M, namely,

d rms ≡ 1 n n 1 (p k -c) T (p k -c) ≡ 1 n tr(M) (13)
Further, the moment of inertia I of S with respect to the centroid is defined as that of a set of unit masses located at the points of S, i.e.,

I ≡ n 1 [ p k -c 2 1 -(p k -c)(p k -c) T ] (14a)
in which 1 is the 2 × 2 identity matrix. Hence, in light of definitions ( 12) and (13),

I = tr(M)1 -M (14b)
We shall refer to I as the geometric moment of inertia of S about its centroid.

It is now apparent that I is composed of two parts, an isotropic matrix of norm tr(M) and the second moment of S with the sign reversed. Moreover, the moment of inertia I can be expressed in a form that is more explicitly dependent upon the set { p k -c } n 1 , if we recall the concept of cross-product matrix [START_REF] Angeles | Fundamentals of Robotic Mechanical Systems[END_REF]. Briefly stated, for any three-dimensional vector v, we define the cross-product matrix P k of (p k -c), or of any other three-dimensional vector for that matter, as

P k ≡ ∂[(p k -c) × v] ∂v (15a)
Further, we recall the identity [5]

P 2 k ≡ -p k -c 2 1 + (p k -c)(p k -c) T (15b)
It is now apparent that the moment of inertia of S takes the simple form

I = - n 1 P 2 k ( 16
)
We thus have Definition 1 (Isotropic Set) The set S is said to be isotropic if its secondmoment tensor with respect to its centroid is isotropic.

As a consequence, we have Lemma 1 The geometric moment of inertia of an isotropic set of points about its centroid is isotropic.

Geometric Properties of Isotropic Sets of Points

We describe below some properties of isotropic sets of points that will help us better visualize the results that follow.

Union of Two Isotropic Sets of Points

Consider two isotropic sets of points in the plane,

S 1 = { P k } n 1 and S 2 = { P k } n+m n+1 . If the centroid C of the position vector c of S 1 coincides with that of S 2 , i.e. if, c ≡ 1 n n 1 p k ≡ 1 m n+m n+1 p k (17)
then, the set S = S 1 ∪ S 2 is isotropic.

For example, let S 1 be a set of three isotropic points and S 2 a set of four isotropic points, as displayed in Fig. 2, i.e.,

S 1 =         - √ 6/2 - √ 2/2    ,    √ 6/2 - √ 2/2    ,    0 √ 2         S 2 =         0 - √ 2    ,    - √ 2 0    ,    0 √ 2    ,    √ 2 0         (18a)
where the centroid C is the origin. The second moment of S with respect to C is isotropic, namely,

M ≡ 3+4 1 (p k -c)(p k -c) T =    7 0 0 7    = (7)1 (18b)
where 1 denotes the 2×2 identity matrix. Furthermore, the geometric moment of inertia of S is

1 = (14)1 -(7)1 = (7)1
Lemma 2 The union of two isotropic sets of points sharing the same centroid is also isotropic.

Rotation of an Isotropic Set of Points

Let R denote a rotation matrix in the plane through an angle α and S = { P k } n 1 a set of isotropic points. A new set of points S ′ = { P ′ k } n 1 is defined upon rotating S through an angle α about C as a rigid body. The second moment of S ′ with respect to C is shown below to be isotropic as well. Indeed, letting this moment be M ′ , we have

M ′ ≡ n 1 (p ′ k -c ′ )(p ′ k -c ′ ) T
where, by definition,

p ′ k -c ′ = R(p k -c)
Thus,

M ′ ≡ n 1 R(p k -c)(p k -c) T R T = R[ n 1 (p k -c)(p k -c) T ]R T
But the summation in brackets is the second moment M of the set S, which is, by assumption, isotropic, and hence, takes the form

M = n 1 (p k -c)(p k -c) T = σ 2 1
for a real number σ > 0 and 1 denoting the 2 × 2 identity matrix. Hence,

M ′ = σ 2 RR T = σ 2 1
thereby proving that the rotated set is isotropic as well. We thus have

Lemma 3

The rotation of an isotropic set of points as a rigid body with respect to its centroid is also isotropic.

The counterclockwise rotation of an isotropic set of three points, S, through an angle of 60 • and the union of the original set and its rotated counterpart are depicted in Fig. 3. Note that the union of the two sets is isotropic as well.

Trivial Isotropic Set of Points

An isotropic set of points can be defined by the union or rotation, or a combination of both, of isotropic sets. The simplest set of isotropic points is the set of vertices of a regular polygon. We thus have Definition 2 (Trivial isotropic set) A set of n points S is called trivial if it is the set of vertices of a regular polygon with n vertices.

Trivial isotropic sets, S = { P k } n 1 are depicted in Fig. 4, for n = 3, • • • , 6.

Also note that

Lemma 4 A trivial isotropic set S remains isotropic under every reflection about an axis passing through the centroid C.

An Outline of Kinematic Chains

The connection between sets of points and planar manipulators of the serial type is the concept of simple kinematic chain. For completeness, we recall here some basic definitions pertaining to this concept.

Simple Kinematic Chains

The kinematics of manipulators is based on the concept of kinematic chain. A kinematic chain is a set of rigid bodies, also called links, coupled by kinematic pairs. In the case of planar chains, two lower kinematic pairs are possible, the revolute, allowing pure rotation of the two coupled links, and the prismatic pair, allowing a pure relative translation, along one direction, of the same links.

For the purpose of this paper, we study only revolute pairs, but prismatic pairs are also common in manipulators.

Definition 3 (Simple kinematic chain) A kinematic chain is said to be simple if each and every one of its links is coupled to at most two other links.

A simple kinematic chain can be open or closed ; in studying serial manipulators we are interested in the former. In such a chain, we distinguish exactly two links, the terminal ones, coupled to only one other link. These links are thus said to be simple, all other links being binary. In the context of manipulator kinematics, one terminal link is arbitrarily designated as fixed, the other terminal link being the end-effector (EE), which is the one executing the task at hand. The task is defined, in turn, as a sequence of poses-positions and orientations-of the EE, the position being given at a specific point P of the EE that we term the operation point.

Isotropic Kinematic Chains

To every set S of n points it is possible to associate a number of kinematic chains. To do this, we number the points from 1 to n, thereby defining n -1 links, the ith link carrying joints i and i + 1. Links are thus correspondingly numbered from 1 to n, the nth link, or EE, carrying joint n on its proximal (to the base) end and the operation point P on its distal end. Furthermore, we define an additional link, the base, which is numbered as 0.

It is now apparent that, since we can number a given set S of n points in n! possible ways, we can associate n! kinematic chains to the above set S of n points. Clearly, these chains are, in general, different, for the lengths of their links are different as well. Nevertheless, some pairs of identical chains in the foregoing set are possible.

Definition 4 (Isotropic kinematic chain) If the foregoing set S of n points is isotropic, and the operation point P is defined as the centroid of S, then any kinematic chain stemming from S is isotropic.

The Posture-Dependent Conditioning Length of Planar n-Revolute Manipulators

Under the assumption that the manipulator finds itself at a posture P that is given by its set of joint angles, { θ k } n 1 , we start by dividing the last n rows of the Jacobian by a length l P , as yet to be determined. This length will be found so as to minimize the distance of the normalized Jacobian to a corresponding isotropic matrix K, subscript P reminding us that, as the manipulator changes its posture, so does the length l P . This length will be termed the conditioning length of the manipulator at P.

A Dimensionally-Homogeneous Jacobian Matrix

In order to distinguish the original Jacobian matrix from its dimensionallyhomogeneous counterpart, we shall denote the latter by J, i.e.,

J =    1 1 • • • 1 (1/l P ) Er 1 (1/l P ) Er 2 • • • (1/l P ) Er n   
Now the conditioning length will be defined via the minimization of the distance of the dimensionally-homogeneous Jacobian matrix J of an n-revolute manipulator to an isotropic 3 × n model matrix K whose entries are dimensionless and has the same gestalt as any 3 × n Jacobian matrix. To this end, we define an isotropic set K = { K i } n 1 of n points in a dimensionless plane, of position vectors { k i } n 1 , which thus yields the dimensionless matrix

K =    1 1 • • • 1 Ek 1 Ek 2 • • • Ek n    (19)
Further, we compute the product KK T :

KK T =    n n 1 k T i E T n 1 Ek i n 1 Ek i k T i E T   
Upon expansion of the summations occurring in the above matrix, we have

n 1 k T i E T = ( n 1 Ek i ) T = E( n 1 k i ) T (20a) n 1 Ek i k T i E T = E( n 1 k i k T i )E T (20b)
Now, by virtue of the assumed isotropy of K, the terms in parentheses in the foregoing expressions become

n 1 k i = 0 n 1 k i k T i = k 2 1 2×2
where the factor k 2 is as yet to be determined and 1 2×2 denotes the 2 × 2 identity matrix. Hence, the product KK T takes the form

KK T =    n 0 T 0 k 2 1 2×2    (21)
Now, in order to determine k 2 , we recall that matrix K is isotropic, and hence that the product KK T has a triple eigenvalue. It is now apparent that the triple eigenvalue of the said product must be n, which means that

k 2 = n (22)
and hence,

n 1 k i k T i = (n)1 2×2

Example 1: A Three-DOF Planar Manipulator

Shown in Fig. 5a is an isotropic set K of three points, of position vectors { k i } n 1 , in a nondimensional plane. The position vectors are given by

k 1 = 1 2    √ 6 √ 2    , k 2 = 1 2    - √ 6 √ 2    , k 3 =    0 - √ 2    (23a)
Hence, the corresponding model matrix is

K =        1 1 1 - √ 2/2 - √ 2/2 √ 2 √ 6/2 - √ 6/2 0        (23b)
which can readily be proven to be isotropic, with a triple singular value of k = √ 3. When the order of the three vectors is changed, the isotropic condition is obviously preserved, for such a reordering amounts to nothing but a relabelling of the points of K. Also note that two isotropic matrices K are associated with two symmetric postures, as displayed in Fig. 5b 5

.3 Example 2: A Four-DOF Redundant Planar Manipulator

An isotropic set K of four points, { K i } 4 1 , is defined in a nondimensional plane, with position vectors k i given below:

k 1 =    √ 2 √ 2    , k 2 =    - √ 2 √ 2    , k 3 =    - √ 2 - √ 2    , k 4 =    √ 2 - √ 2    (24a)
which thus lead to

K =        1 1 1 1 - √ 2 - √ 2 √ 2 √ 2 √ 2 - √ 2 - √ 2 √ 2        (24b)
We thus have 4! = 24 isotropic kinematic chains for a four-dof planar manipulator, but we represent only 6 in Fig. 6 because the choice of the first point is immaterial, since this choice amounts to a rotation of the overall manipulator as a rigid body.

Computation of the Conditioning Length

We can now formulate a least-square problem aimed at finding the conditioning length l P that renders the distance from J to K a minimum. The task will be eased if we work rather with the reciprocal of l P , λ ≡ 1/l P , and hence,

z ≡ 1 2 1 n tr[(J -K)(J -K) T ] → min λ (25)
Upon expansion,

z = 1 2 1 n tr(JJ T -JK T -KJ T + KK T )
Since the trace of a matrix equals that of its transpose, i.e., tr(JK T ) = tr(KJ T ) the foregoing expression for z reduces to

z ≡ 1 2 1 n tr(JJ T -2KJ T + KK T ) (26)
It is noteworthy that the above minimization problem is (a) quadratic in λ, for J is linear in λ and (b) unconstrained, which means that the problem accepts a unique solution. This solution can be found, additionally, in closed form. Indeed, the optimum value of λ is readily obtained upon setting up the normality condition of the above problem, namely,

∂z ∂λ ≡ 1 2n tr   ∂(J J T ) ∂λ   - 1 n tr   K ∂J T ∂λ   = 0 ( 27
)
where we have used the linearity property of the trace and the derivative operators. We calculate below the quantities involved:

JJ T =    n λ n 1 r T j E T λ 1 n3Er j λ 2 n 1 Er j r T j E T    ,KJ T =    n λ n 1 r T j E T n 1 Ek j λ n 1 Ek j r T j E T    Thus, ∂(JJ T ) ∂λ =    0 n 1 r T j E T n 1 Er j 2λ n 1 Er j r T j E T    , K ∂J T ∂λ =    0 n 1 r T j E T 0 n 1 Ek j r T j E T   
whence the normality condition (27) becomes

λ n 1 r j 2 - n 1 k T j r j = 0
Now, if we notice that r j is the distance d j from the operation point P to the center of the jth revolute, the first summation of the above equation yields nd 2 rms , with d rms denoting the root-mean-square value of the set of distances { d j } n 1 , and hence,

λ = n 1 k T i r j nd 2 rms ⇒ l P = nd 2 rms n 1 k T j r j (28)
Thus, the conditioning length is defined so that √ n d rms is the geometric mean between l P and the sum of the projections of the set { r j } n 1 onto the corresponding vectors of the set { k j } n 1 , as illustrated in Fig. 7.

A Rotation of the Isotropic Set as a Rigid Body

Since a rigid-body rotation of a set of isotropic points preserves isotropy, we can find the orientation of this set, as parameterized by the angle of rotation α, that renders z a minimum, for a given manipulator posture. Let this rotation be R(α), which can be expressed as [START_REF] Bottema | Theorical Kinematics[END_REF] R(α) = (cos α)1 + (sin α)E (29) with E defined in eq.( 8). Thus, upon rotating the set K through an angle α about its centroid C or, equivalently, about the operation point P , the isotropic matrix K becomes K, and is given by

K =    1 1 • • • 1 ER(α)k 1 ER(α)k 2 • • • ER(α)k n    (30a)
The objective function z then becomes

z = 1 2n tr(J J T ) -2tr(J KT ) + tr( K KT ) → min α (30b)
Before setting up the normality conditions for the problem at hand, we note that

K KT =    n ( n 1 k i ) T E T R T (α) R(α)E n 1 k i R(α)E( n 1 k i k T i )E T R T (α)    (31)
which can be shown to reduce to

K KT =    n ( n 1 k i ) T E T R T (α) R(α)E n 1 k i k 2 1 2×2   
and hence,

∂[tr( KT )] ∂α = 0
On the other hand, J is independent of α, and hence, the normality condition of problem (30b) reduces to

∂z ∂α ≡ - 1 n tr J ∂ KT ∂α = 0 (32)
We calculate below the partial derivative required above:

∂ K ∂α =    0 0 • • • 0 R ′ (α)Ek 1 R ′ (α)Ek 2 • • • R ′ (α)Ek n   
where R ′ (α) can be expressed, in light of relation (29), as

R ′ (α) = ER(α)
and hence,

∂ K ∂α =    0 0 • • • 0 ER(α)Ek 1 ER(α)Ek 2 • • • ER(α)Ek n    whence, tr J ∂ KT ∂α = λtr{ n 1 Er j [ER(α)Ek j ] T } = λ n 1 r T j E T ER(α)Ek j = λ n 1 r T j R(α)Ek j
Now, under the plausible assumption that l P is finite, λ = 0, and hence, the normality condition (32) reduces to

n 1 r T j R(α)Ek j = 0
Further, substitution of expression (29) into the above expression leads to

(cos α) n 1 r T j Ek j -(sin α) n 1 r T j k j = 0 (33)
Therefore, the value of α minimizing the distance of J to K(α) is, for the given posture P,

α = arctan n 1 r T j Ek j n 1 r T j k j ≡ arctan (1/n) n 1 r T j Ek j (1/n) n 1 r T j k j (34)
Thus, the angle α through which the given isotropic set K is to be rotated in order to obtain the conditioning length of the manipulator pose P is given as the arctan function of the ratio of a numerator N to a denominator D, whose geometric interpretations are straightforward: D is simply the mean value of the projections of the r j vectors onto their corresponding k j vectors. Now, since Ek j is vector k j rotated 90 • counterclockwise, N is the mean value of the projections of the r j vectors onto their corresponding Ek j vectors. We can call the latter the transverse projections of the said vectors. Once we have found the optimum value α opt of α for a given manipulator posture, we redefine, for conciseness,

K ← K(α opt ) (35)
With α opt known, l P is readily computed from eq.( 28). Now, if we regard the columns of J and K as 3-dimensional vectors, then a rotation Q of the corresponding 3-dimensional space about an axis normal to the plane of the sets { r j } n 1 and { k j } n 1 through an angle q can be represented as

Q =    1 0 T 0 R(q)   
where R(q) is a 2 × 2 rotation matrix similar to R(α), as defined in eq.( 29). Hence, under rotation Q, J and K change as described below:

QJ =    1 0 T 0 R(q)       1 1 • • • 1 (1/l P ) Er 1 (1/l P ) Er 2 • • • (1/l P ) Er n    =    1 1 • • • 1 R(q)Er 1 R(q)Er 2 • • • R(q)Er n    QK =    1 1 • • • 1 R(q)Ek 1 R(q)Ek 2 • • • R(q)Ek n   
Now it is apparent that z, as defined in eq.( 25), is invariant under a rotation R(q) of the sets S and K. Indeed, under such a rotation,

z Q ≡ 1 2 1 n tr(QJJ T Q T -QKJ T Q T -QJK T Q T + QKK T Q T ) = 1 2 1 n tr[Q(JJ T -KJ T -JK T + KK T )Q T ]
If we recall relation [START_REF] Ranjbaran | The Mechanical Design of a Seven-Axes Manipulator with Kinematic Isotropy[END_REF], the above expression becomes

z Q ≡ 1 2 1 n tr[Q T Q(JJ T -KJ T -JK T + KK T )] = z (36)
We thus have proven

Lemma 5

The distance of J to K is invariant under a rotation of the sets S and K.

The Optimum Posture

It is now apparent that we can always orient the K set optimally, so that, for any posture P, J lies a minimum distance from the corresponding matrix K. Moreover, by virtue of Lemma 5, a rotation of the whole manipulator as a rigid body about its first joint, i.e., a motion of the manipulator with all its joints but the first one locked, does not affect z. That is, z is a function of only { θ i } n 2 , which can thus be termed the set of conditioning-joint variables, the associated joints being the conditioning joints. Now we aim at finding the optimum posture P o that yields a dimensionless Jacobian J lying a minimum distance to the reference matrix K. To this end, we adopt a given set K at a given orientation at the outset, which thus leads to a constant matrix K in the process of finding P o , the optimum orientation of K being readily determined from eq.(34) once P o has been found. Thus, in the derivations that follow, θ 1 can be set arbitrarily equal to zero, or to any other constant value, for that matter. We now aim at solving the problem

z = 1 2 1 n tr(JJ T -2KJ T + KK T ) → min {θ i } n 2 (37)
An attempt to solving this problem using the approach of the foregoing sections proved to be impractical. Indeed, since z depends on the set of conditioning joint variables both via the set { r j } n 1 and via λ, this dependence leads to a normality condition that does not lend itself to a closed-form solution. As a consequence, the said normality condition does not lead to a direct geometric interpretation of the optimum posture.

We thus follow a different approach here. For each posture, the value of λ is computed using eq.( 28), while α is computed with the eq.( 34). With the foregoing expressions substituted into the expression of z given in eq.(37), the corresponding normality conditions for angles θ i n 2 yield a system of algebraic equations in the foregoing conditioning variables that are amenable to solutions using modern methods, like polynomial continuation, Gröbner bases, or resultant methods [START_REF] Nielsen | Computational Methods in Mechanical Systems[END_REF], that yield all roots of the problem at hand. These roots then lead to the globally-optimum posture P o .

The Characteristic Length

The optimum postures of a given manipulator, i.e., those with a Jacobian matrix closest to a corresponding model matrix K are thus found upon solving the optimization problem (37). Moreover, the conditioning length associated with the posture yielding a global minimum of the foregoing distance is defined as the characteristic length of the manipulator at hand. Prior to discussing some examples, we would like to find out whether the characteristic length thus found bears a minimality geometric property, e.g., whether the characteristic length is the minimum conditioning length of the manipulator over its whole workspace. To this end, we rewrite the objective function z in the form

z = 1 2n (λ 2 nd 2 rms -2λ n 1 k T j r j + n 1 k j 2 ) ( 38
)
Upon substitution of the sum n 1 k T j r j in terms of the optimum value of λ found in eq.( 28) into eq.( 38), we obtain

z = 1 2n n 1 k j 2 - 1 2 λ 2 d 2 rms ≡ 1 2n n 1 k j 2 - 1 2
d rms l P 2 (39)
It is apparent from the above expression that minimizing z is not equivalent to minimizing l P , but rather to maximizing the ratio d rms /l P . Hence, minimizing z is equivalent to minimizing the inverse ratio, i.e., l P /d rms . In other words, minimizing z is equivalent to minimizing the ratio of the conditioning length to the rms value of the distances of the joint centers from the operation point.

Examples:

A Three-DOF Planar Manipulator

An Isotropic Manipulator

In the first example, we have a 1 = a 2 = l and a 3 = √ 3 l/3, with the { r j } 3 1 vectors given by

r 1 = l    cos(θ 1 ) + cos(θ 12 ) + cos(θ 123 ) sin(θ 1 ) + sin(θ 12 ) + sin(θ 123 )    , r 2 = l    cos(θ 12 ) + cos(θ 123 ) sin(θ 12 ) + sin(θ 123 )    , r 3 = √ 3l 3    cos(θ 123 ) sin(θ 123 )   
with the definition θ ij...p ≡ θ i + θ j + . . . + p. Moreover, the model matrix K used for this case is that found for the case of an isotropic set of three points, as discussed in Subsection 5.2, and reproduced below for quick reference:

K =        1 1 1 - √ 2/2 - √ 2/2 √ 2 √ 6/2 - √ 6/2 0        (40)
One optimum posture found with the procedure discussed in Subsection 5.6 is displayed in Fig. 8, the objective function attaining a minimum of zero at this posture, which means that the manipulator can match exactly an isotropic model matrix K within its workspace, the manipulator thus being termed isotropic. The objective function attains the values displayed in Fig. 9 over its whole workspace.

At the optimum posture, we have the values of the joint variables given below:

θ 1 = 0 • , θ 2 = 120 • , θ 3 = 150 •
the conditioning length l P being equal to ( √ 6/6) l, which is thus the characteristic length of this manipulator, as found using an alternative approach in [START_REF] Angeles | Fundamentals of Robotic Mechanical Systems[END_REF]. Moreover, the normalized Jacobian J becomes

J =        1 1 1 - √ 2/2 - √ 2/2 √ 2 √ 6/2 - √ 6/2 0       

An Equilateral Manipulator

In the second example, we assume that all the link lengths are equal to l, and hence,

r 1 = l    cos(θ 1 ) + cos(θ 12 ) + cos(θ 123 ) sin(θ 1 ) + sin(θ 12 ) + sin(θ 123 )    , r 2 = l    cos(θ 12 ) + cos(θ 123 ) sin(θ 12 ) + sin(θ 123 )    r 3 = l    cos(θ 123 ) sin(θ 123 )    (41)
We call this manipulator equilateral.

For this case, we use the same model matrix K that we used in the previous example, for the manipulator has the same number of joints, and only one K was found-up to a reflection-for this number of joints. The minimization of the objective function leads to the optimum values

θ 1 = 0 • , θ 2 = 81.8 • , θ 3 = 155.2 •
which correspond to a minimum value of z = 0.178, the associated characteristic length being l P = 0.563 l. The corresponding posture is displayed in Fig. 10, while the objective function, evaluated throughout the workspace of the manipulator, is displayed in Fig. 11.

Finally, the normalized Jacobian at the posture of Fig. 10 is

J =        1 1 1
-0.268 -0.268 1.489

1.061 -0.714 -0.966

      

The Isocontours of the Objective Function

The minimum of the objective function z corresponds to the posture closest to isotropy. At the other end of the spectrum, the maximum of this function is attained at those singular postures whereby the rank of the Jacobian matrix is two. The curves of constant z-values, termed the isocontours of the manipulator, can be used to define a performance index to compare manipulators, as described below. The isocontours were obtained with Surfer, a Surface Mapping System, for θ 2 and θ 3 ∈ [0, 2π]. The isocontours of the isotropic manipulator, of the first example, are displayed in Fig. 12; those of the equilateral manipulator in Fig. 13.

It is apparent from the two foregoing figures that the isocontours can be closed or open. If closed, the curves enclose the optimum point in the space of conditioning joints; in the second case, the curves are periodic. The shape of the closed curves, additionally, provides useful information on the manipulator performance: For the isotropic manipulator, when the objective function is below 0.25, the curves are close to circular, as shown in Fig. 14; for the equilateral manipulator, these curves are close to elliptical, as shown in Fig. 15. This means that, in the neighborhood of an optimum, the isocontours behave in a way similar to the manipulability ellipsoid [START_REF] Yoshikawa | Manipulability of Robotic Mechanisms[END_REF]: An isotropic manipulator entails a manipulability ellipsoid with semiaxes of identical lengths.

Manipulators are designed for a family of tasks, more so than for a specific task-manipulator design for a specific task defeats the purpose of using a manipulator, in the first place! The first step in designing a manipulator, moreover, is to dimension its links. It is apparent that from a purely geometric viewpoint, the link lengths are not as important as the link-length ratios. Once these ratios are optimally determined, the link lengths can be obtained based on requirements such as maximum reach for a given family of tasks, e.g., whether the manipulator is being used for cleaning a wide-body or a regional aircraft. Now, the maximum reach is directly proportional to the d rms value of the distance of the joint centers to the operation point at the optimum posture, and hence, we can obtain the optimum link-length ratios by assuming that d rms is equal to one unit of length. This means that minimizing the objective function z, as given by eq.( 39), is equivalent to minimizing the normalized conditioning length l P , where the normalization is carried out upon dividing this length by d rms . Furthermore, when deciding on the manipulator linklength ratios, we may specify a certain useful workspace region as a subset of the whole workspace. How to decide on the boundaries of this region is something that can be done based on the value of z, so that we can establish a maximum allowable value of z, say z M < z max , that we are willing to tolerate so as to keep the manipulator far enough from singularities. In this regard, the area enclosed by the isocontour z = z M will give a nondimensional measure, and hence, a measure independent of the scale of the manipulator, of the useful workspace region.

Under no constraints on the link-length ratios, for example, the designer should choose the optimum ratios of the isotropic manipulator of Fig. 8. On the other hand, when the manipulator is given, and it is desired to control it so as to keep it away from singularities, function z can be used again as a measure of the distance to singularities: when z attains its global maximum, the manipulator finds itself at a rank-two singularity. A rank-one singularity occurs at a local maximum. Furthermore, if a manipulator of given link-length ratios-e.g., one out of a family of manipulators with identical architectures, but of different scales, like the Puma 260, 560, or 760-is to be used for arc welding, then (a) the most suitable dimensions should be chosen according with the dimensions of the welding seam, and (b) the seam should be placed with respect to the manipulator in such a way that, as the EE traces that seem with the welding nozzle at a given angle with the seam, the objective function z must remain within a maximum value z M . This means that the seam should lie as close as possible to the optimum posture of Fig. 10. Furthermore, note that a rotation of the manipulator about the first joint axis, while keeping its other two joints locked, does not perturb z, and hence, a set of optimum postures is available. This set comprises the circle centered at the center of the first joint, of radius d 1 -the distance of the operation point P to the center of the first joint. This circle is similar to the isotropy circle of isotropic manipulators [START_REF] Angeles | Fundamentals of Robotic Mechanical Systems[END_REF], and thus, can be termed the conditioning circle. Therefore, a good criterion to properly place the seam is that the seam lie as close a spossible to the conditioning circle.

Finally, while detecting singularities of nonredundant robots is a rather trivial task, detecting those of their redundant counterparts is more involved, and a fast estimation of the proximity of a given manipulator posture to singularity is always advantageous. This estimation is provided by the objective function z proposed in this paper.

Conclusions

The conditioning length l P was defined for a given posture of a planar manipulator. This concept allows us to normalize the Jacobian matrix so as to render it in nondimensional form. We base the definition of the characteristic length on an objective function z that gives a geometric significance to the conditioning length. Moreover, the objective function introduced here is defined as a measure of the distance of the normalized-nondimensional-Jacobian matrix to an isotropic reference matrix. Isotropic sets of points in the plane are defined as well as operations on these sets. The paper is limited to planar manipulators, the treatment of spatial manipulators being as yet to be reported.

K 3 K 1 K 3 K 2 K 1 K 2 K 3 K 1
Fig. 5. Two isotropic manipulator postures stemming from the same isotropic set upon a relabelling of its points z(q 1 2 3 ,q ,q )

K 1 K 4 K 3 K 2 K 1 K 3 K 4 K 2 K 1 K 4 K 2 K 3 K 1 K 3 K 2 K 4 K 1 K 2 K 3 K 4 K 1 K 2 K 4 K 3

3 Fig. 1 .Fig. 2 .

 312 Fig. 1. Planar n-revolute manipulator

Fig. 3 . 6 P 3 P 2 Fig. 4 .

 36324 Fig. 3. (a) Rotation of an isotropic set S and (b) union of S with its rotated image

Fig. 6 .Fig. 7 .Fig. 8 .

 678 Fig. 6. Six isotropic postures for the same isotropic set

Fig. 9 .q 2 q 3 Fig. 10 .Fig. 11 .Fig. 12 .p

 923101112 Fig. 9. Objective function of the isotropic manipulator

Fig. 14 .

 14 Fig. 14. The isocontours closset to isotropy of the objective function of the isotropic manipulator

Fig. 15 .

 15 Fig. 15. The isocontours closest to isotropy of the objective function of the equilateral manipulator

Acknowledgements

The first author acknowledges support from France's Institut National de Recherche en Informatique et en Automatique. The second author acknowledges support from the Natural Sciences and Engineering Research Council, of Canada, and of Singapore's Nanyang Technological University, where he completed the research work reported here, while on sabbatical from McGill University.


Antoine Nongaillard

Sébastien Picault

Gal A Kaminka

Maria Bouquet

Eyke Hüllermeier Dignum

Virginia Dignum

Frank Van Harmelen

Frank

Multilevel Agent-Based Modelling for Assignment or Matching Problems

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.

Multilevel Agent-Based Modelling for Assignment or Matching Problems

Antoine Nongaillard1 and Sébastien Picault 1 Abstract. Assignment or matching problems have been addressed by various multi-agent methods, focused on enhancing privacy and distribution. Nevertheless, they little rely on the organisational structure provided by Multi-Agent Systems (MAS). We rather start from the intrinsic ability of multilevel MAS to represent intermediate points of view between the individual and the collective levels, to express matching or assignment problems in a homogeneous formalism. This model allows to define relevant metrics to assess the satisfaction of agent groups and allow them to build solutions that improve the overall well-being without disclosing all their individual information.

INTRODUCTION AND LITERATURE

A problem of resource allocation aims at distributing a resource set among a population of individuals, optimising a goal defined as the aggregation of individual measures. A matching problem aims at grouping individuals, by optimising a goal defined as the aggregation of assessments made by each individual on other members of their group. In both cases, objectives are often expressed as an aggregation of individual evaluations using the social choice theory [START_REF] Arrow | Social Choice and Individual Values[END_REF]. These two families, despite their similarities, are addressed as different problems, because of the possibility or not for "resources" to express preferences towards other members of their group. They are thus resolved by algorithms dedicated to a specific families, or even specific sub-problems.

The most common resolution methods are centralised and based on complete information. Indeed, all preferences or constraints are public and manipulated by an overall solver. The most known algorithms in this field (e.g., the Hungarian algorithm [START_REF] Kuhn | The Hungarian method for the assignment problem[END_REF] or the Gale-Shapley algorithm [START_REF] Gale | College admissions and the stability of marriage[END_REF])focus in identifying optimal solutions in absolute terms, by making the strong assumption of a full and public information. Mechanisms for achieving such a solution from a given starting point is not a concern of these methods.

Recently, these problems have also been modelled using the multiagent paradigm. On the one hand, one can consider the problem of resources/tasks allocation within a population of agents: MAS are then just an application area [START_REF] Airiau | Multiagent resource allocation with sharable items[END_REF][START_REF] Weerdt | Multiagent task allocation in social networks[END_REF], for which it seems natural to seek distributed solving methods [START_REF] Macarthur | A distributed anytime algorithm for dynamic task allocation in multi-agent systems[END_REF]. On the other hand, MAS can be used as a tool to solve allocation or matching problems in a distributed way. Some of these approaches are a mere distribution of computations [START_REF] Netzer | Distributed envy minimization for resource allocation[END_REF][START_REF] Brito | Distributed stable matching problems[END_REF] and do not consider the behaviours required for agents to achieve a solution, but only protocol issues and solution characteristics.

Instead of addressing the very issue of distributing either the preferences or the resolution among a population of agents for a particular problem, we rather try to build a generic multilevel structure which allows the modelling of assignment or matching problems, and the expression of multiple concerns at the same time.

Thus, we propose a multilevel modelling of these problemswhich increases the variety of constraints and preferences that can be expressed at every organisation level, using the ability to build composite metrics.

MULTILEVEL MODEL

The multilevel formalism we are proposing assume that all relevant entities of the model (e.g. "individuals", "resources", "groups". . . ) are represented by agents and linked by a membership relation. Those relations are not necessarily hierarchical, since for example some problems may imply resource sharing or allow individuals to be members of several groups at the same time. In order to implement these features, the formalism we chose is a multilevel agent-based simulation meta-model called "PADAWAN" [START_REF] Picault | An interaction-oriented model for multi-scale simulation[END_REF].

The set of all agents is denoted by A; a1 < a2 means that agent a1 is contained by agent a2 (or a2 is host to a1).The < relationship induces an oriented, cycle-free, hosting graph between the agents.

For any agent a we also define its hosts and conversely the set of all agents contained in a respectively as: hostspaq " tai P A|a < aiu and contentpaq " taj P A|aj < au Our approach consists in grounding the computation of welfare values in the very membership relations in the MAS. We decompose the individual welfare of any agent into three contributions representing respectively the agent as an individual, as the neighbour of other agents, and as the host to other agents. Thus we have: wpaq " fapσpaq, µpaq, γpaqq where fa function can be chosen arbitrarily, depending on the situation to be modelled.

The σpaq contribution represents the satisfaction of agent a as an individual, which is also situated in a given structure. Thus, this value can be computed from the state of agent a, but also according to the perceived properties of its hosts and of their own "ancestors": Hpaq " th P A|a < h _ Dh 1 P Hpaq, h 1 < hu For instance, in a problem where individuals have to be assigned to groups within organisations, the satisfaction of a person depends on its own state, on the features of its role within its group, on the properties of the group itself, but also on the organisation this group is part of, etc.

The corresponding value can then be computed by using an operator Ë a , specific to agent a (and to be defined for each concrete situation), in order to aggregate the perceptions by agent a of its situation. This situation is composed of the properties χaphq, perceived by agent a, of itself and of all agents that contain a (either directly or transitively):

σpaq " a ë hPtauYHpaq χaphq
The µpaq contribution represents the satisfaction of agent a as member of a group, in other words the contribution of externalities due to the presence of other agents within the same hosts. The γpaq contribution represents the satisfaction of agent a as the representative of a group of agents. This satisfaction as a group is intended to measure the collective welfare of the agents contained in a, which can be done by aggregating the perceived properties of the agents contained in a, using a third domain-dependent operator, denoted by Ê a :

γpaq " a ê mPcontentpaq χapmq

EXAMPLE

In order to illustrate the specific contribution of our multilevel welfare assessment meta-model, we present below a complex problem involving multiple membership, demonstrating the capabilities of our meta-model to represent various points of view (hence, various objectives), specific to each agents family or to each level.

Here we consider individuals (I) allowed to enrol in several associations (A). These associations can gather into federations (F) and can be funded either by municipalities (M) or by regions (R) (Figure 1). The individuals seek to maximise their participation in the associations offering their preferred activities. The associations and federations intend to assert their size (enrolment) so as to defend their grant requests. The municipalities aim at allocating their available budget as fairly as possible between their local associations. The regions try to do the same between municipalities and federations. In this example we assume that the grant allocation is based on a Nash welfare, in order to prevent the largest structures from monopolising the budget, and yet taking their enrolment into account, hence:

Region

Ê R " Ê M " ś . On the contrary, an association a which only intends to assert the number of registered members (without consideration for their satisfaction), can simply use χapiq " 1 for every member i and Ê A " ř . The weight of an association obviously depends on its membership of a federation, thus for each of its hosts h, we assume χaphq " 1 if h P F, and χaphq " 0 otherwise, with Ë A " ř . The individuals are rather in search of a trade-off between the participation to their preferred activities and the cumulative cost of these activities (which requires a cost matrix pci,aq). Again, Ë I " ř can be used. But, in addition, people are highly sensitive to their neighbours, i.e. the other individuals enrolled in the same associations. This can be handled for instance through an affinity-based approach, and an aggregation operator Å I either optimistic (max), or pessimistic (min).

To summarise, the diversity of objectives within the MAS is made explicit by using a large diversity of metrics, within a structure where all agents are otherwise homogeneous. We argue that this systematisation is the basis for defining generic resolution principles, which can deal with quite different situations, in opposition of classical approaches (either centralised or distributed) where each specific problem is to be solved by its specific method. Indeed, we assume that our meta-model allows the construction of intrinsically multi-agent resolution methods, i.e. relying on local perceptions and interactions between agents, and on generic behaviours subject to contextdependent settings.

CONCLUSION, PERSPECTIVES

We proposed a uniform approach to model assignment or matching problems through a multilevel multi-agent system. We have shown the capability of this formalism to express a broad diversity of objectives, representing the viewpoints of the actors of the system. We are currently working on the construction of several protocols, not dedicated to a specific problem, but rather based on the nature of the hosting graph between agents. These algorithmic aspects mix with methodological considerations, so as to identify couplings between the nature and structure of the addressed problems, and the behaviours to give the agents to enable them build a solution in an incremental way.

  of those neighbours are then aggregated using another operator which we denote by Å a :

Figure 1 .

 1 Figure 1. Hosting graph representing a common associative network, with individuals (I) enrolled in several associations (A), possibly grouped into federations (F ) and funded by municipalities (M) or regions (R).

Univ. Lille, CNRS, Centrale Lille, UMR 9189 -CRIStAL (SMAC), F-59000 Lille, France, email: name.surname@univ-lille.fr This project is granting on the PartEns project, within the research program "chercheur citoyen" from the region Hauts de France.