Top

Published in:

2021 | OriginalPaper | Chapter

5. Mission Planning for Shepherding a Swarm of Uninhabited Aerial Vehicles

Authors : Jing Liu, Sreenatha Anavatti, Matthew Garratt, Hussein A. Abbass

Published in: Shepherding UxVs for Human-Swarm Teaming

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Uninhabited aerial vehicles (UAVs) are widely used in many areas for completing complex missions such as tracking targets, search and rescue, farming (shepherding in the traditional sense) and mapping. Mission planning for shepherding a UAV swarm is advantageous for Human-Swarm Teaming. While most research on shepherding see the shepherd as a simple reactive agent, a smart shepherd in a complex environment will need to consider many dimensions and sub-decisions to successfully guide a swarm through complex environment and towards a goal.

In this chapter, we review and offer formal definitions for the sub-problems required for a shepherd to complete a mission successfully. The swarm mission planning system needs to have decision modules capable of solving four main problems: task decomposition, task assignment, path planning and trajectory generation. These sub-problems are coupled differently depending on the scenario. This chapter defines these sub-problems in their general form and gives UAV swarm shepherding problem as a specific application. A brief review of the widely used algorithms for tackling these problems and the state of art of mission planning are also given in this chapter.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter The Influence of Stall Distance on Effective Shepherding of a Swarm

next chapter Towards Ontology-Guided Learning for Shepherding

Adamey, E., Oğuz, A.E., Özgüner, Ü.: Collaborative multi-MSA multi-target tracking and surveillance: a divide & conquer method using region allocation trees. J. Intell. Rob. Syst. 87(3–4), 471–485 (2017)CrossRef

Agassounon, W., Martinoli, A.: Efficiency and robustness of threshold-based distributed allocation algorithms in multi-agent systems. In: Proceedings of the First International Joint Conference on Autonomous Agents and Multiagent Systems: Part 3, pp. 1090–1097. ACM, New York (2002)

Alejo, D., Cobano, J.A., Heredia, G., Ollero, A.: Collision-free 4d trajectory planning in unmanned aerial vehicles for assembly and structure construction. J. Intell. Rob. Syst. 73(1–4), 783–795 (2014)CrossRef

Allaire, F.C., Tarbouchi, M., Labonté, G., Fusina, G.: FPGA implementation of genetic algorithm for UAV real-time path planning. In: Unmanned Aircraft Systems, pp. 495–510. Springer, Berlin (2008)

Anand, R., Mehrotra, K., Mohan, C.K., Ranka, S.: Efficient classification for multiclass problems using modular neural networks. IEEE Trans. Neural Netw. 6(1), 117–124 (1995)CrossRef

Auda, G., Kamel, M.: Modular neural networks: a survey. Int. J. Neur. Syst. 9(02), 129–151 (1999)CrossRef

Bertuccelli, L., Alighanbari, M., How, J.: Robust planning for coupled cooperative UAV missions. In: 2004 43rd IEEE Conference on Decision and Control (CDC)(IEEE Cat. No. 04CH37601), vol. 3, pp. 2917–2922. IEEE, Piscataway (2004)

Bertuccelli, L., Choi, H.L., Cho, P., How, J.: Real-time multi-UAV task assignment in dynamic and uncertain environments. In: AIAA Guidance, Navigation, and Control Conference, p. 5776 (2009)

Botelho, S.C., Alami, R.: M+: A scheme for multi-robot cooperation through negotiated task allocation and achievement. In: Proceedings 1999 IEEE International Conference on Robotics and Automation (Cat. No. 99CH36288C), vol. 2, pp. 1234–1239. IEEE, Piscataway (1999)

10.

Campos, M., Bonabeau, E., Theraulaz, G., Deneubourg, J.L.: Dynamic scheduling and division of labor in social insects. Adaptive Behav. 8(2), 83–95 (2000)CrossRef

11.

Chen, H.X., Nan, Y., Yang, Y.: Multi-UAV reconnaissance task assignment for heterogeneous targets based on modified symbiotic organisms search algorithm. Sensors 19(3), 734 (2019)CrossRef

12.

Chen, Y., Xie, L., He, W., Jiang, Q., Xu, J.: An improved A* algorithm based on divide-and-conquer method for golf unmanned cart path planning. In: International Conference on Artificial Intelligence for Communications and Networks, pp. 497–505. Springer, Berlin (2019)

13.

Choi, H.L., Brunet, L., How, J.P.: Consensus-based decentralized auctions for robust task allocation. IEEE Trans. Rob. 25(4), 912–926 (2009)CrossRef

