Les robots deviennent de plus en plus capables de se déplacer dans le monde, mais leur donner une liste d'instructions sur ce qu'ils doivent faire est souvent trop rigide pour la réalité désordonnée d'un hôpital, d'un entrepôt ou d'une planète lointaine. Une simple liste pourrait dire « allez ici, puis allez là », mais elle peine face aux questions de type « et si » qui définissent la vie réelle : Et si le robot voit une tache et doit la nettoyer ? Et si deux tâches doivent se produire dans un intervalle de temps spécifique, mais pas nécessairement dans un ordre fixe ? Pendant des années, les chercheurs ont utilisé une méthode appelée ordres partiels temporisés pour résoudre cela. Voyez cela comme un organigramme où des flèches indiquent quelles tâches doivent se produire avant d'autres, et des horloges garantissent qu'elles se produisent dans certaines limites de temps. Cette approche est claire pour les humains et facile à traiter pour les ordinateurs, mais elle présente un angle mort. Elle ne peut pas facilement gérer des règles de synchronisation complexes entre des tâches sans rapport, ni dire facilement : « Ne faites cette étape suivante que si une condition spécifique dans l'environnement est remplie ».

Une équipe de chercheurs de l'Université du Colorado à Boulder a développé une nouvelle façon de combler cette lacune, créant un système qu'ils appellent Ordres Partiels Temporisés Conditionnels. Ce cadre permet aux ingénieurs d'écrire des missions de robotique bien plus flexibles et réalistes. Le nouveau système peut imposer des règles telles que : « Ces deux tâches doivent se produire dans les vingt minutes qui les séparent, quel que soit l'ordre de priorité », ou encore : « Si le robot passe près d'une zone spécifique, il doit effectuer un nouvel ensemble de tâches immédiatement ». Les chercheurs ont prouvé qu'ils pouvaient traduire ces missions conditionnelles complexes en un problème mathématique qu'un ordinateur peut résoudre pour trouver le chemin le plus rapide possible. Cependant, ils ont également découvert qu'à mesure que ces missions deviennent plus complexes, le temps de calcul de l'ordinateur peut exploser, devenant trop lent pour être utile. Pour corriger cela, ils ont inventé une méthode pour diviser la mission massive et compliquée en morceaux plus petits et indépendants. Ils ont résolu chaque petit morceau séparément, puis ont recousu les réponses ensemble. Leurs tests ont montré que cette approche pouvait rendre le processus de planification jusqu'à dix mille fois plus rapide qu'en essayant de résoudre l'ensemble de la mission à la fois, sans sacrifier la qualité du plan.

Le cœur de ce travail réside dans la manière dont les chercheurs ont étendu le langage utilisé pour parler aux robots. Dans leurs travaux précédents, la mission d'un robot était une carte statique d'événements. Si une tâche était sur la carte, le robot devait la faire. Si une règle de synchronisation existait, elle s'appliquait à l'ensemble de la mission. Le nouveau système introduit une couche de logique qui réagit au monde. Imaginez un robot d'hôpital chargé de collecter des échantillons de sang et de livrer les résultats. Dans l'ancien système, le robot suivrait un emploi du temps fixe. Dans le nouveau système, on peut dire au robot : « Si tu passes par hasard devant l'aile de cardiologie, tu dois aussi récupérer un rapport d'électrocardiogramme et le livrer dans les quinze minutes ». Le robot n'a pas besoin de savoir à l'avance où se trouve l'aile de cardiologie ; il suit simplement son chemin, et si la condition est remplie, les tâches supplémentaires et leurs règles de synchronisation strictes s'activent automatiquement. Cela rend les instructions du robot beaucoup plus proches de la façon dont un superviseur humain donnerait des ordres, en s'adaptant à ce qui se passe réellement sur le terrain.

Pour que cela fonctionne, les chercheurs ont dû résoudre un casse-tête mathématique difficile. Ils ont montré que trouver le meilleur chemin pour un robot avec ces règles conditionnelles revient à résoudre un problème de routage complexe, similaire à la recherche du moyen le plus efficace de visiter un ensemble de lieux avec des fenêtres de temps spécifiques. Ils ont traduit cela dans un format que les ordinateurs peuvent résoudre à l'aide d'une technique appelée programmation linéaire en nombres entiers mixtes. Cette méthode garantit que le robot trouvera un chemin qui respecte toutes les règles, mais elle a un inconvénient. À mesure que le nombre de tâches et de conditions augmente, la taille du problème mathématique croît de telle sorte que même des ordinateurs puissants peuvent rester bloqués, mettant des heures ou des jours à trouver une réponse. C'est un goulot d'étranglement courant en robotique : plus les instructions sont flexibles, plus il est difficile pour l'ordinateur de concevoir le plan.

