Une nouvelle approche de la conception de plans de mouvement pour plusieurs robots se développe –

Dans un bâtiment de plusieurs étages avec de nombreuses pièces, des centaines d’obstacles et des milliers d’endroits à inspecter, les plusieurs dizaines de robots se déplacent comme une unité cohérente. Ils se déploient dans un modèle de recherche pour vérifier minutieusement l’ensemble du bâtiment tout en fractionnant simultanément les tâches afin de ne pas perdre de temps à doubler sur leurs propres chemins ou à revérifier les endroits que d’autres robots ont déjà visités.

Une telle cohésion serait difficile à atteindre pour les contrôleurs humains, et encore moins pour un contrôleur artificiel à calculer en temps réel.

«Si un problème de contrôle a trois ou quatre robots qui vivent dans un monde avec seulement une poignée de pièces, et si la tâche collaborative est spécifiée par des règles logiques simples, il existe des outils de pointe qui peuvent calculer une solution optimale qui satisfait la tâche dans un laps de temps raisonnable », ont déclaré Michael M. Zavlanos, Mary Milus Yoh et Harold L. Yoh, Jr. Professeur agrégé de génie mécanique et de science des matériaux à l’Université Duke.

«Et si vous ne vous souciez pas de la meilleure solution possible, vous pouvez résoudre quelques pièces de plus et des tâches plus complexes en quelques minutes, mais seulement une douzaine de robots en tête», a déclaré Zavlanos. “Pas plus que cela, et les algorithmes actuels sont incapables de surmonter le volume des possibilités pour trouver une solution.”

Dans un nouvel article publié en ligne le 29 avril dans le Journal international de recherche en robotique, Zavlanos et son récent doctorant, Yiannis Kantaros, qui est maintenant chercheur postdoctoral à l’Université de Pennsylvanie, proposent une nouvelle approche à ce défi appelée STyLuS *, pour la synthèse de logique temporelle optimale à grande échelle, qui peut résoudre des problèmes de plus en plus vastes. que ce que les algorithmes actuels peuvent gérer, avec des centaines de robots, des dizaines de milliers de salles et des tâches très complexes, en une petite fraction du temps.

Pour comprendre la base de la nouvelle approche, il faut d’abord comprendre la logique temporelle linéaire, qui n’est pas aussi effrayante que cela puisse paraître. Supposons que vous vouliez programmer une poignée de robots pour collecter le courrier d’un quartier et le livrer au bureau de poste tous les jours. La logique temporelle linéaire est un moyen d’écrire les commandes nécessaires pour accomplir cette tâche.

Par exemple, ces commandes peuvent inclure de visiter chaque maison dans un ordre séquentiel, de retourner au bureau de poste et d’attendre que quelqu’un récupère le courrier collecté avant de repartir. Bien que cela puisse être facile à dire en anglais, il est plus difficile à exprimer mathématiquement. La logique temporelle linéaire peut le faire en utilisant ses propres symboles qui, bien que pouvant ressembler à des Klingons pour l’observateur commun, sont extrêmement utiles pour exprimer des problèmes de contrôle complexes.

“Le terme linéaire est utilisé parce que les points dans le temps ont un successeur unique basé sur un modèle linéaire discret du temps, et temporel se réfère à l’utilisation d’opérateurs tels que jusqu’à, suivant, finalement et toujours”, a déclaré Kantaros. “En utilisant ce formalisme mathématique, nous pouvons créer des commandes complexes telles que ‘visiter toutes les maisons sauf la maison deux’, ‘visiter les maisons trois et quatre dans un ordre séquentiel’ et ‘attendre d’être en maison une avant d’aller dans la maison cinq ». “

Pour trouver des contrôleurs de robot qui satisfont ces tâches complexes, l’emplacement de chaque robot est mappé en un point de données discret appelé «nœud». Ensuite, à partir de chaque nœud, il existe plusieurs autres nœuds qui constituent une prochaine étape potentielle pour le robot.

Un contrôleur traditionnel recherche dans chacun de ces nœuds et les chemins potentiels à emprunter entre eux avant de déterminer le meilleur moyen de s’y retrouver. Mais à mesure que le nombre de robots et d’emplacements à visiter augmente et que les règles logiques à suivre deviennent plus sophistiquées, l’espace de la solution devient incroyablement grand en très peu de temps.

Un problème simple avec cinq robots vivant dans un monde avec dix maisons pourrait contenir des millions de nœuds, capturant tous les emplacements et comportements de robot possibles pour accomplir la tâche. Cela nécessite beaucoup de mémoire pour stocker et de puissance de traitement pour la recherche.

Pour contourner ce problème, les chercheurs proposent une nouvelle méthode qui, plutôt que de construire ces graphes incroyablement grands dans leur intégralité, crée à la place des approximations plus petites avec une structure arborescente. À chaque étape du processus, l’algorithme sélectionne au hasard un nœud du grand graphique, l’ajoute à l’arborescence et recâblera les chemins existants entre les nœuds de l’arborescence pour trouver plus de chemins directs du début à la fin.

“Cela signifie qu’au fur et à mesure que l’algorithme progresse, cet arbre que nous développons progressivement se rapproche de plus en plus du graphe réel, que nous ne construisons jamais réellement”, a déclaré Kantaros. “Puisque notre graphe incrémental est beaucoup plus petit, il est facile à stocker en mémoire. De plus, comme ce graphe est un arbre, la recherche de graphe, qui autrement a une complexité exponentielle, devient très facile car il ne nous reste plus qu’à tracer la séquence des nœuds parents retour à la racine pour trouver le chemin souhaité. “

Il était admis depuis longtemps que la croissance des arbres ne pouvait pas être utilisée pour rechercher dans l’espace des solutions possibles pour ces types de problèmes de commande de robot. Mais dans le journal, Zavlanos et Kantaros montrent qu’ils peuvent le faire fonctionner en mettant en œuvre deux astuces intelligentes. Tout d’abord, l’algorithme choisit le nœud suivant à ajouter en fonction des informations sur la tâche à accomplir, ce qui permet à l’arbre de se rapprocher rapidement d’une bonne solution au problème. Deuxièmement, même si l’algorithme développe des arbres, il peut toujours détecter des cycles dans l’espace graphique d’origine qui capturent des solutions à de telles tâches de logique temporelle.

Les chercheurs montrent que cette méthode trouvera toujours une réponse s’il y en a une, et qu’elle finira toujours par trouver la meilleure possible. Ils montrent également que cette méthode peut arriver à cette réponse de manière exponentielle. Travailler avec un problème de 10 robots recherchant dans un espace de grille de 50 x 50 – 250 maisons pour récupérer le courrier – les algorithmes de pointe actuels prennent 30 minutes pour trouver une solution optimale.

STyLuS * le fait en 20 secondes environ.

«Nous avons même résolu des problèmes avec 200 robots qui vivent sur un monde en grille de 100 par 100, ce qui est beaucoup trop grand pour les algorithmes d’aujourd’hui», a déclaré Zavlanos. «Bien qu’il n’existe actuellement aucun système qui utilise 200 robots pour faire quelque chose comme livrer des paquets, il pourrait y en avoir dans le futur. Et ils auraient besoin d’un cadre de contrôle comme STyLuS * pour pouvoir les livrer tout en satisfaisant des règles logiques complexes. . “