Partial Robustness in Team Formation: Bridging the Gap between Robustness and Resilience.
Nicolas Schwind - AIST Tokyo7 juil. 2022 - 14:00
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… I will first recall two solution concepts that 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. Then, I will introduce a new robustness notion for team formation called partial robustness. 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 the problem of forming an optimal partially robust team, and present 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.