Resource Welfare Based Task Allocation for UAV Team with Resource Constraints

详细信息    查看全文

• 作者：Min-Hyuk Kim (1)
  Hyeoncheol Baik (2)
  Seokcheon Lee (3)
  
  1. Republic of Korea Army Headquarters ; PO Box 501-15 ; Bunam-ri ; Sindoan-myeon ; Gyeryong-si ; Chungnam-do ; South Korea
  2. GM Korea Company ; 199-1 Cheongcheon-dong ; Bupyeon-gu ; Incheon-si ; South Korea
  3. School of Industrial Engineering ; Purdue University ; 315 N. Grant Street ; 47907 ; West Lafayette ; IN ; USA
  
• 关键词：UAV team ; Task allocation ; Preparedness ; Resource welfare
• 刊名：Journal of Intelligent and Robotic Systems
• 出版年：2015
• 出版时间：March 2015
• 年：2015
• 卷：77
• 期：3-4
• 页码：611-627
• 全文大小：658 KB
• 参考文献：1. Office of Secretary of Defense: Unmanned Aircraft Systems Roadmap 2005鈥?030. (2005). https://www.fas.org/irp/program/collect/uav_roadmap2005.pdf
  2. Shumacher, C., Chandler, P., Pachter, M., Pachter, L.: UAV task assignment with timing constraints via mixed-integer linear programming. Proceedings of AIAA 3 ^rd Unmanned Unlimited Systems Technical Conference, Workshop and Exhibit, Chicago (2004)
  3. Shima, T, Rasmussen, S, Sparks, A, Passino, K (2006) Multiple task assignments for cooperating uninhabited aerial vehicles using genetic algorithms. Comput. Oper. Res. 33: pp. 3252-3269 CrossRef
  4. Shetty, V, Sudit, M, Nagi, R (2008) Priority-based assignment and routing of a fleet of unmanned combat aerial vehicles. Comput. Oper. Res. 35: pp. 1813-1828 CrossRef
  5. Lemaire, T., Alami, R., Lacroix, S.: A distributed task allocation scheme in multi-UAV context. In: Proceedings of the IEEE International Conference on Robotics, New Orleans (2004)
  6. Gurfil, P.: Evaluating UAV flock mission performance using Dudek鈥檚 taxonomy. In: Proceedings of the Amer. Contr. Conf, Portland (2005)
  7. Jin, Y, Liao, Y, Minai, A, Polycarpou, M (2006) Balancing search and target response in cooperative Unmanned Aerial Vehicle (UAV) team. IEEE T. Syst. Man. Cy. B 36: pp. 571-587 CrossRef
  8. Yang, Y., Minai, A., Polycarpou, M.: Decentralized cooperative search by networked UAVs in an uncertain environment. In: Proceedings of the Amer. Contr. Conf, Boston (2004)
  9. Sujit, P., Sinha, A., Ghose, D.: Multiple UAV task allocation using negotiation. In: Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems, Hakodate, Hokkaido (2006)
  10. Sujit, P., Beard, R.: Distributed sequential auctions for multiple UAV task allocation. In: Proceedings of the Amer. Contr. Conf, New York City (2007)
  11. Sujit, P., George, G., Beard, R.: Multiple UAV coalition formation. In: Proceedings of the Amer. Contr. Conf, Seattle (2008)
  12. Li, C., Sycara, K.: A stable and efficient scheme for task allocation via agent coalition formation. Theory and Algorithms for Cooperative Systems. World Scientific, 193鈥?12 (2004)
  13. Gerkey, B, Matari膰, M (2002) Sold! Auction methods for multi-robot coordination. IEEE T Robotic Autom. 18: pp. 758-756 CrossRef
  14. Dias, M (2004) TraderBots: A new paradigm for robust and efficient multirobot coordination in dynamic environment. Ph.D. dissertation, The Robotics Institute. Carnegie Mellon University, Pittsburg
  15. Zhang, D, Xie, G, Yu, J, Wang, L (2007) Adaptive task assignment for multiple mobile robots via swarm intelligence approach. Robot. Auton. Syst. 55: pp. 411-415 CrossRef
  16. Khare, V.R., Wang, F.Z., Wu, S., Deng, Y., Thompson, C.: Ad-hoc network of unmanned aerial vehicle swarms for search and destroy tasks. In: Proceedings of the International IEEE Conference on Intelligent Systems, Varna (2008)
  17. Arslan, G, Marden, JR, Shamma, JS (2007) Autonomous vehicle-target assignment: A game-theoretical formulation: a Game Theoretical Formulation. J. Dyn. Sys., Meas., Control 129: pp. 584-596 CrossRef
  18. Peng, H, Li, Y, Wang, L, Shen, L (2008) Hormone-inspired cooperative control for multiple UAVs wide area search. Lect. Notes Comput. Sci. 5226: pp. 808-816 CrossRef
  19. Gerkey, B, Matari膰, M (2004) A formal analysis and taxonomy of task allocation in multi-robot systems. Int. J. Robot. Res. 23: pp. 939-954 CrossRef
  20. Vig, L, Adams, J (2005) Multi-robot coalition formation. IEEE T. Robot. 22: pp. 637-649 CrossRef
  21. Vig, L, Adams, J (2007) Coalition formation: From software agents to robots. J. Intell. Robot. Syst 50: pp. 85-118 CrossRef
  22. Lin, L., Zheng, Z.: Combinatorial bids based multi-robot task allocation method. In: Proceedings of the IEEE International Conference on Intelligent Robots and Automation, Barcelona (2005)
  23. Sariel, S., Balch, T., Erdogan, N.: Robust multi-robot cooperation through dynamic task allocation and precaution routines. In: Proceedings of the International Conference on Informatics in Control, Automation and Robotics, Set煤bal (2006)
  24. Ok, C, Lee, S, Jeong, B (2007) Toward socially agreeable aggregate functions for group recommender systems. J. Korean Oper. Res. Man 32: pp. 61-75
  25. Ok, C, Lee, S, Mitra, P, Kumara, S (2010) Distributed routing in wireless sensor networks using energy welfare metric. Inform. Sci. 180: pp. 1656-1670 CrossRef
  26. Chevaleyre, Y, Endriss, U, Estivie, S, Maudet, N (2008) Multiagent resource allocation in k-additive domains: preference representation and complexity. Ann. Oper. Res. 163: pp. 49-62 CrossRef
  27. Kim, M., Lee, S.: Resource welfare based distributed task allocation scheme for multiple UAVs. In: Proceedings of the Industrial Engineering Research Conference, Cancun (2010)
  28. Lee, S (2011) The role of preparedness in ambulance dispatching. J. Oper. Res. Soc. 62: pp. 1888-1897 CrossRef
  29. Sen, K (1982) Choice, welfare, and measurement. Basil Blackwell, Oxford
  30. Dagum, C (1990) On the relationship between income inequality measures and social welfare functions. J. Econ. 43: pp. 91-102 CrossRef
  31. Atkinson, AB (1970) On the measurement of inequality. J. Econ. Theory 2: pp. 244-26 CrossRef
  32. Sen, K, Foster, J (1997) On economic inequality. Clarendon Press, Oxford
  33. Manathara, J, Sujit, P, Beard, R (2011) Multiple UAV coalition for a search and prosecute mission. J. Intell. Robot. Syst. 62: pp. 125-158 CrossRef
  34. George, J, Sujit, P, Sousa, J (2011) Search strategies for multiple UAV search and destroy missions. J. Intell. Robot. Syst. 61: pp. 355-367 CrossRef
  
