💻 computer science

Bi-Layer Ant Colony Optimization for Multi-Robot Task Allocation and Routing in Delivery Applications

Cet article propose un algorithme d'optimisation par colonies de fourmis à deux niveaux qui unifie l'allocation des tâches et le routage en un seul problème d'optimisation, démontrant une efficacité et une évolutivité supérieures en réduisant la distance totale parcourue jusqu'à 17,7 % et le temps d'exécution de près de 20 % par rapport aux bases de référence MILP et PSO dans les applications de livraison multi-robots.

Auteurs originaux : Le Na Nguyen, Thanh Long Nguyen, Thanh Thao Ton Nu, Quan Le, Manh Duong Phung

Publié 2026-08-26

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Le Na Nguyen, Thanh Long Nguyen, Thanh Thao Ton Nu, Quan Le, Manh Duong Phung

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Dans le monde trépidant de la logistique moderne, le mouvement des marchandises repose sur des flottes de robots mobiles travaillant de concert. Ces machines doivent naviguer dans des environnements complexes pour ramasser des articles et les livrer à des destinations spécifiques, mais le défi ne réside pas seulement dans le fait de conduire d'un point A à un point B. La véritable difficulté est la coordination : décider quel robot doit s'occuper de quel colis et déterminer l'ordre le plus efficace pour visiter une série de lieux. Si ces décisions sont prises de manière isolée, les robots peuvent finir par croiser leurs trajectoires inutilement, parcourir des distances plus longues que nécessaire ou rester à attendre oisivement pendant que d'autres travaillent. Ce problème, connu sous le nom d'allocation de tâches multi-robots, se situe à l'intersection de la robotique et des mathématiques, où l'objectif est d'orchestrer un groupe d'agents indépendants pour atteindre un objectif collectif avec une efficacité maximale. Pour les services de livraison, la différence entre un bon plan et un excellent plan se traduit directement par du temps gagné, une consommation d'énergie réduite et un service plus rapide pour les clients.

Des chercheurs de l'Université Fulbright du Vietnam et de l'Université Vin ont proposé une nouvelle façon de résoudre ce casse-tête de coordination, s'éloignant de la méthode traditionnelle consistant à diviser le problème en étapes distinctes. Au lieu de décider d'abord quel robot reçoit quelle tâche, puis de déterminer l'itinéraire de chaque robot, leur approche traite ces deux décisions comme un problème unique et interconnecté. Ils ont développé un système inspiré du comportement de recherche de nourriture des véritables fourmis. Dans la nature, les fourmis laissent derrière elles une odeur chimique appelée phéromone au cours de leurs déplacements ; plus l'odeur est forte sur un chemin, plus il est probable que d'autres fourmis le suivent, menant finalement la colonie vers la route la plus courte pour atteindre la nourriture. Les chercheurs ont adapté ce principe biologique en un algorithme informatique qui apprend simultanément la meilleure façon d'assigner les tâches aux robots et le meilleur ordre pour les visiter. En utilisant deux couches de ces traces de senteurs numériques — une couche guidant quel robot prend quelle tâche, et une autre couche guidant la séquence des arrêts pour chaque robot — le système permet à toute la flotte d'optimiser ses performances en tant qu'ensemble unifié plutôt que comme une collection d'entités séparées.

Pour tester cette idée, l'équipe a créé un environnement simulé utilisant un logiciel de robotique standard, plaçant trois robots identiques dans un espace de 10 mètres sur 15 mètres rempli d'obstacles statiques. Ils ont mené des expériences où les robots devaient accomplir des séries de cinq, dix ou vingt tâches de livraison, avec des lieux de ramassage et de dépose générés de manière aléatoire pour chaque essai. Le nouvel algorithme a été mis à l'épreuve face à deux autres méthodes courantes utilisées dans le domaine : l'une reposant sur des calculs mathématiques stricts pour trouver la réponse parfaite, et l'autre utilisant un autre type d'intelligence en essaim. Les résultats ont montré que la nouvelle approche surpassait systématiquement les autres. Dans les simulations, l'algorithme a réduit la distance totale que les robots devaient parcourir jusqu'à 17,7 % par rapport à la méthode mathématique stricte et de près de 10 % par rapport à l'autre méthode d'essaim. Il a également réduit considérablement le temps, diminuant le temps de complétion total de près de 20 % dans certains cas.

