Guillaume Lozenguez
email: guillaume.lozenguez@unicaen.fr

Lounis Adouane
email: lounis.adouane@lasmea.univ-bpclermont.fr

Aurélie Beynier
email: aurelie.beynier@lip6.fr

Abdel-Illah Mouaddib

Philippe Martinet
email: philippe.martinet@lasmea.univ-bpclermont.fr

Calcul distribué de politiques d'exploration pour une flotte de robots mobiles

Keywords: Architecture multi-robots, Processus décisionnels probabilistes, Négociation Multi-Robot Architecture, Decision Making, Negotiation Le niveau décisionnel traite le problème

Ce papier présente une architecture multirobots permettant une allocation automatique de plusieurs objectifs sur une flotte de robots. Le challenge consiste à rendre des robots autonomes pour réaliser coopérativement leur mission sans qu'un plan soit prédéfini. Cette architecture, appelée PRDC, est basée sur 4 modules (Perception, Représentation, Délibération et Contrôle). Nous nous intéressons plus particulièrement au module de délibération en considérant le problème des voyageurs de commerce coopératifs dans un environnement incertain. L'objectif des robots est alors de visiter un ensemble de points d'intérêt représentés dans une carte topologique stochastique (Road-Map). Le processus proposé pour la construction des politiques collaboratives est distribué. Chaque robot calcule ses politiques individuelles possibles de façon à négocier collectivement l'allocation des points d'intérêt entre les membres de la flotte. Enfin, l'approche est évaluée via un important nombre de simulations.

Introduction

Permettre à une flotte de robots d'être complétement autonome pour réaliser des objectifs complexes est un chalenge difficile de la robotique mobile. Les comportements des robots doivent converger efficacement vers la réalisation de tous les objectifs tout en réagissant correctement aux événements perçus. Le besoin de réaliser des comportements complexes et variés pour des robots autonomes a conduit à la proposition d'architectures hiérarchiques [START_REF] Alami | An architecture for autonomy[END_REF][23] [START_REF] Mourioux | Control robot by a generic control architecture[END_REF].

Ce type d'architecture permet de séparer la prise de décision du contrôle/commande d'un robot en utilisant plusieurs niveaux d'abstraction. Généralement, ces architectures incluent un niveau fonctionnel qui supervise les perceptions et asservit le robot pour la réalisation d'une tâche, ainsi qu'un niveau décisionnel qui planifie la réalisation de la mission et supervise le niveau fonctionnel. tives [START_REF] Goldman | Decentralized control of cooperative systems : Categorization and complexity analysis[END_REF][8] [START_REF] Burgard | Coordinated multi-robot exploration[END_REF] basée sur une connaissance de l'environnent modélisé par une carte. Il existe, dans la littérature, 2 principales familles de cartes qui permettent de connecter perception, décision et contrôle : les cartes sous forme de grilles d'occupation [START_REF] Elfe | Sonar-based real-world mapping and navigation[END_REF], qui sont une discrétisation métrique de l'environnement et les cartes dites topologiques [START_REF] Kuipers | A robot exploration and mapping strategy based on a semantic hierarchy of spatial representations[END_REF] qui représentent l'environnement sous forme d'un graphe où les noeuds correspondent à des emplacements particuliers et les arcs représentent la connectivité entre les noeuds. Dans une architecture hiérarchique, nous nous intéressons à définir une carte topologique (Road-Map) qui intègre les contraintes de perception et qui permette la prise de décision et la supervision d'un contrôle réactif.

Dans ce papier, le niveau décisionnel est proposé pour une flotte de robots coopératifs qui ont pour mission de visiter un ensemble de points d'intérêt (Fig. 1). Une solution connue consiste à utiliser les processus décisionnels de Markov décentralisés (Dec-MDPs) pour modéliser les problèmes de collaboration entre plusieurs robots [START_REF] Goldman | Decentralized control of cooperative systems : Categorization and complexity analysis[END_REF] [START_REF] Beynier | An iterative algorithm for solving constrained decentralized markov decision processes[END_REF]. Toutefois, calculer les politiques décentralisées optimales à partir de ce modèle est connu comme un problème difficile (NEXP-complet) [START_REF] Bernstein | The complexity of decentralized control of markov decision processes[END_REF] ce qui limite l'utilisation des Dec-MDPs au contrôle de systèmes à peu d'états.

Une coordination en ligne et à long terme de plusieurs agents oblige à utiliser des méthodes heuristiques qui conduisent à des politiques non-optimales. Une approche distribuée pour la résolution de Dec-MDPs à été proposée afin de permettre de répartir les charges de calculs sur l'ensemble des robots [START_REF] Chades | A heuristic approach for solving decentralized-pomdp : Assessment on the pursuit problem[END_REF]. Même réparties ainsi, le problème du calcul des politiques décentralisées reste difficile. Par ailleurs, des approches de coordination basées sur des ventes aux enchères [START_REF] Dias | Market-based multirobot coordination : A survey and analysis[END_REF] proposent des protocoles dis- Notre approche consiste à diviser le problème du calcul des politiques décentralisées en un problème d'allocation d'objectifs couplé à un problème de calcul de politiques individuelles. Etant donnée une allocation définie à partir des intérêts individuels, chaque robot est alors capable de calculer sa politique individuelle en considérant uniquement les objectifs qui lui sont alloués. Le calcul de ces politiques permet à chaque robot d'évaluer l'intérêt de chacun des points à visiter et d'actualiser ainsi l'allocation courante.

Le papier est organisé comme suit : la section 2 décrit l'architecture des robots permettant la construction des politiques d'actions (section 3). La section 4 présente notre méthode distribuée pour l'allocation des points d'intérêt suivie par des simulations dans la section 5.

Une architecture délibérative

Dans cette section, nous présentons notre architecture nommée (PRDC) (Fig. 2) basée sur 4 modules que sont la Perception, la Représentation, la Délibération et le Contrôle. Ces 4 modules permettent de séparer les problématiques liées à différents domaines et s'organisent en deux niveaux hiérarchiques.

Perception et contrôle

Les modules de perception et de contrôle correspondent au niveau fonctionnel défini dans les architectures hiérarchiques [START_REF] Alami | An architecture for autonomy[END_REF] [START_REF] Volpe | The claraty architecture for robotic autonomy[END_REF]. Le module de perception supervise les capteurs de fa-çon à convertir des flots données en informations utiles à la localisation et au contrôle du robot. Il permet d'avoir une estimation sur le déplacement du robot et sur la reconnaissance des objets alentour comme la forme des obstacles. Les données odométriques, par exemple, permettent au robot de maintenir sa localisation. Ces données sont néanmoins incertaines, elles propagent en effet, l'erreur de localisation et d'orientation au fur et à mesure du déplacement. Toutefois, le robot est capable de se localiser en reconnaissant des positions particulières [START_REF] Kuipers | A robot exploration and mapping strategy based on a semantic hierarchy of spatial representations[END_REF] [START_REF] Ulrich | Appearancebased place recognition for topological localization[END_REF], ce qui permet de corriger ponctuellement les erreurs d'odométrie.

