Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-26T08:56:58.808Z Has data issue: false hasContentIssue false
  • English
  • Français

Distributed task allocation with critical tasks and limited capacity

Published online by Cambridge University Press:  08 April 2021

An Zhang ,
Mi Yang Open the ORCID record for Mi Yang [Opens in a new window] ,
Wenhao Bi  and
Fei Gao
An Zhang
Affiliation:
School of Aeronautics, Northwestern Polytechnical University, Xi’an, China Key Laboratory of Data Link Technology of 20th Research Institute of CETC, Xi’an, China
Mi Yang
Affiliation:
School of Aeronautics, Northwestern Polytechnical University, Xi’an, China
Wenhao Bi*
Affiliation:
School of Aeronautics, Northwestern Polytechnical University, Xi’an, China
Fei Gao
Affiliation:
School of Aeronautics, Northwestern Polytechnical University, Xi’an, China
*
*Corresponding author. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper considers the task allocation problem under the requirement that the assignments of some critical tasks must be maximized when the network capacity cannot accommodate all tasks due to the limited capacity for each unmanned aerial vehicle (UAV). To solve this problem, this paper proposes an extended performance impact algorithm with critical tasks (EPIAC) based on the traditional performance impact algorithm. A novel task list resizing phase is developed in EPIAC to deal with the constraint on the limited capacity of each UAV and maximize the assignments of critical tasks. Numerical simulations demonstrate the outstanding performance of EPIAC compared with other algorithms.

Keywords

