Cet article aborde le problème de la planification de mouvements multi-robots (MRMP), c'est-à-dire le calcul de trajectoires sans collision pour plusieurs robots dans un environnement continu partagé. Les cadres existants décomposent efficacement la MRMP en sous-problèmes mono-robot, mais la planification de mouvements spatio-temporels avec obstacles dynamiques est particulièrement complexe dans les environnements encombrés ou à couloirs étroits. Dans cet article, nous proposons un nouveau planificateur, le graphe spatio-temporel d'ensembles convexes (ST-GCS), qui couvre systématiquement la région spatio-temporelle sans collision avec des ensembles convexes au lieu de s'appuyer sur un échantillonnage aléatoire. En étendant le graphe d'ensembles convexes (GCS) à la dimension temporelle, le ST-GCS formule des trajectoires optimales en temps dans une optimisation convexe unifiée qui s'adapte naturellement aux contraintes de vitesse et aux heures d'arrivée flexibles. De plus, nous proposons une décomposition convexe exacte (ECD) qui « réserve » les trajectoires avec obstacles spatio-temporels afin de maintenir le graphe spatio-temporel d'ensembles convexes sans collision pour la planification ultérieure. Intégré à un cadre de planification à deux priorités, le ST-GCS atteint des taux de réussite nettement supérieurs et une meilleure qualité de solution que les planificateurs par échantillonnage de pointe, avec souvent des temps d'exécution bien plus rapides. Cela souligne l'avantage du ST-GCS par rapport au MRMP dans les environnements difficiles.