• 刊物类别：Engineering
• 刊物主题：Automation and Robotics
  Electronic and Computer Engineering
  Artificial Intelligence and Robotics
  Mechanical Engineering
  
• 出版者：Springer Netherlands
• ISSN：1573-0409

文摘

This paper addresses a task allocation problem for a team of UAVs that cooperatively performs a search and attack mission in an unknown region. The UAVs are heterogeneous carrying different types and amounts of munition resources, and limited in communications and sensing capabilities. The environment is highly uncertain and dynamic where no prior information is available and dynamic events such as UAV failures unpredictably occur. The objective of the mission is to maximize total reward obtained by destroying targets within a given mission horizon. A group of UAVs may need to be formed to attack a target because individual UAVs may not have sufficient resources for the execution of attack tasks. Instantaneous task allocation approaches that seek for optimal solution for current tasks cannot effectively account for the unpredictability of future tasks in the uncertain dynamic environment. In this paper, we propose a distributed task allocation scheme based on resource welfare of which concept is adopted from economics. The approach we present enables the UAV team to effectively utilize resources by balancing resource depletions and consequently be capable of smoothly responding to dynamic events by retaining more UAVs available. Simulation experiments were conducted in various conditions to evaluate the performance of the proposed approach in comparison with the instantaneous task allocation method. The results show that our approach improves the performance by up to 29.3 % with respect to the instantaneous task allocation method.