nach oben

Autonomous Agents and Multi-Agent Systems

Erschienen in:

01.10.2023

Algorithms for partially robust team formation

verfasst von: Nicolas Schwind, Emir Demirović, Katsumi Inoue, Jean-Marie Lagniez

Erschienen in: Autonomous Agents and Multi-Agent Systems | Ausgabe 2/2023

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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 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 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).

Nächster Artikel Actor-critic multi-objective reinforcement learning for non-linear utility functions

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

One does not need to make any assumption about the way f, w, and \(\alpha\) are represented for our result to hold. However, one must assume that the corresponding mappings are computed in polynomial time.

The precise formalization in terms of weighted TF problem description is rather straightforward, it is not provided here to avoid the introduction of heavy notations.

Publicly available benchmark generation protocols related to facility deployment can be found at http://old.math.nsc.ru/AP/benchmarks/english.html. However, to the best of our knowledge, none of these protocols includes the generation of skill weights. Adapting any of these protocols to fit our setting would be necessary, but this falls outside the scope of this paper.

Note that all pairs of sets \(\{z^r_1, z^r_2\}\) and \(\{z^{r'}_1, z^{r'}_2\}\) are pairwise disjoint when \(r \ne r'\), so that all assignments \(\{\omega ^r_Z \mid c_r \in \varphi \}\) can be defined independently of each other.

Garey, M. R., & Johnson, D. S., Freeman W. H (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness.

Okimoto, T., Schwind, N., Clement, M., Ribeiro, T., Inoue, K., & Marquis, P. (2015). How to form a task-oriented robust team. In: Proceedings of the 14th international conference on autonomous agents and multiagent systems (AAMAS’15), pp. 395–403.

Demirović, E., Schwind, N., Okimoto, T., & Inoue, K. (2018). Recoverable team formation: Building teams resilient to change. In: Proceedings of the 17th international conference on autonomous agents and multi-agent systems (AAMAS’18), pp. 1362–1370.

Ahmadi-Javid, A., Seyedi, P., & Syam, S. S. (2017). A survey of healthcare facility location. Computers & Operations Research, 79, 223–263.MathSciNet

Schwind, N., Demirović, E., Inoue, K., Lagniez, J. (2021). Partial robustness in team formation: Bridging the gap between robustness and resilience. In: Proceedings of the 20th international conference on autonomous agents and multiagent systems (AAMAS’21), pp. 1154–1162.

Schwind, N., Demirović, E., Inoue, K., & Lagniez, J. (2022) TF-map-solver. https://github.com/nicolas-schwind/TF-map-solver

Juárez, J., Santos, C. P., & Brizuela, C. A. (2021). A comprehensive review and a taxonomy proposal of team formation problems. ACM Computing Surveys, 54(7), 1–33.

Bruneau, M., Chang, S. E., Eguchi, R. T., Lee, G. C., O’Rourke, T. D., Reinhorn, A. M., Shinozuka, M., Tierney, K., Wallace, W. A., & von Winterfeldt, D. (2003). A framework to quantitatively assess and enhance the seismic resilience of communities. Earthquake Spectra, 19, 733–752.

Schwind, N., Magnin, M., Inoue, K., Okimoto, T., Sato, T., Minami, K., & Maruyama, H. (2016). Formalization of resilience for constraint-based dynamic systems. Journal of Reliable Intelligent Environments, 2(1), 17–35.

10.

Andrejczuk, E., Bistaffa, F., Blum, C., Rodríguez-Aguilar, J. A., & Sierra, C. (2019). Synergistic team composition: A computational approach to foster diversity in teams. Knowledge-Based Systems, 182(104), 799.

11.

Kurtan, C., Yolum, P., & Dastani, M. (2020). An ideal team is more than a team of ideal agents. In: Proceedings of the 24th European conference on artificial intelligence (ECAI’20), vol. 325, pp. 43–50.

12.

Barambones, J., Richoux, F., Imbert, R., & Inoue, K. (2020). Resilient team formation with stabilisability of agent networks for task allocation. ACM Transactions on Autonomous and Adaptive Systems, 15(3), 1–24.

13.

Igarashi, A., Ota, K., Sakurai, Y., & Yokoo, M. (2019). Robustness against agent failure in hedonic games. In: Proceedings of the 28th international joint conference on artificial intelligence (IJCAI’19), pp. 364–370.

14.

Okimoto, T., Ribeiro, T., Bouchabou, D., & Inoue, K. (2016). Mission oriented robust multi-team formation and its application to robot rescue simulation. In: Proceedings of the 25th international joint conference on artificial intelligence (IJCAI’16), pp. 454–460.

15.

Terazawa, R., & Fujita, K. (2022) Allocation considering agent importance in constrained robust multi-team formation. In: Proceedings of the 14th international conference on agents and artificial intelligence (ICAART’22), pp. 131–138.

16.

Malencia, M., Kumar, V., Pappas, G. J., & Prorok, A. (2021). Fair robust assignment using redundancy. IEEE Robotics and Automation Letters, 6(2), 4217–4224.

17.

Bachrach, Y., & Shah, N. (2013). Reliability weighted voting games. In B. Vöcking (Ed.), Algorithmic Game Theory (pp. 38–49). Springer.

18.

Bachrach, Y., Meir, R., Feldman, M., & Tennenholtz, M. (2011). Solving cooperative reliability games. In: Proceedings of the 27th conference on uncertainty in artificial intelligence (UAI’11), p. 27-34.

19.

Bachrach, Y., Kash, I., & Shah, N. (2012). Agent failures in totally balanced games and convex games. In P. W. Goldberg (Ed.), Internet and Network Economics (pp. 15–29). Springer.

20.

Kaminka, G. A., & Tambe, M. (2000). Robust agent teams via socially-attentive monitoring. Journal of Artificial Intelligence Research, 12, 105–147.

21.

Kwak, J.y., Yang, R., Yin, Z., Taylor, M.E., & Tambe, M. (2011). Towards addressing model uncertainty: Robust execution-time coordination for teamwork. In: 2011 IEEE/WIC/ACM international conferences on web intelligence and intelligent agent technology, vol. 2, pp. 204–207

22.

Rahwan, T., Michalak, T. P., Wooldridge, M., & Jennings, N. R. (2015). Coalition structure generation: A survey. Artificial Intelligence, 229, 139–174.MathSciNet

23.

Sandholm, T., Larson, K., Andersson, M., Shehory, O., & Tohmé, F. (1999). Coalition structure generation with worst case guarantees. Artificial Intelligence, 111(1–2), 209–238.MathSciNet

24.

Michalak, T. P., Rahwan, T., Elkind, E., Wooldridge, M., & Jennings, N. R. (2016). A hybrid exact algorithm for complete set partitioning. Artificial Intelligence, 230, 14–50.MathSciNet

25.

Rahwan, T., Ramchurn, S. D., Jennings, N. R., & Giovannucci, A. (2009). An anytime algorithm for optimal coalition structure generation. Journal of Artificial Intelligence Research, 34, 521–567.MathSciNet

26.

Rothkopf, M. H., Pekeč, A., & Harstad, R. M. (1998). Computationally manageable combinatorial auctions. Management Science, 44(7), 1131–1147.

27.

Yeh, D. (1986). A dynamic programming approach to the complete set partitioning problem. BIT Computer Science and Numerical Mathematics, 26(4), 467–474.MathSciNet

28.

Ieong, S., & Shoham, Y. (2005). Marginal contribution nets: a compact representation scheme for coalitional games. In: Proceedings of the 6th ACM conference on electronic commerce (EC’05), pp. 193–202.

29.

Conitzer, V., & Sandholm, T. (2006). Complexity of constructing solutions in the core based on synergies among coalitions. Artificial Intelligence, 170(6–7), 607–619.MathSciNet

30.

Ohta, N., Iwasaki, A., Yokoo, M., Maruono, K., Conitzer, V., & Sandholm, T. (2006). A compact representation scheme for coalitional games in open anonymous environments. In: Proceedings of the 21st national conference on artificial intelligence (AAAI’06), pp. 697–702.

31.

Shrot, T., Aumann, Y., & Kraus, S. (2010). On agent types in coalition formation problems. In: Proceedings of the 9th international conference on autonomous agents and multiagent systems (AAMAS’10), pp. 757–764.

32.

Bachrach, Y., Kohli, P., Kolmogorov, V., & Zadimoghaddam, M. (2013). Optimal coalition structure generation in cooperative graph games. In: Proceedings of the 27th AAAI conference on artificial intelligence (AAAI’13), pp. 81–87.

33.

Okimoto, T., Schwind, N., Demirović, E., Inoue, K., & Marquis, P. (2018). Robust coalition structure generation. In: Proceedings of the 21st international conference on principles and practice of multi-agent systems (PRIMA’18), pp. 140–157.

34.

Ismaili, A., Hazon, N., Watanabe, E., Yokoo, M., & Kraus, S. (2019). Complexity and approximations in robust coalition formation via max-min k-partitioning. In: Proceedings of the 18th international conference on autonomous agents and multiagent systems (AAMAS’19), p. 2036-2038

35.

Schwind, N., Okimoto, T., Inoue, K., Hirayama, K., Lagniez, J., & Marquis, P. (2018). Probabilistic coalition structure generation. In: Proceedings of the 16th international conference on principles of knowledge representation and reasoning (KR’18), pp. 663–664.

36.

Schwind, N., Okimoto, T., Inoue, K., Hirayama, K., Lagniez, J., & Marquis, P. (2021). On the computation of probabilistic coalition structures. Autonomous Agents and Multi Agent Systems, 35(1), 14.

37.

Karp, R. M. (1972). Reducibility among combinatorial problems (pp. 85–103). Springer.

38.

Basu, S., Sharma, M., & Ghosh, P. S. (2015). Metaheuristic applications on discrete facility location problems: A survey. OPSEARCH, 52, 530–561.MathSciNet

39.

Farahani, R. Z., Asgari, N., Heidari, N., Hosseininia, M., & Goh, M. (2012). Covering problems in facility location: A review. Computers & Industrial Engineering, 62(1), 368–407.

40.

Beraldi, P., & Ruszczynski, A. (2002). The probabilistic set-covering problem. Operations Research, 50(6), 956–967.MathSciNet

41.

Chiang, C., Hwang, M., & Liu, Y. (2005). An alternative formulation for certain fuzzy set-covering problems. Mathematical and Computer Modelling, 42(3), 363–365.MathSciNet

42.

Daskin, M. S. (1995). Network and Discrete Location: Models, Algorithms, and Applications. John Wiley and Sons.

43.

Fischetti, M., & Monaci, M. (2012). Cutting plane versus compact formulations for uncertain (integer) linear programs. Mathematical Programming Computation, 4(3), 239–273.MathSciNet

44.

Hwang, M., Chiang, C., & Liu, Y. (2004). Solving a fuzzy set-covering problem. Mathematical and Computer Modelling, 40(7), 861–865.MathSciNet

45.

Lutter, P., Degel, D., Büsing, C., Koster, A. M., & Werners, B. (2017). Improved handling of uncertainty and robustness in set covering problems. European Journal of Operational Research, 263(1), 35–49.MathSciNet

46.

Pereira, J., & Averbakh, I. (2013). The robust set covering problem with interval data. Annals of Operations Research, 207(1), 217–235.MathSciNet

47.

Snyder, L. V., & Daskin, M. S. (2005). Reliability models for facility location: The expected failure cost case. Transportation Science, 39(3), 400–416.

48.

Church, R. L., & Revelle, C. S. (1974). The maximal covering location problem. Papers of the Regional Science Association, 32, 101–118.

49.

Berman, O. (1994). The p maximal cover - p partial center problem on networks. European Journal of Operational Research, 72(2), 432–442.MathSciNet

50.

Berman, O., & Krass, D. (2002). The generalized maximal covering location problem. Computers & Operations Research, 29(6), 563–581.MathSciNet

51.

Bläser, M. (2003). Computing small partial coverings. Information Processing Letters, 85(6), 327–331.MathSciNet

52.

Nozick, L. (2001). The fixed charge facility location problem with coverage restrictions. Transportation Research Part E: Logistics and Transportation Review, 37(4), 281–296.

53.

Berman, O., Drezner, T., Drezner, Z., & Wesolowsky, G. O. (2009). A defensive maximal covering problem on a network. International Transactions in Operational Reseach, 16(1), 69–86.MathSciNet

54.

Church, R. L., & Scaparra, M. P. (2004). Identifying critical infrastructure: The median and covering facility interdiction problems. Annals of the Association of American Geographers, 94(3), 491–502.

55.

Clarke, E.M., Grumberg, O., Jha, S., Lu, Y., & Veith, H. (2000). Counterexample-guided abstraction refinement. In: Proceedings of the 12th international conference on computer aided verification (CAV’00), pp. 154–169.

56.

Janota, M., & Silva, J.P.M. (2011). Abstraction-based algorithm for 2QBF. In: Proceedings of the 14th International conference on theory and applications of satisfiability testing (SAT’11), pp. 230–244.

57.

Janota, M., Klieber, W., Marques-Silva, J., & Clarke, E. M. (2016). Solving QBF with counterexample guided refinement. Artificial Intelligence, 234, 1–25.MathSciNet

58.

Kleine Büning, H., & Bubeck, U. (2009). Theory of quantified boolean formulas. In A. Biere, M. Heule, H. van Maaren, & T. Walsh (Eds.), Handbook of satisfiability, frontiers in artificial intelligence and applications (Vol. 185, pp. 735–760). IOS Press.

59.

Goultiaeva, A., Gelder, A.V., & Bacchus, F. (2011). A uniform approach for generating proofs and strategies for both true and false QBF formulas. In: Proceedings of the 22nd international joint conference on artificial intelligence (IJCAI’11), pp. 546–553.

60.

Papadimitriou, C. H. (1994). Computational complexity. Addison-Wesley.

61.

Beasley, J. E. (1990). OR-library: Distributing test problems by electronic mail. Journal of the Operational Research Society, 41(11), 1069–1072.

62.

Bergman, D., & Ciré, A.A. (2016). Multiobjective optimization by decision diagrams. In: Proceedings of the 22nd international conference on principles and practice of constraint programming (CP’16), pp. 86–95.

63.

Stidsen, T. R., Andersen, K. A., & Dammann, B. (2014). A branch and bound algorithm for a class of biobjective mixed integer programs. Management Science, 60(4), 1009–1032.

64.

Gao, C., Yao, X., Weise, T., & Li, J. (2015). An efficient local search heuristic with row weighting for the unicost set covering problem. European Journal of Operational Research, 246(3), 750–761.MathSciNet

65.

Kadioglu, S., & Sellmann, M. (2009). Dialectic search. In: Proceedings of the 15th International conference on principles and practice of constraint programming (CP’09), pp. 486–500.

66.

Musliu, N. (2006). Local search algorithm for unicost set covering problem. In: Proceedings of the 19th international conference on industrial, engineering and other applications of applied intelligent systems, Advances in Applied Artificial Intelligence (IEA/AIE’06), pp. 302–311.

67.

Perlin, K. (1985). An image synthesizer. In: Proceedings of the 12th annual conference on computer graphics and interactive techniques (SIGGRAPH’85), pp. 287–296.

68.

Downey, R.G., & Fellows, M.R. (2013) Fundamentals of parameterized complexity. Texts in Computer Science, Springer.

69.

Jansen, B. M. P. (2017). On structural parameterizations of hitting set: Hitting paths in graphs using 2-SAT. Journal of Graph Algorithms and Applications, 21(2), 219–243.MathSciNet

70.

Rossi, F., van Beek, P., Walsh, T. (eds) (2006). Handbook of constraint programming, foundations of artificial intelligence, vol. 2. Elsevier.

71.

Balyo, T., Heule, M. J., Iser, M., Järvisalo, M., & Suda, M. (Eds.). (2022). SAT Competition 2022: Solver and Benchmark Descriptions. Department of Computer Science: University of Helsinki.

72.

Karnouskos, S., & de Holanda, T.N. (2009). Simulation of a smart grid city with software agents. In: Al-Dabass D, Katsikas SK, Koukos I, Zobel RN (eds) Proceedings of the 3rd UKSim european symposium on computer modeling and simulation (EMS’09), pp. 424–429.

73.

Meyer, A.R., & Stockmeyer, L.J. (1972). The equivalence problem for regular expressions with squaring requires exponential space. In: Proceedings of the 13th annual symposium on switching and automata theory (SWAT’72), pp. 125–129.

Titel: Algorithms for partially robust team formation
verfasst von: Nicolas Schwind
Emir Demirović
Katsumi Inoue
Jean-Marie Lagniez
Publikationsdatum: 01.10.2023
Verlag: Springer US
Erschienen in: Autonomous Agents and Multi-Agent Systems / Ausgabe 2/2023
Print ISSN: 1387-2532
Elektronische ISSN: 1573-7454
DOI: https://doi.org/10.1007/s10458-023-09608-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 2/2023

Classifying ambiguous identities in hidden-role Stochastic games with multi-agent reinforcement learning

ASN: action semantics network for multiagent reinforcement learning

Non-chaotic limit sets in multi-agent learning

Generating and choosing organisations for multi-agent systems

Balancing fairness and efficiency in traffic routing via interpolated traffic assignment

Hardness of candidate nomination

Premium Partner