De la recherche

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

Pour sortir d'un labyrinthe ou réparer un cœur humain, le même problème se pose ! Il s'agit en fait de calculer une trajectoire.

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é.

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.

vue du robot da vinci, au premier plan la console maitre
Le robot Da Vinci.
Au premier plan, le chirurgien et la console maître ; au second plan : le patient et la console esclave.
planification de chirurgie
Planification de chirurgie assistée par ordinateur.
Image © INRIA - Équipe CHIR.

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é.

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 x0, il faut atteindre un but défini par une région de l'espace. Ce but se formalise par une équation c0(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 ci(x) = 0 qui doit ne pas être vérifiée (sinon une collision se produirait). On cherche donc à maintenir ci(x) > 0 (qui correspond à l'extérieur de l'obstacle).

 

Pour passer d'un état initial x0 à un état final x00, 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.

On peut donc définir un calcul qui, en se basant sur un tel potentiel, va générer une trajectoire « automatiquement ». Nous vous proposons ici un petit exemple où vous pouvez regarder se tracer une telle trajectoire générée par un mécanisme qui a été défini à partir d'un calcul biologiquement plausible, peut-être voisin de ce qui se fait dans les structures cérébrales qui ont cette faculté.

Ce petit exemple est juste une illustration, mais le même calcul a été utilisé pour résoudre des problèmes plus compliqués.

Vous devriez aussi chercher à... faire échouer le mécanisme ! En effet, on ne trouve pas toujours de trajectoire d'un point donné à un autre. C'est peut-être trop long (le présent calcul s'arrête de lui-même au bout de quelques centaines de pas de calcul), ou bien la solution passe peut-être trop près des obstacles... quel que soit le fromage, un rongeur peut se décourager !

Cliquez sur Génération de la trajectoire pour visualiser le tracé. Nous vous proposons deux exemples : simple, avec un obstacle triangulaire, et labyrinthe.
Vous pouvez modifier le point de départ avec le bouton de droite de la souris ou en combinant clic gauche et touche contrôle, et le point d'arrivée avec le bouton du milieu ou en combinant clic gauche et touche majuscule.
En cliquant sur Effacer, vous effacez l'interface avec les points et les obstacles, vous pouvez alors placer d'autres points (comme indiqué précédemment) et tracer vous-même des obstacles avec le bouton de gauche de la souris (cliquez deux fois pour finir un tracé).

Si l'applet ne s'affiche pas correctement :
Vérifiez votre configuration technique - Visionnez une démonstration

 

Des solutions alternatives

D'autres solutions existent pour résoudre ce problème de génération de trajectoire. Dans le cas de la chirurgie cardiaque, c'est une méthode géométrique qui a été employée. Les obstacles ont été triangulés et au sein de cette représentation, la trajectoire n'est plus à rechercher que sur le diagramme des médiatrices. Le problème a ainsi été suffisament simplifié pour recevoir une solution voisine de celle décrite ci-dessus, mais avec une meilleure efficacité.

Dans d'autres cas, il ne s'agit pas de trouver une trajectoire compliquée, mais de suivre ou de corriger une trajectoire prédéfinie : la modélisation du problème est alors plus simple.

Dans tous les cas, résoudre ce problème représente un pas important tant pour la recherche en informatique que pour de nombreuses applications.

Marcelle et André sont des personnages imaginaires, évidemment, mais le robot qui aide le Pr Carpentier à sauver des vies existe, et moi, je peux vous le certifier : le regard d'une « Marcelle » qui retrouvait « son André », ce regard, mes collègues et moi l'avons croisé. Pour de vrai.

Et le petit rongeur, je l'ai vu lui aussi, quand j'ai rendu visite à mes collègues du laboratoire de Marseille. En partant, en revanche, ça a été vraiment la galère, je vous dis pas le labyrinthe pour sortir de Marseille. J'en ronge encore ce qu'il reste de frein à ma pauvre voiture. Comment ? Utiliser mon calcul de génération de trajectoire ? Non mais, je vous parle de Marseille, là, eh ? Les mathématiques c'est bien joli, mais il y tout de même des problèmes où il vaut mieux s'en remettre à la Bonne Mère, peuchère : informaticien mais pas fada, vé !

Niveau de lecture

Aidez-nous à évaluer le niveau de lecture de ce document.

Il vous semble :

Si vous souhaitez expliquer votre choix, vous pouvez ajouter un commentaire (qui ne sera pas publié).