A Distributed Task Scheduling Method Based on Conflict Prediction for Ad Hoc UAV Swarms

  1. Li, Jie
  2. Chen, Runfeng
  3. González Aguilera, Diego ed. lit. 1
  4. Cicirello, Vincent A. ed. lit.
  1. 1 Universidad de Salamanca
    info

    Universidad de Salamanca

    Salamanca, España

    ROR https://ror.org/02f40zc51

Revista:
Drones

ISSN: 2504-446X

Año de publicación: 2022

Volumen: 6

Número: 11

Páginas: 356

Tipo: Artículo

DOI: 10.3390/DRONES6110356 GOOGLE SCHOLAR lock_openAcceso abierto editor

Otras publicaciones en: Drones

Resumen

UAV swarms have attracted great attention, and are expected to be used in scenarios, such as search and rescue, that require many urgent jobs to be completed in a minimum time by multiple vehicles. For complex missions with tight constraints, careful assigning tasks is inseparable from the scheduling of these tasks, and multi-task distributed scheduling (MTDS) is required. The Performance Impact (PI) algorithm is an excellent solution for MTDS, but it suffers from the suboptimal solution caused by the heuristics for local task selection, and the deadlock problem that it may fall into an infinite cycle of exchanging the same task. In this paper, we improve the PI algorithm by integrating a new task-removal strategy and a conflict prediction mechanism into the task-removal phase and the task-inclusion phase, respectively. Specifically, the task-removal strategy results in better exploration of the inclusion of more tasks than the original PI by freeing up more space in the local scheduler, improving the suboptimal solution caused by the heuristics for local task selection, as done in PI. In addition, we design a conflict prediction mechanism that simulates adjacent vehicles performing inclusion operations as the criteria for local task inclusion. Therefore, it can reduce the deadlock ratio and iteration times of the MTDS algorithm. Furthermore, by combining the protocol stack with the physical transmission model, an ad-hoc network simulation platform is constructed, which is closer to the real-world network, and serves as the supporting environment for testing the MTDS algorithms. Based on the constructed ad-hoc network simulation platform, we demonstrate the advantage of the proposed algorithm over the original PI algorithm through Monte Carlo simulation of search and rescue tasks. The results show that the proposed algorithm can reduce the average time cost, increase the total allocation number under most random distributions of vehicles-tasks, and significantly reduce the deadlock ratio and the number of iteration rounds.

€ Ver financiación

Información de financiación

Financiadores

  • Science and Technology Innovation 2030-Key Project of ‘New Generation Artificial Intelligence’
    • 2020AAA0108200

