Résumé Technique : Réallocation Prédictive par Seuil de Confiance (TGPR)

Énoncé du Problème

L'allocation de tâches multi-robots (MRTA) décentralisée repose généralement sur des enchères basées sur le marché (ex. : Protocole Contract Net, CBBA) qui supposent une livraison de messages fiable. Dans les déploiements réels, la communication sans fil est sujette aux pertes en raison de l'atténuation de parcours, des interférences et, plus crucialement, d'une dégradation matérielle persistante (ex. : antennes usées, émetteurs à puissance limitée) qui varie d'un robot à l'autre.

Les méthodes robustes actuelles traitent ce problème soit en réduisant la fréquence des messages, soit en réattribuant les tâches uniquement après la détection d'une défaillance. Ces approches traitent l'incertitude de communication comme un désagrément de planification à absorber par des tentatives de réémission ou une réconciliation périodique, plutôt que comme une quantité apprenable. De plus, les modèles de « confiance » existants dans le MRTA se concentrent sur la capacité d'un agent à accomplir une tâche, et non sur la fiabilité de la liaison de communication elle-même. Cela conduit à deux modes de défaillance principaux dans les réseaux à pertes :

1. Affamement (Starvation) : Une tâche est attribuée mais l'accusé de réception est perdu ; le coordinateur attend indéfiniment tandis qu'aucun autre robot n'intervient.
2. Duplication : Le coordinateur expire en attendant un accusé de réception retardé (mais non perdu) et réattribue la tâche, provoquant l'exécution de la même tâche par deux robots.

Méthodologie : Réallocation Prédictive par Seuil de Confiance (TGPR)

Le TGPR est un mécanisme d'enchères décentralisé qui intègre une estimation bayésienne par robot de la fiabilité du cycle aller-retour de communication dans le cycle standard annonce-offre-attribution-accusé de réception. Il modifie la logique de décision du coordinateur sans altérer le protocole de messagerie sous-jacent.

1. Estimation Bayésienne de la Confiance Aller-Retour

Le coordinateur maintient une distribution postérieure Beta, $Beta(\alpha_i, \beta_i)$, pour chaque robot $i$, représentant la probabilité d'un cycle aller-retour réussi entre l'attribution et l'accusé de réception.

• Mises à jour : Les paramètres sont mis à jour en fonction des résultats observés (succès au délai $\delta$ ou expiration).
• Décroissance : Un facteur de décroissance $\lambda < 1$ permet à l'estimation de suivre des conditions non stationnaires (ex. : développement de pannes matérielles en cours de mission).
• Score de Confiance : La fiabilité estimée est $\hat{p}_i = \alpha_i / (\alpha_i + \beta_i)$.

2. Évaluation des Offres avec Remise de Confiance

Contrairement aux enchères standards qui classent les soumissionnaires selon leur utilité brute ($u_{ij}$), le TGPR classe les candidats par une utilité pondérée par la confiance :
$$\hat{u}_{ij} = u_{ij} \cdot \hat{p}_i$$
Cela donne la priorité aux robots qui sont à la fois capables et joignables, distinguant ainsi un robot hautement capable doté d'une liaison historiquement médiocre d'un robot légèrement moins capable doté d'une liaison fiable.

3. Délai d'Expiration Prédictif Adaptatif

Au lieu d'un délai d'expiration global fixe, le TGPR calcule un délai par robot $\tau_i$ basé sur la distribution de délai apprise :
$$\tau_i = \text{clip}(\mu_i + z\sigma_i, \tau_{min}, \tau_{max})$$
Cela accorde de la patience aux liaisons historiquement lentes mais fiables, tout en permettant une récupération rapide pour les liaisons qui n'ont jamais échoué.

4. Revendication Unilatérale par Témoin avec Seuil de Confiance

Pour réduire la latence de récupération, les robots inactifs qui interceptent une diffusion d'attribution peuvent revendiquer une tâche si l'échéance annoncée expire sans diffusion de confirmation.

• Mécanisme : Si un témoin revendique la tâche, le coordinateur tente d'annuler l'attribution du détenteur original.
• Fenêtre de Grâce : Une courte fenêtre de grâce empêche la revendication du témoin de devancer la propre logique de repli du coordinateur, garantant que la logique de réattribution du coordinateur n'est pas préemptée prématurément.

Contributions Clés

