Task Allocation for Distributed Self-Interested Agents
FU Minglan1, WANG Hao1, FANG Baofu1, HUANG Xiaoling1,2
1.School of Computer Science and Information Engineering, Hefei University of Technology, Hefei 230009 2.School of Computer and Information Engineering, Chuzhou University, Chuzhou 239000
Abstract：In the task allocation with self-interested agents, the agents cannot cooperate effectively due to their selfishness and thus their individual revenues and system performance are decreased. To make a reasonable distribution of the utilities, a self-interested agent task allocation algorithm based on the task allocation model of a distributed self-interested agent coalitional skill game is proposed. The service agents and the task agents are self-interested. They are located in different geographic locations with different scopes of vision. The utility distribution strategies are designed for task agents to make them reasonably distribute their utilities to each required skill. The task allocation results guarantee a higher system revenue even if the agents are all self-interested. The final simulation results verify the effectiveness of the proposed algorithm and examine the impacts of the scope of vision of the self-interested agents on their individual revenues and system performance.
[1] EDALAT N, THAM C K, XIAO W D. An Auction-Based Strategy for Distributed Task Allocation in Wireless Sensor Networks. Computer Communications, 2012, 35(8): 916-928. [2] ANGEL E, BAMPIS E, PASCUAL F. Truthful Algorithms for Sche-duling Selfish Tasks on Parallel Machines. Theoretical Computer Science, 2006, 369(1/2/3): 157-168. [3] YUAN X Q, MIN G Y, YANG L T, et al. A Game Theory-Based Dynamic Resource Allocation Strategy in Geo-distributed Datacenter Clouds. Future Generation Computer Systems, 2017, 76: 63-72. [4] NUNES E, MANNER M, MITICHE H, et al. A Taxonomy for Task Allocation Problems with Temporal and Ordering Constraints. Robo-tics and Autonomous Systems, 2017, 90: 55-70. [5] 冯剑红,李国良,冯建华.众包技术研究综述.计算机学报, 2015, 38(9): 1713-1726. (FENG J H, LI G L, FENG J H. A Survey on Crowdsourcing. Chinese Journal of Computers, 2015, 38(9): 1713-1726.) [6] 李 洋,贾梦迪,杨文彦,等.基于树分解的空间众包最优任务分配算法.软件学报, 2018, 29(3): 824-838. (LI Y, JIA M D, YANG W Y, et al. Optimal Task Assignment Algorithm Based on Tree-Decouple in Spatial Crowdsourcing. Journal of Software, 2018, 29(3): 824-838.) [7] 宋天舒,童咏昕,王立斌,等.空间众包环境下的 3 类对象在线任务分配.软件学报, 2017, 28(3): 611-630. (SONG T S, TONG Y X, WANG L B, et al. Online Task Assignment for Three Types of Objects under Spatial Crowdsourcing Environment. Journal of Software, 2017, 28(3): 611-630.) [8] DENG D X, SHAHABI C, DEMIRYUREK U, et al. Task Selection in Spatial Crowdsourcing from Worker's Perspective. Geoinformatica, 2016, 20(3): 529-568. [9] CHENG P, LIAN X, CHEN L, et al. Task Assignment on Multi-Skill Oriented Spatial Crowdsourcing. IEEE Transactions on Know-ledge and Data Engineering, 2016, 28(8): 2201-2215. [10] HU T T, XIAO M J, HU C, et al. A QoS-Sensitive Task Assignment Algorithm for Mobile Crowdsensing. Pervasive and Mobile Computing, 2017, 41: 333-342. [11] WU P K, NGAI E W T, WU Y Y. Toward a Real-Time and Budget-Aware Task Package Allocation in Spatial Crowdsourcing. Decision Support Systems, 2018, 110: 107-117. [12] 童咏昕,袁 野,成雨蓉,等.时空众包数据管理技术研究综述.软件学报, 2017, 28(1):35-58. (TONG Y X, YUAN Y, CHENG Y R, et al. Survey on Spatiotemporal Crowdsourced Data Management Techniques. Journal of Software, 2017, 28(1): 35-58.) [13] BACHRACH Y, ROSENSCHEIN J S. Coalitional Skill Games // Proc of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems. Richland, USA: International Foundation for Autonomous Agents and Multiagent Systems, 2008: 1023-1030. [14] BACHRACH Y, PARKES D C, ROSENSCHEIN J S. Computing Cooperative Solution Concepts in Coalitional Skill Games. Artificial Intelligence, 2013, 204: 1-21. [15] BACHRACH Y, MEIR R, JUNG K, et al. Coalitional Structure Generation in Skill Games // Proc of the 24th AAAI Conference on Artificial Intelligence. Palo Alto, USA: AAAI, 2010: 703-708. [16] RAHWAN T, MICHALAK T P, WOOLDRIDGE M, et al. Coalition Structure Generation: A Survey. Artificial Intelligence, 2015, 229: 139-174. [17] VIG L, ADAMS J A. Coalition Formation: From Software Agents to Robots. Journal of Intelligent and Robotic Systems, 2007, 50(1): 85-118. [18] SERVICE T C, ADAMS J A. Coalition Formation for Task Allocation: Theory and Algorithms. Autonomous Agents and Multi-agent Systems, 2011, 22(2): 225-248. [19] KONG Y, ZHANG M J, YE D Y, et al. An Intelligent Agent-Based Method for Task Allocation in Competitive Cloud Environments. Concurrency and Computation Practice and Experience, 2017, 30(6): 1-13. [20] SWENSON B, KAR S, XAVIER J. A Computationally Efficient Implementation of Fictitious Play in a Distributed Setting // Proc of the 23rd European Signal Processing Conference. Washington, USA: IEEE, 2015: 1043-1047. [21] XIAO Z, TONG Z, LI K L, et al. Learning Non-cooperative Game for Load Balancing under Self-interested Distributed Environment. Applied Soft Computing, 2017, 52: 376-386. [22] PALMIERI F, BUONANNO L, VENTICINQUE S, et al. A Distributed Scheduling Framework Based on Selfish Autonomous Agents for Federated Cloud Environments. Future Generation Computer Systems, 2013, 29(6): 1461-1472. [23] CHEN X J, HU X D, MA W D, et al. Reducing Price of Anarchy of Selfish Task Allocation with More Selfishness. Theoretical Computer Science, 2013, 507: 17-33. [24] GERKEY B P, MATARIC' M J. A Formal Analysis and Taxonomy of Task Allocation in Multi-robot Systems. The International Journal of Robotics Research, 2004, 23(9): 939-954. [25] IIJIMA N, SUGIYAMA A, HAYANO M, et al. Adaptive Task Allocation Based on Social Utility and Individual Preference in Distributed Environments. Procedia Computer Science, 2017, 112: 91-98. [26] EPSTEIN L, KLEIMAN E. Scheduling Selfish Jobs on Multidimensional Parallel Machines. Theoretical Computer Science, 2017, 694: 42-59. [27] MORTON R D, BEKEY G A, CLARK C M. Altruistic Task Allocation Despite Unbalanced Relationships within Multi-robot Communities // Proc of the IEEE/RSJ International Conference on Intelligent Robots and Systems. Washington, USA: IEEE, 2009: 5849-5854. [28] VIG L, ADAMS J A. Market-Based Multi-robot Coalition Formation // GINI M, VOYLES R, eds. Distributed Autonomous Robo-tic Systems 7. Berlin, Germany: Springer, 2006: 227-236. [29] LIN L, ZHENG Z Q. Combinatorial Bids Based Multi-robot Task Allocation Method // Proc of the IEEE International Conference on Robotics and Automation. Washington, USA: IEEE, 2005: 1145-1150. [30] FU M L, WANG H, FANG B F. Utility Distribution Strategy of the Task Agents in Coalition Skill Games. Algorithms, 2018, 11(5). DOI: 10.3390/a11050064. [31] KOLISCH R, SPRECHER A. PSPLIB-A Project Scheduling Pro-blem Library: OR Software-ORSEP Operations Research Software Exchange Program. European Journal of Operational Research, 1997, 96(1): 205-216. [32] MYSZKOWSKI P B, SKOWRONSKI M E, SIKORA K. A New Benchmark Dataset for Multi-skill Resource-Constrained Project Scheduling Problem // Proc of the Federated Conference on Computer Science and Information System. Washington, USA: IEEE, 2015: 129-138. [33] HOOSHANGI N, ALESHEIKH A A. Agent-Based Task Allocation under Uncertainties in Disaster Environments: An Approach to Interval Uncertainty. International Journal of Disaster Risk Reduction, 2017, 24: 150-171. [34] MYSZKOWSKI P B, SKOWRON／SKI M E, OLECH L P, et al. Hybrid Ant Colony Optimization in Solving Multi-skill Resource-Constrained Project Scheduling Problem. Soft Computing, 2015, 19(12): 3599-3619. [35] HEGAZY T, SHABEEB A K, ELBELTAGI E, et al. Algorithm for Scheduling with Multiskilled Constrained Resources. Journal of Construction Engineering and Management, 2000, 126(6): 414-421. [36] SANTOS M A, TERESO A P. On the Multi-mode, Multi-skill Resource Constrained Project Scheduling Problem-A Software Application // GASPAR-CUNHA A, TAKAHASHI R, SCHAEFER G, et al., eds. Soft Computing in Industrial Applications. Berlin, Germany: Springer, 2011: 239-248. [37] 王 凌.车间调度及其遗传算法.北京:清华大学出版社, 2003. (WANG L. Shop Scheduling with Genetic Algorithms. Beijing, China: Tsinghua University Press, 2003.) [38] VIG L, ADAMS J A. Multi-Robot Coalition Formation. IEEE Transactions on Robotics, 2006, 22(4): 637-649.
2018, Vol. 31 