Le succès de cette méthode réside dans sa capacité à voir la vue d'ensemble. Les approches traditionnelles résolvent souvent l'assignation des tâches et la planification des itinéraires comme des étapes séparées, ce qui peut conduire à des résultats sous-optimaux car une bonne assignation peut nécessir un itinéraire difficile, ou un itinéraire court peut être impossible avec une certaine assignation. En résolvant les deux à la fois, le nouveau système évite ces pièges. Les simulations ont démontré qu'à mesure que le nombre de tâches augmentait, la nouvelle méthode restait stable et efficace, tandis que les autres méthodes montraient plus de variabilité et produisaient souvent des itinéraires plus longs. Les chercheurs ont observé que l'algorithme ne se contentait pas de trouver des chemins plus courts, mais qu'il le faisait avec un haut degré de cohérence, suggérant qu'il s'agit d'un outil fiable pour gérer des flottes de robots dans des scénarios de livraison complexes. Bien que ces conclusions proviennent de simulations informatiques plutôt que de tests réels dans la rue, elles fournissent des preuves solides que traiter l'assignation des tâches et la planification des itinéraires comme un problème couplé peut améliorer considérablement l'efficacité des systèmes multi-robots. Ces travaux suggèrent que les futures flottes de livraison pourraient fonctionner avec une plus grande rapidité et des coûts énergétiques moindres si elles adoptent cette approche unifiée de la prise de décision.

Résumé technique : Optimisation par colonies de fourmis à deux couches pour l'allocation de tâches et le routage multi-robots

Définition du problème

L'article traite du problème d'allocation de tâches multi-robots (MRTA) dans le contexte des applications de livraison et de logistique. Le défi central consiste à coordonner une flotte de robots mobiles pour exécuter un ensemble de tâches de livraison, où chaque tâche est composée d'un lieu de ramassage spécifique et d'un lieu de dépose.

Le problème d'optimisation est défini comme un processus de décision couplé nécessitant deux sorties simultanées :

Allocation des tâches : Déterminer quel robot effectue chaque tâche spécifique.
Séquençage des tâches : Déterminer l'ordre optimal dans lequel un robot exécute ses tâches assignées.

L'objectif est de minimiser la distance de trajet totale de l'ensemble de la flotte tout en garantissant que chaque tâche est exécutée exactement une fois par un seul robot. Les auteurs notent que les approches existantes traitent souvent l'assignation, le séquençage et l'exécution comme des étapes indépendantes optimisées séparément. Cette séparation peut conduire à une coordination globale sous-optimale, des mouvements redondants et une efficacité du système réduite. L'article formule le MRTA comme un problème d'optimisation unifié où les décisions d'assignation et de séquençage sont interdépendantes.

Méthodologie : Optimisation par colonies de fourmis (ACO) à deux couches

Pour résoudre le problème d'optimisation formulé, les auteurs proposent un algorithme d'Optimisation par Colonies de Fourmis (ACO) à deux couches. Contra\text{à} aux méthodes hiérarchiques traditionnelles qui résolvent les couches de manière séquentielle, cette approche intègre deux couches de décision interdépendantes dans un processus de colonie unique.

Cadre de base

L'algorithme emploie une métaheuristique basée sur une population inspirée du comportement de recherche de nourriture des fourmis. Chaque « fourmi » de la colonie construit une solution complète en naviguant simultanément à travers deux couches de décision :

Couche d'assignation des tâches :
- Détermine l'allocation des tâches aux robots ( $x_{i,j}$ ).
- Utilise une matrice de phéromones $\tau_{assign} \in \mathbb{R}^{m \times n}$ (tâches $\times$ robots) représentant la désirabilité apprise d'assigner la tâche $j$ au robot $i$ .
- L'information heuristique ( $\eta_{assign}$ ) est dérivée de l'inverse de la distance entre la position de départ du robot et le lieu de ramassage de la tâche.
Couche de séquençage des tâches :
- Détermine l'ordre de visite ( $\pi_i$ ) des tâches assignées à chaque robot.
- Utilise une matrice de phéromones $\tau_{seq} \in \mathbb{R}^{m \times m}$ représentant la désirabilité de la transition de la tâche $j$ vers la tâche $k$ au sein de la route d'un même robot.
- L'information heuristique ( $\eta_{seq}$ ) est dérivée de l'inverse de la distance entre la dépose de la tâche actuelle et le ramassage de la tâche suivante.