Referencias bibliográficas

  • (2022), IEEE Trans. Netw. Sci. Eng., 9, pp. 2940, 10.1109/TNSE.2022.3174098
  • (2013), Int. J. Robot. Res., 32, pp. 1495, 10.1177/0278364913496484
  • (2015), IEEE Trans. Cybern., 46, pp. 902
  • (2019), IEEE Trans. Autom. Sci. Eng., 16, pp. 478, 10.1109/TASE.2018.2866395
  • (2020), Decis. Mak. Appl. Manag. Eng., 3, pp. 30
  • (2020), Oper. Res. Eng. Sci. Theory Appl., 3, pp. 13, 10.31181/oresta20303013s
  • (2012), ACM Trans. Auton. Adapt. Syst., 7, pp. 21:1
  • Whitbrook, A., Meng, Q., and Chung, P. (October, January 28). A novel distributed scheduling algorithm for time-critical multi-agent systems. Proceedings of the 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Hamburg, Germany.
  • (2017), IEEE Trans. Robot., 33, pp. 1103, 10.1109/TRO.2017.2705044
  • (2017), Int. J. Robot. Res., 36, pp. 231, 10.1177/0278364917692864
  • (2021), IEEE Trans. Syst. Man Cybern. Syst., 52, pp. 6870
  • (2018), IEEE Trans. Syst. Man Cybern. Syst., 49, pp. 42
  • (2018), IEEE Trans. Syst. Man Cybern. Syst., 49, pp. 2536
  • Chen, W., Wang, D., and Li, K (2018). Multi-user multi-task computation offloading in green mobile edge cloud computing. IEEE Trans. Serv. Comput., 12, 726–738.
  • Mnif, S., Elkosantini, S., Darmoul, S., and Said, L.B (2019). An immune network based distributed architecture to control public bus transportation systems. Swarm Evol. Comput., 50, 100478.
  • Mudrova, L., and Hawes, N. (2015, January 26–30). Task scheduling for mobile robots using interval algebra. Proceedings of the 2015 IEEE International Conference on Robotics and Automation (ICRA), Seattle, WA, USA.
  • (2019), IEEE Trans. Autom. Control., 65, pp. 1456
  • (2021), IEEE Trans. Autom. Control., 67, pp. 413
  • (2009), IEEE Trans. Robot., 25, pp. 912, 10.1109/TRO.2009.2022423
  • Buckman, N., Choi, H.-L., and How, J.P. (2019, January 7–11). Partial replanning for decentralized dynamic task allocation. Proceedings of the AIAA Scitech 2019 Forum, San Diego, CA, USA.
  • Johnson, L., Choi, H.L., Ponda, S., and How, J.P. (2012, January 10–13). Allowing non-submodular score functions in distributed task allocation. Proceedings of the 2012 IEEE 51st IEEE Conference on Decision and Control (CDC), Maui, HI, USA.
  • Johnson, L., Ponda, S., Choi, H., and How, J. (2010, January 2–5). Improving the Efficiency of a Decentralized Tasking Algorithm for UAV Teams with Asynchronous Communications. Proceedings of the AIAA Guidance, Navigation, and Control Conference, Toronto, ON, Canada.
  • Ismail, S., and Liang, S. (2017, January 13–16). Decentralized hungarian-based approach for fast and scalable task allocation. Proceedings of the 2017 International Conference on Unmanned Aircraft Systems (ICUAS), Miami, FL, USA.
  • (2020), IEEE Robot. Autom. Lett., 5, pp. 572, 10.1109/LRA.2019.2963646
  • (2021), IEEE Access, 9, pp. 98712, 10.1109/ACCESS.2021.3096229
  • Alighanbari, M., and How, J.P. (2005, January 12–15). Decentralized task assignment for unmanned aerial vehicles. Proceedings of the 44th IEEE Conference on Decision and Control, Seville, Spain.
  • Dionne, D., and Rabbath, C.A. (2007, January 9–13). Multi-UAV decentralized task allocation with intermittent communications: The DTC algorithm. Proceedings of the 2007 American Control Conference, New York, NY, USA.
  • (2022), Front. Robot. AI, 8, pp. 771520, 10.3389/frobt.2021.771520
  • Dong, Y., Dong, Y., Xiaojia, X., Jie, L., and Zhenyi, L. (2020, January 28–31). Research on Ad-hoc Network for UAV Swarm Based on OPNET Simulation. Proceedings of the 2020 IEEE 20th International Conference on Communication Technology (ICCT), Nanning, China.
  • Rantanen, M., Mastronarde, N., Hudack, J., and Dantu, K. (2019, January 10–13). Decentralized task allocation in lossy networks: A simulation study. Proceedings of the 2019 16th Annual IEEE International Conference on Sensing, Communication, and Networking (SECON), Boston, MA, USA.
  • Otte, M., Kuhlman, M.J., and Sofge, D (2020). Auctions for multi-robot task allocation in communication limited environments. Auton. Robots, 44, 547–584.
  • (1960), Bell Syst. Tech. J., 39, pp. 1253, 10.1002/j.1538-7305.1960.tb03959.x
  • (1963), Bell Syst. Tech. J., 42, pp. 1977, 10.1002/j.1538-7305.1963.tb00955.x
  • (2003), IEEE Trans. Commun., 51, pp. 920, 10.1109/TCOMM.2003.813259
  • Khattak, R., Chaltseva, A., Riliskis, L., Bodin, U., and Osipov, E. (2011). International Conference on Wired/Wireless Internet Communications, Springer.
  • Rappaport, T.S. (1996). Wireless Communications: Principles and Practice, Prentice Hall PTR.
  • (2018), Nonlinear Dyn., 93, pp. 1287, 10.1007/s11071-018-4259-1