Une solution au problème de la génération de trajectoires

Au même instant, dans le laboratoire marseillais du professeur Bruno Poucet, un petit rongeur cherche son chemin, tandis qu’à l’hôpital Européen George Pompidou, le professeur Alain Carpentier, chirurgien cardiologue, et son équipe, s’apprêtent une nouvelle fois à sauver une vie. Dans les deux cas, le même type de calcul mathématique est en train de s’effectuer. Certes, pas tout à fait avec le même outil : approchons-nous pour regarder.

Dans le laboratoire de Marseille, c’est dans l’hippocampe du petit rongeur, cette partie du cerveau qui est située sous le cortex, que le calcul est en train de se dérouler. Le problème c’est que – oh oui – il y a un petit morceau de fromage aux effluves attirants, là, pas loin, mais fichtre, le chemin pour y parvenir est bigrement compliqué ! Cela dit, peu importe qui a pu faire une chose pareille, car dans l’hippocampe de notre petit animal quelque chose de fantastique est en train de se produire : chaque lieu, chaque endroit de ce labyrinthe à l’issue prometteuse est en train de se faire répertorier, en vrac d’ailleurs, mais au fur et à mesure des essais, voilà qu’un chemin, découpé en toutes petites portions, commence à émerger de ces neurones à l’activité de plus en plus structurée. Et soudain, ça y est, sans hésitation, la sortie est par là : ah ! le délicieux fromage est enfin trouvé.

Au fur et à mesure de ses déplacements, la cellule de lieu de l’hippocampe observée par le biologiste décharge selon la position absolue de l’animal dans la scène : d’où son nom de « cellule de lieu ». On distingue pour six trajets marqués en bleu et blanc les portions où la cellule est inactive (en bleu) ou active (en blanc), toujours au même endroit. Si on cumule toutes ces données, dans la vue de droite, il apparaît une véritable cartographie où les zones qui correspondent à l’activité de cette cellule sont bien localisées. Images : Bruno Poucet.

Ce que notre petit rongeur ignore, c’est que quelqu’un avait tout prévu : le labyrinthe, mais aussi ces petits fils indolores qui sortent de son cerveau et qui, reliés à un ordinateur, ont pu délivrer un maximum d’informations sur les calculs de trajectoire que l’hippocampe et les structures cérébrales connexes ont effectués. Mais pour l’instant, le professeur Poucet fait une pause. Peut-être pense-t-il à cette première médicale qui a été retransmise à la télé.

Le robot Da Vinci.
Au premier plan, le chirurgien et la console maître ; au second plan : le patient et la console esclave.

Marcelle (ou quel que se soit son prénom), les hippocampes de rats, je préfère vous le dire sans détour : c’est le cadet de ses soucis. À travers le rideau de larmes que cette jolie petite vieille dame essuie délicatement de son mouchoir brodé, elle ne pense qu’à une chose : que c’est trop tôt, beaucoup trop tôt, que son André ne peut pas partir comme ça, pas encore, même si ce crétin a eu bien tort de trop manger et de manger un peu trop arrosé. Ah ça il va l’entendre, celui là, quand il va se réveiller ! Oh oui. Oui. Pourvu que. Pourvu que son André puisse se réveiller.

Tout de même, je vous le demande un peu, à quel monde en est-on arrivé ? « Pas opérable », avait dit le premier chirurgien, c’était pourtant un « simple » pontage coronarien. Mais le reste du corps aussi était bien abimé. Alors, ouvrir la cage thoracique pour aller faire ce travail de couture, ça allait forcément mal se passer : « mort guéri », il paraît qu’on dit. Et puis, il y avait eu le Pr Carpentier, qui lui avait parlé d’un… robot !

Et maintenant, Marcelle essaie de s’imaginer les trois chirurgiens autour de l’énorme machine, qui a juste fait trois petits trous entre les côtes de son André, pour limiter le choc opératoire, et le Pr Carpentier qui pilote une caméra stéréoscopique en plongée entre poumons et cœur, et deux pinces, en train de coudre un nouveau vaisseau sanguin. Il y a même la télé qui filme ! D’ailleurs, il pourrait bien y avoir le Pape, tiens, pourvu qu’on le lui rende, son André.

Planification de chirurgie assistée par ordinateur.
Image © Inria – Équipe CHIR.

Elle a tout de même demandé à cette informaticienne, Ève Coste-Manière, dont l’équipe a conçu et développé les mécanismes logiciels les plus complexes, comment le robot se débrouillait. Eh bien figurez-vous, un des problèmes serait de générer une trajectoire pour les nombreux degrés de liberté du robot chirurgical, à travers le labyrinthe que représente le fait d’arriver à recoudre ce qu’il faut à son André.

Ce qu’il ne faut pas entendre ! En attendant, elle passerait bien à la pâtisserie : un énorme Paris-Brest, c’est le gâteau préféré de son André. Ils pourraient le partager tout doucement, tous les deux, en cachette des infirmières. Il paraît qu’il vient juste de revenir à sa chambre et qu’il va bientôt se réveiller. Il aura sûrement faim, ce goinfre, elle le connaît.

La stratégie à laquelle Dédale n’avait pas pensé