1. Conception du Banc d'Essai : Un simulateur à événements discrets présentant un modèle de canal avec perte dépendante de la distance, un brouillage transitoire et un facteur de fiabilité matérielle par robot persistant et apprenable ($h_i$). Les auteurs démontrent que sans ce différentiel persistant, les mécanismes basés sur la confiance n'offrent aucun avantage par rapport aux heuristiques basées sur la distance.
2. Algorithme TGPR : Un nouveau mécanisme d'enchères combinant l'offre avec remise de confiance, les délais d'expiration adaptatifs par robot et la revendication par témoin.
3. Évaluation Contrôlée : Une comparaison systématique avec trois bases de référence (Délai fixe naïf, Retour exponentiel, et Réconciliation périodique) à travers cinq régimes de qualité de canal, deux tailles d'équipe et une ablation de l'hétérogénéité matérielle.

Résultats Expérimentaux

L'étude a évalué 4 800 essais de balayage principal et 2 000 essais d'ablation.

Efficacité et Réduction du Gaspillage

Le TGPR démontre des améliorations statistiquement significatives de l'efficacité de la communication et de la réduction du gaspillage :

• Exécution en Double : Réduite de 23,9 % par rapport à la base de référence naïve (10,65 % contre 13,99 %).
• Surcharge de Messagerie : Réduite de 13,6 % (167,2 contre 193,6 messages par tâche complétée).
• Tendance : Ces avantages augmentent à mesure que la qualité du canal se dégrade et que la fraction de robots au matériel dégradé augmente.

Taux d'Achèvement des Tâches

Contrairement à l'hypothèse selon laquelle une allocation tenant compte de la fiabilité améliorerait le débit global, le TGPR n'améliore pas le taux d'achèvement global des tâches.

• Performance : Dans des conditions de canal médiocres et sévères, le TGPR complète significativement moins de tâches que la base de référence à délai fixe naïf (ex. : 0,434 contre 0,466 dans des conditions sévères à $N=25$).
• Résultat d'Ablation : L'écart du taux d'achèvement s'élargit (de 1,1 % à 1,9 %) à mesure que la fraction de matériel dégradé augmente, contredisant l'attente selon laquelle le mécanisme de confiance "rattraperait son coût" en évitant le mauvais matériel.

Cause Racine du Coût du Taux d'Achèvement

Les auteurs attribuent le déficit du taux d'achèvement à deux mécanismes spécifiques :

1. Inflation de la Variance Non Bornée : Sous des taux d'échec élevés et soutenus, la règle de mise à jour du délai d'expiration fait gonfler l'estimation de la variance du délai ($\sigma_i$) sans décrue suffisante. Cela provoque une augmentation des délais appris vers la limite maximale, perdant ainsi leur pouvoir discriminatoire entre les robots sains et dégradés.
2. Taxe de Latence Fixe : La fenêtre de grâce de la revendication par témoin introduit un délai fixe sur chaque cycle de récupération, accumulant un coût lors de défaillances fréquentes.

L'analyse de sensibilité des paramètres confirme que la réduction du multiplicateur de délai ($z$) peut récupérer le taux d'achèvement au prix d'une augmentation des doublons et de la messagerie, indiquant un compromis contrôlable plutôt qu'un défaut fondamental de l'estimation de la confiance.

Signification et Revendications

Le papier positionne le TGPR non pas comme une amélioration universelle des enchères plus simples, mais comme une solution spécialisée pour des contraintes opérationnelles spécifiques.

• Limite Opérationnelle : Le TGPR est un gain substantiel pour les déploiements où la bande passante de communication est rare ou la répétition de l'effort physique (ex. : consommation de batterie, usure des actionneurs) est la contrainte limitante. Dans ces scénarios, la réduction du gaspillage et de la surcharge de messagerie est la métrique de succès principale.
• Limitation : Lorsque la seule métrique est le débit brut d'achèvement des tâches dans des environnements hostiles, le TGPR n'est pas une amélioration stricte par rapport aux bases de référence à délai fixe plus simples et peut être moins performant.
• Aperçu Scientifique : L'étude fournit un contre-exemple critique à l'hypothèse selon laquelle la « confiance » aide toujours. Elle démontre que les mécanismes basés sur la confiance nécessitent un signal persistant et apprenable (dégradation matérielle) pour être efficaces ; dans les flottes où l'imprévisibilité est purement positionnelle et transitoire, les mécanismes de confiance n'offrent aucun avantage mesurable.
• Rapport Honnête : Les auteurs rapportent explicitement le compromis, notant que le coût du mécanisme (réduction du taux d'achèvement) augmente avec l'hétérogénéité matérielle, contrairement à leurs attentes initiales, et l'attribuent à des comportements algorithmiques spécifiques (inflation de la variance) plutôt qu'à des facteurs externes.

L'étude conclut que le TGPR offre un compromis quantifiable et précieux : sacrifier une partie du débit d'achèvement pour réduire considérablement la surcharge de communication et l'exécution en double, à condition que l'environnement de déploiement présente des différentiels de fiabilité matérielle persistants et apprenables.