Encadrants: Nicolas Bredeche et Nicolas Maudet
On s'intéresse à l'estimation de la contribution de chaque robot dans un essaim de robots devant réaliser une tâche fixée au préalable par l'utilisateur (par exemple du ramassage de balles). La performance de l'essaim de robots est considérée comme connue (par exemple, une valeur réelle entre 0 et 1). Cependant, la contribution de chaque robot à cette performance globale est inconnue, et peut varier grandement en fonction du rôle pris par le robot. Par exemple, un robot qui ne fait rien bénéficiera d'une bonne note sans contribuer, au même titre qu'un robot qui réalise une action essentielle.
Dans le cadre de ce projet, on souhaite mettre en place une méthode pour identifier la contribution de chaque robot. On dispose alors d'un ensemble de robots, et d'un simulateur qui permet d'estimer la performance globale d'un groupe constitué de l'ensemble des robots, d'une partie, voire d'un seul individu. Le but de ce projet est de mettre en place cet environnement de test et, dans un premier temps, d'implémenter une méthode naïve d'estimation de la contribution marginale (valeur de Shapley, indice de Banzhaf), en commençant par implémenter la méthode décrite dans l'article [1].
Bien qu'elle donne un résultat exact, la complexité d'une telle méthode la rend difficile à appliquer en pratique pour de grande taille d'essaim. Ainsi, dans un second temps, on explorera comment obtenir une estimation approximée de la contribution de chaque individu, par exemple en se basant sur des heuristiques comme par exemple celle utilisée dans les sports collectifs (ex.: le score d'un individu est déterminé par le nombre de partie que son équipe a gagné avec lui par rapport au nombre de partie perdue).
Le simulateur utilisé est codé en C++. Une partie du code pourra être faîte en Python.
[1] P. Stone, G. Kaminka, S. Kraus, J. RosenscheinAd hoc autonomous agent teams: Collaboration without pre-coordination
Proceedings of the International Conference on Artificial Intelligence (2010)