La solution des chercheurs a été de cesser d'essayer de résoudre tout le problème à la fois. Ils ont réalisé que de nombreuses missions sont composées de groupes de tâches plus petits et autonomes, étroitement liés entre eux mais seulement lâchement connectés au reste de la mission. Par exemple, une séquence de tâches de nettoyage déclenchée par une tache pourrait être une unité autonome qui commence lorsque le robot entre dans la zone de la tache et se termine lorsqu'il en sort. Les chercheurs ont développé un algorithme pour identifier automatiquement ces groupes, ou « sous-tâches », au sein de la mission plus large. Ils ont ensuite résolu la synchronisation et le chemin pour chaque petit groupe indépendamment. Une fois qu'ils ont obtenu le meilleur chemin pour chaque petit groupe, ils ont traité chaque groupe comme une étape unique dans la mission globale, en y intégrant le temps nécessaire pour accomplir ce groupe. Cela a transformé un puzzle massif et impossible à résoudre en une série de petits puzzles faciles.

Les résultats de cette approche ont été frappants. Lors de leurs tests, les chercheurs ont comparé leur nouvelle méthode à l'ancienne façon de résoudre l'ensemble de la mission à la fois. Pour des missions simples, les deux méthodes étaient rapides. Mais à mesure que les missions devenaient plus complexes, avec plus de conditions et des règles de synchronisation plus serrées, l'ancienne méthode ralentissait considérablement, prenant parfois des minutes ou même des heures. La nouvelle méthode de décomposition, cependant, est restée rapide, résolvant souvent les mêmes problèmes en moins d'une seconde. Dans les cas les plus difficiles, la nouvelle méthode était jusqu'à dix mille fois plus rapide. Crucialement, les chercheurs ont prouvé mathématiquement que cette vitesse ne se faisait pas au détriment de la qualité. Les plans générés en découpant la mission en morceaux étaient tout aussi bons que les plans générés en résolvant l'ensemble à la fois. Ils ont trouvé les mêmes chemins optimaux et respecté les mêmes contraintes de temps.

Les chercheurs ont démontré cela avec deux scénarios du monde réel. Dans l'un, un robot dans un entrepôt devait visiter trois étagères et revenir à un quai. Si le robot empruntait un chemin qui traversait une tache d'huile, il devait s'arrêter pour nettoyer trois zones spécifiques avant de continuer. Le système a réussi à planifier un itinéraire évitant la tache si possible, mais si le chemin le plus court nécessitait de la traverser, le robot insérait automatiquement la séquence de nettoyage dans son plan, garantissant qu'il termine le nettoyage dans les délais requis. Dans un second scénario, un rover martien devait analyser des échantillons de sol. Si le rover passait près d'une formation rocheuse spécifique, il devait naviguer vers un nouvel emplacement et collecter un échantillon dans un intervalle de temps strict. Le système a planifié un itinéraire évitant la formation rocheuse quand cela était possible, mais lorsque le terrain forçait le rover à passer à proximité, le plan s'adaptait de manière fluide pour inclure la tâche d'échantillonnage supplémentaire.

Ce travail représente une étape importante pour rendre les robots plus autonomes et adaptables. En permettant aux spécifications de mission d'être à la fois conditionnelles et temporellement complexes, les chercheurs ont donné aux ingénieurs un outil pour écrire des instructions qui semblent plus naturelles et moins fragiles. La capacité de décomposer ces instructions complexes en morceaux gérables signifie que les robots peuvent désormais gérer des missions qui étaient auparavant trop coûteuses en calcul pour être planifiées. Les chercheurs ont noté que, bien que leur travail actuel se concentre sur des robots uniques, la prochaine étape consiste à étendre ce cadre à des groupes de robots travaillant ensemble. Pour l'instant, la méthode constitue un moyen robuste de garantir que lorsqu'un robot reçoit l'ordre de faire quelque chose de complexe dans un monde changeant, il peut déterminer exactement comment le faire, rapidement et correctement.