Algorithms for partially robust team formation
Algorithms for partially robust team formation
复制标题
DOI：
10.1007/s10458-023-09608-7
复制
发表时间：
2023-04
影响因子：
1.9
通讯作者：
Nicolas Schwind;Emir Demirovic;Katsumi Inoue;Jean-Marie Lagniez
中科院分区：
文献类型：
--
作者：
Nicolas Schwind;Emir Demirovic;Katsumi Inoue;Jean-Marie Lagniez
在其最简单的形式之一中，团队形成涉及部署成本最低的代理团队，同时涵盖一组技能。虽然目前的算法在计算最佳团队方面相当成功，但这种解决方案对变化的适应能力仍然是一个重要的问题：一旦组成了一个团队，开始时考虑的一些代理可能最终会有缺陷，一些技能可能会被发现。最近引入的两个解决方案概念积极地处理了这个问题：1)组建一个对更改健壮的团队，以便在一些代理丢失后，所有技能都得到覆盖；2)选择一个可恢复的团队，也就是说，在最坏的情况下，可以通过雇用新代理来“修复”，同时保持最小的总体部署成本。本文引入了部分鲁棒团队形成问题。部分鲁棒性是鲁棒性的一种较弱形式，它保证在一些智能体丢失后仍有一定程度的技能覆盖。我们分析了PR-TF的计算复杂度，并给出了两种完整的算法。在几个现有的和新引入的基准测试中，我们将算法的性能与现有的鲁棒性和可恢复性团队形成方法进行了比较。我们的实证研究表明，部分鲁棒性在计算效率、代理损失后保证的技能覆盖和可修复性方面提供了（完全）鲁棒性和可恢复性之间的有趣权衡。本文是（Schwind et al.，第二十届自主代理和多代理系统国际会议论文集（AAMAS ' 21）， pp. 1154-1162, 2021）报道的扩展和修订版本。
In one of its simplest forms, Team Formation involves deploying the least expensive team of agents while covering a set of skills. While current algorithms are reasonably successful in computing the best teams, the resilience to change of such solutions remains an important concern: Once a team has been formed, some of the agents considered at start may be finally defective and some skills may become uncovered. Two recently introduced solution concepts deal with this issue proactively: 1) form a team which is robust to changes so that after some agent losses, all skills remain covered, and 2) 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 ofpartially 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 two complete algorithms for it. We compare the performance of our algorithms with the existing methods for robust and recoverable team formation on several existing and newly introduced benchmarks. Our empirical study demonstrates that partial robustness offers an interesting trade-off between (full) robustness and recoverability in terms of computational efficiency, skill coverage guaranteed after agent losses and repairability. This paper is an extended and revised version of as reported by (Schwind et al., Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’21), pp. 1154–1162, 2021).