Coordination multi-robot résistante aux pannes par maximisation sous-modulaire avec contrainte de $k$-connectivité

Des chercheurs publient sur arXiv (2610.13049) une méthode de coordination multi-robot qui tient compte d'un angle mort des approches existantes: la perte de connectivité réseau après la défaillance de robots. Les cadres de maximisation sous-modulaire servent déjà à répartir des actions entre robots pour des tâches de couverture, de suivi de cibles ou de collecte d'information. Leurs variantes dites résilientes anticipent la perte ou le retrait adversarial de certains robots. Les auteurs introduisent la « Resilient k-Connected Submodular Maximization », qui optimise conjointement la performance de la tâche, la résilience et la connectivité de communication. Techniquement, ils s'appuient sur une réduction de la connectivité fondée sur le théorème de Menger, sur un algorithme glouton sensible à la connectivité avec un mécanisme de repli qui préserve la faisabilité, et sur une nouvelle analyse de courbure. Le résultat garantit, dans le pire cas après défaillance, un objectif égal à au moins [max(1-νf(I), h(N,β))]² · ρ · (1/κf) · (1-e^(-κ_f)) de celui de l'affectation résiliente optimale respectant la connectivité. Les expériences portent sur du suivi de cibles multi-robot.

L'enjeu est pratique pour quiconque déploie des essaims ou des flottes coopérantes: les garanties de résilience classiques supposent implicitement que les robots survivants peuvent encore échanger leurs informations. Or, si la perte de quelques unités scinde le réseau en sous-groupes isolés, la coordination s'effondre, même quand l'objectif de tâche reste théoriquement atteignable. En imposant une k-connectivité, c'est-à-dire un réseau qui reste connexe après la suppression de jusqu'à k-1 nœuds, la méthode offre une borne de performance qui reste valable dans des scénarios de panne réaliste, notamment en environnement hostile ou en inspection et surveillance. Le facteur ρ quantifie explicitement le coût de cette contrainte, ce qui permet à un intégrateur d'arbitrer entre redondance du réseau et performance nominale. Il faut toutefois relativiser: il s'agit d'un résultat théorique de garanties d'approximation, validé en simulation sur une tâche de suivi de cibles. Il n'existe ni déploiement sur flotte réelle, ni chiffres de performance en conditions industrielles, et les bornes de pire cas sont souvent conservatrices par rapport au comportement observé.

Ce travail prolonge la lignée de la maximisation sous-modulaire pour la planification multi-robot, où les algorithmes gloutons offrent le célèbre ratio (1-1/e) sous contrainte de matroïde, puis les extensions résilientes qui protègent contre les retraits adverses. La difficulté ici tient au fait que l'ensemble des affectations faisables sous contrainte de connectivité n'est pas un matroïde, ce qui empêche d'appliquer directement les garanties classiques fondées sur la courbure. Les auteurs montrent néanmoins qu'ils retrouvent la garantie non contrainte dans les cas limites. La suite logique serait de tester l'approche avec des contraintes de communication réalistes (portée radio, latence, pertes de paquets), sur des flottes hétérogènes et sur du matériel réel. Cela permettrait de mesurer l'écart entre garanties théoriques et performances effectives.