14.

Coello, C.A.C., Pulido, G.T., Lechuga, M.S.: Handling multiple objectives with particle swarm optimization. IEEE Trans. Evol. Comput. 8(3), 256–279 (2004)CrossRef

15.

Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2), 182–197 (2002)CrossRef

16.

Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1(1), 269–271 (1959)MathSciNetMATHCrossRef

17.

Dorigo, M., Stützle, T.: The ant colony optimization metaheuristic: Algorithms, applications, and advances. In: Handbook of Metaheuristics, pp. 250–285. Springer, Berlin (2003)

18.

Duan, H.b., Zhang, X.y., Wu, J., Ma, G.j.: Max-min adaptive ant colony optimization approach to multi-UAVs coordinated trajectory replanning in dynamic and uncertain environments. J. Bionic Eng. 6(2), 161–173 (2009)

19.

Edison, E., Shima, T.: Integrated task assignment and path optimization for cooperating uninhabited aerial vehicles using genetic algorithms. Comput. Operat. Res. 38(1), 340–356 (2011)MathSciNetMATHCrossRef

20.

Ergezer, H., Leblebicioglu, K.: Path planning for UAVs for maximum information collection. IEEE Trans. Aerosp. Electro. Syst. 49(1), 502–520 (2013)CrossRef

21.

Ergezer, H., Leblebicioğlu, K.: 3D path planning for multiple UAVs for maximum information collection. J. Intell. Rob. Syst. 73(1–4), 737–762 (2014)CrossRef

22.

Fei, S., Yan, C., Lin-Cheng, S.: UAV cooperative multi-task assignment based on ant colony algorithm. Acta Aeronautica et Astronautica Sinica 29, 188–s189 (2008)

23.

Fiorini, P., Shiller, Z.: Motion planning in dynamic environments using velocity obstacles. Int. J. Rob. Res. 17(7), 760–772 (1998)CrossRef

24.

Foo, J.L., Knutzon, J., Oliver, J., Winer, E.: Three-dimensional path planning of unmanned aerial vehicles using particle swarm optimization. In: 11th AIAA/ISSMO Multidisciplinary Analysis and Optimization Conference, p. 6995 (2006)

25.

Fraichard, T.: Trajectory planning in a dynamic workspace: a’ state-time space’approach. Adv. Rob. 13(1), 75–94 (1998)CrossRef

26.

Fu, Y., Ding, M., Zhou, C.: Phase angle-encoded and quantum-behaved particle swarm optimization applied to three-dimensional route planning for UAV. IEEE Trans. Syst. Man Cybern. Part A Syst. Humans 42(2), 511–526 (2012)CrossRef

27.

Gallinari, P.: Training of modular neural net systems. In: The Handbook of Brain Theory and Neural Networks, pp. 582–585. MIT Press, Cambridge (1998)

28.

Gautam, S.A., Verma, N.: Path planning for unmanned aerial vehicle based on genetic algorithm & artificial neural network in 3D. In: 2014 International Conference on Data Mining and Intelligent Computing (ICDMIC), pp. 1–5. IEEE, Piscataway (2014)

29.

Gerkey, B.P., Mataric, M.J.: Sold!: Auction methods for multirobot coordination. IEEE Trans. Rob. Autom. 18(5), 758–768 (2002)CrossRef

30.

Gerkey, B.P., Matarić, M.J.: A formal analysis and taxonomy of task allocation in multi-robot systems. Int. J. Rob. Res. 23(9), 939–954 (2004)CrossRef

31.

Goerzen, C., Kong, Z., Mettler, B.: A survey of motion planning algorithms from the perspective of autonomous UAV guidance. J. Intell. Rob. Syst. 57(1–4), 65 (2010)MATHCrossRef

32.

González, V., Monje, C., Moreno, L., Balaguer, C.: UAVs mission planning with flight level constraint using fast marching square method. Rob. Auton. Syst. 94, 162–171 (2017)CrossRef

33.

Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4(2), 100–107 (1968)CrossRef

34.

Hartigan, J.A., Wong, M.A.: Algorithm as 136: A k-means clustering algorithm. J. R. Stat. Soc. Ser. C (Appl. Stat.) 28(1), 100–108 (1979)

35.

Holland, J.H., et al.: Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. MIT Press, Cambridge (1992)CrossRef

36.

Jain, A.K.: Data clustering: 50 years beyond k-means. Pattern Recogn. Lett. 31(8), 651–666 (2010)CrossRef

37.