Le module de contrôle est basé sur un ensemble de contrôleurs réactifs [START_REF] Rosenblatt | Damn : A distributed architecture for mobile navigation -thesis summary[END_REF][1] (évitement d'obstacles, attraction vers une cible, suivi d'un robot ou d'une trajectoire,. . . ). Dans le cadre de la tâche de déplacement entre deux positions, nous avons choisi d'utiliser une architecture de contrôle basée sur une structure multi-contrôleurs [START_REF] Adouane | Hybrid and safe control architecture for mobile robot navigation[END_REF] qui permet d'alterner entre un contrôleur d'attraction vers une cible et un contrôleur d'évitement. Le passage d'un contrôleur à un autre se fait via une fonction d'adaptation permettant d'éviter les à-coups sur la commande.

Cette architecture de contrôle permet au robot de rejoindre une position dans un environnement encombré sans qu'une trajectoire soit pré-calculée. Les tâches locales du module de contrôle sont envoyées par le module délibératif (Fig. 2) et correspondent à la position immédiate à rejoindre pour orienter le robot vers un objectif plus lointain.

Représentation

Au niveau supérieur, le module de Représentation est responsable des connaissances sur l'environnement accumulées par le robot. Le module de représentation est un module actif dans le sens qu'il inclut un processus de localisation et de cartographie simultanée (SLAM : Simultaneous Localization And Mapping) [START_REF] Kuipers | A robot exploration and mapping strategy based on a semantic hierarchy of spatial representations[END_REF]. La connaissance est définie par rapport aux capacités de perception. Une Road-Map < W, P > est définie dans notre architecture comme une carte topologique où chaque noeud w ∈ W (way-points) représente une position particulière identifiable par le module de perception [START_REF] Ulrich | Appearancebased place recognition for topological localization[END_REF]

w p , w ′ p ∈ W, - → v p ∈ R 2 , c p ∈ R, d p : W → [0, 1], u p ∈ [0, 1]
Modéliser la connaissance sous forme de chemins stochastiques permet de planifier un déplacement sûr et efficace entre deux positions [START_REF] Alterovitz | The stochastic motion roadmap : A sampling framework for planning with markov motion uncertainty[END_REF]. Sur la base de ces chemins structurés comme un graphe représentant la connectivité globale, nous nous sommes intéressés, lors de la mise en place du module de délibération, à planifier automatiquement des comportements coopératifs pour les robots de la flotte.

Délibération

Le module délibératif, second composant du niveau supérieur, connecte la représentation de l'environnement, les objectifs et le contrôle effectif du robot. Il est divisé en 2 parties : construction de la politique (Decision Making) et exécution (Fig. 2). La partie exécutive supervise le contrôle du robot par rapport à la politique d'actions calculée.

Une politique est une fonction π : S → A qui associe une action à chaque état défini s ∈ S.

Les états du robot sont composés de l'état perceptif (qui inclut la position du robot dans sa Road-Map) et un état logique qui correspond à l'étape achèvement des objectifs. Etant données les capacités perceptives de nos robots, un état ne peut pas toujours inclure les positions des autres robots dans l'environnement. Les actions sont définies par rapport aux tâches réalisables par le module de contrôle. Elles sont définies par l'ensemble des chemins P .

La politique calculée dans notre approche est actualisée, en ligne, chaque fois qu'une incohérence est détectée entre la topologie locale et la politique pré-calculée. Cela se produit si la Road-Map, au moment de l'exécution, devient suffisamment différente de celle utilisée lors de la construction de la politique. Notons que la politique d'un robot doit être collaborative, elle peut être calculée en utilisant des protocoles décentralisés basés sur la communication.

La partie d'exécution évalue l'état courant, vérifie la cohérence entre l'action donnée par la politique et la topologie courante de façon à demander ou non une actualisation de la politique puis, transforme cette action en une tâche locale pour le module de contrôle.

Construction des politiques

Pour chaque robot, la partie qui consiste à construire sa politique collaborative doit permettre à la partie exécutive de superviser le contrôle du robot et d'atteindre les objectifs propres du robot. Dans ce papier nous nous intéressons au problème d'une équipe de voyageurs de commerce pour lesquels l'objectif est de visiter collectivement un ensemble de points d'intérêt. En raison de l'aspect non déterministe de la réalisation des actions de déplacement, nous avons choisi de modéliser le problème à l'aide du formalisme des Processus Décisionnels de Markov (Markov Decision Process, MDP) [START_REF] Puterman | Markov Decision Processes : Discrete Stochastic Dynamic Programming[END_REF].

Les Processus Décisionnels de Markov

Un MDP est défini par un tuple < S, A, t, r > avec S et A représentant respectivement les ensembles d'états et d'actions qui définissent le système et ses possibilités de contrôle. t est la fonction de transition définie par t : S × A × S → [0, 1] qui donne la probabilité t(s, a, s ′ ) d'atteindre s ′ depuis s en exécutant l'action a. La fonction de récompense r est définie par r : S × A → R, où r(s, a) retourne la récompense obtenue en exécutant a depuis s.

Trouver la solution optimale d'un MDP consiste à chercher la politique optimale π * qui maximise les gains espérés sur les récompenses. π * maximise la fonction de valeur V π : S → R donnée par l'équation de Bellman [START_REF] Bellman | A markovian decision process[END_REF]. Soit, pour une politique π : Résoudre un Dec-MDP est connu pour être difficile (NEXP-complet). Afin de gérer cette complexité, ce formalisme a été étendu pour plusieurs sous-classes de problèmes [START_REF] Goldman | Decentralized control of cooperative systems : Categorization and complexity analysis[END_REF]. Des approches approximées ont également été proposées [START_REF] Goldman | Decentralized control of cooperative systems : Categorization and complexity analysis[END_REF]. Parmi elles [START_REF] Beynier | An iterative algorithm for solving constrained decentralized markov decision processes[END_REF][START_REF] Chades | A heuristic approach for solving decentralized-pomdp : Assessment on the pursuit problem[END_REF]

V π (s) = r(s, π(s)) + γ s ′ ∈S t(s, π(s), s ′ )V π (s ′ )
π * (s) = argmax a∈A ( V π * (s) ) Le paramètre γ ∈ [0,

Résultats de simulation

Une première série de simulations cherche à évaluer l'efficacité du protocole d'allocation distribuée par rapport à une solution optimale calculée de façon centralisée par une recherche exhaustive. L'optimalité est définie comme l'allocation qui maximise la somme des gains espérés de tous les robots.

Les simulations considèrent 3 robots dans 2 cartes différentes (Fig. 4 Les scores obtenus (Tableau 1) nous permettent de valider que l'allocation par une approche distribuée reste proche de l'optimale pour des problèmes de tailles réduites avec un score moyen de 99% et seulement 2 expériences qui retournent un score inférieur à 70%. D'un autre côté, la probabilité de trouver réellement l'allocation optimale diminue avec la possibilité de tomber dans des optimums locaux (surtout dans En utilisant des agents bavards, nous nous sommes intéressés au nombre d'itérations utiles par robot Ag i où l'attribution I Ag i est actualisée (Fig. 5). Une itération utile correspond à une actualisation des utilités suivie par une phase de communication.

FIGURE 1 -

 1 FIGURE 1 -Problématique : illustration avec 2 robots et 4 points d'intérêt I = {a, b, c, d}.

FIGURE 2 -

 2 FIGURE 2 -L'architecture PRDC implémentée sur chaque robot.

FIGURE 3 -

 3 FIGURE 3 -Exemple d'une énumération des états possibles pour un MDP individuel orienté par 2 objectifs.

FIGURE 5 -

 5 FIGURE 5 -Nombre moyen d'itérations utiles (n robots et 4 * n points d'intérêt).

  Quand une action a = p a est exécutée depuis un way-point w s , la fonction de transition t retourne la probabilité u pa de tomber dans l'état s update ou la probabilité d'atteindre un waypoint w ∈ W en accord avec les valeurs de la fonction d pa . Une transition déterministe est ajoutée pour l'action de valider la visite d'un point d'intérêt a = p s , elle conduit dans l'état correspondant où le point d'intérêt courant est ajouté à l'ensemble des points d'intérêt déjà visités.

	Un état s du MDP individuel d'exploration in-clut la dernière position reconnue du robot w s ∈ W et l'ensemble des points d'intérêt déjà at-teints I s . Un état spécifique s update est ajouté pour modéliser l'état particulier où la percep-tion de l'environnement conduit à une incohé-rence de la politique. Une action a est ajoutée pour chaque chemin p 3.3 Politiques décentralisées Un MDP permet de calculer une politique pour un agent. Pour adapter ce formalisme à des systèmes multi-agents coopératifs, Bernstein et al. [5] ont défini les MDPs Décentralisés (Dec-MDPs). Un Dec-MDP est défini par un tuple < S, A, t, Ω, O, r >. Les éléments S, A, t et r sont similaires aux éléments d'un MDP clas-sique avec comme différence que chaque action a ∈ A est l'union des actions réalisées simul-tanément par tous les agents. L'ensemble A est un produit cartésien A 1 × • • • × A n des actions individuelles. Le formalisme des Dec-MDP in-clut la notion d'observation locale de l'agent où Ω est l'ensemble des observations jointes

1] pondère l'importance entre les récompenses immédiates et futures. Dans le cas d'un problème de taille finie, comme atteindre un nombre donné d'objectifs, γ est considéré égal à 1. L'algorithme "value iteration"

[START_REF] Puterman | Markov Decision Processes : Discrete Stochastic Dynamic Programming[END_REF]

permet de converger sur la politique optimale π * et de calculer la fonction de valeur associée V π * .

3.2 MDP individuel d'exploration

Les MDPs ont été utilisés avec succès en robotique mobile pour une décision et un contrôle basés sur une représentation en grille d'occupation

[START_REF] Foka | Real-time hierarchical pomdps for autonomous robot navigation[END_REF]

[7]

[START_REF] Teichteil-Königsbuch | Autonomous search and rescue rotorcraft mission stochastic planning with generic dbns[END_REF]

. L'approche proposée dans ce papier se base sur une carte topologique, la politique doit assigner un point cible à atteindre au module de contrôle pour toutes les positions possibles du robot. a ∈ P pour cibler le waypoint w pa . L'action de rester sur place est modélisée comme un chemin p s depuis w s qui boucle sur lui même. Ce type d'action permet aussi de valider la visite d'un point d'intérêt associée à l'obtention d'une récompense ponctuelle.

S = {(w s , I s ) | w s ∈ W, I s ⊂ I} ∪ {s update } A = { (p a ) | p a ∈ P } ∪ { (p s ) = (w s , w s ) | w s ∈ W } t((

w s , I s ), p a , s update ) = u pa | (w s = w pa ) t((w s , I s ), p a , (w s ′ , I s )) = (1 -u pa ) * d pa (w s ′ ) t((w s , I s ), p s , (w s , I s ∪ (I ∩ w s )) = 1 La fonction de récompense retourne la valeur du coût c p de suivre le chemin p et une valeur constante du gain g si un nouveau point d'intérêt est visité. r((w s , I s ), p a ) = c pa r((w s , I s ), p s ) = g if w s ∈ I -I s , else 0 Le nombre d'états augmente exponentiellement par rapport au nombre total de points d'intérêt à visiter (|S| > 2 |I| ). o ∈ Ω et la fonction O connecte les observations des n agents à la dynamique du système. O(s, a, s ′ , o = < o 1 . . . o n >) ∈ [0, 1] donne la probabilité que les agents Ag 1 . . . Ag n observent respectivement o 1 . . . o n quand l'action jointe a est exécutée à partir de s et que s ′ est atteint.

  Ag i ) et de sa position courante dans sa carte (w Ag i ), le gain individuel (gi ) du robot Ag i est défini en considérant que tous les points d'intérêt qui ne lui sont pas attribués sont visités ((I -I Ag i )). Le gain individuel est la valeur donnée par l'équation de Bellman pour l'état (w Ag i , I -I Ag i ).gi (I Ag i ) = V π * (w Ag i , I -I Ag i )

	"manager" ou "contractuel potentiel" et plu-constat nous conduit à proposer un protocole dit	table fermée. La garantie d'atteindre cet état
	sieurs ventes peuvent s'effectuer en parallèle. de la table ronde roundTable où toutes les al-	n'est pas triviale, elle dépend des règles de
	D'autres protocoles sont dérivés de "Contract locations s'effectuent et se terminent en même	fonctionnement établies et de la cohérence
	net" comme MURDOCH [13] qui présente des temps.	des comportements individuels.
	permettent aux agents d'actualiser itérativement leur politique pour converger sur une collaboration localement optimale. Le nombre d'états du problème de la visite d'un ensemble de points d'intérêt par une flotte de plusieurs robots ne permet pas une résolution qui garantisse l'optimalité. Par rapport au sujet traité ici nous avons choisi d'utiliser une collec-tion de MDPs individuels plutôt que de chercher à résoudre un Dec-MDP global. Il est consi-déré que seulement l'allocation de l'ensemble des points d'intérêt modifie la politique indivi-duelle d'un robot. De cette façon, pour une al-location donnée, la connaissance de l'état des autres robots à chaque instant n'est pas requise et le MDP individuel est totalement observable. Le calcul des politiques décentralisées peut être décomposé en deux problèmes dépendants l'un de l'autre qui sont l'allocation des points d'inté-rêt et le calcul d'une politique individuelle. Les hypothèses utilisées ne permettent pas une réso-lution optimale du problème mais la résolution du probléme doit permettre aux robots de colla-borer en cours de mission. 3.4 Coopération par négociation Chaque robot, en utilisant un MDP individuel d'exploration, est donc capable de calculer sa politique d'exploration pour une attribution de points d'intérêt fixée. Au regard de cette poli-tique et de l'équation de Bellman, le robot est capable d'évaluer son attribution et donc de la comparer avec d'autres attributions candidates. Nous avons donc mis en place un protocole de négociation basé sur la communication qui per-mette aux robots d'échanger leurs préférences de façon à construire une allocation des points d'intérêt qui fasse consensus. Il existe des protocoles distribués de coopéra-tion basés sur des ventes aux enchères. Dans "Contract net" [9], un objet, une ressource, ou une tâche à réaliser est mise en vente par un agent qui devient le "manager" pour l'item ciblé, les autres agents endossent le rôle de "contractuel potentiel" et peuvent émettre des 4.3 Comportement individuels somme cumulée des récompenses qui seront sta-tistiquement perçues par le robot Ag i pour la vi-site des points d'intérêt appartenant à I Ag i . En considérant le robot comme faisant partie d'une équipe, il est intéressant de répercuter une va-leur sociale représentant un coût occasionné par les actions d'un robot sur son groupe. La diffi-culté consiste à distribuer sur chacun des robots présents des contraintes globales. Par exemple, équilibrer le nombre de points d'intérêt attribués sur les n robots présents. à opposer au gain individuel. Ainsi, chaque robot s'auto-rise à déséquilibrer plus ou moins sa propre al-location en comparant ses utilités qui sont fonc-tion de sa charge actuelle, avec les utilités com-muniquées par ses collaborateurs. 4.2 Protocole de la table ronde Les n robots présents lors d'une étape de com-munication souhaitent donc se répartir entre eux l'ensemble des points d'intérêt à visiter. L'approche distribuée ici consiste à permettre à chaque robot de construire en parallèle sa propre allocation. La difficulté réside dans le fait que Le protocole roundTable pour l'attribution des points d'intérêt est indépendant des comporte-ments individuels permettant aux agents d'éva-luer leurs utilités. Par contre, fermer la table sur un consensus général suppose certaines capaci-tés de la part des agents présents : la capacité in-dividuelle d'un agent à proposer un vecteur de valeurs d'utilité stable quelles que soient les va-leurs d'utilités communiquées par les autres ; la capacité sociale des agents à proposer des va-leurs d'utilité qui permettent de converger sur un consensus. La fonction d'utilité proposée (Section 4.1) est cohérente sur les valeurs calculées. Pour un ro-bot, quelque soit un point d'intérêt, ajouter ou supprimer ce point dans son attribution courante ne modifie pas la valeur de ce point. Par exemple (Fig.1) la valeur d'utilité du point a pour un Le comportement de chaque robot vise à maxi-miser une somme globale de gain espéré sur tous les robots. Bien que cela permette a priori de converger sur un consensus, chaque robot est limité à un nombre fini d'actualisation sur ses valeurs de façon à garantir l'arrêt de la table ronde. De cette façon, le consensus est forcé après avoir dépassé un certain temps. De plus, l'état stable ou instable de chaque robot est explicitement communiqué pour détecter l'état global de consensus. En considérant des communications sans erreur et sans perte, les robots sont capables indivi-duellement de calculer l'allocation et de détec-ter la fermeture de la table. Les robots utilisent actuellement un même protocole qui consiste à : -actualiser le tableau des valeurs d'utilités grâce aux communications, -s'il existe un ou des points d'intérêt appar-tenant à seulement un des ensembles consti-FIGURE 4 -les 2 Road-Map considérés : (a)(b) avec quelques obstacles et (c) le labyrinthe. (a)(c) garanties de robustesse. La coopération basée sur des ventes aux en-Le protocole roundTable se divise en 5 étapes : 1 -Inscription La table est ouverte à l'initia-chères est utilisée avec succès en robotique [10] ainsi qu'en robotique mobile avec des valeurs évaluées par MDP [7][20]. Cette approche ne garantit pas que les politiques décentralisées construites soient optimales. Par contre, ce type d'approche permet de distribuer la charge de calcul et de relâcher la contrainte d'une connais-sance identique pour tous les agents. En effet, chaque politique est construite par l'agent de-puis sa connaissance courante et individuelle de l'environnement. Aussi, par la suite nous proposons protocole basé sur le principe d'une table ronde où, à chaque itéra-tion, tous les points d'intérêt sont réévalués en parallèle et seuls les points d'intérêt pour les-quels une meilleure allocation est trouvée sont échangés. 4 Allocation des points d'intérêt Nous nous intéressons particulièrement aux étapes de la mission où plusieurs robots de la flotte communiquent pour calculer leur po-litique collaborative. La communication est considérée sans erreur pendant ces étapes. Dans un premiers temps, nous nous intéressons à l'évaluation individuelle des points d'intérêt puis au protocole de table ronde qui permet aux robots de trouver un allocation qui fasse consen-sus. Cette approche s'oppose à une résolution centralisée sur un leader [16]. 4.1 Evaluation individuelle tive d'un agent, la première phase vise à recenser les agents qui feront partie de la négociation. Il n'est pas possible pour un agent d'entrer ou de sortir simplement de la table à partir du moment où l'inscrip-tion est close. Cette étape permet notam-ment d'identifier le réseau de communica-tion. Dans le cadre de notre étude, nous consi-dérons un groupe de robots où chaque peut communiquer directement avec chacun des autres robots. 2 -Définition des règles Les agents inscrits doivent ensuite valider les règles de fonc-tionnement de la table ainsi que les règles d'attribution finale des items. Les règles de fonctionnement peuvent intégrer une attribution de rôles particuliers utiles au bon fonctionnement de la table (comme un qui en propose la plus forte valeur d'utilité. 3 -Enumération des items Les items sont, par la suite, énumérés de façon à ce que chaque agent puisse construire son tableau de va-leur (Item/Agent). Ici, chaque robot énumère l'ensemble des points d'intérêt dont il a la charge. Nous supposons que tous les points d'intérêt sont identifiables dans les cartes individuelles. 4 -Itérations Tous les agents actualisent et communiquent leurs valeurs conformément aux règles de fonctionnement établies. Ici, les robots sont désynchronisés, ils itèrent et communiquent en parallèle sur un modèle de broad-cast. Chaque robot com-munique son vecteur de nouvelles valeurs à tous les autres robots. 5-Fermeture Les itérations sur les valeurs s'effectuent jusqu'à trouver un consensus, c'est-à-dire que pour chaque agent l'allo-présentent une allocation construite de façon distribuée et (b) l'allocation optimale. muniquer un état instable ; sinon communi-quer un état stable et sauter l'étape suivante, -ajouter ou enlever dans l'attribution courante, le point le plus intéressant parmi les points dé-tectés et communiquer les nouvelles valeurs, -boucler jusqu'à détecter l'état de consensus. Ce comportement individuel (dit bavard) est dé-fini pour un cadre où les communications sont peu coûteuses. Il est possible, pour minimiser les communications, d'instaurer un tour de pa-Un robot Ag Ainsi formalisé, le gain individuel exprime la robot est la même en considérant les attribu-role et/ou de limiter les valeurs communiquées président). tions individuelles {a, b, c} ou {b, c}. Cette co-aux valeurs qui correspondent à un état stable du Dans le cadre de notre étude, les règles de fecte chacun des points d'intérêt au robot par les autres robots. de rôle particulier. La règle d'attribution af-stable quelque soit les utilités communiquées par les agents et elles ne nécessitent pas guration lui permettant d'être individuellement fonctionnement sont connues initialement hérence permet aux robots d'avoir une confi-robot.
	cation donnée par les règles d'attribution	enchères. Après un temps déterminé par le la valeur d'utilité d'un point d'intérêt pour un tués : 1-par l'attribution courante du robot, 2-
	ne modifie plus ses valeurs communiquées.	"manager" l'item est attribué à l'agent ayant agent est réévaluée à chaque fois que l'agent ef-à partir des règles d'attribution (mais pas aux
	L'allocation peut donc être validée et la	fait la meilleure offre. Chaque agent peut être fectue une modification sur son allocation. Ce deux) alors, détecter tous ces points et com-

Dans le cadre de l'allocation de tous les points d'intérêt pour une flotte de robots explorateurs la valeur d'un point d'intérêt pour un robot dépend des autres points qui lui sont attribués ou non. Par exemple, la valeur du point d'intérêt b pour le robot 2 n'est pas la même s'il doit ou non visiter c (Fig.

1

). L'utilisation des protocoles classiques de ventes induit une remise aux enchères constante de tous les points d'intérêt jusqu'à obtention du consensus. i est capable de construire son MDP individuel d'exploration à partir de sa propre Road-Map en considérant qu'il est seul pour visiter tous les points d'intérêt (I). A partir de l'ensemble des points d'intérêt qui lui sont attribués (I Un gain espéré (ge) propre à chaque robot et à sa charge d'exploration est donc défini comme la différence du gain individuel et du coût social occasionné. A partir de ce gain espéré, il est possible d'évaluer l'utilité d'ajouter ou d'enlever un point d'intérêt k ∈ I à I Ag i . ge(I Ag i ) = gi (I Ag i ) -| |I| n -|I Ag i || * oc utility(k, I Ag i ) = eg(I Ag i + k)eg(I Ag i -k) Le coût social proposé ici, est proportionnel à la différence entre : la taille de l'allocation propre au robot Ag i et la taille moyenne (|I|/n pour n robots). Le facteur oc définit le coût

  ) et entre 2 et 13 points d'intérêt. Pour 13 points d'intérêt, cela induit 3 13 allocations possibles et entre 50 * 2 13 et 70 * 2 13 états pour les MDPs individuels (en fonction de |W |). Les coûts sur les chemins sont calculés directement comme la distance entre 2 positions de la carte ; un coût maximum de 51.2 est relevé pour la diagonale des limites des environnements. La récompense gagnée pour visiter un point d'intérêt est posée à 1000 et le coût d'opportunité oc est égal à 0 ou à 5.12 (0.1 * maxCost).

	En se basant sur la somme des gains espérés,
	un score (en pourcentage) peut être calculé pour

TABLE 1

 1

	-Scores

  2 moyennes du nombre d'itérations utiles sont calculées : une à partir de tous les robots et une seconde en ne considérant que le pire des robots de chaque simulation. La figure 4(c) présente les résultats d'une simulation pour 6 robots et 24 points d'intérêt dans le labyrinthe. Il est possible de conclure que seulement quelques actualisations individuelles sont nécessaires par rapport au nombre total de points d'intérêt. Délibération et Contrôle) est présentée dans ce papier. Cette architecture sépare les problèmes de l'élaboration de la décision et du contrôle/commande du robot. Nous nous sommes intéressés au module délibératif gérant la construction des politiques collaboratives permettant de visiter un ensemble de points d'intérêt avec une flotte de robots.L'approche distribuée proposée permet aux robots d'aboutir à une solution valide. Un important nombre de simulations permet une évaluation encourageante de l'efficacité de l'approche sur des problèmes de tailles restreintes et démontre, d'autre part, la capacité de l'approche à considérer un nombre relativement important de robots. Ces résultats sont encourageant sachant que le problème traité ne peut être optimalement résolu.Dans de futurs travaux, l'approche devrait être utilisée sur des robots réels avec une carte initiale incomplète. Nous souhaitons aussi étudier l'intérêt (efficacité, robustesse) d'utiliser différentes règles de fonctionnement pour la table ronde et différents comportements individuels.

	6 Conclusion
	Une architecture hiérarchique basée sur 4 mo-
	dules (Perception, Représentation,


L Rubbert

S Caro

J Gangloff
email: jacques.gangloff@unistra.frpierre.renaud@insa-strasbourg.fr

P Renaud

Using Singularities of Parallel Manipulators to Enhance the Rigid-body Replacement Design Method of Compliant Mechanisms

The rigid-body replacement method is often used when designing a compliant mechanism. The stiffness of the compliant mechanism, one of its main properties, is then highly dependent on the initial choice of a rigid-body architecture. In this paper, we propose to enhance the efficiency of the synthesis method by focusing on the architecture selection. This selection is done by considering the required mobilities and parallel manipulators in singularity to achieve them. Kinematic singularities of parallel structures are indeed advantageously used to propose compliant mechanisms with interesting stiffness properties. The approach is first illustrated by an example, the design of a one degree of freedom compliant architecture. Then the method is used to design a medical device where a compliant mechanism with three degrees of freedom is needed. The interest of the approach is outlined after application of the method.

Introduction

Compliant mechanisms are monolithic structures taking advantage of elasticity to produce movements. The absence of backlash and friction allows the production of very accurate movements making them suitable for medical devices [START_REF] Kota | Design and application of compliant mechanisms for surgical tools[END_REF][START_REF] Choi | Flexure-based manipulator for active handhled microsurgical instrument[END_REF][START_REF] Savall | Micromanipulator for enhancing surgeon's dexterity in cochlear atraumatic surgery[END_REF], micropositioning [START_REF] Tian | Design and dynamics of a 3-dof flexure-based parallel mechanism for micro/nano manipulation[END_REF][START_REF] Richard | Concept of modular flexure-based mechanisms for ultra-high precision robot design[END_REF] and space applications [START_REF] Fowler | Compliant space mechanisms: a new frontier for compliant mechanisms[END_REF]. One challenge is to design compliant mechanisms with multiple degrees of freedom that have adequate stiffness performances, i.e. that demonstrate low stiffnesses along the desired degrees of freedom (DOF), high stiffnesses in the other directions, and that fulfill other design criteria such as compactness. There are different ways to design compliant mechanisms. The most common synthesis approaches, described in [START_REF] Gallego | Synthesis methods in compliant mechanisms: An overview[END_REF], are the kinematic-based approaches, the building blocks approaches and the structural optimizationbased approaches. Among the kinematic-based approaches, the FACT method does not require knowledge of existing rigid-body mechanisms, the synthesis being performed using screw theory [START_REF] Hopkins | Synthesis of precision serial flexure systems using freedom and constraint topologies (fact)[END_REF][START_REF] Dibiasio | A building block synthesis approach for precision flexure systems with integrated, strain-based position sensing[END_REF]. The rigid-body replacement approach is very interesting since it takes advantage of the large number of existing rigid-body mechanisms and their modeling tools [START_REF] Olsen | Utilizing a classification scheme to facilitate rigid-body replacement for compliant mechanism design[END_REF]. With this approach, a rigid-body mechanism is first designed, or selected in the literature, then converted into a compliant mechanism, followed by pseudo-rigid body modeling [START_REF] Howell | Compliant mechanisms[END_REF] and optimization. Complex compliant mechanisms with multiple DOF can thus be obtained [START_REF] Richard | Concept of modular flexure-based mechanisms for ultra-high precision robot design[END_REF][START_REF] Bachta | The cardiolock project: Design of an active cardiac stabilizer for cardiac surgery[END_REF][START_REF] Ouyang | A spatial hybrid motion compliant mechanism: Design and optimization[END_REF][START_REF] Xu | Analytical modeling, optimization and testing of a compound bridge-type compliant displacement amplifier[END_REF].

The design or selection of the rigid-body mechanism architecture, which will be used for the compliant mechanism synthesis, is critical. For identical mobilities, the mechanism architecture can be, for instance, serial or parallel. For a mechanism composed of a serial linkage, a direct conversion into a compliant structure may lead to insufficient stiffness performances, whatever the geometry of the flexure joints is. In such a situation, it is interesting to provide the designer with alternative solutions. Olsen et al. proposed a classification scheme to identify subgroups in a mechanism which can be independently converted into compliant elements [START_REF] Olsen | Utilizing a classification scheme to facilitate rigid-body replacement for compliant mechanism design[END_REF][START_REF] Olsen | A design framework that employs a classification scheme and library for compliant mechanism design[END_REF]. The main idea is that some subchains from an initial architecture can be efficiently replaced by alternative architectures to improve the final performances of the compliant mechanism. The use of parallel architectures has been proposed for this purpose because of their interesting intrinsic stiffness properties. Selecting or proposing a parallel mechanism is however a delicate task. First, even though many parallel architectures exist [START_REF] Merlet | Parallel robots[END_REF], the choice of a parallel mechanism with particular mobilities is generally not obvious. Second, each parallel mechanism has its own workspace and its kinematic properties are strongly dependent on the mechanism configuration [START_REF] Mattson | Development of commercially viable compliant mechanisms using the pseudo-rigid-body model: Case studies of parallel mechanisms[END_REF]. Therefore, selecting a parallel mechanism also requires an expertise in the definition of the configuration used for the compliant mechanism.

One well-known feature of parallel mechanisms is the existence of so-called singular configurations. In those configurations, the parallel mechanism locally exhibits specific mobilities. Since compliant mechanisms usually work around a given position, it seems interesting to start their design with the architectures obtained from parallel mechanisms in singularity, for three reasons. First, the designer only has to focus on the selection of a parallel architecture with adequate singular configurations, instead of having to select a parallel mechanism and afterward a configuration. Second, the designer can benefit from the knowledge of singularity analysis for many parallel manipulators [START_REF] Merlet | Parallel robots[END_REF][START_REF] Amine | Singularity analysis of 3t2r parallel mechanisms using grassmann-cayley algebra and grassmann line geometry[END_REF]. It is then easy to obtain mechanisms that can achieve particular mobilities with parallel architectures for the sake of stiffness. Third, many spatial parallel manipulators reach a singular configuration in planar configurations. Planar configurations are of particular interest for the design of compliant mechanisms since their manufacturing is usually largely simplified [START_REF] Choueifati | Compliant mems motion characterization by nanoindentation[END_REF][START_REF] Lusk | Components, building blocks, and demonstrations of spherical mechanisms in microelectromechanical systems[END_REF].

In this paper, the singularity analysis of parallel manipulators is considered in the type-synthesis of compliant mechanisms based on the rigid-body replacement approach. Therefore, the singularities of parallel manipulators, that are generally avoided, are here at the center of a design approach.

In Section 2, we detail how a parallel manipulator and its singularities can be used to design a parallel architecture that can be integrated later in a compliant mechanism. The approach is illustrated with the design of a simple 1-DOF compliant mechanism. The design of an active cardiac stabilizer, a medical device, is performed by using rigid-body replacement method in Section 3. The use of the proposed approach is outlined, with the introduction of an original parallel architecture in the compliant device. The performance of the mechanism is evaluated and its interest is discussed before drawing a conclusion on the relevance of the approach.

The Design Approach

The proposed approach for rigid-body mechanism selection is intrinsically related to the singularities of parallel manipulators. They are first briefly outlined. Then details are given on how mechanism selection can be achieved by using them.

Singularities of Parallel Manipulators

For a given parallel manipulator, q a and q p denote the actuated joint angle vector and the passive joint angle vector, respectively. The full twist T describes the velocities along the 6-DOF of the end-effector. It can be divided into T n , the velocities of the n-DOF of the end-effector of the manipulator, and T n, the complementary velocities which should be zero in the normal case. The relationship between the input velocities of the actuators qa , the passive joint velocities qp and the full twist of the end-effector T can be written as [START_REF] Merlet | Parallel robots[END_REF][START_REF] Zlatanov | A unifying framework for classification and interpretation of mechanism singularities[END_REF]:

A qa + BT + C qp = 0 (1)
This equation can be rewritten as:

L ( qa , qp , T) T = 0 ( 2
)
where L is a N × (N + n) matrix, N being the number of equations and N + n the number of unknowns.

If the end-effector does not move while the actuators have non-zero velocities, the manipulator is in a serial singularity, or redundant input singularity (Type 1 [START_REF] Gosselin | Singularity analysis of closed-loop kinematic chains[END_REF]). Therefore it can be said that the end-effector loses one or more DOF. Inversely, if the end-effector of the manipulator can move locally even if the actuators are locked and T n = 0 the manipulator is in a parallel singularity, or redundant output singularity (Type 2 [START_REF] Gosselin | Singularity analysis of closed-loop kinematic chains[END_REF]). It can be said that the end-effector gains one or more DOF. The manipulator is in a Type 3 singularity if the manipulator reaches both serial and parallel singularities. In case of a parallel singularity, if T n = 0 and T n = 0, the manipulator reaches a constraint singularity that includes the case of architectural singularity where self-motions occur and the end-effector can move with finite amplitude [START_REF] Merlet | Parallel robots[END_REF][START_REF] Zlatanov | Classification and interpretation of the singularities of redundant mechanisms[END_REF]. If the actuators are locked, T = 0 and the passive joints can move, the manipulator is in a redundant passive motion singularity.

Here, the redundant output singularities where the endeffector moves while the actuators are locked are interesting for the design of compliant mechanisms. As a matter of fact, as a compliant mechanism only works around a given configuration, the motions of the moving platform can be used to produce the required displacements. At the same time, the actuated joints can be suppressed as they are considered locked, which simplifies the architecture of the compliant mechanism.

It is noteworthy that Type 2 singularities have already been considered for simple mechanisms, for instance in the case of orthoplanar mechanisms [START_REF] Parise | Ortho-planar linear-motion springs[END_REF] or the development of 1-DOF structures such as torque sensors [START_REF] Chapuis | Design of a simple mri/fmri compatible force/torque sensor[END_REF][START_REF] Renaud | Kinematic analysis for a novel design of mri-compatible torque sensor[END_REF], but have never been applied in a more generic way to compliant mechanisms.

Principle of the Design Approach

The approach to select a rigid-body mechanism from parallel mechanisms in a singular configuration is introduced with the example of the design of a 1-DOF compliant mechanism equivalent to a revolute joint. The approach is broken down into four steps.

Step 1 -Selection of a mechanism: First, a parallel manipulator needs to be selected or identified. It needs to exhibit in singularity at least the desired mobilities of the compliant linkage. Here, the 3-PRR planar parallel manipulator illustrated in Figure 1a is chosen. The singularity analysis of this manipulator was performed in [START_REF] Bonev | Singularity analysis of 3-dof planar parallel mechanisms via screw theory[END_REF]. The manipulator has a planar architecture and is composed of three identical limbs and has three degrees of freedom. Each limb contains a prismatic actuated joint and two passive revolute joints. The 3-PRR can reach some parallel singularities and the gained motions are instantaneous rotations about an axis normal to the plane of motion.

Step 2 -Singularity analysis: For a given architecture, the nature of the displacements in singularity depends on the actuated joints, i.e. the actuation mode. For parallel singularities, the end-effector motion is obtained while the actuated joints are locked. The choice of these actuated joints is crucial for the design of the compliant structure since this latter is obtained by their suppression. Consequently, Step 2 consists in analyzing all possible actuation modes for the selected architecture, in order to identify the one that most simplifies the subsequent compliant structure.

In the case of the 3-PRR architectures, their singular configurations have been analyzed with the screw theory [START_REF] Bonev | Singularity analysis of 3-dof planar parallel mechanisms via screw theory[END_REF]. Considering symmetrical actuation modes, i.e., the same joint in each leg is actuated, a singular configuration of Type 2 exists for the three possible actuation modes. Considering the 3-PRR parallel manipulator, the singular configuration occurs when the lines associated with the distal links intersect at a single point as illustrated in Figure 1b. Considering the 3-PRR parallel manipulator and the 3-PRR parallel manipulator, their singular configurations of Type 3 occur when the lines associated with the distal links intersect at one point and are normal to the axis of their prismatic joint as illustrated in Figure 1c and Figure 1d.

Step 3 -Actuation mode selection: If different actuation modes allow the manipulator in singularity to have the desired mobilities, the one which simplifies the most the compliant mechanism architecture and its manufacturing is selected. It is noteworthy that revolute joints are the simplest and easiest-to-manufacture joints [START_REF] Lobontiu | Compliant Mechanisms -design of flexure hinges[END_REF]. A prismatic joint is more complex to manufacture as it requires at least two leafspring joints or four notch joints [START_REF] Trease | Design of large-displacement compliant joints[END_REF]. A compliant mechanism only composed of compliant revolute joints may therefore be preferred. If a parallel manipulator is composed of joints of the same kind, i.e. it is only composed of revolute joints or prismatic joints, the designer has to choose the actuation mode that mostly simplifies the conversion to a compliant mechanism: decision criteria will be based on the manufacturing process, the global arrangement with respect to space requirements.

Here, the architecture illustrated in Figure 1e, obtained from the first actuation mode after suppression of the prismatic joints, has only revolute joints and is therefore preferred.

Step 4 -Design of the compliant mechanism: The simplified kinematic architecture can now be converted to a compliant mechanism by replacing each joint by a notch joint. Here, the 3-RR architecture of the final compliant mechanism is illustrated in Figure 1f.

Design of a Compliant Mechanism for an Active Cardiac Stabilizer

The design approach which was introduced in the previous section is now applied in the context of a medical device design. The aim of this section is first to show the interest of the proposed approach during the design of a compliant device, and second to show its potential efficiency, with the introduction of a non-trivial 3-DOF mechanism.

The Design Problem

Coronary artery bypass grafting is a common procedure in cardiac surgery. It usually requires the use of a heart-lung machine to ease the task, with possible side-effects for the patient. A solution is to perform grafting procedures on the surface of a beating heart, its surface being locally immobilized with a so-called active cardiac stabilizer [START_REF] Bachta | Cardiolock: an active cardiac sta-bilizer, first in vivo experiments using a new robotized device[END_REF]. It is an active compliant mechanism controlled by vision that detects any heart displacement and suppresses it by modifying the position of a shaft applied on the heart. It can be compared to an active compensation device cancelling in real time the influence of the heart contraction. The most recent device, Cardiolock 2, is illustrated in Figure 2. It provides the 2 DOF needed for the compensation task [START_REF] Bachta | Active stabilization for robotized beating heart surgery[END_REF]. The actuation is performed with piezoelectric stacks because of their accuracy and large bandwidth. In presence of the 5 N cardiac forces, the stabilizer exhibits displacements at its tip due to its own flexibilities and the lack of stiffness of its mounting system [START_REF] Bachta | The cardiolock project: Design of an active cardiac stabilizer for cardiac surgery[END_REF]. Consequently, the device must be able to compensate for these displacements at the shaft tip in the two directions perpendicular to the shaft axis. Piezoelectric stacks have very limited stroke, so that an amplification mechanism is necessary in order to obtain the required displacements [START_REF] Bachta | Active stabilization for robotized beating heart surgery[END_REF].

Shaft Piezoelectric stack

Joint #1 Joint #2 15 mm Fig. 2: The Cardiolock II [START_REF] Bachta | Active stabilization for robotized beating heart surgery[END_REF].

At this point, the compactness of this device needs to be increased to meet the requirements of an operation room while maintaining the same level of performances. As a consequence, we consider as a new architecture the kinematic scheme represented in Figure 3. The stabilizer is then composed of two prismatic joints in P 1 to control the orientation of the shaft with respect to the base, thanks to a spherical joint located in O 2 . The variation of the shaft orientation and the distance between O 1 and O 2 require the interconnection of O 1 andO 2 by a universal joint and a prismatic joint (Fig. 3).

The two serially-connected prismatic joints in the plane P 1 can be easily designed as a parallel planar mechanism, for instance with the solutions presented in [START_REF] Choi | Analysis and design of linear parallel compliant stage for ultraprecision motion based on 4-pp flexural joint mechanism[END_REF][START_REF] Wang | Input coupling analysis and optimal design of a 3-dof compliant micropositioning stage[END_REF][START_REF] Yong | Kinetostatic modeling of 3-rrr compliant micro-motion stages with flexure hinges[END_REF], in order to minimize the compliance of the mechanism that can lower the achievable shaft displacements.

The design of a compliant spherical joint by means of a planar parallel mechanism of 3-RRR type has been previously developed in [START_REF] Rubbert | Design and optimization for a cardiac active stabilizer based on planar parallel compliant mechanism[END_REF]. This mechanism can be placed in O 2 . With two planar architectures, one in P 1 and one in P 2 (Fig. 3), it becomes easy to minimize the distance a between the two planes, and finally amplify the displacements given by the piezoelectric stacks in P 1 thanks to the ratio between a and b, the length of the shaft. Compactness should also be improved by stacking two planar compliant structures together.

A serial subgroup with RRP mobilities, i.e. the DOF of a universal joint (RR) serially connected to a prismatic joint(P), connects the spherical joint and the end of the shaft in O 1 . At this point, it needs to be designed. Piezoelectric stacks will deliver high forces to counterbalance the cardiac forces exerted on the shaft tip. The subgroup will therefore be subjected to high loads. Converting the RRP chain in three serially connected equivalent compliant joints may lead to a compliant structure with limited stiffness, that will exhibit significant deflections. Therefore, this section deals with the design of a planar compliant mechanism with RRP mobilities.

Step 1: Selection of a Mechanism: the 3-US Parallel Manipulator

An interesting parallel mechanism is the 3-DOF 3-US mechanism, considered for lamina emergent mechanisms and for foldable mechanisms [START_REF] Andersen | Principles and preliminary concepts for compliant mechanically reactive armor[END_REF][START_REF] Qin | Forward displacement analysis of two foldable 3us parallel mechanisms[END_REF], illustrated in Figure 6. The architecture of the 3-US mechanism is interesting since it has three identical legs only composed of a universal joint in A i and a spherical joint in B i that can be broken down into five revolute joints, which are easy to manufacture.

A 1 A 1 B 1 B 1 A 2 A 2 B 2
Here, the planar configuration is interesting as the possible motions of the end-effector are translations normal to the plane of the mechanism (Fig. 5a) and rotations around the axes in the plane of the mechanism (Fig. 5b and Fig. 5b). So, in the planar configuration, the end-effector of the 3-US mechanism has precisely the RRP mobilities.

Plane of the manipulator

V 1 V 2 V 3 V 4 (a) Translation velocity vector field. V 1 V 2 V 3
Plane of the manipulator (b) First rotation velocity vector field. Moreover, in the planar configuration, at least one Type 2 singular configuration can be identified. In fact, if the first or the second revolute joints of the universal joints are locked, it is not possible to counterbalance the normal forces applied to the end-effector. In this case, the end-effector exhibits instantaneous motions corresponding to the desired RRP mobilities.

As for the design of the 1-DOF compliant mechanism illustrated in the previous section, the architecture of the 3-US may be simplified in a 3-RS mechanism. But another simplified architecture could be obtained in the planar configuration with another actuation mode that would finally ease the design and the manufacturing of the compliant mechanism.

We therefore perform the singularity analysis of the 3-US in the planar configuration for the different possible actuation modes.

Step 2: Singularity Analysis of the 3-US Parallel

Manipulator for Different Actuation Modes Each leg of the 3-US parallel mechanism is composed of a universal joint and a spherical joint. The universal joint is similar to two revolute joints with perpendicular and intersecting axes. The spherical joint can be broken down into three revolute joints with perpendicular and intersecting axes as shown in Figure 6. Hence, there are 15 3 = 455 possible actuation modes. Among these 455 modes, 5 of them are symmetric, i.e. the same rotational joint on each leg is actuated. If we consider that the manipulator has similar legs, there are also 150 unique asymmetric actuation modes. Among these 155 possible unique actuation modes there may be many singular configurations which could lead to different compliant mechanism architectures.

A i B i P O u 1i u 2i u 3i u 4i u 5i
Analyzing the five symmetric actuation modes of the 3-US parallel manipulator is indeed sufficient to analyze the 155 possible unique actuation modes. This will be shown later in the paper, after detailing the singularity analysis of the symmetric actuation modes.

A direct analysis of the singularities of the extended forward Jacobian matrix involves the calculation of its determinant which may be a difficult task even with symbolic computation softwares [START_REF] Merlet | Parallel robots[END_REF]. Here, the singularities are analyzed with the screw theory [START_REF] Kong | Type Synthesis of Parallel Mechanisms[END_REF], which allows us to obtain the global wrench system of the manipulator. In fact, the degeneration of the global wrench system of a parallel manipulator is directly related to the degeneration of its extended forward kinematic Jacobian matrix. The singularity analysis of the 3-US manipulator is therefore performed through the analysis of its global wrench system degeneration. In [START_REF] Rubbert | A planar rrp compliant mechanism based on the singularity analysis of a 3-us parallel mechanism[END_REF] the singularity analysis of the mechanism was performed in the whole workspace for the five symmetric actuation modes. Screw theory and Grassmann-Cayley algebra were then used. Here, we perform the singularity analysis for all possible actuation modes of the 3-US manipulator but only in the planar configuration. In this situation, the use of the screw theory is sufficient.

The global wrench system of the 3-US is spanned by the constraint wrench system and its actuation wrench system. The constraint wrench system describes how the end-effector is constrained by the leg of the manipulator and the actuation wrench system describes how the actuators act on the end-effector. Therefore, in a non-singular pose, the global wrench system describes how the end-effector is mechanically fully constrained. If the global wrench system degenerates, the end-effector is no more constrained and the manipulator reaches a parallel singularity.

Twist system of the 3-US

A twist is a screw representing the instantaneous motion of a rigid body. An infinite-pitch twist ε ∞ represents a pure translation, whereas a zero-pitch twist ε 0 represents a pure rotation. As the 3-US can be represented using only revolute joints, the twist system T i associated with the i-th leg of the 3-US is spanned by five zero-pitch twists defined as [START_REF] Kong | Type Synthesis of Parallel Mechanisms[END_REF]:

εi 01 = u 1i a i × u 1i , εi 02 = u 2i a i × u 2i εi 03 = u 3i b i × u 3i εi 04 = u 4i b i × u 4i , εi 05 = u 5i b i × u 5i , i = 1, 2, 3 (3)
u 1i and u 2i are the unit vectors of the first and second revolute joint axes of the universal joint of the i-th leg. u 3i , u 4i and u 5i are the unit vectors of the revolute joints associated with the spherical joint of the i-th leg. a i and b i are the Cartesian coordinate vectors of points A i and B i shown in Figure 6. The twist system T of the 3-US is the intersection of T 1 , T 2 and T 3 , namely,

T 3US = 3 i=1 T i (4)

Constraint wrench system

A wrench is a screw representing a system of forces and moments acting on a rigid body. The constraint wrench system describes how the legs constrain the end-effector of the 3-US parallel manipulator. Hence, for each leg, the constraint wrench associated to the leg must be reciprocal to the twist system T i of the leg. In a non-singular configuration, the constraint wrench system W c of the 3-US is a three-system spanned by the following three pure forces (Fig. 7):

F c i = n i b i × n i , i = 1, 2, 3 (5)
n i being the unit vector of --→ A i B i .

F c 2 F c 3 F c 1 A 1 A 3 A 2 B 1 B 2 B 3
Fig. 7: Constraint forces applied by the legs to the movingplatform.

Actuation wrench system

The actuation wrench system W a of the 3-US manipulator depends on its actuation scheme and describes how the actuators act on the end-effector. Hence, for each leg, the actuation wrench should be reciprocal to the twists in the leg, except for the twist associated with the actuated joint. Moreover, it should lie in the constraint wrench system W c . In case the first revolute joint of each leg is actuated, W a is spanned by the following three pure forces, called actuation forces (Fig. 8): In case the second revolute joint of each leg is actuated, W a is spanned by the following three pure forces:

F a 1i = u 2i b i × u 2i , i = 1, 2, 3 (6)
F a 2i = u 1i b i × u 1i , i = 1, 2, 3 (7)
In case the j-th revolute joint of each leg is actuated, j = 3, 4, 5, W a is spanned by the following three pure forces:

F a ji = v ji c ji × v ji , i = 1, 2, 3 (8)
v ji being the unit vector of the intersection line L ji of planes P 1i and P ji . c ji is the Cartesian coordinate vector of any point C ji on line L ji . P 1i is spanned by vectors u 1i and u 2i and passes through point A i . P 3i is spanned by vectors u 4i and u 5i and passes through point B i . P 4i is spanned by vectors u 3i and u 5i and passes through point B i . P 5i is spanned by vectors u 3i and u 4i and passes through point B i (Fig. 9 for the fourth actuation mode).

Global wrench system

Let k be the number of the actuated joint in each leg for the k-th actuation mode of the mechanism, k = 1, . . . , 5. As a result, the global wrench system W k 3US of the 3-US associated with its k-th actuation scheme is spanned by W a and W c , namely,

W k 3US = span( F c 1 , F c 2 , F c 3 , F a k1 , F a k2 , F a k3 ), k = 1, . . . , 5 (9)

Instantaneous gained motions

For the manipulator in the planar configuration and for the five symmetrical actuation modes, the three actuation forces are in the plane of the manipulator (Fig. 10a). It means that the actuation wrench system degenerates and the 3-US manipulator reaches a parallel singularity in such a configuration. As the three actuation forces are coplanar, the actuators are not able to counterbalance the forces normal to the end-effector and the moments around the axes in the plane of the manipulator.

In section 3.3.3 we have seen that actuating any of the five revolute joints of a leg produces an actuation force in the plane of the planar configuration. In other words, there is no actuation mode that produces non-coplanar actuation forces. It means that for any of the 150 asymmetrical possible actuation modes, the actuation wrench system will always be composed of coplanar pure forces in the planar configuration of the 3-US manipulator. As a consequence, the planar configuration of the 3-US parallel manipulator is, for the 155 possible actuation modes, a singular configuration of Type 2 where the end-effector exhibits the desired instantaneous RRP mobilities. 155 unique architectures can thus be considered to design a compliant structure with adequate mobilities. Design and manufacturing considerations are used to make a selection.

Step 3: Selection of an actuation mode

A first remark is that the design of a spherical compliant joint is complex. In fact, two design options can be considered. One solution consists in designing a single revolute notch [START_REF] Xu | Mechanical design of compliant parallel micromanipulators for nano scale manipulation[END_REF]. With this solution, the ratio between the translational and the rotational stiffnesses along the revolution axis of this joint can be low. Thus, the kinematic behavior would be different of that of a spherical joint. Moreover, the small cross-section can lead to high stresses. A second solution consists in designing a spherical compliant joint with three compliant revolute joints. Stiffness properties are improved, but since we would like to have a device composed of two planar mechanisms, the joint needs to be machined in a plate. Manufacturing three compliant revolute joints with orthogonal and intersecting axes as proposed by [START_REF] Xu | Mechanical design of compliant parallel micromanipulators for nano scale manipulation[END_REF] is then complex. It is more interesting to choose an actuation mode which allows to suppress one revolute joint that composes the spherical joints and therefore to have a compliant mechanism only composed of universal joints.

In order to machine this planar structure, it is more convenient to machine flexure joints with revolute joint axes in the plane. Hence, it seems easier to consider the fifth symmetric actuation mode (u 5i , Fig. 6), which suppresses the three revolute axes normal to the base and moving platform in the planar configuration of the 3-US manipulator. As a result, the 3-US architecture becomes a 3-UU architecture as illustrated in Figure 11.

To the best of our knowledge, such an architecture has never been considered to obtain this type of mobilities. Without the proposed approach, it would have been very difficult to identify this structure for the design of the active stabilizer.

Step 4: Design of the compliant mechanism

The 3-UU compliant mechanism is only composed of universal joints. Interesting designs of compliant universal joints have been proposed in [START_REF] Xu | Mechanical design of compliant parallel micromanipulators for nano scale manipulation[END_REF] and [START_REF] Tanik | Compliant cardan universal joint[END_REF], but they can not be manufactured in a planar structure or requires an assembly.

We therefore propose for the design of the compliant universal joints to manufacture two compliant revolute joints in the plane with intersecting axes in A i or B i depending on the considered universal joint. The 3-UU compliant mechanism is then designed by replacing each revolute joint by a circular flexure hinge. A computer-aided design (CAD) of the compliant 3-UU mechanism is shown in Figure 12. The dimensional synthesis of the obtained compliant mechanism is performed by considering the other elements that compose the active stabilizer, i.e. the two prismatic joints and the spherical joint.

The length of the stabilizer shaft b = 250 mm is constrained by the medical context. The only way to modify the amplification ratio of the device is therefore to modify the distance a between planes P 1 and P 2 . The distance a can not exceed 12 mm (Fig. 3) to get sufficient shaft displacements. In this situation, static analysis shows that the PZT stacks deliver forces above 100 N in O 1 .

For a first dimensional synthesis of the 3-UU mechanism, a trial-and-error design is performed using finite element analysis (FEA). To limit the number of possibilities, we only tuned two design parameters: the radius and the thickness of the circular notches. As a matter of fact, the notch thicknesses mainly influence the global stiffness of the compliant structure and the circular notch radius mainly in-fluences the level of the stress concentration. The goal is then to find a good compromise between output displacement amplitude of the whole mechanism and the maximal stress level. Finally, the thickness of the 3-UU mechanism and the outer radius of its legs have been chosen equal to 5 mm and 35 mm, respectively. The compliant joints have a thickness equal to 0.2 mm, a width equal to 15 mm and the radius of the circular notches is equal to 2 mm.

Performances of the compliant mechanism

With the considered design, PZT stacks should apply forces in the order of 300 N on the planar 3-UU compliant mechanism in order to counterbalance the cardiac forces during the stabilization task. Stiffness of the mechanism must be high enough in order to limit the deflections that can lower the device performance. In Figure 13a and Figure 13c, 300 N forces are applied in the plane XY . This produces an inplane displacement of less than 20 µm which is small compared to the 0.7 mm that can be generated by the device. In comparison, in Figure 13e, applying 300 N along Z produces a displacement of 10 mm. The in-plane stiffnesses are therefore 200 times greater than along Z. In Figure 13b and Figure 13d, a moment of 100 N.mm around X and Y is applied and produces a rotation of 1.3e-2 rad. In comparison, in Figure 13f applying a moment of 100 N.mm around Z only produces a rotation of 1.0e-5 rad. The torsional stiffness is 1300 times greater than the other rotational stiffnesses. The estimation of the compliance of the 3-UU structure is given by the compliance matrix, a 6 × 6 matrix, which relates the displacement u = [x; y; z; θ x ; θ y ; θ z ], in millimeters and in radians, to the load L = [F x ; F y ; F z ; M x ; M y ; M z ], in newtons and newtons per millimeter, applied at the center of the end-effector:

u = C.L (10)
The 6×6 compliance matrix C is evaluated using a finite element analysis (PTC Pro/Mechanica):

C =        
4.6e-5 1.0e-8 2.6e-8 -4e-8 -6.7e-6 3.5e-9 5.4e-8 4.6e-5 1.6e-7 -6.6e-6 8.0e-6 7e-10 1.4e-8 2.0e-8 3.5e-2 2.3e-6 1.1e-6 2.9e-9 -5.6e-9 0.0 4.6e-6 1.3e-4 -1.2e-7 9.3e-11 0.0 1.7e-9 6.8e-7 1.1e-8 1.3e-4 2.5e-9 1.4e9 0.0 0.0 0.0 0.0 1e-7

        (11
) When three forces are applied at the center of the mechanism, there is only a displacement along the vertical axis. When three moments are applied at the center of the mechanism, there are only two significant rotations about in-plane axes. Therefore, from a kinematic point-of-view, the behavior of the mechanism is in accordance with the need for a RRP mechanism.

Integration into the cardiac stabilizer and new performances

The 3-UU compliant mechanism has been synthesized considering the active stabilizer requirements. The CAD modeling of the whole compensation mechanism composed of the two planes, which integrates the 3-UU compliant mechanism, is illustrated in Figure 14. For the design of the two prismatic joints (Fig. 3), we choose a 2-PRR 1-RR planar mechanism. The 3-UU mechanism is then integrated in the platform of the 2-PRR 1-RR planar mechanism as illustrated in Figure 14a. A first dimensional synthesis of the compliant spherical joint has been performed in [START_REF] Rubbert | Design and optimization for a cardiac active stabilizer based on planar parallel compliant mechanism[END_REF] according to the requirements for active cardiac stabilization, and is integrated in the device as illustrated in Figure 14b. The planar structures in P 1 and P 2 have thicknesses equal to 5 mm and 6 mm respectively.

Yet, the synthesis has been achieved without an optimization process of the whole device. The presented design allows us to produce a displacement of 0.7 mm which is sufficient to compensate for the flexibilities of the device and the mounting system, according to [START_REF] Bachta | The cardiolock project: Design of an active cardiac stabilizer for cardiac surgery[END_REF]. With an optimization process, this output displacement could still be increased as the maximal stress level reaches only 82% of the fatigue limit of the material, which is here alloy steel. Finally, the size of the device is divided by four compared to the previous one, the Cardiolock 2 (Fig. 2). The device compactness is significantly improved by considering an assembly of planar structures.

Conclusion

In this paper a design approach of compliant mechanism based on the analysis of singularities of parallel manipulators has been presented. This approach is an extension of the rigid-body replacement approach that takes advantage of the knowledge of the singularity analysis of parallel manipulators. In addition to taking advantage of the intrinsic stiffness properties of parallel manipulators, the analysis of the singularities in this design approach introduces a simplification step of the compliant mechanism architecture. This design approach has first been presented with the example of the design of 1-DOF compliant mechanism and then successfully applied to the design of a compact 3-DOF compliant mechanism for a surgical device. Finally, an original 3-UU planar compliant mechanism with RRP mobilities has been obtained and presented.

(a) Step 1 :

 1 Selection of a parallel manipulator: 3-PRR planar parallel manipulator. (b) Step 2: Singular configuration for the first actuation mode. (c) Step 2: Singular configuration for the second actuation mode. (d) Step 2: Singular configuration for the third actuation mode. (e) Step 3: Selection of the most suitable actuation mode. (f) Step 4: Design of the compliant mechanism.

Fig. 1 :

 1 Fig. 1: Principle of the design approach based on singularity analysis of parallel manipulators. Colored joints represent the actuated joints considered locked, big arrows represent the possible instantaneous motions of the end-effector.

Fig. 3 :

 3 Fig. 3: The new considered architecture for the active stabilizer.

Fig. 4 : 3 -

 43 Fig. 4: 3-US parallel manipulator and its planar configuration.

  Plane of the manipulator (c) Second rotation velocity vector field.

Fig. 5 :

 5 Fig. 5: Instantaneous motions of the 3-US manipulator in the planar configuration.

Fig. 6 : 3 -

 63 Fig. 6: 3-US manipulator broken down into rotational joints.

Fig. 8 :

 8 Fig. 8: Constraint and actuation wrench system of the 3-US parallel manipulator for the first actuation mode.

Fig. 9 :

 9 Fig. 9: Constraint and actuation forces of the 3-US parallel manipulator for the fourth actuation mode.

  First actuation mode.

  Second actuation mode.

  Third actuation mode.

  Fith actuation mode.

Fig. 10 :

 10 Fig. 10: Constraint and actuation forces of the 3-US parallel manipulator for the five actuation modes.

Fig. 11 : 3 -

 113 Fig. 11: 3-UU planar mechanism with RRP mobilities.

Fig. 12 :

 12 Fig. 12: CAD view of the 3-UU compliant mechanism.

  M x = 100 N.mm. M z = 100 N.mm.

Fig. 13 :

 13 Fig. 13: Finite element analysis of the 3-UU mechanism. Forces F and moments M are applied at the center of the mechanism (color online).

  Integration of the 3-UU compliant mechanism into the 2PRR-1RR actuation mechanism.

  Integration of the compliant 3-RRR orientation mechanism[START_REF] Rubbert | Design and optimization for a cardiac active stabilizer based on planar parallel compliant mechanism[END_REF].

Fig. 14 :

 14 Fig. 14: CAD view of the final device integrating the different elements composing the compensation mechanism.