Partial Robustness in Team Formation

Partial Robustness in Team Formation: Bridging the Gap between Robustness and Resilience

Schwind, Nicolas (National Institute of Advanced Industrial Science and Technology (AIST))
Inoue, Katsumi (National Institute of Advanced Industrial Science and Technology (AIST))
Demirović, E. (TU Delft Algorithmics)

2021

Team formation is the problem of deploying the least expensive team of agents while covering a set of skills. Once a team has been formed, some of the agents considered at start may be finally defective and some skills may become uncovered. Two solution concepts have been recently introduced to deal with this issue in a proactive manner: one may form a team which is robust to changes so that after some agent losses, all skills remain covered; or one may opt for a recoverable team, i.e., it can be “repaired” in the worst case by hiring new agents while keeping the overall deployment cost minimal. In this paper, we introduce the problem of partially robust team formation (PR-TF). Partial robustness is a weaker form of robustness which guarantees a certain degree of skill coverage after some agents are lost. We analyze the computational complexity of PR-TF, and provide a complete algorithm for it. The performance of our algorithm is empirically compared with the existing methods for robust and recoverable team formation, on a number of existing benchmarks and some newly introduced ones. Partial robustness is shown to be an interesting trade-off notion between (full) robustness and recoverability in terms of computational efficiency, skill coverage guarantees after agent losses, and repairability.

http://resolver.tudelft.nl/uuid:d60730cd-3882-4ca0-b475-5613c57968c4

International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC

9781450383073

Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems

20th International Conference on Autonomous Agentsand Multiagent Systems, 2021-05-03 → 2021-05-07, Virtual/online event due to COVID-19

AAMAS '21, 2523-5699

Institutional Repository

conference paper

© 2021 Nicolas Schwind, Katsumi Inoue, E. Demirović