Distributed task allocationExtended performance impact algorithmLimited capacityCritical tasksMulti-UAV system
Type
Article
Information
Robotica , Volume 39 , Issue 11 , November 2021 , pp. 2008 - 2032
Copyright
© The Author(s), 2021. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Khamis, A., Hussein, A. and Elmogy, A., “Multi-Robot Task Allocation: A Review of the State-of-the-Art,” In: Cooperative Robots and Sensor Networks 2015 (Springer, 2015) pp. 31–51.CrossRefGoogle Scholar
[2] Zhang, A., Zhou, D., Yang, M. and Yang, P., “Finite-time formation control for unmanned aerial vehicle swarm system with time-delay and input saturation,” IEEE Access 7, 5853–5864 (2018).CrossRefGoogle Scholar
[3] Shen, W., Wang, L. and Hao, Q., “Agent-based distributed manufacturing process planning and scheduling: a state-of-the-art survey,” IEEE Trans. Syst. Man Cybern. C (Appl. Rev.) 36(4), 563–577 (2006).CrossRefGoogle Scholar
[4] Cao, Y., Yu, W., Ren, W. and Chen, G., “An overview of recent progress in the study of distributed multi-agent coordination,” IEEE Trans. Ind. Inform. 9(1), 427–438 (2012).CrossRefGoogle Scholar
[5] Xie, S., Zhang, A., Bi, W. and Tang, Y., “Multi-UAV mission allocation under constraint,” Appl. Sci. 9(11), 2184 (2019).CrossRefGoogle Scholar
[6] Torreño, A., Onaindia, E., Komenda, A. and Štolba, M., “Cooperative multi-agent planning: A survey,” ACM Comput. Surv. (CSUR) 50(6), 84 (2018).CrossRefGoogle Scholar
[7] Khamis, A. M., Elmogy, A. M. and Karray, F. O., “Complex task allocation in mobile surveillance systems,” J. Intell. Robot. Syst. 64(1), 33–55 (2011).CrossRefGoogle Scholar
[8] Kaminka, G. A., “Autonomous Agents Research in Robotics: A Report from the Trenches,” In: 2012 AAAI Spring Symposium Series (2012).Google Scholar
[9] Chen, X., Zhang, P., Du, G. and Li, F., “A distributed method for dynamic multi-robot task allocation problems with critical time constraints,” Robot. Autonom. Syst. 118, 31–46 (2019).CrossRefGoogle Scholar
[10] Nunes, E., Manner, M., Mitiche, H. and Gini, M., “A taxonomy for task allocation problems with temporal and ordering constraints,” Robot. Autonom. Syst. 90, 55–70 (2017).CrossRefGoogle Scholar
[11] Gerkey, B. P. and Matarić, M. J., “A formal analysis and taxonomy of task allocation in multi-robot systems,” Int. J. Robot. Res. 23(9), 939–954 (2004).CrossRefGoogle Scholar
[12] Bruno, J., Coffman, E. G. Jr. and Sethi, R., “Scheduling independent tasks to reduce mean finishing time,” Commun. ACM 17(7), 382–387 (1974).CrossRefGoogle Scholar
[13] Korsah, G. A., Stentz, A. and Dias, M. B., “A comprehensive taxonomy for multi-robot task allocation,” Int. J. Robot. Res. 32(12), 1495–1512 (2013).CrossRefGoogle Scholar
[14] Huang, L., Ding, Y., Zhou, M., Jin, Y. and Hao, K., “Multiple-solution optimization strategy for multirobot task allocation,” IEEE Trans. Syst. Man Cybern. Syst. (2018).Google Scholar
[15] Pendharkar, P. C., “An ant colony optimization heuristic for constrained task allocation problem,” J. Computat. Sci. 7, 37–47 (2015).CrossRefGoogle Scholar
[16] Younas, I., Kamrani, F., Bashir, M. and Schubert, J., “Efficient genetic algorithms for optimal assignment of tasks to teams of agents,” Neurocomputing 314, 409–428 (2018).CrossRefGoogle Scholar
[17] Catoni, O., “Solving scheduling problems by simulated annealing,” SIAM J. Cont. Optim. 36(5), 1539–1575 (1998).CrossRefGoogle Scholar
[18] Yin, P.-Y., Yu, S.-S., Wang, P.-P. and Wang, Y.-T., “Task allocation for maximizing reliability of a distributed system using hybrid particle swarm optimization,” J. Syst. Softw. 80(5), 724–735 (2007).CrossRefGoogle Scholar
[19] Sabuncuoglu, I. and Gurgun, B., “ A neural network model for scheduling problems,” Eur. J. Operat. Res. 93(2), 288–299 (1996).CrossRefGoogle Scholar
[20] Bertsimas, D. and Weismantel, R., Optimization Over Integers, Volume 13 (Dynamic Ideas Belmont, 2005).Google Scholar
[21] Dias, M. B. and Stentz, A., “Opportunistic Optimization for Market-Based Multirobot Control,” In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IEEE 2002), Volume 3, pp. 2714–2720.CrossRefGoogle Scholar
[22] Oh, G., Kim, Y., Ahn, J. and Choi, H.-L., “Market-based task assignment for cooperative timing missions in dynamic environments,” J. Intell. Robot. Syst. 87(1), 97–123 (2017).CrossRefGoogle Scholar
[23] Oliver, G. and Guerrero, J., “Auction and Swarm Multi-Robot Task Allocation Algorithms in Real Time Scenarios,” In: Multi-Robot Systems, Trends and Development (IntechOpen, 2011).CrossRefGoogle Scholar
[24] Bertsekas, D. P., “The auction algorithm for assignment and other network flow problems: A tutorial,” Interfaces 20(4), 133–149 (1990).CrossRefGoogle Scholar
[25] Choi, H.-L., Brunet, L. and How, J. P., “Consensus-based decentralized auctions for robust task allocation,” IEEE Trans. Robot. 25(4), 912–926 (2009).CrossRefGoogle Scholar
[26] Choi, H.-L., Whitten, A. K. and How, J. P., “Decentralized Task Allocation for Heterogeneous Teams with Cooperation Constraints,” In: Proceedings of the 2010 American Control Conference, (IEEE 2010), pp. 3057–3062.Google Scholar
[27] Binetti, G., Naso, D. and Turchiano, B., “Decentralized Task Allocation for Surveillance Systems with Critical Tasks,” Robot. Autonom. Syst. 61(12), 1653–1664 (2013).CrossRefGoogle Scholar
[28] Ponda, S., Redding, J., Choi, H.-L., How, J. P., Vavrina, M. and Vian, J., “Decentralized Planning for Complex Missions with Dynamic Communication Constraints,” In: Proceedings of the 2010 American Control Conference (IEEE 2010), pp. 3998–4003.CrossRefGoogle Scholar
[29] Johnson, L., Ponda, S., Choi, H.-L. and How, J., “Asynchronous Decentralized Task Allocation for Dynamic Environments,” In: Infotech@ Aerospace 2011 (2011), p. 1441.Google Scholar
[30] Buckman, N., Choi, H.-L. and How, J. P., “Partial Replanning for Decentralized Dynamic Task Allocation,” In: AIAA Scitech 2019 Forum (2019), p. 0915.Google Scholar
[31] Whitten, A. K., Choi, H.-L., Johnson, L. B. and How, J. P., “Decentralized Task Allocation with Coupled Constraints in Complex Missions,” In: Proceedings of the 2011 American Control Conference, (IEEE 2011), pp. 1642–1649.CrossRefGoogle Scholar
[32] Fu, X., Feng, P. and Gao, X., “Swarm UAVs task and resource dynamic assignment algorithm based on task sequence mechanism, IEEE Access 7, 41090–41100 (2019).CrossRefGoogle Scholar
[33] Johnson, L. B., Choi, H.-L., Ponda, S. S. and How, J. P., “Decentralized task allocation using local information consistency assumptions,” J. Aerosp. Inform. Syst., 103–122 (2017).CrossRefGoogle Scholar
[34] Hunt, S., Meng, Q. and Hinde, C. J., “An Extension of the Consensus-Based Bundle Algorithm for Multi-Agent Tasks with Task Based Requirements,” In: 2012 11th International Conference on Machine Learning and Applications (IEEE 2012), Volume 2, pp. 451–456.CrossRefGoogle Scholar
[35] Kim, K.-S., Kim, H.-Y. and Choi, H.-L., “Minimizing Communications in Decentralized Greedy Task Allocation,” J. Aerosp. Inform. Syst., 1–6 (2019).Google Scholar
[36] Zhao, W., Meng, Q. and Chung, P. W., “A heuristic distributed task allocation method for multivehicle multitask problems and its application to search and rescue scenario,” IEEE Trans. Cybern. 46(4), 902–915 (2015).CrossRefGoogle ScholarPubMed
[37] Whitbrook, A., Meng, Q. and Chung, P. W., “Reliable, distributed scheduling and rescheduling for time-critical, multiagent systems,” IEEE Trans. Automat. Sci. Eng. 15(2), 732–747 (2017).CrossRefGoogle Scholar
[38] Turner, J., Meng, Q., Schaefer, G., Whitbrook, A. and Soltoggio, A., “Distributed task rescheduling with time constraints for the optimization of total task allocations in a multirobot system,” IEEE Trans. Cybern. 48(9), 2583–2597 (2017).CrossRefGoogle Scholar
[39] Whitbrook, A., Meng, Q. and Chung, P. W., “Addressing robustness in time-critical, distributed, task allocation algorithms,” Appl. Intell. 49(1), 1–15 (2019).CrossRefGoogle Scholar
[40] Dias, M. B., Zlot, R., Kalra, N. and Stentz, A., “Market-based multirobot coordination: A survey and analysis,” Proc. IEEE 94(7), 1257–1270 (2006).CrossRefGoogle Scholar
[41] Lin, S.-W. and Vincent, F. Y.. “A simulated annealing heuristic for the team orienteering problem with time windows,” Eur. J. Oper. Res. 217(1), 94–107 (2012).CrossRefGoogle Scholar
[42] Luo, Z., Qin, H. and Lim, A., “Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints,” Eur. J. Oper. Res. 234(1), 49–60 (2014).CrossRefGoogle Scholar
[43] Butt, S. E. and Cavalier, T. M., “A heuristic for the multiple tour maximum collection problem,” Comput. Oper. Res. 21(1), 101–111 (1994).CrossRefGoogle Scholar
[44] Guerrero, J. and Oliver, G., “Auction and swarm multi-robot task allocation algorithms in real time scenarios,” Multi-Robot Syst. Trends Dev. 437–456 (2011).Google Scholar
[45] Wei, C., Hindriks, K. V. and Jonker, C. M., “Dynamic task allocation for multi-robot search and retrieval tasks”. Appl. Intell. 45(2), 383–401 (2016).CrossRefGoogle Scholar
[46] Lee, D.-H., “Resource-based task allocation for multi-robot systems,” Robot. Autonom. Syst. 103, 151–161 (2018).CrossRefGoogle Scholar