, Stephen Okamoto

Open Computational systems comprise physical enti-ties coordinating their activities in dynamic environments. Many exciting applications require a large number of such entities to achieve team coordination in complex missions execution. To meet the fundamental challenge of role al-location in such extreme teams, we propose an algorithm called LA-DCOP, that overcomes the limitations of previ-ous algorithms by incorporating three key ideas. First, we represent the role allocation problem as a Distributed Con-straint Optimization Problem and use tokens representing roles to minimize constraint violations. Second, we use probabilistic information about the team to guide the search quickly towards good solutions Third, we designed the al-gorithm to manage constrained roles. We show that LA-DCOP not only meets our requirements in extreme teams, but also compares favorably against previous role alloca-tion algorithms. LA-DCOP has allowed an order of mag-nitude scale-up in extreme teams, with role allocation in a fully distributed proxy-based teams with up to 200 members.