Centralized Mission Planning for Multiple Robots Minimizing Total Mission Completion Time

  1. Hwang, Nam Eung 1
  2. Kim, Hyung Jun 1
  3. Kim, Jae Gwan 1
  4. González Aguilera, Diego 2
  1. 1 Hanwha Systems Co., Seongnam-si 13524, Gyeonggi-do, Republic of Korea
  2. 2 Universidad de Salamanca
    info

    Universidad de Salamanca

    Salamanca, España

    ROR https://ror.org/02f40zc51

Revista:
Applied Sciences

ISSN: 2076-3417

Año de publicación: 2023

Volumen: 13

Número: 6

Páginas: 3737

Tipo: Artículo

DOI: 10.3390/APP13063737 GOOGLE SCHOLAR lock_openAcceso abierto editor

Otras publicaciones en: Applied Sciences

Resumen

Most mission planning algorithms solve multi-robot-multi-mission problems based on mixed integer linear programming. In these algorithms, the rewards (or costs) of missions for each robot are calculated according to the purpose of the user. Then, the (robot-mission) pair that has maximum rewards (or minimum costs) is found in the rewards (or costs) table and the mission is allocated to the robot. However, it is hard to design the reward for minimizing total mission completion time because not only a robot, but also the whole robots’ mission plans must be considered to achieve the purpose. In this paper, we propose centralized mission planning for multi-robot-multi-mission problems, minimizing total mission completion time. First, mission planning for single-robot-multi-mission problems is proposed because it is easy to solve. Then, this method is applied for multi-robot-multi-mission problems, adding a mission-plan-adjustment step. To show the excellent performance of the suggested algorithm in diverse situations, we demonstrate simulations for 3 representative cases: a simple case, which is composed of 3 robots and 8 missions, a medium case, which is composed of 4 robots and 30 missions, and a huge case, which is composed of 6 robots and 50 missions. The total mission completion time of the proposed algorithm for each case is lower than the results of the existing algorithm.

€ Ver financiación

Información de financiación

Financiadores

