Allocation distribuée de tâches et équité

Nous nous intéressons aux problèmes de l’allocation de tâches dans des groupes d’agents coopératifs (par exemple une équipe de robots mobiles devant exécuter des tâches en différents lieux d’un environnement). Afin de permettre une plus grande autonomie des agents et une meilleure robustesse du système, nous souhaitons que les agents soient capables de se répartir les tâches de manière distribuée, c’est-à-dire sans avoir recours à une entité centrale décidant de l’allocation pour tout le monde.
Afin de réaliser une allocation d’un ensemble connu de tâches entre des agents, nous proposons d’étudier l’algorithme CBBA (consensus-based bundle algorithm) basé sur des enchères. Bien que cet algorithme ne fournisse pas de garantie d’optimalité de la répartition des tâches, il fournit en moyenne des solutions de bonne qualité en terme d’utilité pour le groupe.

Lorsque l’ensemble de tâches n’est pas connu a priori et que les tâches à réaliser par les agents arrivent au fur et à mesure du temps, l’algorithme CBBA peut-être adapté afin de tenir compte de la dynamicité de l’ensemble des tâches.
On peut alors s’interroger sur la répartition des tâches au fil du temps et en particulier sur l’équité de la répartition des tâches au cours de l’exécution. En effet, il est souhaitable que la répartition de la charge de travail entre les agents soit équitable à long-terme.

Ce sujet vise à étudier l’équité à long-terme des allocations de tâches réalisées par CBBA.

Le travail consistera plus précisément à :
- implémenter CBBA,
- adapter CBBA pour le cas des ensemble de tâches dynamiques (approches décrites dans la littérature),
- étudier l’équité à long-terme des allocations,
- proposer des solutions pour améliorer l’équité si nécessaire.
-
Les développements seront réalisés en Java sur la plate-forme JADE (aussi utilisée en FoSyMa).

CBBA : http://acl.mit.edu/papers/BrunetChoiHow_GNC08.pdf