Restauration de chemin multi-agents dans des environnements continus

Par Kristýna Janovská et Pavel Surynek

Imaginez si toutes nos voitures pouvaient conduire elles-mêmes – la conduite autonome devient possible, mais dans quelle mesure? Pour obtenir un véhicule quelque part seul peut ne pas sembler aussi délicat si l’itinéraire est clair et bien défini, mais que se passe-t-il s’il y a plus de voitures, chacune essayant de se rendre à un autre endroit? Et si nous ajoutons des piétons, des animaux et d’autres éléments non comptabilisés? Ce problème a récemment été de plus en plus étudié et déjà utilisé dans des scénarios tels que la logistique de l’entrepôt, où un groupe de robots déplace des boîtes dans un entrepôt, chacun avec son propre objectif, mais tous se déplaçant tout en s’assurant de ne pas entrer en collision et de faire leurs itinéraires – des chemins – aussi courts que possible. Mais comment formaliser un tel problème? La réponse est Mapf – Recherche de chemin multi-agents (Silver, 2005).

La recherche de chemin multi-agents décrit un problème où nous avons un groupe d’agents – robots, véhicules ou même des personnes – qui essaient chacun de passer de leurs positions de départ à leurs positions d’objectif à la fois sans jamais entrer en collision (être dans la même position en même temps).

En règle générale, ce problème a été résolu sur les graphiques. Les graphiques sont des structures capables de simplifier un environnement en utilisant ses points focaux et ses interconnexions entre eux. Ces points sont appelés sommets et peuvent représenter, par exemple, les coordonnées. Ils sont connectés par des bords, qui connectent les sommets voisins et représentent des distances entre eux.

Si toutefois nous essayons de résoudre un scénario réel, nous nous efforçons de nous rapprocher du plus possible la réalité. Par conséquent, une représentation discrète (en utilisant un nombre fini de sommets) peut ne pas suffire. Mais comment rechercher un environnement continu, c’est-à-dire celui où il y a essentiellement une quantité infinie de sommets connectés par des bords de tailles infiniment petites?

C’est là que quelque chose appelé algorithmes basé sur l’échantillonnage entre en jeu. Des algorithmes tels que RRT * (Karaman et Frazzoli, 2011), que nous avons utilisés dans notre travail, sélectionnez au hasard les coordonnées (échantillon) dans notre espace de coordonnées et utilisez-les comme sommets. Plus il y a de points échantillonnés, plus la représentation de l’environnement est précise. Ces sommets sont connectés à celui de leurs voisins les plus proches qui minimise la longueur du chemin du point de départ au point nouvellement échantillonné. Le chemin est une séquence de sommets, mesurée comme une somme des longueurs des bords entre elles.

Figure 1: Deux exemples de chemins reliant les positions de départ (bleu) et les positions d’objectif (vert) de trois agents. Une fois qu’un obstacle est présent, les agents planifient des chemins incurvés lisses autour de lui, évitant avec succès l’obstacle et les uns des autres.

Nous pouvons obtenir un chemin près de cette façon, bien qu’il y ait encore un problème. Les chemins créés de cette façon sont encore quelque peu cahoteux, car la transition entre les différents segments d’un chemin est nette. Si un véhicule devait emprunter ce chemin, il devrait probablement se tourner en même temps lorsqu’il atteindra la fin d’un segment, comme le font certains aspirateurs robotiques lorsqu’ils se déplacent. Cela ralentit considérablement le véhicule ou un robot. Une façon de résoudre ce problème consiste à prendre ces chemins et à les lisser, afin que les transitions ne soient plus nettes, mais des courbes lisses. De cette façon, des robots ou des véhicules qui se déplacent dessus peuvent se déplacer en douceur sans jamais s’arrêter ou ralentir considérablement lorsqu’ils ont besoin d’un tour.

Notre papier (Janovská et Surynek, 2024) a proposé une méthode de recherche de chemin multi-agents dans des environnements continus, où les agents se déplacent sur des ensembles de chemins lisses sans entrer en collision. Notre algorithme est inspiré par la recherche basée sur les conflits (CBS) (Sharon et al.2014). Notre extension dans un espace continu appelé recherche basée sur les conflits à l’environnement continu (CE-CBS) fonctionne à deux niveaux:

Figure 2: Comparaison des chemins trouvés avec l’algorithme CBS discret sur une grille 2D (à gauche) et ce-CBS dans une version continue du même environnement. Trois agents passent des points de départ bleus aux points verts. Ces expériences sont réalisées dans le Robotic Agents Laboratory de la Faculté de technologie de l’information de l’Université technique tchèque de Prague.

Premièrement, chaque agent recherche individuellement un chemin. Cela se fait avec l’algorithme RRT * comme mentionné ci-dessus. Le chemin résultant est ensuite lissé à l’aide de courbes B-Spline, des courbes polynomiales par morceaux appliquées aux sommets du chemin. Cela supprime les virages nets et rend le chemin plus facile à parcourir pour un agent physique.

Des chemins individuels sont ensuite envoyés au niveau supérieur de l’algorithme, dans lequel des chemins sont comparés et des conflits sont trouvés. Le conflit survient si deux agents (qui sont représentés comme des corps circulaires rigides) se chevauchent à tout moment. Dans l’affirmative, des contraintes sont créées pour interdire à l’un des agents de passer à travers l’espace contradictoire à un intervalle de temps au cours de laquelle il était auparavant présent dans cet espace. Les deux options qui limitent l’un des agents sont essayés – un arbre d’éventuels paramètres de contrainte et leurs solutions est construit et étendu à chaque conflit trouvé. Lorsqu’une nouvelle contrainte est ajoutée, ces informations transmettent à tous les agents qu’elle concerne et que leurs chemins sont re-planifiés afin d’éviter le temps et l’espace contraints. Ensuite, les chemins sont à nouveau vérifiés pour la validité, et cela se répète jusqu’à ce qu’une solution sans conflit, qui vise à être aussi courte que possible.

De cette façon, les agents peuvent se déplacer efficacement sans perdre de la vitesse tout en tournant et sans entrer en collision les uns avec les autres. Bien qu’il existe des environnements tels que des couloirs étroits où le ralentissement ou même l’arrêt peut être nécessaire pour que les agents passent en toute sécurité, Ce-CBS trouve des solutions dans la plupart des environnements.

Cette recherche est soutenue par la Fondation des sciences tchèques, 22-31346S.

Vous pouvez lire notre papier ici.

Références

• Janovská, K. et Surynek, P. (2024). Fédération de chemin multi-agents dans un environnement continuCorr.
• Sharon, G., Stern, R., Felner, A., et Sturtevant, NR (2014). Recherche basée sur les conflits pour un chemin multi-agent optimalIntelligence artificielle.
• Karaman, S. et Frazzoli, E. (2011). Algorithmes basés sur l’échantillonnage pour une planification de mouvement optimaleCorr.
• Piegl, L. et Tiller, W. (1996). Le livre NurbsSpringer-Verlag, New York, États-Unis, deuxième édition.
• Silver, D. (2005). Fending coopératifActes de la première conférence d’intelligence artificielle et de divertissement numérique interactif, Marina del Rey, Californie, États-Unis.