Referencias bibliográficas

  • Rubenstein, (2014), Science, 345, pp. 795, 10.1126/science.1254295
  • Nouryan, (2007), Swarm Intell., 2, pp. 1, 10.1007/s11721-007-0009-6
  • Penders, (2012), Adv. Robot., 25, pp. 93, 10.1163/016918610X538507
  • Chen, (2020), IEEE Netw., 34, pp. 278, 10.1109/MNET.001.1900521
  • Asaamoning, G., Mendes, P., Rosario, D., and Cerqueira, E. (2021). Drone swarms as networked control systems by integration of networking and computing. Sensors, 21.
  • Taylor, G., and Turpin, T. (2015, January 4–7). Army Aviation Manned-Unmanned Teaming (MUM-T): Past, Present, and Future. Proceedings of the 18th International Symposium on Aviation Psychology, Dayton, OH, USA.
  • Das, A.N., Doelling, K., Lundberg, C., Sevil, H.E., and Lewis, F. (2017, January 3–9). A Mixed reality based on hybrid swarm control architecture for manned-unmanned teaming (MUM-T). Proceedings of the ASME 2017 International Mechanical Engineering Congress and Exposition, Tampa, FL, USA.
  • Frey, M., and Schulte, A. (2022, January 3–7). TacARA: Tactical Analysis and Reconnaissance Assistant to Support Pilots in MUM-T Scenarios. Proceedings of the AIAA SCITECH 2022 Forum, San Diego, CA, USA.
  • Uhrmann, J., Stenzke, R., and Schulte, A. (2010, January 22). Task-based guidance of multiple detached unmanned sensor platforms in military helicopter operations. Proceedings of the Cognitive Systems with Interactive Sensors, Crawley, UK.
  • Goetz, J., Kiesler, S., and Powers, A. (2003, January 2). Matching robot appearance and behavior to tasks to improve human-robot cooperation. Proceedings of the 12th IEEE International Workshop on Robot and Human Interactive Communication, Millbrae, CA, USA.
  • Parker, L.E. (1994). Heterogeneous Multi-Robot Cooperation. [Ph.D. Thesis, Massachusetts Institute of Technology].
  • Khan, (2018), IEEE Trans. Cybern., 48, pp. 187, 10.1109/TCYB.2016.2628161
  • Xiang, C., Zhou, Y., Dai, H., Qu, Y., He, S., Chen, C., and Yang, P. (2021). Reusing Delivery Drones for Urban Crowdsensing. IEEE Trans. Mob. Comput., 1.
  • Xiang, C., Li, Y., Zhou, Y., He, S., Qu, Y., Li, Z., Gong, L., and Chen, C. (2022, January 2–5). A Comparative Approach to Resurrecting the Market of MOD Vehicular Crowdsensing. Proceedings of the IEEE INFOCOM 2022-IEEE Conference on Computer Communications, London, UK.
  • Billonnet, (1992), J. ACM, 39, pp. 502, 10.1145/146637.146646
  • Moon, (2012), J. Inst. Contr. Robot Syst., 18, pp. 218, 10.5302/J.ICROS.2012.18.3.218
  • Lim, M.C., and Choi, H.L. (2019). Improving Computational Efficiency in Crowded Task Allocation Games with Coupled Constraints. Appl. Sci., 9.
  • Oh, K.T., and Kim, W.D. (2012, January 14–16). Task Assignment Algorithm for Rendezvous of Multiple UAVs. Proceedings of the Korean Society for Aeronautical and Space Sciences Fall Conference, Jeju, Republic of Korea.
  • Marcarthur, K.S., Stranders, R., Ramchum, S.D., and Jennings, N.R. (2011, January 7–11). A Distributed Anytime Algorithm for Dynamic Task Allocation in Multi-Agent Systems. Proceedings of the AAAI Conference on Artificial Intelligence, San Francisco, CA, USA.
  • Jin, Y., Minai, A.A., and Polycarpou, M.M. (2003, January 9–12). Cooperative Real-Time Search and Task Allocation in UAV Teams. Proceedings of the 42nd IEEE International Conference on Decision and Control, Maui, HI, USA.
  • Thenepalle, (2019), Decis. Sci. Lett., 8, pp. 121, 10.5267/j.dsl.2018.8.002
  • Ahmeda, (2020), Int. J. Netw. Secur., 20, pp. 65
  • Levchuk, (2022), IEEE Trans. Syst. Man Cybern. Part A Syst. Hum., 32, pp. 346, 10.1109/TSMCA.2002.802819
  • Qin, A., Li, A., Dong, C., Dai, H., and Xu, Z. (2019). Completion time minimization for multi-UAV information collection via trajectory planning. Sensors, 19.
  • Choi, (2009), IEEE Trans. Robot., 25, pp. 912, 10.1109/TRO.2009.2022423
  • Whitten, A.K., Choi, H.L., Johnson, L.B., and How, J.P. (July, January 29). Decentralized Task Allocation with Coupled Constraints in Complex Missions. Proceedings of the 2011 American Control Conference, San Francisco, CA, USA.
  • Whitten, A.K. (2010). Decentralized Planning for Autonomous Agents Cooperating in Complex Missions. [Master’s Thesis, Massachusetts Institute of Technology].
  • Wei, H., Lv, Q., Duo, N., Wang, G.S., and Liang, B. (2019). Consensus Algorithms Based Multi-Robot Formation Control under Noise and Time Delay Conditions. Appl. Sci., 9.
  • Lagoudakis, M.G., Berhault, M., Koenig, S., Keskinocak, P., and Kleywegt, A.J. (October, January 28). Simple Auctions with Performance Guarantees for Multi-Robot Task Allocation. Proceedings of the 2004 IEEE/RSJ International Conference on Intelligent Robots and Systems, Sendai, Japan.
  • Lee, (2011), J. Korea Soc. Aeronaut. Space Sci., 40, pp. 988
  • Kim, (2019), Int. J. Aeronaut. Space Sci., 21, pp. 290, 10.1007/s42405-019-00205-1
  • Oh, G., Kim, Y., Ahn, J., and Choi, H.L. (2017, January 25–27). Task allocation of multiple UAVs for cooperative parcel delivery. Proceedings of the 4th CEAS Specialist Conference on Guidance, Navigation and Control, Warsaw, Poland.
  • Hwang, N.E., Kim, H.J., and Kim, J.G. (2022). Centralized Task Allocation and Alignment based on Constraint Table and Alignment Rules. Appl. Sci., 12.
  • Wang, (2019), IEEE Trans. Wirel. Commun., 18, pp. 3485, 10.1109/TWC.2019.2914203