Token Approach for Role Allocation in Extreme Teams: analysis and experimental evaluation

Paul Scerri, A. Farinelli, S. Okamoto, and M. Tambe
Proceedings of 2nd IEEE International Workshop on Theory and Practice of Open Computational Systems, 2004.


Download
  • Adobe portable document format (pdf) (294KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract
Open Computational systems comprise physical entities 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 allocation in such extreme teams, we propose an algorithm called LA-DCOP, that overcomes the limitations of previous algorithms by incorporating three key ideas. First, we represent the role allocation problem as a Distributed Constraint 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 algorithm to manage constrained roles. We show that LA-DCOP not only meets our requirements in extreme teams, but also compares favorably against previous role allocation algorithms. LA-DCOP has allowed an order of magnitude scale-up in extreme teams, with role allocation in a fully distributed proxy-based teams with up to 200 members.

Notes
Associated Center(s) / Consortia: Center for Integrated Manfacturing Decision Systems
Associated Lab(s) / Group(s): Advanced Agent - Robotics Technology Lab
Associated Project(s): Cooperative Attack Munition Real Time Assessment
Number of pages: 6

Text Reference
Paul Scerri, A. Farinelli, S. Okamoto, and M. Tambe, "Token Approach for Role Allocation in Extreme Teams: analysis and experimental evaluation," Proceedings of 2nd IEEE International Workshop on Theory and Practice of Open Computational Systems, 2004.

BibTeX Reference
@inproceedings{Scerri_2004_4884,
   author = "Paul Scerri and A. Farinelli and S. Okamoto and M. Tambe",
   title = "Token Approach for Role Allocation in Extreme Teams: analysis and experimental evaluation",
   booktitle = "Proceedings of 2nd IEEE International Workshop on Theory and Practice of Open Computational Systems",
   year = "2004",
}