{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T20:35:12Z","timestamp":1648758912208},"reference-count":22,"publisher":"Frontiers Media SA","license":[{"start":{"date-parts":[[2021,5,20]],"date-time":"2021-05-20T00:00:00Z","timestamp":1621468800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["frontiersin.org"],"crossmark-restriction":true},"short-container-title":["Front. Neurorobot."],"abstract":"In recent years, it is a trend to integrate the ideas in game theory into the research of multi-robot system. In this paper, a team-competition model is proposed to solve a dynamic multi-robot task allocation problem. The allocation problem asks how to assign tasks to robots such that the most suitable robot is selected to execute the most appropriate task, which arises in many real-life applications. To be specific, we study multi-round team competitions between two teams, where each team selects one of its players simultaneously in each round and each player can play at most once, which defines an extensive-form game with perfect recall. We also study a common variant where one team always selects its player before the other team in each round. Regarding the robots as the players in the first team and the tasks as the players in the second team, the sub-game perfect strategy of the first team computed via solving the team competition gives us a solution for allocating the tasks to the robots\u2014it specifies how to select the robot (according to some probability distribution if the two teams move simultaneously) to execute the upcoming task in each round, based on the results of the matches in the previous rounds. Throughout this paper, many properties of the sub-game perfect equilibria of the team competition game are proved. We first show that uniformly random strategy is a sub-game perfect equilibrium strategy for both teams when there are no redundant players. Secondly, a team can safely abandon its weak players if it has redundant players and the strength of players is transitive. We then focus on the more interesting case where there are redundant players and the strength of players is not transitive. In this case, we obtain several counterintuitive results. For example, a player might help improve the payoff of its team, even if it is dominated by the entire other team. We also study the extent to which the dominated players can increase the payoff. Very similar results hold for the aforementioned variant where the two teams take actions in turn.<\/jats:p>","DOI":"10.3389\/fnbot.2021.674949","type":"journal-article","created":{"date-parts":[[2021,5,20]],"date-time":"2021-05-20T06:28:26Z","timestamp":1621492106000},"update-policy":"http:\/\/dx.doi.org\/10.3389\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Dynamic Task Allocation in Multi-Robot System Based on a Team Competition Model"],"prefix":"10.3389","volume":"15","author":[{"given":"Kai","family":"Jin","sequence":"first","affiliation":[]},{"given":"Pingzhong","family":"Tang","sequence":"additional","affiliation":[]},{"given":"Shiteng","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Jianqing","family":"Peng","sequence":"additional","affiliation":[]}],"member":"1965","published-online":{"date-parts":[[2021,5,20]]},"reference":[{"key":"B1","first-page":"27","article-title":"Nonmanipulable selections from a tournament","volume-title":"IJCAI","author":"Altman","year":"2009"},{"key":"B2","first-page":"1234","article-title":"M+: a scheme for multi-robot cooperation through negotiated task allocation and achievement","volume-title":"Proceedings 1999 IEEE International Conference on Robotics and Automation","author":"Botelho","year":"1999"},{"key":"B3","doi-asserted-by":"publisher","first-page":"1257","DOI":"10.1109\/JPROC.2006.876939","article-title":"Market-based multirobot coordination: a survey and analysis","volume":"94","author":"Dias","year":"2006","journal-title":"Proc. IEEE"},{"key":"B4","doi-asserted-by":"publisher","first-page":"758","DOI":"10.1109\/TRA.2002.803462","article-title":"Sold! Auction methods for multirobot coordination","volume":"18","author":"Gerkey","year":"2002","journal-title":"IEEE Trans. Robot. Autom"},{"key":"B5","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1080\/00029890.1982.11995420","article-title":"New concepts in seeding knockout tournaments","volume":"89","author":"Hwang","year":"1982","journal-title":"Am. Math. Monthly"},{"key":"B6","first-page":"14","article-title":"On the power of dominated players in team competitions","volume-title":"Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, AAMAS 2016","author":"Jin","year":"2016"},{"key":"B7","volume-title":"Olympic Badminton Is Not Incentive Compatible, Turing's Invisible Hand","author":"Kleinberg","year":"2012"},{"key":"B8","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1137\/1029011","article-title":"A random knockout tournament","volume":"93","author":"Knuth","year":"1987","journal-title":"Am. Math. Monthly"},{"key":"B9","doi-asserted-by":"crossref","DOI":"10.1515\/9781400881970-012","volume-title":"Extensive Games and the Problem of Information","author":"Kuhn","year":"1953"},{"key":"B10","first-page":"28","article-title":"Monte Carlo tree search in simultaneous move games with applications to goofspiel","volume-title":"Computer Games, Volume 408 of Communications in Computer and Information Science","author":"Lanctot","year":"2014"},{"key":"B11","volume-title":"A Course in Game Theory","author":"Osborne","year":"1994"},{"key":"B12","volume-title":"Olympic Badminton Is Not Incentive Compatible-Revisited, Turing's Invisible Hand","author":"Procaccia","year":"2013"},{"key":"B13","doi-asserted-by":"publisher","first-page":"701","DOI":"10.3386\/w1668","article-title":"Prizes and incentives in elimination tournaments","volume":"76","author":"Rosen","year":"1986","journal-title":"Am. Econ. Rev"},{"key":"B14","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1080\/00029890.2000.12005171","article-title":"What is the correct way to seed a knockout tournament?","volume":"107","author":"Schwenk","year":"2000","journal-title":"Am. Math. Monthly"},{"key":"B15","article-title":"Team competition","volume-title":"Proceedings of AAMAS","author":"Tang","year":"2009"},{"key":"B16","doi-asserted-by":"publisher","first-page":"749","DOI":"10.1016\/j.artint.2010.04.025","article-title":"Designing competitions between teams of individuals","volume":"174","author":"Tang","year":"2010","journal-title":"Artif. Intell"},{"key":"B17","first-page":"225","article-title":"On the complexity of schedule control problems for knockout tournaments","volume-title":"AAMAS '09","author":"Vu","year":"2009"},{"key":"B18","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1109\/ICNSC.2004.1297449","article-title":"A multi-agent model based on market competition for task allocation: a game theory approach","volume-title":"IEEE International Conference on Networking, Sensing and Control, 2004","author":"Wang","year":"2004"},{"key":"B19","volume-title":"Goofspiel","year":""},{"key":"B20","volume-title":"Sun bin","year":""},{"key":"B21","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/j.isatra.2020.03.004","article-title":"Potential game for dynamic task allocation in multi-agent system","volume":"102","author":"Wu","year":"2020","journal-title":"ISA Trans"},{"key":"B22","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1177\/0278364906061160","article-title":"Market-based multirobot coordination for complex tasks","volume":"25","author":"Zlot","year":"2006","journal-title":"Int. J. Robot. Res"}],"container-title":["Frontiers in Neurorobotics"],"original-title":[],"link":[{"URL":"https:\/\/www.frontiersin.org\/articles\/10.3389\/fnbot.2021.674949\/full","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,20]],"date-time":"2021-05-20T06:28:32Z","timestamp":1621492112000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.frontiersin.org\/articles\/10.3389\/fnbot.2021.674949\/full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,20]]},"references-count":22,"alternative-id":["10.3389\/fnbot.2021.674949"],"URL":"https:\/\/doi.org\/10.3389\/fnbot.2021.674949","relation":{},"ISSN":["1662-5218"],"issn-type":[{"value":"1662-5218","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,20]]}}}