Exécution de l'algorithme

L'algorithme procède par cycles itératifs :

Construction : Chaque fourmi assigne de manière probabiliste les tâches aux robots en se basant sur les valeurs de phéromones et d'heuristique de la couche d'assignation. Une fois les assignations effectuées, la couche de séquençage construit la route pour chaque robot. La première tâche est sélectionnée en fonction de la proximité avec le point de départ du robot, et les tâches suivantes sont échantillonnées en fonction de la phéromone de séquençage et des valeurs heuristiques.
Évaluation : La distance de trajet totale pour la solution construite est calculée, en sommant les distances pour tous les robots (départ-vers-ramassage, ramassage-vers-dépose, et dépose-vers-prochain-ramassage).
Mise à jour des phéromones : Après que toutes les fourmis ont construit leurs solutions, les traces de phéromones sur les deux matrices sont mises à jour. Cela implique :
- Évaporation : Réduction des niveaux de phéromones existants pour éviter la stagnation.
- Renforcement : Dépôt de nouvelles phéromones proportionnellement à la qualité de la solution ( $Q/C(a)$ ), où les meilleures solutions (coût plus faible) déposent plus de phéromones. Les équations de mise à jour garantissent que les paires d'assignation ainsi que les transitions de tâches spécifiques dans la route sont renforcées.

Principales contributions

L'article identifie les contributions primaires suivantes :

Fonction d'objectif unifiée : La formulation d'une nouvelle fonction de coût qui transforme le MRTA en un problème d'optimisation couplé, capturant explicitement l'interdépendance entre la distribution globale des tâches et la planification locale des routes.
Architecture ACO à deux couches : L'introduction d'un nouveau cadre algorithmique qui intègre l'assignation et le séquençage dans un processus de colonie unique utilisant deux matrices de phéromones distinctes et interconnectées. Cela permet l'optimisation simultanée de l'allocation des tâches et de la planification des routes.
Validation des performances : Des expériences comparatives exhaustives démontrant l'efficacité de la méthode proposée par rapport à la Programmation Linéaire en Nombres Entiers Mixtes (MILP) et à l'Optimisation par Essaim de Particules (PSO).

Résultats expérimentaux

La méthode proposée a été évaluée dans un environnement de simulation ROS 2 Humble et Gazebo utilisant trois robots TurtleBot3. Les expériences ont été menées selon trois scénarios avec 5, 10 et 20 tâches.

Métriques de performance :

Distance de trajet totale : L'ACO à deux couches a systématiquement obtenu la distance de trajet totale moyenne la plus faible pour toutes les tailles de tâches.
- Comparé à MILP, l'ACO a réduit la distance totale d'environ 17,7 % (à 5 tâches).
- Comparé à PSO, l'ACO a réduit la distance totale d'environ 9,8 %.
Temps de complétion : La méthode proposée a également démontré des temps de complétion de tâches plus rapides.
- Comparé aux méthodes de référence, l'ACO a réduit le temps de complétion de près de 20 %.
Stabilité et scalabilité :
- L'ACO a présenté des écarts-types plus faibles pour la distance et le temps par rapport à PSO et MILP, indiquant une convergence plus stable.
- À mesure que la complexité des tâches augmentait (jusqu'à 20 tâches), l'ACO maintenait des performances supérieures, tandis que MILP et PSO montraient une dispersion accrue et des coûts plus élevés.

Signification et affirmations

L'article affirme que le cadre ACO à deux couches répond efficacement à la limitation de la séparation de l'assignation des tâches et du routage dans les approches MRTA existantes. En optimisant ces décisions conjointement, la méthode réduit les mouvements redondants et améliore l'efficacité globale de la mission.

Les auteurs concluent que l'ACO à deux couches est une solution évolutive et fiable pour les tâches de livraison multi-robots, offrant un équilibre entre exploration et exploitation qui produit des routes plus courtes et plus cohérentes que les méthodes exactes traditionnelles (MILP) ou d'autres métaheuristiques (PSO). Ce travail suggère que cette approche unifiée est particulièrement précieuse pour améliorer l'efficacité des systèmes de logistique et de livraison du monde réel. Les travaux futurs porteront sur l'extension de l'approche aux environnements dynamiques, aux flottes de robots hétérogènes et aux contraintes de communication.