Kant, K., Zucker, S.W.: Toward efficient trajectory planning: The path-velocity decomposition. Int. J. Rob. Res. 5(3), 72–89 (1986)CrossRef

38.

Kanungo, T., Mount, D.M., Netanyahu, N.S., Piatko, C.D., Silverman, R., Wu, A.Y.: An efficient k-means clustering algorithm: Analysis and implementation. IEEE Trans. Pattern Anal. Mach. Intell. 24(7), 881–892 (2002)MATHCrossRef

39.

Karaman, S., Frazzoli, E.: Optimal kinodynamic motion planning using incremental sampling-based methods. In: 49th IEEE Conference on Decision and Control (CDC), pp. 7681–7687. IEEE, Piscataway (2010)

40.

Kavralu, L.E., Svestka, P., Latombe, J.C., Overmars, M.H.: Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans. Rob. Autom. 12(4), 566–580 (1996)CrossRef

41.

Kennedy, J., Eberhart, R.: Particle swarm optimization. In: Proceedings., IEEE International Conference on Neural Networks, 1995, vol. 4, pp. 1942–1948. IEEE, Piscataway (1995)

42.

Kim, M.H., Baik, H., Lee, S.: Response threshold model based UAV search planning and task allocation. J. Intell. Rob. Syst. 75(3–4), 625–640 (2014)CrossRef

43.

Lamont, G.B., Slear, J.N., Melendez, K.: UAV swarm mission planning and routing using multi-objective evolutionary algorithms. In: 2007 IEEE Symposium on Computational Intelligence in Multi-Criteria Decision-Making, pp. 10–20. IEEE, Piscataway (2007)

44.

Landén, D., Heintz, F., Doherty, P.: Complex task allocation in mixed-initiative delegation: a UAV case study. In: International Conference on Principles and Practice of Multi-Agent Systems, pp. 288–303. Springer, Berlin (2010)

45.

Latombe, J.C.: Robot Motion Planning, vol. 124. Springer Science & Business Media, Berlin (2012)

46.

LaValle, S.M.: Rapidly-Exploring Random Trees: A New Tool for Path Planning. CiteSeer (1998)

47.

Lim, K.K., Ong, Y.S., Lim, M.H., Chen, X., Agarwal, A.: Hybrid ant colony algorithms for path planning in sparse graphs. Soft Comput. 12(10), 981–994 (2008)CrossRef

48.

Lin, W., Wang, J.Z., Liang, C., Qi, D.: A threshold-based dynamic resource allocation scheme for cloud computing. Procedia Eng. 23, 695–703 (2011)CrossRef

49.

Liu, J., Wang, W., Li, X., Wang, T., Bai, S., Wang, Y.: Solving a multi-objective mission planning problem for UAV swarms with an improved nsga-iii algorithm. Int. J. Comput. Intell. Systems 11(1), 1067–1081 (2018)CrossRef

50.

Liu, J., Wang, W., Li, X., Wang, T., Wang, T.: A motif-based mission planning method for UAV swarms considering dynamic reconfiguration. Defence Sci. J. 68(2), 159–166 (2018)CrossRef

51.

Lloyd, S.: Least squares quantization in PCM. IEEE Trans. Inf. Theory 28(2), 129–137 (1982)MathSciNetMATHCrossRef

52.

Lu, B.L., Ito, M.: Task decomposition and module combination based on class relations: a modular neural network for pattern classification. IEEE Trans. Neur. Netw. 10(5), 1244–1256 (1999)CrossRef

53.

Mac, T.T., Copot, C., Tran, D.T., De Keyser, R.: Heuristic approaches in robot path planning: a survey. Rob. Auton. Syst. 86, 13–28 (2016)CrossRef

54.

MacQueen, J., et al.: Some methods for classification and analysis of multivariate observations. In: Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, vol. 1, pp. 281–297. Oakland (1967)

55.

Masehian, E., Amin-Naseri, M.: A voronoi diagram-visibility graph-potential field compound algorithm for robot path planning. J. Rob. Syst. 21(6), 275–300 (2004)CrossRef

56.

Máthé, K., Buşoniu, L.: Vision and control for UAVs: a survey of general methods and of inexpensive platforms for infrastructure inspection. Sensors 15(7), 14,887–14,916 (2015)CrossRef

57.

Miettinen, K.: Nonlinear Multiobjective Optimization, vol. 12. Springer Science & Business Media, Berlin (1999)MATH

58.