Le robot chirurgical, comme le rongeur, au départ, est dans un état donné. Son état, ce sont tous les degrés de liberté qui vont lui permettre d’effectuer la trajectoire. Pour le rongeur, ce sont ses muscles. Pour le robot, entre son socle mobile, ses pinces, sa caméra stéréoscopique, il y a une vingtaine de degrés de liberté. Trouver une trajectoire qui permette de passer d’un état à un autre, cela veut dire trouver pour tous les degrés de liberté une courbe qui parte de l’état initial et qui aboutisse à l’état final souhaité. On représente donc toutes les variables du problème dans un espace dont les dimensions correspondent à chaque paramètre à ajuster : il s’agit donc d’un espace de grandes dimensions.

Représentation schématique du problème de la génération de trajectoire.
D’un point de départ x₀, il faut atteindre un but défini par une région de l’espace. Ce but se formalise par une équation c₀(x) = 0 qui doit être vérifiée pour y arriver. De même, chaque obstacle est une région de l’espace dont la frontière est définie par une équation c_i(x) = 0 qui doit ne pas être vérifiée (sinon une collision se produirait). On cherche donc à maintenir c_i(x) > 0 (qui correspond à l’extérieur de l’obstacle).

Pour passer d’un état initial x₀ à un état final x₀₀, le chemin le plus court… serait un segment de droite reliant ces deux points, s’il n’y avait ni obstacle, ni contrainte. Des obstacles physiques, certes, comme le mur du labyrinthe du rongeur de Bruno Poucet ou les côtes et les organes de celui que nous nous sommes permis d’appeler André. Mais il y a d’autres contraintes à respecter : ne pas aller trop vite pour éviter de déraper, par exemple, cela veut dire ne pas dépasser une certaine vitesse, donc mettre un obstacle dans l’espace des vitesses possibles. Mathématiquement, cela signifie respecter une certaine inégalité.

Ce qu’il faut bien comprendre ici, c’est que dire « je vais résoudre un problème de calcul de trajectoire » c’est se donner un défi aussi compliqué que « je vais concevoir un algorithme qui va être capable de faire passer n’importe quel système d’un état dans un autre » donc capable de réaliser une action robotique peut-être bien compliquée.

C’est là un des grands défis informatiques auxquels les chercheurs se sont attaqués.

La bonne nouvelle, c’est qu’il existe une « solution universelle » à ce problème compliqué. Deux chercheurs américains, Christopher Connolly et Roderic Grupen, l’ont mis à jour il y a quelques années.

Prenons le labyrinthe avant que notre petit rongeur ne s’y hasarde, et jetons un drap sur lui, en faisant bien attention qu’au but à atteindre le drap touche le sol. Sur les murs du labyrinthe, le drap est à la hauteur la plus élevée. Ailleurs, le drap est à une hauteur intermédiaire. Posons ensuite une bille extrêmement légère à l’endroit initial et… laissons-la rouler : si le drap est bien lisse, sans pli, alors la bille va tout naturellement rouler de son point initial au point le plus bas : le but à atteindre. Elle ne rencontrera jamais d’obstacle, puisqu’elle roule vers le bas, le drap étant lui en hauteur sur le bord des murs du labyrinthe. Nous venons de construire un dispositif qui génère automatiquement une trajectoire de n’importe quel point initial vers le but choisi.

Il est très important que le drap n’ait pas de pli, ni de cuvette intermédiaire où la bille resterait coincée sans aller jusqu’au but recherché, mais ça aussi, il est possible de s’en assurer.

Une méthode à fort potentiel

Mathématiquement, définir un tel drap revient à définir pour chaque point de l’espace une valeur de hauteur : on parle de potentiel. Ce potentiel a une valeur minimale au but à atteindre, maximale au niveau des obstacles. Faire rouler la bille veut simplement dire se déplacer de proche en proche dans une direction où le potentiel est plus petit, pour aller vers son minimum. Avoir un drap sans pli veut dire avoir un potentiel sans minimum local, où partout il y a une pente : la variation de hauteur ne doit jamais s’annuler, sauf au but.

Un exemple de potentiel, avec un obstacle en fer à cheval et un but à atteindre au centre du carré. Le potentiel décroît régulièrement en direction du but et croît en direction des obstacles : suivre localement la pente de ce critère permet d’atteindre automatiquement le but en contournant les obstacles.

Les mathématiciens savent depuis des années que certains potentiels, appelés potentiels harmoniques parce qu’ils sont définis par une fonction harmonique, vérifient exactement cette propriété. En effet, une fonction harmonique est caractérisée par le fait que chaque valeur correspond à la valeur moyenne des valeurs voisines, par conséquent elle n’a pas d’« aspérités », de minima locaux.

Mais cette solution présente un avantage supplémentaire : les potentiels harmoniques peuvent facilement s’additionner entre eux. Alors, il devient possible non seulement de générer en une fois une trajectoire dans un espace entièrement connu à l’avance, mais aussi, au fur et à mesure de l’exploration, de définir des petits bouts de potentiel en vrac : des parties qui correspondent à une répulsion par rapport aux obstacles au fur et à mesure de leur découverte, et bien sûr un morceau qui correspond à une attirance vers le but. La somme de tous ces morceaux forme automatiquement le potentiel dont on a besoin. Toute ressemblance avec les cellules de l’hippocampe qui s’activent au fur et à mesure du passage d’une partie d’un lieu à un autre ne serait pas fortuite : cette ressemblance a même été détaillée par les chercheurs qui modélisent cette faculté au niveau biologique et artificiel.