Nikolos, I.K., Valavanis, K.P., Tsourveloudis, N.C., Kostaras, A.N.: Evolutionary algorithm based offline/online path planner for UAV navigation. IEEE Trans. Syst. Man Cybern. Part B (Cybern.) 33(6), 898–912 (2003)

59.

Nikolos, I.K., Zografos, E.S., Brintaki, A.N.: UAV path planning using evolutionary algorithms. In: Innovations in Intelligent Machines-1, pp. 77–111. Springer, Berlin (2007)

60.

Oh, G., Kim, Y., Ahn, J., Choi, H.L.: Market-based distributed task assignment of multiple unmanned aerial vehicles for cooperative timing mission. J. Aircraft 54(6), 2298–2310 (2017)CrossRef

61.

Paden, B., Čáp, M., Yong, S.Z., Yershov, D., Frazzoli, E.: A survey of motion planning and control techniques for self-driving urban vehicles. IEEE Trans. Intell. Veh. 1(1), 33–55 (2016)CrossRef

62.

Peng, X., Xu, D.: Intelligent online path planning for UAVs in adversarial environments. Int. J. Adv. Rob. Syst. 9(1), 3 (2012)CrossRef

63.

Peng, Z.h., Wu, J.p., Chen, J.: Three-dimensional multi-constraint route planning of unmanned aerial vehicle low-altitude penetration based on coevolutionary multi-agent genetic algorithm. J. Cent. South Univ. Technol. 18(5), 1502 (2011)

64.

Phung, M.D., Quach, C.H., Dinh, T.H., Ha, Q.: Enhanced discrete particle swarm optimization path planning for UAV vision-based surface inspection. Autom. Constr. 81, 25–33 (2017)CrossRef

65.

Pohl, A.J., Lamont, G.B.: Multi-objective UAV mission planning using evolutionary computation. In: 2008 Winter Simulation Conference, pp. 1268–1279. IEEE, Piscataway (2008)

66.

Ramirez-Atencia, C., Camacho, D.: Extending QGroundcontrol for automated mission planning of UAVs. Sensors 18(7), 2339 (2018)CrossRef

67.

Ramirez-Atencia, C., R-Moreno, M.D., Camacho, D.: Handling swarm of UAVs based on evolutionary multi-objective optimization. Prog. Artif. Intell. 6(3), 263–274 (2017)CrossRef

68.

Reif, J.H.: Complexity of the mover’s problem and generalizations. In: 20th Annual Symposium on Foundations of Computer Science (SFCS 1979), pp. 421–427. IEEE, Piscataway (1979)

69.

Ren, X., Zhang, L., Ahmad, S., Nie, D., Yang, F., Xiang, L., Wang, Q., Shen, D.: Task decomposition and synchronization for semantic biomedical image segmentation (2019). Preprint arXiv:1905.08720

70.

Richards, A., Bellingham, J., Tillerson, M., How, J.: Coordination and control of multiple UAVs. In: AIAA Guidance, Navigation, and Control Conference and Exhibit, p. 4588 (2002)

71.

Richter, C., Bry, A., Roy, N.: Polynomial trajectory planning for aggressive quadrotor flight in dense indoor environments. In: Robotics Research, pp. 649–666. Springer, Berlin (2016)

72.

Salman, A., Ahmad, I., Al-Madani, S.: Particle swarm optimization for task assignment problem. Microprocess. Microsyst. 26(8), 363–371 (2002)CrossRef

73.

Salvo, G., Caruso, L., Scordo, A.: Urban traffic analysis through an UAV. Procedia-Soc. Behav. Sci. 111, 1083–1091 (2014)CrossRef

74.

Schumacher, C., Chandler, P., Pachter, M., Pachter, L.: Constrained optimization for UAV task assignment. In: AIAA Guidance, Navigation, and Control Conference and Exhibit, p. 5352 (2004)

75.

Shima, T., Schumacher, C.: Assigning cooperating UAVs to simultaneous tasks on consecutive targets using genetic algorithms. J. Oper. Res. Soc. 60(7), 973–982 (2009)MATHCrossRef

76.

Shorakaei, H., Vahdani, M., Imani, B., Gholami, A.: Optimal cooperative path planning of unmanned aerial vehicles by a parallel genetic algorithm. Robotica 34(4), 823–836 (2016)CrossRef

77.

Stentz, A.: Optimal and efficient path planning for partially known environments. In: Intelligent Unmanned Ground Vehicles, pp. 203–220. Springer, Berlin (1997)

78.

Stone, P., Veloso, M.: Task decomposition, dynamic role assignment, and low-bandwidth communication for real-time strategic teamwork. Artif. Intell. 110(2), 241–273 (1999)MATHCrossRef

79.

Suzuki, S., Komatsu, Y., Yonezawa, S., Masui, K., Tomita, H.: Online four-dimensional flight trajectory search and its flight testing. In: AIAA Guidance, Navigation, and Control Conference and Exhibit, p. 6475 (2005)

80.

Van Den Berg, J.P., Overmars, M.H.: Roadmap-based motion planning in dynamic environments. IEEE Trans. Rob. 21(5), 885–897 (2005)CrossRef

81.

Wagstaff, K., Cardie, C., Rogers, S., Schrödl, S., et al.: Constrained k-means clustering with background knowledge. In: Proceedings of the Eighteenth International Conference on Machine Learning, vol. 1, pp. 577–584 (2001)

82.

Wang, L., Su, F., Zhu, H., Shen, L.: Active sensing based cooperative target tracking using UAVs in an urban area. In: 2010 2nd International Conference on Advanced Computer Control, vol. 2, pp. 486–491. IEEE, Piscataway (2010)

83.

Yan, F., Liu, Y.S., Xiao, J.Z.: Path planning in complex 3D environments using a probabilistic roadmap method. Int. J. Autom. Comput. 10(6), 525–533 (2013)CrossRef

84.

Yan, Z., Jouandeau, N., Cherif, A.A.: A survey and analysis of multi-robot coordination. Int. J. Adv. Rob. Syst. 10(12), 399 (2013)CrossRef

85.

Yang, Y., Zhou, C., Tian, Y.: Swarm robots task allocation based on response threshold model. In: 2009 4th International Conference on Autonomous Robots and Agents, pp. 171–176. IEEE, Piscataway (2009)

86.

Yang, L., Qi, J., Song, D., Xiao, J., Han, J., Xia, Y.: Survey of robot 3D path planning algorithms. J. Control Sci. Eng. 2016, 5 (2016)

87.

Yazdani, D., Omidvar, M.N., Branke, J., Nguyen, T.T., Yao, X.: Scaling up dynamic optimization problems: A divide-and-conquer approach. IEEE Trans. Evol. Comput. 24, 1–15 (2019)CrossRef

88.

Yershova, A., Jaillet, L., Siméon, T., LaValle, S.M.: Dynamic-domain RRTs: Efficient exploration by controlling the sampling domain. In: Proceedings of the 2005 IEEE International Conference on Robotics and Automation (2005)

89.

Yu, X., Chen, W.N., Gu, T., Yuan, H., Zhang, H., Zhang, J.: Aco-A*: Ant colony optimization plus A* for 3d traveling in environments with dense obstacles. IEEE Trans. Evol. Comput. 23, 617–631 (2018)CrossRef

90.

Zhang, B., Duan, H.: Predator-prey pigeon-inspired optimization for UAV three-dimensional path planning. In: International Conference in Swarm Intelligence, pp. 96–105. Springer, Berlin (2014)

91.

Zhang, B., Duan, H.: Three-dimensional path planning for uninhabited combat aerial vehicle based on predator-prey pigeon-inspired optimization in dynamic environment. IEEE/ACM Trans. Comput. Biol. Bioinform. 14(1), 97–107 (2015)CrossRef

92.

Zhang, S., Zhou, Y., Li, Z., Pan, W.: Grey wolf optimizer for unmanned combat aerial vehicle path planning. Adv. Eng. Softw. 99, 121–136 (2016)CrossRef

93.

Zhang, L., Chen, J., Deng, F., Bi, Y., Phang, S.K., Chen, X.: Trajectory planning for improving vision-based target geolocation performance using a quad-rotor UAV. IEEE Trans. Aerosp. Electron. Syst. 55, 2382–2394 (2018)CrossRef

94.

Zhou, Z., Feng, J., Gu, B., Ai, B., Mumtaz, S., Rodriguez, J., Guizani, M.: When mobile crowd sensing meets UAV: energy-efficient task assignment and route planning. IEEE Trans. Commun. 66(11), 5526–5538 (2018)CrossRef

Title: Mission Planning for Shepherding a Swarm of Uninhabited Aerial Vehicles
Authors: Jing Liu
Sreenatha Anavatti
Matthew Garratt
Hussein A. Abbass
Publisher: Springer International Publishing
Book: Shepherding UxVs for Human-Swarm Teaming
Print ISBN: 978-3-030-60897-2

Electronic ISBN: 978-3-030-60898-9

Copyright Year: 2021
DOI: https://doi.org/10.1007/978-3-030-60898-9_5

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner